考虑外协策略的电动车辆路径优化研究

doi:10.3778/j.issn.1002-8331.2205-0298

摘要/Abstract

摘要： 针对电动车充电时间较长，影响配送效率的缺点，提出一种考虑外协服务的混合配送策略，在电动车充电间隙将社会闲置运输资源整合到配送过程中。以最小化车辆固定成本、路径成本、时间窗惩罚成本和外协成本为目标，建立混合整数规划数学模型，并设计三阶段求解算法。结合重庆某物流企业进行实际配送案例分析，结果表明提出的外协策略能够减少总配送时间，有效地节约成本。

关键词: 电动车, 路径优化问题, 外协策略, 三阶段算法

Abstract: Aiming at the disadvantages of electric vehicles（EVs） charging time and distribution efficiency, a hybrid distribution strategy considering outsourcing service is proposed to integrate the social idle transportation resources into the distribution process during charging time. A novel mixed integer programming model is established with minimizing fixed cost, distance cost, time windows penalty cost, and outsourcing service cost. Then, a three-stage heuristic algorithm is designed to solve the proposed model. The case study related to a logistics enterprise in Chongqing indicates that the model and the algorithm are effective and applicable. Meanwhile, numerical experiments show that the proposed distribution strategy can reduce the total delivery time and effectively save costs.

Key words: electric vehicle, routing optimization problem, outsourcing strategy, three-stage algorithms

葛显龙, 邓诗言. 考虑外协策略的电动车辆路径优化研究[J]. 计算机工程与应用, 2023, 59(16): 316-323.

GE Xianlong, DENG Shiyan. Electric Vehicle Routing Problems Considering Outsourcing Strategy[J]. Computer Engineering and Applications, 2023, 59(16): 316-323.

参考文献

[1] ERDOĞAN S，MILLER-HOOKS E.A green vehicle routing problem[J].Transportation Research Part E，2011，48（1）：100-114.
[2] 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.
[3] GOEKE D，SCHNEIDER M.Routing a mixed fleet of electric and conventional vehicles[J].European Journal of Operational Research，2015，245（1）：81-99.
[4] 付朝晖，刘长石.生鲜电商配送的开放式时变车辆路径问题研究[J].计算机工程与应用，2021，57（1）：271-278.
FUC H，LIU C S.Research on open time-dependent vehicle routing problem of fresh food e-commerce distribution[J].Computer Engineering and Applications，2021，57（1）：271-278.
[5] 刘育良，陈淮莉.负载影响下纯电动汽车配送路径规划及充电策略[J].计算机应用，2020，40（10）：2831-2837.
LIU Y L，CHEN H L.Distribution path planning and charging strategy for pure electric vehicles with load constraint[J].Journal of Computer Applications，2020，40（10）：2831-2837.
[6] MONTOYA A，GUéRET C，MENDOZA J E，et al.The electric vehicle routing problem with nonlinear charging function[J].Transportation Research Part B，2017，103：87-110.
[7] 葛显龙，李祖伟，葛小波.考虑灵活充电策略的带时间窗物流配送路径优化研究[J].控制理论与应用，2020，37（6）：1293-1301.
GE X L，LI Z W，GE X B.Research on logistics distribution route optimization with time window considering flexible charging strategy[J].Control Theory & Applications，2020，37（6）：1293-1301.
[8] 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.
[9] LIM S，KUBY M.Heuristic algorithms for siting alternative-fuel stations using the flow-refueling location model[J].European Journal of Operational Research，2010，204（1）：51-61.
[10] YANG J，SUN H.Battery swap station location-routing problem with capacitated electric vehicles[J].Computers & Operations Research，2015，55：217-232.
[11] HOF J，SCHNEIDER M，GOEKE D.Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops[J].Transportation Research Part B：Methodological，2017，97（3）：102-112.
[12] ARCHETTI C，SAVELSBERGH M，SPERANZA M G.The vehicle routing problem with occasional drivers[J].European Journal of Operational Research，2016，254（2）：472-480.
[13] KAFLE N，LIN J.Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery[J].Transportation Research Part B，2017，99：62-82.
[14] CORTéS-MURCIA D L，PRODHON C，AFSAR H M.The electric vehicle routing problem with time windows，partial recharges and satellite customers[J].Transportation Research Part E，2019，130：184-206.
[15] 饶卫振，朱庆华，金淳，等.协作车辆路径成本分摊问题的B-T Shapley方法[J].管理科学学报，2019，22（1）：107-126.
RAO W Z，ZHU Q H，JIN C，et al.A binary tree shapely method for cost sharing of the collaborative vehicle routing problem[J].Journal of Management Science，2019，22（1）：107-126.
[16] SALANI M，VACCA I.Branch and price for the vehicle routing problem with discrete split deliveries and time windows[J].European Journal of Operational Research，2011，213（3）：470-477.
[17] BELFIORE P，YOSHIZAKI H.Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries[J].Computers & Industrial Engineering，2013，64（2）：589-601.
[18] CHEN P，GOLDEN B，WANG X Y，et al.A novel approach to solve the split delivery vehicle routing problem[J].International Transactions in Operational Research，2017，24：27-41.
[19] WANG H J，DU L J，MA S H.Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake[J].Transportation Research Part E：Logistics & Transportation Review，2014，69：160-179.
[20] 姚恩建，鲁楠，郎志峰，等.考虑节能的城市物流配送方案优化[J].北京交通大学学报，2015，39（6）：85-91.
YAO E J，LU N，LANG Z F，et al.Optimization of city logistics delivery plan with the objective of energy saving[J].Journal of Beijing Jiaotong University，2015，39（6）：85-91.
[21] 符卓，刘文，邱萌.带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J].中国管理科学，2017，25（5）：78-86.
FU Z，LIU W，QIU M.A tabu search algorithm for vehicle routing problem with soft time windows and spit deliveries by order[J].Chinese Journal of Management Science，2017，25（5）：78-86.
[22] 裴振兵，陈雪波.改进蚁群算法及在车辆运输调度中的应用[J].信息与控制，2015，44（6）：753-758.
PEI Z B，CHEN X B.Improved ant colony algorithm and its application in vehicle routing and scheduling problems[J].Information and Control，2015，44（6）：753-758.
[23] 葛显龙，竹自强.带软时间窗的电动车辆路径优化问题[J].工业工程与管理，2019，24（4）：96-104.
GE X L，ZHU Z Q.The electric vehicle routing problem with soft time window[J].Industrial Engineering and Management，2019，24（4）：96-104.
[24] 庞燕，罗华丽，夏扬坤.基于禁忌搜索算法的废弃家具回收车辆路径优化[J].计算机集成制造系统，2020，26（5）：1425-1433.
PANG Y，LUO L H，XIA Y K.Waste furniture recycling vehicles routing optimization based on tabu search algorithm[J].Computer Integrated Manufacturing System，2020，26（5）：1425-1433.
[25] 葛显龙，冉小芬.考虑时变交通拥堵的污染路径优化研究[J].工业工程与管理，2020，25（3）：75-85.
GE X L，RAN X F.Study on the optimization of pollution routing problem with time-varying traffic congestion[J].Industrial Engineering and Management，2020，25（3）：75-85.