# A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times

@article{Han2014ARS, title={A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times}, author={Jinil Han and Chungmok Lee and Sungsoo Park}, journal={Transp. Sci.}, year={2014}, volume={48}, pages={373-390} }

We consider a vehicle routing problem with uncertain travel times in which a penalty is incurred for each vehicle that exceeds a given time limit. A traditional stochastic programming approach would require precise knowledge of the underlying probability distributions of random data. In a novel approach presented here, we assume that only rough information on future travel times is available, leading to the multiple range forecasts of travel times and the probabilities of each range being… Expand

#### Figures, Tables, and Topics from this paper

#### 49 Citations

A Robust optimization approach for the Vehicle Routing problem with uncertain travel cost

- Engineering, Computer Science
- 2014 International Conference on Control, Decision and Information Technologies (CoDIT)
- 2014

A Genetic Algorithm is proposed for the RVRP considering a bounded set of discrete scenarios and the asymmetric arc costs on the transportation network and results indicate the GA produces good solutions and retrives the majority of proven optima in a moderate computational time. Expand

Discrete scenario-based optimization for the robust vehicle routing problem: The case of time windows under delay uncertainty

- Computer Science
- Comput. Ind. Eng.
- 2020

A robust model in which the uncertain travel time is related to a discrete set of scenarios: each scenario can be viewed as an observation of time required to complete a current route is presented. Expand

Heuristic Approaches for the Robust Vehicle Routing Problem

- Mathematics, Computer Science
- ISCO
- 2014

A mixed integer linear program is proposed to model the Robust Vehicle Routing Problem (RVRP) and some classical VRP heuristics are adapted to improve the obtained solutions and be integrated in a Greedy Randomized Adaptive Search Procedure (GRASP). Expand

Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios

- Mathematics, Computer Science
- Appl. Soft Comput.
- 2015

A robust version of the vehicle routing with uncertain travel times is studied, extending the Capacitated Vehicle Routing Problem (CVRP) to handle uncertain arc costs without resorting to probability distributions, giving the Robust VRP (RVRP). Expand

Dynamic routing with real-time traffic information

- Mathematics, Computer Science
- Oper. Res.
- 2019

An approximate dynamic programming algorithm based on a semi-infinite linear programming, which can be derived from a class of affine time-to-go approximation functions and generate lower bound only dependent on the expected duration and the description of support set of the stochastic time vectors is developed. Expand

Application of route flexibility in data-starved vehicle routing problem with time windows

- Computer Science
- 2016 IEEE Congress on Evolutionary Computation (CEC)
- 2016

An evolutionary algorithm is presented that in the absence of data on travel time uncertainty, provides a decision maker with a collection of solutions, each with a corresponding level of trade-off between total travel distance and solution robustness. Expand

Modelling and inference for the travel times in vehicle routing problems

- Computer Science
- 2019

The delay behaviour is studied and a novel model consisting of three parts: the delay occurrence rate, length and size is suggested, which results in an optimal solution that is more robust to delays. Expand

Integrated production and multiple trips vehicle routing with time windows and uncertain travel times

- Computer Science
- Comput. Oper. Res.
- 2019

A robustness approach is presented, known as “Elastic p-Robustness”, to deal with travel time variations when historical risk data are limited or non-existent, and a memetic algorithm with an effective search strategy is developed to solve the problem. Expand

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

- Mathematics, Computer Science
- Comput. Ind. Eng.
- 2017

This paper focuses on providing two robust conclusions for the new robust criterion: perfectly robust and pseudo robust, which is compared with the classical robust criteria, such as best-case, worst-case and min-max deviation. Expand

Robust vehicle routing problem with hard time windows under demand and travel time uncertainty

- Computer Science
- Comput. Oper. Res.
- 2018

The numerical results show that the proposed two-stage algorithm is able to find optimal solutions for small-sized instances and good-quality robust solutions for large-sized instance with little increase to the total travel distance and/or the number of vehicles used. Expand

#### References

SHOWING 1-10 OF 45 REFERENCES

A Vehicle Routing Problem with Stochastic Demand

- Mathematics, Computer Science
- Oper. Res.
- 1992

This work considers a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are stochastic, and proposes heuristics and algorithms to construct an a priori sequence among all customers of minimal expected total length. Expand

Robust vehicle routing problem with deadlines and travel time/demand uncertainty

- Computer Science
- J. Oper. Res. Soc.
- 2012

A Dantzig-Wolfe decomposition approach is proposed, which enables the uncertainty of the data to be encapsulated in the column generation subproblem, and a dynamic programming algorithm is proposed to solve the subproblem with data uncertainty. Expand

An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers

- Engineering, Computer Science
- Transp. Sci.
- 1995

The stochastic vehicle routing problem, where each customer has a known probability of presence and a random demand, is considered and is solved for the first time to optimality by means of an integer L-shaped method. Expand

A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty

- Economics
- 2008

In this paper we introduce a robust optimization approach to solve the Vehicle Routing Problem (VRP) with demand uncertainty. This approach yields routes that minimize transportation costs while… Expand

New optimality cuts for a single‐vehicle stochastic routing problem

- Computer Science, Mathematics
- Ann. Oper. Res.
- 1999

This investigation considers an application in which the demands are unknown prior to the creation of vehicle routes, but follow some known probability distribution, and solves a single‐vehicle problem with a relaxed IP. Expand

The Vehicle Routing Problem with Stochastic Demand and Duration Constraints

- Engineering, Computer Science
- Transp. Sci.
- 2010

This work shows that tour duration limits can effectively and efficiently be incorporated in solution approaches that build fixed, or a priori, tours for vehicle routing problems with stochastic demands by assuming that each tour must be duration feasible for all demand realizations. Expand

An Integer L-Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands

- Economics, Computer Science
- Oper. Res.
- 2002

An implementation of the IntegerL-shaped method for the exact solution of the capacitated vehicle routing problem with stochastic demands develops new lower bounds on the expected penalty for failures and provides variants of the optimality cuts for the SVRP that also hold at fractional solutions. Expand

Stochastic Vehicle Routing with Random Travel Times

- Engineering, Computer Science
- Transp. Sci.
- 2003

This work considers stochastic vehicle routing problems on a network with random travel and service times and provides bounds on optimal objective function values and conditions under which reductions to simpler models can be made. Expand

The vehicle scheduling problem with intermittent customer demands

- Computer Science
- Comput. Oper. Res.
- 1992

This research considers three alternative approaches for modelling the VSP with uncertain customer demands and proposes a simple but practical heuristic which captures the best of all three approaches in order to handle the dynamic nature of vehicle scheduling under uncertain demand. Expand

The Stochastic Vehicle Routing Problem for Minimum Unmet Demand

- Economics
- 2009

In this chapter, we are interested in routing vehicles to minimize unmet demand with uncertain demand and travel time parameters. Such a problem arises in situations with large demand or tight… Expand