A fuzzy two-stage capacitated continuous p-centmedian vehicle routing problem: A self-adaptive evolutionary

Document Type : Research Paper

Authors

1 M.Sc. Student, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 Professor, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

3 Ph.D. candidate, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

Abstract

In this paper, a two-stage continuous p-center and p-median (namely p-centmedian) problem is developed. In the first step, a location problem is studied to compare the differences between the p-center and p-median by considering facility disruption. P-center problems are common in emergency situations with aim of minimizing the maximum distance between the facilities and costumers, while p-median problem aim is to minimize the total spent distance. Moreover, an integer linear programming is developed to deal with a time-window multi-depot capacitated vehicle routing problem in order to optimize the flows between facilities. This paper compares the mentioned p-center and p-median effects along with the vehicle routing problem as a two-step integrate problem. Since both steps are NP-hard, to deal with the problem in both stages a possibilistic programming, fuzzy single-objective programming is developed and solved by an efficient algorithm, namely self-adaptive differential evolution algorithm. Considering demand as a fuzzy parameter is an important factor and makes the problem more realistic, this feature is more considerable in emergency situations such as p-center problems. To improve the performance of results, the Taguchi method is used. In order to validate the results of the mentioned algorithms of small-sized test problems are compared with GAMS, also other valid meta-heuristics are developed to be compared with the proposed algorithm in large-sized problems. The results show the capability of algorithm to generate near-optimal solutions. Also, the results demonstrate the p-median problem is more volatile against variation in the parameters while the p-center problem is more expensive.

Keywords


