A new robust criterion for the vehicle routing problem with uncertain travel time
Résumé
This article investigates a new robust criterion for the vehicle routing problem with uncertainty on the travel time. The objective of the proposed criterion is to find a robust solution which displays better behaviour on a majority of scenarios, where each scenario represents a potential state of an uncertain event. In order to highlight the robustness of the proposed approach, the new robust criterion is compared with the classical robust criteria, such as best-case, worst-case and min-max deviation. Inspired from the mechanism developed by B. Roy for evaluating the robustness, this paper focuses on providing two robust conclusions for the new robust criterion: perfectly robust and pseudo robust. For the perfectly robust, the robust criterion is evaluated by using an exact method on a set of 480 small-scale instances generated from Solomon's benchmark instances. For the pseudo robust, the robust criterion is evaluated by using a metaheuristic on a set of 54 medium-scale and large-scale instances. The numerical results show that the new approach is able to produce the robust solutions in a majority of cases. (C) 2017 Elsevier Ltd. All rights reserved.