EUVIMEDEUVIMED entdecken
Crossref

Polyhedral theory for the stochastic vehicle routing problem with mixed and signed demands: Valid inequalities and recourse structure

Quang-Vinh Dang, Hoang-Viet Vu

Open Journal of Mathematical Sciences · 30.06.2026 · 10 · 1057-1070

DOI: 10.30538/oms2026.0331 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Open Journal of Mathematical Sciences, online erschienen am 30.06.2026. Verfasst von Quang-Vinh Dang und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Stochastic Vehicle Routing Problem (VRPSD) has been extensively studied under the assumption that all customer demands are non-negative random variables. In many real-world settings, however, demands may be signed: customers simultaneously act as sources (pickup, increasing vehicle load) and sinks (delivery, decreasing vehicle load), or excess inventory is returned to the depot. This paper introduces the Stochastic Vehicle Routing Problem with Mixed and Signed Demands (SVRP-MD), in which each customer \(i\) has a real-valued random demand \(\xi_i \in \mathbb{R}\), modelled as a net change in an abstract vehicle load-balance process under a reactive, signed detour-to-depot (DTD) recourse policy in which a violating visit triggers a depot round trip before service and the vehicle resumes at the same customer. Our contributions are: (i) a counterexample proving that the classical superadditivity of the recourse function fails when demands are signed; (ii) an incomparability result showing that the positive-part recourse neither upper- nor lower-bounds the signed recourse under the two-sided failure rule, together with a valid lower bound based on the absolute net demand that underlies our cut inequalities; (iii) a family of signed net-demand (SND) incumbent bounds, embedded in valid integer L-shaped optimality cuts in the extended \((x, \theta)\) space; (iv) a Jensen-type lower bound using a convex lower approximation of the recourse cost; and (v) a branch-and-cut sample-average bounding procedure with a Monte Carlo, confidence-based acceptance rule. Preliminary experiments suggest the SND cuts reduce the LP relaxation gap; the reported figures predate the protocol and bound corrections and are being regenerated.

Zitieren

APA

Dang, Q., & Vu, H. (2026). Polyhedral theory for the stochastic vehicle routing problem with mixed and signed demands: Valid inequalities and recourse structure. Open Journal of Mathematical Sciences, 10, 1057-1070. https://doi.org/10.30538/oms2026.0331

Vancouver

Dang Q, Vu H. Polyhedral theory for the stochastic vehicle routing problem with mixed and signed demands: Valid inequalities and recourse structure. Open Journal of Mathematical Sciences. 2026;10:1057-1070. doi:10.30538/oms2026.0331

BibTeX
@article{Dang2026,
  author = {Dang, Quang-Vinh and Vu, Hoang-Viet},
  title = {Polyhedral theory for the stochastic vehicle routing problem with mixed and signed demands: Valid inequalities and recourse structure},
  journal = {Open Journal of Mathematical Sciences},
  year = {2026},
  volume = {10},
  pages = {1057--1070},
  doi = {10.30538/oms2026.0331}
}
Kostenlos starten →