- Alp, O.,  Erkut, E. and Drezner, Z. (2003) “An efficient genetic algorithm for the p-median problem”, Annals of Operations Research, Vol. 122, No. 1, pp. 21-42.
- Alinezhad, H., Yaghoubi, Ù. S., Hoseini Motlagh, S. M. and Allahyari, S. (2018) “An improved particle swarm optimization for a class of capacitated vehicle routing problems”, International Journal of Transportation Engineering, Vol. 5, No. 4, pp. 331-347
- Azadeh, A., Habibnejad-Ledari, H., Abdolhossein Zadeh, S. and Hosseinabadi Farahani, M. (2017) “A single-machine scheduling problem with learning effect, deterioration and non-monotonic time-dependent processing times”, International Journal of Computer Integrated Manufacturing, Vol. 30, Nos. 2-3, pp. 292-304.
- Basappa, M., Jallu, R. K. and Das, G. K. (2015) “Constrained k-center problem on a convex polygon”, Proceedings of the 15th International Conference on Computational Science and its Applications (ICCSA 2015), Banff, Canada, 22-25 June 2015, pp. 209-222.
- Blanco, V., Puerto, J. and  Ben-Ali, S. E. (2016) “Continuous multifacility ordered median location problems”, European Journal of Operational Research,Vol. 250, No. 1, pp. 56-64.
- Callaghan, B., Salhi, S., and Nagy, G. (2017) “Speeding up the optimal method of Drezner for the p-centre problem in the plane”, European Journal of Operational Research,Vol. 257, No. 3, pp. 722-734.
- Colmenar, J. M., Greistorfer, P.,  Martí, R. and Duarte, A. (2016) “Advanced greedy randomized adaptive search procedure for the obnoxious p-median problem”, European Journal of Operational Research,Vol. 252, No. 2, pp. 432-442.
- Dantrakul, S.,  Likasiri, C. and Pongvuthithum, R.  (2014) “Applied p-median and p-center algorithms for facility location problems”, Expert Systems with Applications, Vol. 41, No. 8, pp. 3596-3604.
- Dantzig, G. B. and Ramser.,  H. (1959) “The truck dispatching problem”, Management Science, Vol. 6, No. 1, pp. 80-91.
- 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.
- Ghannadpour, S. F. and Zarrabi, A. (2017) The special application of vehicle routing problem with uncertainty travel times: locomotive routing problem”, International Journal of Transportation Engineereing, Vol. 5, No. 2, pp. 119-136
- Hakimi, S. L. (1964) “Optimum locations of switching centers and the absolute centers and medians of a graph”, Operations Research, Vol. 12, No. 3, pp. 450-459.
- Irawan, C. A. and Salhi, S. (2015) “Solving large p-median problems by a multistage hybrid approach using demand points aggregation and variable neighbourhood search”, Journal of Global Optimization, Vol. 63, No. 3, pp. 537-554.
- Issabakhsh, M., Hosseini-Motlagh, S. M., Pishvaee, M.S. and Saghafi Nia, M. (2018) “A vehicle routing problem for modeling home healthcare: A case study. International Journal of Transportation Engineering, Vol. 5, No. 3, pp. 211-228.
- Kazakovtsev, L.A., Orlov, V., Stupina, A.A. and Kazakovtsev, V., (2015) “Modied genetic algorithm with greedy heuristic for continuous and discrete p-median problems”, Facta Universitatis, Series: Mathematics and Informatics, Vol. 30, No. 1, pp. 89-106.
- Koç, Ç., Bektaş, T., Jabali, O. and Laporte, G. (2016) “The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm”, European Journal of Operational Research, Vol. 248, No. 1, pp. 33-51.
- Lightner-Laws, C., Agrawal, V., Lightner, C. and Wagner, N. (2016) “An evolutionary algorithm approach for the constrained multi-depot vehicle routing problem”, International Journal of Intelligent Computing and Cybernetics, Vol. 9, No. 1, pp. 2-22.
- Mahmudy, W.F. (2014) “Improved simulated annealing for optimization of vehicle routing problem with time windows (VRPTW)”, KURSOR Journal Vol. 7, No. 3, pp. 109-116.
- Maleki, K. and Abbasi, M. (2015) “A hybrid iterated local search-firefly algorithm for solving discrete p-center problem”, Cumhuriyet Science Journal, Vol. 36, No. 4, pp. 202-210.
- Marinakis, Y. (2015) “An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands”, Applied Soft Computing, Vol. 37, pp. 680-701.
- Mehrjerdi, Y. Z. 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.
- Montoya-Torres, J. R. Franco, J. L., Isaza, S.N., Jiménez, H. F. and Herazo-Padilla, N. (2015) “A literature review on the vehicle routing problem with multiple depots“, Computers and Industrial Engineering,Vol. 79, pp. 115-129.
- Mousazadeh, M., Torabi, S. A. and Pishvaee, M. S. (2014) “Green and reverse logistics management under fuzziness”, In: C. Kahraman and B. Öztaysi (eds.), Supply Chain Management Under Fuzziness, Studies in Fuzziness and Soft Computing, Vol. 313, Springer-Verlag, Berlin, pp. 607-637.
- Nadizadeh, A. and Hosseini Nasab, H. (2019) “Modelling and solving the capacitated location-routing problem with simultaneous pickup and delivery demands”, International Journal of Transportation Engineering, Vol. 6, No. 3, pp. 217-235.
- Neema, N., Maniruzzaman, M. and Ohgai, A. (2011) “New genetic algorithms based approaches to continuous p-median problem”, Networks and Spatial Economics, Vol. 11, No. 1, pp. 83-99.
- Nematian, J. and Sadati, M. (2015) “New methods for solving a vertex p-center problem with uncertain demand-weighted distance: A real case study”, International Journal of Industrial Engineering Computations, Vol. 6, No. 2, pp. 253-266.
- Nikkhah Qamsari, A., Hosseini Motlagh, S. M. and Jokar, A. (2017) “A two-phase hybrid heuristic method for a multi-depot inventory-routing problem”, International Journal of Transportation Engineering, Vol. 4, No. 4, 287-304.
- Rabbani, M., Bosjin, S., Yazdanparast, R. and Saravi, N. (2018) “A stochastic time-dependent green capacitated vehicle routing and scheduling problem with time window, resiliency and reliability: a case study”, Decision Science Letters, Vol. 7, No. 4, pp. 381-394
- Rabbani, M. and Yousefnejad, H. (2013) “A novel approach for solving a capacitated location allocation problem”, International Journal of Industrial Engineering Computations, Vol. 4, No. 2, pp. 203-214.
- Stanimirovic, P. S. and Ciric, M. (2011) “Single-facility Weber location problem based on the lift metric”, Technical Report, arXiv preprint arXiv:1105.0757.
- Storn, R. and Price, K. (1997) “Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces”, Journal of Global Optimization, Vol. 11, No. 4, pp. 341-359.
- Szeto, W.Y., Wu, Y. and Ho, S. C. (2011) “An artificial bee colony algorithm for the capacitated vehicle routing problem”, European Journal of Operational Research, Vol. 215, No. 1, pp. 126-135.
- 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.
- Xu, J. and Zhou, X. (2013) “Approximation based fuzzy multi-objective models with expected objectives and chance constraints: Application to earth-rock work allocation”, Information Sciences, Vol. 238, No., pp. 75-95.
- Yalcın, G. D. and Erginel, N. (2015) “Fuzzy multi-objective programming algorithm for vehicle routing problems with backhauls", Expert Systems with Applications, Vol. 42, No. 13, pp. 5632-5644.
- Zhalechian, M., Tavakkoli-Moghaddam, R. and Rahimi, Y. (2017) “A self-adaptive evolutionary algorithm for a fuzzy multi-objective hub location problem: An integration of responsiveness and social responsibility”, Engineering Applications of Artificial Intelligence, Vol. 62, No., pp. 1-16.
- Zhou, Y., Luo, Q., Xie, J. and Zheng, H. (2016) “A hybrid bat algorithm with path relinking for the capacitated vehicle routing problem”, In: A. Abraham, A. Haqiq, A.M. Alimi, G. Mezzour, N. Rokbani, A.K. Muda, Proceedings of the 16th International Conference on Hybrid Intelligent Systems (HIS 2016), Marrakech, Morocco, 21–23 Nov. 2016, Vol. 552 of Advances in Intelligent Systems and Computing, Springer.