Metaheuristics for the Generalised Periodic Electric Vehicle Routing Problem - Université de Lorraine Access content directly
Book Section Year : 2019

Metaheuristics for the Generalised Periodic Electric Vehicle Routing Problem


This paper presents the Generalized Periodic Electric Vehicle Routing Problem, named GPEVRP, which is an extension of the Periodic Electric Vehicle Routing Problem (PEVRP) proposed in previous research. The GPEVRP is defined by a planning horizon of several periods typically “days”, with the constraints that each customer must be visited a required number of times, which must be related to a pattern, that is, a combination of days chosen among a set of allowed combinations of days, must be satisfied every time by its required demand, and that a limited fleet of electric vehicles (EVs) available each day at the depot must be respected. The EVs could be charged during their trips at the depot and in the available external charging stations. The objective of the GPEVRP is to minimize the total cost of routing and charging over the time horizon. We propose three metaheuristics to solve the problem. The first two methods are global approaches, allow solving simultaneously the planning level (pattern assignment) and the operational level (routing and charging). These methods are Large Neighbourhood Search (LNS) and Adaptive Large Neighbourhood Search (ALNS) for which we have proposed a new metric for the selection of patterns. The third method is a two-phase approach, called Multi-start Guided LNS, for which a perturbation phase changes the pattern and manages the planning level, and an intensification phase based on LNS optimizes the operational level and guides the perturbation through a memory. The results show that a simple global approach such as LNS leads to better results on a very constraining problem such as the problem of our study.
No file

Dates and versions

hal-02982806 , version 1 (29-10-2020)



Tayeb Oulad Kouider, Wahiba Ramdane Cherif-Khettaf, Ammar Oulamara. Metaheuristics for the Generalised Periodic Electric Vehicle Routing Problem. C. Paternina-Arboleda; S. Voß. Computational Logistics. ICCL 2019, 11756, springer, pp.219-232, 2019, Lecture Notes in Computer Science book series, ⟨10.1007/978-3-030-31140-7_14⟩. ⟨hal-02982806⟩
65 View
0 Download



Gmail Facebook X LinkedIn More