A Set Cover Mapping Heuristic for Demand-Robust Fleet Size Vehicle Routing Problem with Time Windows and Compatibility Constraints
<|reference_start|>A Set Cover Mapping Heuristic for Demand-Robust Fleet Size Vehicle Routing Problem with Time Windows and Compatibility Constraints: We study the demand-robust fleet size vehicle routing problem with time windows and compatibility constraints. Unlike traditional robust optimization, which considers uncertainty in the data, demand-robust optimization considers uncertainty in which constraints must be satisfied. This paper is the first to solve a practical demand-robust optimization problem at large scale. We present an MILP formulation and also propose a heuristic that maps the problem to set cover in polynomial time. We show that under modest assumptions the relative difference in time complexity from a standard branch-and-bound algorithm to the proposed heuristic scales exponentially with the size of the problem. We evaluate our heuristic using a simulation case study on the Solomon benchmark instances for a variety of practical problem sizes, and compare with Gurobi. The empirical approximation ratio remains below 2.0.<|reference_end|>
@article{makansi2024a,
    title={A Set Cover Mapping Heuristic for Demand-Robust Fleet Size Vehicle
  Routing Problem with Time Windows and Compatibility Constraints},
    author={Jordan Makansi},
    journal={arXiv preprint arXiv:2406.07719},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.07719},
    primaryClass={eess.SY cs.SY}
}