A Value-at-Risk (VAR) approach to routing rail hazmat shipments

Hazardous materials (hazmat) accidents are rare though the consequences could be disastrous. Given the possibility of low probability – high consequence event, a risk-averse routing hazmat shipment is necessary. We propose a value-at-risk (VaR) approach to route rail hazmat shipments, using the best train configuration, over a given railroad network with limited number of train services such that the transport risk as measured by VaR is minimized. Freight train derailment reports of the Federal Railroad Administration were analyzed to develop expressions that would incorporate characteristics of railroad accidents, and then to estimate the different inputs. The proposed methodology was used to study several problem instances generated using the realistic network of a railroad operator, and to demonstrate that it is possible to develop different routes for shipments depending on the risk preference of the decision maker.     

A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem

This paper deals with a practical tramp ship routing problem while taking into account different bunker prices at different ports, which is called the joint tramp ship routing and bunkering (JSRB) problem. Given a set of cargoes to be transported and a set of ports with different bunker prices, the proposed problem determines how to route ships to carry the cargoes and the amount of bunker to purchase at each port, in order to maximize the total profit. After building an integer linear programming model for the JSRB problem, we propose a tailored branch-and-price (B&P) solution approach. The B&P approach incorporates an efficient method for obtaining the optimal bunkering policy and a novel dominance rule for detecting inefficient routing options. The B&P approach is tested with randomly generated large-scale instances derived from real-world planning problems. All of the instances can be solved efficiently. Moreover, the proposed approach for the JSRB problem outperforms the conventional sequential planning approach and can incorporate the prediction of future cargo demand to avoid making myopic decisions.     

Recent success stories on integrated optimization of railway systems

Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain developing mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice (e.g. Cacchiani et al., 2014; Borndörfer et al., 2010), with a few notable exceptions. In this paper we address three individual success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will discuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that mathematical optimization can support the planning of railway resources. Thus, mathematical models and optimization can lead to a greater efficiency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.     

Real-time energy consumption minimization in railway networks

A new timetable must be calculated in real-time when train operations are perturbed. Although energy consumption is becoming a central issue both from the environmental and economic perspective, it is usually neglected in the timetable recalculation. In this paper, we formalize the real-time Energy Consumption Minimization Problem (rtECMP). It finds in real-time the driving regime combination for each train that minimizes energy consumption, respecting given routing and precedences between trains. In the possible driving regime combinations, train routes are split in subsections for which one of the regimes resulting from the Pontryagin’s Maximum Principle is to be chosen. We model the trade-off between minimizing energy consumption and total delay by considering as objective function their weighted sum. We propose an algorithm to solve the rtECMP, based on the solution of a mixed-integer linear programming model. We test this algorithm on the Pierrefitte-Gonesse control area, which is a critical area in France with dense mixed traffic. The results show that the problem is tractable and an optimal solution of the model tackled can often be found in real-time for most instances.     

A decomposition-based iterative optimization algorithm for traveling salesman problem with drone

This study investigates a new delivery problem that has emerged after the attempts of several e-commerce and logistics firms to deploy drones in their operations to increase efficiency and reduce delivery times. In this problem, a delivery truck that carries a drone on its roof serves customers in coordination with a drone. The drone is considered to complement the truck due to its cost-efficiency and ability to access difficult terrains and to travel without exposure to congestion. This study presents an iterative algorithm that is based on a decomposition approach to minimize delivery completion time. In the first stage of the proposed methodology, the truck route and the customers assigned to the drone are determined. In the second stage, a mixed-integer linear programming model is solved to optimize the drone route by fixing the routing and the assignment decisions that are made in the first stage. Beginning with the shortest truck route, the assignment and the routing decisions are iteratively improved. The solution times of our algorithm are compared with the solution times of the state-of-the-art formulations that are solved by CPLEX. The results demonstrate that our algorithm yields shorter solution times for the instances that we generated with the specified parameters. An optimization-based heuristic algorithm, which obtains solutions for medium-sized instances, is developed by reducing the feasible search area.     

Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem

The traditional distribution planning problem in a supply chain has often been studied mainly with a focus on economic benefits. The growing concern about the effects of anthropogenic pollutions has forced researchers and supply chain practitioners to address the socio-environmental concerns. This research study focuses on incorporating the environmental impact on route design problem. In this work, the aim is to integrate both the objectives, namely economic cost and emission cost reduction for a capacitated multi-depot green vehicle routing problem. The proposed models are a significant contribution to the field of research in green vehicle routing problem at the operational level. The formulated integer linear programming model is solved for a set of small scale instances using LINGO solver. A computationally efficient Ant Colony Optimization (ACO) based meta-heuristic is developed for solving both small scale and large scale problem instances in reasonable amount of time. For solving large scale instances, the performance of the proposed ACO based meta-heuristic is improved by integrating it with a variable neighbourhood search.     

