Applied Research of Improved Hybrid Genetic Algorithm in Multiple Constraints Location - Routing Problem

Abstract:

The location routing problem (LRP), which simultaneously tackles both facility location and the vehicle routing decisions to minimize the total system cost, is of great importance in designing an integrated logistic distribution network. In this paper a simulated annealing algorithm (SA) based hybrid genetic algorithm was developed to solve the LRP with capacity constraints (CLRP) on depots and routes. The proposed hybrid genetic algorithm modified the population generation method, genetic operators and recombination strategy and realized the combination of the local searching ability of SA and global searching ability of GA. To evaluate the performance of the proposed approach, we conducted an experimental study and compared its results with other heuristics on a set of well-known Barreto Benchmark instances. The experimental results verified the feasibility and effectiveness of our approach.

• Periodical: Advanced Materials Research (Volumes 791-793)
• Pages: 1176-1179
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.791-793.1176
• Online since: September 2013
• Authors: Yan Fen Jiang, Chun Ling Feng
• Keywords: Genetic Algorithm (GA), Integrated Logistic Distribution Network, Location-Routing Problem, Simulated Annealing Algorithm

References

[1] Hokey Min, Vaidyanathan Jayaraman, Rajesh Srivastava. Combined location-routing problems: A synthesis and future research direction [J]. European Journal of Operational Research, 1998, 108: 1-15.

DOI: 10.1016/s0377-2217(97)00172-0

[2] Barreto, S. S. Analysis and modeling of location-routing problems. Ph.D. Thesis, University of Aveiro, Aveiro, Portugal, (2004).

[3] Salhi S, GK. Rand. The effect of ignoring routes when locating depots [J]. European Journal of Operational Research, 1989, 39: 150-156.

DOI: 10.1016/0377-2217(89)90188-4

[4] Dilek Tuzun, Laura I. Burke. A two-phase tabu search approach to the location routing problem [J]. European Journal of Operational Research, 1999, 116(1): 87-99.

DOI: 10.1016/s0377-2217(98)00107-6

[5] Chien, T.W., Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems. Decision Sciences. 1993, 24(5)：995-1021.

DOI: 10.1111/j.1540-5915.1993.tb00500.x

[6] Barreto, Ferreira, Paixão, &Santos. Using clustering analysis in a capacitated location-routing problem [J]. European Journal of Operational Research, 2007, 179(3): 968-977.

DOI: 10.1016/j.ejor.2005.06.074

[7] Bouhafs, Hajjam, Koukam. A combination of simulated annealing and ant colony system for the capacitated location-routing problem [J]. Lecture Notes in Computer Science, 2006, 4251: 409-416.

DOI: 10.1007/11892960_50

[8] Albareda-Sambola, M., Teodor Gabriel Crainic. Acompact model and tight bounds for a combined location-routing problem. Computers and Operations Research [J]. Computers and Operations Research, 2005, 32(3): 407-428.

DOI: 10.1016/s0305-0548(03)00245-4

[9] Christophe Duhamel, Philippe Lacomme, Christian Prins, Caroline Prodhon. A GRASP×ELS approach for the capacitated location-routing problem [J]. Computers and Operations Research, 2010, 37: 1912-(1923).

DOI: 10.1016/j.cor.2009.07.004