考虑充电设施重入的电动汽车旅行商问题研究

doi:10.12005/orms.2018.0035

摘要/Abstract

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

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

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

中图分类号:

F224.31

张鹏威, 李英. 考虑充电设施重入的电动汽车旅行商问题研究[J]. 运筹与管理, 2018, 27(2): 54-64.

ZHANG Peng-wei, LI Ying. Electric VehicleTraveling Salesman Problem with Recharging Infrastructure Revisit[J]. Operations Research and Management Science, 2018, 27(2): 54-64.

参考文献

[1] Bae S H, Sarkis J, Yoo C S. Greening transportation fleets: insights from a two-stage game theoretic model[J]. Transportation Research Part E: Logistics and Transportation Review, 2011, 47(6): 793-807.
[2] ćirovió G, Pamuar D, Božanió D. Green logistic vehicle routing problem: routing light delivery vehicles in urban areas using a neuro-fuzzy model[J]. Expert Systems with Applications, 2014, 41(9): 4245-4258.
[3] Erdoan S, Miller-Hooks E. A green vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48: 100-114.
[4] Jung J, Chow J Y J, Jayakrishnan R, Park, J Y. Stochastic dynamic itinerary interception refueling location problem with queue delay for electric taxi charging stations[J]. Transportation Research Part C: Emerging Technologies, 2014, 40: 123-142.
[5] Jung J, Jayakrishnan R. High-coverage point-to-point transit: electric vehicle operations[J]. Transportation Research Record, 2012, 329(2287): 44-53.
[6] Eggers F, Eggers F. Where have all the flowers gone? forecasting green trends in the automobile industry with a choice-based conjoint adoption model[J]. Technological Forecasting and Social Change, 2011, 78: 51-62.
[7] Conrad R G, Figliozzi M A. The recharging vehicle routing problem[A]. Doolen T, Aken E V. 2011 Industrial Engineering Research Conference[C]. 2011.
[8] Schneider M, Stenger A, Goeke D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520.
[9] Merting S, Schwan C, Strehler M. Routing of electric vehicles: constrained shortest path problems with resource recovering nodes[A]. Italiano G F, Schmidt M. 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems(ATMOS’ 15)[C]. Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. 29-41.
[10] Yang J, Sun H. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers & Operations Research, 2015, 55: 217-232.
[11] Lin C, Choy K L, Ho G T S, et al. Survey of green vehicle routing problem: past and future trends[J]. Expert Systems with Applications, 2014, 41(4): 1118-1138.
[12] Kuo Y. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J]. Computers & Industrial Engineering, 2010, 59: 157-165.
[13] Cinar D, Gakis K, Pardalos P M. Reduction of CO2 emissions in cumulative multi-trip vehicle routing problems with limited duration[J]. Environmental Modeling & Assessment, 2014, 20(4): 273-284.
[14] Wu X, He X, Yu G, Harmandayan A, Wang Y. Energy-optimal speed control for electric vehicles on signalized arterials[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(5): 2786-2796.
[15] Mak H Y, Rong Y, Shen Z J M. Infrastructure planning for electric vehicles with battery swapping[J]. Management Science, 2013, 59(7): 1557-1575.
[16] Felipe Á, OrtuonM T, Righini G, et al. A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 71: 111-128.
[17] Yang H, Yang S, XU Y, et al. Electric vehicle route optimization considering time-of-use electricity price by learnable partheno-genetic algorithm[J]. IEEE Transactions on Smart Grid, 2015, 6(2): 657-666.
[18] Wang Y W. Locating battery exchange stations to serve tourism transport: a note[J]. Transportation Research Part D: Transport and Environment, 2008, 13(3): 193-197.
[19] Wang Y W, Lin C C. Locating road-vehicle refueling stations[J]. Transportation Research Part E: Logistics and Transportation Review, 2009, 45(5): 821-829.
[20] Wang Y W, Lin C C. Locating multiple types of recharging stations for battery-powered electric vehicle transport[J]. Transportation Research Part E: Logistics and Transportation Review, 2013, 58: 76-87.
[21] 杨珺,冯鹏祥,孙昊,杨超.电动汽车物流配送系统的换电站选址与路径优化问题研究[J].中国管理科学,2015,23(9):87-95.
[22] Roberti R, Wen M. The electric traveling salesman problem with time windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 89: 32-52.
[23] Doppstadt C, Koberstein A, Vigo D. The hybrid electric vehicle-traveling salesman problem[J]. European Journal of Operational Research, 2016, 253(3): 825-842.
[24] Dorigo M, Maniezzo V, Colorni A. The ant system: optimization by a colony of cooperation agents[J]. IEEE Transactions on Systems Man & Cybernetics Part B: Cybernetics, 1996, 26(1): 29-41.
[25] Löfberg J. YALMIP: A toolbox for modeling and optimization in MATLAB[A]. 2004 IEEE International Symposium on the Computer Aided Control Systems Design[C]. 2004. 284-289.
[26] 揭婉晨,杨珺,陆坚毅.基于分支定价算法的电动汽车车辆路径问题[J].运筹与管理,2016,25(4):93-100.