A Multi Depot Multi Product Split Delivery Vehicle Routing Problem with Time Windows: A Real Cash in Transit Problem Application in Istanbul, Turkey

Abstract

In today’s highly competitive world market, companies and private enterprises deliver their business on time. Their value and total costs play an essential role in their positions in the market. The most costly and difficult factors to regulate are shipping and distribution systems. The high cost of transportation and distribution systems is one reason for the increase in vehicle routing problems and studies in logistics network design. Vehicle routing problems (VRPs) are concerned with finding the optimal or near-optimal routes for vehicles to follow in meeting the demands of customers or facilities. The cash in transit (CIT) problem as a version of the VRP, deals with the planning of money distribution from the depot(s) to Automated Teller Machines (ATMs) safely and quickly. This paper investigates a novel CIT problem, which is a variant of split delivery VRP with time windows. To establish a novel approach to the CIT problem, different money currencies are considered. Also, multiple depots and heterogeneous fleet are included in the problem. To handle the CIT problem more realistically, a risk constrained multi-depot multi-product heterogeneous fleet split delivery VRP with a time windows formulation is proposed. The problem is hence formulated as a mixed-integer mathematical model. The mathematical model is run for different scenarios and optimal routes are obtained. The experimental analysis shows that the mathematical model developed, can help decision-makers to obtain effective solutions for their CIT operations with different money currencies.

Keywords

• vehicle routing problem
• cash in transit
• split-delivery
• İstanbul

References

1. Afshar-Nadjafi, B., & Afshar-Nadjafi, A. (2017). A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. Journal of King Saud University - Engineering Sciences, 29(1), 29–34. https://doi.org/10.1016/j.jksues.2014.04.007
2. Ágoston, K. C., Benedek, G., & Gilányi, Z. (2016). Pareto improvement and joint cash management optimisation for banks and cash-in-transit firms. European Journal of Operational Research, 254(3), 1074–1082. https://doi.org/10.1016/j.ejor.2016.04.045
3. Archetti, C., & Speranza, M. G. (2012). Vehicle routing problems with split deliveries. International Transactions in Operational Research, 19(1–2), 3–22. https://doi.org/10.1111/j.1475-3995.2011.00811.x
4. Boonsam, P., Suthikarnnarunai, N., & Chitphaiboon, W. (2011). Assignment problem and vehicle routing problem for an improvement of cash distribution. Proceedings of the World Congress on Engineering and Computer Science, 2, 1160–1164.
5. Bozkaya, B., Salman, F. S., & Telciler, K. (2017). An adaptive and diversified vehicle routing approach to reducing the security risk of cash-in-transit operations. Networks, 69(3), 256–269. https://doi.org/10.1002/net.21735
6. Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., & Juan, A. A. (2014). Rich vehicle routing problem: Survey. ACM Computing Surveys, 47(2), 1–28. https://doi.org/10.1145/2666003
7. Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80–91. https://doi.org/10.1287/mnsc.6.1.80
8. Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342–354. https://doi.org/10.1287/opre.40.2.342

