An Augmented Variable Neighborhood Search to Solve the Capacitated Location-Routing Problem

##plugins.themes.bootstrap3.article.main##

  •   Alireza Mohamadi-Shad

  •   Hamed Niakan

  •   Hasan Manzour

Abstract

In this paper we proposed a new variable neighborhood search (VNS) for solving the location- routing problem with considering capacitated depots and vehicles. A set of capacitated vehicles, a set of depots with restricted capacities, and associated opening costs, and a set of customers with deterministic demands are given. The problem aims to determine the depots to be opened, fleet assignment to each depot, and the routes to be performed to satisfy the demand of the customers. The objective is to minimize the total costs of the open depots, the setup cost associated with the used vehicles, and transportation cost. We proposed a new VNS which is augmented with a probabilistic acceptance criterion as well as a set of efficient local searches. The computational results implemented on four well-known data sets demonstrate that the proposed algorithm is competitive with other well- known algorithms while reaching many best-known solutions and updating six best new results with reasonable computational time. Conclusions and future research avenues close the paper.


Keywords: Capacitated location routing, variable neighborhood search, heuristic, local search, simulated annealing, dynamic penalty function

References

Afrooz Ansaripour and Theodore B Trafalis. A robust multicriteria optimization model for city logistic terminal locations. In IIE Annual Conference. Proceedings, page 2801. Institute of Industrial and Systems Engineers (IISE), 2013.

Afrooz Ansaripour, Adriana Mata, Sara Nourazari, Hillel Kumin, et al. Some explicit results for the distribution problem of stochastic linear programming. Open Journal of Optimization, 5(04):140, 2016.

Sergio Barreto, Carlos Ferreira, Jose Paixao, and Beatriz Sousa Santos. Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 179(3): 968–977, 2007.

Christophe Duhamel, Philippe Lacomme, Christian Prins, and Caroline Prodhon. A grasp els approach for the capacitated location-routing problem. Computers & Operations Research, 37(11): 1912–1923, 2010.

John Willmer Escobar, Rodrigo Linfati, and Paolo Toth. A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Computers & Operations Research, 40(1):70–79, 2013.

Seyed Sajjad Fazeli, Saravanan Venkatachalam, Ratna Babu Chinnam, and Alper Murat. Two-stage stochastic choice modeling approach for electric vehicle charging station network design in urban communities. IEEE Transactions on Intelligent Transportation Systems, 2020.

Seyed Sajjad Fazeli, Saravanan Venkatachalam, and Jonathon M Smereka. Efficient algorithms for autonomous electric vehicles’ min-max routing problem. arXiv preprint arXiv:2008.03333, 2020.

Pierre H Hansen, B Hegedahl, S Hjortkjaer, and Børge Obel. A heuristic solution to the warehouse location-routing problem. European Journal of Operational Research, 76(1):111–127, 1994.

Bassem Jarboui, Houda Derbel, Saïd Hanafi, and Nenad Mladenovic´. Variable neighborhood search for location routing. Computers & Operations Research, 40(1):47–57, 2013.

Rui Borges Lopes, Carlos Ferreira, Beatriz Sousa Santos, and Sérgio Barreto. A taxonomical analysis, current methods and objectives on location-routing problems. International Transactions in Operational Research, 20(6):795–822, 2013.

Yannis Marinakis and Magdalene Marinaki. A particle swarm optimization algorithm with path relinking for the location routing problem. Journal of Mathematical Modelling and Algorithms, 7 (1):59–78, 2008.

Yannis Marinakis, Magdalene Marinaki, and Nikolaos Matsatsinis. Honey bees mating optimization for the location routing problem. In Engineering Management Conference, 2008. IEMC Europe 2008. IEEE International, pages 1–5. IEEE, 2008.

Nenad Mladenovic´ and Pierre Hansen. Variable neighborhood search. Computers & Operations Research, 24(11):1097–1100, 1997.

Gábor Nagy and Saïd Salhi. Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2):649–672, 2007.

Jossef Perl and Mark S Daskin. A warehouse location-routing problem. Transportation Research Part B: Methodological, 19(5):381–396, 1985.

Jossef Perl and Mark S Daskin. A warehouse location-routing problem. Transportation Research Part B: Methodological, 19(5):381–396, 1985.

Christian Prins, Caroline Prodhon, and Roberto Wolfler Calvo. A memetic algorithm with population management (ma| pm) for the capacitated location-routing problem. In Evolutionary computation in combinatorial optimization, pages 183–194. Springer, 2006.

Christian Prins, Caroline Prodhon, and Roberto Wolfler Calvo. Solving the capacitated location- routing problem by a grasp complemented by a learning process and a path relinking. 4OR, 4(3): 221–238, 2006.

Christian Prins, Caroline Prodhon, Angel Ruiz, Patrick Soriano, and Roberto Wolfler Calvo. Solv- ing the capacitated location-routing problem by a cooperative lagrangean relaxation-granular tabu search heuristic. Transportation Science, 41(4):470–483, 2007.

Caroline Prodhon and Christian Prins. A survey of recent research on location-routing problems. European Journal of Operational Research, 2014.

Ching-Jung Ting and Chia-Ho Chen. A multiple ant colony optimization algorithm for the capacitated location routing problem. International Journal of Production Economics, 141(1):34–44, 2013.

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

Tai-Hsi Wu, Chinyao Low, and Jiunn-Wei Bai. Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10):1393–1415, 2002.

Vincent F Yu, Shih-Wei Lin, Wenyih Lee, and Ching-Jung Ting. A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2):288–299, 2010.

Downloads

Download data is not yet available.

##plugins.themes.bootstrap3.article.details##

How to Cite
[1]
Mohamadi-Shad, A., Niakan, H. and Manzour, H. 2021. An Augmented Variable Neighborhood Search to Solve the Capacitated Location-Routing Problem. European Journal of Engineering and Technology Research. 6, 4 (Jun. 2021), 67-76. DOI:https://doi.org/10.24018/ejers.2021.6.4.2380.