考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究

郭 放，杨 珺，杨 超

(1.郑州大学管理工程学院，河南 郑州 450001；2.华中科技大学管理学院，湖北 武汉 430074)

1 引言

城市内小件货物送货上门服务处于物流环节的最末端。受到交通、人员以及环境的影响，市内配送环节产生的服务成本占据物流环节总成本的35%-60%[1]。为提高物流配送效率抢占末端配送市场，物流企业和学者在服务模式以及服务效率等方面进行了诸多尝试。陈义友等[2]研究了顾客差异化选择对自提点选址的影响。符卓等[3]研究了顾客需求可依据订单拆分情形下的物流车辆路径问题。此外，配送车辆的多样性、服务路径选择、人车匹配策略以及服务时间差异化等因素都会影响物流运营成本。因此，高效的物流配送服务需要物流专员、配送车辆和顾客三方协作完成。在熟悉顾客点周边的环境的情况下，物流专员能够快速准确地找到配送地址与合适的停车点，甚至能够熟悉顾客点周边交通状况从而避开拥堵的路段。物流专员的服务时间存在差异，由此带来的经济效益也愈加受到物流企业的重视。除差异化服务时间以外，物流专员指派策略还与配送车辆载重量、行驶成本和顾客位置等多种因素相互影响。相对于大型配送车辆，小型配送车辆较低的可变成本使其在路径选择方面更加灵活。但是，受到载重量较小的限制，物流企业需要安排更多数目的车辆与人员才能够满足服务需求。另一方面，具备较大载重量的车型可以满足更多顾客点的服务需求。车辆服务路径的增加可能会导致物流配送人员对配送区域和配送顾客不熟悉，增加了整体服务时间成本。由此可见，统筹安排物流专员、配送车辆和顾客三者的匹配工作，有助于物流企业提高人员、物流车辆、服务时间等资源的利用效率，降低运营成本。

近几年来，国内外学者分别从车队规模、车型选择和差异化服务时间等方面拓展了对物流路径优化问题的研究。一部分学者探讨了多车型车辆路径问题(HVRP)，Golden等[4]研究了考虑车队规模与车型选择的车辆路径问题，在其研究中多车型通过不同的载重量体现。Liu和Shen[5]基于不同型号车辆的行驶成本不同而载重量相同的假设，探讨了时间窗约束下的HVRP问题。Taillard[6]结合了禁忌搜索和列生成算法的优势，采用混合算法解决了兼顾可变成本和不同载重量的多车型车辆路径问题。Salhi等[7]在多车型车辆路径问题的基础上进一步探究了载货返程情形下的服务策略。另一部分学者研究了考虑差异化服务成本的车辆路径问题(VRP)。差异化服务相关研究集中于小件商品的物流配送领域，服务的差异性通常表现为服务成本不同。Zhong等[8]采用差异化服务成本体现物流服务专员对不同服务对象的熟悉程度，通过允许跨区域服务实现路径策略的灵活性。Schneider等[9-11]在VRP问题的研究中引入了配送人员个性化服务时间的概念。服务时间的差异通过熟悉因子σis体现，熟悉因子表示熟悉服务对象i的物流专员s(以下简称为熟悉专员)相对于对服务对象完全陌生的物流专员(以下简称为陌生专员)可节约的服务时间百分比。例如，熟悉因子σis=0.2的时候，熟悉专员的服务时间降低为陌生专员的80%。Sungur等[12]采用补偿随机规划和鲁棒优化分别对顾客点和服务时间的不确定性进行研究。Schneide等[13]在时间窗约束下研究服务时间差异化的车辆路径问题。上述文献从不同角度分别研究了考虑多车型或差异化服务时间的车辆路径问题，鲜有文献涉及关于协调物流专员、配送车辆和顾客三方匹配策略的研究。

