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:
Testing Modified Confusion Entropy as Split Criterion for Decision Trees Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Constraint Programming Based Algorithm for Solving Large-Scale Vehicle Routing Problems

Authors : Bochra Rabbouch, Foued Saâdaoui, Rafaa Mraihi

Published in: Hybrid Artificial Intelligent Systems

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Smart cities management has become currently an interesting topic where recent decision aid making algorithms are essential to solve and optimize their related problems. A popular transportation optimization problem is the Vehicle Routing Problem (VRP) which is high complicated in such a way that it is categorized as a NP-hard problem. VRPs are famous and appear as influential problems that are widely present in many real-world industrial applications. They have become an elemental part of economy, the enhancement of which arises in a significant reduction in costs.
The basic version of VRPs, the Capacitated VRP (CVRP) occupies a central position for historical and practical considerations since there are important real-world systems can be satisfactorily modeled as a CVRP. A Constraint Programming (CP) paradigm is used to model and solve the CVRP by applying interval and sequence variables in addition to the use of a transition distance matrix to attain the objective. An empirical study over 52 CVRP classical instances, with a number of nodes that varies from 16 to 200, and 20 CVRP large-scale instances, with a number of nodes that varies from 106 to 459, shows the relative merits of our proposed approach. It shows also that the CP paradigm tackles successfully large-scale problems with a percentage deviation varying from 2% to 10% where several exact and heuristic algorithms fail to tackle them and only a few meta-heuristics can probably solve instances with a such big number of customers.

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 Measuring Lower Limb Alignment and Joint Orientation Using Deep Learning Based Segmentation of Bones
next chapter Application of Extractive Text Summarization Algorithms to Speech-to-Text Media
Footnotes
Literature
1.
Akhand, M.A.H., Paya, Z.J., Murase, K.: Capacitated vehicle routing problem solving using adaptive sweep and velocity tentative PSO. Int. J. Adv. Comput. Sci. Appl. 8(12), 288–295 (2017)
2.
Altinel, I.K., Öncan, T.: A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem. J. Oper. Res. Soc. 56(8), 954–961 (2005)CrossRef
3.
Baran, E.: Route determination for capacitated vehicle routing problem with two different hybrid heuristic algorithm. Int. J. Eng. Sci. Appl. 2(2), 55–64 (2018)
4.
Borčinová, Z.: Two models of the capacitated vehicle routing problem. Croatian Oper. Res. Rev. 8, 463–469 (2017)MathSciNetCrossRef
5.
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12, 568–581 (1964)CrossRef
6.
Comert, S.E., Yazgan, H.R., Kir, S., Yener, F.: A cluster first-route second approach for a capacitated vehicle routing problem: a case study. Int. J. Procurement Manage. 11(4), 399–419 (2018)CrossRef
7.
8.
Faulin, J., García del Valle, A.: Solving the capacitated vehicle routing problem using the ALGELECT electrostatic algorithm. J. Oper. Res. Soc. 59(12), 1685–1695 (2008)CrossRef
9.
Gillet, B.E., Johnson, J.G.: Multi-terminal vehicle-dispatch algorithm. Omega 4, 711–718 (1976)CrossRef
10.
Goli, A., Aazami, A., Jabbarzadeh, A.: Accelerated cuckoo optimization algorithm for capacitated vehicle routing problem in competitive conditions. Int. J. Artif. Intell. 16(1), 88–112 (2018)
11.
Guimarans, D., Herrero, R., Riera, D., JuanJuan, A.A., Ramos, J.: Combining probabilistic algorithms, constraint programming and lagrangian relaxation to solve the vehicle routing problem. Ann. Math. Artif. Intell. 62(3), 299–315 (2011)MathSciNetCrossRef
12.
Ham, A., Cakici, E.: Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches. Comput. Ind. Eng. 102, 160–165 (2016)CrossRef
13.
Hannan, M.A., Akhtar, M., Begum, R.A., Basri, H., Hussain, A., Scavino, E.: Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm. Waste Manage. 71, 31–41 (2018)CrossRef
14.
Kerwad, M.M., Othman, Z.A., Zainudin, S.: Improved water flow-like algorithm for capacitated vehicle routing problem. J. Theor. Appl. Inf. Technol. 96(15), 4836–4853 (2018)
15.
Kir, S., Yazgan, H.R., Tüncel, E.: A novel heuristic algorithm for capacitated vehicle routing problem. J. Ind. Eng. Int. 13(3), 323–330 (2017)CrossRef
16.
17.
Laborie, P., Rogerie, J., Shaw, P., Vilm, P.: IBM ILOG CP optimizer for scheduling. Constraints 23(2), 210–250 (2018)MathSciNetCrossRef
18.
Noorizadegan, M., Chen, B.: Vehicle routing with probabilistic capacity constraints. Eur. J. Oper. Res. 270(2), 544–555 (2018)MathSciNetCrossRef
19.
Na, B., Jun, Y., Kim, B.I.: Some extensions to the sweep algorithm. Int. J. Adv. Manufact. Technol. 56, 1057–1067 (2011)CrossRef
20.
21.
Rabbouch, B., Saadaoui, F., Mraihi, R.: Empirical mode simulated annealing for solving the capacitated vehicle routing problem. J. Exp. Theor. Artif. Intell. (2019, forthcoming)
22.
23.
Sahraeian, R., Esmaeili, M.: A multi-objective two-echelon capacitated vehicle routing problem for perishable products. J. Ind. Syst. Eng. 11(2), 62–84 (2018)
24.
Tlili, T., Faiz, S., Krichen, S.: A hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem. Procedia Soc. Behav. Sci. 109, 779–783 (2014)CrossRef
25.
Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., Subramanian, A.: New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3), 845–858 (2017)MathSciNetCrossRef
Metadata
Title
Constraint Programming Based Algorithm for Solving Large-Scale Vehicle Routing Problems
Authors
Bochra Rabbouch
Foued Saâdaoui
Rafaa Mraihi
Copyright Year
2019
Book
Hybrid Artificial Intelligent Systems

Print ISBN: 978-3-030-29858-6

Electronic ISBN: 978-3-030-29859-3

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-29859-3_45

Premium Partner

    Image Credits