TY - JOUR
T1 - A branch-and-cut framework for the consistent traveling salesman problem
AU - Subramanyam, Anirudh
AU - Gounaris, Chrysanthos E.
N1 - Publisher Copyright:
© 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.
PY - 2016/1/16
Y1 - 2016/1/16
N2 - We develop an exact solution framework for the Consistent Traveling Salesman Problem. This problem calls for identifying the minimum-cost set of routes that a single vehicle should follow during the multiple time periods of a planning horizon, in order to provide consistent service to a given set of customers. Each customer may require service in one or multiple time periods and the requirement for consistent service applies at each customer location that requires service in more than one time period. This requirement corresponds to restricting the difference between the earliest and latest vehicle arrival-times, across the multiple periods, to not exceed some given allowable limit. We present three mixed-integer linear programming formulations for this problem and introduce a new class of valid inequalities to strengthen these formulations. The new inequalities are used in conjunction with traditional traveling salesman inequalities in a branch-and-cut framework. We test our framework on a comprehensive set of benchmark instances, which we compiled by extending traveling salesman instances from the well-known TSPLIB library into multiple periods, and show that instances with up to 50 customers, requiring service over a 5-period horizon, can be solved to guaranteed optimality. Our computational experience suggests that enforcing arrival-time consistency in a multi-period setting can be achieved with merely a small increase in total routing costs.
AB - We develop an exact solution framework for the Consistent Traveling Salesman Problem. This problem calls for identifying the minimum-cost set of routes that a single vehicle should follow during the multiple time periods of a planning horizon, in order to provide consistent service to a given set of customers. Each customer may require service in one or multiple time periods and the requirement for consistent service applies at each customer location that requires service in more than one time period. This requirement corresponds to restricting the difference between the earliest and latest vehicle arrival-times, across the multiple periods, to not exceed some given allowable limit. We present three mixed-integer linear programming formulations for this problem and introduce a new class of valid inequalities to strengthen these formulations. The new inequalities are used in conjunction with traditional traveling salesman inequalities in a branch-and-cut framework. We test our framework on a comprehensive set of benchmark instances, which we compiled by extending traveling salesman instances from the well-known TSPLIB library into multiple periods, and show that instances with up to 50 customers, requiring service over a 5-period horizon, can be solved to guaranteed optimality. Our computational experience suggests that enforcing arrival-time consistency in a multi-period setting can be achieved with merely a small increase in total routing costs.
UR - http://www.scopus.com/inward/record.url?scp=84942296297&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84942296297&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2015.07.030
DO - 10.1016/j.ejor.2015.07.030
M3 - Article
AN - SCOPUS:84942296297
SN - 0377-2217
VL - 248
SP - 384
EP - 395
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -