Mathematical Model for Multi Depot Simultaneously Pick Up and Delivery Vehicle Routing Problem with Stochastic Pick Up Demand

Abstract

In a classical vehicle routing problem (VRP), customer demands are known with certainty. On the other hand, in real-life problems, customer demands may change over time. Therefore, in the classical VRP, the assumption that customer demands are stochastic should be taken into account. To expedite consumer demands and minimize fuel use and carbon emissions, organizations must concurrently address client distribution and collection requirements. Customers' distribution requirements can be predicted, but it is impossible to predict in advance the product requirements they will send for recycling. Hence, in this study, a mathematical programming model is developed for the multi-depot simultaneous pick-up and delivery vehicle routing problem under the assumption that customers' picking demands are stochastic. However, there are non-linear constraints in the developed model. Thereby, firstly, the stochastic model is linearized, and then the effectiveness of the model is analyzed. The efficacy of the linearized model is ascertained by generating test problems. The study investigated the impact of varying reliability levels and the number of depots on the model. As a result of the sensitivity analysis, it was determined that by decreasing the reliability level, the solution time of the problems decreased and the number of problems reaching the best solution increased. In the study, 135 test problems were solved by changing the reliability level, and the best result was achieved in 105 of these problems within 7200 s. The increase in the number of depots both reduced the solution time of the problems and was effective in reaching the best solution for all solved test problems.

Keywords

• Stochastic Demand
• Vehicle Routing Problem
• Mathematical Model
• Chance Constrained Programming
• Stochastic Programming

References

1. [1] Toth, P., and Vigo, D., (Eds.). Vehicle routing: problems, methods, and applications, Society for industrial and applied mathematics, (2014).
2. [2] Desticioglu, B., Calipinar, H., Ozyoruk, B., and Koc, E., “Model for Reverse Logistic Problem of Recycling under Stochastic Demand”, Sustainability, 14(8): 4640, (2022).
3. [3] Tasan, A.S., and Gen, M., “A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries”, Computers & Industrial Engineering, 62(3): 755-761, (2012).
4. [4] Yücenur, G.N., and Demirel, N.Ç., “A hybrid algorithm with genetic algorithm and ant colony optimization for solving multi-depot vehicle routing problems”, Sigma Journal of Engineering and Natural Sciences, 29: 340-350, (2011).
5. [5] Uslu, A., Cetinkaya, C., and İşleyen, S.K., “Vehicle routing problem in post-disaster humanitarian relief logistics: A case study in Ankara”, Sigma Journal of Engineering and Natural Sciences, 35(3): 481-499, (2017).
6. [6] Oyola, J., Arntzen, H., and Woodruff, D.L., “The Stochastic Vehicle Routing Problem a Literature Review, Part I: Models”, EURO Journal on Transportation Logistics, 7: 193-221, (2018).
7. [7] Desticioğlu, B., and Özyörük, B., “Stokastik Talepli Araç Rotalama Problemi İçin Literatür Taraması”, Savunma Bilimleri Dergisi, 36: 181-222, (2019).
8. [8] Charnes, A., and Cooper, W.W., “Chance Constraints and Normal Derivates”, Journal of the American Statistical Association, 57: 134-148, (1962).

