Clustering algorithm for a vehicle routing problem with time windows
Abstract
The demand for daily food purchases has increased dramatically, especially during the Covid-19 pandemic. This requires suppliers to face a huge and complex problem of delivering products that meet the needs of their customers on a daily basis. It also puts great pressure on managers on how to make day-to-day decisions quickly and efficiently to both satisfy customer requirements and satisfy capacity constraints. This study proposes a combination of the cluster-first –route-second method and k-means clustering algorithm to deal with a large Vehicle Routing Problem with Time Windows (VRPTW) in the logistics and transportation field. The purpose of this research is to assist decision-makers to make quick and efficient decisions, based on optimal costs, the number of vehicles, delivery time, and truck capacity efficiency. A distribution system of perishable goods in Vietnam is used as a case study to illustrate the effectiveness of our mathematical model. In particular, perishable goods include fresh products of fish, chicken, beef, and pork. These products are packed in different sizes and transferred by vehicles with 1000 kg capacity. Besides, they are delivered from a depot to the main 39 customers of the company with arrival times following customers’ time window. All of the data are collected from a logistics company in Ho Chi Minh city (Vietnam). The result shows that the application of the clustering algorithm reduces the time for finding the optimal solutions. Especially, it only takes an average of 0.36 s to provide an optimal solution to a large Vehicle Routing Problem (VRP) with 39 nodes. In addition, the number of trucks, their operating costs, and their utilization are also shown fully. The logistics company needs 11 trucks to deliver their products to 39 customers. The utilization of each truck is more than 70%. This operation takes the total costs of 6586215.32 VND (Vietnamese Dong), of which, the transportation cost is 1086215.32 VND. This research mainly contributes an effective method for enterprises to quickly find the optimal solution to the problem of product supply.
Keyword : vehicle routing problem, logistics, time window, cluster, route, k-means clustering, transportation
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Aggarwal, D.; Kumar, V. 2019. Mixed integer programming for vehicle routing problem with time windows, International Journal of Intelligent Systems Technologies and Applications 18(1–2): 4–19. https://doi.org/10.1504/IJISTA.2019.097744
Bachu, A. K.; Reddy, K. K.; Vanajakshi, L. 2021. Bus travel time prediction using support vector machines for high variance conditions, Transport 36(3): 221–234. https://doi.org/10.3846/transport.2021.15220
Birim, Ş. 2016. Vehicle routing problem with cross docking: a simulated annealing approach, Procedia – Social and Behavioral Sciences 235: 149–158. https://doi.org/10.1016/j.sbspro.2016.11.010
Cao, W.; Yang, W. 2017. A survey of vehicle routing problem, MATEC Web of Conferences 100: 01006. https://doi.org/10.1051/matecconf/201710001006
Comert, S. E.; Yazgan, H. R.; Kır, S.; Yener, F. 2018. A cluster first-route second approach for a capacitated vehicle routing problem: a case study, International Journal of Procurement Management 11(4): 399–419. https://doi.org/10.1504/IJPM.2018.092766
Ekşioğlu, S. D.; Acharya, A.; Leightley, L. E.; Arora, S. 2009. Analyzing the design and management of biomass-to-biorefinery supply chain, Computers & Industrial Engineering 57(4): 1342–1352. https://doi.org/10.1016/j.cie.2009.07.003
El-Sherbeny, N. A. 2010. Vehicle routing with time windows: an overview of exact, heuristic and metaheuristic methods, Journal of King Saud University – Science 22(3): 123–131. https://doi.org/10.1016/j.jksus.2010.03.002
Kantawong, K.; Pravesjit, S. 2020. An enhanced ABC algorithm to solve the vehicle routing problem with time windows, ECTI Transactions on Computer and Information Technology 14(1): 46–52. https://doi.org/10.37936/ecti-cit.2020141.200016
Khan, S. S.; Ahmad, A. 2004. Cluster center initialization algorithm for k-means clustering, Pattern Recognition Letters 25(11): 1293–1302. https://doi.org/10.1016/j.patrec.2004.04.007
Le, T. D. C.; Nguyen, D. D.; Oláh, J.; Pakurár, M. 2020. Optimal vehicle route schedules in picking up and delivering cargo containers considering time windows in logistics distribution networks: a case study, Production Engineering Archives 26(4): 174–184. https://doi.org/10.30657/pea.2020.26.31
Londoño, J. C.; Tordecilla, R. D.; Martins, L. C.; Juan, A. A. 2021. A biased-randomized iterated local search for the vehicle routing problem with optional backhauls, TOP 29(2): 387–416. https://doi.org/10.1007/s11750-020-00558-x
Pérez-Rodríguez, R.; Hernández-Aguirre, A. 2019. A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows, Computers & Industrial Engineering 130: 75–96. https://doi.org/10.1016/j.cie.2019.02.017
Qi, C; Hu, L. 2020. Optimization of vehicle routing problem for emergency cold chain logistics based on minimum loss, Physical Communication 40: 101085. https://doi.org/10.1016/j.phycom.2020.101085
Ruiz, E.; Soto-Mendoza, V.; Ruiz Barbosa, A. E.; Reyes, R. 2019. Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm, Computers & Industrial Engineering 133: 207–219. https://doi.org/10.1016/j.cie.2019.05.002
Rushton, A.; Croucher, P.; Baker, P. 2022. The Handbook of Logistics and Distribution Management: Understanding the Supply Chain. 7th Edition. Kogan Page. 824 p.
Spliet, R.; Desaulniers, G. 2015. The discrete time window assignment vehicle routing problem, European Journal of Operational Research 244(2): 379–391. https://doi.org/10.1016/j.ejor.2015.01.020
Tasar, B.; Türsel Eliiyi, D.; Kandiller, L. 2019. Vehicle routing with compartments under product incompatibility constraints, Promet – Traffic & Transportation 31(1): 25–36. https://doi.org/10.7307/ptt.v31i1.2670
Toth, P.; Vigo, D. 2014. Vehicle Routing: Problems, Methods, and Applications. 2nd Edition. SIAM – Society for Industrial and Applied Mathematics. 481 p. https://doi.org/10.1137/1.9781611973594
Tretjakovas, J.; Čereška, A. 2021. The truck trailer suspension axles failure analysis and modelling, Transport 36(3): 213–220. https://doi.org/10.3846/transport.2021.14964
VILAS. 2021. Thực trạng chi phí Logistics Việt Nam năm 2020. Vietnam Logistics and Aviation School (VILAS). Available from Internet: https://vilas.edu.vn/chi-phi-logistics-tai-viet-nam-2020.html (in Vietnamese).
Wang, Y.; Wang, L.; Chen, G.; Cai, Z.; Zhou, Y.; Xing, L. 2020. An improved ant colony optimization algorithm to the periodic vehicle routing problem with time window and service choice, Swarm and Evolutionary Computation 55: 100675. https://doi.org/10.1016/j.swevo.2020.100675
Xu, X.; Yuan, H.; Liptrott, M.; Trovati, M. 2018. Two phase heuristic algorithm for the multiple-travelling salesman problem, Soft Computing 22(19): 6567–6581. https://doi.org/10.1007/s00500-017-2705-5
Yao, Y.; Zhu, X.; Dong, H.; Wu, S.; Wu, H.; Tong, L. C.; Zhou, X. 2019. ADMM-based problem decomposition scheme for vehicle routing problem with time windows, Transportation Research Part B: Methodological 129: 156–174. https://doi.org/10.1016/j.trb.2019.09.009
Zhang, D.; Cai, S.; Ye, F.; Si, Y.-W.; Nguyen, T. T. 2017. A hybrid algorithm for a vehicle routing problem with realistic constraints, Information Sciences 394–395: 167–182. https://doi.org/10.1016/j.ins.2017.02.028
Zhang, H.; Zhang, Q.; Ma, L.; Zhang, Z.; Liu, Y. 2019. A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows, Information Sciences 490: 166–190. https://doi.org/10.1016/j.ins.2019.03.070
Zhu, D.; Mortazavi, S. M.; Maleki, A.; Aslani, A.; Yousefi, H. 2020. Analysis of the robustness of energy supply in Japan: Role of renewable energy, Energy Reports 6: 378–391. https://doi.org/10.1016/j.egyr.2020.01.011
Zhu, L; Hu, D. 2019. Study on the vehicle routing problem considering congestion and emission factors, International Journal of Production Research 57(19): 6115–6129. https://doi.org/10.1080/00207543.2018.1533260