另一方面，零排放的特点使得电动汽车非常适合城市良性发展的需求，促使其在城市物流配送行业中得到关注与应用[14]。国家各部门相继出台了一系列政策法规推进电动物流汽车产业和配套服务设施快速发展，为电动汽车在物流配送行业的普及提供了有力保障。电动物流车辆行驶距离受电池容量约束，电量不足时需要前往充电站点通过充电模式补充电量。如何科学地规划电动汽车服务路径与充电策略，优化电动汽车物流与服务网络成为了近来的研究热点问题。Erdogan和Miller-Hooks[15]最早提出绿色车辆路径问题(Green Vehicle Routing Problem，GVRP)，建立起以累计行驶距离最短为优化目标的混合整数规划模型。Schneider等[16-17]研究了时间窗与允许在途充电的电动汽车路径优化问题，并在文中采用变邻域搜索和禁忌搜索相结合的混合启发式算法对上述问题进行求解。杨珺等[18]研究电动汽车物流配送网络的设施选址和配送路径优化问题，提出了禁忌搜索和改进节约算法相结合的两阶段启发式算法。Bruglieri等[19]将电动汽车在服务站点的充电量作为决策变量，研究了带时间窗约束且允许在途充电的电动汽车路径问题。研究结果发现在带时间窗的前提下灵活可变的充电策略能够以较低的资金投入为顾客提供更加高效率的服务。

近期，部分学者将多车型与电动物流汽车车辆路径问题结合起来进行研究。揭婉晨等[20]和Penna等[21]研究了含时间窗的多车型电动汽车车辆路径问题(E-HVRPTW)，其中揭婉晨等[20]运用基于列生成的分支定价算法求解该问题的最优解，并提出了两种加速策略优化算法求解效率。Hiermann等[22]根据不同车型电动汽车的能源消耗和载重量等性能的差异性，将电动物流车队的车辆数和车型选择作为优化对象。

本文与已有研究的主要区别在于考虑了物流专员、配送车辆和服务对象三方协调匹配策略。研究了将上述三方指派与匹配策略作为优化对象的多车型电动汽车配送路径问题。随后，本文提出了基于改进节约算法、混合遗传算法以及禁忌搜索算法的混合启发式算法MCWGATS。采用CPLEX求解小规模算例并将其结果与MCWGATS算法的计算结果进行比较，证实了算法的有效性。最后，分析多车型与差异化服务时间对运营成本的影响。

2 问题描述及数学模型

2.1 问题描述

2.2 基础模型

基于上述条件， 数学模型如下：

(1)

(2)

(3)

∀h∈V{o,o′},k∈K

(4)

(5)

(6)

(7)

(8)

(9)

(10)

∀k∈K,s∈S,i∈V{o′}

(11)

uhk≤ugk-qhxghk+Uk(1-xghk)

∀h∈V{o},g∈V{o′},g≠h,k∈K

(12)

uok≤Uk∀k∈K

(13)

uhk≥0≤∀k∈K,h∈V{o′}

(14)

∀h∈V{o},g∈V{o′},g≠h,k∈K

(15)

(16)

(17)

(18)

(19)

(20)

xghk,ysk,zisk∈{0,1} ∀h∈V{o},g∈V{o′},k∈K,j∈J,s∈S

(21)

3 启发式算法MCWGATS

本节采用启发式算法MCWGATS求解考虑物流专员个性化服务时间的多车型电动汽车路径与充电策略问题。MCWGATS主要由改进节约算法(MCWS)、混合遗传算法(HGA)和禁忌搜索(TS)组成。

3.1 初始选址

依次将各备选位置作为圆心，标记其周围Qk/2距离内的顾客点(此处k为最大行驶距离最短的车型)。将所有备选点根据其标记的顾客数目按照由高到低的顺序排列在集合G中，随后将集合G的前n个点添加到站点集合S0。

3.2 路径预处理

步骤1：为每一个等待服务的顾客点i生成一条对应的线路(o-i-o)，其中o为配送中心。

步骤2：核查路径(o-i-o)是否满足最大行驶里程约束。本节假设车辆离开配送中心时电池状态为满电量Qk，doi+dio≤Qk表示此路径符合行驶里程约束，可移入可行路径集合FR。反之则移入不可行路径集合IR。

