Network flow problems with electric vehicles

• 成果类型: Article
• 署名作者: Pulyassary, Haripriya; Kollias, Kostas; Schild, Aaron; Shmoys, David; Wu, Manxi
• 署名单位: Cornell University; Alphabet Inc.; Google Incorporated; University of California System; University of California Berkeley
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02295-0
• 发表日期: 2026-03
• 页码: 489-520
• 关键词: Electric vehicle routing; network flow algorithms; Charge-augmented networks; routing problem; time; algorithms

摘要

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.