[A-13] ITS

10:45 AM - 11:00 AM JST(1:45 AM - 2:00 AM UTC)Candidate for Academic Incentive AwardCareer Explorer

[A-13-09] AHRO-VRPTW: A Hybrid ALNS-VND Method Using Time-Window Slack Criticality for VRPTW

◎△YUZE LI¹, Tohgoroh Matsui¹ (1. Chubu University)

Keywords:

VRPTW,Metaheuristics

We propose AHRO-VRPTW, a hybrid metaheuristic for the Vehicle Routing Problem with Time Windows (VRPTW), which integrates Adaptive Large Neighborhood Search (ALNS) and Variable Neighborhood Descent (VND) through a Time-Window Slack Criticality (TWSC) measure. TWSC is a unified indicator that combines the narrowness of the time window, the remaining forward slack, and the insertion cost; it is applied as a weighting factor in both the destroy operators and the k-regret insertion, thereby directly reflecting the temporal structure inherent to VRPTW in the neighborhood operations. On the Solomon C1 benchmark, the proposed method reaches the best-known solution (BKS) on all 9 instances, achieving improvements of 7.1% over VND alone and 2.6% over ALNS alone, which confirms the effectiveness of the proposed approach.