2018/10/09 by Anirudh Subramanyam, Subramanyam, Anirudh, Panagiotis P. Repoussis +3 · 1 citation
Engineering · Social Sciences · #Vehicle Routing Optimization Methods #Transportation Planning and Optimization #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.1810.04348
This paper studies robust variants of an extended model of the classical\nHeterogeneous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles\nwith different capacities, availabilities, fixed costs and routing costs is\nused to serve customers with uncertain demand. This model includes, as special\ncases, all variants of the HVRP studied in the literature with fixed and\nunlimited fleet sizes, accessibility restrictions at customer locations, as\nwell as multiple depots. Contrary to its deterministic counterpart, the goal of\nthe robust HVRP is to determine a minimum-cost set of routes and fleet\ncomposition that remains feasible for all demand realizations from a\npre-specified uncertainty set. To solve this problem, we develop robust\nversions of classical node- and edge-exchange neighborhoods that are commonly\nused in local search and establish that efficient evaluation of the local moves\ncan be achieved for five popular classes of uncertainty sets. The proposed\nlocal search is then incorporated in a modular fashion within two metaheuristic\nalgorithms to determine robust HVRP solutions. The quality of the metaheuristic\nsolutions is quantified using an integer programming model that provides lower\nbounds on the optimal solution. An extensive computational study on literature\nbenchmarks shows that the proposed methods allow us to obtain high quality\nrobust solutions for different uncertainty sets and with minor additional\neffort compared to deterministic solutions.\n