A Set-Covering Based Heuristic for Rich Vehicle Routing Problems with a Heterogneous Fleet

Felix Brandt and Nitin Ahuja and Werner Heid and Anne Meyer and Frank Radaschewski
EURO Working Group on Vehicle Routing and Logistics Optimization
The Heterogeneous Vehicle Routing Problem (HVRP), as defined by Golden et. al, assumes a fleet that is composed of different types of vehicles. Usually, the vehicles are differing in their loading capacities as well as fixed or variable costs. The objective is to minimize the total cost of all vehicles used in the solution. One way to tackle the problem, presented by Taillard, is to solve a homogeneous fleet VRP for each vehicle type independently with an unlimited number of vehicles. Thereby, a lot of (partly overlapping) tours are generated. From these tours, the least cost subset visiting each customer once is found by solving a Set Partitioning Problem. In our work, we apply and extend the ideas of Taillard, to enable a commercial library for rich but homogeneous fleet VRPs to handle heterogeneous fleets. For the creation of tour plans, we rely on the VRP software package PTV xTour Server. Thereby, we are able to incorporate all of its supported types of restrictions from real world problems, like break and rest rules or multi-trips. We propose different strategies to create a number of preferably diverse solutions from the homogeneous fleet VRPs. To find the least cost subset of tours, we choose a Set Covering formulation. To make each customer visited exactly once, we introduce one additional step to repair the solution. The main idea of this step is to generate promising subtours out of the tours that contain customers, which are visited more than once in the current solution. These subtours are added to the Set Covering problem, which is solved repeatedly until no more duplicate visits exist. In this talk we present our solution approach, our insights of the experiment phase and from a real world application. Furthermore, we talk about some experience gained from implementing our approach into PTV xTour Server, a commercial vehicle routing solution.
Logistik und Supply-Chain-Optimierung
Logistikoptimierung für die PTV Group
Download .bib
Download .bib
Eingetragen von
Felix Brandt