网约车、乘客与快递协同配送路径匹配优化问题是基本车辆路径规划问题(vehicle routing problem，VRP)的拓展．近年来，为降低车辆配送总成本，带有不同复杂约束条件的共同配送问题模型及其求解算法引起了学者们的广泛关注．文献[1-2]提出将共同配送模式应用到最后1 km末端配送中，并有效提高了城市配送效率；文献[3-5]利用改进的启发式算法，将碳排放量最低作为优化目标求解VRP问题；文献[6-7]采用粒子群优化方法求解考虑能源消耗的动态多目标VRP问题；文献[8]提出一种基于自适应分组的方法将大规模路径优化问题转化为数量不断减少的多目标优化问题；文献[9-10]通过建立多重约束的路径优化模型求解实际的VRP问题；文献[11-13]在VRP问题的基础上，分别考虑了道路坡度因素、车辆容量限制和离散时间窗．对于上述求解具有不同约束的VRP问题，常用的精确算法有分支定界法[14-15]和两级动态规划法[16-17]，然而越来越多的学者采用启发式算法或启发式扩展算法，如结合禁忌搜索与大邻域搜索算法[18]、粒子群算法[19]、三阶段禁忌启发式算法[20-21]、果蝇优化算法[22-23]及改进模拟退火算法[24]等；文献[25]基于联合配送，提出了一种多对多的网络共同配送模式；文献[26]提出在考虑劳动力不足的情况下，采用外租车辆的路径优化问题．上述研究对于共同配送问题都是以单一货物作为对象，仅考虑经济利益，然而配送车辆数量和种类同样也是限制交通管制与环境质量提升的重要约束．与货物共同配送货物模式类似的乘客合乘出租车模式在近几年也受到众多学者关注．文献[27]建立了一个实时匹配司机和乘客的动态合乘模型；文献[28]以车辆总行驶里程最短为目标，研究带容量约束的VRP；文献[29-30]基于合乘路径总费用最小为目标，提出以乘客的位置、时间窗及出租车载客容量为约束的合乘模型，并设计启发式算法求解．对于求解模型的算法，文献[31]提出基于模糊聚类和模糊识别的出租车合乘算法，实现乘客与出租车之间的匹配；文献[32]采用贪心算法对以系统时间成本最小为优化目标的多约束大规模动态合乘模型进行了求解；并行模拟退火算法[33-34]、混合启发式算法[35-37]、改进遗传算法[38-39]也相继用于对模型进行求解．出租车合乘模式以其缓解交通拥堵、减少环境污染的优点被社会所认可和支持．现有研究成果大多关注于共同配送经济效益最大化或路径优化里程最小化的单独研究，而鲜有文献从系统论的角度出发研究同时考虑两者的协同配送问题；针对于共同配送的对象，少数文献在众包物流配送货物+货物与出租车合乘接送乘客+乘客方面取得了一定的研究成果，而将两者结合实行乘客+货物协同配送的文献较少．考虑将末端配送与其他行业结合形成更加多元化的共同配送策略，从而提升传统共同配送的整体效率及收益．本研究基于共享经济的视角，建立同时考虑多方主体利益和路径规划的车辆配送路径匹配优化模型，并提出一种适用于求解全局优化问题的混合遗传算法对模型予以求解，为网约车与快递配送的路径联合规划提供理论支撑与技术支持．1 问题描述与假设1.1　问题描述网约车路径联合优化前后的路线对比图如图1所示．10.13245/j.hust.210721.F001图1路径联合优化前后网约车路线对比图假设：乘客与快递的出发点、目的地及各个快递点的需求量已知；网约车的车型、固定成本及每公里的燃油费成本相同；车辆匀速行驶，不考虑实时交通情况；乘客在最早出发时间已经到达上车点；快递的大小体积相同，不做其他特殊区别；快递与网约车搭建的共同平台的配送资质及网约车车主配送快递的合规性等法律对快递配送业务不会产生影响．1.2　符号与决策变量模型中涉及到的符号与决策变量如下：W=K⋃Om⋃Dm⋃P⋃N为所有节点的集合，包括网约车的集合K，乘客m上车点集合Om，乘客m下车点集合Dm，配送中心的集合P，快递点的集合N；qk为网约车k的最大搭载货物量；dij为站点i和j之间的距离；tij为网约车从站点i至j所花费的时间；c0为网约车的起步价；l0为网约车起步价对应的公里数；r0为网约车超出起步公里数的每公里单价；v为网约车匀速行驶时的速度；当车辆k从顶点i行驶至顶点j时，Xijk=1，否则Xijk=0；当车辆k对快递点n进行配送时，ynk=1，否则ynk=0；当乘客m乘坐车辆k时，Smk=1，否则Smk=0；当快递由车辆k从站点i运至站点j时，qijk=1，否则qijk=0．2 模型构建2.1　乘客支付的费用计算乘客最终须支付的费用为通过最短路径实现出行时所支付的费用扣除乘客由于路线绕行造成的时间价值损失．[Ei，Li]为乘客上车需求点i的硬时间窗，Ei为乘客最早出发时间，Li为乘客最晚出发时间；[ei，li]和[e'i，l'i]为乘客下车需求点i的软时间窗，[ei，li]为乘客期望下车时间段，[e'i，l'i]为乘客可接受下车时间段，且e'i≤ei≤li≤l'i．乘客下车点软时间窗为Pi(ti)=M    (tie'i);f1(ei-ti)    (e'i≤tiei);0    (ei≤ti≤li);f2(ti-li)    (liti≤l'i);M    (til'i), (1)式中：f1和f2为惩罚成本；M为一个极大值．在求解目标中，须考虑到乘客的利益，因此将时间价值损失转化为乘客在乘车途中可享受的折扣费率，用rkij表示．乘客支付的费用为F1=∑i∈Om∑j∈DmXijkrijkPi(ti). (2)2.2　快递公司支付的费用计算配送中心与快递点间不是以最短路径进行配送，造成的经济损失转化为网约车搭载快递绕行时间成本为P=γ*(∑i∈P∑j∈NXijktij-dij/v), (3)式中γ*为快递单位绕行时间价值．在求解目标中，须考虑到快递公司的利益，因此将经济损失转化为快递公司每通过网约车配送一单快递所享受的折扣费率，由Rkij表示．快递公司支付的费用为F2=w∑i∈P∑j∈NXijkRijkqij，(4)式中：w为快递公司外包给网约车配送每件快递所支付的费用；qij为网约车从站点i到站点j单次配送的快递数量．2.3　网约车的成本计算网约车由网约车平台进行统一管理，网约车接收到的乘客信息与快递信息均由平台接收，然后发送至网约车车主终端，因此网约车平台须从网约车的收入中收取比例为h的费用；此外，网约车还有固定成本C1(车损及保养)与变动成本(即油耗成本)C2的支出，由此网约车的总成本支出为C=h(F1+F2)+C1+C2．(5)假设车辆每行驶1 km保养费用为a，折旧费用为b，则有：C1=(a+b)v∑i,j∈HXijktij；(6)C2=ϕv∑i,j∈HXijktij，(7)式中ϕ为网约车每公里的油耗费用．2.4　模型建立以网约车为载体，在满足乘客出行需求和快递配送的需求前提下，以乘客、网约车车主、网约车平台与快递公司四方参与主体的总利益最大化作为优化目标进行研究．综上所述，为求解上述问题建立如下混合整数规划数学模型max f=(1-h)(∑i∈Om∑j∈DmXijkrijkPi(ti)+w∑i∈P∑j∈NXijkRijkqij)-[(a+b)v∑i,j∈HXijktij+ϕv∑i,j∈HXijktij, (8)可将目标函数简化为max f=(1-h)(F1+F2)-(C1+C2)，(9)模型约束条件为：ei≤ATik≤li  (i∈Om）；(10)∑i,j∈HqijkXijk≤qk  (k∈K); (11)∑k∈Kynk=1  (n∈N); (12)∑k∈KSmk=1  (m∈M); (13)∑i∈Om∑j∈PXijk-∑i∈Dm∑j∈NXijk=0  (k∈K); (14)ATik+ti,m+i=ATm+ik  (i∈Om,  k∈K)；(15)Rijk≤1; (16)      ∑i∈Om∑j∈DmXijkrijkPi(ti)≤2C0/3+r0(∑i∈Om∑j∈DmXijkdij-L0)    (∑i∈Om∑j∈DmXijkdij≥L0),∑i∈Om∑j∈DmXijkrijkPi(ti)≤2C0/3    (其他). (17)式(8)为四方参与主体的总利益，求最大值；式(10)为乘客时间窗约束；式(11)为网约车容量约束；式(12)和(13)为服务约束；式(14)为乘客与快递配送成对约束；式(15)为乘客上下车点时间顺序约束；式(16)和(17)为费用约束．3 模型求解算法求解前，首先利用重心分区法将配送中心与快递点进行分组，然后设计一种启发式算法构造初始解，最后运用改进的遗传算法对模型进行优化求解．3.1　快递点分组由于在本问题中配送网络涉及网约车、乘客上下车点、配送中心与快递点多个节点，因此首先采用重心分区法将总系统内的快递点和配送中心进行分组，使得位置相近的快递点存在的区域仅有一个配送中心提供服务，满足不交叉条件，且该方法在进行大规模数据的计算时操作简单、结果清晰．3.2　混合遗传算法混合遗传算法如图2所示．图中：I为个体编号，J为基因编号，g为迭代次数，S为种群规模，T为计数器．10.13245/j.hust.210721.F002图2混合遗传算法3.2.1　染色体编码规则采用自然数编码规则，以网约车、乘客上车点、乘客下车点、配送中心和快递点5种节点进行编号．每一条染色体代表x辆网约车搭载y名乘客到达其目的地的过程中，前往p个配送中心对z个快递点进行配送，染色体长度取决于有配送需求的乘客和快递的数量．例如有3辆网约车，在前往乘客上下车点途中经过配送中心与快递点取送快递，则其编码如图3所示．10.13245/j.hust.210721.F003图3染色体编码3.2.2　种群初始化初始解的优劣直接影响算法收敛效率，良好的初始解能保证算法在短时间内获得全局最优解或近似最优解，且遗传算法在构造初始解时大多采用随机的策略，这在一定程度上会造成早熟收敛的问题，因此通过利用插入启发式算法进行遗传算法初始解的构造．初始解创建步骤如下．步骤1 将网约车固定在每条路径的第一个位置上．步骤2 将乘客上下车点随机插入到路径中，并记录两点对应的硬时间窗和软时间窗．步骤3 根据上述配送中心与快递点分组结果，随机选择配送中心-快递点，并将其插入到该条路径．可行的条件为满足模型的约束．为每辆网约车的配送路径重复上述过程，即创建一个初始解．其中插入过程算法流程如图4所示．10.13245/j.hust.210721.F004图4插入启发式算法3.2.3　适应度函数每一条染色体均由所有网约车的路径组成，因此在计算适应度函数的过程中，首先将染色体拆分为基因片段，即每辆车的路径，然后进行计算每段基因的适应度值，在同一染色体中进行累加，得到该条染色体的适应度值．根据问题与模型特点，将目标函数作为适应度函数F(x)=max[f(x)]．4 实例分析4.1　算例构建采用2018年京东全球运筹优化挑战赛的中A榜赛题部分数据进行实验，选取某个时间段内的10辆网约车(1~10)、10位乘客(11~20)及乘客在上下车点的服务时间窗、5个配送中心(31~35)、50个快递点(36~85)及其对应的快递需求量．根据该问题的特点，并结合目前网约车的现实情况，以两点之间的直线距离作为配送距离，未考虑实时的交通路况等因素．网约车的参数设置如下：每辆网约车的最大搭载快递数为30，车辆均以v=40 km/h的速度匀速行驶，网约车平台抽成比例h=20%，油耗费用a=0.6 元/km．4.2　实验仿真与对比分析采用Matlab2019a进行编程求解，在CPU为1.90 GHz、内存为8 GBi、64 bit操作系统的Intel笔记本上测试．混合遗传算法的实验参数设置如下：种群规模为60，记忆库容量为20，迭代最大次数为100，交叉概率为0.8，变异概率为0.2．选取变邻域搜索算法与本文算法分别求解该车辆联合路径优化问题．实验结果得到变邻域搜索算法进化曲线与混合遗传算法迭代收敛曲线如图5和6所示．10.13245/j.hust.210721.F005图5变邻域搜索算法进化曲线 10.13245/j.hust.210721.F006图6混合遗传算法迭代收敛曲线 经过50次寻优过程，其最终输出结果得到10辆网约车的最优路径分配方案，其中总利益为该问题的最终求解目标值，最优路径分配方案如表1所示．10.13245/j.hust.210721.T001表1网约车的最优路径分配方案车辆序号混合遗传算法变邻域搜索算法车辆路径总利益/元车辆路径总利益/元11→35→19→78→81→80→29→85259.3031→34→19→71→77→72→75→29→74161.48522→32→14→58→24→612→14→2433→20→31→46→42→30→45→473→33→20→62→65→30→63→6944→11→32→59→60→34→21→72→73→74→75→764→32→56→12→60→57→2255→12→31→48→49→22→365→35→79→11→80→82→2166→35→84→16→82→83→266→16→2677→13→31→44→43→48→49→23→507→13→32→61→60→59→2388→17→31→51→55→53→54→32→27→57→588→17→2799→31→18→40→37→38→28→39→419→18→31→44→53→46→28→471010→33→15→62→64→68→66→34→25→77→7110→31→48→15→49→50→55→25→53→51从图5与图6中可以得到：变邻域搜索算法在迭代至100代时结果仍未稳定，本文算法在迭代至第33代时结果就已收敛，即得到配送路径中乘客、网约车、网约车平台和快递公司四方参与主体总利益较优值，且总利益值有所提高，其中插入启发式算法构造初始解操作帮助算法跳出了局部最优，有效提高求解问题的全局寻优能力及运行速度．对比最优路径分配方案中可知：在最优路径分配方案方面，变邻域搜索算法得到的最优路径分配方案，编号为2，6，8的网约车仅前往乘客上下车点接送乘客，没有取送快递；本文算法得到的最优路径分配方案中，所有网约车均在接送乘客去往下车点的途中，到达配送中心与快递点进行取送快递，其中编号为1，2，3，5，6，7，9的网约车在接送乘客途中到达一个配送中心进行取快递，而编号为4，8，10的网约车共对两个配送中心与多个快递点进行取送快递服务；在配送效率方面，变邻域搜索算法在网约车同时服务乘客与快递的订单中，只对56%的快递点进行取送快递服务，本文算法优化网约车配送路径共服务了90%的快递点，效率得到较大提升；在最终求解目标值方面，变邻域搜索算法的总利益为161.485元，采用混合遗传算法得到的总利益值为259.303元，比前者增加了97.818元．利用本文算法能够使结果达到更优，证明本文算法能极大程度地利用网约车的运力资源，联合路径配送方案能够达到预期效果，更符合共享经济理念．5 结语基于传统路径规划问题提出了网约车、乘客与快递配送路径匹配优化方案，从系统的角度构建目标函数，同时考虑网约车、快递公司、乘客等多方参与主体利益，通过合理运用网约车运力资源来弥补物流末端配送即时性的不足，从而实现全局优化达到降低配送成本、提升服务时效及实现多方利益最大化的目标．此外，为了更好地求解该问题，通过设计插入启发式算法优化初始解，再运用改进遗传算法对解进行优化，最终采用Matlab2019a软件进行实验并得到较优解．结果表明：共同配送策略不仅能充分利用社会资源，而且能有效提升多方利益；仿真实验结果对比验证了本文算法对于复杂约束条件的车辆路径问题具有出色的求解能力，提升了理论成果的实用性．