6533b833fe1ef96bd129ca7c

RESEARCH PRODUCT

Contributions to Branch-and-Price-and-Cut Algorithms for Routing Problems

Ann-kathrin Rothenbächer

subject

050210 logistics & transportation021103 operations researchComputer scienceBranch and price05 social sciences0211 other engineering and technologiesTime horizon02 engineering and technologyDynamic choiceHub location problemNetwork planning and design0502 economics and businessVehicle routing problemPeriodic vehicle routing problemColumn generationAlgorithm

description

This article deals with new exact branch-and-price-and-cut algorithms for the solution of routing problems. Specialized methods for the pickup-and-delivery problem (PDP), the truck-and-trailer routing problem (TTRP), the periodic vehicle routing problem (PVRP) and a service network design and hub location problem (SNDHLP) are presented. We develop a new technique for the acceleration of bidirectional labeling algorithms by a dynamic choice of the merge point. Moreover, for variants of the PDP, the bidirectional labeling can be effectively applied for the first time. In the TTRP, we model the extension to a 2 days planning horizon and the consideration of a quantity-dependent transfer time. The PVRP is treated with full flexible schedule structures for the first time. For these two last-mentioned problems, special techniques to tackle the symmetry are presented. The SNDHLP constitutes a new real-world problem in the application area of combined transport and is also solved with a problem-specific branch-and-price-and-cut algorithm.

yearjournalcountryeditionlanguage
2019-01-01
https://doi.org/10.1007/978-3-030-18500-8_5