多时空配送任务驱动的无人车队车辆数优化方法

郑李萍，王建强，张玉召，董祚帆

（兰州交通大学交通运输学院，兰州 730070）

（*通信作者电子邮箱xinxiwjq@126.com）

0 引言

具有精确导航和自动化配送特征的无人配送车（后文简称为无人车）受到物流企业的青睐，并将其应用于社区和园区等特定场景的快递终端配送。已有研究表明由无人车参与的快递终端配送模式具有众多优势。Boysen 等［1］提出由卡车和无人车协作完成市中心最后1 km 快递配送有利于缓解市中心的拥堵；Ulmer等［2］提出将无人车与快递取件站相结合以降低终端配送运营成本；Figliozzi［3］发现相较于电动车和传统内燃机车，无人车有利于降低快递配送中的碳排放。

物流配送过程存在时间的随机性，通常做法是假设时间服从一定的概率分布。如Ehmke 等［4］在给定顾客服务水平的前提下，假设车辆的行驶时长服从正态分布；Gutierrez 等［5］假设具有不确定性的到达时间服从对数正态分布，并论证了其合理性；Binart 等［6］在模型构建时将时间离散化，假设服务时长服从离散三角形分布。

在任务驱动下的路径优化研究中，已有成果关注对象主要是某一具体任务。如Wang 等［7］提出考虑个体出行者偏好的个性化路径推荐算法，实现了从起点到目的地的最优路径规划；麻存瑞等［8］设计了一种采用自然数编码的遗传算法以寻找在一次配送中总时间最短的多车配送路径方案；李玲玉等［9］针对单配送员多任务的配送路径优化问题，设计出C-W（Clark-Wright）节约算法。解决方案主要是算法优化，如Yu等［10］提出一种改进分支定界算法优化车队的行驶路径；张毅等［11］针对人工鱼群算法在机器人全局路径规划中容易陷入局部最优的缺陷，提出一种混合改进人工鱼群算法；赵志学等［12］设计一种融合模拟退火算法的混合差分进化算法优化交通拥堵区域的物流配送线路。

在已有研究成果的基础上，尚存在3 个问题有待于进一步探讨：1）如何在满足一定成功服务率的同时，确定并优化无人车队数量依然是快递终端配送面临的巨大挑战；2）如何利用网络转化方法进行路径规划缺乏研究；3）服务时长的设定也未充分考虑顾客的行走时长特征。

基于此，本文提出可靠车队问题并进行了详细描述，以确保在高成功服务率的前提下为配送中心规划最小无人车队车辆数。充分考虑顾客行走时长特征，假设无人车服务时长服从正态分布。网络模型的构建与转化的过程，也是将求解最小车队车辆数通过最小路径覆盖问题转化为网络最大流问题的过程。最后设计了在大规模服务网络计算中适用的Dijkstra-Dinic算法求解该问题。

1 问题描述

给定服务需求集合C，每一个服务ci∈C被定义为一个元组(ei，li，ni，qi)，其中ei、li分别表示预约服务时间窗的最早时刻和最晚时刻，ni表示服务地点，qi表示取/送货物量。将可靠车队问题定义为：将最晚时刻li作为无人车的目标开始服务时刻，在保证高成功服务率的前提下，使最小车辆数的车队从配送中心出发，并在完成所有服务后返回配送中心。便于研究，本文假设如下：1）无人车在路段aij，以速度vij匀速行驶；2）所有车辆在初始时刻续航里程相同；3）顾客在最晚时刻li后到达服务点ni。

2 模型构建

通过构建最短路径模型、服务网络模型和最小车队模型，将可靠车队问题转化为便于求解的最大流问题，如图1所示。

图1 模型构建流程Fig.1 Model construction process

2.1 最短路径模型

用G(V，A)表示一个由有限个节点组成的交通网络，其中V是节点集，V=Vser∪Vcro包括服务节点集Vser（包含配送中心集O）和路口节点集Vcro，A为路段集。ni表示节点集合中的任意一个节点，ni∈V；aij表示相邻节点间路段，aij∈A。

对于最晚时刻不同的起讫点nr、ns，∀nr，ns∈Vser，lr＜ls，建立距离最短路径模型。

目标函数：

约束条件：

式中：dij为路段aij的距离，xij为决策变量xij∈{0，1}，(i，j) ∈A。

服务时长和等待时长是最短路径规划需要考虑的重要参数，考虑服务时长是为了确保高成功服务率，等待时长的设定是避免无人车提前到达服务点后因长时间等待而影响整体配送效率［13］。

