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:
Optimization of Home Care Visits Schedule by Genetic Algorithm Read chapter Read first chapter

2018 | OriginalPaper | Chapter

A New Binary Encoding Scheme in Genetic Algorithm for Solving the Capacitated Vehicle Routing Problem

Authors : Stanley Jefferson de A. Lima, Sidnei Alves de Araújo

Published in: Bioinspired Optimization Methods and Their Applications

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

In the last decades the Vehicle Routing Problem (VRP) and its ramifications, including the Capacitated Vehicle Routing Problem (CVRP), have attracted the attention of researchers mainly because their presence in many practical situations. Due to the difficulties encountered in their solutions, such problems are usually solved by means of heuristic and metaheuristics algorithms, among which is the Genetic Algorithm (GA). The solution of CVRP using GA requires a solution encoding step, which demands a special care to avoid high computational cost and to ensure population diversity that is essential for the convergence of GA to global optimal or sub-optimal solutions. In this work, we investigated a new binary encoding scheme employed by GA for solving the CVRP. Conducted experiments demonstrated that the proposed binary encoding is able to provide good solutions and is suitable for practical applications that require low 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 Comparing Boundary Control Methods for Firefly Algorithm
next chapter Ensemble and Fuzzy Techniques Applied to Imbalanced Traffic Congestion Datasets: A Comparative Study
Literature
1.
Dalfard, V.M., Kaveh, M., Nosratian, N.E.: Two meta-heuristic algorithms for two-echelon location-routing problem with vehicle fleet capacity and maximum route length constraints. Neural Comput. Appl. 23(7–8), 2341–2349 (2013)CrossRef
2.
Nazif, H., Lee, L.S.: Optimised crossover genetic algorithm for capacitated vehicle routing problem. Appl. Math. Model. 36(5), 2110–2117 (2012)MathSciNetCrossRef
3.
Vieira, H.P.: Metaheuristic to solve vehicles routing problems with time windows (2013)
4.
Lau, H.C., Chan, T., Tsui, W., Pang, W.: Application of genetic algorithms to solve the multidepot vehicle routing problem. IEEE Trans. Autom. Sci. Eng. 7(2), 383–392 (2010)CrossRef
5.
Bermudez, C., Graglia, P., Stark, N., Salto, C., Alfonso, H.: Comparison of recombination operators in panmictic and cellular GAs to solve a vehicle routing problem. Intel. Artif. Rev. Iberoam. de Intel. Artif. 14(46), 34–44 (2010)
6.
Wang, C.H., Lu, J.Z.: An effective evolutionary algorithm for the practical capacitated vehicle routing problems. J. Intell. Manuf. 21(4), 363–375 (2010)MathSciNetCrossRef
7.
Tasan, A.S., Gen, M.: A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Comput. Ind. Eng. 62(3), 755–761 (2012)CrossRef
8.
Ursani, Z., Essam, D., Cornforth, D., Stocker, R.: Localized genetic algorithm for vehicle routing problem with time windows. Appl. Soft Comput. 11(8), 5375–5390 (2011)CrossRef
9.
Lu, C.C., Vincent, F.Y.: Data envelopment analysis for evaluating the efficiency of genetic algorithms on solving the vehicle routing problem with soft time windows. Comput. Ind. Eng. 63(2), 520–529 (2012)CrossRef
10.
Kuo, R., Zulvia, F.E., Suryadi, K.: Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand – a case study on garbage collection system. Appl. Math. Comput. 219(5), 2574–2588 (2012)MathSciNetMATH
11.
Vidal, T., Crainic, T.G., Gendreau, M., Lahrichi, N., Rei, W.: A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60(3), 611–624 (2012)MathSciNetCrossRef
12.
Reiter, P., Gutjahr, W.J.: Exact hybrid algorithms for solving a bi-objective vehicle routing problem. Cent. Eur. J. Oper. Res. 20(1), 19–43 (2012)MathSciNetCrossRef
13.
Osaba, E., Diaz, F., Onieva, E.: Golden ball: a novel meta-heuristic to solve combinatorial optimization problems based on soccer concepts. Appl. Intell. 41(1), 145–166 (2014)CrossRef
14.
Lima, S.J.A., Araújo, S.A., Schimit, P.H.: A hybrid approach based on genetic algorithm and nearest neighbor heuristic for solving the capacitated vehicle routing problem. Acta Scientiarum Technology (2018)
15.
Laporte, G.: The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(3), 345–358 (1992)CrossRef
16.
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989)MATH
17.
Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D.: Genetic Programming: An Introduction, vol. 1. Morgan Kaufmann, San Francisco (1998)CrossRef
18.
Brooker, R.: Concepts of Genetics. McGraw-Hill Higher Education, New York (2012)
19.
Kumar, R.: Novel encoding scheme in genetic algorithms for better fitness. Int. J. Eng. Adv. Technol. 1(6), 214–219 (2012)
20.
Kumar, A.: Encoding schemes in genetic algorithm. Int. J. Adv. Res. IT Eng. 2(3), 1–7 (2013)
21.
Wall, M.: GAlib: a C++ library of genetic algorithm components (1996)
22.
Grassi, F.: Optimization by genetic algorithms of the sequencing of production orders in job shop environments. Master’s Dissertation, Industrial Engineering Post Graduation Program, Universidade Nove de Julho (UNINOVE) (2014)
23.
Reinelt, G., Wenger, K.M.: Maximally violated mod-p cuts for the capacitated vehicle-routing problem. INFORMS J. Comput. 18(4), 466–479 (2006)MathSciNetCrossRef
24.
Ralphs, T., Pulleyblank, W., Trotter Jr., L.: On capacitated vehicle routing. Problem, Mathematical Programming (1998)
Metadata
Title
A New Binary Encoding Scheme in Genetic Algorithm for Solving the Capacitated Vehicle Routing Problem
Authors
Stanley Jefferson de A. Lima
Sidnei Alves de Araújo
Copyright Year
2018
Book
Bioinspired Optimization Methods and Their Applications

Print ISBN: 978-3-319-91640-8

Electronic ISBN: 978-3-319-91641-5

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-91641-5_15

Premium Partner

    Image Credits