Polyhedral theory for the stochastic vehicle routing problem with mixed and signed demands: Valid inequalities and recourse structure
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.
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}
}
EUVIMED