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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Novel Approach to Multimedia Ontology Engineering for Automated Reasoning over Audiovisual LOD Datasets Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

How to Generate Benchmarks for Rich Routing Problems?

verfasst von : Marcin Cwiek, Jakub Nalepa, Marcin Dublanski

Erschienen in: Intelligent Information and Database Systems

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

In this paper, we show how to generate challenging benchmark tests for rich vehicle routing problems (VRPs) using a new heuristic algorithm (termed HeBeG—Heuristic Benchmark Generator). We consider a modified VRP with time windows, in which the depot does not define its time window. Additionally, the taxicab metric is utilized to determine the distance between travel points, instead of a standard Euclidean metric. HeBeG was used to create a test set for the qualifying round of Deadline24—an international 24-hour programming marathon. Finally, we compare the best results submitted to the server during the qualifying round of the contest with the routing schedules elaborated using other algorithms, including a new heuristics proposed in this paper.

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

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
Vorheriges Kapitel Enhanced Guided Ejection Search for the Pickup and Delivery Problem with Time Windows
Nächstes Kapitel Formal a Priori Power Analysis of Elements of a Communication Graph
Fußnoten
Literatur
1.
Nalepa, J., Blocho, M.: Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows. Soft Comput. 1–19 (2015). doi:10.​1007/​s00500-015-1642-4
2.
Kalina, P., Vokrinek, J.: Parallel solver for vehicle routing and pickup and delivery problems with time windows based on agent negotiation. In: Proceedings of IEEE SMC, pp. 1558–1563 (2012)
3.
Lau, H.C., Liang, Z.: Pickup and delivery with time windows: algorithms and test case generation. Int. J. Artif. Intell. Tools 11(03), 455–472 (2002)CrossRef
4.
Cordeau, J.F., Laporte, G., Savelsbergh, M.W., Vigo, D.: Chapter 6 vehicle routing. In: Barnhart, C., Laporte, G. (eds.) Transportation. Handbooks in Operations Research and Management Science, vol. 14, pp. 367–428. Elsevier (2007)
5.
Bard, J.F., Kontoravdis, G., Yu, G.: A branch-and-cut procedure for the vehicle routing problem with time windows. Trans. Sci. 36(2), 250–269 (2002)CrossRefMATH
6.
Ropke, S., Cordeau, J.F., Laporte, G.: Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49(4), 258–272 (2007)MathSciNetCrossRefMATH
7.
Abdallah, K.S., Jang, J.: An exact solution for vehicle routing problems with semi-hard resource constraints. Comp. Ind. Eng. 76, 366–377 (2014)CrossRef
8.
Bettinelli, A., Ceselli, A., Righini, G.: A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows. Math. Program. Comput. 6(2), 171–197 (2014)MathSciNetCrossRefMATH
9.
Chabrier, A.: Vehicle routing problem with elementary shortest path based column generation. Comput. Oper. Res. 33(10), 2972–2990 (2006)MathSciNetCrossRefMATH
10.
Baldacci, R., Mingozzi, A., Roberti, R.: New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5), 1269–1283 (2011)MathSciNetCrossRefMATH
11.
Bent, R., Van Hentenryck, P.: A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 123–137. Springer, Heidelberg (2003)CrossRef
12.
Parragh, S.N., Doerner, K.F., Hartl, R.F.: A survey on pickup and delivery problems. Journal fur Betriebswirtschaft 58(1), 21–51 (2008)CrossRef
13.
Nanry, W.P., Barnes, J.W.: Solving the pickup and delivery problem with time windows using reactive tabu search. Transp. Res. 34(2), 107–121 (2000)CrossRef
14.
Ropke, S., Pisinger, D.: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40(4), 455–472 (2006)CrossRef
15.
Nagata, Y., Kobayashi, S.: Guided ejection search for the pickup and delivery problem with time windows. In: Cowling, P., Merz, P. (eds.) EvoCOP 2010. LNCS, vol. 6022, pp. 202–213. Springer, Heidelberg (2010)CrossRef
16.
Nalepa, J., Blocho, M.: Co-operation in the parallel memetic algorithm. Int. J. Parallel Program. 43(5), 812–839 (2015)CrossRef
17.
Cherkesly, M., Desaulniers, G., Laporte, G.: A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading. Comput. Oper. Res. 62, 23–35 (2015)MathSciNetCrossRef
Metadaten
Titel
How to Generate Benchmarks for Rich Routing Problems?
verfasst von
Marcin Cwiek
Jakub Nalepa
Marcin Dublanski
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Intelligent Information and Database Systems

Print ISBN: 978-3-662-49380-9

Electronic ISBN: 978-3-662-49381-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-49381-6_38