Abstract
This paper discusses the problem of predicting the length of Traveling Salesman Problem (TSP) tour in dynamic and uncertain environments. Our findings, which are guided by extensive simulation runs, provide statistical estimations for the tour length under different scenarios. One of the applications that can benefit from these estimates includes warehouse order picking, which has seen increased importance due to online shopping. The utility of statistical estimates for TSP tour length for order picking is demonstrated on a common warehouse layout.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Antosiewicz M, Koloch G, Kamiński B (2013) Choice of best possible metaheuristic algorithm for the travelling salesman problem with limited computational time: quality, uncertainty and speed. J Theor Appl Comput Sci 7(1):46–55
Beardwood J, Halton JH, Hammersley JM (1959) The shortest path through many points. In: Mathematical proceedings of the Cambridge Philosophical Society, vol 55. Cambridge University Press, Cambridge, pp 299–327
Bertsimas DJ (1992) A vehicle routing problem with stochastic demand. Oper Res 40(3):574–585
Bertsimas DJ, Van Ryzin G (1991) A stochastic and dynamic vehicle routing problem in the euclidean plane. Oper Res 39(4):601–615
Brown JR, Guiffrida AL (2017) Stochastic modeling of the last mile problem for delivery fleet planning. J Transp Res Forum 56
Çavdar B, Sokol J (2015) A distribution-free tsp tour length estimation model for random graphs. Eur J Oper Res 243(2):588–598
Cook WJ (2011) In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, Princeton
Daganzo CF (1984) The distance traveled to visit n points with a maximum of c stops per vehicle: an analytic model and an application. Transp Sci 18(4):331–350
Franceschetti A, Jabali O, Laporte G (2017) Continuous approximation models in freight distribution management. Top 25(3):413–433
Geem ZW, Kim JH, Loganathan G (2001) A new heuristic optimization algorithm: harmony search. Simulation 76(2):60–68
Gendreau M, Hertz A, Laporte G (1994) A tabu search heuristic for the vehicle routing problem. Manag Sci 40(10):1276–1290
Ghiani G, Guerriero F, Laporte G, Musmanno R (2003) Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. Eur J Oper Res 151(1):1–11
Grefenstette J, Gopal R, Rosmaita B, Van Gucht D (1985) Genetic algorithms for the traveling salesman problem. In: Proceedings of the first international conference on genetic algorithms and their applications, pp 160–165
Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations. Springer, New York, pp 85–103
Kennedy J (2011) Particle swarm optimization. In: Encyclopedia of machine learning. Springer, New York, pp 760–766
Kirkpatrick S, Gelatt CD, Vecchi MP et al (1983) Optimization by simulated annealing. Science 220(4598):671–680
Kwon O, Golden B, Wasil E (1995) Estimating the length of the optimal tsp tour: an empirical study using regression and neural networks. Comput Oper Res 22(10):1039–1046
Law AM, Kelton WD, Kelton WD (2000) Simulation modeling and analysis, vol 3. McGraw-Hill, New York
Lawer E, Lenstra JK, Kan AR, Shmoys D (1985) The traveling salesman problem: a guided tour of combinatorial optimization
Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J ACM 7(4):326–329
Nicola D, Vetschera R, Dragomir A (2019) Total distance approximations for routing solutions. Comput Oper Res 102:67–74
Ong H, Huang H (1989) Asymptotic expected performance of some tsp heuristics: an empirical evaluation. Eur J Oper Res 43(2):231–238
Papadimitriou CH (1977) The euclidean travelling salesman problem is np-complete. Theor Comput Sci 4(3):237–244
Stein DM (1978a) An asymptotic, probabilistic analysis of a routing problem. Math Oper Res 3(2):89–101
Stein DM (1978b) Scheduling dial-a-ride transportation systems. Transp Sci 12(3):232–249
Vinel A, Silva DF (2018) Probability distribution of the length of the shortest tour between a few random points: a simulation study. In: 2018 Winter simulation conference (WSC). IEEE, pp 3156–3167
Acknowledgements
The authors would like to thank two anonymous referees for their insightful comments on the earlier versions of this paper. Addressing these comments has led to a much improved manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Madani, A., Batta, R. & Karwan, M. The balancing traveling salesman problem: application to warehouse order picking. TOP 29, 442–469 (2021). https://doi.org/10.1007/s11750-020-00557-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-020-00557-y