Arc Routing with Electric Vehicles: Dynamic Charging and Speed-Dependent Energy Consumption
研究了电动汽车在弧路径规划中的动态充电、速度依赖能耗和非线性充电问题，提出了基于能量索引图的整数规划模型和分支切割求解框架，以及大规模实例的启发式算法。
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 nonlinear charging functions that depend on the battery’s 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 a 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.