A Matheuristic for the Multi-Compartment Vehicle Routing Problem with Multiple Periods
Tino Henke  1@  , M. Grazia Speranza  2@  , Gerhard Wäscher  1@  
1 : Otto-von-Guericke University Magdeburg
2 : University of Brescia

In this presentation, an extension of the multi-compartment vehicle routing problem (MCVRP) is considered, in which a planning horizon of not only one but multiple periods is taken into account. The problem is inspired by the real-world application of glass waste collection from public containers. In each of the regarded periods, the containers are filled by a certain amount of glass waste and they must be emptied before their capacity would be exceeded. To collect the glass waste, a fleet of vehicles with multiple compartments is available, where each compartment can be used to collect exactly one type of glass waste. Thus, different types of glass waste cannot get mixed during transportation and an efficient recycling process is supported. In addition to the typical assignment and sequencing decisions in (multi-compartment) vehicle routing problems, for each container a visiting schedule needs to be determined.

For solving this problem, a matheuristic has been developed and implemented. The algorithm uses a tabu search framework, in which the defined neighborhood structure is searched by an integer program. Extensive numerical experiments have been conducted in order to evaluate the performance matheuristic, to gain insights into the problem structure, and to determine the managerial value of considering multiple periods simultaneously. The corresponding results will be presented. 


Online user: 2 RSS Feed