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

Resource type
Martin Pouls, Matthias Bender, Jörg Kalcsics, Stefan Nickel
Many companies employ field representatives to provide services at their customers’ sites on a regular basis. Consider, for instance, the delivery of goods to retailers or regular technical maintenance tasks. In these applications, the entire region under study is subdivided into service territories, with one field representative being responsible for all customers in a territory. At a tactical planning level, customer visits within each service territory must be scheduled over a given planning horizon. The goal is to determine a valid visit schedule for each customer that meets customer-specific requirements such as visiting rhythms. In addition, the schedule must achieve a balanced daily and weekly workload. Lastly, compactness is important, as field representatives need to travel to their customers, and thus visits on the same day should be geographically concentrated. In this talk we present a column generation formulation of the resulting scheduling problem and propose an exact branch-and-price algorithm. Our method incorporates specialized acceleration techniques, such as a fast pricing heuristic and a symmetry handling strategy. The latter aims to reduce the symmetry inherent to the model by fixing variables and thereby eliminating symmetric solutions from the search tree. We perform extensive experiments on test instances based on realworld data in order to evaluate the different algorithmic components, such as branching variable selection and symmetry handling. Compared to the commercial general purpose mixed integer programming solver Gurobi, our algorithm achieves a significant speedup and is able to solve instances with up to 55 customers and a planning horizon of 4 weeks to optimality in a reasonable running time.
Research focus
Logistics and Supply Chain Optimisation
Logistikoptimierung für die PTV Group
Download .bib
Download .bib
Published by
Martin Pouls