Abstract: In order to reduce environmental impact or meet environmental regulations, logistics enterprises are converting their fleets of trucks to include electric vehicles. Due to the limited driving range, recharging infrastructures are involved in the routing plan of electric vehicles as well. The recharging infrastructure revisit refers to the circumstance that an electric vehicle returns to a previously visited recharging infrastructure. Due to the recharging infrastructure revisit, some constraints of classical Traveling Salesman Problem need to be modified, particularly the subtour elimination constraints. The paper focuses on the recharging infrastructure revisit, constructs a model of electric vehicleTraveling Salesman Problem with recharging infrastructure revisit which doesn’t have to estimate the count of revisits, and designs a modified ant colony optimization by introducing a method to distinguish the tour’s feasibility and a strategy to select and reuse infrastructures. The result shows that compared to the model without revisit, the proposed model with recharging infrastructure revisit is able to obtain the optimal solution under the lower driving range, and obtain a feasible route with the fewer recharging infrastructures by allowing them to provide the charge service repeatedly.

Key words: electric vehicle, recharging infrastructure revisit, traveling salesman problem

摘要： 出于减少环境危害和响应相关法规的考虑,物流企业开始逐步将运输车辆转变为电动汽车;而由于电动汽车的续航里程有限,对电动汽车的路径优化也将涉及充电设施。充电设施的“重入”是指电动汽车返回之前已经通过的充电设施进行充能的现象,它的存在需要改变经典旅行商问题模型中的“子回路约束”。本文聚焦于充电设施的“重入”,构建了一个无需预估充电设施重入次数上限的电动汽车旅行商问题模型,并通过引入路径可行性判别方法和增加充电设施选择与重复策略,设计了一种改进蚁群算法对问题进行求解。结果表明:与未考虑重入的模型相比,本文提出的考虑充电设施重入的模型能在电动汽车电池容量较低的情况下求出最优解,同时也能够使充电设施承担多次充电任务,从而在较少充电设施情况下依然能够得到可行的最优路径。

关键词: 电动汽车, 充电设施重入, 旅行商问题