Network flow problems with electric vehicles

Haripriya Pulyassary

doi:10.1007/s10107-025-02295-0

Network flow problems with electric vehicles

2025-10-01

0

PRE

AI

H

Haripriya Pulyassary *

DOI：10.1007/s10107-025-02295-0

Original

Original request for help

Save

Abstract

En 中文

In this article, we introduce new models and algorithms that extend the classical network flow problems to the setting with electric vehicles (EV) that accommodate EV-specific constraints such as range limitations, charging strategies, and station capacities. Our work focuses on solving three key problems: single EV optimal charging strategy, maximum EV flow, and minimum-cost EV flow, each central to the efficient operation of EV routing systems. We establish the computational complexity of these problems, demonstrating their NP-hardness in general settings, while also identifying precise conditions under which they become polynomial-time solvable. For these tractable cases, we develop exact algorithms, and for the general settings, we design fully polynomial-time approximation schemes (FPTAS). We conduct numerical experiments using a network calibrated with real-world data. Although the conditions for polynomial time solvability do not hold in this setting, our algorithm still computes the optimal solution, which demonstrates its scalability and practical relevance.

Keywords:

Electric vehicle routing

Network flow algorithms

Charge-augmented networks

Network flow problems with electric vehicles

Abstract

Journal

Organization