A new robust criterion for the vehicle routing problem with uncertain travel time

作者：Wu, Lei^*; Hifi, Mhand; Bederina, Hiba

来源：Computers & Industrial Engineering, 2017, 112: 607-615.

DOI：10.1016/j.cie.2017.05.029

• Robust optimization
• Worst case criterion
• Integer linear programming
• Measures of robustness
• Metaheuristic

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.

• 出版日期2017-10
• 单位中南财经政法大学