本文设定预处理阶段为一位顾客提供服务的车辆最多可在往返途中各充电一次。在执行上述步骤1-4后依旧存在不符合行驶里程约束的路径，则视为选址方案存在不可行路线。

3.3 服务路径优化

首先对本节涉及的概念进行介绍：

(c)路径节约值：找出可行线路中与o点相连的毗邻点，计算任意连接不同路径上两个毗邻点的savekk′值。假设点i和j分别是路径r1和r2上与o点相连的毗邻点。r1、r2和r3的路径长度分别为s1、s2和s3。其中,r3是r1和r2连接后产生的新路径，S3=S1+S2-doj-doi+dij。计算路径r1、r2和r3的顾客需求量，满足相应载重需求的最小车辆行驶成本系数记为w1、w2和w3。将毗邻点以成对的形式按照节约值savekk′降序排列放入节省对列表SPL中，save12=w1*S1+w2*S2-w3*S3。将SPL中小于0 的savekk′值和与之对应的毗邻点删除。

(d)合并收益：路径ra和rb连接成为新路径rc的合并收益为Ararb。合并收益包括路径熟悉度损失grarb，里程节约值saverarb和断点惩罚值erarb。

Ararb=β1saverarb-β2tigrarb-β3erarbra,rb∈R

(22)

其中，

β1+β2+β3=1,β1,β2,β3≥0

(23)

grarb

(24)

(25)

步骤1：查找当前所有可行线路中与配送中心o相连的点(毗邻点)，计算不同路径上两个毗邻点对应的合并收益。将毗邻点以成对的形式按照合并收益降序排列存入节省对列表SPL。将SPL中小于0 的合并收益和对应的毗邻点删除。

步骤2：将SPL节省对按照合并收益降序顺序执行线路合并。合并方法如下：删除毗邻点与o点之间的连接线，随后将两个毗邻点直接相连。

步骤3：检查合并路径是否满足里程约束与载重量约束。如果不满足载重量约束则放弃此次合并，继续对SPL中下一组进行合并。如果合并后的路径不满足里程约束，则在两个毗邻点之间加入一个绕行成本最低的充电站。如果路线仍不可行则放弃此次线路合并，继续对SPL中下一组进行合并。

步骤4：将SPL中所有毗邻点对合并之后，识别合并后的线路中多余的充电站点并删除。

步骤5：返回本环节步骤1进入新一轮线路合并，直到任意两条可行线路都不能进一步合并。

3.4 物流专员指派子问题

求得服务路径策略后调用改进混合遗传算法为其指派物流专员使服务时间成本最低。本节使用物流专员自身排列的编码方法来确定配送路径策略。直接生成N个1～N间不重复的整数的排列，每个自然数表示一个物流专员个体。根据排列中数字的顺序，依次指派给配送路径集合中的路径。当路径集合中的配送路径数多于可使用的物流专员数目的时候，认定该个体对应解为不可行解。在群体初始化过程中，采用随机生成的方式产生M个不同个体，每个个体包含N个1～N间不重复的整数的排列。适应度公式F=1/(Z+MP)，Z为目标函数值，M表示该配送方案中缺少物流专员的数目，P表示对缺少物流专员的惩罚权重。为了控制算法的收敛速率确保其不过早陷入局部最优解，本节将每代群体中适应度最高的个体复制后存入下一子代第一行，其余个体根据适应度大小在轮盘赌机制下以一定概率进入下一代。进化代数达到指定值则终止。

3.5 局部搜索

本节采用局部搜索中的点移动、点交换以及点插入策略进一步优化当前解。

(1)点移动：将点i从当前位置移动到同路径的其他位置。

(2)点交换：从两条路径分别选取一个点加入到对方路径，交换点在新路径中的位置为该点插入后距离增量最小处。

(3)点插入：以路径1中的顾客点i为例，在路径2中找出距离i点最近的两个点a和b。将i点移动到路径2中a点和b点之间的位置，并将原路径2中a、b两点间各点依次移动到b点之后。