Optimizing train stopping patterns and schedules for high-speed passenger rail corridors

High-speed railway (HSR) systems have been developing rapidly in China and various other countries throughout the past decade; as a result, the question of how to efficiently operate such large-scale systems is posing a new challenge to the railway industry. A high-quality train timetable should take full advantage of the system’s capacity to meet transportation demands. This paper presents a mathematical model for optimizing a train timetable for an HSR system. We propose an innovative methodology using a column-generation-based heuristic algorithm to simultaneously account for both passenger service demands and train scheduling. First, we transform a mathematical model into a simple linear programming problem using a Lagrangian relaxation method. Second, we search for the optimal solution by updating the restricted master problem (RMP) and the sub-problems in an iterative process using the column-generation-based algorithm. Finally, we consider the Beijing–Shanghai HSR line as a real-world application of the methodology; the results show that the optimization model and algorithm can improve the defined profit function by approximately 30% and increase the line capacity by approximately 27%. This methodology has the potential to improve the service level and capacity of HSR lines with no additional high-cost capital investment (e.g., the addition of new tracks, bridges and tunnels on the mainline and/or at stations).     

The vehicle platooning problem: Computational complexity and heuristics

We create a mathematical framework for modeling trucks traveling in road networks, and we define a routing problem called the platooning problem. We prove that this problem is NP-hard, even when the graph used to represent the road network is planar. We present integer linear programming formulations for instances of the platooning problem where deadlines are discarded, which we call the unlimited platooning problem. These allow us to calculate fuel-optimal solutions to the platooning problem for large-scale, real-world examples. The problems solved are orders of magnitude larger than problems previously solved exactly in the literature. We present several heuristics and compare their performance with the optimal solutions on the German Autobahn road network. The proposed heuristics find optimal or near-optimal solutions in most of the problem instances considered, especially when a final local search is applied. Assuming a fuel reduction factor of 10% from platooning, we find fuel savings from platooning of 1–2% for as few as 10 trucks in the road network; the percentage of savings increases with the number of trucks. If all trucks start at the same point, savings of up to 9% are obtained for only 200 trucks.     

Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network

Based on train scheduling, this paper puts forward a multi-objective optimization model for train routing on high-speed railway network, which can offer an important reference for train plan to provide a better service. The model does not only consider the average travel time of trains, but also take the energy consumption and the user satisfaction into account. Based on this model, an improved GA is designed to solve the train routing problem. The simulation results demonstrate that the accurate algorithm is suitable for a small-scale network, while the improved genetic algorithm based on train control (GATC) applies to a large-scale network. Finally, a sensitivity analysis of the parameters is performed to obtain the ideal parameters; a perturbation analysis shows that the proposed method can quickly handle the train disturbance.     

A tabu search algorithm to solve the integrated planning of container on an inter-terminal network connected with a hinterland rail network

Transport demand for containers has been increasing for decades, which places pressure on road transport. As a result, rail transport is stimulated to provide better intermodal freight transport services. This paper investigates mathematical models for the planning of container movements in a port area, integrating the inter-terminal transport of containers (ITT, within the port area) with the rail freight formation and transport process (towards the hinterland). An integer linear programming model is used to formulate the container transport across operations at container terminals, the network interconnecting them, railway yards and the railway networks towards the hinterland. A tabu search algorithm is proposed to solve the problem. The practical applicability of the algorithm is tested in a realistic infrastructure case and different demand scenarios. Our results show the degree by which internal (ITT) and external (hinterland) transport processes interact, and the potential for improvement of overall operations when the integrated optimization proposed is used. Instead, if the planning of containers in the ITT system is optimized as a stand-alone problem, the railway terminals may suffer from longer delay times or additional train cancellations. When planning the transport of 4060 TEU containers within one day, the benefits of the ITT planning without considering railway operations account for 17% ITT cost reduction but 93% railway operational cost growth, while the benefits of integrating ITT and railway account for a reduction of 20% in ITT cost and 44% in railway operational costs.     

Prediction of ground vibration amplitudes due to urban railway traffic using quantitative and qualitative field data

