具有容量限制的无人驾驶清扫车路径优化模型及求解算法

Optimization Model and Solving Algorithm for Autonomous Sweeper Path Planning with Capacity Constraints

摘要: 合理规划车辆行驶路线，减少不必要的行驶时间是实现无人清扫车推广的关键技术。本文为有容量限制和中间设施点选择的无人清扫车路线问题建立了一个可以直接求出行驶路线的优化模型，并设计了对应的二级模拟退火算法进行求解。首先，以平均分配为原则，根据容量限制确定垃圾站，生成两辆无人清扫车可行的初始路线；其次，对两辆无人清扫车的行驶路线进行组合并利用模拟退火算法加以优化；最后，逐一优化两辆清扫车的行驶路线并分别生成其最终行驶路线。通过算例分析结果显示，本文设计的二级模拟退火算法可将无人清扫车的总行驶时间减少高达44%，减少了清扫车的工作成本，实现最终线路的工作负荷的均衡，证明了该模型和算法的可靠与高效性。

Abstract: Efficient route planning for vehicles, aimed at minimizing unnecessary travel time, is a critical technology for the widespread adoption of unmanned cleaning vehicles. This paper establishes an optimization model for the unmanned cleaning vehicle routing problem with capacity constraints and the selection of intermediate facility points. It also designs a corresponding two-stage simulated annealing algorithm for solution. First, following the principle of equitable distribution, garbage stations are determined based on capacity constraints to generate initial feasible routes for two unmanned cleaning vehicles. Second, the routes of the two vehicles are combined and optimized using a simulated annealing algorithm. Finally, each of the two cleaning vehicle routes is optimized individually to generate their final travel routes. Results from case studies demonstrate that the two-stage simulated annealing algorithm designed in this paper can reduce the total travel time of unmanned cleaning vehicles by up to 44%. This reduction leads to cost savings for the cleaning vehicles and balances the workload for the final routes, confirming the reliability and efficiency of the proposed model and algorithm.

1. 引言

随着无人驾驶技术的快速发展，无人驾驶清扫车作为一种典型的无人作业车，不仅可以代替环卫工人在恶劣环境中工作，还可以在突发卫生事件期间负责疫区的清洁工作，以减少人员接触造成的交叉感染。与传统的有人清扫车不同，无人清扫车装有远程控制系统和高精度地图 [1] ，车辆可按提前规划好的线路执行清扫任务，而有效的路线优化技术是普及推广无人清扫车的关键技术。若把垃圾站看作一种设施，那么无人清扫车的行驶路线问题将转化为一个在特定路径中存在设施选择和车辆容量受限的弧路径问题(Capacitated Arc Routing Problem with Intermediate Facilities-CARPIF) [2] ，此种类问题具有明显的NP-hard特征 [3] [4] [5] 。Ghiani [6] 等人为具有容量和长度限制的中间设施点问题(GARPIF)设计了三种启发式方法，分别是基于分区域的构造方法以及禁忌搜索算法，并分析了一组具有50个节点，92条弧段的实际案例来验证所提出方法的可靠性。Willemse [7] 等人考虑了车辆工作时间，为CARPIF问题加入了时间限制，对其进行了拓展，评估了四种能够解决具有中间设施的时间限制下的混合容量路径问题，利用启发式算法求解最小车队数量和最小总成本。随后他们 [8] 又改进了局部搜索算法，快速生成大型路网的局部最优解，加快了启发式算法的求解速度。Mofid-Nakhaee等人 [9] 研究了使用多隔间车厢收集不同垃圾的清扫车的路线规划问题，以车辆使用成本和弧段遍历成本最小为目标建立了数学模型，并设计了自适应大邻居搜索算法混合鲸鱼优化算法求解。姚文龙等人 [10] 针对清扫车在固定路段上进行周期性工作这一特点，提出一个智能PD型迭代学习控制方法，降低车辆行驶路线跟踪误差，实现高精度路径跟踪。Zhang等人 [11] 为了实现室内区域的清扫，设计了室内扫地机在环境栅格图中，围绕环境边缘旋转向内的螺旋清扫算法，每次遇到死角时，使用A*算法找到从死角到最近需要清扫的栅格，直至每个栅格都被遍历清扫。侯俊等人 [12] 设计了能使无人清扫车在社区、公园等室外道路自主循迹清扫方案，该方案可以使清扫车自主辨别直行路段和交叉口路段，可简便有效地控制清扫车工作。Alan等人 [13] 设计了可用于公共场所清扫的无人清扫车，后续将进行更准确的路径规划和跟踪。Darsana等人 [14] 研究了清洁机器人能通过给定区域或环境内所有点的全局覆盖路径，该清洁路径可以降低重复清扫路线概率，减少车辆转弯次数，使起点和终点间路径最短。季长明 [15] 研发出了针对室外的无人清扫车移动平台，可以替代环卫工人在道路两侧作业，实现对道路两侧停车位之间垃圾的清扫，同时也可以对同侧停车位与停车位间的垃圾进行清扫。张周平 [16] 研究了N3类大型清扫车，能够识别道路上垃圾种类和分布情况，根据道路清洁度实时规划清扫车行驶速度和上装执行器行为。刘志忠 [17] 设计一种可以在大面积公共区域工作的无人清扫车，建立了清扫车的运动学模型，能够智能避开障碍物，利用田埂法在栅格地图中实现了全局路径的遍历。Yang等人 [18] 基于虚拟现实技术构建了用于自动驾驶清洁卡车的3D虚拟无人驾驶车辆测试系统，在系统中实现了人机交互，车辆避障，完成了交通信号灯的识别和十字路口识别等虚拟场景的无人驾驶测试。本文立足于程朝中等人 [19] 研究的基础上，深入分析无人清扫车的工作过程，完善了其数学模型，并改进其求解算法。