9. [9] Charnes, A., and Cooper, W.W., “Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints”, Operations Research, 11(1): 18-39, (1963).
10. [10] Marković, D., Petrovć, G., Ćojbašić, Ž., and Stanković, A., “The vehicle routing problem with stochastic demands in an urban area–a case study”, Facta Universitatis, Series: Mechanical Engineering, 18(1): 107-120, (2020).
11. [11] Florio, A.M., Hartl, R.F., and Minner, S., “New exact algorithm for the vehicle routing problem with stochastic demands”, Transportation Science, 54(4): 1073-1090, (2020).
12. [12] Omori, R., and Shiina, T., “Solution algorithm for the vehicle routing problem with stochastic demands”, 11th International Conference on Soft Computing and Intelligent Systems and 21st International Symposium on Advanced Intelligent Systems, 1-6, IEEE, (2020).
13. [13] Gaur, D.R., Mudgal, A., and Singh, R.R., “Improved approximation algorithms for cumulative VRP with stochastic demands”, Discrete Applied Mathematics, 280: 133-143, (2020).
14. [14] Ma, J., Zhang, J., and Guo, Y., “The Stochastic and Dynamic Vehicle Routing Problem: A Literature Review”, 2021 Chinese Intelligent Automation Conference, Zhanjiang, 344-351, (2022).
15. [15] Niu, Y., Zhang, Y., Cao, Z., Gao, K., Xiao, J., Song, W., and Zhang, F., “MIMOA: A membrane-inspired multi-objective algorithm for green vehicle routing problem with stochastic demands”, Swarm and Evolutionary Computation, 60: 100767, (2021).
16. [16] Xia, X., Liao, W., Zhang, Y., and Peng, X., “A discrete spider monkey optimization for the vehicle routing problem with stochastic demands”, Applied Soft Computing, 111: 107676, (2021).
17. [17] Komatsu, M., Omori, R., Sato, T., and Shiina, T., “New Methods to Solve Vehicle Routing Problem Considering Stochastic Demand”, 10th International Congress on Advanced Applied Informatics (IIAI-AAI), Tokio, 861-866, (2021).
18. [18] Bernardo, M., Du, B., and Pannek, J., “A simulation-based solution approach for the robust capacitated vehicle routing problem with uncertain demands”, Transportation Letters, 13(9): 664-673, (2021).
19. [19] Zarouk, Y., Mahdavi, I., Rezaeian, J., and Santos-Arteaga, F.J., “A novel multi-objective green vehicle routing and scheduling model with stochastic demand, supply, and variable travel times” Computers & Operations Research, 141: 105698, (2022).
20. [20] Ledvina, K., Qin, H., Simchi-Levi, D., and Wei., Y., “A new approach for vehicle routing with stochastic demand: Combining route assignment with process flexibility”, Operations Research, 70(2-3): 2597-3033, (2022).
21. [21] Florio, A. M., Feillet, D., Poggi, M., and Vidal, T., “Vehicle routing with stochastic demands and partial reoptimization.”, Transportation Science, 56(5): 1393-1408, (2022).
22. [22] Niu, Y., Shao, J., Xiao, J., Song, W., and Cao, Z., “Multi-objective evolutionary algorithm based on RBF network for solving the stochastic vehicle routing problem”, Information Sciences, 609: 387-410, (2022).
23. [23] Singh, V.P., Sharma, K., and Chakraborty, D., “Fuzzy Stochastic Capacitated Vehicle Routing Problem and Its Applications”, Int. J. Fuzzy Syst., 24: 1478–1490, (2022).
24. [24] Hoogendoorn, Y. N., and Spliet, R., “An improved integer L-shaped method for the vehicle routing problem with stochastic demands”, INFORMS Journal on Computing, 35(2): 423-439, (2023).
25. [25] De La Vega, J., Gendreau, M., Morabito, R., Munari, P., and Ordóñez, F., “An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands”, European Journal of Operational Research, 308(2): 676-695, (2023).
26. [26] Che, Y., and Zhang, Z., “An Integer L-shaped algorithm for vehicle routing problem with simultaneous delivery and stochastic pickup”, Computers & Operations Research, 154: 106201, (2023).
27. [27] Zhang Z, Ji, B., and Yu, S.S., “An adaptive tabu search algorithm for solving the two-dimensional loading constrained vehicle routing problem with stochastic customers”, Sustainability, 15(2): 1741, (2023).
28. [28] Marinaki, M., Taxidou, A., and Marinakis, Y., “A hybrid dragonfly algorithm for the vehicle routing problem with stochastic demands”, Intelligent Systems with Applications, 18: 200225, (2023).
29. [29] Sluijk, N., Florio, A.M., Kinable, J., Dellaert, N., and Van Woensel, T., “A chance-constrained two-echelon vehicle routing problem with stochastic demands”, Transportation Science, 57(1): 252-272, (2023).
30. [30] Fukasawa, R., and Gunter, J., “The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands”, Operations Research Letters, 51(1): 11-16, (2023).
31. [31] Karaoglan, I., Altiparmak, F., Kara, I., and Dengiz, B., “The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach”, Omega, 40(4): 465-477, (2012).
32. [32] Ağpak, K., and Gökçen, H., “A Chance-Constrained Approach to Stochastic Line Balancing Problem”, European Journal of Operational Research, 180: 1098-1115, (2006).
33. [33] Ozcan, U., “Balancing Stochastic Two-Sided Assembly Lines: A Chance-Constrained, Piecewise-Linear, Mixed Integer Program and Simulated Annealing Algorithm”, European Journal of Operational Research, 205: 81-97, (2010).
34. [34] Olson, D.L., and Swenseth, S.R., “A linear approximation for chance-constrained programming”, The Journal of the Operational Research Society, 38(3): 261-267, (1987).
35. [35] Christofides, N., and Eilon, S., “An Algorithm for the Vehicle-dispatching Problem”, Journal of Operational Research Society, 20: 309-318, (1969). [dataset].
36. [36] Augerat, P., Belenguer, J.M., Benavent, E., Corberan, A., Naddef, D., and Rinaldi, G., “Computational Results with a Branch and Cut Code for the Capacited Vehicle Routing Problem”, Research Report RR949-M. Artemis-Image, France, 1-27, (1995). [dataset].
37. [37] Salhi, S., and Nagy, G., “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling”, Journal of the Operational Research Society, 50(10): 1034-1042, (1999).
38. [38] Baykoç, Ö.F., and İşleyen, S.K., “Stokastik Talepli Araç Rotalama Problemi İçin Şans Kısıtı Yaklaşımı”, Teknoloji, 10(1): 31-39, (2007).
39. [39] Foroughi, A., Gökçen, H., and Tiacci, L., “The Cost-Oriented Stochastic Assembly Line Balancing Problem: A Chance Constrained Programming Approach”, International Journal of Industrial Engineering, 23(6): 412-430, (2016).
40. [40] Huang, C.H., “An Effective Linear Approximation Method for Seperable Programming Problems”, Applied Mathematics and Computation, 215(4): 1496-1506, (2009).