A Comparison of Four Multi-Objective Meta-Heuristics for a Capacitated Location-Routing Problem

Document Type: Research Paper

Authors

1 Department of Industrial Engineering, Shahed University, Tehran, Iran

2 Departmentof Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

Abstract

In this paper, we study an integrated logistic system where the optimal location of depots and vehicles routing are considered simultaneously. This paper presents a new mathematical model for a multi-objective capacitated location-routing problem with a new set of objectives consisting of the summation of economic costs, summation of social risks and demand satisfaction score. A new multi-objective adaptative simulated annealing (MOASA) is proposed to obtain the Pareto solution set of the presented model according to the previous studies. We also apply three multi-objective meta-heuristic algorithms, namely MOSA, MOTS and MOAMP, on the simulated data in order to compare the proposed procedure performance. The computational results show that our proposed MOASA outperforms the three foregoing algorithms.

Keywords

Main Subjects


[1] Albareda-Sambola M., Diaz J., Fernandez E. (2005),A compact model and tight bounds for a
combined location-routing problem. Computers and Operations Research 32; 407–428.
[2] Barreto S., Ferreira C., Paixão J., Santos B. (2007),Using clustering analysis in a capacitated locationrouting
problem. European Journal of Operational Research, 179; 968-977.
[3] Belenguer J., Benavent E., Prins C., Prodhon C., Wolfler Calvo R. (2011), A Branch-and-Cut method
for the Capacitated Location-Routing Problem. Computers and Operations Research 38; 931-941.
[4] Bouhafs L., Hajjam A., Koukam A. (2006),A combination of simulated annealing and ant colony
system for the capacitated location-routing problem. Lecture Notes in Computer Science 4251; 409–
416.
[5] Caballero R., Gonzalez M., Flor M., Molina J., Paralera C. (2007), Solving a multiobjective location
routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia.
European Journal of Operational Research 177; 1751–1763.
[6] Deb, K. (2001),Multiobjective optimization using evolutionary algorithms. Wiley, Chichester, UK.
[7] Duhamel C., Lacomme P., Prins C., Prodhon C. (2010),A GRASP×ELS algorithm for the capacitated
location-routing problem. Computers and Operations Research, 37; 1912-1923.
[8] Gover F., Kochenberger G. (2003),Handbook of metahuristics. New York: Kluwer Academic
Publishers.
[9] Lin C., Kwok R. (2006), Multi-objective metaheuristics for a location-routing problem with multiple
use of vehicles on real data and simulated data. European Journal of Operational Research 175; 1833–
1849.
[10] Lin C., Chow C., Chen A. (2002), A location-routing-loading problem for bill delivery services.
Computers and Industrial Engineering 43; 5–25.
[11] Min H., Jayaraman V., Srivastava R. (1998), Combined location-routing problems: a synthesis and
future research directions. European Journal of Operational Research 108; 1–15.
[12] Nagy G., Salhi S. (2007), Location-routing: Issues, models and methods. European Journal of
Operational Research 177; 649–672.
[13] Perl J., Daskin M. (1984), A unified warehouse location-routing methodology. Journal of Business
Logistics 5; 92–111.
[14] Prins C., Prodhon C., Calvo R. W. (2006b),Solving the capacitated location-routing problem by a
GRASP complemented by a learning process and a path relinking.4OR 4; 221–238.
[15] Prins C., Prodhon C., Wolfler Calvo R. (2006a), A memetic algorithm with population management
(MA|PM) for the capacitated location-routing problem. Lecture Notes in Computer Science 3906; 183–
194.
[16] Prins C., Prodhon C., Ruiz A., Soriano P., Wolfler Calvo R. (2007),Solving the capacitated locationrouting
problem by a cooperative lagrangean relaxationgranular tabu search heuristic. Transportation
Science 41(4); 470–483.
[17] Prodhon C. (2011), A hybrid evolutionary algorithm for the periodic location-routing problem.
European Journal of Operational Research 210; 204-212.
[18] Schott J. (1995),Fault tolerant design using single and multicriteria genetic algorithms
optimization.Department of Aeronautics and Astronautics. Cambridge: Master’s thesis, Massachusetts
Institute of Technology.
[19] Tavakkoli-Moghaddam R., Makui A., Mazloomi Z. (2010), A new integrated mathematical model for
a bi-objective multi-depot location-routing problem solved by a multi-objective scatter search algorithm. Journal of Manufacturing Systems 29; 111–119.

[20] Tuzun D., Burke L. (1999), A two-phase tabu search algorithm to the location routing problem.

European Journal of Operational Research 116; 87–89.
[21] Ulungu E. L., Teghem J., Fortemps P. H., Tuyttens D. (1999), MOSA method: a tool for solving
multiobjective combinatorial optimization problems. Journal of Multicriteria Decision Analysis 8;
221-236.
[22] Van Veldhuizen D. (1999),Multiobjective evolutionary algorithms: Classification, analyses and new
innovations.Dayton, Ohio: Doctoral dissertation, Air Force Institute of Technology.
[23] Wu T., Low C., Bai J. (2002), Heuristic solutions to multi-depot location-routing problems. Computers
and Operations Research 29; 1393–1415.
[24] Yu V. F., Shih-Wei Lin, Wenyih Lee, Ching-Jung Ting. (2010), A simulated annealing heuristic for
the capacitated location routing problem. Computers & Industrial Engineering; 288–299.
[25] Zitzler E. (1999),Evolutionary algorithms for multiobjective optimization: Methods and
applications.Zurich: PhD thesis, Swiss Federal Institute of Technology Zurich.

[26] Zitzler E., Deb K., Thiele L. (2000), Comparison of multiobjective evolutionary algorithms: Empirical
results. Evolutionary Computation 8(2); 173-195.