EUVIMEDEUVIMED entdecken
Crossref

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

Asri Bekti Pratiwi, Salmah Salmah, Irwan Endrayanto

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →