A concurrent evolutionary approach for rich combinatorial optimization

ABSTRACT

In this paper, we propose a meta-heuristic method based on the concurrent evolution of heterogeneous populations, decomposition/recomposition principles and specialized operators to address multi-attribute, rich, combinatorial optimization problems. We illustrate the method through an application to a rich Vehicle Routing Problem that considers duration and capacity constraints as well as time windows, multiple periods and multiple depots.

REFERENCES

• 1: http://neumann.hec.ca/chairedistributique/data
• 2: Enrique Alba, Parallel Metaheuristics: A New Class of Algorithms, Wiley-Interscience, 2005
• 3: J. Berger and M. Barkaoui (2004). A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research, 31:2037--2053.
• 4: J.-F. Cordeau, G. Laporte and A. Mercier (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52: 928--936.
• 5: T.G. Crainic, B. Di Chiara, M. Nonato and L. Tarricone (2006). Tackling electrosmog in completely configured 3G networks by parallel cooperative meta-heuristics. IEEE Wireless Communications, 13(6): 34--41.
• 6: T.G. Crainic and H. Nourredine (2005). Parallel meta-heuristics applications, In Parallel Metaheuristics, E. Alba, editor, John Wiley & Sons publishers, Hoboken, NJ, 447--494.
• 7: T.G. Crainic and M. Toulouse (2003). Parallel strategies for meta-heuristics. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, Kluwer Academic Publishers, Norwell, MA, 475--513.
• 8: T.G. Crainic and M. Toulouse (2009). Explicit and emergent cooperation schemes for search algorithms. In Reactive Search and Intelligent Optimization, R. Battiti, M. Brunato, F. Mascia (Eds.), Vol 45 of Operations Research/Computer Science Interfaces Series, Springer.
• 9: P.M. Francis, K.R. Smilowitz and M. Tzur (2008). The Period Vehicle Routing Problem and its Extensions. The Vehicle Routing Problem: Latest Advances and New Challenges, in Operations Research/Computer Science Interfaces Series, 73--102.
• 10: B. L. Golden , A. A. Assad , E. A. Wasil, Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries, The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 01
• 11: E. Hadjiconstantinou and R. Baldacci (1998). A multi-depot period vehicle routing problem arising in the utilities sector. Journal of the Operational Research Society, 49: 1239--1248.
• 12: R.F. Hartl, G. Hasle and G.K. Janssens (2006). Special issue on rich vehicle routing problems. Central European Journal of Operations Research, 14.
• 13: J. Homberger and H. Gehring (1999). Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR, 37: 297--318.
• 14: J. Homberger and H. Gehring (2005). A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research, 162: 220--238.
• 15: N. Jozefowiez, F. Semet and E.-G. Talbi (2008). Multi-objective vehicle routing problems. European Journal of Operational Research, 189: 293--309.
• 16: K.H. Kang, Y.H. Lee and B.K. Lee (2005). An exact algorithm for multi-depot and multi-period scheduling problem. Computational Science and Its Applications -- ICCSA 2005, in Lecture Notes in Computer Science, 3483: 350--359.
• 17: P. Lacomme, C. Prins and W. Ramdane-Chérif (2005). Evolutionary algorithms for periodic arc routing problems. European Journal of Operational Research, 165: 535--553.
• 18: P. Parthanadee and R. Logendran (2006). Periodic product distribution from multi--depots under limited suplies. IIE Transactions, 38: 1009--1026.
• 19: C. Prins (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31: 1985--2002.
• 20: Paolo Toth , Daniele Vigo, The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 01
• 21: W.-T. Yang and L.-C. Chu (2000). A heuristic algorithm for the multi-depot periodic Vehicle Routing Problems. Journal of Information & Optimization Sciences, 22: 359--367.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms

Keywords:
combinatorial optimization, concurrent evolution, cooperative algorithms, multi-attribute problems, rich vrp