nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Average TSP Tour Length Approximations for Territory Design

verfasst von : Daisuke Hasegawa, Naoshi Shiono

Erschienen in: Proceedings of Industrial Engineering and Management

Verlag: Springer Nature Singapore

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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

Nächstes Kapitel 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

Titel: Average TSP Tour Length Approximations for Territory Design
verfasst von: Daisuke Hasegawa
Naoshi Shiono
Verlag: Springer Nature Singapore
Buch: Proceedings of Industrial Engineering and Management
Print ISBN: 978-981-9701-93-3

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

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

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht