EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

ETHC-VRC: Explicit Time-State Representation and Hybrid Constraint Handling for Time-Windowed Vehicle Routing Construction

Qing Ye, Gaoxian Peng, Xinyan Huang, Shan Liu, Di Hou

Algorithms · 29.10.2026 · 19 (11) · 935

DOI: 10.3390/a19110935 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithms, online erschienen am 29.10.2026. Verfasst von Qing Ye und 4 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Hunan Provincial Natural Science Foundation, Xiangtan Science and Technology Innovation Cultivation Project.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Learning-based routing for the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) must let a policy visit infeasible states in training, yet deploy routes that provably respect every time window under stated assumptions. In existing deep reinforcement learning (DRL) methods, however, time information serves a single constraint-handling mode, fixed for training and inference. We propose ETHC-VRC, a DRL construction method whose explicit time state is shared by the decoder context and the hard time-window mask, so that a policy trained with soft penalties can be decoded under this mask without retraining; its hybrid constraint strategy decodes each instance in both modes and keeps the lower-cost solution. On 20- to 100-node instances, greedy decoding solves 10,000 instances within seconds on a GPU at a lower hybrid cost than the greedily decoded DRL baselines (not significantly against MVMoE at 100 nodes). Sampling 1280 solutions per mode lowers it by another 3.8–4.9% at 0.07–0.32 s per instance, to within 2.1–4.3% of OR-Tools run for 10–120 s per instance and below OR-Tools at equal time. In zero-shot generalization across five scales, greedy decoding stays ahead of TPA-Reward on all 15 training–test combinations and of MVMoE, which has 5.3 times the parameters, on 8. A single model thus offers an explicit quality–latency trade-off, which we expect to suit both latency-critical and quality-critical logistics applications.

Förderung

  • Hunan Provincial Natural Science Foundation
  • Xiangtan Science and Technology Innovation Cultivation Project

Zitieren

APA

Ye, Q., Peng, G., Huang, X., Liu, S., & Hou, D. (2026). ETHC-VRC: Explicit Time-State Representation and Hybrid Constraint Handling for Time-Windowed Vehicle Routing Construction. Algorithms, 19(11), 935. https://doi.org/10.3390/a19110935

Vancouver

Ye Q, Peng G, Huang X, Liu S, Hou D. ETHC-VRC: Explicit Time-State Representation and Hybrid Constraint Handling for Time-Windowed Vehicle Routing Construction. Algorithms. 2026;19(11):935. doi:10.3390/a19110935

BibTeX
@article{Ye2026,
  author = {Ye, Qing and Peng, Gaoxian and Huang, Xinyan and Liu, Shan and Hou, Di},
  title = {ETHC-VRC: Explicit Time-State Representation and Hybrid Constraint Handling for Time-Windowed Vehicle Routing Construction},
  journal = {Algorithms},
  year = {2026},
  volume = {19},
  number = {11},
  pages = {935},
  doi = {10.3390/a19110935}
}
Kostenlos starten →