Electric vehicle scheduling and optimal charging problem: complexity, exact and heuristic approaches

Ons Sassi and Ammar Oulamara

International Journal of Production Research, 2017, vol. 55, issue 2, 519-535

Abstract: This paper deals with the Electric Vehicle (EV) Scheduling and Optimal Charging Problem. More precisely, given a fleet of EVs and Combustion Engine Vehicles (CVs), a set of tours to be processed by vehicles and a charging infrastructure, the problem aims to optimise the assignment of vehicles to tours and minimise the charging cost of EVs while considering several operational constraints mainly related to chargers, electricity grid and EVs driving range. We prove that the Electric Vehicle Scheduling and Charging Problem (EVSCP) is NP-hard in the ordinary sense. We provide a mixed-integer linear programming formulation to model the EVSCP and use CPLEX to solve small and medium instances. To solve large instances, we propose two heuristics: a Sequential Heuristic (SH) and a Global Heuristic (GH). The SH considers the EVs sequentially. To each EV, it assigns a set of tours and guarantees the feasibility of a charging schedule. Then, it generates an optimal charging schedule for this EV. However, the GH computes, in the first step, a feasible assignment of tours to all EVs. In the second step, it applies a global Min-Cost-Flow-based charging algorithm to minimise the charging cost of the EVs fleet. To evaluate the efficiency of our solving approaches, computational results on a large set of real and randomly generated test instances are reported and compared.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2016.1192695 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:55:y:2017:i:2:p:519-535

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2016.1192695

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().