The growth of railway transport in urban areas has lead to an increase in ground vibrations enhancing their negative environmental impact. Therefore is mandatory to predict and control ground vibrations. This work presents a methodology for the determination of prediction models of ground vibration amplitudes due to railway train circulation in urban environments. Using quantitative predictors (train speed and distance) and qualitative predictors (railway track type, dominant geology and building type), being the use of the latter predictors justified by the fact that, most frequently, quantitative parameters are very difficult to obtain in the urban environment due to their characterization. Thus, a detailed statistical study based on the proposal and validation of multiple linear regression models, is successfully applied in order to predict vibration amplitudes produced by railway train circulation, in the considered domain, as function of quantitative and qualitative predictors, easily obtained in field work. A multiple linear regression model for ground vibration prediction due to underground railway traffic has been presented for the Lisbon area.     

On fitting mode specific constants in the presence of new options in RP/SP models

We treat the problem of fitting alternative specific constants (ASC) in models estimated with a mixture of revealed preference (RP) and stated preference (SP) data to forecast the market shares of new alternatives. This important problem can have non-trivial solutions, particularly when some of the SP alternatives are completely revamped versions of existing ones (i.e., an advanced passenger train replacing a normal railway service). As there is no explicit treatment of this problem in the literature we examined it in depth and illustrated it empirically using data especially collected to analyse mode choice in a corridor to the West of Cagliari. We propose a hopefully useful guide to this art (as no practical recipes seem to serve all purposes). Careful specification of the systematic component of utility functions in RP and SP, including the ASC, serves to illuminate the true nature of the underlying error structure in the different data sets, yielding superior forecasting models.     

Train routing and timetabling problem for heterogeneous train traffic with switchable scheduling rules

This paper proposes a mathematical model for the train routing and timetabling problem that allows a train to occasionally switch to the opposite track when it is not occupied, which we define it as switchable scheduling rule. The layouts of stations are taken into account in the proposed mathematical model to avoid head-on and rear-end collisions in stations. In this paper, train timetable could be scheduled by three different scheduling rules, i.e., no switchable scheduling rule (No-SSR) which allows trains switching track neither at stations and segments, incomplete switchable scheduling rule (In-SSR) which allows trains switching track at stations but not at segments, and complete switchable scheduling rule (Co-SSR) which allows trains switching track both at stations and segments. Numerical experiments are carried out on a small-scale railway corridor and a large-scale railway corridor based on Beijing–Shanghai high-speed railway (HSR) corridor respectively. The results of case studies indicate that Co-SSR outperforms the other two scheduling rules. It is also found that the proposed model can improve train operational efficiency.     

A constraint generation algorithm for the construction of periodic railway timetables

This paper addresses the problem of constructing periodic timetables for train operations. We use a mathematical model consisting of periodic time window constraints by means of which arrival and departure times can be related pairwise on a clock, rather than on a linear time axis. Constructing a timetable, then, means solving a set of such constraints. This problem is known to be hard, i.e. it is NP-complete. We describe a new algorithm to solve the problem based on constraint generation and work out a real-life example. It appears that, for problem instances of modest, yet non-trivial, size, the algorithm performs very well, which opens a way to thorough performance analysis of railway systems by studying a large number of possible future timetables.     

An optimization model for integrated planning of railway traffic and network maintenance

Railway transportation systems are important for society and have many challenging and important planning problems. Train services as well as maintenance of a railway network need to be scheduled efficiently, but have mostly been treated as two separate planning problems. Since these activities are mutually exclusive they must be coordinated and should ideally be planned together. In this paper we present a mixed integer programming model for solving an integrated railway traffic and network maintenance problem. The aim is to find a long term tactical plan that optimally schedules train free windows sufficient for a given volume of regular maintenance together with the wanted train traffic. A spatial and temporal aggregation is used for controlling the available network capacity. The properties of the proposed model are analyzed and computational experiments on various synthetic problem instances are reported. Model extensions and possible modifications are discussed as well as future research directions.     

A delay propagation algorithm for large-scale railway traffic networks

In scheduled railway traffic networks a single delayed train may cause a domino effect of secondary delays over the entire network, which is a main concern to planners and dispatchers. This paper presents a model and an algorithm to compute the propagation of initial delays over a periodic railway timetable. The railway system is modelled as a linear system in max-plus algebra including zero-order dynamics corresponding to delay propagation within a timetable period. A timed event graph representation is exploited in an effective graph algorithm that computes the propagation of train delays using a bucket implementation to store the propagated delays. The behaviour of the delay propagation and the convergence of the algorithm is analysed depending on timetable properties such as realisability and stability. Different types of delays and delay behaviour are discussed, including primary and secondary delays, structural delays, periodic delay regimes, and delay explosion. A decomposition method based on linearity is introduced to deal with structural and initial delays separately. The algorithm can be applied to large-scale scheduled railway traffic networks in real-time applications such as interactive timetable stability analysis and decision support systems to assist train dispatchers.     