本研究的主要工作如下：(1) 建立了考虑中间设施点和容量限制的无人清扫车路线优化模型；(2) 根据问题特征设计了一个二级模拟退火算法；(3) 利用MATLAB语言实现算法，并基于经典的Sinoux Fall网络，验证了新方法的有效性。

2. 无人清扫车路径优化模型

本节首先介绍建立数学模型所需的相关参数，然后给出考虑中间设施点和容量限制的无人清扫车路线优化模型。

2.1. 参变量介绍

A表示网络中所有清扫弧段(需要进行清扫作业的街道)构成的集合。

$a\in A$ 表示集合A内的一条弧段。

V表示无人驾驶清扫车集合。

$v\in V$ 表示集合V内的一辆无人驾驶清扫车。

$A_v$ 表示清扫车v最终遍历的清扫弧段构成的有序集合，其元素顺序表示车辆v的服务顺序。

$n_v$ 表示集合 $A_v$ 内有向弧段的个数。

$x_{a,v}\in \left\{0,1\right\}$ 是一个决策变量。如果车辆v清扫弧段 $a\in A_v$ ，则 $x_{a,v}=1$ ；否则 $x_{a,v}=0$ 。

$y_{a,v}\in \left\{0,1,2,\cdots ,n_V\right\}$ 也是一个决策变量。当 $y_{a,v}>0$ 时，其值代表弧段a在集合 $A_v$ 内的序号；而 $y_{a,v}=0$ 表示 $a\notin A_v$ 。

$r_a$ 表示弧段a上所需清扫的垃圾量。

$c_a^0$ 表示无人清扫车进入弧段a时的车内垃圾量。

$c_a^1$ 表示无人清扫车离开弧段a时的车内垃圾量。

$c_v$ 表示清扫车v的最大垃圾装载量。

$z_a\in \left\{0,1\right\}$ 为决策变量，指示清扫完弧段a后清扫车是否需要倒垃圾。

$t_{a,b}^0$ 表示从弧段a行驶到弧段b，中间不需要倒垃圾的最短行程时间。

