Optimization Online


Arc routing with electric vehicles: dynamic charging and speed-dependent energy consumption

Elena Fernandez (elena.fernandez***at***uca.es)
Markus Leitner (m.leitner***at***vu.nl)
Ivana Ljubic (ivana.ljubic***at***essec.edu)
Mario Ruthmair (mario.ruthmair***at***univie.ac.at)

Abstract: Concerns about greenhouse gas emissions and government regulations foster the use of electric vehicles. Several recently published articles study the use of electric vehicles (EVs) in node-routing problems. In contrast, this article considers EVs in the context of arc routing while also addressing practically relevant aspects that have not been addressed sufficiently so far. These include dynamic charging of EVs while driving, speed-dependent energy consumption, and non-linear charging functions that depend on the battery state-of-charge and the charging time. A generic way of dealing with these aspects is introduced through the concept of an energy-indexed graph, which is used to derive an integer linear programming formulation and an exact solution framework based on branch-and-cut. Efficient construction heuristics and a local search for approximately solving large-scale instances are proposed. A computational study is performed on realistic problem instances. Besides analyzing the performance of all proposed methods, the obtained results also provide insights into strategic decisions related to the battery size and the amount of charging facilities.

Keywords: integer programming, arc routing, electric vehicles, speed-dependent energy consumption, non-linear charging, branch-and-cut, heuristics

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: University of Vienna, 7/2020

Download: [PDF]

Entry Submitted: 06/21/2019
Entry Accepted: 06/23/2019
Entry Last Modified: 07/17/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society