A branch-and-cut framework for the consistent traveling salesman problem

摘要: Abstract We develop an exact solution framework for the Consistent Traveling Salesman Problem. This problem calls identifying minimum-cost set of routes that a single vehicle should follow during multiple time periods planning horizon, in order to provide consistent service given customers. Each customer may require one or and requirement applies at each location requires more than period. corresponds restricting difference between earliest latest arrival-times, across periods, not exceed some allowable limit. present three mixed-integer linear programming formulations this introduce new class valid inequalities strengthen these formulations. The are used conjunction with traditional traveling salesman branch-and-cut framework. test our on comprehensive benchmark instances, which we compiled by extending instances from well-known TSPLIB library into show up 50 customers, requiring over 5-period can be solved guaranteed optimality. Our computational experience suggests enforcing arrival-time consistency multi-period setting achieved merely small increase total routing costs.