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:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

An Investigation on Compound Neighborhoods for VRPTW

verfasst von : Binhui Chen, Rong Qu, Ruibin Bai, Hisao Ishibuchi

Erschienen in: Operations Research and Enterprise Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The Vehicle Routing Problem with Time Windows (VRPTW) consists of constructing least cost routes from a depot to a set of geographically scattered service points and back to the depot, satisfying service time intervals and capacity constraints. A Variable Neighbourhood Search algorithm which can simultaneously optimize both objectives of VRPTW (to minimize the number of vehicles and the total travel distance) is proposed in this paper. The three compound neighbourhood operators are developed with regards to problem characteristics of VRPTW. Compound neighbourhoods combine a number of independent neighbourhood operators to explore a larger scale of neighbourhood search space. Performance of these operators has been investigated and is evaluated on benchmark problems.

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
Nächstes Kapitel Product Modularization Using Cuckoo Search Algorithm
Literatur
1.
Laporte, G.: The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59, 345–358 (1992)CrossRefMATH
2.
Cordeau, J.F., Desaulniers, G., Desrosiers, J., Solomon, M., Soumis, F.: VRP with time windows. In: The vehicle routing problem, Society for Industrial and Applied Mathematics, pp. 157–193 (2001)
3.
Bräysy, O.: A reactive variable neighborhood search for the vehicle-routing problem with time windows. INFORMS J. Comput. 15, 347–368 (2003)MathSciNetCrossRefMATH
4.
Ghoseiri, K., Ghannadpour, S.F.: Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Appl. Soft Comput. 10, 1096–1107 (2010)CrossRef
5.
6.
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35, 254–265 (1987)MathSciNetCrossRefMATH
7.
Bräysy, O., Gendreau, M.: Metaheuristics for the vehicle routing problem with time windows. Report STF42 A 1025 (2001)
8.
Potvin, J.Y., Kervahut, T., Garcia, B.L., Rousseau, J.M.: The vehicle routing problem with time windows part I: tabu search. INFORMS J. Comput. 8, 158–164 (1996)CrossRefMATH
9.
Van Breedam, A.: Improvement heuristics for the vehicle routing problem based on simulated annealing. Eur. J. Oper. Res. 86, 480–490 (1995)CrossRefMATH
10.
Hansen, P., Mladenović, N., Pérez, J.A.M.: Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175, 367–407 (2010)MathSciNetCrossRefMATH
11.
12.
Hansen, P., Mladenović, N.: J-means: a new local search heuristic for minimum sum of squares clustering. Pattern Recogn. 34, 405–413 (2001)CrossRefMATH
13.
Hansen, P., Mladenović, N., Perez-Britos, D.: Variable neighborhood decomposition search. J. Heuristics 7, 335–350 (2001)CrossRefMATH
14.
Hansen, P., Mladenović, N., Urośević, D.: Variable neighborhood search and local branching. Comput. Oper. Res. 33, 3034–3045 (2006)CrossRefMATH
15.
Polacek, M., Hartl, R.F., Doerner, K., Reimann, M.: A variable neighborhood search for the multi depot vehicle routing problem with time windows. J. Heuristics 10, 613–627 (2004)CrossRef
16.
Fleszar, K., Osman, I.H., Hindi, K.S.: A variable neighbourhood search algorithm for the open vehicle routing problem. Eur. J. Oper. Res. 195, 803–809 (2009)CrossRefMATH
17.
Hemmelmayr, V.C., Doerner, K.F., Hartl, R.F.: A variable neighborhood search heuristic for periodic routing problems. Eur. J. Oper. Res. 195, 791–802 (2009)CrossRefMATH
18.
19.
Or, I.: Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Xerox University Microfilms (1976)
20.
Osman, I.H.: Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann. Oper. Res. 41, 421–451 (1993)CrossRefMATH
21.
Taillard, A., Badeau, P., Gendreau, M., Guertin, F.A., Potvin, J.Y.: A tabu search heuristic for the vehicle routing problem with soft time windows. Transp. Sci. 31, 170–186 (1997)CrossRefMATH
22.
Ergun, Ö., Orlin, J.B., Steele-Feldman, A.: Creating very large scale neighborhoods out of smaller ones by compounding moves. J. Heuristics 12, 115–140 (2006)CrossRefMATH
23.
Rego, C.: A subpath ejection method for the vehicle routing problem. Manag. Sci. 44, 1447–1459 (1998)CrossRefMATH
24.
Dueck, G.: New optimization heuristics: the great deluge algorithm and the record-to-record travel. J. Comput. Phys. 104, 86–92 (1993)CrossRefMATH
25.
26.
Alvarenga, G.B., Mateus, G.R., De Tomi, G.: A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Comput. Oper. Res. 34, 1561–1584 (2007)CrossRefMATH
27.
Tan, K., Chew, Y., Lee, L.: A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Comput. Optim. Appl. 34, 115–151 (2006)MathSciNetCrossRefMATH
28.
Küçükoğlu, İ., Öztürk, N.: An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows. Comput. Ind. Eng. 86, 60–68 (2014)
29.
Kallehauge, B., Larsen, J., Madsen, O.B.: Lagrangian duality applied to the vehicle routing problem with time windows. Comput. Oper. Res. 33, 1464–1487 (2006)MathSciNetCrossRefMATH
30.
Cook, W., Rich, J.L.: A parallel cutting-plane algorithm for the vehicle routing problem with time windows. Computational and Applied Mathematics Department, Rice University, Houston, TX, Technical report (1999)
31.
Ombuki, B., Ross, B.J., Hanshar, F.: Multi-objective genetic algorithms for vehicle routing problem with time windows. Appl. Intell. 24, 17–30 (2006)CrossRef
32.
Chiang, W.C., Russell, R.A.: A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS J. Comput. 9, 417–430 (1997)CrossRefMATH
33.
Rochat, Y., Taillard, É.D.: Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995)CrossRefMATH
34.
Ursani, Z., Essam, D., Cornforth, D., Stocker, R.: Localized genetic algorithm for vehicle routing problem with time windows. Appl. Soft Comput. 11, 5375–5390 (2011)CrossRef
Metadaten
Titel
An Investigation on Compound Neighborhoods for VRPTW
verfasst von
Binhui Chen
Rong Qu
Ruibin Bai
Hisao Ishibuchi
Copyright-Jahr
2017
Buch
Operations Research and Enterprise Systems

Print ISBN: 978-3-319-53981-2

Electronic ISBN: 978-3-319-53982-9

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-53982-9_1