A pickup and delivery problem with a fleet of electric vehicles
and a local energy production unit
M. Trottaa,∗ , C. Archettib , D. Feilletc and A. Quilliotaa Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, LIMOS 63000

Clermont-Ferrand, Francemanuel.trotta@emse.fr, quilliot@isima.fr
b ESSEC Business School, 3 Avenue Bernard Hirsch, 95000 Cergy, Francearchetti@essec.edu
c Mines de Saint-Etienne, Université Clermont-Auvergne, CNRS, UMR 6158 LIMOS, CentreCMP, F-13541 Gardanne Francedominique.feillet@mines-stetienne.fr∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 11, 2022
Keywords: pickup and delivery, electric vehicles, routing, energy production

1INTRODUCTION

We study a problem in which a set of capacitated Battery Electric Vehicles (BEVs) carry out
pickup and delivery operations with time windows constraints. The energy needed to recharge
the batteries of these vehicles is produced in a production unit (p.u.) that is also the depot ofthe vehicles. Additional batteries are available at the depot, where vehicles can go and swap
their batteries. Pickup and delivery operations must be planned over a time horizon divided into
periods. In each period it must be decided how much energy to give to the batteries that are atthe production unit. Also, if the energy produced is in excess of that required by the batteries,
this excess can be sold to the general network at a profit. If the energy required by the batteries
is greater than the energy produced, an unlimited amount of energy can be bought from thegeneral network. The objective of the problem is to plan vehicle routes to meet all pickup anddelivery demands while maximizing the profit that is made from the energy sold over the timehorizon.
We now briefly cite the relevant literature. Gonçalves et al. (2011) is one of the first papers
to study pickup and delivery problems with a mixed fleet of BEVs and Internal Combustion
Engine Vehicles. In Grandinetti et al. (2016) the electric Pickup and Delivery Problem withTime Windows (E-PDPTW) is studied. In the context of people transportation, one of the firststudies on Dial-a-Ride problems with electric vehicles is Chabrol et al. (2008). In Masmoudi
et al. (2018) the authors address the DARP with electric vehicles and a battery swapping policy.
Since our problem deals with the management of the energy produced, it can be seen as anintegrated problem sharing similarities with the Inventory Routing Problem (IRP) Dror et al.
(1985) or the Production Routing Problem (PRP) Adulyasak et al. (2014).
TRISTAN XI Symposium

Original abstract submittal

M. Trotta, C. Archetti, D.Feillet and A.Quilliot