$t_{a,b}^1$ 表示从弧段a行驶到弧段b，中间需要去垃圾站倒垃圾的最短行程时间。此处最短行程时间包含从弧段a到垃圾站和从垃圾站到弧段b两部分。如有多个垃圾站备选时，选择行程时间最短的垃圾站。

$w_{a,b,v}\in \left\{0,1\right\}$ 是决策变量。如果车辆v相继清扫弧段a和弧段b， $$ 值为1，否则为0。

$t_a^0$ 表示清扫完弧段a，不需要倒垃圾便返回车场或去清扫另一个弧段的行程时间。

$t_a^1$ 表示清扫完弧段a，需要先去倒垃圾，然后返回车场或去清扫另一弧段的行程时间。

$t_{a,depot}^1$ 表示弧段a是最后一个清扫弧段时，从弧段a先去倒垃圾然后回到车场的行程时间。

$t_{depot,b}^0$ 表示弧段b是清扫车的第一个清扫弧段时，从车场到弧段 的行程时间。

$h_a\in \left\{0,1\right\}$ 为指示变量，其值为1表示弧段a是最后一个清扫弧段。

$j_b\in \left\{0,1\right\}$ 为指示变量，其值为1表示弧段b是第一个清扫弧段。

2.2. 数学模型

基于上述参变量，可以构建如下无人清扫车路线优化模型，其目标函数为：

$\min \underset{a\in A}{{\displaystyle \sum }}\left[\left(1-z_a\right)t_a^0+z_a{t}_a^1+h_a{t}_{a,depot}^1+j_b{t}_{depot,b}^0\right]$ (1)

目标函数(1)表示最小化所有清扫车总的非服务时间。非服务时间指的是车辆经过无清扫任务的弧段的时间或途径清扫弧段但不实施清扫作业的旅行时间。非服务时间会在以下四种情况的最短路径中出现：一是车场到第一条清扫弧段的最短路径；二是两条相继需要清扫的弧段之间的最短路；三是清扫途中需要倒垃圾时，前一条弧段到垃圾站的最短路以及垃圾站到后一条清扫弧段的最短路；四是结束工作从最后一个清扫弧段到垃圾站，再从垃圾站到车场的最短路。

相关的约束条件包括：

$\underset{a\in A}{{\displaystyle \sum }}{x}_{a,v}=n_v,\forall v\in V$ (2)

$\underset{v\in V}{{\displaystyle \sum }}{x}_{a,v}=1,\forall a\in A$ (3)

$n_v\ge y_{a,v}\ge x_{a,v},\forall a,v$ (4)

