ON DIFFERENT FORMULATIONS FOR THE MULTI-PERIOD VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICKUP AND DELIVERY
DOI:
https://doi.org/10.11113/aej.v13.17888Keywords:
Integer programming, Mathematical formulation, Periodic routing, Simultaneous pickup and delivery, Vehicle routing problemAbstract
In this paper, we extend the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) with a consideration of multiple planning horizons. We propose three alternative mathematical formulations for Periodic-VRPSPD (P-VRPSPD) based on the available formulations for VRPSPD in the literatures, namely the three-index commodity flow formulation, four-index commodity flow formulation, and three-index vehicle flow formulation. We perform comparison analysis by conducting extensive numerical experiments on a set of instances with various complexities in order to evaluate the performance of these formulations. Overall, it is observed that the three-index commodity flow formulation returns the best results.
References
Dantzig, G. B. and Ramser, J. H. 1959. The truck dispatching problem. Management Science, 6: 80–91, 1959. DOI: https://doi.org/10.1287/mnsc.6.1.80
Eksioglu, B., Vural, A. V. and Reisman, A. 2009. The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57: 1472-1483. DOI: https://doi.org/10.1016/j.cie.2009.05.009
Braekers, K., Ramaekers, K., and Van Nieuwenhuyse, I. 2016. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99: 300–313. DOI: https://doi.org/10.1016/j.cie.2015.12.007.
Vidal, T., Laporte, G. and Matl, P. 2020. A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research, 286: 401-416. DOI: https://doi.org/10.1016/j.ejor.2019.10.010.
Berbeglia, G., Cordeau, J. F., Gribkovskaia, I. and Laporte, G. 2007. Static pickup and delivery problems: a classification scheme and survey. TOP, 15: 1-31. DOI: https://doi.org/10.1007/s11750-007-0009-0.
Battarra, M., Cordeau, J. F. and Iori, M. 2015. Pickup-and-delivery problems for goods transportation in: P. Toth, D. Vigo (Eds.). Vehicle Routing: Problems, Methods, and Applications. MOS-SIAM Series on Optimization. Chapter 6: 161–191.
Çatay, B. 2010. A new saving-based ant algorithm for the Vehicle Routing Problem with simultaneous Pickup and Delivery. Expert Systems With Applications, 37: 6809-6817. DOI: https://doi.org/10.1016/j.eswa.2010.03.045.
Drexl, M., Rieck, J., Sigl, T. and Press, B. 2013. Simultaneous Vehicle and Crew Routing and Scheduling for Partial- and Full-Load Long-Distance Road Transport. Business Research, 6: 242-264. DOI: https://doi.org/10.1007/BF03342751.
Belgin, O., Karaoglan, I. and Altiparmak, F. 2018. Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering, 115: 1-16. DOI: https://doi.org/10.1016/j.cie.2017.10.032.
Zhang, Z., Cheang, B., Li, C. and Lim, A. 2019. Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer. Computers & Operations Research, 103: 81-96. DOI: https://doi.org/10.1016/j.cor.2018.10.020.
Hemmelmayr, V., Doerner, K. F., Hartl, R. F. and Rath, S. A heuristic solution method for node routing based solid waste collection problems. Journal of Heuristics, 19: 129-156. DOI: https://doi.org/10.1007/s10732-011-9188-9.
Coene, S., Arnout, A. and Spieksma, F. C. R. 2010. On a periodic vehicle routing problem. Journal of the Operational Research Society, 61: 1719–1728. DOI: https://doi.org/10.1057/jors.2009.154.
An, Y. J., Kim, Y. D., Jeong, B. J. and Kim, S. D. 2012. Scheduling healthcare services in a home healthcare system. Journal of the Operational Research Society, 63: 1589-1599. DOI: https://doi.org/10.1057/jors.2011.153.
Koç, Ç., Laporte, G. and Tükenmez, İ. 2020. A review of vehicle routing with simultaneous pickup and delivery. Computers & Operations Research, 122: 104987. DOI: https://doi.org/10.1016/j.cor.2020.104987.
Dell’Amico, M., Righini, G. and Salani, M. 2006. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Science, 40: 235–247. DOI: https://doi.org/10.1287/trsc.1050.0118.
Montané, F. A. T. and Galvão, R. D. 2006. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33: 595–619. DOI: https://doi.org/10.1016/j.cor.2004.07.009.
Rieck, J. and Zimmermann, J. 2013. Exact Solutions to the Symmetric and Asymmetric Vehicle Routing Problem with Simultaneous Delivery and Pick-Up. Business Research, 6: 77–92. DOI: https://doi.org/10.1007/BF03342743.
Campbell, A. M. and Wilson, J. H. 2012. Forty Years of Periodic Vehicle Routing. Networks, 60: 45–58. DOI: https://doi.org/10.1002/net.21527.
Hadjiconstantinou, E. and Baldacci, R. 1998. A multi-depot period vehicle routing problem arising in the utilities sector. Journal of the Operational Research Society, 49: 1239–1248. DOI: https://doi.org/10.1057/palgrave.jors.2600641.
Blakeley, F., Bozkaya, B., Cao, B., Hall, W. and Knolmajer, J. 2003. Optimizing periodic maintenance operations for schindler elevator corporation. Interfaces, 33: 67–79. DOI: https://doi.org/10.1287/inte.33.1.67.12722.
Nuortio, T., Kytöjoki, J., Niska, H. and Bräysy, O. 2006. Improved route planning and scheduling of waste collection and transport. Expert Systems With Applications, 30: 223–232. DOI: https://doi.org/10.1016/j.eswa.2005.07.009.
Angelelli, E. and Speranza, M. G. 2002. The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research, 137: 233–247. DOI: https://doi.org/10.1016/S0377-2217(01)00206-5.
Bommisetty, D., Dessouky, M. and Jacobs, L. 1998. Scheduling collection of recyclable material at northern Illinois university campus using a two-phase algorithm. Computers & Industrial Engineering, 35: 435-438. DOI: https://doi.org/10.1016/s0360-8352(98)00127-2.
Baptista, S., Oliveira, R. C. and Zúquete, E. 2002. A period vehicle routing case study. European Journal of Operational Research, 139: 220-229. DOI: https://doi.org/10.1016/S0377-2217(01)00363-0.
Aksen, D., Kaya, O., Salman, F. S. and Akça, Y. 2012. Selective and periodic inventory routing problem for waste vegetable oil collection. Optimization Letters, 6: 1063–1080. DOI: https://doi.org/10.1007/s11590-012-0444-1.
Shih, L. H. and Chang, H. C. 2001. A routing and scheduling system for infectious waste collection. Environmental Modeling & Assessment, 6: 261–269. DOI: https://doi.org/10.1023/A:1013342102025.
Shih, L. H. and Lin, Y. T. 2019. Optimal routing for infectious waste collection. Journal of Environmental Engineering, 125: 479–484. DOI: https://doi.org/10.1061/(ASCE)0733-9372(1999)125:5(479).
Claassen, G. D. H. and Hendriks, T. H. B. 2007. An application of Special Ordered Sets to a periodic milk collection problem. European Journal of Operational Research, 180: 754–769. DOI: https://doi.org/10.1016/j.ejor.2006.03.042.
Alegre, J., Laguna, M. and Pacheco, J. 2007. Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts. European Journal of Operational Research, 179: 736–746. DOI: https://doi.org/10.1016/j.ejor.2005.03.063.
Rademeyer, A. L. and Benetto, R. 2012. A rich multi-period delivery vehicle master routing problem case study. in: Computers and Industrial Engineering 42 Proceedings, Cape Town, South Africa.
Ronen, D. and Goodhart, C. A. 2008. Tactical store delivery planning. Journal of the Operational Research Society, 59: 1047–1054. DOI: https://doi.org/10.1057/palgrave.jors.2602449.
Banerjea-Brodeur, M., Cordeau, J. F. Laporte, G. and Lasry, A. 1998. Scheduling linen deliveries in a large hospital. Journal of the Operational Research Society, 49: 777–780. DOI: https://doi.org/10.1057/palgrave.jors.2600581.
Rusdiansyah, A. and Tsao, D. B. 2005. An integrated model of the periodic delivery problems for vending-machine supply chains. Journal of Food Engineering, 70: 421–434. DOI: https://doi.org/10.1016/j.jfoodeng.2004.05.073.
Angelelli, E. and Mansini, R. 2002. The vehicle routing problem with time windows and simultaneous pick-up and delivery. in: Klose, A. Speranza, M.G. and Van Wassenhove, L. N. Quantitative Approaches to Distribution Logistics and Supply Chain Management, Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, Berlin: 249–267.
Fan, J. 2011. The vehicle routing problem with simultaneous pickup and delivery based on customer satisfaction. in: Procedia Engineering, 15: 5284-5289. DOI: https://doi.org/10.1016/j.proeng.2011.08.979.
Wang, H. F. and Chen, Y. Y. 2013. A coevolutionary algorithm for the flexible delivery and pickup problem with time windows. International Journal of Production Economics, 141: 4–13. DOI: https://doi.org/10.1016/j.ijpe.2012.04.011.
Wang, Y., Ma, X., Lao, Y., Wang, Y. and Mao, H. 2013. Vehicle Routing Problem Simultaneous Deliveries and Pickups with Split Loads and Time Windows. Transportation Research Record, 2378: 120-128.
Wang, C., Mu, D., Zhao, F. and Sutherland, J. W. 2015. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows. Computers & Industrial Engineering, 83: 111–122.DOI: https://doi.org/10.1016/j.cie.2015.02.005.
Qu, Y. and Bard, J. F. 2013. The heterogeneous pickup and delivery problem with configurable vehicle capacity. Transportation Research Part C: Emerging Technologies, 32: 1–20.DOI: https://doi.org/10.1016/j.trc.2013.03.007.
Avci, M. and Topaloglu, S. 2016. A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery. Expert Systems With Applications, 53: 160–171.DOI: https://doi.org/10.1016/j.eswa.2016.01.038.
Nagy, G. and Salhi, S. 2005. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162: 126-141. DOI: https://doi.org/10.1016/j.ejor.2002.11.003.
Li, J., Pardalos, P. M., Sun, H., Pei, J. and Zhang, Y. 2015. Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups. Expert Systems With Applications, 42: 3551–3561. DOI: https://doi.org/10.1016/j.eswa.2014.12.004.
Wang, C. and Qiu, Y. 2011. Vehicle routing problem with stochastic demands and simultaneous delivery and pickup based on the cross-entropy method. in: Lecture Notes in Electrical Engineering. DOI: https://doi.org/10.1007/978-3-642-25646-2_7.
Zhang, T., Chaovalitwongse, W. A. and Zhang, Y. 2012. Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries. Computers & Operations Research, 39: 2277–2290. DOI: https://doi.org/10.1016/j.cor.2011.11.021.
Yin, C., Bu, L. and Gong, H. 2013. Mathematical model and algorithm of split load vehicle routing problem with simultaneous delivery and pickup. International Journal of Innovative Computing, Information and Control, 9: 4497–4508.
Wang, J., Zhou, Y., Wang, Y. Zhang, J., Chen, C. L. P. and Zheng, Z. 2016. Multiobjective Vehicle Routing Problems with Simultaneous Delivery and Pickup and Time Windows: Formulation, Instances, and Algorithms. IEEE Transactions on Cybernetics, 46: 582–594. DOI: https://doi.org/10.1109/TCYB.2015.2409837.
Subramanian, A., Uchoa, E., Pessoa, A. A. and Ochi, L. S. 2011. Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Operations Research Letters, 39: 338–341. DOI: https://doi.org/10.1016/j.orl.2011.06.012.
Subramanian, A., Uchoa, E., Pessoa, A. A. and Ochi, L. S. 2013. Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery. Optimization Letters, 7: 1569–1581. DOI: https://doi.org/10.1007/s11590-012-0570-9.
Baldacci, R., Hadjiconstantinou, E. and Mingozzi, A. 2004. An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation., Operations research, 52(5): 723-738. DOI: https://doi.org/10.1287/opre.1040.0111
Laporte, G., Nobert, Y. and Desrochers, M. 1985. Optimal routing under capacity and distance restrictions., Operations research, 33(5): 1050-1073. DOI: https://doi.org/10.1287/opre.33.5.1050
Dantzig, G., Fulkerson, R. and Johnson, S. 1954. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4): 393-410DOI: https://doi.org/10.1287/opre.2.4.393
Miller, C. E., Tucker, A. W. and Zemlin, R. A. 1960. Integer programming formulation of traveling salesman problems., Journal of the ACM (JACM), 7(4): 326-329. DOI: https://doi.org/10.1145/321043.321046
Solomon, M. M. and Desrosiers, J. 1988. Survey paper—time window constrained routing and scheduling problems., Transportation science, 22(1): 1-13. DOI: https://doi.org/10.1287/trsc.22.1.1
Dethloff, J. 2001. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum, 23: 79–96. DOI: https://doi.org/10.1007/PL00013346.
Salhi, S. and Nagy, G. 1999. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the Operational Research Society, 50: 1034-1042. DOI: https://doi.org/10.1057/palgrave.jors.2600808.
de Freitas, J. C. and Penna, P. H. V. 2020. A variable neighborhood search for flying sidekick traveling salesman problem. International Transactions in Operational Research, 27: 267–290. DOI: https://doi.org/10.1111/itor.12671.
Murray, C. C. and Chu, A. G. 2015. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54: 86–109. DOI: https://doi.org/10.1016/j.trc.2015.03.005.
Furtado, M. G. S., Munari, P. and Morabito, R. 2017. Pickup and delivery problem with time windows: a new compact two-index formulation. Operations Research Letters, 45(4): 334-341. DOI: https://doi.org/10.1016/j.orl.2017.04.013
Camm, J. D., Raturi, A. S. and Tsubakitani, S. 1990. Cutting big M down to size. Interfaces, 20(5): 61-66. DOI: https://doi.org/10.1287/inte.20.5.61
Belotti, P., Bonami, P., Fischetti, M., Lodi, A., Monaci, M., Nogales-Gómez, A. and Salvagnin, D. 2016. On handling indicator constraints in mixed integer programming. Computational Optimization and Applications, 65(3): 545-566. DOI: https://doi.org/10.1007/s10589-016-9847-8