22PROBLEM DESCRIPTION AND MILP MODELLINGThe problem can be formally described as follows. We have a complete directed graph G =(N , A), where N is the set of all nodes and A = {(i, j) : i, j ∈ N , i ̸= j} is the set of arcs
connecting each pair of nodes. The set of nodes N = {0, 2n + 1} ∪ P ∪ D consists of two copiesof the depot/production plant (0, 2n + 1) , the set of pickup nodes P = {1, . . . , n} and theset of delivery nodes D = {n + 1, . . . , 2n}. Every route begins and ends at the depot. There
are n transportation requests that have to be served over a planning horizon H of H periods{1, . . . , H}, each of duration τ . Periods can be interpreted as hours. The time horizon can beinterpreted as a whole day, and nothing happens between two time horizons. The state of thefleet/system at the end of the time horizon is exactly the state of the system at the beginningof the following time horizon. An arc (i, j) in set A has an associated non-negative energy cost
eij and a non-negative travel time τij . We assume that a fleet V of |V| = V homogeneous BEVs
is available at the depot, each of capacity Q. Vehicles can swap their batteries at the depot. Weassume that vehicles move at constant speed on the network. K batteries are available, each ofcapacity Qe . Among them, V batteries are located on the vehicles and K − V are located at thedepot. In each period h, ph is the energy produced, and it is available at the beginning of theperiod. If a battery is recharged during a period, it is available only at the end of the period.
Moreover, if a vehicles visits the depot to swap its battery, the latter can be recharged only fromthe following period on. Anyway, vehicles are allowed to visit the depot and wait for the end of
the period. The recharging rate is denoted by λ, and corresponds to the maximum quantity ofenergy that a battery can get in a period. The average state of charge of a battery is the same at
the beginning and at the end of the time horizon. We make this hypothesis because the idea isto define a sustainable/domestic production and consumption of the energy that vehicles use. Infact, the production unit can be imagined as a solar power plant. Every transportation request
specifies an origin si , a destination ti , a time window [ri , di ] and a demand qi , where this demandat each delivery is equal to qn+i = −qi . Each user node must be visited exactly once, while thedepot may be visited multiple times. Moreover, the depot must be visited at the beginning andat the end of each tour. The time window to visit the depot is set to [0, L], where L is length ofthe planning horizon (L = Hτ ). Moreover, we assume that the number of stops that a vehicle
can make to swap its battery is not limited. Vehicles are allowed to wait at any node in thegraph.
At the beginning of each period h, the energy ph must be split among the batteries locatedat the depot and the general network. If the energy is assigned to the general network there
is a profit. If in a period h the energy produced ph is not sufficient to recharge the batteries,additional energy can be bought from the general network. Obviously, the energy cannot bebought and sold to the general network in the same period h. The quantity of energy that canbe bought from the general network is not limited. The energy cost is different for each periodh: αh denotes the unitary selling cost and βh denotes the unitary purchasing cost (βh > αhsignificantly). The objective is to satisfy all transportation requests at maximal revenue. The
revenue is defined as the difference between the quantity of energy sold to and the quantity ofenergy bought from the general network. The side-effect is that the energy used by the vehicles
must be minimised.
We now introduce the notation used in the problem formulation. We call trip a couplet = (r, h) where r is a path between two nodes and h is the starting period of the path. All
trips are made up by paths where the depot is the starting and ending node. In what follows, we
make the simplifying hypothesis that trips can only start (end) at the beginning (at the end) of aperiod. We denote the set of trips with T . Let ϵit denote a parameter that is equal to 1 if request
i belongs to trip t and δth is equal to 1 if trip t is active during period h. Let cth denote the costof trip t in period h. Let γk denote the state of charge of battery k at the beginning of the time
horizon. For each period h, let the continuous variables sh denote the quantity of energy sold,bh the quantity of energy bought and lkh the state of charge of battery k at the end of period
TRISTAN XI Symposium

Original abstract submittal

M. Trotta, C. Archetti, D.Feillet and A.Quilliot

3h. Let akh denote the quantity of energy given to battery k in period h. Let ukh be a binarydecision variable equal to 1 if battery k is at the depot for an entire period h.
PLet xkt denote abinary decision variable equal to 1 if battery k is used in trip t. Note that if k∈K xkt = 0 thentrip t is not selected.
The formulation is as follows:XXmax
αh sh −βh bh(1)h∈Hh∈Hs.t.:Xh∈H(2)

akh ≤ λukhk ∈ K, h ∈ H(3)

lk0 = γk
XXlkH ≥
lk0k∈K(4)akh + sh = ph + bhk∈Kk∈K(5)k∈K

lkh = lkh−1 + akh −X

k ∈ K, h ∈ H(6)k ∈ K, h ∈ H(7)h∈H(8)k ∈ K, h ∈ H(9)i∈R(10)bh , sh ≥ 0h∈H(11)akh ≥ 0k ∈ K, h ∈ H(12)lkh ≥ 0k ∈ K, h ∈ H ∪ {0}(13)ukh ∈ {0, 1}

k ∈ K, h ∈ H(14)

xkt ∈ {0, 1}

k ∈ K, t ∈ T(15)

cth δth xktt∈Tlkh ≤ QeX
(1 − ukh ) ≤ Vk∈Kukh +X

δth xkt ≤ 1t∈TXt∈TϵitX