$x_{a,v}=\{\begin{array}{l}0,\text{if}{y}_{a,v}=0\hfill \\ 1,\text{otherwise}\hfill \end{array},\forall a,v$ (5)

$x_{a,v}+x_{b,v}=\{\begin{array}{l}0,\text{if}{y}_{a,v}=y_{b,v}\hfill \\ 2,\text{if}{y}_{a,v}\ne y_{b,v},y_{a,v}>0\text{and}{y}_{b,v}>0\hfill \\ 1,\text{otherwise}\hfill \end{array},\forall a,b,v$ (6)

$r_a+c_a^0=c_a^1,\forall a\in A$ (7)

$c_a^1\le \underset{v\in V}{{\displaystyle \sum }}{c}_v{x}_{a,v},\forall a\in A$ (8)

$w_{a,b,v}=\{\begin{array}{l}1,\text{if}{x}_{a,v}+x_{b,v}=2\text{and}{y}_{a,v}+1=y_{b,v}\hfill \\ 0,\text{otherwise}\hfill \end{array},\forall a,b,v$ (9)

$c_b^0={\displaystyle {\sum }_v{\displaystyle {\sum }_a{w}_{a,b,v}{c}_a^1\left(1-z_a\right)}},\forall b$ (10)

${\displaystyle {\sum }_v{\displaystyle {\sum }_a{w}_{a,b,v}}}\le 1,\forall b$ (11)

${\displaystyle {\sum }_v{\displaystyle {\sum }_a{w}_{a,b,v}}}\le 1,\forall a$ (12)

$t_a^0={\displaystyle {\sum }_v{\displaystyle {\sum }_a{w}_{a,b,v}{t}_{a,b}^0}},\forall a\in A$ (13)

$t_a^1={\displaystyle {\sum }_v{\displaystyle {\sum }_a{w}_{a,b,v}{t}_{a,b}^1}},\forall a\in A$ (14)

${\displaystyle {\sum }_v{\displaystyle {\sum }_a{w}_{a,b,v}}}+h_a=1,\forall a\in A$ (15)

${\displaystyle {\sum }_v{\displaystyle {\sum }_a{w}_{a,b,v}}}+j_b=1,\forall b\in A$ (16)

$x_{a,v},w_{a,b,v},z_a,h_a\text{and}{j}_b\in \left\{0,1\right\}$ (17)

$y_{a,v}\in \left\{0,1,2,3,\cdots ,n_V\right\}$ (18)

上述约束中，约束(2)计算了每辆无人清扫车所服务的弧段个数。约束(3)限制了每条弧段必须且只能被一辆无人清扫车服务。约束(4)表示变量 $y_{a,v}$ 的取值范围。约束(5)表示变量 $y_{a,v}$ 与 $x_{a,v}$ 之间存在的关联关系。约束(6)进一步明确两条清扫弧段之间变量 $y_{a,v}$ 与 $x_{a,v}$ 的关系。约束(7)表示车辆清扫一条弧段后的容量变化情况。约束(8)表示车辆垃圾装载量需要小于等于其最大容量。约束(9)表示如何由变量 $y_{a,v}$ 与 $x_{a,v}$ 推出 $w_{a,b,v}$ 。约束(10)表示在垃圾场倾倒完垃圾后，其剩余可装载垃圾容量恢复到最大值；如果清扫车不去倾倒垃圾就服务下一条弧段，车内垃圾量不变。约束(11)和(12)表明两条需清扫弧段被相继清扫的可能性。约束(13)和(14)表示当车辆v相继服务a和b两弧段时， $t_a^0$ 和 $t_a^1$ 可用 $t_{a,b}^0$ 和 $t_{a,b}^1$ 表示。约束(15)和(16)分别给出了变量 $w_{a,b,v}$ 与 $h_a$ 及变量 $w_{a,b,v}$ 与 $j_b$ 之间的依存关系。约束(17)和(18)限制了各个决策变量的取值范围。

3. 模拟退火算法

3.1. 模拟退火算法简介

模拟退火算法(Simulated Annealing—SA)来源于固体退火原理，将固体加温至足够高，再让其缓缓冷却。加温时，固体内部粒子随着温度升高呈无序状态，内能增大。冷却时，粒子逐渐呈有序状并在每个温度下都达到平衡状态。最后在常温时达到基态，内能减为最小。SA算法最初由Metropolis等人在1953年提出，由于固体物质的退火过程与一般组合优化问题具有极大的类似性，1983年Kirkpatrick等人成功将模拟退火算法引入组合优化领域。与邻域搜索算法类似，SA算法是一种基于概率的寻优算法，用来在一定时间内在一个很大的空间里搜索问题的近似最优解。模拟退火算法从一个较高的温度出发，利用降温参数使温度不断下降，直至达到最低温度，利用模拟算法求得的解与初始值无关。与其他启发式方法相比不同的是，SA算法可以按照一定的概率接受劣质解，即能有效的以一定概率性跳出局部最优而趋近于全局最优。接受劣解的概率取决于当前温度和降温速度，温度越高接受劣解的概率越大。当初始温度足够大且冷却速度很慢时，算法已在理论上被证明可以以概率1收敛到全局最优；否则，算法将收敛到局部最优。

模拟退火算法从初始解和初始温度开始，对当前解重复进行“产生新解 → 计算目标函数差 → 接受或舍弃新解”的迭代。根据Metropolis准则，模拟退火算法以一定的概率接受新解。用 $\Delta Y$ 表示新解对应的目标函数值减去当前解对应的目标函数值的差值。在某一温度下，如果 $\Delta Y<0$ ，则接受新解作为当

前解；如果 $\Delta Y>0$ ，则以概率 ${\text{e}}^{-\frac{\Delta Y}{T}}$ 判断是否接受新解，T表示当前温度。在区间[0, 1]上生成一个均匀分布的随机变量 $\theta$ ，若 ${\text{e}}^{-\frac{\Delta Y}{T}}>\theta$ ，则接受新解；否则，保持当前解不变。当前温度T越大，接受新解的概率

越大，算法能够跳出当前局部最优向全局最优靠近；当前温度 越小，接受新解的概率越小，算法大概率停留在当前局部最优。

3.2. 模拟退火算法求解流程

模型(1~18)属于非线性整数规划模型，当路网规模很大时，其求解难度较高，使用现有商业软件直接求解的效率不高。因此，下面将根据问题和模型解的特征，基于经典的模拟退火算法，设计了一个对应的启发式求解方法。算法的基本思路如下：首先，以各个清扫车分配的需清扫弧段数量均衡为原则，为每辆无人清扫车分配需要清扫的弧段，并根据垃圾承载量确定垃圾站位置，确定清扫的初始线路；其次，通过将无人清扫车的路线两两组合，形成新路线，利用模拟退火算法对其加以优化；最后，利用模拟退火算法对单辆车的清扫路线加以优化，从而获取最终的车辆清扫路线。

基于模拟退火算法的启发式算法步骤如下：

步骤1：生成初始可行解。首先，将集合A内的清扫弧段尽量平均地分配给每辆无人清扫车，得到 $\left|V\right|$ 个有序的清扫弧段集合 $A_v,\forall v\in V$ 。其次，累计弧段垃圾量标记垃圾站位置，并确定行驶时段最短的垃圾站。然后，搜索车场到第一个清扫弧段的最短路径、联接清扫弧段的最短路径、到垃圾站的最短路以及清扫完最后一个弧段倾倒垃圾再返回车场的最短路径。最后，将上述最短路径添加至对应位置，生成每辆车的具体行驶路线 $A_r$ ，并计算其目标函数值 $z\left(A_r\right)$ 。每辆车 $v\in V$ 的行驶路线 $A_r$ 都对应一个清扫弧段集合 $A_v$ 。

步骤2：第一级SA算法，将无人清扫车的路线合成并优化。

步骤2.1：初始化参数。第一级初始温度 $T_s$ ，降温系数 $\alpha \in \left(0,1\right)$ ，终止温度 $T_e$ ，当前温度最大迭代次数 ${\beta }_{\max }$ 。令当前温度 $T:=T_s$ ，当前迭代次数 $\beta :=0$ 。两两组合步骤1得到的单车路线，以合并后的双车路线为初始解。

步骤2.2：对所有车辆进行车辆间的邻域搜索操作。对于任意一个双车路线 $A_{r1,2}$ ，交叉变换 $A_{r1,2}$ 对应的清扫弧段集合 $A_{v1,2}$ 中的清扫弧段， $A_{v1,2}$ 更新为 ${A^{\prime }}_{v1,2}$ 。确定垃圾站位置，并搜索需要的联接弧段并将其插入对应位置，生成新的双车路线 ${A^{\prime }}_{r1,2}$ 。

步骤2.3：计算双车路线 $A_{r1,2}$ 和 ${A^{\prime }}_{r1,2}$ 的目标函数值 $z\left(A_{r1,2}\right)$ 、 $z\left({A^{\prime }}_{r1,2}\right)$ 。如果目标函数值下降，即 $\Delta Y=z\left({A^{\prime }}_{r1,2}\right)-z\left(A_{r1,2}\right)<0$ ，则接受新解；否则，以一定概率接受劣解，即在区间[0, 1]上生成一个均匀分布的随机变量 $\theta$ ，若 ${\text{e}}^{-\frac{\Delta Y}{T}}>\theta$ ，则接受新解；否则，保持当前解不变。当前温度 越大，接受新解的概率越大。

步骤2.4：令 $\beta :=\beta +1$ 。如果 $\beta >{\beta }_{\max }$ ，则以当前解为最优解，再进行降温。令 $T:=T\left(1-\alpha \right)$ 后转步骤2.5；否则，返回步骤2.2。

步骤2.5：判断是否达到终止温度。如果是，则以当前解为最优解，并转步骤2.6；否则转步骤2.2。

步骤2.6：以服务时间平均为原则，拆分步骤2.5得到的双车路线，生成两条行驶路线，分配给对应的两辆车。

步骤3：第二级SA算法，单辆车路线优化。

步骤3.1：初始化参数，第二级初始温度 ${T^{\prime }}_S$ ，其他参数与步骤2.1相同。以步骤2得到的清扫弧段集合 $A_v$ 为初始解。

步骤3.2：调换 $A_v$ 内任意两条弧段的位置，生成新的有序弧段集合 ${A^{″}}_v$ 。重新确定垃圾站的位置，搜索需要的弧段联接，得到新的行驶路线 ${A^{″}}_r$ ，并计算其目标函数值 $z\left({A^{″}}_r\right)$ 。

步骤3.3：比较变换前后的目标函数值。如果 $z\left({A^{″}}_r\right)<z\left(A_r\right)$ ，则接受其作为当前解；否则，以概率 ${\text{e}}^{-\frac{z\left({A^{\prime }}_r\right)-z\left(A_r\right)}{T}}>\theta$ 接受劣解。

步骤3.4：令 $\beta :=\beta +1$ 。如果 $\beta >{\beta }_{\max }$ ，则以当前解为最优解，令 $T:=T\left(1-\alpha \right)$ 并转下一步3.5，否则转步骤3.2。

步骤3.5：如果 $T<T_e$ ，则输出结果并结束算法；否则转步骤3.2。

4. 算例分析

本节利用图1所示经典的Sinoux Fall网络，结合特定案例来说明文中第3节所设计的模拟退火算法的可靠性。利用MATLAB R2022b程序语言编写算法，使用的计算机处理器为Intel(R) Core(TM) i5-8265U CPU。算法设定的参数如下：第一级初始温度T_s = 1000，第二级初始温度T_s = 10,000，降温系数α = 0.005，终止温度T_e = 1，第一级SA算法最大邻域搜索次数为2，第二级SA算法的最大邻域搜索次数为6。

该网络具有24个节点，76个弧段，弧段上的数字为弧段的标号。将SinouxFall网络的数据转化清扫车需要的数据，如表1所示。假设图1中所有弧段都需要被清扫，节点19为车场，节点3和节点16为垃圾站。使用两辆相同的无人清扫车执行清扫任务，垃圾箱容量为30升(L)，倒垃圾的速度为3 L/m，空驶时间单位取秒(s)。

Figure 1. Sinoux Fall Network

图1. Sinoux Fall网络

Table 1. Data on sweepers corresponding to the Sinoux Fall network

表1. Sinoux Fall网络对应的清扫车数据

表1中第1列表示两节点之间的对向弧段，可以看出两条对向弧段上的垃圾量和空驶时间相同，第2列表示弧段上的垃圾量，第3列表示弧段的空驶时间，规定执行清扫任务所需的服务时间为空驶时间的1.5倍。

运行上节所设计的模拟退火算法，可得到一组初始路线，其总行驶时间为1310 s，其中服务时间为471 s (该值为定值)，非服务时间为839 s。非服务时间大于服务时间，这是因为初始路线是通过随机分配服务弧段所导致，分配到一辆车的服务弧段之间的距离较远，造成空驶时间较长。经过两次优化，车辆的总行驶时间大幅度下降，计算结果如表2所示。第一级SA算法的求解结果与初始路线相比优化了约35%；第二级SA算法的求解结果与第一级SA算法的解相比优化了约13%，而与初始解相比优化了约44%。第一辆清扫车的清扫时间、非清扫行驶时间和倾倒垃圾时间分别为237 s、121 s和17.7 s；而第二辆清扫车的清扫时间、非清扫行驶时间和倾倒垃圾时间分别为234 s、114 s和14.9 s。计算上述算例，程序所需运行时间约6秒。

Table 2. Total vehicle running time during the iteration (time in minutesm)

表2. 迭代过程中的车辆总运行时间(时间单位：分钟m)

第二级SA算法优化后的车辆行驶路线如表3所示。为了更清晰地表现出每辆无人驾驶清扫车行驶路线的特点，给出两辆无人驾驶清扫车的行驶路线简图，如图2所示。实线表示有清扫任务的弧段，虚线表示空驶弧段，弧段上的数字表示车辆经过的顺序。为使车辆行走路线更加清晰，用虚拟节点表示车场和垃圾站，将其与原始路网中的节点区分开。并用虚拟弧段连接虚拟节点和原始路网节点，虚拟弧段上的垃圾量和行驶时间为0。通过车辆行驶简图可知，清扫过程中快要到达垃圾箱容量时，车辆前往最近的垃圾站倾倒垃圾；访问完最后一个服务弧段，也选择了最近的垃圾站倾倒垃圾，整个工作过程都没有超过车辆最大容量，选择的垃圾站也是距当前清扫车位置最近的垃圾站。

Table 3. Optimised vehicle routes

表3. 优化后车辆行驶路线

注：弧段序列中加粗且带下划线的项表示有清扫任务的弧段；带波浪线的项表示在车场和垃圾站处添加的虚拟弧段。

Figure 2. Specific sweeping routes for both vehicles

图2. 两辆车的具体清扫线路

5. 结论

本文研究了无人驾驶清扫车的路径优化问题，着重考虑了垃圾站位置和无人清扫车的容量限制等现实情况，建立了无人驾驶清扫车的路径优化模型。新模型不仅能够详细刻画每辆无人驾驶清扫车的行驶路线，而且将垃圾站的位置、垃圾站选择以及车辆空驶路线考虑进全局行驶路线中，如访问垃圾站的往返路线。然后利用已知路网进行求解，得出的行驶路线符合日常工作要求，该研究具有较高的实用价值，可直接应用于现实场景。研究还设计了求解上述模型的“双车 → 单车”两级模拟退火算法，该算法能在较短的时间求解出每辆无人驾驶清扫车在已知路网中行驶时间最短的行驶路线。通过实例分析发现，利用新算法得到的最优解与初始路线相比，无人清扫车总行驶时间可大幅降低高达44%。研究可为无人驾驶清扫车的推广应用提供有力的理论和技术支持。

无人驾驶清扫车路径优化问题是一个实际应用性很强的问题，该问题的多变性使得研究的方面有很多，基于本文的研究，未来潜在研究包括：1) 无人驾驶清扫车路径问题可以有很多拓展类型，如多车型、任务弧可拆分、弧上垃圾量不确定等。这些拓展问题都有一个共同的约束条件，即容量约束，但是一些额外的约束条件各有不同，能处理的实际问题是不一样的。因此如何将不同的拓展问题应用到实际，并进行综合考虑，值得深入研究。2) 本文研究的无人驾驶清扫车路径问题是属于静态问题，清扫车行驶速度固定，任务弧上的垃圾量固定，而实际的无人驾驶清扫车路径问题是属于动态问题。车辆行驶速度会受到道路交通环境的影响，弧上垃圾量会受到季节影响和道路交通量影响。例如道路交通繁忙的时间段垃圾会变多，秋季路边树叶垃圾多，春季路边树叶垃圾少，因此动态的问题需要进一步研究。