9. Ghannadpour, S. F., & Zandiyeh, F. (2020). An adapted multi-objective genetic algorithm for solving the cash in transit vehicle routing problem with vulnerability estimation for risk quantification. Engineering Applications of Artificial Intelligence, 96(June 2019), 103964. https://doi.org/10.1016/j.engappai.2020.103964
10. Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers and Industrial Engineering, 65(1), 39–53. https://doi.org/10.1016/j.cie.2012.01.005
11. Hepenstal, S., & Johnson, S. D. (2010). The concentration of cash-in-transit robbery. Crime Prevention and Community Safety, 12(4), 263–282. https://doi.org/10.1057/cpcs.2010.14
12. Ho, S. C., & Haugland, D. (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers and Operations Research, 31(12), 1947–1964. https://doi.org/10.1016/ S0305-0548(03)00155-2
13. Kaabachi, I., Jriji, D., & Krichen, S. (2017). An improved ant colony optimization for green multi-depot vehicle routing problem with time windows. Proceedings - 18th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, SNPD 2017, 339–344. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/ SNPD.2017.8022743
14. Larrain, H., Coelho, L. C., & Cataldo, A. (2017). A Variable MIP Neighborhood Descent algorithm for managing inventory and distribution of cash in automated teller machines. Computers and Operations Research, 85, 22–31. https://doi.org/10.1016/j.cor.2017.03.010
15. Levy, D., Sundar, K., & Rathinam, S. (2014). Heuristics for routing heterogeneous unmanned vehicles with fuel constraints. Mathematical Problems in Engineering, 2014. https://doi.org/10.1155/2014/131450
16. Michallet, J., Prins, C., Amodeo, L., Yalaoui, F., & Vitry, G. (2014). Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services. Computers and Operations Research, 41(1), 196–207. https://doi.org/10.1016/j.cor.2013.07.025
17. Nugroho, S. M., Nafisah, L., Khannan, M. S. A., Mastrisiswadi, H., & Ramdhani, M. N. (2020). Vehicle Routing Problem with Heterogeneous Fleet, Split Delivery, Multiple Product, Multiple Trip, and Time Windows: A Case study in fuel distribution. IOP Conference Series: Materials Science and Engineering, 847(1), 012066. Institute of Physics Publishing. https://doi.org/10.1088/1757-899X/847/1/012066
18. Park, Y. B., Yoo, J. S., & Park, H. S. (2016). A genetic algorithm for the vendor-managed inventory routing problem with lost sales. Expert Systems with Applications, 53, 149–159. https://doi.org/10.1016/j.eswa.2016.01.041
19. Ramos, T. R. P., Gomes, M. I., & Barbosa-Póvoa, A. P. (2020). A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes. OR Spectrum, 42(1), 75–110. https://doi. org/10.1007/s00291-019-00568-7
20. Sharma, R., & Saini, S. (2020). Heuristics and Meta-Heuristics Based Multiple Depot Vehicle Routing Problem: A Review. Proceedings of the International Conference on Electronics and Sustainable Communication Systems, ICESC 2020, 683–689. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/ICESC48915.2020.9155814
21. Soeanu, A., Ray, S., Berger, J., Boukhtouta, A., & Debbabi, M. (2020). Multi-depot vehicle routing problem with risk mitigation: Model and solution algorithm. Expert Systems with Applications, 145, 113099. https://doi.org/10.1016/j.eswa.2019.113099
22. Stodola, P. (2018). Using Metaheuristics on the Multi-Depot Vehicle Routing Problem with Modified Optimization Criterion. Algorithms, 11(5), 74. https://doi.org/10.3390/a11050074
23. Talarico, L. (2016). Secure vehicle routing: models and algorithms to increase security and reduce costs in the cash-in-transit sector. 4OR, 14(1), 105–105. https://doi.org/10.1007/s10288-015-0290-y
24. Talarico, L., Sörensen, K., & Springael, J. (2015). Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem. European Journal of Operational Research, 244(2), 457–470. https://doi. org/10.1016/j.ejor.2015.01.040
25. Talarico, L., Sörensen, K., & Springael, J. (2017). A biobjective decision model to increase security and reduce travel costs in the cash-in-transit sector. International Transactions in Operational Research, 24(1–2), 59–76. https://doi.org/10.1111/itor.12214
26. Tarantilis, C. D., & Kiranoudis, C. T. (2004). An adaptive memory programming method for risk logistics operations. International Journal of Systems Science, 35(10), 579–590. https://doi.org/10.1080/00207 720412331285986
27. Van Anholt, R. G., Coelho, L. C., Laporte, G., & Vis, I. F. A. (2016). An inventory-routing problem with pickups and deliveries arising in the replenishment of automated teller machines. Transportation Science, 50(3), 1077–1091. https://doi.org/10.1287/trsc.2015.0637
28. Wang, B., Qian, Q., Tan, Z., Zhang, P., Wu, A., & Zhou, Y. (2020). Multidepot Heterogeneous Vehicle Routing Problem for a Variety of Hazardous Materials with Risk Analysis. Scientific Programming, 2020. https://doi.org/10.1155/2020/8839628
29. Xu, Y., Wang, L., & Yang, Y. (2012). A New Variable Neighborhood Search Algorithm for the Multi Depot Heterogeneous Vehicle Routing Problem with Time Windows. Electronic Notes in Discrete Mathematics, 39, 289–296. https://doi.org/10.1016/j.endm.2012.10.038
30. Yan, S., Wang, S. S., & Wu, M. W. (2012). A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem. Computers and Industrial Engineering, 63(2), 464–473. https:// doi.org/10.1016/j.cie.2012.04.004
31. Yao, B., Yu, B., Hu, P., Gao, J., & Zhang, M. (2016). An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot. Annals of Operations Research, 242(2), 303–320. https://doi.org/10.1007/s10479-015-1792-x