USE OF HEURISTIC METHODS IN VEHICLE ROUTING PROBLEMS AND AN APPLICATION

Year 2023, Issue: 12, 163 - 176, 29.12.2023

Bilge Meydan

https://doi.org/10.58627/dpuiibf.1395353

Abstract

Logistics activities are one of the biggest cost items for businesses in delivering the products and services they produce to the demand points whether they procure their own logistics network or outsource the logistics service. Vehicle Routing Problems (VRP) applications, which enable both customer satisfaction and saving on the cost of the distance traveled while carrying out logistics activities, provide great benefits to businesses. Firstly in this study presents a literatüre review compiling studies examining VRP models for different needs and heuristic and meta-heuristic approaches used to support the solution. Then, an empirical study has been carried out that fuel replenishment routing for 45 fuel stations in Ankara with the help of a solver based on the Clarke and Wright saving algorithm and improvement heuristics. This study has examined parameter sensitivities under different scenarios and it has indicated how demand variability, vehicle capacity, number of iterations and depth parameters affected the solution time in routing, the number of routes created and the distance traveled.

Keywords

Vehicle Routing Problems, Clarke and Wright Saving Algorithm, Fuel Replenishment Routing

ARAÇ ROTALAMA PROBLEMLERİNDE SEZGİSEL YÖNTEMLERİN KULLANIMI VE BİR UYGULAMA

Abstract

Lojistik faaliyetleri işletmelerin ürettiği ürün ve hizmeti müşteri talepleri doğrultusunda belirtilen noktalara ulaştırmada ister kendi lojistik ağını ister lojistik hizmetini dışarıdan tedarik etsin en büyük maliyet kalemlerinden biridir. Lojistik faaliyetlerini gerçekleştirirken hem müşteri memnuniyetini sağlamak hem de kat edilen yolun maliyetinden tasarruf etmeyi sağlayan Araç Rotalama Problemleri (ARP) uygulamaları işletmelere büyük fayda sağlamaktadır. Bu çalışmada, farklı ihtiyaçlara yönelik ARP modelleri tanıtılmış, çözüme destek olarak kullanılan sezgisel ve meta sezgisel yaklaşımlar incelenen çalışmalar üzerinden açıklanarak detaylı bir literatür sunulmuştur. Ankara’da 45 akaryakıt istasyonu için ikmal dağıtımı yapan tankerlerin rotalaması Clarke ve Wright kazanım algoritması tabanlı ve iyileştirme sezgisellerinin kullanıldığı bir çözücü yardımıyla gerçekleştirilmiş ve parametre duyarlılıkları farklı senaryolar altında incelenmiştir. Bu çalışma ile sezgisel yaklaşımın talep değişkenliği, araç kapasitesi, iterasyon ve derinlik sayısı parametrelerinin rotalamada çözüm süresi, oluşturulan rota sayısı ve kat edilen mesafeye nasıl etki ettiği gösterilmiştir.

Keywords

Araç Rotalama Problemleri, Clarke ve Wright Kazanım Algoritması, Akaryakıt İkmal Rotalaması

References

