A branch-and-price algorithm for the scheduling of customer visits in the context of multi-period service territory design

作者：Bender Matthias^*; Kalcsics Jorg; Nickel Stefan; Pouls Martin

来源：European Journal of Operational Research, 2018, 269(1): 382-396.

DOI：10.1016/j.ejor.2018.01.047

• Transportation
• Multi-period service territory design
• Scheduling of customer visits
• Branch-and-price
• Acceleration techniques

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.

• 出版日期2018-8-16