Exact column generation for the electrical vehicle scheduling problem
Axel Parmentier  1@  , Rafael Martinelli  2@  , Thibault Vidal  2@  
1 : Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique  (CERMICS)  -  Website
École des Ponts ParisTech (ENPC)
6 et 8 avenue Blaise Pascal Cité Descartes - Champs sur Marne 77455 Marne la Vallée Cedex 2 -  France
2 : Pontifical Catholic University of Rio de Janeiro  (PUC)
Rua Marques de Sao Vicente, 225-Gavea, Rio de Janeiro, 22451-900, Brazil -  Brazil

Green and electrical routing problems attract a growing attention. We consider the electrical Vehicle Scheduling Problem (eVSP). A set of trips must be operated by a fleet of electrical vehicles. Each trip is scheduled between an origin and a destination at a given time. Vehicles have a limited battery capacity. Inbetween two trips, a vehicle can go to a station to charge its battery. Costs are associated to vehicle use and distance traveled. The objective is to build a sequence of trips and recharge followed by each vehicle in order to operate all trips at minimum cost. We propose an exact column generation approach to the eVSP. Numerical benchmark on instances of the literature demonstrate the efficiency of our approach. Our pricing algorithm, and more precisely the way it encodes energy consumption information in an ad-hoc algebraic structure, plays a key role in the efficiency of our column generation. 

Online user: 1 RSS Feed