Enhancing Vehicle Routing Efficiency through Branch and Bound and Heuristic Methods

Authors

  • Ahmad Zaki Mubarak Graduate School of Mathematics, Universitas Sumatera Utara, Medan, Indonesia
  • Herman Mawengkang Department of Mathematics, Universitas Sumatera Utara, Medan, Indonesia
  • Saib Suwilo Department of Mathematics, Universitas Sumatera Utara, Medan, Indonesia

DOI:

10.33395/sinkron.v8i3.13759

Keywords:

Vehicle Routing Problem; Branch and Bound; heuristic techniques; route optimization; supply chain management

Abstract

The Vehicle Routing Problem (VRP) is a critical challenge in logistics, impacting delivery efficiency and costs. Traditional VRP solutions often fail to address real-world dynamics such as fluctuating traffic conditions and varying customer demands. This research proposes a novel VRP model integrating real-time data to enhance route optimization. By combining the precision of the Branch and Bound (B&B) approach with the flexibility of heuristics like Genetic Algorithms and Simulated Annealing, the hybrid method dynamically adjusts routes based on live traffic and demand updates. The objective is to reduce operational costs and improve logistical performance. The hybrid model’s effectiveness is validated through comparative analysis with traditional VRP solutions, demonstrating significant improvements in cost reduction, fuel consumption, vehicle wear and tear, and customer satisfaction due to timely deliveries. These advancements highlight the potential of real-time data integration and advanced optimization techniques in providing robust solutions for modern logistics challenges. Future research should focus on incorporating more advanced data sources and testing the model in various real-world scenarios to further enhance its practicality and performance, ensuring businesses remain competitive in a dynamic market. This study underscores the importance of continuous innovation in VRP solutions to achieve sustainable, efficient, and customer-centric logistics operations.

GS Cited Analysis

Downloads

Download data is not yet available.

References

Ai, T. J., & Kachitvichyanukul, V. (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693–1702. https://doi.org/10.1016/j.cor.2008.04.003

Baldacci, R., Hadjiconstantinou, E., & 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. https://doi.org/10.1287/opre.1040.0111

Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120(2), 347–380. https://doi.org/10.1007/s10107-008-0218-9

Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300–313. https://doi.org/https://doi.org/10.1016/j.cie.2015.12.007

Chen, K.-T., Dai, Y., Fan, K., & Baba, T. (2015). A Particle Swarm Optimization with Adaptive Multi-Swarm Strategy for Capacitated Vehicle Routing Problem. Proceedings of the 1st International Conference on Industrial Networks and Intelligent Systems. https://doi.org/10.4108/icst.iniscom.2015.258972

Cordeau, J.-F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007). Vehicle Routing. In C. Barnhart & G. Laporte (Eds.), Handbooks in Operations Research and Management Science (Volume 14, pp. 367–428). Elsevier. https://doi.org/10.1016/S0927-0507(06)14006-2

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

Davoodi, M., Malekpour Golsefidi, M., & Mesgari, M. S. (2019). A HYBRID OPTIMIZATION METHOD FOR VEHICLE ROUTING PROBLEM USING ARTIFICIAL BEE COLONY AND GENETIC ALGORITHM. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLII-4/W18, 293–297. https://doi.org/10.5194/isprs-archives-XLII-4-W18-293-2019

Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. de, Reis, M., Uchoa, E., & Werneck, R. F. (2006). Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Mathematical Programming, 106(3), 491–511. https://doi.org/10.1007/s10107-005-0644-x

Gendreau, M., Laporte, G., & Potvin, J.-Y. (2002). Metaheuristics for the Capacitated VRP. In P. Toth & D. Vigo (Eds.), The Vehicle Routing Problem (pp. 129–154). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898718515.ch6

Herrero, R., Rodríguez, A., Cruz, J. C., & Juan, A. A. (2014). Solving vehicle routing problems with asymmetric costs and heterogeneous fleets. International Journal of Advanced Operations Management, 6(1), 58–80. https://doi.org/10.1504/IJAOM.2014.059620

Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation Science, 43(4), 408–416. https://doi.org/10.1287/trsc.1090.0301

Laporte, G., & Semet, F. (2002). Classical Heuristics for the Capacitated VRP. In P. Toth & D. Vigo (Eds.), The Vehicle Routing Problem (pp. 109–128). SIAM.

Mingozzi, A. (2005). The Multi-depot Periodic Vehicle Routing Problem. In J.-D. Zucker & L. Saitta (Eds.), Abstraction, Reformulation and Approximation (pp. 347–350). Springer Berlin Heidelberg. https://doi.org/10.1007/11527862_27

Nurcahyo, R., Irawan, D. A., & Kristanti, F. (2023). The Effectiveness of the Clarke & Wright Savings Algorithm in Determining Logistics Distribution Routes (case study PT.XYZ). E3S Web of Conferences, 426, 01107. https://doi.org/10.1051/e3sconf/202342601107

Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal Für Betriebswirtschaft, 58(1), 21–51. https://doi.org/10.1007/s11301-008-0033-7

Prins, C. (2002). Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case. Journal of Mathematical Modelling and Algorithms, 1(2), 135–150. https://doi.org/10.1023/A:1016516326823

Pureza, V., Morabito, R., & Reimann, M. (2012). Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW. European Journal of Operational Research, 218(3), 636–647. https://doi.org/10.1016/j.ejor.2011.12.005

Razali, N. M. (2015). An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints. Procedia - Social and Behavioral Sciences, 195, 1922–1931. https://doi.org/10.1016/j.sbspro.2015.06.203

Toth, P., & Vigo, D. (1998). Exact Solution of the Vehicle Routing Problem. In T. G. Crainic & G. Laporte (Eds.), Fleet Management and Logistics (pp. 1–31). Springer US. https://doi.org/10.1007/978-1-4615-5755-5_1

Wang, G., Zhang, Y.-B., & Chen, J.-W. (2011). A Novel Algorithm to Solve the Vehicle Routing Problem with Time Windows: Imperialist Competitive Algorithm. INTERNATIONAL JOURNAL ON Advances in Information Sciences and Service Sciences, 3(5), 108–116. https://doi.org/10.4156/aiss.vol3.issue5.14

Wang, W., & Jiang, L. (2022). Two-Stage Solution for Meal Delivery Routing Optimization on Time-Sensitive Customer Satisfaction. Journal of Advanced Transportation, 2022, 1–15. https://doi.org/10.1155/2022/9711074

Yi, S., & Yue, S. (2016). Study of logistics distribution route based on improved genetic algorithm and ant colony optimization algorithm. Internet of Things (IoT) and Engineering Applications. https://doi.org/10.23977/iotea.2016.11003

Downloads


Crossmark Updates

How to Cite

Mubarak, A. Z., Mawengkang, H., & Suwilo, S. (2024). Enhancing Vehicle Routing Efficiency through Branch and Bound and Heuristic Methods. Sinkron : Jurnal Dan Penelitian Teknik Informatika, 8(3), 1463-1472. https://doi.org/10.33395/sinkron.v8i3.13759

Issue

Vol. 8 No. 3 (2024): Research Artikel Volume 8 Issue 3, July 2024

Section

Articles

License

Copyright (c) 2024 Ahmad Zaki Mubarak, Herman Mawengkang

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Crossref
Scopus
Google Scholar
Europe PMC

Most read articles by the same author(s)

1 2 > >>