电动汽车物流配送系统的换电站选址与路径优化问题研究

Battery Exchange Station Location and Vehicle Routing Problem in Electric Vehicles Distribution System

在能源、环境形势日益严重的今天,电动汽车因其清洁、节能的显著优势,已经逐步成为物流配送公司重要的新能源交通工具,优化物流配送网络成为电动汽车作为物流工具普及的一个重要问题。本文提出了电动汽车物流配送系统的换电站选址与配送路径优化问题,建立了整数规划模型,并设计禁忌搜索-改进Clarke-Wright节省的两阶段启发式算法来求解该模型,提出了两种不同的禁忌准则,并且通过算例对这两种准则进行了比较。为了证明算法的有效性,还将该算法的结果同CPLEX的计算结果进行了比较,结果表明该算法更加有效和可靠。最后,对车辆的装载容量、电池续航里程和单位建站成本做敏感性分析,发现总成本随着装载容量的增加而显著降低,电池续航里程的提升有助于降低建站成本并降低目标函数值,而单位建站成本的增加可能减少建站个数,增加运输成本,但由于续航里程的限制,建站个数也可能保持不变。

With the increasingly serious situation of environmental protection and energy conservation,electric vehicles（EVs）are becoming an ideal transportation source of many logistic service companies for their outstanding cleanliness and energy efficiency.The battery exchange station location and vehicle routing problem（ELRP）are investigated in this paper.To solve the problem,an integer programming model is established and a two-stage hybrid algorithm for the new problem is proposed.The algorithm first locates battery exchange stations using tabu search with two different tabu criteria.It then determines the routing plan by using a modified Clarke-Wright saving heuristic.The computational experiments firstly compare the two different aspiration criteria.Extensive comparison experiments with CPLEX have been conducted on random generated instances and shows that our algorithm is more efficient to obtain highquality solutions.Finally,two sensitivity analyses on vehicle capacity and driving range are presented.The results show that the increase in vehicle capacity or the improvement in driving range is beneficial to cut down the total cost.Further more,the sensitivity analysis on the unit construction cost tells that increasing construction cost per station may also lead to less located stations and higher shipping cost number of located stations.