服务时长Ti表示无人车在服务点ni从最晚时刻li到离开时刻ti的时间差，Ti=ti-li。本文假设Ti近似服从均值为μi、方差为σi2的正态分布，Ti∈N(μi，σi2)，σi2体现顾客到达服务点时刻的集中程度，σi2越小，顾客到达时刻越集中。当成功服务概率为1-α时，可靠服务时长的计算如式（3）所示，由于不考虑顾客提前到达，可靠服务时长区间为

式中：trs为起讫点nr，ns的行驶时长，计算方法如式（5）所示：

式中drs表示路段ars的长度。

无人车需要提前或准时在最晚时刻到达，如式（6）所示，图2展示了无人车在相邻起讫点nr，ns具体时间状态。

图2 无人车在相邻起讫点间的时间状态Fig.2 Time state between the adjacent origin-destination nodes of autonomous vehicle

若车辆在最晚时刻ls准时到达，则到达时刻=ls，到达即开始服务；若提前到达，则＜ls，此时无人车需要等到最晚时刻ls才开始服务。

2.2 服务网络模型

在包括空间维、时间维的二维时空网络中构造服务网络，即服务序列网络，用(M，E)表示。将物理节点ni∈Vser映射到时空网络中形成带时间索引的时空节点(i，t)（(i，t)∈M）。时空节点之间的连接形成了时空弧(i，j，t，t′)，表示一条从时空节点(i，t)到(j，t′)的有向时空路径。图3展示了服务网络的转化过程。

图3（a）中包含配送中心O和6 个带时间窗的服务节点。图3（b）在时空网络中刻画无人车的行进状态，其中行驶弧是指无人车在空间上从服务节点ni位移到nj，时间上从t时刻转移到t′；等待弧的出现是因为车辆到达服务节点的时刻早于最晚时刻；服务弧是在服务节点装/卸载货物的过程。根据图3（b）的服务序列，图3（c）在时空网络中形成服务网络。

图3 服务网络转化Fig.3 Service network transformation

给定服务网络(M，E)中路径R由一组时空弧的序列构成{(n1，n2，t1，t2)，(n2，n3，t2，t3)，…，(nk-1，nk，tk-1，tk)} ∈E，相 邻服务节点时刻满足式（7）：

式中：ti为离开服务节点ni的时刻，ti，i+1表示从服务节点ni到ni+1的行驶时长和Ti+1分别表示在服务节点ni+1的等待时长和服务时长（i=1，2，…，k-1)。路径R中的节点集合被定义为M(R)=若两个服务节点能被一条时空弧连接，表明这两个服务节点可以被一辆车连续服务。文献［14］提出并证明了在有向网络中最小车队数量求解相当于最小节点不相交路径覆盖问题。

定义1节点不相交路径覆盖。给定有向网络(M，E)中，若一个路径集合{R1，R2，…，Rh}满足M=并且M(Ri) ∩M(Rj)=∅（i≠j），则称{R1，R2，…，Rh}为(M，E)的一个节点不相交路径覆盖。

有向网络的最小路径覆盖求解是NP-hard 问题［15］，在大规模服务网络的计算上是不可行的。但是，若该网络为有向无环网络，则最优解可以在多项式时间内找到。本文构建的服务网络都是有向无环网络，可以采用矛盾法进行证明。

证明 若服务网络(M，E)中存在循环路径，简单起见，假设路径R={(n1，n2，t1，t2)，(n2，n1，t2，t1)}，根据服务网络的定义和式（7），则有：

很显然，式（8）中t1＜t1是矛盾的；同理可以推断出任意路 径R={(n1，n2，t1，t2)，…，(nk-1，nk，tk-1，tk)，(nk，n1，tk，t1)}都有t1＜t1+t1，2++T2=t2，…，＜tk+tk，1++T1=t1，因此服务网络中不存在循环的路径。

图3（c）节点不相交路径覆盖结果如图4 所示，最小节点不相交路径覆盖数（最小车队车辆数）为3。特别的，若存在单一节点的路径覆盖，无人车配送路径为O-ni-O。

图4 路径覆盖示例Fig.4 Path coverage sample

2.3 最小车队模型

