홈 › Papers

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.

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

Similar Papers 제목 키워드 기반