• Abraham, A., Jos, B., & Mangalathu, G. (2012). The Pickup And Delivery Vehicle Routing Problem For Perishable Goods In Air-Cargo Industry. International Journal of Emerging Technology and Advanced Engineering, 790-794.
• Al-Hinai, N., & Triki, C. (2020). A two-level evolutionary algorithm for solving the petrol station replenishment problem with periodicity constraints and service choice. Annals of Operations Research, 286(1-2), 325-350.
• Annouch, A., & Bellabdaoui, A. (2017). Variable Neighborhood Search heuristic for the full truckload problem in liquefied petroleum gas supply. International Colloquium on Logistics and Supply Chain Management (LOGISTIQUA) (pp. 193-198). Rabat, Morocco: IEEE.
• Archetti, C., Savelsbergh, M., & Speranza, M. (2006). Worst-Case Analysis for Split Delivery Vehicle Routing Problems. Transportation Science, 226-234.
• Azi, N., Gendreau, M., & Potvin, J.-Y. (2010). An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. European Journal of Operational Research, 756-763.
• Battarra, M., Erdoğan, G., Laporte , G., & Vigo, D. (2010). The Traveling Salesman Problem with Pickups. Deliveries, and Handling Costs, Transportation Science, 383-399.
• Belfiore, P., Tsugunobu, H., & Yoshizaki, Y. (2009). Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil. European Journal of Operational Research, 750-758.
• Calvete, H. I., Galé, C., Oliveros, M.-J., & Sánchez-Valverde, B. (2007). A goal programming approach to vehicle routing problems with soft time windows. European Journal of Operational Research, 1720-1733.
• Che, A., Wang, W., Mu, X., Zhang, Y., & Feng, J. (2022). IEEE Transactions on Intelligent Transportation Systems. Tabu-Based Adaptive Large Neighborhood Search for Multi-Depot Petrol Station Replenishment With Open Inter-Depot Routes, 24(1), 316-330.
• Chu, C.-W. (2005). A heuristic algorithm for the truckload and less-than-truckload problem. European Journal of Operational Research, 657-667.
• Clarke, G., & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operation Research, 12, 568-581.
• Cordeau, J., Laporte, G., Savelsbergh, M., & Vigo, D. (2007). Vehicle routing. Handbooks in operations research and management science, 14, 367-428.
• Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., & Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society, 53, 512-522.
• Cornillier, F., Laporte, G., Boctor, F., & Renaud, J. (2009). The petrol station replenishment problem with time windows. Computers & Operations Research, 36(3), 919-935.
• Crevier, B., Cordeau , J.-F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 756-773.
• Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
• Dantzig, G. B., Fulkerson, D., & Johnson, S. (1959). On a linear-programming, combinatorial approach to the traveling-salesman problem. Operations Research, 7, 58-66.
• 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.
• Dror, M., & Trudeau, P. (1986). Stochastic vehicle routing with modified savings algorithm. European Journal of Operational Research, 23(2), 228-235.
• Dror, M., Laporte, G., & Trudeau, P. (1989). Vehicle routing with stochastic demands: Properties and solution frameworks. Transportation science, 23(3), 166-176.
• Dror, M., Laporte, G., & Trudeau, P. (1994). Vehicle routing with split deliveries. Discrete Applied Mathematics, 50(3), 239-254.
• Dündar, H., Soysal, M., Ömürgönülşen, M., & Kanellopoulos, A. (2022). A green dynamic TSP with detailed road gradient dependent fuel consumption estimation. Computers & Industrial Engineering, 168, 108024.
• Grondys, K. (2020). Optimization of Vehicle Routes for Inter-warehouse Operations Using the Clark and Wright's Saving Algorithm. Global Journal of Entrepreneurship and Management, 1(2), 16-26.
• Ho, W., Ho, G., Ji, P., & Lau, H. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 547-558.
• Hoff, A., & Løkketangen, A. (2006). Creating Lasso-solutions for the Traveling Salesman Problem with Pickup and Delivery by Tabu Search. Central European Journal of Operations Research, 125-140.
• Jaegere, N. D., Defraeye, M., & Van Nieuwenhuyse, I. (2014). The Vehicle Routing Problem: State Of The Art Classification And Review. KU Leuven - Faculty of Economics and Business. Leuven (Belgium): FEB Research Report KBI.
• Kang, K. H., Lee, B., Lee, Y., & Lee, Y. (2008). A heuristic for the vehicle routing problem with due times. Computers & Industrial Engineering, 421-431.
• Kumar, S., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 4, 66-74.
• Laporte, G. (2009). Fifty years of vehicle routing. Transportation science, 43(4), 4008-416.
• Liu, X., Chen, Y., Por, L., & Ku, C. (2023). A systematic literature review of vehicle routing problems with time windows. Sustainability, 15(15), 12004.
• Mahmoudi, M., & Zhou, X. (2016). Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations. Transportation Research Part B: Methodological, 19-42.
• Mańdziuk, J. (2018). New shades of the vehicle routing problem: Emerging problem formulations and computational intelligence solution methods. IEEE Transactions on Emerging Topics in Computational Intelligence, 3(3), 230-244.
• Martinovic, G., Aleksi, I., & Baumgartner, A. (2008). Single-Commodity Vehicle Routing Problem with Pickup and Delivery Service. Hindawi Publishing Corporation Mathematical Problems in Engineering, 1-18.
• Miller, C., Tucker, A., & Zemlin, R. (1960). Integer Programming Formulation of Traveling Salesman Problems. JACM.
• Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386.
• Nagy, G., Wassan, N., Sperenza, M., & Salhi, S. (2015). The Vehicle Routing Problem with Divisible Deliveries and Pickups. Transportation Science, 271-294.
• Osvald, A., & Stirn, L. (2008). A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food. Journal of Food Engineering, 285-295.
• Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & operations research, 34(8), 2403-2435.
• Prins, C. (2009). Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence, 916-928.
• R.Tavakkoli-Moghaddam, Safaei, N., & Gholipour, Y. (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 445-454.
• R.Tavakkoli-Moghaddam, Saremi, A., & Ziaee, M. (2006). A memetic algorithm for a vehicle routing problem with backhauls. Applied Mathematics and Computation, 1049-1060.
• Solomon, M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
• Soysal, M., Çimen, M., Ömürgönülşen, M., & Belbağ, S. (2019). Performance comparison of two recent heuristics for green time dependent vehicle routing problem. International Journal of Business Analytics (IJBAN), 6(4), 1-11.
• Tan, K. C. (2000). A Framework Of Supply Chain Management Literature. European Journal Of Purchasing & Supply Chain Management, 39-48.
• Tang, J., Pan, Z., Fung, R., & Lau, H. (2009). Vehicle routing problem with fuzzy time windows. Fuzzy Sets and Systems, 683-695.
• Toth, P., & Vigo, D. (2002). The vehicle routing problem. In Society for Industrial and Applied Mathematics (pp. 13-15). Philadelphia.
• Toth, P., & Vigo, D. (1997). An exact algorithm for the vehicle routing problem with backhauls. Transportation science,, 31(4), 372-385.
• Wang, H., & Shen, J. (2007). Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints. Applied Mathematics and Computation, 1237-1249.
• Wei, X., Liao, Q., Zhang, H., Liang, Y., Wang, B., Xu, N., & Yuan, M. (2021). MILP formulations for highway petrol station replenishment in initiative distribution mode. Petroleum Science, 18, 994-1010.
• Xu, G., Xu, M., Wang, Y., Liu, Y., & Lv, Q. (2020). Collaborative multidepot petrol station replenishment problem with multicompartments and time window assignment. Journal of Advanced Transportation, 1-22.
• Xu, X., Lin, Z., & Zhu, J. (2022). DVRP with limited supply and variable neighborhood region in refined oil distribution. Annals of Operations Research, 1-25.
• Xu, X., Lin, Z., Li, X., Shang, C., & Shen, Q. (2022). Multi-objective robust optimisation model for MDVRPLS in refined oil distribution. International Journal of Production Research, 60(22), 6772-6792.