1,721,169 research outputs found
A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs
No full textWe study convex multi-objective Mixed Integer Non-Linear Programming problems (MINLPs), which are characterized by multiple objective functions and non linearities, features that appear in real-world applications. To derive a good approximated set of non-dominated points for convex multi-objective MINLPs, we propose a heuristic based on a branch-and-bound algorithm. It starts with a set of feasible points, obtained, at the root node of the enumeration tree, by iteratively solving, with an ε-constraint method, a single objective model that incorporates the other objective functions as constraints. Lower bounds are derived by optimally solving Non-Linear Programming problems (NLPs). Each leaf node of the enumeration tree corresponds to a convex multi-objective NLP, which is solved heuristically by varying the weights in a weighted sum approach. In order to improve the obtained points and remove dominated ones, a tailored refinement procedure is designed. Although the proposed method makes no assumptions on the number of objective functions nor on the type of the variables, we test it on bi-objective mixed binary problems. In particular, as a proof-of-concept, we tested the proposed heuristic algorithm on instances of a real-world application concerning power generation, and instances of the convex biobjective Non-Linear Knapsack Problem. We compared the obtained results with those derived by well-known scalarization methods, showing the effectiveness of the proposed method
Timetable Optimization for High-Speed Trains at Chinese Railways
No full textWe study the Train Timetabling Problem (TTP) of the high-speed trains at the Chinese railways. TTP calls for determining, in the planning phase, an optimal schedule for a given set of trains, while satisfying track capacity occupation constraints. In this work, we are given on input a set of feasible timetables for the trains already planned along a double-track high-speed line, and the main goal consists of scheduling as many additional trains as possible. Beside the main goal, a second objective is to obtain a regular schedule, i.e. a schedule showing regularity in the train frequency. We model TTP on a time-space graph and propose a heuristic algorithm for it. Preliminary computational results on real-world instances of the high-speed line from Beijing to Shanghai in China are reported
An Effective Peak Period Heuristic for Railway Rolling Stock Planning
No full textIn this work we tackle a real-world application of railway rolling stock planning, known as the train unit assignment problem (TUAP), arising for a regional train operator in the North of Italy. Given a set of timetabled train trips, each with a demand of passenger seats, as well as a set of train units, each with a cost and a number of available passenger seats, the goal is to determine the minimum cost daily assignment of the train units to the trips, satisfying a set of operational constraints. The context we focus on is that of a competitive bid process whereby a train operator competes to win a contract for providing rolling stock circulation in a regional railway network. From a theoretical perspective, we prove that even a relaxation of the TUAP is NP-hard. To solve the TUAP, we propose a heuristic algorithm based on the optimal solution of the restricted problem associated with a peak period (i.e., a period of the day in which many trips overlapping in time must be performed). The heuristic algorithm is tested on real-world instances provided by the regional train operator and on larger realistic instances of TUAP. The obtained results are compared with those of previously developed methods, showing the effectiveness of the new algorithm that finds optimal or near-optimal solutions and outperforms, for what concerns both the solution quality and the computing time, the considered methods from the literature
A tutorial on non-periodic train timetabling and platforming problems
No full textIn this tutorial, we give an overview of two fundamental problems arising in the optimization of a railway system: the train timetabling problem (TTP), in its non-periodic version, and the train platforming problem (TPP). We consider for both problems the planning stage, i.e. we face them from a tactical point of view. These problems correspond to two main phases that are usually optimized in close sequence by the railway infrastructure manager. First, in the TTP phase, a schedule of the trains in a railway network is determined. A schedule consists of the arrival and departure times of each train at each (visited) station. Second, in the TPP phase, one needs to determine a stopping platform and a routing for each train inside each (visited) station, according to the schedule found in the TTP phase. Due to the complexity of the two problems, an integrated approach is generally hopeless for real-world instances. Hence, the two phases are considered separately and optimized in sequence. Although there exist several versions for both problems, depending on the infrastructure manager and train operators requirements, we do not aim at presenting all of them, but rather at introducing the reader to the topic using small examples. We present models and solution approaches for the two problems in a didactic way and always refer the reader to the corresponding papers for technical details
Robust Train Timetabling
No full textNowadays railway systems are highly affected by disturbances, occurring in daily operations, and causing train delays and passenger inconvenience. Not only they negatively affect the passengers satisfaction, but they also cause additional operational costs, since the planned schedule needs to be modified in real-time. Train timetabling is a particularly critical phase in railway system management, since, in real-time operations, all the changes applied to the planned timetable impact on platform assignment, rolling stock circulation and crew scheduling. Therefore, in the strategic planning, it is an important issue to determine robust timetables, i.e., timetables that “perform well” under disturbances, avoiding delay propagation as much as possible. In this chapter, we present state-of-the-art methods that achieve robust timetables, and discuss their advantages and drawbacks
Robust Train Timetabling and Stop Planning with Uncertain Passenger Demand
No full textThe integrated Train Timetabling and Stop Planning (TTSP) problem calls for determining the optimal timetables for a given set of trains, while choosing, for each train, the subset of stations where it will stop. Both the timetable and the stop plan are determined based on the passenger demand, i.e. on the number of passengers travelling between an origin and a destination stations. In this work, we study the Robust TTSP (RTTSP), where passenger demand is considered to be uncertain, as it is often the case in real practice. We propose an Integer Linear Programming (ILP) model for RTTSP based on Light Robustness, an effective technique introduced in [Fischetti, M., and M. Monaci, Light robustness In: Ahuja RK, Möhring RH, Zaroliagis CD (eds) Robust and online large-scale optimization. Lecture Notes in Computer Science 5868 (2009), 61–84. Springer, Berlin Heidelberg]. We test the proposed ILP model on real-world data of the Wuhan-Guangzhou high-speed railway corridor under different demand scenarios
Optimal solutions to a real-world integrated airline scheduling problem
Full text linkWe study an integrated airline scheduling problem for a regional carrier. It integrates three stages of the planning process (i.e., fleet assignment, aircraft routing, and crew pairing) that are typically solved in sequence. Aircraft maintenance is also taken into account. The objective function aims at minimizing a weighted sum of the number of aircraft routes, the number of crew pairings, and the waiting times of crews between consecutive flights. In addition, it aims at maximizing the robustness of the solution by also minimizing the number of times that crews need to change aircraft. We present two mixed integer linear programming models for the integrated problem. The first formulation, called the path-path model, can be considered as the “natural model” in which both the crew pairings and the aircraft routes are represented by path-based variables. The other formulation, called the arc-path model, is a novel model in which the aircraft routes are represented by arc-based variables and the crew pairings by path-based variables. We propose two exact methods (called path-path method and arc-path method) for solving the integrated problem, each one based on one of the proposed models. Both methods consist of three phases. In the first phase, the linear programming relaxation of the corresponding model is solved to optimality by column generation on the path-based variables, thus providing a lower bound. The second phase computes a heuristic solution (upper bound) by using only the variables generated in the first phase. The third phase makes use of the lower and upper bounds (obtained in the previous phases) to compute an optimal solution. We propose a bounding cut based on computing a lower bound on the number of aircraft changes that are needed in a feasible solution, and empirically show that this cut significantly speeds up the exact methods. The proposed methods are tested on real-world instances of a regional carrier with up to 172 flights and three fleet operators. The results show that the arc-path method outperforms the path-path method as well as a heuristic approach from the literature, and derives the optimal solutions for all of the considered instances in at most two hours of computing time
Train timetabling by skip-stop planning in highly congested lines
Full text linkWe study the problem of scheduling passenger trains in a highly congested railway double-track line with the aim of increasing the number of scheduled trains. A feasible timetable of the trains currently scheduled in the network is given. Additional trains should be scheduled to meet the increasing passenger demand. To achieve this goal, we are allowed to increase the dwelling time of some trains at some stations, to let them stop at some additional stations and even to skip a few stops. Thereby, we need to take explicitly into account the deceleration and acceleration times that are needed by the train when it stops at a station. This problem integrates the choice of the train schedule with the choice of the train stops, the latter being usually made in the Line Planning process. To solve this problem, we propose a heuristic algorithm, extended from a previous method to include the new features of the studied application, and show its performance on real-world instances of the Chinese high-speed JingHu corridor (between Beijing and Shanghai) involving up to 387 trains
- …
