A Branch-and-Price Algorithm for the Scheduling of Customer Visits in the Context of Multi-Period Service Territory Design

Matthias Bender, Jörg Kalcsics, Stefan Nickel, Martin Pouls
European Journal of Operational Research
A problem that arises in the context of multi-period service territory design is the scheduling of customer visits. In this problem, customer visits must be assigned to the days of the planning horizon subject to customer-specific requirements. We consider a highly relevant planning scenario of this problem and present an exact branch-and-price algorithm. We propose specialized acceleration techniques, particularly a fast pricing heuristic and techniques to reduce the symmetry inherent to the problem. Experiments on real-world data sets show that instances with up to 55 customers and a planning horizon of four weeks with five days per week can be solved to optimality in reasonable running times.
Research focus
Logistics and Supply Chain Optimisation
Logistikoptimierung für die PTV Group
Download .bib
Download .bib
Published by
Martin Pouls