3.6 禁忌搜索

步骤1：初始化站点集合，计算目标函数值并赋给当前解和满意解，置空禁忌表。

步骤2：在已建成的充电站点集合中随机选择一个点并删除此处的充电站点。随后，在没有建站的备选点中随机开设一个充电站点。在新的邻域生成后再次求解，将产生的新解存入候选解集中。

步骤3：如果当前解的最小值优于满意解，则认为此候选解满足特赦准则，更新满意解与其目标函数值。否则，在未被禁忌的候选解中选择成本最小的解作为当前解。同时用与它对应的禁忌对象替代最早进入禁忌列表的禁忌对象。

重复执行步骤2-3直到迭代次数达到预定最大次数，执行步骤4。

步骤4：如果站点数达到最大值或者增加ψ次后满意解仍没有改进则停止。否则，充电站点数目加1，返回步骤1开始下一轮搜索。

4 实验结果及分析

本节通过多组算例验证MCWGATS的寻优能力并分析车型和服务时间等参数对运营策略的影响。实验的计算机参数配置为Intel(R) I5-4460，3.20GHz，8GB RAM。算法在JAVA 中实现为单线程代码。

4.1 测试用例

到目前为止，已发表文献中没有专门用于分析物流专员差异性服务时间的实验算例。本文采用Augerat等[23]、Rinaldi和Yarrow[24]及Taillard[25]使用的三种被广泛应用于VRP研究的算例作为实验数据，相关数据可以从网站http://neo.lcc.uma.es/vrp/vrp-instances/获取。熟悉因子是求解DSTHEVRP问题的重要参数，其最大值介于0.4到0.5之间[9]。本文算例中熟悉因子最大值取0.4，物流专员s为顾客点i服务所需时间tis=(1-σis)qiti。根据物流专员对于其服务对象的熟悉程度，熟悉因子σis在[0,0.4]范围内取值。在物流专员对服务对象完全不熟悉的情况下σis=0。通过实地调研与数据采集可知物流专员每天工作时间约10小时，人均派件100-150件，单件配送收益0.6到3元不等。由此估算出派送一件货物平均需要4-6分钟，本节折中选择ti=5，η=0.5。算例中使用A、B、C 三种车型，B车型满电量状态下最大行驶距离为当前网络中两点间欧几里得距离最大值的ω倍(|I|≤20时，ω=1.2。否则ω=1.3)，B车型其余参数取值与上述网站对应算例相同。A、C车型的载重与可变成本分别B车型的0.9和1.1倍，A、C车型的满电量最大行驶距离分别B车型的0.8和1.2倍。Sce.1-3分别使用A、B和C车型。算法参数设置如表1所示。

表1 MCWGATS参数设置

4.2 算例分析

4.2.1 算法验证

本节使用IBM CPLEX求解小规模算例并将其结果与MCWGATS算法的计算结果进行比较。为了保证实验的一般性，实验数据来源于Augerat[23]及Rinaldi和Yarrow[24]提出的算例，且只选用原文算例的最后n个顾客点。考虑到实际使用效果，设定CPLEX的运行时间上限为3小时(10800s)。“*”为CPLEX运行3小时得到的满意解，“#”表示CPLEX没有找到可行解。实验结果如表2所示，第11列是算法满意解与CPLEX最优解的相对差值(Gap)：(算法满意解-CPLEX最优解)/CPLEX最优解。通过表2可以看出在CPLEX能够在限定时间内找到最优解的情况下(P-n6，P-n7，P-n8)，MCWGATS算法与CPLEX计算结果非常接近并且启发式算法的求解效率较更高。随着算例规模增大，MCWGATS寻优能力与计算效率的优势更加明显。当顾客数达到15时(RY-n15)，CPLEX在3小时内不能找到可行解，而算法在5秒内得到满意解。实验结果表明MCWGATS求解此问题的效果好于CPLEX，验证了本文提出的算法的有效性。

