Modelling and Solving the Capacitated Location-Routing Problem with Simultaneous Pickup and Delivery Demands

Document Type : Research Paper

Authors

1 Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, Ardakan University, Ardakan, Iran

2 Professor, Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran

Abstract

In this work, the capacitated location-routing problem with simultaneous pickup and delivery (CLRP-SPD) is considered. This problem is a more realistic case of the capacitated location-routing problem (CLRP) and belongs to the reverse logistics of the supply chain. The problem has many real-life applications of which some have been addressed in the literature such as management of liquid petroleum gas tanks, laundry service of hotels and drink distribution. The CLRP-SPD is composed of two well-known problems; facility location problem and vehicle routing problem. In CLRP-SPD, a set of customers with given delivery and pickup demands should be supplied by a fleet of vehicles that start and end their tours at a single depot. Moreover, the depots and vehicles have a predefined capacity and the objective function is minimizing the route distances, fixed costs of establishing the depot(s) and employing the vehicles. The node-based MIP formulation of the CLRP-SPD is proposed based on the literature of the problem. To solve the model, a greedy clustering method (GCM) is developed which includes four phases; clustering the customers, establishing the proper depot(s), assigning the clusters to depot(s) and constructing the vehicle tours by ant colony system (ACS). The numerical experiments on two sets of test problems with different sizes on the number of customers and candidate depots show the efficiency of the heuristic method with the proposed method in the literature. Finally, performance of the heuristic method to the similar methods in the literature is evaluated by several standard test problems of the CLRP.

Keywords


