Contributed Session Wed.3.H 0106

Wednesday, 15:15 - 16:45 h, Room: H 0106

Cluster 13: Logistics, traffic, and transportation [...]

Vehicle and crew planning


Chair: Gary Froyland



Wednesday, 15:15 - 15:40 h, Room: H 0106, Talk 1

Gary Froyland
Robust airline schedule planning, aircraft routing and crew pairing: An integrated scenario-based approach

Coauthors: Michelle Dunbar, Cheng-Lung Wu


For reasons of tractability, classical approaches to the airline scheduling problem have been to sequentially decompose the problem into various stages (eg. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision making process in subsequent stages. Such a sequential approach unfortunately fails to capture the many dependencies between the various stages, most notably between those of aircraft routing and crew pairing, and how these dependencies affect the propagation of delays through the flight network. As delays are commonly transferred between late-running aircraft and crew, it is important that aircraft routing and crew pairing decisions are made together. The propagated delay may then be accurately estimated to minimise the overall propagated delay for the network and produce a robust solution for both aircraft and crew. We introduce a new scenario-based approach to accurately calculate and minimise the cost of propagated delay, in a framework that integrates aircraft routing, crew pairing, and re-timing, and uses delay information from multiple scenarios.



Wednesday, 15:45 - 16:10 h, Room: H 0106, Talk 2

Elmar Swarat
Modeling and solving a toll enforcement problem

Coauthors: Ralf Borndörfer, Guillaume Sagnol


We present the Toll Enforcement Problem to optimize the tours of toll inspectors on German motorways. This is an integrated planning and scheduling model, consisting of a tour planning and a duty rostering part. The goal is to achieve a network-wide control proportional to the traffic distribution. We introduce a time-expanded planning graph, based on a given time discretization, where computing the tours corresponds to a Multi-Commodity flow problem. This is formulated as an IP using path variables. For the rostering problem we develop a graph model, where arcs model feasible sequences of duties. Finding feasible rosters again comes up to a Multi-Commodity flow problem in an IP formulation. By introducing coupling constraints, both problems were connected to an integrated model. We will show, that many important requirements and legal rules can be modeled by this approach. By our modeling issues the extreme complexity of our problem can be reduced to reasonable size problem instances. Computational experiments on several real-world instances indicate that we are able to solve them to a proven optimality with only a small gap.



Wednesday, 16:15 - 16:40 h, Room: H 0106, Talk 3

Guvenc Sahin
Tactical and strategic crew planning problems in railways

Coauthors: Fardin Dashty Saridarq, A. Çetin Suyabatmaz


We consider the tactical level planning problem in railways that determine the minimum sufficient crew resources level for one crew region at a time given the list of periodic train duties in a finite planning horizon. We formulate this problem once as a network flow problem and once as a set covering problem. The set covering version may only be attacked with a column-and-row generation algorithm, and the experimental results are not satisfactory from a computational point of view when compared to the network flow formulation. Even with complicating hard constraints that challenge the network flow formulation, the set covering problem is not easy to handle while the network flow formulations conveys optimal solutions with no additional effort. We also extend the network flow formulation to consider multiple regions simultaneously while the allocation of train duties among the regions is partially unknown. The problem is to determine the allocation and the level of minimum sufficient crew resources level coherently. The network flow formulation still provides satisfactory results, but only for a limited number of regions under consideration.


  Online lending company provides a wide range of ways to get money by means of Payday Loans Tennessee. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.