Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Novel Approach to Multimedia Ontology Engineering for Automated Reasoning over Audiovisual LOD Datasets Read chapter Read first chapter

2016 | OriginalPaper | Chapter

How to Generate Benchmarks for Rich Routing Problems?

Authors : Marcin Cwiek, Jakub Nalepa, Marcin Dublanski

Published in: Intelligent Information and Database Systems

Publisher: Springer Berlin Heidelberg

Log in

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

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.

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

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!

inform now
previous chapter Enhanced Guided Ejection Search for the Pickup and Delivery Problem with Time Windows
next chapter Formal a Priori Power Analysis of Elements of a Communication Graph
Footnotes
Literature
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
Metadata
Title
How to Generate Benchmarks for Rich Routing Problems?
Authors
Marcin Cwiek
Jakub Nalepa
Marcin Dublanski
Copyright Year
2016
Publisher
Springer Berlin Heidelberg
Book
Intelligent Information and Database Systems

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

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

Copyright Year: 2016

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

Premium Partner

    Image Credits