表2 CPLEX与MCWGATS实验结果对比

4.2.2 差异化服务时间对运营成本的影响性分析

不同于传统车辆路径问题，本文考虑了物流专员、配送车辆和服务对象三方协调匹配策略，帮助物流企业提高人员、物流车辆、服务时间等资源的利用效率，降低运营成本。本节通过设置对照实验组，在输入参数完全一致的情况下，将对照组实验结果与本文所述协调匹配策略进行对比分析。本文从Taillard[25]算例中选取6组实例，各组实例包含的顾客点由75到150不等。对照组采用分阶段优化策略，第一阶段在不考虑时间成本的前提下采用改进节约算法与禁忌搜索完成站点选址与车辆服务路径策略。第二阶段将上一阶段的最优解作为输入参数，采用混合遗传算法完成物流专员指派策略。分阶段优化策略与MCWGATS的主要区别在于前者仅能在路径成本最低的策略下进行物流专员指派优化，无法统筹兼顾三方协调匹配策略。表3-5分别展示了Sce1-3情形下MCWGATS和分阶段优化策略的满意解、距离成本、时间成本、建站数、求解时间以及时间成本相对差值Gap，其中GapX=(时间成本X-时间成本)/时间成本。以表3为例，受益于MCWGATS提供的协调匹配策略Sce.1的时间成本相对较低，Gap 1的平均值达到-3.49%。虽然Sce.1对照组的距离成本略低于Sce.1，Sce.1的总运营成本(满意解)在6组实例中均比对照组更低，表4-5情况与表3类似。此外，服务策略会因目标权重的调整产生相应变化。本节以时间成本为例，分析其权重变化对于路径选择策略的影响。实验结果如图1所示，其中Tw=0.5与Tw=1.0分别表示时间成本权重为0.5和1.0情形下的距离成本与时间成本权重为0情形下距离成本的相对差值Gap。由图1可知，所有算例的距离成本Gap均为正数且Tw=1.0对应结果高于Tw=0.5。实验结果可由如下现象解释：在制定路径策略时，为达到总成本最低的目的，时常需要选择非最短的路径来谋求更低的时间成本。因此图1实验结果均为正数。此外，时间成本权重越高，可接受的绕行距离越长，图1中表现为Tw=1.0折线在Tw=0.5折线之上。

表3 Sce1实验结果对比

表4 Sce2实验结果对比

表5 Sce3实验结果对比

图1 时间成本权重对比

4.2.3 物流专员的选择对时间成本的影响性分析

本节从两个方面分析了物流专员自身特性对时间成本的影响。Sce1-3情形下物流专员对顾客的熟悉因子为[0，0.4]范围内事先生成的随机数。Sce1-3对照组中物流专员对顾客的熟悉因子为在集合{0，0.4}内事先随机选择的数值，对照组中物流专员对顾客的熟悉程度只有两种情况(非常熟悉和完全不熟悉)。实验结果如表6所示，其中GapX=(SceX对照组-SceX)/SceX。Gap值为负数表示对照组的时间成本更低，其中3组出现在Sce1，1组出现在Sce2。上述现象的原因在于Sce.1采用的车型载重量较小且物流专员平均服务的顾客数最少，而同一路径中服务顾客越多服务时间与效率越难以得到保障。整体来看，即便是平均服务顾客数最少的Sce.1，对照组的服务时间成本也处于不利位置。为兼顾服务质量与运营成本，只有在安排较小车型为少数顾客提供服务时，使用对照组类型的物流专员更加有利。一般情形下，对不同区域熟悉程度相差较小的物流专员较为适合服务区域广、顾客数量多的配送任务。图2-3展示了Sce.1和Sce.3情形下熟悉因子取值范围对时间成本的影响。对于不同车型，提升物流专员的熟悉因子上限均有助于降低时间成本。值得注意的是Sce.1在不同熟悉因子上限条件下时间成本差异大于Sce.3，在平均服务顾客数较少的情形下时间成本对熟悉因子上限的变化更加敏感。物流企业为少数顾客提供服务计划的时候，安排熟悉度上限较高的物流专员能节约更多的时间成本。而在服务顾客数量较多的情形下，熟悉度上限较高的物流专员相对于熟悉度上限较低者的时间成本优势会在一定程度上被拉近。

