Invited Session Mon.2.H 0106

Monday, 13:15 - 14:45 h, Room: H 0106

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

Branch-and-price algorithms in transportation


Chair: Florian Dahms and Marco Lübbecke



Monday, 13:15 - 13:40 h, Room: H 0106, Talk 1

Robert Voll
Branch-and-price-and-cut for railroad blocking plans

Coauthor: Uwe Clausen


We present a consolidation problem from wagonload traffic, which is a production form in railway freight traffic. A huge number of OD-requests -each of them consists of only a small number of wagons- has to be routed through the railway network. Wagons from different OD-pairs (relations) are consolidated in reclassification yards in order to use trains jointly for parts of their routes. The route of each relation is determined by so called Blocking Plans which shall be optimized. The objective is to minimize the sum of train and reclassification costs.
We consider a multicommodity flow problem with elements of a fixed charge problem. A column generation pattern developed earlier is extended to a Branch-and-Price-algorithm. Our branching rule destroys the simple subproblem structure of the aforementioned column generation approach, but we overcome this problem by dynamical programming. We can take advantage from our branching rule by deriving effective cuts.
Numerical results are presented and compared to solutions provided by commercial solvers. We also analyze the impact of our cuts empirically. First experiments are very promising.



Monday, 13:45 - 14:10 h, Room: H 0106, Talk 2

Michel Povlovitsch Seixas
Branch-and-price for a rich vehicle routing and scheduling problem

Coauthor: André B. Mendes


This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity and average speed. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to deal with the possibility for each vehicle to perform multiple routes per day and to deal with the need to determine the workday beginning instant of time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a metaheuristic based on tabu search were also developed.



Monday, 14:15 - 14:40 h, Room: H 0106, Talk 3

Markus Bohlin
An extended formulation for allocating classification tracks in hump yards

Coauthors: Florian Dahms, Holger Flier, Sara Gestrelius, Matús Mihalák


A major task in railway operations is shunting trains in a hump yard. Freight
cars need to be assigned to classification tracks where they can be formed
into outgoing trains. Often the objective is to minimize the number of
shunting operations like pulling out and rolling in cars to the hump yard.
Our model is based on the processes at the Hallsberg hump yard in Sweden. The
problem formulation derived from these processes was already shown to be
NP-hard by Bohlin et al.
Natural compact MIP formulations so far have only yielded very weak linear
relaxations and could not be used to efficiently generate optimal solutions
for problem instances of reasonable size.
We present an extended formulation that produces a very tight linear
relaxation and can be efficiently solved via column generation for large
problem instances. For several real world instances we are now able to produce
optimal solutions.
Furthermore we discuss issues like symmetry, branching decisions and
problem specific heuristics necessary to improve the solving process.


  Most online loan lenders allow getting New Jersey Loans Online without visiting a bank, straight to your bank account. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis is the one that definitely differs from all other products.