Randomized Constructive Heuristics for the VRPTW: A Focus on Regret-k

Florian Rascoussier, Romain Billot, Lina Fahed, Christine Solnon

arXivarxiv/2607.22581Jun 8, 2026math.OCscore 0

The Vehicle Routing Problem with Time Windows (VRPTW) requires a fleet of capacitated vehicles to serve customers within strict time windows while minimizing total travel time. Constructive heuristics are fundamental for generating solutions and commonly serve as starting points for metaheuristics such as Iterated Local Search (ILS), Genetic Algorithms, and Ant Colony Optimization (ACO). This work studies three classical constructive heuristics - Nearest Neighbor, Best Insertion, and Regret-k - within a randomized, multi-start framework, a setting that remains largely under-explored despite…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2607.22581
curl -X POST /api/v1/records/arxiv/2607.22581/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.22581/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'