A TACTICAL/STRATEGIC LEVEL COST ANALYSIS BASED ON VISIT TIME PREFERENCES FOR VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICKUP AND DELIVERY

Abstract

Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) has been studied for long years and used to model for many real-life applications. The problem is basically to find optimal routes for vehicles that serve customers in a service area to collect as well as deliver goods at the same time. Many logistic companies such as cargo, post, online supermarket, etc. face this problem in their daily operations. Because of high competitions in the sector, companies start to provide visit time preferences that customers can select. Although this is highly preferred by customers, it causes additional costs for companies since it is highly probable that preferences of customers violate optimal routes of vehicles. This problem is called as VRPSPD in Time Windows (VRPSPDTW). In this study, we develop a tactical/strategic level pricing policy based on calculation of additional travel time cost caused by visit time preferences of customers. Idea behind the policy is that solving VRPSPD for same customer set with/without considering time windows in each trial. After conducting many trials for different customer sets, average differences between travel times of VRPSPD and VRPSPDTW are determined. A generic hourly additional prices based on the average differences are calculated. Both problems are modelled as mixed ineger linear programmings and solved with CPLEX 12.9. Differences among travel times vary from 32 to 180 minutes according to experimental settings. Furthermore, results do not only change with time windows, but also different service regions play important role on results.

Keywords

• Vehicle Routing Problem with Simultaneous Pickup and Delivery
• Cost Analysis
• Mixed Integer Linear Programming Model

References

1. Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management science, 6(1), 80-91.
2. Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408–416.
3. Dethloff, J. (2001). Vehicle routing and reverse logistics : the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum, 23(1), 79-96.
4. Montané, F. A. T., & Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33(3), 595–619.
5. Golden, B. L., Raghavan, S., & Wasil, E. A. (Eds.) (2008). The vehicle routing problem: Latest advances and new challenges. Springer Science & Business Media, 43.
6. Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377–386.
7. Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65(1), 39–53.
8. Yazgan, H. R., & Büyükyilmaz, R. G. (2017). Eş zamanlı topla dağıt araç rotalama problemine sezgisel bir çözüm yaklaşımı. Sakarya Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 22(2), 436–449.

9. Kececi, B., Altiparmak, F., & İmdat, K. (2015). Heterojen Eş-Zamanli Topla-Dağit Araç Rotalama Problemi̇: Matemati̇ksel Modeller Ve Sezgi̇sel Bi̇r Algori̇tma. Journal of the Faculty of Engineering and Architecture of Gazi University, 30(2), 185–195.
10. Hezer, S. and Kara, Y. (2013). Eşzamanli daǧitimli ve toplamali araç rotalama problemlerinin çözümü için bakteriyel besin arama optimizasyonu tabanli bir algoritma. Journal of the Faculty of Engineering and Architecture of Gazi University, 28(2), 373–382.
11. Kalayci, C. B. and Kaya, C. (2016). An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 66, 163–175.
12. Koç, Ç. and Laporte, G. (2018). Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research, 91, 79–91.
13. Angelellil, E. and Mansini, R. (2002). The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and Delivery. Quantitative Approaches to Distribution Logistics and Supply Chain Management, 519, 249–267
14. Lagos, C., Guerrero, G., Cabrera, E., Moltedo-Perfetti, A., Johnson, F., & Paredes, F. (2018). An improved particle swarm optimization algorithm for the VRP with simultaneous pickup and delivery and time windows. IEEE Latin America Transactions, 16(6), 1732–1740.
15. Çetin, S. and Gencer, C. (2010). Kesin Zaman Pencereli - Es Zamanli Dagitim Toplamali Arac Rotalama Problemi: Matematiksel Model. Journal of the Faculty of Engineering and Architecture of Gazi University, 25(3), 579-585.
16. Çetin, S. and Gencer, C. (2011). Heterojen Araç Filolu Zaman Pencereli Eş Zamanlı Dağıtım-Toplamalı Araç Rotalama Problemleri: Matematiksel Model. Uluslararası Mühendislik Araştırma ve Geliştirme Dergisi, 3(1), 19–27.
17. Wang, J., Zhou, Y., Wang, Y., Zhang, J., Chen, C. P., & Zheng, Z. (2016). Multiobjective Vehicle Routing Problems with Simultaneous Delivery and Pickup and Time Windows: Formulation, Instances, and Algorithms. IEEE Transactions on Cybernetics, 46(3), 582–594.
18. Wang, C., Mu, D., Zhao, F., & 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.
19. Liu, R., Xie, X., Augusto, V., & Rodriguez, C. (2013). Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. European Journal of Operational Research, 230(3), 475–486.