针对快递终端配送，服务网络有其独特性，无人车队从配送中心出发，完成服务后返回配送中心，即，每条路径起点和终点都为配送中心O。因此，在二分图基础上设置超级源点O和超级汇点O′，形成容量网络。二分图是将服务节点集合中的每个节点，分别放置于两列M1={n1，n2，…，nk}，M2=｛n1′，n2′…，nk′}，ni=ni′；将服务网络中的边(i，j，t，t′) ∈E映射到二分图，连接两列的节点形成二分图的边。

定义2容量网络。在二分图基础上，设置超级源点O并连接到M1={n1，n2，…，nk}所有元素，超级汇点O′并连接到M2={n1′，n2′，…，nk′}所有元素，使弧容量uij=1，弧流量fij=0。容量网络表示为(M′，E′，u，f)，其中：

图5展示了服务网络图3（c）对应的容量网络。

图5 容量网络Fig.5 Capacity network

定义3残余网络。对于容量网络(M′，E′，u，f)，若弧容量uij被使用，则uij=0，弧(ni，nj)∈E′转化为弧(nj，ni)∈E″，且uji=1，以此为原则，更新容量网络，得到残余网络（M′，E″，u′，f′）。

定理1残余网络中若节点ni和nj间存在流，则(ni，nj)∈E′ 和(nj，ni)∈E″有且只存在其中一个，并且若uij′(uji′)=1，则uji′(uij′)=0。

证明 此定理可以用矛盾法证明，对于残余网络（M′，E″，u′，f′）的存在流的两个节点n1、n2，若同时存在(ni，nj)∈E″，(nj，ni)∈E″，则fij′=1、fji′=1，也就是说服务节点ni与nj之间的容量为2，这与残余网络定义中的弧容量为1矛盾。因此，在残余网络中，(ni，nj)或(nj，ni)存在且仅存在1个。

定义4层次网络。在残余网络中，超级源点O的层次为0，从超级源点到节点ni的最短路径的弧容量之和β，称为节点ni的层次。

定理2如果Ψ是二分图的匹配数，则残余网络存在流F，使得F=Ψ。

证明 在定理1 中已经证明，残余网络中两节点之间的弧容量为0 或1，如果{(ni，nj)|ni∈M1，nj∈M2，fij=1} 是二分图中一个匹配，那么该匹配的流为1。由于每个节点只存在于一个匹配中，因此每增加一个匹配，流也增加1，则F=Ψ。有如下推论：

推论1 路径覆盖数Θ为服务节点的数量与流F之差，即Θ=‖Vser‖-F。

证明 如果匹配数为0，那么每个节点都是一条独立的路径O-ni-O′，ni∈Vser，路径数为‖Vser‖；但是，除了超级源点O和超级汇点O′，残余网络中的路径都是节点不相交的，意味着每个点只会被匹配一次。每增加一组匹配{(ni，nj)|ni∈M1，nj∈M2，fij=1}，即将两个节点ni，nj合并到一条路径上，O-ni-nj-O′，路径数为‖Vser‖-1。同理可得，若有Ψ个匹配，路径数为‖Vser‖-Ψ。根据定理2，可推出Θ=‖Vser‖-F。

推论2 最小路径覆盖数minΘ为服务节点与最大流maxF之差，即minΘ=‖Vser‖-maxF。

车辆续航里程和容量有限，需要满足约束式（9）和（10）：

式中：D为无人车的续航里程，qi表示在服务节点ni的装载/卸载货物数量，若卸载qi＜0，装载qi＞0，Q为无人车的容量。

3 算法设计

在确定起点和终点网络中寻找最优路径，Dijkstra 算法是一种高效可靠的方法［16］，同时Dinic算法在网络最大流计算中效率较高，因此，本文设计Dijkstra-Dinic 算法求解模型，并插入One-stop算子有效地缩小了搜索空间。

One-stop 算子 在一次广度优先搜索（Breadth First Search，BFS）后的深度优先搜索（Depth First Search，DFS）中，为层次为β的节点ni搜索层次为β+1 的节点时，只考虑存在流的节点nj，fij=1，ni∈M1，nj∈M2，并且在找到一条有效增广路径后就停止搜索。若层次网络层次为β，每个层次平均有β′个元素，在下一层次中平均有β″个节点与之存在流，那么全搜索最多需要有β′β次，但是插入One-stop 算子，搜索次数最多为(β-1)*β′*β″。值得注意的是，一般相邻两层次的节点若存在流，说明可连接成有效增广路径，所以在众多可连接的下一层次节点中，第一个节点往往就是可行的，即搜索次数基本控制在(β-1)*β′。算法流程如图6所示。

