Top

Published in:

2024 | OriginalPaper | Chapter

Average TSP Tour Length Approximations for Territory Design

Authors : Daisuke Hasegawa, Naoshi Shiono

Published in: Proceedings of Industrial Engineering and Management

Publisher: Springer Nature Singapore

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In vehicle routing, estimating route lengths using continuous approximation models can be valuable for delivery planning, especially for tour cost estimation and territory design because it avoids the computational cost associated with solving TSP and VRP directly. In this study, we propose a route length estimation formula based on rectilinear distances by considering the shape of the area. We calibrated the parameters through numerical experiments. Thus, our proposed formula can estimate the average tour length in rectilinear distance with high accuracy; and as the number of points increases, the influence of the shape decreases.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Mathematical Analysis on Optimal Assignment in Limited-Cycle Multiple Periods Considering Quality and Due Time ~the Case of Two Worker Levels~

next chapter Motion Capture Analysis of Learning Effect for Assembly Tasks

Applegate DL, Bixby RE, Chvatál V, Cook WJ (2006) The traveling salesman problem. Computational study. Princeton University Press, Princeton, New Jersey

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. https://doi.org/10.1016/0305-0548(94)00093-N

Franceschetti A, Jabali O, Laporte G (2017) Continuous approximation models in freight distribution management. TOP 25:413–433. https://doi.org/10.1007/s11750-017-0456-1MathSciNetCrossRef

Beardwood J, Halton JH, Hammersley JM (1959) The shortest path through many points. Math Proc Cambridge Philos Soc 55(4):299–327. https://doi.org/10.1017/S0305004100034095MathSciNetCrossRef

Vig V, Palekar US (2008) On estimating the distribution of optimal traveling salesman tour lengths using heuristics. Eur J Oper Res 186(1):111–119. https://doi.org/10.1016/j.ejor.2006.12.066MathSciNetCrossRef

Johnson DS, McGeoch LA, Rothberg EE (1996) Asymptotic experimental analysis for the Held-Karp traveling salesman bound. In: The proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms, pp. 341–350, Atlanta, Georgia

Deza E, Deza MM (2014) Encyclopedia of distances. Springer-Verlag, Berlin, HeidelbergCrossRef

Koshizuka T, Kobayashi J (1983) On the relation between road distance and euclidean distance. J City Planning Institute of Japan 18:43–48. https://doi.org/10.11361/journalcpij.18.43 (in Japanese)

Kurita O (2001) Theory of road patterns for a circular disk city. J City Planning Institute of Japan 36:859–864. https://doi.org/10.11361/journalcpij.36.859 (in Japanese)

10.

Çavdar B, Sokol J (2015) A distribution-free TSP tour length estimation model for random graphs. Eur J Oper Res 243(2):588–598. https://doi.org/10.1016/j.ejor.2014.12.020MathSciNetCrossRef

11.

Holguín-Veras J, Patil GR (2005) Observed trip chain behavior of commercial vehicles. Transp Res Rec 1906(1):74–80. https://doi.org/10.1177/0361198105190600109CrossRef

12.

Choi Y, Schonfeld PM (2022) Review of length approximations for tours with few stops. Transp Res Rec 2676(3):201–213. https://doi.org/10.1177/03611981211049433CrossRef

13.

Chien TW (1992) Operational estimators for the length of a traveling salesman tour. Comput Oper Res 19(6):469–478. https://doi.org/10.1016/0305-0548(92)90002-MCrossRef

14.

Helsgaun K (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur J Oper Res 126(1):106–130. https://doi.org/10.1016/S0377-2217(99)00284-2MathSciNetCrossRef

15.

Johnson DS, McGeoch LA (2002) Experimental analysis of heuristic for the STSP. In: Gutin G, Punnen AP (eds) The traveling salesman problems and its variations. Kluwer Acdemic Publishers. Springer New York, New York, pp 369–443

Title: Average TSP Tour Length Approximations for Territory Design
Authors: Daisuke Hasegawa
Naoshi Shiono
Publisher: Springer Nature Singapore
Book: Proceedings of Industrial Engineering and Management
Print ISBN: 978-981-9701-93-3

Electronic ISBN: 978-981-9701-94-0

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-981-97-0194-0_5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Premium Partners