ROADEF Conference 2011

I gave the following talk at the 2011 ROADEF conference, held in March in Saint-Etienne, abstract and slides are available here.

A dynamic approach for the vehicle routing problem with stochastic demands

Victor Pillaca,b, Christelle Guereta, Andrés L. Medagliab

a Équipe Systèmes Logistiques et de Production, IRCCyN
École des Mines de Nantes, B.P.20722, F-44307 Nantes Cedex 3, France
b Centro para la Optimización y Probabilidad Aplicada (COPA) & CEIBA
Universidad de los Andes, Cr1 Este No.19A-10 Bogotá, Colombia

The Vehicle Routing Problem with Stochastic Demands (VRPSD) is a variation of the classical Capacitated Vehicle Routing Problem (CVRP) in which the demand of each customer is modeled as a random variable and its realization is only known upon vehicle arrival to the customer site. Under this uncertain scenario, a possible outcome is that the demand of a customer ends up exceeding the remaining capacity of the vehicle, leading to a route failure. In this study we will focus on the single vehicle VRPSD in which the fleet is limited to one vehicle with finite capacity, that can execute various routes sequentially.

Traditional approaches for this problem involve a two-phase procedure~\cite{Cordeau07b,Mendoza09}. In the first phase, the problem is solved a-priori with the goal of finding a set of robust routes; while in the second phase routes failures are handled by means of recourse actions, such as forcing the vehicle to go back to the depot and restore its capacity, to then visit the client again and serve the remaining demand.

Recently, new approaches were developped based on the dynamic re-optimization of the vehicle routes \cite{Secomandi01,Secomandi09,Novoa09}. In this context the routing is no longer done a-priori but instead performed (and re-optimized) throughout the day: as soon as the vehicle becomes idle, a decision has to be taken regarding the next customer visit. The algorithms proposed by the aforementioned authors offer greater flexibility in comparison with two-stage approaches, allowing significant cost reductions. However, they assume discrete uniform demand distributions and have to be run every time a decision has to be taken, which can be time consuming for large instances.

The present work is based on an adaptation of an optimization framework developed initially for the vehicle routing problem with dynamic customers (i.e., customers appear while the vehicles are executing their routes).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s