xkt ≥ 1k∈KConstraints (2) ensure that in each period, the energy produced is completely split among thebatteries and the general network. Constraints (3) impose a limit on the amount of energy given
to a battery in a period. Constraints (4) and (5) ensure that the average state of charge is thesame at the beginning and at the end of the time horizon. Constraints (6) model the change inbattery charge levels over time. Constraints (7) specify the upper bound for the battery charge
levels. Constraints (8) set an upper bound on the number of active vehicles. Constraints (9)ensure that trips are done only by active vehicles. Constraints (10) ensure that each request
belongs to at least one trip. Constraints (11)-(15) define the decision variables. Note that timeand capacity constraints are taken into account when the trips are generated.

3SOLUTION METHOD

Our problem can be seen as an integrated problem where both routing decisions and energy
management decisions have to be made. Formulation (1)-(15) is an integrated model based on
set T of trips. As formulation (1)-(15) suffers from the fact that the number of feasible trips
is exponential, we propose a heuristic algorithm which is based on a heuristic generation of asubset of feasible trips. Specifically, the solution method can be divided into three phases:
TRISTAN XI Symposium

Original abstract submittal

M. Trotta, C. Archetti, D.Feillet and A.Quilliot

4

1. generation of a subset T of trips
2. resolution of formulation (1)-(15) based on T
3. repair procedure.
As for phase 1, we use a randomized construction heuristic. Let h1 and h2 denote the startingand ending period of a trip t, respectively. For every possible pair (h1 , h2 ) we generate a poolof promising trips using a Greedy Randomized Adaptive Search Procedure (GRASP). Once wehave set T we solve formulation (1)-(15) over set T (phase 2). Due to constraints (10) multiple
trips that contain the same request may be selected and therefore a pair of nodes may be visited
more than once. This could be needed in order to satisfy all requests, as we do not generate all
possible trips. In such a case, solutions are repaired as follows (phase 3). If Ti is the subset of
selected trips that all contain request i, we leave i in the trips that corresponds to the maximum
saving of the distance travelled.
We tested our formulation on benchmark instances introduced in Li & Lim (2003) for thePickup and Delivery Problem with Time Windows (PDPTW). We adapted the instances bygenerating data on energy production and consumption, as well as on selling and buying pricefor energy. Detailed results of the solutions will be presented during the conference.

References
Adulyasak, Yossiri, Cordeau, Jean-François, & Jans, Raf. 2014. Optimization-Based Adaptive Large
Neighborhood Search for the Production Routing Problem. Transportation Science, 48(1), 20–45.
Chabrol, Michelle, Gourgand, Michel, & Leclaire, Patrice. 2008. A Coupling Metaheuristic-Simulation fora Dial-A-Ride Problem with Electric Autonomy Constraints in Real Traffic Conditions. In: Workshop
on Metaheuristics for Logistics and Vehicle Routing, EUIMEeting 2008.
Dror, M, Ball, M, & Golden, B. 1985. A computational comparison of algorithms for the inventory
routing problem. Annals of Operations Research, 4, 1–23.
Gonçalves, Frederico, Cardoso, Sonia R, Relvas, Susana, & Barbosa-Póvoa, APFD. 2011. Optimizationof a distribution network using electric vehicles: A VRP problem. Pages 18–20 of: Proceedings of theIO2011-15 Congresso da associação Portuguesa de Investigação Operacional, Coimbra, Portugal.
Grandinetti, Lucio, Guerriero, Francesca, Pezzella, Ferdinando, & Pisacane, Ornella. 2016. A pick-up
and delivery problem with time windows by electric vehicles. International Journal of Productivity andQuality Management, 18, 403–423.
Li, Haibing, & Lim, Andrew. 2003. A Metaheuristic for the Pickup and Delivery Problem with TimeWindows. International Journal on Artificial Intelligence Tools, 12(02), 173–186.
Masmoudi, Mohamed Amine, Hosny, Manar, Demir, Emrah, Genikomsakis, Konstantinos N., &Cheikhrouhou, Naoufel. 2018. The dial-a-ride problem with electric vehicles and battery swapping
stations. Transportation Research Part E: Logistics and Transportation Review, 118, 392–420.

TRISTAN XI Symposium

Original abstract submittal