Skip to main content
Top

2014 | OriginalPaper | Chapter

A Parallel Matheuristic for Solving the Vehicle Routing Problems

Authors : Umman Mahir Yıldırım, Bülent Çatay

Published in: Computer-based Modelling and Optimization in Transportation

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

In this chapter, we present a matheuristic approach for solving the Vehicle Routing Problems (VRP). Our approach couples the Ant Colony Optimization (ACO) algorithm with solving the Set Partitioning (SP) formulation of the VRP. As the ACO algorithm, we use a rank-based ant system approach where an agent level-based parallelization is implemented. The interim solutions which correspond to single vehicle routes are collected in a solution pool. To prevent duplicate routes, we present an elimination rule based on an identification key that is used to differentiate the routes. After a pre-determined number of iterations, the routes accumulated in the solution pool are used to solve the SP formulation of the problem to find a complete optimal solution. Once the optimal solution is obtained it is fed back to ACO as an elite solution that can be used in the pheromone reinforcement procedure. Our experimental study using the well-known VRP with Time-Windows benchmark instances of Solomon shows that the proposed methodology provides promising results.

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!

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!

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!

Literature
1.
go back to reference Boschetti, M.A., Maniezzo, V., Roffilli, M., Röhler, A.B.: Matheuristics: optimization, simulation and control. In: Hybrid Metaheuristics. Lecture Notes Computer Science, vol. 5818, pp. 171–177 (2009) Boschetti, M.A., Maniezzo, V., Roffilli, M., Röhler, A.B.: Matheuristics: optimization, simulation and control. In: Hybrid Metaheuristics. Lecture Notes Computer Science, vol. 5818, pp. 171–177 (2009)
2.
go back to reference Bertazzi, L., Speranza, M.G.: Matheuristics for inventory routing problems. In: Montoya-Torres, J.R., Juan, A.A., Huatuco, L.H., Faulin, J., Rodriguez-Verjan, G.L. (eds.) Hybrid Algorithms for Service, Computing and Manufacturing Systems: Routing and Scheduling Solutions. IGI Global, Hershey (2011) Bertazzi, L., Speranza, M.G.: Matheuristics for inventory routing problems. In: Montoya-Torres, J.R., Juan, A.A., Huatuco, L.H., Faulin, J., Rodriguez-Verjan, G.L. (eds.) Hybrid Algorithms for Service, Computing and Manufacturing Systems: Routing and Scheduling Solutions. IGI Global, Hershey (2011)
3.
go back to reference Maniezzo, V., Stützle, T., Voß, S.: Matheuristics: Hybridizing Metaheuristics and Mathematical Programming. Springer, New-York (2010)CrossRef Maniezzo, V., Stützle, T., Voß, S.: Matheuristics: Hybridizing Metaheuristics and Mathematical Programming. Springer, New-York (2010)CrossRef
4.
go back to reference Doerner, K.F., Schmid, V.: Survey: matheuristics for rich vehicle routing problems. In: 7th International Workshop on Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 6373, pp. 206–221 (2010) Doerner, K.F., Schmid, V.: Survey: matheuristics for rich vehicle routing problems. In: 7th International Workshop on Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 6373, pp. 206–221 (2010)
5.
go back to reference Groër, C., Golden, B., Wasil, E.: A library of local search heuristics for the vehicle routing problem. Math. Program Comput. 2, 79–101 (2010)CrossRefMATHMathSciNet Groër, C., Golden, B., Wasil, E.: A library of local search heuristics for the vehicle routing problem. Math. Program Comput. 2, 79–101 (2010)CrossRefMATHMathSciNet
6.
7.
go back to reference Alvarenga, G.B., Mateus, G.R., 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 Alvarenga, G.B., Mateus, G.R., 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
8.
go back to reference Pirkwieser, S., Raidl, G.R.: Multiple variable neighborhood search enriched with ILP techniques for the periodic vehicle routing problem with time windows. In: Hybrid Metaheuristics. Lecture Notes Computer Science, vol. 5818, pp. 45–59 (2009) Pirkwieser, S., Raidl, G.R.: Multiple variable neighborhood search enriched with ILP techniques for the periodic vehicle routing problem with time windows. In: Hybrid Metaheuristics. Lecture Notes Computer Science, vol. 5818, pp. 45–59 (2009)
9.
go back to reference Mendoza, J.E., Villegas, J.G.: A multi-space sampling heuristic for the vehicle routing problem with stochastic demands. Optim. Lett. (2012) (Available online) Mendoza, J.E., Villegas, J.G.: A multi-space sampling heuristic for the vehicle routing problem with stochastic demands. Optim. Lett. (2012) (Available online)
10.
go back to reference Archetti, C., Speranza, M., Savelsbergh, M.: An optimization-based heuristic for the split delivery vehicle routing problem. Transp. Sci. 42, 22–31 (2008)CrossRef Archetti, C., Speranza, M., Savelsbergh, M.: An optimization-based heuristic for the split delivery vehicle routing problem. Transp. Sci. 42, 22–31 (2008)CrossRef
11.
go back to reference Gulczynski, D., Golden, B., Wasil, E.: The period vehicle routing problem: new heuristics and real-world variants. Transp. Res. E-Log. 47, 648–668 (2011)CrossRef Gulczynski, D., Golden, B., Wasil, E.: The period vehicle routing problem: new heuristics and real-world variants. Transp. Res. E-Log. 47, 648–668 (2011)CrossRef
12.
13.
go back to reference Subramanian, A., Penna, P.H.V., Uchoa, E., Ochi, L.S.: A hybrid algorithm for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res. 221, 285–295 (2012)CrossRefMATHMathSciNet Subramanian, A., Penna, P.H.V., Uchoa, E., Ochi, L.S.: A hybrid algorithm for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res. 221, 285–295 (2012)CrossRefMATHMathSciNet
14.
go back to reference Subramanian, A., Uchoa, E., Ochi, L.S.: A hybrid algorithm for a class of vehicle routing problems. Comput. Oper. Res. 40, 2519–2531 (2013)CrossRef Subramanian, A., Uchoa, E., Ochi, L.S.: A hybrid algorithm for a class of vehicle routing problems. Comput. Oper. Res. 40, 2519–2531 (2013)CrossRef
15.
go back to reference Villegas, J.G., Prins, C., Prodhon, C., Medaglia, A.L., Velasco, N.: A matheuristic for the truck and trailer routing problem. Eur. J. Oper. Res. 230, 231–244 (2013)CrossRefMathSciNet Villegas, J.G., Prins, C., Prodhon, C., Medaglia, A.L., Velasco, N.: A matheuristic for the truck and trailer routing problem. Eur. J. Oper. Res. 230, 231–244 (2013)CrossRefMathSciNet
16.
go back to reference Calvo, R.W., Touati-Moungla, N.: A matheuristic for the dial-a-ride problem. In: Network Optimization. Lecture Notes Computer Science, vol. 6701, pp. 450–463 (2011) Calvo, R.W., Touati-Moungla, N.: A matheuristic for the dial-a-ride problem. In: Network Optimization. Lecture Notes Computer Science, vol. 6701, pp. 450–463 (2011)
17.
go back to reference Rodríguez-Martín, I., Salazar-González, J.J.: The multi-commodity one-to-one pickup-and-delivery traveling salesman problem: a matheuristic. In: Network Optimization. Lecture Notes Computer Science, vol. 6701, pp. 401–405 (2011) Rodríguez-Martín, I., Salazar-González, J.J.: The multi-commodity one-to-one pickup-and-delivery traveling salesman problem: a matheuristic. In: Network Optimization. Lecture Notes Computer Science, vol. 6701, pp. 401–405 (2011)
18.
go back to reference Pillac, V., Guéret, C., Medaglia, A.: A parallel matheuristic for the technician routing and scheduling problem. Optim. Lett. (2012) (Available online ) Pillac, V., Guéret, C., Medaglia, A.: A parallel matheuristic for the technician routing and scheduling problem. Optim. Lett. (2012) (Available online )
21.
go back to reference Blosch, J.: Effective Java, 2nd edn. Addison-Wesley, Boston (2008) Blosch, J.: Effective Java, 2nd edn. Addison-Wesley, Boston (2008)
22.
go back to reference Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35, 254–265 (1987)CrossRefMATHMathSciNet Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35, 254–265 (1987)CrossRefMATHMathSciNet
23.
go back to reference Russell, R.A., Chiang, W-C.: Scatter search for the vehicle routing problem with time windows. Eur. J. Oper. Res. 169, 606–622 (2006) Russell, R.A., Chiang, W-C.: Scatter search for the vehicle routing problem with time windows. Eur. J. Oper. Res. 169, 606–622 (2006)
24.
go back to reference Cordeau, J.-F., Laporte, G., Mercier, A.: A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52, 928–936 (2001)CrossRefMATH Cordeau, J.-F., Laporte, G., Mercier, A.: A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52, 928–936 (2001)CrossRefMATH
25.
go back to reference Jung, S., Moon, B-R.: A hybrid genetic algorithm for the vehicle routing problem with time windows. In: Proceedings of the 2002 Genetic and Evolutionary Computation Conference, pp. 1309–1316. GECCO 2002, New York (2002) Jung, S., Moon, B-R.: A hybrid genetic algorithm for the vehicle routing problem with time windows. In: Proceedings of the 2002 Genetic and Evolutionary Computation Conference, pp. 1309–1316. GECCO 2002, New York (2002)
26.
go back to reference Oliveira, H.C.B., Vasconcelos, G.C.: A hybrid search method for the vehicle routing problem with time windows. Ann. Oper. Res. 180, 125–144 (2008) Oliveira, H.C.B., Vasconcelos, G.C.: A hybrid search method for the vehicle routing problem with time windows. Ann. Oper. Res. 180, 125–144 (2008)
27.
go back to reference 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 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
28.
go back to reference Rochat, Y., Taillard, E.D.: Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995)CrossRefMATH Rochat, Y., Taillard, E.D.: Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995)CrossRefMATH
29.
go back to reference Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Principles and Practice of Constraint Programming (CP’98). Lecture Notes Computer Science, vol. 1520, pp. 417–431 (1998) Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Principles and Practice of Constraint Programming (CP’98). Lecture Notes Computer Science, vol. 1520, pp. 417–431 (1998)
Metadata
Title
A Parallel Matheuristic for Solving the Vehicle Routing Problems
Authors
Umman Mahir Yıldırım
Bülent Çatay
Copyright Year
2014
DOI
https://doi.org/10.1007/978-3-319-04630-3_35

Premium Partner