A Two-Index Formulation for the Fixed-Destination Multi-Depot Asymmetric Travelling Salesman Problem and Some Extensions

Aguayo, Maichel M.; Avilés, Francisco N.; Sarin, Subhash C.; Sherali, Hanif D.

doi:10.15388/22-INFOR485

Informatica

A Two-Index Formulation for the Fixed-Destination Multi-Depot Asymmetric Travelling Salesman Problem and Some Extensions

Volume 33, Issue 4 (2022), pp. 671–692

Maichel M. Aguayo Francisco N. Avilés Subhash C. Sarin Hanif D. Sherali

https://doi.org/10.15388/22-INFOR485

Pub. online: 1 June 2022 Type: Research Article

Open Access

Received
1 January 2022

Accepted
1 May 2022

Published
1 June 2022

Abstract

We introduce a compact formulation for the fixed-destination multi-depot asymmetric travelling salesman problem (FD-mATSP). It consists of m salesmen distributed among D depots who depart from and return to their respective origins after visiting a set of customers. The proposed model exploits the multi-depot aspect of the problem by labelling the arcs to identify the nodes that belong to the same tour. Our experimental investigation shows that the proposed-two index formulation is versatile and effective in modelling new variations of the FD-mATSP compared with existing formulations. We demonstrate this by applying it for the solution of two important extensions of the FD-mATSP that arise in logistics and manufacturing environments.

References

Aguayo, M.M. (2016). Modeling, Analysis, and Exact Algorithms for Some Biomass Logistics Supply Chain Design and Routing Problems. PhD thesis, Virginia Polytechnic Institute and State University.

Anily, S., Hassin, R. (1992). The swapping problem. Networks, 22(4), 419–433.

Bektaş, T. (2012). Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing. European Journal of Operational Research, 216(1), 83–93.

Bektaş, T., Gouveia, L., Santos, D. (2020). Compact formulations for multi-depot routing problems: theoretical and computational comparisons. Computers & Operations Research, 124, 105084.

Burger, M. (2014). Exact and compact formulation of the fixed-destination travelling salesman problem by cycle imposement through node currents. In: Huisman, L.I.W.A.D. (Ed.), Operations Research Proceedings 2013. Springer, Cham.

Burger, M., Su, Z., Schutter, B.D. (2018). A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem. European Journal of Operational Research, 265(2), 463–477.

Chira, C., Sedano, J., Villar, J.R., Cámara, M., Corchado, E. (2014). Urban bicycles renting systems: Modelling and optimization using nature-inspired search methods. Neurocomputing, 135, 98–106.

Cordeau (2007). Multiple Depot VRP Instances. http://neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/.

Davendra, D. (2010). Traveling Salesman Problem: Theory and Applications. BoD–Books on Demand.

Gavish, B., Graves, S.C. (1978). The travelling salesman problem and related problems. Working paper GR-078-78. Cambridge, MA: Operation Research Center, Massachusetts Institute of Technology.

Golden, B.L., Raghavan, S., Wasil, E.A. (2008). The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, New York.

Guastaroba, G., Speranza, M.G., Vigo, D. (2016). Intermediate facilities in freight transportation planning: a survey. Transportation Science, 50(3), 763–789.

Kara, I., Bektaş, T. (2006). Integer linear programming formulations of multiple salesman problems and its variations. European Journal of Operational Research, 174(3), 1449–1458.

Kumar, S.N., Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 4(03), 66.

Laporte, G. (1992a). The traveling salesman problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231–247.

Laporte, G. (1992b). The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345–358.

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H., Shmoys, D.B. (1985). The traveling salesman problem; a guided tour of combinatorial optimization. Journal of the Operational Research Society.

Lou, Z., Li, Z., Luo, L., Dai, X. (2016). Study on multi-depot collaborative transportation problem of milk-run pattern. In: MATEC Web of Conferences, Vol. 81, 01004. EDP Sciences.

Malik, W., Rathinam, S., Darbha, S. (2007). An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Operations Research Letters, 35(6), 747–753.

Montoya-Torres, J.R., Franco, J.L., Isaza, S.N., Jiménez, H.F., Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115–129.

Paredes-Belmar, G., Lüer-Villagra, A., Marianov, V., Cortés, C.E., Bronfman, A. (2017). The milk collection problem with blending and collection points. Computers and Electronics in Agriculture, 134, 109–123.

Ramos, T.R.P., Gomes, M.I., Póvoa, A.P.B. (2020). Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Logistics Research and Applications, 23(2), 103–120.

Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer-Verlag, Berlin.

Toth, P., Vigo, D. (2002). The Vehicle Routing Problem. SIAM, Philadelphia.

TSPLIB (1997). A Library of traveling salesmen and related problem instances. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/atsp/index.html.

Zhang, R., Yun, W.Y., Moon, I. (2009). A reactive tabu search algorithm for the multi-depot container truck transportation problem. Transportation Research Part E: Logistics and Transportation Review, 45(6), 904–914.

Biographies

Aguayo Maichel M.

maichel.aguayo@uss.cl

M.M. Aguayo is an assistant professor at Universidad San Sebastián. He is a graduate of Virginia Polytechnic Institute and State University, where he received his doctoral degree. His research interests include mathematical programming and optimization with applications to real-world problems such as location, transportation, scheduling, and routing problems.

Avilés Francisco N.

francisco.aviles@uss.cl

F.N. Avilés is an instructor at the Department of Industrial Engineering at Universidad San Sebastián. He is a graduate of Universidad de Concepción, where he received his master’s degree in industrial engineering. Currently, his research interests are related to the design and applications of optimization models and algorithms to real-world logistic and operations systems.

Sarin Subhash C.

sarins@vt.edu

S.C. Sarin is the Paul T. Norton endowed professor of the Grado Department of Industrial and Systems Engineering at Virginia Polytechnic Institute and State University. He has made research contributions in production scheduling, sequencing, applied mathematical programming, and analysing and designing algorithms for the operational control of manufacturing systems. He has published over a hundred papers in the industrial engineering and operation research journals and has co-authored three books in the production scheduling area. He has been recognized with several prestigious awards at the university, state, and national levels for his research work, teaching, service, and advising.

Sherali Hanif D.

hanifs@vt.edu

H.D. Sherali is a university distinguished professor emeritus at the Industrial and Systems Engineering Department, Virginia Polytechnic Institute and State University. His areas of research interest are in mathematical optimization modelling, analysis, and design of algorithms for specially structured linear, nonlinear, and continuous and discrete nonconvex programs, with applications to transportation, location, engineering and network design, production, economics, and energy systems. He has published over 351 refereed articles in various operations research journals and has (co-)authored nine books, with a total Google Scholar citation count of over 40,844 and an H-index of 81. He is an elected member of the National Academy of Engineering, a fellow of both INFORMS and IIE, and a member of the Virginia Academy of Science Engineering and Medicine.

Full article Related articles Cited by

Open access article under the CC BY license.

Keywords

logistics travelling salesman multiple depot fixed-destination

Funding

Maichel M. Aguayo thanks ANID (The Chilean Agency for Research and Development) for its support through the FONDECYT Iniciación Project number 11190157.

Metrics

since January 2020

817 Article info views	855 Full article views
529 PDF downloads	154 XML downloads

RSS

Authors

Abstract

References

Biographies

Export citation

Copy and paste formatted citation

Download citation in file