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:
Determination of Operating Parameters and Performance Analysis of Computer Networks with Paraconsistent Annotated Evidential Logic Eτ Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Combining Genetic Algorithm with Constructive and Refinement Heuristics for Solving the Capacitated Vehicle Routing Problem

Authors : Stanley Jefferson de Araujo Lima, Renato Alessandro Rocha Santos, Sidnei Alves de Araujo, Pedro Henrique Triguis Schimit

Published in: Advances in Production Management Systems. Initiatives for a Sustainable World

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

This work presents a hybrid strategy for optimization of Capacitated Vehicle Routing Problem (CVRP) that employs Genetic Algorithms (GA) combined with the heuristics of Gillett & Miller (GM) and Hill Climbing (HC). The first heuristic is used to incorporate feasible solutions in the initial population of the GA while the second is responsible for the refinement of solutions after a certain number of generations without improvements. The computational experiments showed that the proposed strategy presented good results for the optimization of CVRP with respect to the quality of solutions well as the computational cost.

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 Water Usage Charge in Brazil: Emergy Donor-Side Approach for Calculating Water Costs
next chapter Container Crane Controller with the Use of a NeuroFuzzy Network
Footnotes
Literature
1.
Kunnathur, A.S., Sundararaghavan, P., Sampath, S.: Dynamic rescheduling using a simulation-based expert system. J. Manufact. Technol. Manag. 15(2), 199–212 (2004)CrossRef
2.
Heinonen, J., Pettersson, F.: Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem. Appl. Math. Comput. 187(2), 989–998 (2007)MathSciNetCrossRefMATH
3.
Cordeau, J.F., Laporte, G., Potvin, J.Y., Savelsbergh, M.W.: Chapter 7 transportation on demand. In: Barnhart, C., Laporte, G. (eds.) Transportation, Handbooks in Operations Research and Management Science, vol. 14, pp. 429–466. Elsevier, Amsterdam (2007)
4.
Xu, H., Chen, Z.L., Rajagopal, S., Arunapuram, S.: Solving a practical pickup and delivery problem. Transp. Sci. 37(3), 347–364 (2003)CrossRef
5.
Gillett, B.E., Miller, L.R.: A heuristic algorithm for the vehicle-dispatch problem. Oper. Res. 22(2), 340–349 (1974)CrossRefMATH
6.
Laporte, G.: The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(3), 345–358 (1992)CrossRefMATH
7.
Laporte, G., Gendreau, M., Potvin, J.Y., Semet, F.: Classical and modern heuristics for the vehicle routing problem. Int. Trans. Oper. Res. 7(4–5), 285–300 (2000)MathSciNetCrossRef
8.
Cordeau, J.F., Laporte, G.: Tabu Search Heuristics for the Vehicle Routing Problem. Technical report (2002)
9.
Holland, J., Goldberg, D.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading (1989)
10.
Bjarnadóttir, Á.S.: Solving the vehicle routing problem with genetic algorithms. Ph.D. thesis, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark (2004)
11.
Vieira, H.P.: Metaheuristica para a Solução de Problemas de Roteamento de Veículos com Janela de Tempo. Ph.D. thesis, Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas (2008)
12.
Goldbarg, M.C., Luna, H.P.L.: Otimização Combinatória e Programação Linear: Modelos e Algoritmos, vol. 2. Elsevier, Amsterdam (2005)
13.
Engelbrecht, A.P.: Fundamentals of Computational Swarm Intelligence. Wiley, Hoboken (2006)
14.
Russell, S., Norvig, P., Intelligence, A.: A Modern Approach: Artificial Intelligence. Prentice-Hall, Egnlewood Cliffs (1995)MATH
15.
Christofides, N.: Vehicle Routing. A Guided Tour of Combinatorial Optimization. Wiley, New York (1985)MATH
16.
Reinelt, G., Wenger, K.M.: Maximally violated mod-p cuts for the capacitated vehicle-routing problem. INFORMS J. Comput. 18(4), 466–479 (2006)MathSciNetCrossRefMATH
17.
Ralphs, T., Pulleyblank, W., Trotter Jr., L.: On capacitated vehicle routing. In: Problem, Mathematical Programming (1998)
Metadata
Title
Combining Genetic Algorithm with Constructive and Refinement Heuristics for Solving the Capacitated Vehicle Routing Problem
Authors
Stanley Jefferson de Araujo Lima
Renato Alessandro Rocha Santos
Sidnei Alves de Araujo
Pedro Henrique Triguis Schimit
Copyright Year
2016
Book
Advances in Production Management Systems. Initiatives for a Sustainable World

Print ISBN: 978-3-319-51132-0

Electronic ISBN: 978-3-319-51133-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-51133-7_14

Premium Partner

    Image Credits