The electric vehicles powered by batteries can effectively reduce exhaust pollution and save environment harness cost, which has attracted attention and application in logistics field. The maximum driving range of an electric vehicle is limited by the capacity of the battery, and it is necessary to charge the vehicle at the charging station during driving. Secondly, the choice of a charging station will affect the distribution path of electric vehicles. The shortage of charging stations results in electric vehicles being forced to detour to the charging sites. Thirdly, the charge needed by the electric vehicle at the charging station is dynamic, which is related to the battery remaining capacity and the subsequent distribution route of the vehicle. The charge and battery status of the electric vehicle also directly affect the charging time. The electric vehicle routing problem is studied which aims to reduce the operational cost of logistics enterprises with the consideration of charging time and battery consumption cost. The problem is formulated as an integer programming model. The cost of battery loss is added to vehicle routing problem for the first time, and the distance traveled by vehicle in the state of deep discharge is taken as the optimization object. The battery charge rate used in this article is no longer a constant value, but a function related to the current state of the battery. The charging time depends not only on the battery status of the vehicle when it arrives at the charging station and the vehicle's subsequent delivery schedule, but also on the trade-off between the cost of charging time and the opportunity cost of deep discharge driving. A four-phase heuristic called MCWIGALNS is proposed to solve the problem. In the first phase, an initial routing plan is generated with a modified Clarke and Wright Saving heuristic, leading to the battery charging stations (BCSs) selection subproblem, which is then solved by the iterated greedy heuristic in the second phase. The iterated greedy heuristic algorithm first removes all the existing charging sites, and then arranges the lowest-cost charging strategy according to the existing path strategy. In the third phase, the vehicle routes resulting from the selection subproblem are determined by applying an adaptive large neighborhood search heuristic with several new neighborhood structures. Through the iterative of deleting part of the customer's point from the current path and re-putting it into the path according to the predetermined rule, a new solution is searched within the larger neighborhood scale. By exchanging the information of the charging and path strategy, the algorithm can make the feasible solution approach the optimal solution gradually in the iterative process. At the end of MCWIGALNS, the solution is further improved by a split procedure. The BCSs selection and the vehicle routing stages are alternated iteratively. Compared with the MIP solver of CPLEX on small-size instances, the MCWIGALNS can solve the problem within a shorter computing time and get reasonable solutions. Furthermore, a parameter analysis is systemically conducted for comparing two models. The one with the consideration of charge time and battery consumption cost is able to significantly reduce the total operation cost. MCWIGALNS searches the solution space more efficiently and produces better solutions than existing heuristic algorithms on the medium and large instances. To sum up, MCWIGALNS is a time-saving and stable algorithm to provide reference and help on the electric vehicle routing problem for green logistics.
GUO Fang, YANG Jun, YANG Chao
. Study on the Electric Vehicle Routing Problem in the Present of Charging Strategy and Battery Consumption[J]. Chinese Journal of Management Science, 2018
, 26(9)
: 106
-118
.
DOI: 10.16381/j.cnki.issn1003-207x.2018.09.011
[1] Chellaswamy C, Ramesh R, Rau C V. A supervisory control of a fuel free electric vehicle for green environment[C]//Proceedings of the 2012 International Conference on Emerging Trends in Electrical Engineering and Energy Management(ICETEEEM), Chennai, India, December 13-15, 2012.
[2] Green Car Report. Leasing and swapping electric car batteries. Will it happen[EB/OL]. http://www.greencarreports.com/.
[3] 艾学勇, 顾洁, 解大, 等. 电动汽车日充电曲线预测方法[J]. 电力系统及其自动化学报, 2013, 25(6):25-30.
[4] 何秋生, 徐磊, 吴雪雪. 锂电池充电技术综述[J]. 电源技术, 2013, 37(8):1464-1466.
[5] Erdogan S, Miller-Hooks E. A green vehicle routing problem[J]. Transportation Research Part E:Logistics and Transportation Review, 2012, 48(1):100-114.
[6] 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.
[7] Yang Jun, Sun Hao. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers and Operations Research, 2015, 55:217-232.
[8] 杨珺, 冯鹏祥, 孙昊,等.电动汽车物流配送系统的换电站选址与路径优化问题研究[J].中国管理科学,2015, 23(9):87-96.
[9] 符卓, 刘文, 邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 中国管理科学, 2017, 25(5):78-86.
[10] 李进, 傅培华, 李修琳, 等. 低碳环境下的车辆路径问题及禁忌搜索算法研究[J]. 中国管理科学, 2015, 23(10):98-106.
[11] 揭婉晨, 杨珺, 杨超. 多车型电动汽车车辆路径问题的分支定价算法研究[J]. 系统工程理论与实践, 2016, 36(7):1795-1805.
[12] Felipe A, Ortuno M 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.
[13] Desaulniers G, Errico F, Irnich S, et al. Exact algorithms for electric vehicle-routing problems with time windows[J]. Operations Research, 2016,64(6):1388-1405.
[14] Keskin M, Catay B. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C:Emerging Technologies, 2016, 65:111-127.
[15] Bruglieri M, Pezzella F, Pisacane O, et al. A variable neighborhood search branching for the electric vehicle routing problem with time windows[J]. Electronic Notes in Discrete Mathematics, 2015, 47:221-228.
[16] Penna P H V, Afsar H M, Prins C, et al. A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations[J]. IFAC-PapersOnLine, 2016, 49(12):955-960.
[17] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation science, 2006, 40(4):455-472.
[18] Adulyasak Y, Cordeau J F, Jans R. Optimization-based adaptive large neighborhood search for the production routing problem[J]. Transportation Science, 2012, 48(1):20-45.
[19] Hemmelmayr V C, Cordeau J F, Crainic T G. An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics[J]. Computers and operations research, 2012, 39(12):3215-3228.
[20] Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems[R].APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK,1997.
[21] Pisinger D, Ropke S. A general heuristic for vehicle routing problems[J]. Computers and Operations Research, 2007, 34(8):2403-2435.
[22] Augerat P, Belenguer J M, Benavent E, et al. Computational results with a branch and cut code for the capacitated vehicle routing problem[R]. Rapport de recherche-IMAG, 1995.
[23] Taillard E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2):278-285.
[24] Golden B L, Wasil E A, Kelly J P, et al. The impact of metaheuristics on solving the vehicle routing problem:algorithms, problem sets, and computational results[M]//Crainic T G, Laporte G. Fleet management and logistics. Boston, MA:Springer US, 1998:33-56.