A branch-and-price approach for solving the train unit scheduling problem

We propose a branch-and-price approach for solving the integer multicommodity flow model for the network-level train unit scheduling problem (TUSP). Given a train operator’s fixed timetable and a fleet of train units of different types, the TUSP aims at determining an assignment plan such that each train trip in the timetable is appropriately covered by a single or coupled train units. The TUSP is challenging due to its complex nature. Our branch-and-price approach includes a branching system with multiple branching rules for satisfying real-world requirements that are difficult to realize by linear constraints, such as unit type coupling compatibility relations and locations banned for coupling/decoupling. The approach also benefits from an adaptive node selection method, a column inheritance strategy and a feature of estimated upper bounds with node reservation functions. The branch-and-price solver designed for TUSP is capable of handling instances of up to about 500 train trips. Computational experiments were conducted based on real-world problem instances from First ScotRail. The results are satisfied by rail practitioners and are generally competitive or better than the manual ones.     

The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems

Most of the studies address issues relating to the delivery from satellites to customers, which is throughout the end part of the linehaul-delivery system. Differing from the long-term strategic problems including the two-echelon vehicle routing problem (2E-VRP), the two-echelon location routing problem (2E-LRP) and the truck and trailer routing problem (TTRP) which make location decisions in depots or satellites, the paper introduces a short-term tactical problem named the two-echelon time-constrained vehicle routing problem in linehaul-delivery systems (2E-TVRP) that does not involve location decisions. The linehaul level and the delivery level are linked through city distribution centers (CDCs) located on the outskirts of cities. The 2E-TVRP has inter-CDC linehaul on the first level and urban delivery from CDCs to satellites on the second level. Vehicle routes on different levels are interacted by time constraints. A mixed integer nonlinear programming model for the 2E-TVRP is put forward, and a mixed integer linear programming model is used as the benchmark model. The Clarke and Wright savings heuristic algorithm (CW) improved by a local search phase is adopted. The 2E-TVRP formulations and the heuristic algorithm are tested by using 140 randomly-generated instances with up to 10 CDCs and 500 satellites. The computational results indicate that the heuristic can effectively solve various instances of the 2E-TVRP.     

An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network

In practice, a train-conflict resolution is decentralized around dispatchers each of whom controls a few segments in a global railway network with her rule-of-thumb to operational data. Conceptually, the global sub-optimality or infeasibility of the decentralized system is resolved by a network controller who coordinates the dispatchers and train operators at the lower layers on a real-time basis. However, such notion of a multi-layer system cannot be effectual unless the top layer is able to provide a global solution soon enough for the dynamic lower layers to adapt in a seamless manner. Unfortunately, a train-conflict resolution problem is NP-hard as formally established in this paper and an effective solution method traded off between computation time and solution quality has been lacking in literature. Thus, we propose a column-generation-based algorithm that exploits the separability of the problem. A key ingredient of the algorithm is an efficient heuristic for the pricing subproblem for column generation. Tested on the real data from the Seoul metropolitan railway network, the algorithm provides near-optimal conflict-free timetables in a few seconds for most cases. The performance of the proposed algorithm is compared to the ones of the previous MIP-based heuristic by Törnquist and Persson (2007) and the priority-based heuristic by Sahin (1999).     

Non-discriminatory train dispatching in a rail transport market with multiple competing and collaborative train operating companies

Train dispatching is vital for the punctuality of train services, which is critical for a train operating company (TOC) to maintain its competitiveness. Due to the introduction of competition in the railway transport market, the issue of discrimination is attracting more and more attention. This paper focuses on delivering non-discriminatory train dispatching solutions while multiple TOCs are competing in a rail transport market, and investigating impacting factors of the inequity of train dispatching solutions. A mixed integer linear programming (MILP) model is first proposed, in which the inequity of competitors (i.e., trains and TOCs) is formalized by a set of constraints. In order to provide a more flexible framework, a model is further reformulated where the inequity of competitors is formalized as the maximum individual deviation of competitors’ delay cost from average delay cost in the objective function. Complex infrastructure capacity constraints are considered and modelled through a big M-based approach. The proposed models are solved by a standard MILP solver. A set of comprehensive experiments is conducted on a real-world dataset adapted from the Dutch railway network to test the efficiency, effectiveness, and applicability of the proposed models, as well as determine the trade-off between train delays and delay equity.