AccScience Publishing / IJOCTA / Online First / DOI: 10.36922/IJOCTA025480215
Submit to IJOCTA
Cite this article
4
Download
32
Views
Journal Browser
Volume | Year
Issue
Search
Forthcoming Issue
Current Issue
View All
News and Announcements
View All
RESEARCH ARTICLE

A two-phase branch-and-bound algorithm for solving vehicle routing problem with maximum duration constraint

Asri Bekti Pratiwi1,2 ,  Salmah Salmah1* ,  Irwan Endrayanto1
Show Less
1 Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Gadjah Mada, Yogyakarta, Indonesia
2 Department of Mathematics, Faculty of Science and Technology, Universitas Airlangga, Surabaya, East Java, Indonesia
IJOCTA, 025480215 https://doi.org/10.36922/IJOCTA025480215
Received: 27 November 2025 | Revised: 12 February 2026 | Accepted: 24 February 2026 | Published online: 30 April 2026
© 2026 by the Author(s). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC-by the license) ( https://creativecommons.org/licenses/by-nc/4.0/ )
Download PDF
XML
Cite
Abstract

Branch-and-bound (B&B) methods are widely recognized for their ability to provide exact solutions to combinatorial optimization problems, including routing models. This study presents a Two-phase B&B algorithm developed to address the Vehicle routing problem (VRP) under maximum duration constraints, offering an effective framework for obtaining a cost-optimal routing solution. The first phase of the algorithm employs a heuristic to construct a tour that satisfies the classical VRP constraints. In the second phase, a recursive dynamic programming procedure is applied to partition the obtained tour into a set of feasible subtours that meet the maximum allowable duration per vehicle. This dual-phase approach addresses the computational challenges of traditional B&B methods by decoupling tour optimization from constraint satisfaction. Computational experiments were conducted on benchmark VRP datasets and compared with exact methods and heuristic algorithms. The computational results demonstrate that the proposed algorithm consistently outperforms in terms of solution quality, number of explored nodes, and computation time. These findings demonstrate the effectiveness of the algorithm in obtaining optimal solutions for VRP with maximum duration constraints.

Keywords
Branch and bound
Dynamic programming
Heuristic algorithm
Vehicle routing problem
Maximum duration constraint
Funding
None.
Conflict of interest
The authors report no conflicts of interest. The authors alone are responsible for the content and writing of this article.
References
  1. Morrison DR, Jacobson SH, Sauppe JJ, Sewell EC. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 2016;19:79–102. https://www.doi.org/10.1016/j.disopt.2016.01.005
  2. Taha AH. Operations Research: An Introduction. 8th ed. Upper Saddle River, New Jersey; 2006. https://www.amazon.com/Operations-Research-Introduction-Hamdy-Taha
  3. Theurich F,  Fischer  A,  Scheithauer    A branch-and-bound approach for a vehicle routing problem with customer costs. EURO J Comput Optim. 2021;9:100003. https://www.doi.org/10.1016/j.ejco.2020.100003
  4. Duman EN, Tas D, Catay B. A bidirectional branch-and-price algorithm with pulse procedure for the electric vehicle routing problem with flexible deliveries. Transp Res Part C Emerg Technol. 2024;165:104699. https://www.doi.org/10.1016/j.trc.2024.104699
  5. Ozbaygin G, Karasan OE, Savelsbergh M, Yaman H. A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transp Res Part B Methodol. 2017;100:115–137. https://www.doi.org/10.1016/j.trb.2017.02.003
  6. Li J, Qin  H,  Baldacci  R,  Zhu  Branch-and-price-and-cut for the synchronized vehicle  routing  problem  with  split  delivery, proportional service time and multiple time windows. Transp Res Part E Logist Trans Rev. 2020;140:101955. https://www.doi.org/10.1016/j.tre.2020.101955
  7. Laporte G,   Nobert   Y,   Taillefer   A   branch-and-bound   algorithm for the    asymmetrical distance-constrained vehicle  routing  problem.  Math Model. 1987;9(12):857–868. https://www.doi.org/10.1016/0270-0255(87)90004-2
  8. Zhang X, Chen L, Gendreau M, Langevin A branch-and-cut  algorithm  for  the vehicle routing problem with two-dimensional loading constraints. Eur J of Oper Res. 2020;302(1):259–269. https://www.doi.org/10.1016/j.ejor.2021.12.050
  9. Morrison DR, Sauppe JJ, Sewell EC, Jacobson SH. A wide branching strategy for the graph coloring   INFORMS  J Comput. 2014;26:704–717. https://www.doi.org/10.1287/ijoc.2014.0593
  10. Kolesar PJ. A branch and bound algorithm for the knapsack problem. Manag Sci. 1967;13(9):723–735. https://www.doi.org/10.1287/mnsc.13.9.723
  11. Fischetti M, Toth P, Vigo D. A branch-and-bound algorithm for the capacitated vehicle routing problem on directed   Oper Res. 1994;42:846–859. https://www.doi.org/10.1287/opre.42.5.846
  12. Dantzig GB, Ramser JH. The truck dispatching problem. Manag Sci. 1959;6:80–91. https://www.doi.org/10.1287/mnsc.6.1.80
  13. Toth P, Vigo D. The Vehicle Routing Problem. Philadelphia; 2001. https://www.doi.org/10.1137/1.9780898718515
  14. Golden B, Wang X, Wasil E. The Evolution of the Vehicle Routing Problem : A Survey of VRP Research and Practice from 2005 to 2022. Springer Cham; 2023.
  15. Achuthan NR, Caccetta L. Integer linear programming formulation for a vehicle routing problem. Eur J Oper Res. 1991;52(1):86-89. https://www.doi.org/10.1016/0377-2217(91)90338-V
  16. Bula GA, Gonzalez FA, Prodhon C, Afsar HM, Velasco NM. Mixed Integer Linear Programming Model for Vehicle Routing Problem for Hazardous Materials Transportation. IFAC-PapersOnLine. 2016;49(12):538-543. https://www.doi.org/10.1016/j.ifacol.2016.07.691
  17. Madankumar S, Rajendran C. A mixed integer linear programming model for the vehicle routing problem with simultaneous delivery and pickup by heterogeneous vehicles, and constrained by time windows. S¯adhan¯a. 2019;44:39. https://www.doi.org/10.1007/s12046-018-1048-y
  18. Florio AM, Hartl RF, Minner S, Salazar-Gonz´alez J-S. A Branch-and-Price Algorithm for the Vehicle Routing Problem  with  Stochastic Demands and Probabilistic Duration Constraints. Transp Sci. 2020;55(1):1-17. https://www.doi.org/10.1287/trsc.2020.1002
  19. Yang W, Ke L, Wang DZW, Lam JSL. A branch-price-and-cut algorithm  for the vehicle routing problem with release and due dates. Transp Res Part E Logist Transp Rev. 2021;145:102167. https://www.doi.org/10.1016/j.tre.2020.102167
  20. Nafstad GM, Desaulniers G, St˚alhane M. Branch-Price-and-Cut for the Electric Vehicle Routing Problem with Heterogeneous Recharging Technologies and Nonlinear Recharging Functions. Transp Sci. 2025;59(3):628-646. https://www.doi.org/10.1287/trsc.2024.0725
  21. Cordeau JF, Gendreau M, Hertz A, Laporte G, Sormany JS. New Heuristics for the Vehicle Routing Problem. In: Langevin, A., Riopel, D. (eds) Logistics  Systems:   Design and Optimization. Springer, Boston, MA; 2005. https://www.doi.org/10.1007/0-387-24977-X9
  22. Ahmed ZH, Yousefikhoshbakht    An improved  tabu  search  algorithm  for  solving heterogeneous fixed fleet open vehicle routing problem  with  time  windows.  Alex Eng J. 2023;64(1):349-363. https://www.doi.org/10.1016/j.aej.2022.09.008
  23. Voigt S. A review and ranking of operators in adaptive large  neighborhood  search for vehicle routing problems. Eur J Oper Res. 2015;322(2):357-375. https://www.doi.org/10.1016/j.ejor.2024.05.033
  24. French AP, Robinson AC, Wilson JM. Using a Hybrid Genetic-Algorithm/Branch and Bound Approach to Solve Feasibility and Optimization Integer Programming Problems. J Heuristics. 2001;7:551–564. https://www.doi.org/10.1023/A:1011921025322
  25. Bertacco L, Fischetti M, Lodi A. A feasibility pump heuristic for  general  mixed-integer problems. Discrete Optim. 2007;4(1)63-76. https://www.doi.org/10.1016/j.disopt.2006.10.001
  26. Fischetti M, Glover F, Lodi A. The feasibility pump. Math Program. 2005;104:91–104. https://www.doi.org/10.1007/s10107-004-0570-3
  27. Conforti M, Cornuejols G, Zambelli G. Integer Programming. Switzerland; 2014. https://www.doi.org/10.1007/978-3-319-11008-0
  28. Praveen V, Keerthika  P,  Sivapriya  G, Sarankumar  A,  Bhasker  B.  Vehicle  Routing Optimization Problem: A Study on Capacitated Vehicle Routing Problem. Mater Today Proc. 2022;64(1):670-674. https://www.doi.org/10.1016/j.matpr.2022.05.185
  29. Kandakoglu A, Saure  A,  Michalowski W, Aquino  M,  Graham  J,  McCormick  A decision support system for home dialysis visit scheduling and nurse routing. Decis Support Syst. 2020;130. https://www.doi.org/10.1016/j.dss.2019.113224
  30. Kulkarni RV, Brave PR. Integer programming formulations of vehicle routing problems. Eur J Oper Res. 1985;20(1):58-67. https://www.doi.org/10.1016/0377-2217(85) 90284-X
  31. Golden B, Raghavan S, Wasil E. The Vehicle Routing Problem: Latest Advances and New Challenges. Springer New York, NY; 2010. https://www.doi.org/10.1007/978-0-387-77778-8
  32. Pereira FB, Tavares J. Bio-inspired Algorithms for the Vehicle Routing Problem. Springer Berlin, Heidelberg; 2010. https://www.doi.org/10.1007/978-3-540-85152-3
  33. Korte B, Vygen J. Combinatorial Optimization: Theory and Algorithm. Germany; 2000. https://www.doi.org/10.1007/978-3-662-56039-6
  34. Lin S. Computer solutions of the travelling salesman Bell  Syst  Tech  J. 1965;44:2245–2269. https://www.doi.org/10.1002/j.1538-7305.1965.tb04146.x
  35. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 4th edition. The MIT Press Cambridge, Massachusetts London, England; 2022. https://www.amazon.com/Introduction-Algorithms-fourth-Thomas-Cormen
  36. Denardo EV. Dynamic programming: models and applications. Prentice-Hall. Inc; 2003.
  37. Art L, Mauch H. Dynamic Programming: A computational tools. Springer Berlin, Heidelberg; 2006. https://www.doi.org/10.1007/978-3-540-37014-7
  38. Bellman R. Dynamic Programming. New Jersey, USA; 1957. https://www.doi.org/10.2307/j.ctv1nxcw0f
  39. Solomon M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Oper Res. 1987;35(2):254–265. https://www.doi.org/10.1287/opre.35.2.254
  40. Zhou Y, Hao  J-K,  Xiao  M,  Jin    An effective branch-and-bound algorithm for the maximum s-bundle problem. Eur J Oper Res. 2022;297(1):27–39. https://www.doi.org/10.1016/j.ejor.2021.05.001
Share
Back to top
An International Journal of Optimization and Control: Theories & Applications, Electronic ISSN: 2146-5703 Print ISSN: 2146-0957, Published by AccScience Publishing
We use cookies on our website to ensure you get the best experience.
Read more about our cookies here
Accept