• Setyo Tri Windras Mara Department of Mechanical and Industrial Engineering, Faculty of Engineering, Universitas Gadjah Mada, Indonesia
  • Achmad Pratama Rifai Department of Mechanical and Industrial Engineering, Faculty of Engineering, Universitas Gadjah Mada, Indonesia
  • Rachmadi Norcahyo Department of Mechanical and Industrial Engineering, Faculty of Engineering, Universitas Gadjah Mada, Indonesia




Integer programming, Mathematical formulation, Periodic routing, Simultaneous pickup and delivery, Vehicle routing problem


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.


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.

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







How to Cite