图6 Dijkstra-Dinic算法流程Fig.6 Flowchart of Dijkstra-Dinic algorithm

4 仿真分析

考虑在包括服务节点在内的625个节点、1 200条路段的网络中进行仿真，路段长度为［180，600］的随机整数（距离单位为m）。由于完整网络图较大，因此截取局部仿真场景如图7所示。仿真场景包括服务节点249、349、449和549四种规模。相关数据假设如下所示：容量为100，续航里程90 km，速度为12 km/h，可预约时间9：00—21：00。假设服务时长Ti∈N(7，1.5)，不同可靠服务时长对应着不同的成功服务率，如表1所示。

表1 可靠服务时长与成功服务率Tab.1 Reliable service time and successful service rate

图7 局部仿真路网Fig.7 Local simulation road network

图8 展示了在服务节点分别为249、349、449 和549 的四种不同规模的服务网络中，考虑成功服务率，最小车队车辆数随δ变化的情况。

图8 四种可靠服务时长的最小车队车辆数随最大等待时长演化Fig.8 Evolution of the minimum vehicle number of fleet with maximum waiting time in four reliable service time cases

图8 纵坐标采用对数显示方法，图形整体呈现凹形。当最大等待时长δ=0 时，最小车队车辆数等于服务节点数，意味着每个服务节点都需要一辆车单独服务。随着δ的增大，不同服务网络规模下的最小车队车辆数都呈现下降趋势，逐渐平缓并会趋向稳定。当达到一个临界值，即使δ继续增加，车辆数保持不变。趋向稳定的δ和最小车队车辆数如图9 和图10所示。

从图9 可以看出，当成功服务率相同时，最小车队车辆数随服务网络规模增加而增加；在不同规模的服务网络中，最小车队车辆数与可靠服务时长呈正相关；而最大等待时长临界值都在可靠服务时长为9 min 时保持最小。货物如未成功配送，必然导致第二次配送。在首次配送中未成功服务的数量、配送效率以及第二次配送车辆数如表2所示。

图9 四个服务网络的最小车队车辆数Fig.9 The minimum vehicle number of fleet in four service networks

根据表2，服务网络规模越大，车辆的使用效率（每辆车成功服务的数量）也越高，虽然第二次配送的数量总体呈现增长趋势，但是增长率越来越低。最小车队车辆数和第二次配送车辆数的合计结果如图10所示。

表2 车队服务效率及第二次配送车辆数Tab.2 Fleet service efficiency and the number of secondary distribution vehicles

图10 四个服务网络的最大等待时长临界值Fig.10 Critical value of maximum waiting time in four service networks

根据图11，在服务节点数为249、449 和549 的服务网络中，可靠服务时长为8 min 和9 min 时两次配送的合计车辆数最小，但是可靠服务时长为8 min 时，最小车队车辆数更少。当服务节点数为349时，可靠服务时长为9 min时更好。

图11 四个服务网络的两次配送车辆合计数量Fig.11 Total number of vehicles for two deliveries in four service networks

本文算法是用Python 3.7编写，在一台CPU 为1.80 GHz、内存为8 GB的个人计算机上评估。Dijkstra-Dinic算法在大规模网络计算中表现出良好的性能：在625个节点、1 200条边的仿真场景中，等待时长和可靠服务时长为9 min，服务网络规模为549，计算最小车队共用时21.56 s。

5 结语

为了求解并优化无人配送车队车辆数问题，本文构建了最短路径模型、服务网络模型和最小车队模型，引入One-stop算子设计了Dijkstra-Dinic 算法求解模型，通过数值实验验证了模型和算法的可行性与有效性。主要结论有：1）可靠车队的数量与可靠服务时长呈正相关，和等待时长则反之；2）在不同服务网络规模中，可靠车队的数量趋于稳定的最大等待时长临界值不同，因此最大等待时长应与服务网络规模相适应；3）可靠车队的数量与服务网络规模呈正相关，表明配送中心应根据服务区域范围大小和需求量配置无人车队车辆数；4）本文算法在大规模网络计算中表现出良好的性能；并且网络规模越大车队利用效率越高；5）本文提出的可靠车队方案有效地解决了配送中心车队数量配置问题。

在已有研究的基础上，本文服务时长的设定具有一定的合理性，接下来将以实际服务中顾客的行走时长数据为基础，探讨不同场景中（例如商业区、居住区、高层和底层社区）顾客的行走时长特征，为终端配送更精细化的管理提供参考。