FROGER, Aurélien; JABALI, Ola; MENDOZA, Jorge E.; LAPORTE, Gilbert

Métadonnées

Licence d’utilisation du document

FROGER, Aurélien
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]

JABALI, Ola
Politecnico di Milano [Milan] [POLIMI]

MENDOZA, Jorge E.
HEC Montréal [HEC Montréal]

Langue

Communication dans un congrès

Ce document a été publié dans

SynchroTrans 2019 - 2nd International Workshop on Synchronisation in Transport, 2019-09-10, Nantes.

Résumé en anglais

In this research we focus on an electric vehicle routing problem in which 1) vehicles can be partially recharged between customer visits, 2) the quantity of energy recharged is a piecewise linear function of the time spent charging and of the current state of charge of the vehicle, and 3) the number of vehicles simultaneously charging at each charging station does not exceed the number of available chargers. The objective is to minimize the total time needed to serve all the customers. In this problem, resource synchronization takes place at nodes whose visit is a decision that depends on the sequence of customers served on the routes and on the objective. We propose two mixed integer linear programming formulations of the problem based either on charging stations replication and recharging paths. Solving the model using a commercial solver allows us to solve only small-sized instances. To tackle large-sized instances, we propose an hybrid algorithm that combines two components: an iterated local search algorithm responsible for generating a pool of high-quality routes and a branch-and-cut algorithm responsible for assembling a solution to the problem from the generated pool. We perform a comparison between four assembling strategies. Our computational results show that the strategies have different degrees of effectiveness and efficiency in addressing the capacity constraints of charging stations. < Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

A matheuristic algorithm to solve the electric vehicle routing problem with capacitated charging stations

Langue

Ce document a été publié dans

Résumé en anglais

URI

Origine

Unités de recherche