A two-phase branch-and-bound algorithm for solving vehicle routing problem with maximum duration constraint
An International Journal of Optimization and Control: Theories & Applications (IJOCTA) · 30.04.2026 · 16 (3) · 981
DOI: 10.36922/ijocta025480215 ↗Kurz gefasst
Fachartikel in der Zeitschrift An International Journal of Optimization and Control: Theories & Applications (IJOCTA), online erschienen am 30.04.2026. Verfasst von Asri Bekti Pratiwi und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Pratiwi, A. B., Salmah, S., & Endrayanto, I. (2026). A two-phase branch-and-bound algorithm for solving vehicle routing problem with maximum duration constraint. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 16(3), 981. https://doi.org/10.36922/ijocta025480215
Vancouver
Pratiwi AB, Salmah S, Endrayanto I. A two-phase branch-and-bound algorithm for solving vehicle routing problem with maximum duration constraint. An International Journal of Optimization and Control: Theories & Applications (IJOCTA). 2026;16(3):981. doi:10.36922/ijocta025480215
BibTeX
@article{Pratiwi2026,
author = {Pratiwi, Asri Bekti and Salmah, Salmah and Endrayanto, Irwan},
title = {A two-phase branch-and-bound algorithm for solving vehicle routing problem with maximum duration constraint},
journal = {An International Journal of Optimization and Control: Theories & Applications (IJOCTA)},
year = {2026},
volume = {16},
number = {3},
pages = {981},
doi = {10.36922/ijocta025480215}
}
EUVIMED