表6 时间成本实验结果对比

图2 Sce.1时间成本对比

图3 Sce.3时间成本对比

4.2.4 多车型的影响性分析

本节从Augerat[23]和Taillard[25]采用的算例中共选取11组实例(顾客点数目为20-150)，通过改变可用车辆的限制型号研究车型选择对运营成本的影响。Sce.0情形下可用车型包含A、B、C三种，而Sce.1-3只能分别使用A、B和C车型。表7的第2列表示实例包含的顾客数，第3-4列为Sce.0情形下MCWGATS求得的满意解和求解时间。第5-10列展示Sce.X情形下MCWGATS的满意解X以及Gap X，其中GapX=(满意解X-满意解0)/满意解0。实验结果显示有三种车型可供使用的情形下运营总成本低于其余只能选用单一车型的情形，Sce.0以更加低廉的总运营成本完成配送任务，体现出多车型策略下的成本优势。在使用单一车型的情况下Sce.1的平均Gap最低，分别为1.23%和1.04%。受到载重量较小的约束Sce.1情形下各车辆(或物流专员)平均服务顾客数最少，物流专员可以专注服务熟悉度更高的顾客而降低因地点相邻等原因“顺路”服务熟悉度不高顾客的概率。另一方面，具备最大载重量的C车型受到时间成本和可变成本的影响，Sce.3的平均Gap最高，分别为2.80%和3.40%。

4.2.5 差异化服务时间与车型策略对时间成本的影响

本节在考虑差异化服务时间的情形下，采取随机指派策略、分阶段优化策略与本文提出的MCWGATS算法策略的时间成本进行比较，随后分析多车型策略在差异化服务时间下对时间成本的影响。从Taillard[25]采用的算例中选取8组对其服务时间成本进行分析。图4随机组表示随机指派物流专员情形下的时间成本，对照组表示分阶段优化策略对应的时间成本。随机指派策略产生的服务时间成本在8个算例中均高于其余两种策略。Sce.0与Sce.0随机组的时间成本平均差异接近30%，最高达到38.2%(tai100c)。Sce.0与Sce.0对照组的时间成本平均差异为6.1%。实验结果表明相对于仅考虑多车型的服务路径问题(随机组)和分阶段优化策略(对照组)，协调与兼顾服务员人、服务车型和服务对象三者匹配的HVRP问题更有利于降低成本提高企业利润。

表7 车型实验结果对比

图4 多车型时间成本对比

5 结语

顺应电动汽车在物流配送行业发展趋势，考虑差异化服务时间的多车型电动物流车辆路径问题是一个应用前景广泛的现实问题。电动汽车参与的物流配送服务需要物流专员、电动汽车和顾客三方协作的完成。兼顾服务人员指派、车型选择和服务对象选择三者的匹配问题有助于提升资源利用率提高企业收益。本文提出了考虑差异化服务成本的多车型电动汽车路径优化与充电策略问题，并建立了该问题的整数规划数学模型。为求得模型的满意解，本文采用了基于改进节约算法、遗传算法与禁忌算法结合的混合启发式算法MCWGATS，通过多组中小规模算例验证了算法的有效性。最后，分析了多车型类型和差异化服务时间对运营成本的影响。实验结果表明，该模型可以帮助物流企业高效率地降低行驶成本节约服务时间进而到达降低运营成本的目的，为物流企业提供良好借鉴与帮助。以下方面还有待进一步研究，在未来的研究中可以进一步分析不同车型电池充电率，电池单位消耗率与固定成本在内的更多因素；其次，为保障物流服务的时效性，硬时间窗因素将作为重要参数纳入后续研究中；最后，设计更加高效的算法策略将是未来工作的一个重点。