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

Computer Engineering and Applications计算机工程与应用2023，59（16）电动车作为一种新能源汽车，以“零排放”的优势在物流行业中备受青睐，尤其是在配送最后1 km中，与传统燃油货运车相比，电动车存在续航里程短的问题，因此在配送过程中会使用充电/换电的方式来提高电动车的续航里程，以完成配送任务。由于换电站的建设成本高昂，且车辆型号较多，电池规格不统一，目前物流企业车辆大多采用充电的方式补充电量。不同于传统燃油车的补能方式，电动车的充电时间较长，基于不同的充电技术和电池容量，通常在18 h之间。这会对后续货物配送的时效性造成严重影响，导致配送成本增加。因此，为了降低电动车辆充电时间对配送时效性的影响，研究考虑外协服务的电动车辆路径问题（electricvehicle routing problems considering outsourcing strategy，EVRPOS）具有重要的现实意义。在考虑利用社会闲散资源进行协同配送的情况下，研究了城市物流中电动车辆配送路径问题。EVRPOS由电动车辆路径问题（electric vehicle routing problems，EVRP）延伸而来，二者均属于组合优化领域的经典问题，也是NP-hard问题。已有学者从多方面对电动车配送路径优化问题进行了研究，取得了丰富的成果。大致分为以下几个方面：一是电动车路径优化问题。Erdoan和Miller-Hooks1考虑的绿色车辆路径问题（green vehiclerouting problem，G-VRP）是最早研究行驶路程中充电问题的论文之一，车队由替代燃油车辆（alternative fuelvehicle，AFV）组成，车辆可以访问充电站以扩大行驶里程，目的是最小化车辆总行驶距离。Schneider等2研究带时间窗的电动车辆路径问题（electric vehicle routingproblems with time windows，EVRPTW），对电动车访考虑外协策略的电动车辆路径优化研究葛显龙1，2，邓诗言11.重庆交通大学 经济与管理学院，重庆 4000742.重庆交通大学 智能物流网络重庆市重点实验室，重庆 400074摘要：针对电动车充电时间较长，影响配送效率的缺点，提出一种考虑外协服务的混合配送策略，在电动车充电间隙将社会闲置运输资源整合到配送过程中。以最小化车辆固定成本、路径成本、时间窗惩罚成本和外协成本为目标，建立混合整数规划数学模型，并设计三阶段求解算法。结合重庆某物流企业进行实际配送案例分析，结果表明提出的外协策略能够减少总配送时间，有效地节约成本。关键词：电动车；路径优化问题；外协策略；三阶段算法文献标志码：A中图分类号：TP18doi：10.3778/j.issn.1002-8331.2205-0298Electric Vehicle Routing Problems Considering Outsourcing StrategyGE Xianlong1，2,DENG Shiyan11.School of Economics and Management,Chongqing Jiaotong University,Chongqing 400074,China2.Chongqing Key Laboratory of Intelligent Logistics Network,Chongqing Jiaotong University,Chongqing 400074,ChinaAbstract：Aiming at the disadvantages of electric vehicles（EVs）charging time and distribution efficiency,a hybrid distri-bution strategy considering outsourcing service is proposed to integrate the social idle transportation resources into the dis-tribution process during charging time.A novel mixed integer programming model is established with minimizing fixedcost,distance cost,time windows penalty cost,and outsourcing service cost.Then,a three-stage heuristic algorithm isdesigned to solve the proposed model.The case study related to a logistics enterprise in Chongqing indicates that the modeland the algorithm are effective and applicable.Meanwhile,numerical experiments show that the proposed distributionstrategy can reduce the total delivery time and effectively save costs.Key words：electric vehicle;routing optimization problem;outsourcing strategy;three-stage algorithms基金项目：重庆市自然科学基金（KJCXZD2020031）。作者简介：葛显龙（1984），博士，教授，主要研究方向为网络配送与路径优化，E-mail：；邓诗言（1997），硕士研究生，主要研究方向为城市配送。收稿日期：2022-05-16修回日期：2022-10-13文章编号：1002-8331（2023）16-0316-083162023，59（16）问客户点的时间进行约束，提出一个双层目标函数，目的是最小化车辆数量和总行驶距离。Goeke和Schneide3提出了带有时间窗和混合车队的电动车辆路径问题，针对物流企业同时使用电动车和燃油车进行配送的情况，研究了不同目标函数下使用电动车和燃油车进行配送的成本，为企业的配送发展提供了一定的选择依据，具有较强的现实意义。付朝晖等4研究在时变网络下的生鲜产品配送问题，考虑货物新鲜度的变化，以改进蚁群算法分别对开放式和封闭式策略路径进行求解对比，结果表明该开放式策略更优。刘育良等5考虑了负载对能耗的影响，提出了一个现实的能耗模型，可以减少不可行路线的产生。二是电动车的充电策略。Montoya等6研究了非线性充电时间的EVRP，使用分段线性逼近来捕获充电过程的非线性充电行为。结果表明忽略充电函数的非线性性质可能会导致不可行的解决方案，此变体最大程度地缩短了总行驶距离和充电时间。葛显龙等7将充电量定义为决策变量，电动车的充电量由接下来的配送任务决定，而不用每次都充满电，此策略可以降低充电成本以及减少总的配送时间。Desaulniers等8提出四种不同的充电策略，包括单次充电、多次充电、部分充电和完全充电策略，研究表明多次充电和部分充电策略能够降低物流成本。三是电动汽车的充/换电站选址问题。Lim等9基于加油站的选址模型，提出了替代燃油车辆的流量-补能选址模型，并设计三种启发式算法有效求解该模型。Yang等10同时考虑了电动车路径规划和充电站选址问题（electric vehicles battery swap stationslocation routing problem，BSS-EV-LRP），以最小化配送和选址成本。Hof等11使用自适应可变邻域搜索算法来解决BSS-EV-LRP，改善了Yang等10求解的结果。根据以上分析，已有文献将研究重点放在了充电策略和电动汽车的充/换电站选址上，因较长充电时间而造成的配送效率低下问题没有得到解决。为了减轻充电时间造成的影响，一种可行的解决思路是利用社会闲散运输资源配送部分客户，以减少电动车辆因充电而暂停配送造成的时间损失。在实践中，随着滴滴共享模式向物流行业的渗透，通过分享车辆资源实现闲置车辆与货运需求协同的匹配，从而提高了资源的利用率。在学术上，目前已有学者对利用社会闲散资源提升配送效率的相关问题进行了研究。Archetti等12利用社会闲散运输资源配送一些位置较为偏远的客户，其余客户则由专用车队统一配送，有效降低了配送成本。Kafle等13研究了一个混合网络，用卡车将货物从仓库运输到中转点，利用行人或骑自行车的人完成配送任务的最后一步（或取货任务的第一步），避免了传统卡车在城市配送中的低效率。Corts-Murcia等14研究了电动车充电时进行混合配送的问题，在电动车充电间隙，电动车司机采用无人机和自行车等交通工具去配送部分客户，其余客户由司机驾驶电动车进行配送，有效缩短了总配送时间。绕卫振等15对多个企业协同配送过程的成本分摊策略进行了研究，提出了一种新的成本分摊方法，对利用社会闲散配送资源进行协作配送的成本分摊有一定的借鉴意义。已有文献中采用社会闲散运输资源和专用电动车队两种方式共同配送，采用行人、自行车和个人运输车辆等方式配送部分客户以提高效率，社会闲散运输资源在降低配送成本方面有足够的潜力。根据以上分析，本文提出一种外协策略以减轻充电时间对配送时效性的影响，即当电动车位于充电站时，利用社会闲散运输资源如达达配送等方式去配送部分客户。由社会闲散运输资源进行配送的客户称为外协客户。建立以最小化总成本为目标的电动车辆路径问题模型，设计三阶段算法进行求解。最后结合实例对本文提出的模型进行检验和分析。1问题描述存在外协服务的配送网络是一个复杂的物流系统，顾客的配送需求由企业电动车队和社会闲置运输资源共同完成。为界定研究范围，考虑在单一配送中心拥有同质电动车队背景下，客户相关配送信息均已知。规划电动车和社会闲散运输车辆服务所有客户的路径，使得：（1）电动车队的起始点均在配送中心；（2）电动车辆和社会闲散运输车辆速度相同且恒定，未在客户时间窗内将货物送达会产生惩罚成本；（3）每个顾客由电动车或外协方式服务一次；（4）电动车离开配送中心的载重量不超过最大负载；（5）电动车电量低于阈值需前往充电站充电。具体情况如图1所示。由图1（a）所示，8，9；10表示客户点的时间窗为8，9，配送车辆到达客户点的时间为10点。其中车辆达到充电站的时间为10点半，充电时间为1 h，因此离开充电站的时间为11点半。由于较长的充电时间，导致车辆到达客户点5和6时，已晚于其最晚开始服务时间。在图 1（b）中将客户点 5外协，电动车充满电后只服务客户 6，可以在规定的时间窗内将货物送至客户5和6处。显然（a）的时间窗惩罚成本比（b）高，（b）的总配送时间配送中心充电站客户点电动车配送路线外协配送路线8，9；9：30234659，10；1010：3011，12；12：4010，11；12111，12；125610，11；1128，9；9：309，10；10310：3041（a）方案1（b）方案2图1车辆路线图Fig.1Vehicle route map葛显龙，等：考虑外协策略的电动车辆路径优化研究317Computer Engineering and Applications计算机工程与应用2023，59（16）更少，但（b）可能带来更大的路径成本。因此，选择合适的外协客户在降低总配送成本和时间方面有很大的潜力。当不考虑使用外协服务进行配送时，问题就简化为了带时间窗的电动车辆路径问题（EVRPTW）。为了界定研究范围，在建立模型前提出以下假设：（1）车辆离开仓库或充电站时，电池是满电状态；（2）配送车辆的电量损耗和行驶距离成正比；（3）配送车辆的充电时长恒定；（4）每个客户都必须被访问，且只能被访问一次；（5）每个充电站可被多次访问；（6）电动车到达充电站时社会闲散运输资源已经到达充电站，社会闲散运输资源可以即时获取包裹后按照指定的目标进行配送；（7）电动车最多只能访问一次充电站；（8）每条路线最多只能存在一个外协客户。2外协客户选择策略使用外协的方式能否降低成本则取决于减少的时间窗惩罚成本和使用外协服务策略增加的额外配送费用。当减少的时间窗惩罚成本大于增加的额外配送费用，则能够降低总的配送成本。下面为外协客户的选择依据：(j-i-tijzij)lpu(c3-c1)dij，iF,jV（1）(j-lj)lpu(c3-c1)dij，iF,jV（2）约束（1）表示外协前到达客户j的时间晚于最晚时间窗，节约的时间为电动车到达客户j的时间减去外协车辆到达客户点的时间。约束（2）表示外协前到达客户j的时间早于最晚时间窗，则节约的时间为电动车到达客户j的时间减去最晚到达时间。每次访问充电站最多只能外协一个客户，因此选择满足约束（1）和（2）中节约成本最大的客户作为外协客户，以最小化总成本。3建立EVRPOS数学模型3.1符号说明为便于建模，所使用的符号如表1所示。3.2模型构建根据上述分析，以车辆固定成本、路径成本、时间窗惩罚成本以及外协成本最小化为优化目标，建立考虑外协服务的电动车路径优化模型。min(c1kKiVjV,ijxijkdij+c2kKiVx0ik+)iVpui(ti)+c3iFjVzijdij（3）jV,ijxijk+jFzij=1,iV,kK（4）jV,ijxijk1,iF,kK（5）jV,ijxijk-jV,ijxjik=0,iV,kK（6）iVx0ik|K,kK（7）ui-qixijk+Q(1-xijk)uj,i,jV,kK（8）ui-qozio+Q(2-xijk-zio)uj,iF,jV,oV,kK（9）uiQ,iV（10）i+(si+tij)xijk-lN+1(1-xijk)j,i,jV,kK（11）i+tijzij-lN+1(1-zij)j,iF,jV（12）i+ti+tijkxijk-(lN+1+ti)(1-xijk)j,i,jV,kK（13）o+(tio+so)zio+tijxijk-(lN+1+ti)(2-xijk-zio)j,iF,jV,oV,kK（14）pui(i)=epumax(ei-i,0)+lpumax(i-li,0),iV（15）yi-dijxijk+B(1-xijk)yj,iV,jV,kK（16）yi=B,iF（17）0yiB,iV（18）iFzij1,jV（19）类型集合参数变量符号VFVK0,N+1QBqisieilidijtijctepulpuc1c2c3Pciuiyixijkzij说明顾客集合充电站的集合顾客、充电站和仓库的集合电动车集合配送中心车辆最大装载量电池容量顾客i的需求顾客i的服务时间顾客i最早开始服务时间顾客i最晚开始服务时间节点i到j之间的距离车辆从节点i到j的行驶时间电池能量消耗系数在充电站的充电时间车辆早于时间窗到达产生的单位惩罚成本，元/min车辆晚于时间窗到达产生的单位惩罚成本，元/min电动车辆配送单位距离的运输成本，元/km每辆电动车辆的固定成本，元/辆外协配送单位距离的运输成本，元/km单次充电成本到达节点i的时间到达节点i时的剩余载重量到达节点i时的剩余电量如果车辆k从节点i访问了节点j为1，否则为0如果顾客j由外协服务为1，否则为0表1模型中的符号说明Table 1Symbol description in model3182023，59（16）iV,ijxijkiVzij,jF,kK（20）ui,i,yi0,iV（21）目标函数（3）最小化总成本，由电动车辆的路径成本、电动车辆的固定成本、电动车辆违背软时间窗的惩罚成本以及外协成本四部分构成。约束（4）表示必须对所有客户进行一次访问。约束（5）表示对充电站的访问不能超过一次。约束（6）表示电动车辆的流量平衡。车队规模由约束条件（7）表示。约束（8）表示节点的剩余负载。约束（9）表示位于充电站后访问节点的剩余负载，其中协作车辆拜访客户的需求影响剩余的负荷。车辆容量受到约束（10）的限制。对于每个节点的到达时间，必须考虑三种情况：约束（11）表示车辆路线中节点j的到达时间，约束（12）表示通过外协服务访问的顾客j的到达时间，约束（13）和（14）表示在充电站i之后访问的节点j的到达时间。约束（15）表示电动车违背软时间窗的惩罚成本。约束（16）表示节点处的电量约束。而约束（17）表示电动车在访问充电站后其电量更新为满电。约束（18）保证电量非负且不超过电池最大容量。约束条件（19）确定了每次到达充电站可以拜访的外协客户的最大数量。变量x和z之间的关系用约束条件（20）表示。约束（21）是变量的定义域。4设计算法求解EVRPOS问题属于NP-hard问题，精确算法16难以有效求解大规模配送问题，一般采用启发式算法17-22进行求解。考虑外协服务的电动车辆路径问题是在电动车辆路径问题上的拓展，主要区别在于需要在电动车辆配送路线上选择合适的外协客户进行剔除。因此算法思路是先规划电动车辆路径，再剔除外协客户得到所研究问题的解。第一阶段根据节约里程算法23得出初始EVRP解，此时所获得的EVRP解不够精确；第二阶段采用禁忌搜索算法进行搜索优化，提升EVRP解质量；第三阶段根据第二阶段优化后所获得的EVRP解，选择合适的外协客户进行剔除，重新生成配送路径，即考虑外协服务的电动车辆路径问题可行解。采用三阶段算法可以在短时间内有效获得EVRPOS的高质量解。4.1初始解产生（1）编码方法本文采用自然数编码的形式，“051374260”表示EVRP问题的一条配送路线，包含6个客户和1个充电站，其中0表示配送中心，7表示充电站点，其余表示客户。（2）初始解的设计首先采用节约里程算法，得到包含配送中心和所有客户点的TSP解，即使用一辆车从仓库出发，访问所有客户完成配送任务后返回仓库，此时并未考虑车辆的载重和电量约束。然后采用逐边修正算子24对当前TSP解进行优化得到新的TSP解。车辆的载重量有限，单一车辆无法装载所有货物进行配送。因此通过分车算子，将新的TSP解转化为包含多条路径的VRP解，即将一条包含所有客户的大路径分解成若干条子路径，每条子路径客户的需求之和均满足车辆载重约束，并采用逐边修正算子进行优化。计算子路径的耗电量，若超过最大电池容量则需插入充电站，从而得到EVRP问题的初始解（在上一步骤获得VRP解时，并未考虑电量约束，采用充电站插入算子提高路径的可行性）。4.2领域搜索采用禁忌搜索算法对第一阶段获得的解进行搜索优化。（1）邻域解的产生随机选择以下四种算子25来产生邻域解。逆序邻域搜索算子：选择路径中的部分连续点，逆反访问顺序。1-opt交换搜索算子：选择路径中的一个点插入到路径中的另一个位置。2-opt交换搜索算子：选择路径中的两个点，交换访问顺序。3-opt交换搜索算子：选择路径中的3个点，交换访问顺序。通过以上四种算子得到若干个候选解，其中适应度函数由电车车辆固定成本、行驶成本和惩罚成本构成，不考虑外协成本。将每代适应度函数最小的解加入禁忌列表，禁忌列表大小根据问题大小和邻域解规模确定。（2）算法终止准则当算法迭代1 000次后停止邻域搜索，输出优化后的EVRP解。4.3外协客户选择针对禁忌搜索得到的EVRP解，将位于充电站后访3 2 4 8 6 5 1邻域解7初始解8 4 2 3 6 5 173 2 4 8 6 5 1邻域解73 4 8 2 6 5 17初始解3 2 4 8 6 5 1邻域解73 2 7 8 6 5 14初始解3 2 4 8 6 5 1邻域解7初始解邻域解初始解4 2 3 8 6 5 174 2 3 8 6 5 174 2 5 8 6 3 17葛显龙，等：考虑外协策略的电动车辆路径优化研究319Computer Engineering and Applications计算机工程与应用2023，59（16）问且车辆晚于最晚时间窗进行服务的客户标记，如路径“051374260”，将客户点 4、2 和 6 标记，所标记的客户数量记为N。选择一个标记的客户点删除，访问顺序不改变，得到新的路径，如路径“05137420”，重新计算路径所消耗的电量。若低于电池总量，则取消外协，路径不改变；若高于电池总量，根据约束条件（1）和（2）计算出新路径相比于原路径所节约的成本。重复上述步骤，将所有标记的客户删除一遍，得到n(nN)个节约成本，将最大节约成本且为正对应的路径作为EVRPOS的解，否则取消外协，路径不变。4.4算法流程图本文设计的算法流程如图2所示。5案例分析5.1基础数据以重庆市某物流企业为例，选择重庆市的50个配送客户和12个常用充电站分别作为客户点和可用充电站集合，具体位置如图3所示。其中0为配送中心，150为客户点，5162为12个充电站点。其中电动车的电池容量62 kWh，载重量为1 800 kg，电动车的平均速度为33 km/h，单次充电时间为70 min，单次充电成本为100元，每个客户的固定服务时间为6 min，时间惩罚成本系数epu和lpu分别为0.2元/min和0.5元/min，车辆固定成本为180元/辆，单位行驶成本为0.75元/km，单位外协成本为1元/km。5.2求解结果在处理器为AMD，内存为8 GB的计算机上，使用MATLAB软件编写算法对模型进行求解。将算法运行10次后，取得到的最优解作为考虑外协服务的电动车路径问题最佳配送方案，结果如表2所示。将得到的配送方案转化到百度地图的实际路网中，可以得到电动车的实际运行路线，如图4所示。客户需求量客户地理位置车场地理位置TSP解车辆装载量VRP解续航距离第一阶段第二阶段第三阶段充电站位置EVRP解是否满足停止准则结束搜索输出结果是由当前解产生邻域解并确定一系列候选解否候选解是否优于历史最优解将其作为当前解并与最早进入禁忌表的对象做替换并更新最优状态是将非禁忌对象相对应的最佳解作为当前解，并用该对象替换最早进入禁忌表的对象否寻找合适的外协客户剔除新路径是否需要充电取消外协策略，路径不变选择节约成本最大的新路径作为EVRPOS的解是否图2算法流程图Fig.2Algorithm flow chart车辆编号12345配送路径0112933611253230151400282448184344594637364100273168597454216221700132151095940474850490012201932532634350行驶距离/km117.05128.91121.80131.33139.62行驶时间/min285.57303.36297.71312.00309.43表2考虑外协服务的电动车辆最佳配送方案Table 2Optimal distribution scheme of electric vehiclesconsidering outsourcing service图3配送网络图Fig.3Distribution network diagram3202023，59（16）根据运行结果可知，需要5辆电动车对50个客户进行服务，5辆车都在配送途中进行了充电操作。其中路线 1 原本的路线为 01129336123125323015140，客户点23作为外协点；路线3原本的路线为 02731685973945421622170，客户点39作为外协点；路线4原本的路线为013215109594038474850490，客户点38作为外协点。外协前整个配送过程需要的总配送成本为 2 048元，总配送时间为 1 505 min，外协后整个配送过程的成本为1 985元，配送时间为1 397 min，分别节约了63元的成本和108 min的时间。为验证算法的有效性，将节约里程和禁忌搜索构成的两阶段算法（CW-TS）分别与节约里程（CW）和禁忌搜索算法（TS）进行性能对比。分别在使用外协服务和不使用外协服务的情况下进行验证，使用上述基础数据，三种算法运算结果如表3所示。经过测算，在不考虑外协服务时，两阶段算法求解效果均优于CW和TS算法单独求解结果。两阶段算法得到的平均解成本比节约里程算法节约了18.9%，比禁忌搜索算法节约了24.9%。在考虑外协服务时，两阶段算法优势依旧明显。两阶段算法得到的平均解成本比节约里程算法节约了17.0%，比禁忌搜索算法节约了24.0%。因此所提出的三阶段算法能有效解决考虑外协服务的电动车辆路径问题，并优于传统的禁忌搜索算法。5.3灵敏度分析为了验证本文提出的外协策略能否有效降低成本，减少充电时间对路径规划的影响及其适用情况。本节固定了其他参数，对比分析不同时间窗惩罚系数和单位外协成本的EVRPOS的求解结果。将时间窗惩罚系数lpu设置为 0.5 元/min、0.7 元/min、0.9 元/min，在其他参数不变的情况下进行测试，求解结果如表4所示。时间窗惩罚系数成本越大，总配送成本越大，相应使用外协服务所节约的成本越大。在不同时间窗惩罚系数下，节约时间都是108 min，因为测试过程中路径并未发生改变，因此所节约的时间相同。将单位外协成本分别设置为0.75元/km、1.00元/km、1.25 元/km 进行测试，固定其他参数，求解结果如表 5所示。单位外协成本越大，使用外协策略节约的成本越小。在单位外协成本为0.75元/km和1.00元/km的情况下，存在3个外协客户，在单位外协成本为1.25元/km的情况下，只存在 2 个外协客户，因此所节约的时间为74 min。5.4不同规模实例验证为进一步验证算法的有效性和外协策略的普遍适用性，随机生成不同规模的客户实例，并以重庆市主城区的现有充电桩为背景进行仿真实验。采用本文模型和三阶段算法，分别对包含30个客户、40个客户和70个客户的实例进行求解，除客户本身需求和时间窗等参数有所不同，其余参数固定不变。三种不同规模实例求解结果如表6所示。在不同客户规模下，使用三阶段算法可以有效对模型进行求解，并且验证了本文提出的外协策略在不同情策略EVRPEVRPOSCW平均解2 4662 374最优解2 3822 306TS平均解2 5912 516最优解2 4942 458CW-TS平均解2 0732 029最优解2 0481 985表3三种算法性能比较Table 3Comparison of three algorithms单位：元lpu/(元/min)0.50.70.9外协前配送成本/元2 0482 1162 184外协后配送后成本/元1 9852 0292 072节约成本/元6387112节约时间/min108108108表4不同时间窗惩罚系数求解结果Table 4Solution results of penalty coefficients indifferent time windowsc3/(元/km)0.751.001.25外协前配送成本/元2 0482 0482 048外协后配送后成本/元1 9731 9852 016节约成本/元756332节约时间/min10810874表5不同单位外协成本求解结果Table 5Solution results of different outsourcing costs图4实际车辆运行路线Fig.4Actual vehicle route葛显龙，等：考虑外协策略的电动车辆路径优化研究321Computer Engineering and Applications计算机工程与应用2023，59（16）况下的可行性，因此提出的外协策略和三阶段算法能够求解不同规模的实例，具有一定的普适性。6结束语针对电动车配送中途停靠时间较长的缺点，通过考虑车辆行程限制、车辆载重限制、时间窗约束等因素，提出了考虑外协服务的电动车辆路径问题，设计了三阶段的启发式算法进行求解。对比分析了传统配送方案和考虑外协服务的配送方案，通过案例仿真，得出结论：在传统的EVRPTW问题的基础上，采用外协服务策略可以降低总配送时间及部分配送路径的成本。同时，本文对时间窗惩罚成本和单位外协成本等模型参数进行灵敏度分析，分别取3个不同的值进行测试。结果表明时间窗惩罚成本较高时，使用外协策略节约的成本更多；外协成本较低时，使用外协策略节约的时间和成本更多。通过三种算法对考虑外协服务和不考虑外协服务的情况分别进行求解，验证了所提出算法的有效性。本文忽略了外协车辆转运时间和操作成本，因此该模型更适用于城市中的末端小型配送问题。对于物流企业管理者，在配送客户较多、时间窗较窄的情况下，采用外协服务策略，选择合适的外协客户可以降低配送成本，缩短总配送时间。未来的研究可以从以下方面进行拓展：（1）放宽每条路线最多只存在一个外协客户的条件，可以考虑每条路线多个客户外协的情况。（2）现实配送中访问充电站不一定要将电量充满，在后续的研究中可以考虑采用部分充电策略。参考文献：1 ERDOAN S，MILLER-HOOKS E.A green vehicle routingproblemJ.Transportation Research Part E，2011，48（1）：100-114.2 SCHNEIDER M，STENGER A，GOEKE D.The electricvehicle-routing problem with time windows and rechargingstationsJ.Transportation Science，2014，48（4）：500-520.3 GOEKE D，SCHNEIDER M.Routing a mixed fleet ofelectric and conventional vehiclesJ.European Journal ofOperational Research，2015，245（1）：81-99.4 付朝晖，刘长石.生鲜电商配送的开放式时变车辆路径问题研究J.计算机工程与应用，2021，57（1）：271-278.FUC H，LIU C S.Research on open time-dependent vehiclerouting problem of fresh food e-commerce distributionJ.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 charg-ing strategy for pure electric vehicles with load constraintJ.Journal of Computer Applications，2020，40（10）：2831-2837.6 MONTOYA A，GURET C，MENDOZA J E，et al.Theelectric vehicle routing problem with nonlinear chargingfunctionJ.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 distri-bution route optimization with time window consideringflexible charging strategyJ.Control Theory&Applica-tions，2020，37（6）：1293-1301.8 DESAULNIERS G，ERRICO F，IRNICH S，et al.Exact algo-rithms for electric vehicle-routing problems with timewindowsJ.Operations Research，2016，64（6）：1388-1405.9 LIM S，KUBY M.Heuristic algorithms for siting alterna-tive-fuel stations using the flow-refueling location modelJ.European Journal of Operational Research，2010，204（1）：51-61.10 YANG J，SUN H.Battery swap station location-routingproblem with capacitated electric vehiclesJ.Computers&Operations Research，2015，55：217-232.11 HOF J，SCHNEIDER M，GOEKE D.Solving the batteryswap station location-routing problem with capacitatedelectric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stopsJ.TransportationResearch Part B：Methodological，2017，97（3）：102-112.12 ARCHETTI C，SAVELSBERGH M，SPERANZA M G.The vehicle routing problem with occasional driversJ.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 deliveryJ.Transportation Research Part B，2017，99：62-82.14 CORTS-MURCIA D L，PRODHON C，AFSAR H M.Theelectric vehicle routing problem with time windows，partial recharges and satellite customersJ.TransportationResearch 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客户数量304070外协前配送成本/元1 2491 8122 833外协后配送后成本/元1 2221 7602 736节约成本/元275297节约时间/min5189160表6不同客户规模求解结果Table 6Solution results of different customer sizes3222023，59（16）method for cost sharing of the collaborative vehiclerouting problemJ.Journal of Management Science，2019，22（1）：107-126.16 SALANI M，VACCA I.Branch and price for the vehiclerouting