在能源、环境形势日益严重的今天,电动汽车因其清洁、节能的显著优势,已经逐步成为物流配送公司重要的新能源交通工具,优化物流配送网络成为电动汽车作为物流工具普及的一个重要问题。本文提出了电动汽车物流配送系统的换电站选址与配送路径优化问题,建立了整数规划模型,并设计禁忌搜索-改进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 high-quality 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.
[1] Kuby M, Lim S. The flow-refueling location problem for alternative-fuel vehicles [J]. Socio-Economic Planning Sciences, 2005, 39(2): 125-145.
[2] Kuby M, Lim S. Heuristic algorithms for sitting alternative-fuel stations using the Flow-Refueling Location Model [J]. European Journal of Operational Research, 2010, 204(1): 51-61.
[3] Wang Yingwei. An optimal location choice model for recreation-oriented scooter recharge stations [J]. Transportation Research Part D, 2007, 12(3): 231-237.
[4] Wang Yingwei. Locating battery exchange stations to serve tourism transport: A note [J]. Transportation Research Part D, 2008, 13(3): 193-197.
[5] Wang Yingwei, Chuah-Chih L. Locating road-vehicle refueling stations [J]. Transportation Research Part E, 2009, 45(5): 821-829.
[6] Mak H Y, Rong Ying, Shen Z J M. Infrastructure planning for electric vehicles with battery swapping[J]. Management Science, 2013,59(7):1557-1575.
[7] 任玉珑, 史乐峰, 张谦, 等. 电动汽车充电站最优分布和规模研究[J]. 电力系统自动化. 2011, 35(14): 53-57.
[8] 韩笑, 姜久春, 张微戈. 纯电动公交车充电站运营规划及仿真[J]. 微处理机, 2011, 32(2):88-91.
[9] 康继光,卫振林,程丹明,等.电动汽车充电模式与充电站建设研究.电力需求管理[J],2009,11(5):64-66.
[10] 徐凡, 俞国勤, 顾临峰,等. 电动汽车充电站布局规划浅析[J].华东电力, 2009, 37(10): 1678-1682.
[11] Artmeier A, Haselmayr J, Leucker M, et al. The optimal routing problem in the context of battery-powered electric vehicles//Proceedings of Second Bologna International Workshop on Constraint Reasoning and Optimization for Computational Sustainability, Bologna, Italy, June 15,2010.
[12] Conrad R G, Figliozzi M A. The recharing vehicle routing problem //Proceedings of the 2011 Reno Industrial Engineering Research Conference, Reno, USA, May 21-25,2011.
[13] Erdogan S, Miller-Hooks E. A green vehicle routing problem [J]. Transportation Research Part E, 2012, 48(1):100-114.
[14] Worley O, Klabjan D, Sweda T M. Simultaneous vehicle routing and charging station siting for commercial Electric Vehicles//Proceedings of International Electric Vehicle Conference (IEVC), Greenville, SC, USA,Mar 4-8, 2012.
[15] 刘华旭. 基于电动汽车技术特征的共同配送调度优化研究. 北京:北京交通大学,2012.
[16] Tuzun D, Burke L I. A two-phase tabu search approach to the location routing problem [J]. European Journal of Operational Research, 1999, 116(1): 87-99.
[17] Barreto S, Ferreira C, Paixao J, Santos B S. Using clustering analysis in a capacitated location-routing problem [J]. European Journal of Operational Research, 2007, 179(1): 968-977.
[18] Derbel H, Jarboui B, Hanafi S, Chabchoub H. Genetic algorithm with iterated local search for solving a location-routing problem [J]. Expert Systems with Application, 2012, 39(1): 2865-2871.
[19] Jarboui B, Derbel H, Hanafi S, et al. Variable neighborhood search for location routing [J]. Computers & Operations Research, 2013, 40(1): 47-57.
[20] 汪寿阳,赵秋红,夏国平. 集成物流管理系统中定位—运输路线安排问题的研究[J]. 管理科学学报, 2000, 3(2): 69-75.
[21] 张敏,杨超,杨珺,等. 危险品集成物流管理系统选址一选线模型研究[J].管理科学学报, 2008, 11(1): 59-67.
[22] 代颖,马祖军,朱道立,等. 震后应急物资配送的模糊动态定位—路径问题[J]. 管理科学学报, 2012, 15(7): 60-70.
[23] Clarke G, Wright J W. Scheduling of vehicles from a central depot to a number of delivery points [J]. Operations Research, 1964, 12(4): 568-581.
