Heiko Breier

Dissertation, Karlsruhe Institute of Technology (KIT), Series: Institute for Material Handling and Logistics (IFL), Volume 83

This thesis examines the Vehicle-Routing-Problem with split-deliveries and alternative delivery periods (SDVRPA). The problem is partitioned into a Master-Problem and Pricing-Problems. It is solved with a Branch-and-Price-Algorithm. Subsequently, the results are evaluated.

While previous research considered Vehicle-Routing-Problems either focusing on split-deliveries or alternative periods, this thesis explores the combination of both. New feasible tours are generated using a Column-Generation method. To find a solution of integer values, we apply branching rules. The Pricing-Problem is solved with a Labeling-Algorithm.

In contrast to conventional approaches, this thesis investigates the impact not only on the shipper but also on the freight forwarder and the recipient. When alternative delivery periods and split-deliveries are employed, freight forwarders get a wider scope for planning and can therefore plan more efficient routes. The total distance and the number of trips decreases while the utilization of vehicles increases. Consequently, the number of trips leaving the depot can be reduced, benefitting the shipper.

Even with few alternative delivery periods, which allow vehicles to be used more efficiently, substantial savings can be achieved.