带时间窗的电动汽车物流配送车辆路径问题研究
|
摘要
根据网上零售订单兼具"多品种、小批量、多频次、送货时间严格"等特点,从网上零售商的配送中心角度出发,提出了带软时间窗及充电站定位的电动汽车车辆路径问题,从配送中心角度分析了车辆使用数量与使用成本对总物流配送成本的影响,根据充电度数来计算充电成本的方式,增强了成本核算的精确性。并设计改进遗传算法进行求解,在染色体交叉操作中选择改进交叉算子,最大限度地保留优秀个体,加快寻找最优解的速度。最后通过算例验证了模型及算法的有效性。
According to the characteristics of online retail orders, such as large variety, small batch, high frequency, and tight delivery time, this paper proposes an electric vehicle routing problem with soft time window and charging station positioning from the perspective of online retailers' distribution center, analyzes the influence of the number of vehicle used and the utility cost on the total logistics distribution cost from the perspective of the distribution center, and calculates the charging cost according to the kilowatt-hours of power charged, thus enhancing the accuracy of the accounting of the distribution process. Next, it designes an improved genetic algorithm to solve the problem,and selects the improved crossover operator in the chromosome crossover operation so as to retain the good outcomes to the greatest extent and speed up the search for the optimal solution. Finally, a numerical example is given to verify the effectiveness of the model and algorithm proposed.
According to the characteristics of online retail orders, such as large variety, small batch, high frequency, and tight delivery time, this paper proposes an electric vehicle routing problem with soft time window and charging station positioning from the perspective of online retailers' distribution center, analyzes the influence of the number of vehicle used and the utility cost on the total logistics distribution cost from the perspective of the distribution center, and calculates the charging cost according to the kilowatt-hours of power charged, thus enhancing the accuracy of the accounting of the distribution process. Next, it designes an improved genetic algorithm to solve the problem,and selects the improved crossover operator in the chromosome crossover operation so as to retain the good outcomes to the greatest extent and speed up the search for the optimal solution. Finally, a numerical example is given to verify the effectiveness of the model and algorithm proposed.
引文
[1]Monthly gas statistics[EB/OL].Available:http:www.iea.org/statistics/monthlystatistics/monthlygasstatistics/,2009.
[2]北京市交通委员会,北京市环境保护局.北京市公安局公安交通管理局关于对部分机动车采取交通管理措施降低污染物排放的通告[EB/OL].Available:http:zfxxgk.beijing.gov.cn/columns/77/2/461498.html,2014-08-14.
[3]广州车展新能源汽车高峰论坛成功召开[EB/OL]. Available:http:www.auto-ccpit.org/hyxw/1646.jhtml,2014-11-20.
[4]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报,2005,19(1):124-130.
[5]杨文霞,郭海湘,杨娟,等.改进的扫描法求解单车场多车型车辆路径问题[J].物流技术,2010,29(8):50-53.
[6]朱奕丹,张杨.城市物流共同配送合理性探析[J].物流技术.2018,37(4):36-40.
[7]陈萍,黄厚宽,董兴业.求解多车型车辆路径问题的变邻域搜索算法[J].系统仿真学报,2011,23(9):1 945-1 950.
[8]揭婉晨,杨珺,杨超.多车型电动汽车车辆路径问题的分支定价算法研究[J].系统工程理论与实践,2016,36(7):1 795-1805.
[9]C Qi,Y Sun.An Improved Ant Colony Algorithm for VRPTW[A].International Conference on Computer Science and Software Engineering[C].2008.
[10]谢秉磊,安实,郭耀煌.随机车辆路径问题的多回路优化策略[J].系统工程理论与实践,2007,27(2):167-171.
[11]石建力.张锦.需求点随机的分批配送VRP模型与算法研究[J].控制与决策,2017,32(2):213-222.
[12]Daya Ram Gaura.Apurva Mudgalb, Rishi Ranjan Singh. Improved approximation algorithms for cumulative VRP with storhastic demands[J].Discrete Applied Mathematics,2018:176-189.
[13]M Schneider,A Stenger,D Goeke.The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations[J].IN FO RMS,2014,48(4):500-520.
[14]Siddiqi U F.Shiraishi Y,Sait S M,et al.LMulti-constrained route optimization for Electric Vehicles(EVs)using Particle Swarm Optimization(PSO)[A].International Conference on Intelligent Systems Design&Applications[C].2012.
[15]F Baouche,R Billot,R Trigui,et al.Electric Vehicle green routing with possible en-route recharging[A].17th International IEEE Conference on Intelligent Transportation Systems(ITSC)[C].2014.
[16]Y Kobayashi,N Kiyama,H Aoshima,et al.A route search method for electric vehicles in consideration of range and locations of charging stations[J].Intelligent Vehicles Symposium(Ⅳ),2011:920-925.
[17]Li-ying W,Yuan-bin S.Multiple Charging Station LocationRouting Problem with Time Window of Electric Vehicle[J].Journal of Engineering Science and Technology Review,2015,8(5):190-201.
[18]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.
[19]高升.基于电动汽车的带时间窗的路径优化问题研究[D].大连:大连海事大学,2015.
[20]朱颖.电动汽车智能充电服务优化模型的研究[D].北京:北京交通大学,2016.
[21]杨松平.电动汽车行驶路径优化及其价格响应特性分析[D].长沙:长沙理工大学,2014.
[2]北京市交通委员会,北京市环境保护局.北京市公安局公安交通管理局关于对部分机动车采取交通管理措施降低污染物排放的通告[EB/OL].Available:http:zfxxgk.beijing.gov.cn/columns/77/2/461498.html,2014-08-14.
[3]广州车展新能源汽车高峰论坛成功召开[EB/OL]. Available:http:www.auto-ccpit.org/hyxw/1646.jhtml,2014-11-20.
[4]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报,2005,19(1):124-130.
[5]杨文霞,郭海湘,杨娟,等.改进的扫描法求解单车场多车型车辆路径问题[J].物流技术,2010,29(8):50-53.
[6]朱奕丹,张杨.城市物流共同配送合理性探析[J].物流技术.2018,37(4):36-40.
[7]陈萍,黄厚宽,董兴业.求解多车型车辆路径问题的变邻域搜索算法[J].系统仿真学报,2011,23(9):1 945-1 950.
[8]揭婉晨,杨珺,杨超.多车型电动汽车车辆路径问题的分支定价算法研究[J].系统工程理论与实践,2016,36(7):1 795-1805.
[9]C Qi,Y Sun.An Improved Ant Colony Algorithm for VRPTW[A].International Conference on Computer Science and Software Engineering[C].2008.
[10]谢秉磊,安实,郭耀煌.随机车辆路径问题的多回路优化策略[J].系统工程理论与实践,2007,27(2):167-171.
[11]石建力.张锦.需求点随机的分批配送VRP模型与算法研究[J].控制与决策,2017,32(2):213-222.
[12]Daya Ram Gaura.Apurva Mudgalb, Rishi Ranjan Singh. Improved approximation algorithms for cumulative VRP with storhastic demands[J].Discrete Applied Mathematics,2018:176-189.
[13]M Schneider,A Stenger,D Goeke.The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations[J].IN FO RMS,2014,48(4):500-520.
[14]Siddiqi U F.Shiraishi Y,Sait S M,et al.LMulti-constrained route optimization for Electric Vehicles(EVs)using Particle Swarm Optimization(PSO)[A].International Conference on Intelligent Systems Design&Applications[C].2012.
[15]F Baouche,R Billot,R Trigui,et al.Electric Vehicle green routing with possible en-route recharging[A].17th International IEEE Conference on Intelligent Transportation Systems(ITSC)[C].2014.
[16]Y Kobayashi,N Kiyama,H Aoshima,et al.A route search method for electric vehicles in consideration of range and locations of charging stations[J].Intelligent Vehicles Symposium(Ⅳ),2011:920-925.
[17]Li-ying W,Yuan-bin S.Multiple Charging Station LocationRouting Problem with Time Window of Electric Vehicle[J].Journal of Engineering Science and Technology Review,2015,8(5):190-201.
[18]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.
[19]高升.基于电动汽车的带时间窗的路径优化问题研究[D].大连:大连海事大学,2015.
[20]朱颖.电动汽车智能充电服务优化模型的研究[D].北京:北京交通大学,2016.
[21]杨松平.电动汽车行驶路径优化及其价格响应特性分析[D].长沙:长沙理工大学,2014.