-Angelelli, E. and Mansini, R. (2002) "The vehicle routing problem with time windows and simultaneous pick-up and delivery. In: Lecture Notes in Economics and Mathematical Systems", Springer, Germany, pp. 249–267.
-Barreto, S. (2003) "http://sweet.us.pt/_iscf143".
-Barreto, S., Ferreira, C., Paixao, J. and Sousa Santos, B. (2007) "Using clustering analysis in a capacitated location-routing problem", European Journal of Operational Research, Vol. 179, pp. 968-977.
-Belenguer, J. M., Benavent, E., Prins, C., Prodhon, C. and Wolfler-Calvo, R. (2011) "A Branch-and-cut method for the Capacitated Location-Routing Problem", Computers and Operations Research, Vol. 38 pp. 931-941.
-Bouhafs, L., Hajjam, A. and Koukam, A. (2010) "A hybrid heuristic approach to solve the capacitated vehicle routing problem", Journal of Artificial Intelligence: Theory and Application, Vol. 1, No. 1, pp. 31-34.
-Catay, B. (2010) "A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery", Expert Systems with Applications, Vol. 37, pp. 6809–6817.
-Derbel, H., Jarboui, B., Hanafi, S. and Chabchoub, H. (2012) "Genetic algorithm with iterated local search for solving a location-routing problem", Expert Systems with Applications, Vol. 39, pp. 2865-2871.
-Dorigo, M. and Gambardella, L. M. (1996) "A study of some properties of ant-Q", PPSN, springer-Verlag, Berlin, pp. 656-665.
-Drexl, M. and Schneider, M. (2015) "A survey of variants and extensions of the location-routing problem", European Journal of Operational Research, Vol. 241, No. 2, pp. 283-308.
-Duhamel, C., Lacomme, P., Prins, C. and Prodhon C. (2010) "A GRASP×ELS approach for the capacitated location-routing problem", Computers & Operations Research, Vol. 37, pp. 1912-1923.
-Escobar, J. (2014) "Heuristic algorithms for the capacitated location-routing problem and the multi-depot vehicle routing problem", 4OR, Vol. 12, No. 1, pp. 99-100.
-Ghatreh Samani, M. and Hosseini-Motlagh, S.-M. (2017) "A hybrid algorithm for a two-echelon location- routing problem with simultaneous pickup and delivery under fuzzy demand", International Journal of Transportation Engineering, Vol. 5, No. 1, pp. 59-85.
-Huang, S.-H. (2015) "Solving the multi-compartment capacitated location routing problem with pickup–delivery routes and stochastic demands", Computers & Industrial Engineering, Vol. 87, pp. 104-113.
-Karaoglan, I., Altiparmak, F., Kara, I. and Dengiz, B. (2011) "A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery", European Journal of Operational Research, Vol. 211, pp. 318-332.
-Karaoglan, I., Altiparmak, F., Kara, I. and Dengiz, B. (2012) "The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach", Omega, Vol. 40, No. 4, pp. 465-477.
-Laporte, G. (1988) "Location-routing problems. Vehicle Routing: Methods and Studies", B. L. In: Golden, Assad, A.A. (Eds.). North-Holland, Amsterdam, pp. 163–198.
-Lopes, R. B., Ferreira, C. and Santos, B. S. (2016) "A simple and effective evolutionary algorithm for the capacitated location–routing problem", Computers & Operations Research, Vol. 70, pp. 155-162.
-Manzour-al-Ajdad, S. M. H., Torabi, S. A. and Salhi, S. (2012) "A hierarchical algorithm for the planar single-facility location routing problem", Computers & Operations Research, Vol. 39, pp. 461-470.
-Marinakis, Y. and Marinaki, M. (2008) "A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem", Journal of Mathematical Modelling and Algorithm, Vol. 7, pp. 59–78.
-Min, H., Jayaraman, V. and Srivastava, R. (1998) "Combined location-routing problems: A synthesis and future research directions", European Journal of Operational Research, Vol. 108, pp. 1–15.
-Nadizadeh, A. (2017) "The fuzzy multi-depot vehicle routing problem with simultaneous pickup and delivery: Formulation and a heuristic algorithm", International Journal of Industiral Engineering & Producion Research, Vol. 28, No. 3, pp. 325-345.
-Nadizadeh, A. and Kafash, B. (2017) "Fuzzy capacitated location-routing problem with simultaneous pickup and delivery demands", Transportation Letters, DOI: 10.1080/19427867.2016.1270798.
-Nadizadeh, A. and Hosseini Nasab, H. H. (2014) "Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm", European Journal of Operational Research, Vol. 238, No. 2, pp. 458-470.
-Nadizadeh‎‎, A., Sadegheih, A. and Sabzevari ‎Zadeh, A.‎ (2017) "A hybrid heuristic algorithm to solve capacitated location-routing problem with fuzzy ‎demands‎", International Journal of Industrial Mathematics, Vol. 9, No. 1, pp. 1-20.
-Nadizadeh, A., Sahraeian, R., Sabzevari Zadeh, A. and Homayouni, S. M. (2011) "Using greedy clustering method to solve capacitated location-routing problem", African Journal of Business Management, Vol. 5, No. 17, pp. 7499-7506.
-Nagy, G. and Salhi, S. (2007) "Location-routing: Issues, models and methods", European Journal of Operational Research, Vol. 177, pp. 649-672.
-Prins, C., Prodhon, C. and Wolfler Calvo, R. (2006) "Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking", Operational Research Quarterly, Vol. 4, pp. 221-238.
-Prodhon, C. (2008) "http://prodhonc.free.fe/homepage".
-Prodhon, C. and Prins, C. (2014) "A survey of recent research on location-routing problems", European Journal of Operational Research, Vol. 238, No. 1, pp. 1-17.
-Rahmani, Y., Cherif-Khettaf, W. R. and Oulamara, A. (2015) "A local search approach for the two–echelon multi-products location–routing problem with pickup and delivery", IFAC-Papers On Line, Vol. 48, No. 3, pp. 193-199.
-Rahmani, Y., Ramdane Cherif-Khettaf, W. and Oulamara, A. (2016) "The two-echelon multi-products location-routing problem with pickup and delivery: formulation and heuristic approaches", International Journal of Production Research, Vol. 54, No. 4, pp. 999-1019.
-Rath, S. and Gutjahr, W. J. (2014) "A math-heuristic for the warehouse location–routing problem in disaster relief", Computers & Operations Research, Vol. 42, pp. 25–39.
-Salhi, S. and Nagy, G. (1999) "Consistency and robustness in location routing", Studies in Locational Analysis, Vol. 13, pp. 3-19.
-Salhi, S. and Rand, G. K. (1989) "The effect of ignoring routes when locating depots", European Journal of Operational Research, Vol. 39, pp. 150–156.
-Tavakkoli-Moghaddam, R., Razie, Z. and Tabrizian, S. (2016) "Solving a Bi-Objective Multi-Product Vehicle Routing Problem with Heterogeneous Fleets under an Uncertainty Condition", International Journal of Transportation Engineering, Vol. 3, No. 3, pp. 207-225.
-Wang, X. and Li, X. (2017) "Carbon reduction in the location routing problem with heterogeneous fleet, simultaneous pickup-delivery and time windows", Procedia Computer Science, Vol. 112, pp. 1131-1140.
-Webb, M. H. J. (1968) "Cost functions in the location of depots for multiple delivery journeys", Operational Research Quarterly, Vol. 19, No. 3, pp. 311-320.
-Yang, J. and Sun, H. (2015) "Battery swap station location-routing problem with capacitated electric vehicles", Computers & Operations Research, Vol. 55, pp. 217-232.
-Yu, V. F. and Lin, S.-W. (2014) "Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery", Applied Soft Computing, Vol. 24, pp. 284-290.
-Yu, V. F. and Lin, S.-Y. (2016) "Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing", International Journal of Production Research, Vol. 54, No. 2, pp. 526-549.
-Zarandi, M., Hemmati, A., Davari S. and Turksen, I. (2013) "Capacitated location-routing problem with time windows under uncertainty", Knowledge-Based Systems, Vol. 37, pp. 480–489.
-Zarandi, M. H. F., Hemmati, A. and Davari, S. (2011) "The multi-depot capacitated location-routing problem with fuzzy travel times", Expert Systems with Applications, Vol. 38, No. 8, pp. 10075-10084.
-Zare Mehrjerdi, Y. and Nadizadeh, A. (2013) "Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands." European Journal of Operational Research, Vol. 229, No. 1, pp. 75-84.
-Zare Mehrjerdi, Y. and Nadizadeh, A. (2016) "Heuristic Method to Solve Capacitated Location-Routing Problem with Fuzzy Demands", International Journal of Industiral Engineering & Producion Research, Vol. 27, No. 1, pp. 1-19.
*Zhao, J. and Verter, V. (2014) "A bi-objective model for the used oil location-routing problem", Computers & Operations Research, Vol. 62, pp. 157-168.