EUVIMEDEUVIMED entdecken
Crossref

Vehicle Routing Problem With Time Windows—New Valid Inequalities From Polar Duality

Yogesh Kumar Agarwal, Prahalad Venkateshan

Networks · 2026-01 · 87 (1) · 3-22

DOI: 10.1002/net.70005 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Networks, online erschienen am 15.09.2025. Verfasst von Yogesh Kumar Agarwal und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 36 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The vehicle routing problem with time windows is a well‐researched problem in literature. We study the 2‐index flow formulation for the problem and propose a relatively little‐used approach of polar duality/local cuts to compute new general valid inequalities for the problem. Our method of applying polar duality is quite distinct from and complimentary to an earlier attempt of applying the same idea to this problem and produces significantly better results on instances with tight time windows. On almost all 25‐customer Solomon instances with tight time windows, our approach is capable of producing very strong lower bounds that are close to 100% of the optimal solution within reasonable computing time. On larger instances too the lower bounds are significantly better than those reported in the literature. We also present a new version of the previously proposed ‐path inequalities that are easy to compute as well as effective. These inequalities also lead to a substantial improvement in lower bounds and solution times for some classes of instances. Computational tests performed on benchmark instances indicate significant improvement in computing time and decrease in the number of nodes in the branch‐and‐bound tree as compared to extant methods that employ the flow formulation for the problem.

Zitieren

APA

Agarwal, Y. K., & Venkateshan, P. (2026). Vehicle Routing Problem With Time Windows—New Valid Inequalities From Polar Duality. Networks, 87(1), 3-22. https://doi.org/10.1002/net.70005

Vancouver

Agarwal YK, Venkateshan P. Vehicle Routing Problem With Time Windows—New Valid Inequalities From Polar Duality. Networks. 2026;87(1):3-22. doi:10.1002/net.70005

BibTeX
@article{Agarwal2026,
  author = {Agarwal, Yogesh Kumar and Venkateshan, Prahalad},
  title = {Vehicle Routing Problem With Time Windows—New Valid Inequalities From Polar Duality},
  journal = {Networks},
  year = {2026},
  volume = {87},
  number = {1},
  pages = {3--22},
  doi = {10.1002/net.70005}
}
Kostenlos starten →