A specialized column generation approach for a vehicle routing problem with demand allocation

Abstract

Motivated by logistical operations for a food bank, this paper addresses a class of vehicle routing problems with demand allocation considerations over a network of partner agencies locations and candidate delivery sites. Any delivery tour starts at a central depot operated by the food bank and selected delivery sites are sequentially visited in order to supply goods to a set of partner agencies who travel from their respective locations to their assigned delivery sites. The problem is modelled as a mixed-integer programme with the objective of minimizing a weighted average of the distances travelled by delivery vehicles and partner agencies, and is tackled via two heuristics. First, a relax-and-fix heuristic is presented for the proposed model and is computationally enhanced using two symmetry-defeating strategies. Second, the problem is reformulated as a set partitioning model with side packing constraints that prompts a specialized column generation approach. Computational experience is provided using realistic data instances to demonstrate the usefulness of the proposed heuristics and the importance of integrated solution techniques for this class of problems.

Keywords:

• distribution networks
• location and vehicle routing
• symmetry-defeating constraints
• column generation
• relax-and-fix

Acknowledgements

This work has been supported by the University of Massachusetts, Amherst Faculty Research Grant/Healey Endowment Grant Award Number P1FRG0000000055.