Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
EURO Journal on Transportation and Logistics
Erschienen in: EURO Journal on Transportation and Logistics 1/2017

31.07.2014 | Research Paper

The multi-path Traveling Salesman Problem with stochastic travel costs

verfasst von: Roberto Tadei, Guido Perboli, Francesca Perfetti

Erschienen in: EURO Journal on Transportation and Logistics | Ausgabe 1/2017

Einloggen

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

search-config
loading …

Abstract

Given a set of nodes, where each pair of nodes is connected by several paths and each path shows a stochastic travel cost with unknown probability distribution, the multi-path Traveling Salesman Problem with stochastic travel costs aims at finding an expected minimum Hamiltonian tour connecting all nodes. Under a mild assumption on the unknown probability distribution, a deterministic approximation of the stochastic problem is given. The comparison of such approximation with a Monte Carlo simulation shows both the accuracy and the efficiency of the deterministic approximation, with a mean percentage gap around 2% and a reduction of the computational times of two orders of magnitude.
Vorheriger Artikel Introduction to the special issue on City Logistics
Nächster Artikel An extended demand responsive connector

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

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

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
Literatur
Applegate DL, Bixby RE, Chvátal V, Cook WJ (2007) The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton
Baldi MM, Ghirardi M, Perboli G, Tadei R (2012) The capacitated transshipment location problem under uncertainty: A computational study. Procedia - Social and Behavioral Sciences 39:424–436CrossRef
Berbeglia G, Cordeau J-F, Laporte G (2010) Dynamic pickup and delivery problems. Eur J Operat Res 202:8–15CrossRef
Bertsimas D, Van Ryzin G (1991) A stochastic and dynamic vehicle-routing problem in the Euclidean plane. Operat Res 39:601–615CrossRef
Birge JR and Louveaux FV (1997) Introduction to stochastic programming. Springer
Chourabi H, Nam T, Walker S, Gil-Garcia JR, Mellouli S, Nahon K, Pardo TA, Scholl HJ (2012) Understanding smart cities: An integrative framework. Proceedings of the 2012 45th Hawaii International Conference on System Sciences HICSS ’12. IEEE Computer Society, Washington, pp 2289–2297CrossRef
CITYLOG Consortium (2010). CITYLOG European project
Cook WJ (2012) In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton
Cordeau J-F, Laporte G, Savelsbergh M, Vigo D (2007) Vehicle Routing. In: Barnhart C, Laporte G (eds) Transportation Handbooks on Operations Research and Management Science. North Holland, Amsterdam, pp 367–428
Demir E, Bektas T, Laporte G (2014) A Review of Recent Research on Green Road Freight Transportation. Eur J Operat Res 237:775–793CrossRef
Eiger A, Mirchandani PB, Soroush H (1985) Path preferences and optimal paths in probabilistic networks. Transportation Science 19:75–84CrossRef
Figliozzi MA (2010) The impacts of congestion on commercial vehicle tour characteristics and costs. Transp res part E: logist transp rev 46:496–506CrossRef
Figliozzi MA (2010) An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows. Transp Res Part C: Emerg Technol 18:668–679CrossRef
Figliozzi MA (2011) The impacts of congestion on time-definitive urban freight distribution networks CO2 emission levels: Results from a case study in Portland, Oregon. Transp Res Part C: Emerg Technol 19:766–778CrossRef
Franceschetti A, Honhon D, Van Woensel T, Bektaş T, Laporte G (2013) The time-dependent pollution-routing problem. Transp Res Part B: Methodol 56:265–293CrossRef
Galambos J, Lechner J, Simiu E (1994) Extreme Value Theory and Applications. Kluwer
Gendreau M, Laporte G, Séguin R (1996) Stochastic vehicle routing. Eur J Operat Res 88:3–12CrossRef
Ghiani G, Guerriero F, Laporte G, Musmanno R (2003) Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. Eur J Operat Res 151:1–11CrossRef
Goemans MX, Bertsimas D (1991) Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem. Math Operat Res 16:72–89CrossRef
Golden BL, Raghavan S, Wasil EA (2008) The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, New York
Gumbel EJ (1958) Statistics of Extremes. Columbia University Press, Columbia
Güner AR, Murat A, Chinnam RB (2012) Dynamic routing under recurrent and non-recurrent congestion using real-time ITS information. Comput Operat Res 39:358–373CrossRef
Hame L, Hakula H (2013) Dynamic journeying under uncertainty. Eur J Operat Res 225:455–471CrossRef
Hansen W (1959) How accessibility shapes land use. J Am Inst Planners 25:73–76CrossRef
Hvattum LM, Lokketangen A, Laporte G (2006) Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transp Sci 40:421–438CrossRef
Hvattum LM, Lokketangen A, Laporte G (2007) A branch-and-regret heuristic for stochastic and dynamic vehicle routing problems. Networks 49:330–340CrossRef
Ichoua S, Gendreau M, Potvin J-Y (2006) Exploiting knowledge about future demands for real-time vehicle dispatching. Transp Sci 40:211–225CrossRef
Jaillet P (1988) A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operat Res 36:929–936CrossRef
Jaillet P, Melvyn Sim JQ (2013) Routing Optimization with Deadlines under Uncertainty. “Tech. Rep”. MIT
Kenyon AS, Morton DP (2003) Stochastic vehicle routing with random travel times. Transp Sci 37:69–82CrossRef
Lecluyse C, van Woensel T, Peremans H (2009) Vehicle routing with stochastic time-dependent travel times. 4OR 7:363–377CrossRef
Lee C, Lee K, Park S (2012) Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J Operat Res Soc 63:1294–1306CrossRef
Leipala T (1978) On the solutions of stochastic traveling salesman problems. EurJOperat Res 2:291–297
Maggioni F, Kaut M, Bertazzi L (2009) Stochastic optimization models for a single-sink transportation problem.Comput Manag Sci 6:251–267CrossRef
Maggioni F, Wallace S (2012) Analyzing the quality of the expected value solution in stochastic programming. Annals Operat Res 200:37–54CrossRef
Perboli G, Tadei R, Baldi MM (2012) The stochastic generalized bin packing problem. Discrete Appl Math 160:1291–1297CrossRef
Perboli G, Tadei R, Vigo D (2011) The two-echelon capacitated vehicle routing problem: Models and math-based heuristics.Transp Sci 45:364–380CrossRef
Pillac V, Gendreau M, Guéret C, Medaglia AL (2013) A review of dynamic vehicle routing problems. Eur J Operat Res 225:1–11CrossRef
Psaraftis HN, Tsitsiklis JN (1993) Dynamic shortest paths in acyclic networks with markovian arc costs. Operat Res 41:91–101CrossRef
Reinelt G (1991) TSPLIB- a traveling salesman problem library. ORSA J Comput 3:376–384CrossRef
Tadei R, Perboli G, Ricciardi N, Baldi MM (2012) The capacitated transshipment location problem with stochastic handling utilities at the facilities. Int Trans Operat Res 19:789–807CrossRef
Taş D, Dellaert N, Van Woensel T, De Kok T (2013) Vehicle routing problem with stochastic travel times including soft time windows and service costs. Comput Biomed Res Operat Res 40:214–224CrossRef
Toriello A, Haskell WB,Poremba M (2012) A Dynamic Traveling Salesman Problem with Stochastic Arc Costs. Technical Report Optimization Online
Weisbrod G, Vary D, Treyz G (2001) Economic implications of congestion. Project A2–21 FY’97
Metadaten
Titel
The multi-path Traveling Salesman Problem with stochastic travel costs
verfasst von
Roberto Tadei
Guido Perboli
Francesca Perfetti
Publikationsdatum
31.07.2014
Verlag
Springer Berlin Heidelberg
Erschienen in
EURO Journal on Transportation and Logistics / Ausgabe 1/2017
Print ISSN: 2192-4376
Elektronische ISSN: 2192-4384
DOI
https://doi.org/10.1007/s13676-014-0056-2

Weitere Artikel der Ausgabe 1/2017

EURO Journal on Transportation and Logistics 1/2017 Zur Ausgabe

Research Paper

An extended demand responsive connector

Editorial

Introduction to the special issue on City Logistics

Research Paper

Vehicle routing problems for city logistics

Research Paper

Optimization of a city logistics transportation system with mixed passengers and goods

Premium Partner

    Bildnachweise