路径规划典型算法篇（1）

1.AGV系统地图建模

实际应用当中，AGV的工作路径随着不同工厂的环境条件和规划可能各不相同。

图1.1中AGV轨道模型，图中圆圈内的数字代表该位置的站点号，直有向线代表直线轨道，弯曲的有向线代表半圆轨道，线上的数值代表其长度或者半圆的半径。图1.1所示显然为一个有向赋权图，记为G（V，E），V为图中所有站点的集合，显然非空，E为任意站点Vi到另一站点Vj的边的集合。

2.AGV调度问题研究

2.1单个AGV路径规划算法

单个AGV的调度问题可以简化为AGV的路径规划问题，即等价为求最短路径问题。

Dijkstra算法是一种用于计算有向图中一个节点到其他所有节点最短路径的典型图形搜索算法。其时间复杂度O（V2+E）～O（VlgV+E）取决于是否采用最小优先级队列。

实现的具体方法，即当不用队列而用数组实现时为O（V2），用二叉最小堆来实现时为：

O（（V+E）lgV），用Fibonacci堆来实现时为：

O（VlgV+E）。采用Fibonacci堆使算法的运行时间性能相比于O（V2）虽然有一些提高，但是编程时由于其常数较大，多数时候会发现其实际运行速度并没有明显的提高，并没有多大的效率优势。算法具体步骤为：

1）分组初始化，集合S中只有源节点v0，T由除V外的剩余节点组成。根据图的信息初始化各个节点的邻接关系和权值。

2）从T中选取与v0有邻接关系且权值最小的顶点Tp，把Tp又加入到S中（v0到Tp的最短路径值即为其权值大小，最短路径为v0Tp）。

3）以Tp为中间节点，考察T中与Tp邻接的节点。如果从源节点v0经过Tp到T中节点的距离比不经过Tp时距离短，则修改T中已比较过的顶点的路径值为经过Tp的路径。

4）判断T是否为空，或者源顶点到目的顶点的最短路径是否已经找到，若没有则

重新返回步骤2再次寻找。否则，推出循环，算法结束。

2.2 多个AGV路径规划算法

协调各个AGV之间能够无碰撞地高效完成其工厂里的作业任务，是多AGV调度系统的主要任务。相向冲突、站点冲突、拐角冲突、赶超冲突是多AGV运行过程中常见的几种基本冲突。多AGV的任务调度问题的典型的有效方法有以下几种：

（1）基于时间窗的AGV无碰撞路径规划

针对每段路径引入时间窗来指示该路段在某段时间是否已经被AGV占用，根据接受任务的优先级依次分配空闲的AGV，并利用算法选择最优路径，并产生各路径的时间窗。

（2）混合区域控制模型调度方法

通过对AGV的工作空间进行按不同的区域建模，AGV作业于不同区域内，且一个区域中最多只有一台AGV位于其中。

（3）线段网络控制调度算法通过把AGV小车的路线分为可进行控制的若干条路段，当小车将要或已经在一个路段上行驶时，AGV调度系统将这个路段及其终点分配给该AGV，当AGV行驶离开此路段的起始点一定距离后，系统又将该路段释放。

（4）两阶段控制调度算法

将AGV的调度控制系统分为离线路径表的生成和在线交通控制两个模块，其中离线路径表生成模块根据路径网路模型离线生成各结点间的所有路径，而在线交通控制模块根据下达的任务和工作中AGV的运行信息利用路径库中的路径表生成无冲突的最佳路径。

两阶段控制算法，利用已知信息先离线生成路径库，能很好的减少在线阶段的运行负担，提高系统实时性，且分阶段的控制方法使得实现和优化改进更简单。但是该算法生成的不是各结点的k条最优路径，当某个路段堵塞时，又要附加约束条件在线重新生成最优路径，使得效率反而更差。因此提出离线阶段对每个顶点生成k条最短路径集，以改进两阶段控制算法。

3 AGV调度算法算法分析与实现

（1）流程分析

假设AGV任务离线批量下发，本系统基于改进的两阶段控制算法的流程图设计如图3.1所示。正如图3.1所示，路径规划工作大部分静态工作如最优路径的生成等由调度系统离线阶段完成，而系统在线阶段主要负责动态的状态监控和资源的管理以及进行突况处理。突况下如果下位机可以采用一般的等待策略解决，则调度系统只负责路径资源时间窗的更新即可；若发现等待超时，即视为不能解决，则需以当前站点为起点重新为该任务进行路径规划。

在任务下发后，AGV开始执行任务，AGV执行任务过程中的避障策略算法如图图3.2所示。AGV根据调度系统对任务的路径规划，从起点开始不断检测障碍物和冲突以确定是否进行下一步。当遇到冲突时，首先自行进行等待处理，若调度系统发现等到时间过长而超时会对任务进行重新路径规划并发送任务的更新命令，AGV接收到该命令后会终止当前流程重新任务的执行。同时，AGV会定时不断的向监控调度系统更新AGV自身的状态信息，供调度系统决策使用。

结论

路径规划典型算法篇（2）

中图分类号：TP301 文献标识码：A 文章编号：1672-3791（2014）01（c）-0238-03

随着需求的增长，市民出行时除路程外还将其他要素纳入考虑，比如驾驶过程中的舒适度体验，行程的安全性，路段的拥挤程度等等。所以把市民出行时的路径规划问题抽象成多目标优化模型更加符合实际[1]。在实际应用中，用户需要在可忍受的时间内获得一组高质量的解。因为用户最满意的不一定是算法定义的最优解，而是最符合现实情境要求的解，所以合理的做法是提供多个选择，让用户根据实际情况进行决策。上述背景对算法提出了两个基本要求，即高效性和解的多样性。在一个城市内进行最优路径搜索时，所涉及到的节点数高达几千多个，而路径规划问题是典型的NP难问题，一些精确算法，如动态规划，分枝定界，其计算量呈指数增长[2]。而经典Dijkstra算法在节点数比较多时，消耗的时间和存储空间都十分巨大，所以应用也十分有限。近几年来，遗传算法在解决复杂的多目标优化问题中有成功应用，将其应用于大规模的多目标路径规划问题开始成为学者们研究的热点。相较于前面提到的几种算法，遗产算法在处理大规模路径规划问题时更具优势，更加容易实现解的多样性[3]。本文在遗传算法的传统框架上进行优化，用贪心算法设计初始种群，将压缩映像引入适应度标定中并且改进了更新策略，从而将算法更好地植入模型中，提高了计算效率。

1 模型建立

本文设定三个目标，，，分别代表最小路径长度，最小事故发生率和最小路径拥挤度，建立多目标路径规划问题的数学模型：

（1）

（2）

（3）

（4）

其中，为全体有效路径；为路径的路段总数。为路径中第个路段的长度；为路段的事故发生率；为路段的拥挤程度，且。求解该模型的目的在于找到一个非劣解集，协调各个目标之间的矛盾，达到目标间的平衡[3]。

2 算法设计

在60年代中期，Holland提出遗传算法，模仿达尔文的生物进化论，将适者生存的概念引入算法设计中，其主要组成部分包括初始种群的产生，个体适应度标定，选择算子，交叉算子和变异算子[4]。本文对传统遗传算法进行了三处改动：（1）用贪心算法设计初始种群；（2）将压缩映像法引入适应度标定中；（3）改进更新策略。

2.1 初始种群的生成

初始种群最常用的是逐次递进法，节点从起始点开始深入，逐层递进，不满足条件时，逐步退回上一个节点，再次逐层深入直至到达终点。还有随机节点生成法，由计算机随机生成一列节点，检验是否构成有效路径。与上述两种方法的盲目式搜索相反，利用贪心算法能够在起点和终点唯一确定一条路径。

算法步骤是这样的：决定起点的下一个节点时，考察其邻节点到终点的距离，两点间的距离由坐标计算可得，选择离终点最近的节点，依此类推直至到达终点。所以建立每个节点的二维坐标信息是算法实现的重要前提，节点的坐标能简化算法设计，提高搜索效率，并且通过现有的科技手段很容易获得，既不占用过大的存储空间，也不增加数据结构的设计的难度。所以路径搜索时引入节点的坐标有很大的价值。

为生成大量初始路径，将贪心算法与随机节点生成法结合，由计算机随机生成个节点，，1，2，…，。是给定常量，表示起点，表示终点。在和间运用贪心算法生成连通道路，最后整合成从起点到终点的通路。需要注意的是，该路径可能存在回路，必须使用紧缩算子消除回路[5]。

2.2 压缩映像在适应度评价中的应用

权重法是将多目标优化转化成单目标最简单和直接的手段，其算法实现相当容易，只需为每个目标赋予权重系数，但存在这样一个缺点：不同性质的目标之间单位不一致，单位小的目标函数值对结果影响微弱，比如本文提到的事故发生率。为改善这一不足，作者引入模糊数学领域中的压缩映像法[6]，将三个目标的度量纳入一个体系中。

以第一个目标为例，假设有一列染色体，，，则第一个目标函数值的压缩值为：

（5）

同理可计算和。经过压缩后，，，都落在中，完成了单位的统一。设给三个目标赋予的权重分别为，，，适应度的计算公式为：

（6）

2.3 更新策略

设为第代父代种群，为经交叉生成的子代种群，种群规模均为。传统的遗传算法通过选择算子从选出一组染色体进入池，交叉生成子代，经变异后直接作为新种群继续进化[7]。这种做法会流失父代中的优秀基因，从而降低收敛效率。结合精英保留策略和NSGA-Ⅱ算法中的更新策略[8～9]，本文采用如下方法：合并父代和子代组成规模为的，剔除中重复的染色体，根据适应度从大到小排列，选取前条染色体进入新种群，若不足，剩余个体从中随机产生。在更新过程中，子代个体并不比父代更具被选入的先天优势，两者根据适应度大小公平竞争，获得继续进化的机会。相较经典的“精英保留”策略，它扩大了父代染色体参与竞争的数量，使更多优良个体被保留，相较NSGA-Ⅱ，它的计算量要小得多。其中删除重复个体的操作维持了种群在进化过程中的多样性，避免算法陷入早熟收敛。

2.4 几个关键算子

选择算子使用普通的赌方式，在文献[10]中有详细介绍。交叉算子采用常用的一点交叉，但如果随机选出的染色体，没有共同节点时，则搜索二者中距离最近的节点，（距离由坐标计算可得），使用前文提到的贪心算法构造连通路径，接着仿照一点交叉法完成染色体交叉，得到两条新的染色体。

设计变异算子时，首先由计算机随机生成两个节点，通过贪心算法构造这两个节点间的连通路径替代原染色体中的路段。

无论是交叉算子还是变异算子，生成的新染色体都有可能产生回路，和初始种群的产生一样，也需要消除路径中的回路。强调一点，在本文的交叉算子和变异算子中，节点的坐标信息发挥了很大的作用，笔者认为在解决多目标路径规划问题时，有必要将节点的坐标进行充分利用。

2.5 算法流程

step1：产生初始种群。

step2：计算个体适应度并判断是否满足终止条件；若满足，输出一组最优解，否则转入step3。

step3：用选择算子从中选出条染色体进入池。

step4：对池中的染色体通过交叉算子进行随机，产生种群。

step5：合并，组成，用本文设计的更新策略获得条染色体。

step6：对更新后的种群应用变异算子，结果作为新种群，返回第二步。

3 试验结果及分析

3.1 前5条最优解

利用几何画板5.0绘制出33个节点75条边的无向图，节点坐标和路段长度由几何画板获得，事故发生率和拥挤度由计算机随机产生，构造出验证遗传算法效果的算例，如图1所示。

算法在MATLAB7.0环境下编译。种群规模取40，迭代次数取200，交叉率取0.8，变异率取0.08，路程，事故发生率，拥挤程度的权重系数分别为0.4，0.3，0.3，求得从节点1到节点33的在多目标规划下的前5条最优解，结果见表1。从表1中可以看出目标之间的相互制约关系。由于本文选取的算例规模比较小，所以可以用Dijkstra算法获得算例在仅考虑一个目标下的精确的最优值，见表1中最后一行。从表中可以发现没有一条路径能同时取得单目标下最小值，这证明求解多目标优化模型的关键在于协调和平衡几个目标。值得一提的是，为考察本文使用的更新策略的作用，将传统方法即把交叉变异后的种群直接作为进化的新种群的方式和改进后的方法对比，经试验发现，用传统方法得到的最后一代几乎全是路径1，而后者却得到了超过30条互不相同的路径。实验结果表明，该遗传算法在解决解的多样性问题上效果很好，扩大了用户决策的空间。（如表1）

3.2 解的收敛性

图2是迭代200次中种群的路程平均值变化曲线。从图中可以看出，最初种群的路程平均值比较大，经过50代后开始逐渐趋向平稳，在100代时因变异算子产生小的波动，最后稳定在18.7左右。曲线表明算法是快速收敛的。

3.3 解的有效性

我们知道在多目标路径规划问题中，绝大多数情况下无法找到一条路径同时取得三个目标的最优值。现在假定这条路径存在，那么非劣性解越接近它，表明解的质量越好[11]。基于这种思想，定义任意一条有效路径到虚拟的最优路径的距离，记这条虚拟路径的三个目标函数值为，，，任意有效路径函数值为，，。计算两者距离的公式如下：

（7）

公式（7）给出了比较两条路径优劣的指标。那么用产生初始种群的算法随机生成一条有效路径，挑战表中的5条最优解，如果最优路径到虚拟路径的距离小于随机路径到虚拟路径的距离，则称这个最优解是成功的，否则失败。试验200次，5条最优路径的成功率分别为100%，98%，99.5%，99%，91%。为避免算法的偶然性，对算例求解10次，其最优解的成功率均在90%以上，说明这5条最优解的性质都不错，证明遗传算法是有效的。

4 结语

本文采用遗传算法解决大规模的多目标路径规划，并对传统的遗传算法进行改进，使之具备更好的计算性能。在具体试验中，该算法体现了良好的收敛性和解的多样性，同时保证了最优解的有效性。为缓解种群陷入早熟收敛的压力，本文改进了传统的更新策略，但尚不明确它是否会带来意想不到的副作用。遗传算法的研究仍将集中在两方面：一是改进交叉和变异算子，防止种群早熟或陷入局部最优解[12]；二是提高算法的搜索能力，减少求解时间。

参考文献

[1] 潘斌斌.多目标路径规划问题的算法综述[J].重庆工商大学学报：自然科学版，2012，29（5）：78-84.

[2] 郎茂祥.基于遗传算法的物流配送路径优化问题研究[J].中国公路学报，2002，15（7）：77-79.

[3] 梁晓辉，吴威，赵沁平.大规模真实地形数据中的全局路径规划方法―― 基于遗传算法的研究[J].计算机研究与发展，2002，39（3）：301-306.

[4] 阮宏博.基于遗传算法的工程多目标优化研究[D].山东：大连理工大学土木工程系，2007.

[5] 刘旭红，张国英，刘玉树，等.基于多目标遗传算法的路径规划[J].北京理工大学学报，2005，25（7）：613-616.

[6] 宋晓秋.模糊数学原理与方法[M].徐州：中国矿业大学出版社，2004.

[7] 肖晓伟，肖迪，林锦国.多目标优化问题的研究概述[J].计算机应用研究，2011，28（3）：805-808，827.

[8] 刘旭红，刘玉树，张国英，等.多目标优化算法NSGA-II的改进[J].计算机工程与应用，2005（15）：76-78.

[9] 关志华.非支配排序遗传算法（NSGA）算子分析[J].管理工程学报，2004（1）：56-60.

路径规划典型算法篇（3）

中图分类号：TP301.6

Dijkstra算法是一种经典的求最短路径的算法。所谓最短路径问题是指：从带权图的某一顶点出发，找出一条通往另一顶点的最短路径。最短路径问题是GIS应用中研究的一个重要内容，在事故抢修、交通指挥、应急管理、GPS导航等应用中都是必要的功能，所以最短路径分析功能一般会作为基本功能集成到GIS平台中，如ARCGIS，SuperMap。多数系统解决最短路径问题采用Dijkstra算法为理论基础，它非常适合在带权有向图中求解单源单目的最短路径问题。

1 经典Dijkstra算法

1.1 算法思想

Dijkstra算法是典型最短路算法，用于计算一个顶点到其他所有顶点的最短路径。其基本思想是，逐步产生最短路径。首先求出从某一顶点出发到其他顶点长度最短的一条路径，然后参照它求出长度次短的路径，依次类推，按路径长度的递增次序，直到计算出该顶点到其他所有顶点的最短路径。

为了实现该算法，设带权图G=（V，E），V为图中顶点的集合，E为边或者弧的集合。设集合S存放已经求出的最短路径的顶点，设集合T为除了S以外的其他顶点，引入辅助数组dist[]，它的每一个分量dist[i]表示当前找到的从出发点到顶点i的最短路径长度。

算法的具体步骤：

（1）初始化：S={V0}；T={V-S}；Dist[j]=Edge[0][j]；j=1，2，…..n-1，n为图中顶点的个数；

（2）求出最短路径长度：dist[k]=min{dist[i]}，i∈V-S；S=S∪{k}；

（3）修改：dist[i]=min{dist[i]，dist[k]+EDedge[k][i]}对于每一个i∈V-S；

（4）判断：若S=V，则算法结束，否则转到（2）；

初始时，S中仅含有初始顶点V0，每次从V-S中取出具有最短特殊路长度的顶点，将其添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

1.2 算法分析

实现经典的Dijkstra算法需要两个并列的for循环。一个循环用来实现辅助数组的初始化工作，时间复杂度为O（n），第二个for循环是一个二重循环，实现最短路径求解的功能，因为图中所有顶点都要做计算，每个顶点的计算又要对集合S内的顶点进行检测，对集合V-S中的顶点进行修改，所以时间复杂度为O（n2）。算法总的时间复杂度为O（n2），复杂度比较高。

2 Dijkstra算法改进

通过Dijkstra经典算法思想可知，计算从u到v的最短路径时，也计算了u到S中所有顶点的最短路径，但是，S中的某些顶点可能与最终最短路径中的顶点无关，该算法在进行最短路径搜索过程中会涉及到图中所有的顶点，那么图中S的大小直接影响着算法的速度。这直接影响了算法的效率，因为由时间复杂度可看出顶点数量越多所用时间就越长。优化该算法势在必行。

2.1 改进策略

改进的策略用一句话描述就是顶点覆盖，分段进行。通过前面的分析可知，如果能减少算法中集合S中顶点的个数，会减少算法的运行时间。在这借用希尔提出希尔排序的思想，把有向图中的顶点按照某种策略分成若干个小的集合，形成顶点的全覆盖，这样每个集合的数量就比原来少了，但是把他们合起来顶点及关系总数不变，并且要求不同的集合要有一个连接的关键顶点，关键点的确定是计算最短路径的关键。

顶点覆盖划分的方法可根据具体的计算应用决定，比如可以按照区域划分，按关键点划分，按公路、铁路线划分等等。划分的数量不宜太多也不宜太少，应根据实际情况科学分析。划分数量和每个划分中顶点的数量应事宜，划分数量多，重复执行的次数就有可能多；划分的数量少对算法的改进程度不高。确定连接不同集合的关键点和划分策略有关，有时也要进行事先的运算，关键点应该具有这样的性质，是从一个集合区域到另一个集合区域必经的顶点或者就是终点。最短路径的计算结果是每个小集合划分的结果之和得到的。这样改的好处是，既能减少程序运行时涉及的顶点的数量，如果采用邻接矩阵的方式存储带权图，还能节省存储空间。

2.2 算法设计

下面给出改进算法的方法步骤：

（1）根据划分策略，确定顶点所属不同集合Si，i=1，2，3小于等于划分的个数，确定存储表示方法，并建立相应带全图；

（2）把所有关键点放入关键点集合key，并表示关键点所连接的区域信息，并建立拓扑图；

（3）计算关键点集合顶点间的最短路径，并放入专门的数组或数据表中；

（4）计算任意两个顶点间的最短路径，首先判断顶点所属范围，若两个点均属于关键顶点集合，则直接查找步骤四的计算结果数据表，算法执行结束；若属于同一个顶点划分，直接调用Dijkstra算法，转步骤（5），若属于不同的集合，转步骤（6）；

（5）在两顶点所属划分Si范围内，直接调用Dijkstra算法求两点间的最短距离，算法结束；

（6）假定两定点分别属于划分Si和Sj，则两顶的距离等于，u0和v0所属的集合分别为Ti和Tj，那么最短路径的计算有三部分组成，先计算起始结点到与其所在集合Si连接的关键点的最短距离，在计算与Sj相连接的关联点到终点的最短路径，再计算两个关键点之间的最短路径，最后将三部分计算结果相加，即为两定点间的最短路径。

2.3 性能分析

首先该算法是从减少顶点数量的角度对算法进行优化，对经典算法本身的执行没有改动，不论是计算关键结点之间的最短路径，还是计算任意两个顶点之间的最短路径，仍然调用迪杰斯特拉算法，这就保证了算法的可行性。如两个顶点不属于同一区域采用的是分阶段计算最短路径然后相加的方法，减少了计算的复杂性，增强了可理解性和可执行性。

其次关于改进算法的时间复杂度，和顶点集合划分的数量有关。假设带权图中共有n个顶点，有m个顶点集合划分，k为关键顶点的数量。时间复杂度分为以下几种情况：

（1）如果两顶点均属于关键顶点，则只需要到数据表中进行查找，则复杂度取决于关键顶点的数量和查找最短路径所需要的时间。计算关键顶点的复杂度为O（k2），查找路径可以用优化的查找方法；

（2）如果两顶点属于同一个集合划分，复杂度为O（（n/m）2），是没有改进前的算法复杂度的1/m2。

（3）如果两顶点，不属于同一个集合划分，最短路径计算是三部分计算之和，三次调用经典算法，复杂度与第二种情况同，但事件应该略多。

从空间复杂度角度，若采用邻接矩阵的存储表示方法，经典算法需要用n2个存储空间，改进后只需k*（n/m）2，当然增加了存储关键顶点和其最短路径的存储空间，但相比节省的存储空间和优化的时间复杂度，必要的增加还是值得的。

通过对时间和空间复杂度的分析可以看出改进算法可以极大的减少运算量，降低时间复杂度和空间复杂度。

3 改进算法在GIS中的应用

在ArcGIS平台中实现改进算法的应用，在Java环境下利用Arcobject进行二次开发，采用改进的Dijkstra算法思想编写函数，实现最短路径的搜索。

ArcGIS自带的网络分析模块，具有分析矢量数据的功能，只对具有拓扑关系的矢量数据进行分析，所以首先在ARCGIS环境下对地图进行矢量化，然后进行拓扑分析。本文采用的数据是某一地区的地图数据，文件中一共有3572条地理实体记录，共有2826个顶点，通过对地图数据的分析，确定了按照地理区域进行顶点划分的策略，共分成23个区域，共找到72个关键顶点，每个划分的顶点根据地域及关键点的链接，并不十分平均，但是比起总体的数据量，每个集合的规模都小的多。

利用改进算法进行计算时，按照算法思想采用了两个顶点在关键顶点集合、在两个不同顶点划分集合和两个顶点在同一个顶点集合三组不同的数据进行验证。通过和经典的Dijkstra算法运行结果从正确性和运行时间的对比，证明一方面改进的算法进行最短路径搜索的结果和经典算法相同的，另一方面比经典的算法无论从时间上还是从空间上都有一定的提高。如图1所示，两种算法运行时间的对比图。

图1 运行时间对比

4 结束语

本文在分析经典Dijkstra算法的基础上，提出了“顶点覆盖，分段计算”的思想，进行算法的改进。通过对原带权图中顶点进行覆盖划分，减少算法中顶点集合数目，缩小问题的规模，并通过分段计算最短路径以达到降低算法时间复杂度和空间复杂度的目的，经在ArcGIS中二次开发，结果正确实现了预期设想。

参考文献：

[1]殷人昆.数据结构（用面向对象方法与C++语言描述）（第二版）[M].北京：清华大学出版社，2007.

[2]王涛春，齐学梅，赵诚.Dijkstra优化算法及其在电子导游中的应用[J].安徽师范大学学报（自然科学版），2010（33）：525-529.

[3]陈红琳.在ArcGis矢量图中搜寻最短路径的实现[J].北京测绘，2009（02）：16-18.

[4]王华.基于Dijkstra算法的物流配送最短路径算法研究[J].计算机与数字工程，2011（39）：48-50.

[5]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.

路径规划典型算法篇（4）

中图分类号： TP311 文献标识码：A 文章编号：1009-3044（2016）36-0188-04

Increment-dimensional Heuristic Search Motion Planning Algorithm

WU Hong

（Department of Computer Science and Technology， Tongji University， Shanghai 201804， China）

Abstract： For intelligent vehicle motion planning， effective enough is always an important issue. The huge statue-space， high time complexity of the high dimensional search approach is always the bottle-neck of the algorithm. To solve this problem， this paper proposes a new method， increment-dimensional heuristic search algorithm. This method is a stepped-up heuristic search to reduce the searching status and improve the search algorithm execution efficiency. In experiment， the result shows that this algorithm reduces 87% of searching status and executes time is nearly 1/10 of that of the traditional heuristic search method. It is a very good trade-off between execution efficiency and trajectory quality.

Key words： increment-dimensional heuristic search； intelligent vehicle； motion planning； effective； trade-off

1 引言

在智能无人车领域，智能车无人车的行驶安全以及驾驶舒适度一直是一个非常重要的研究问题。而智能无人车的路径规划是这一问题的核心。智能无人车路径规划算法需要在有限的时间内，输出高质量高精度的路径，传输给智能无人车的控制模块、执行模块加以执行。一般的移动机器人路劲规划算法研究的是在高维度的空间里探索出一条路径，相比之下，智能无人车的路径规划则需要考虑车辆动力学模型约束，通常我们需要考虑四维状态。二维状态（x， y），表示车辆的地理坐标，车辆的航向角θ，以及行驶速度v。在四维状态空间里搜素出一条可行路径，是一个计算密集型的任务。与此同时，智能无人车的行驶速度可能很高，因此要求规划算法能够在一个非常有限的时间里给出搜索的结果。

为了解决这一问题，本文给出一种增维启发式路径规划搜索算法。该算法采取一种分阶段，逐步增加搜索维度的方法来生成路径。在每一个阶段，增维搜索算算法选择离车辆当前位置附近的一个区域，增加状态空间维度，进行启发式搜索。因此该算法的输出轨迹是多精度的轨迹。在车辆附近位置，输出轨迹为高维度高精度，充分考虑车辆动力学模型，驾驶舒适度，能耗以及可靠性。而在远处，低维度低精度的轨迹依然可以引导智能无人车的行驶方向正确，充分考虑的地图信息，障碍物信息。从人类正常的驾驶习惯上来说，驾驶员总是对近处的驾驶精度较高，而远处相对较低。该算法充分利用了这一点原理，牺牲了远处的轨迹精度，极大地提高了算法的运行效率。在频繁联系的反复规划中，车辆会一直执行高精度部分轨迹。因此，该算法在运行效率以及输出轨迹质量方面，取得一个非常好的均衡。

为了展示该算法的性能，本文进行了仿真实验。在实验中，智能无人车刚刚进入一个停车场，需要在目标停车位泊车。实验结果表明，相比传统的高维度启发式搜索算法，该算法减少了超过87%的搜索状态，运行性能提高了近10倍。

2 研究现状及文献综述

从20世纪70年代开始，欧美的西方国家开始无人驾驶汽车方面的研究工作，并在智能无人车的控制和商用化方面取得一定进展。在汽车工业非常发达的德国，各大汽车公司都资助或者联合高等院校以开发可在普通道路上行驶的智能无人车。目前，欧盟已启动一个名叫CyberCars的智能无人车项目，以推动智能无人车的研究和各国间智能无人车技术的信息共享。

在20世纪的80年代，我国部分大学开始智能无人车的研究工作，虽然起步较晚也取得一定成果。目前，从事这方面研究工作的 主要是国防科技大学、军事交通学院及清华大学等科研机构。[1-6]

在智能无人车决策模块的相关研究中，最核心的部分是路径规划算法的研究。文献[7]提出一种快速扩展随机树生成算法―RRT （Rapid-Exploring Random Tree）算法。RRT是一种多维空间中有效的路径规划算法。它以一个初始点作为根节点，通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或者进入目标区域，便可以在当前随机树中找到一条从初始点到目标点的路径。文献[8]在RRT算法在自动驾驶汽车以及宇宙空间探测器路径规划上的应用。文I[9]对RRT算法提出优化方法并通过实验，解决了基本RRT算法存在的动态环境中规划路径不稳定的问题，同时提出双向RRT生成算法以及动态步长等优化方法，提高了RRT算法生成初始点到目标点路径生成的速度。然而RRT算法在规划路径的过程中产生的是可行解，而非最优解。文献[10]提出了RRT*算法，RRT算法进行了改进，保证了RRT算法生成解是渐进最优解。然而RRT*算法在时间复杂度上远高于朴素的RRT算法。文献[11]提出了一种RRT*算法加速的方法，通过使用预生成RRT随机树，在使用RRT*_S算法优化当前随机树，构造出与RRT*算法生成随机树本质相同的RRT*_S随机树，从而实现RRT*算法的加速。文献[12]为麻省理工学院将RRT*算法运用于叉车移动路径规划的一次应用实践，并对RRT算法与RRT*算法在实际应用中的结果给出对比分析。

文献[13][14][15][16]给出了2007年美国DARPA智能无人车比赛麻省理工学院（MIT）参赛智能无人车的整体架构，MIT智能无人车的轨迹生成算法，主要是用RRT算法生成可行路径，并对该路径进行平滑，以此为基础生成智能无人车运动轨迹。

文献[17][18][19][20][21][22]主要阐述了状态空间搜索算法，通过估价函数进行启发式搜索以及状态空间搜索剪枝。文献[23]提出了ARA*（Anytime A*）算法，对短时间间隔内连续反复用A*搜素算法进行空间状态搜索这一类状态空间搜索应用场景进行优化。

3 增维启发式搜索算法

增维启发式搜索是一种两阶段的启发式搜索算法。在算法的第一阶段，搜索出一条从车辆当前位置到目标位置的几何最短路的轨迹。在第一阶段的搜索，我们只考虑二维的搜索状态空间（x， y），即车辆的地理坐标。第二阶段，选取第一阶段的路径中的一个点作为本阶段目标点，搜索状态加入车辆的航向角θ，以及行驶速度v，总体状态空间提升到四维，并且考虑车辆动力学模型，在此状态空间下，搜索出一条高精度可执行的车辆行驶轨迹。

3.1 第一阶段搜索

在这一阶段，因为我们只考虑二维状态空间（x， y），即车辆的地理坐标。如果将状态空间离散化，这一搜索问题会退化成一个图论的最短路问题。虽然图论的最短路问题有很多经典成熟的算法。但是在这里还是有一些值得讨论的问题。

3.1.1 栅格随机化

一般地，在执行最短路算法之前，会把状态空间离散化成栅格，然后对栅格做4联通或者8联通处理，但是这种离散化方法会使最短路失去最优解，如图1a、1c所示。

图1 a. 离散化使得几何最短路失解；b. 随机化18联通栅格法；c. 8联通栅格法几何最短路（黑），随机化18联通栅格法几何最短路（红）。

a b c

为了解决这一问题。如图1b所示，算法使用一种随机化18联通的栅格法来离散化空间。即在栅格之间连边的时候，每个栅格除了相邻向相邻8个栅格联通，同时随机向其他10个栅格联通。选取的10个栅格满足与该栅格曼哈顿距离小于7，满足条件的格子约为100个，足以随机化，同时连边长度小于两个栅格长度，也方便计算是否与障碍物碰撞。

3.1.2 最短路算法

在离散化为栅格之后，采用单源最短路算法来计算车辆当前位置到其他位置的几何最短路，虽然单源最短路算法非常的经典成熟，但依旧有值得讨论的地方。

最短路的经典算法是堆优化的Dijkstra算法，该算法时间复杂度为 [O（eloge）]，其中[e]代表离散化后边的数量，然而在稀疏图中，SPFA算法的实际时间复杂度约为[O（e）]，在18随机联通结构的图中效率比价高，因而在本阶段中，我们采用SPFA算法计算单源最短路。

3.2 第二阶段搜索

在第二阶段的搜索中，我们选取第一阶段结果，几何最短路上的一个点来作为目标点，在搜索状态加入车辆的航向角θ，以及行驶速度v，在搜索中充分考虑车辆动力学模型，搜索出一条高精度可执行的车辆行驶轨迹。

3.2.1 启发函数

在启发式搜索过程中，一个强力有效的启发式函数对搜索效率来说至关重要。启发式函数不仅为搜索的实际代价提供了一个下界，同时也是实际代价的一个良好估算，可以引导搜索往正确的方向扩展，并且实现搜索剪枝，在第二阶段的搜索中，使用以下启发式函数。

动力学约束无障碍启发函数，[hnh（x，y，θ，v）]，该函数忽略障碍物信息，考虑车辆动力学模型，在此条件下求出最优的路径。这一启发式函数因为忽略了障碍物信息，只考虑动力学模型，所以可以离线计算、存储，在真实路径规划的过程中查询，计算速度极快。该函数极大的消除接近目标点航向角错误的搜索分支。

地图信息非动力学模型启发函数，[hh（x，y）]，该启发函数是上一启发函数的对偶函数，忽略车辆动力学模型，以几何最短路作为启发函数。该启发函数充分考虑的地理信息，消除了错误行驶方向的搜索分支。

结合二者，选取启发函数[h（x， y，θ，v）] = max（[hnhx，y，θ，v， hh（x，y））]，

fxyv） = g（x， y， ，v） + h（x， y， ，v） （1）

fxyv） Fxyv） （2）

f 为状态[（x， y， θ， v）]的估价函数， g为当前搜索状态[（x， y， θ， v）]的实际代价， [F]为实际搜索代价。

在该启发函数的引导下，第二阶段启发式搜索可以高效地计算出四维高精度路径。

4 仿真实验以及实验结果

为了展示该算法的性能，本文进行了仿真实验。在实验中，智能无人车刚刚进入一停车场，需要在目标停车位泊车。实验环境为Ubuntu 12.04 Linux系统，Intel i5处理器， 8GB内存。停车场大小为长80米宽50米，栅格离散化精度为10厘米，车辆采用72个不同的航向角，同时采用两个速度，最大的前向速度以及最大的后向速度。

图2 a朴素四维启发式搜索；b增维启发式搜索；c朴素四维启发式搜索输出路径；d增维启发式搜索输出路径

a

b

c

d

表1 算法性能比^

[ 阶段 朴素四维启发式搜索 增维启发式搜索 搜索状态数量 第一阶段 400000 第二阶段 10808634 408773 共计 10808634 808773 算法运行时间

（毫秒） 第一阶段 142 第二阶段 2844 141 共计 2844 283 ]

如图1b，对于每一次路径规划，增维启发式搜索算法可以有效地减少搜索状态的数量，因为高维度高精度部分的搜索集中在离车辆较近的区域，而从全局的角度，二维的几何最短路依旧引导着轨迹往正确的方向。相比之下朴素的四维启发式搜索搜索量极大（图2b）。从输出轨迹上看，两者的输出轨迹质量几乎相同（图2c、2d）。

5 结论

本文展示了增维启发式搜索路径规划算法。该算法分为两阶段。第一阶段在全局考虑二维的搜索状态空间，得出起始点到目标位置的几何最短路。在第一阶段几何最短路基础上选取一个目标点作为第二阶段目标状态空间，进而得到考虑了车辆动力学模型、四维的高精度可执行轨迹。仿真实验结果表明，在现实场景下，该算法极大地减少了搜索状态数量，提高了算法执行效率，同时输出高质量的智能无人车行驶轨迹。

参考文献：

[1] 杨明.无人驾驶车辆研究综述与展望[J]..哈尔滨工业大学学报，2006，38（增刊）：1259-1262.

[2] 孙振平.自主驾驶汽车智能控制系统[D].国防科技大学，2004.

[3] 杨森森.基于GPS/INS/激光雷达的无人车组合导航[D].上海交通大学硕士学位论文，2013.

[4] 钱钧，杨汝清，王晨，等，基于路标的智能车辆定位[J].上海交通大学学报，2007，41（6）：894-898.

[5] 王曦鸣.军用无人车的路径规划与仿真研究[D].北京交通大学硕士学位论文，2010.

[6] 曹玉芬，张国斌.美国无人地面车辆计划[J].国外坦克，2004（5）：25-27.

[7] Rapidly-exploring random trees： A new tool for path planning. S. M. LaValle. TR 98-11， Computer Science Dept.， Iowa State University， October 1998

[8] RRT-based trajectory design for autonomous automobiles and spacecraft. P. Cheng， Z. Shen， and S. M. LaValle. Archives of Control Sciences， 11（3-4）：167--194， 2001.

[9] Rapidly-exploring random trees： Progress and prospects. S. M. LaValle and J. J. Kuffner. In Proceedings Workshop on the Algorithmic Foundations of Robotics， 2000.

[10] S. Karaman and E. Frazzoli， Sampling-based algorithms for optimal motion planning，I. Robotic Res.， vol. 30， no. 7， pp. 846C894， 2011.

[11] Yun-xiao Shan Bi-jun Li Jian-Zhou Yue-Zhang，An Approach to Speed Up RRT* ，2014 IEEE Inteligent Vehicles Symposium （IV） June 8-11

[12] Karaman S， Walter M R， Perez A， et al. Anytime motion planning using the RRT*[C]//Robotics and Automation （ICRA）， 2011 IEEE International Conference on. IEEE， 2011： 1478-1483.

[13] Leonard J， How J， Teller S， et al. A perception-driven autonomous urban vehicle[J]. Journal of Field Robotics， 2008， 25（10）： 727-774.

[14] Kuwata Y， Fiore G， Teo J， et al. Motion planning for urban driving using RRT[C]//Intelligent Robots and Systems， 2008. IROS 2008. IEEE/RSJ International Conference on. IEEE， 2008： 1681-1686.

[15] Leonard J， Barrett D， How J， et al. Team MIT urban challenge technical report[J]. 2007.

[16] Kuwata Y， Karaman S， Teo J， et al. Real-time motion planning with applications to autonomous urban driving[J]. Control Systems Technology， IEEE Transactions on， 2009， 17（5）： 1105-1118.

[17] Barbehenn， M. and Hutchinson， S. （1995）. Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest path trees. IEEE Transactions on Robotics and Automation， 11（2）： 198C214.

[18] Gaschnig， J. G. （1979）. Performance measurement and analsis of certain search algorithms. Ph.D. Dissertation， Carnegie Mellon University.

[19] Stentz， A. （1995）. The Focussed D* Algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence （IJCAI）， pp. 1652C1659.

路径规划典型算法篇（5）

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2016）26-0079-02

Development and Application of Vehicle Routing Problem

BIAN Chen， ZHAO Jian-dong

（School of Computer Science and Engineering， Anhui University of Science & Technology， Huainan 232001， China）

Abstract： As a hotspot in the field of operational research and combinatorial optimization， vehicle routing problem is closely related to real life.As long as the deepening study of vehicle routing problem， various kinds of new types of heuristic algorithm is applied to solve such problems.The vehicle routing problem with various constraint were investigated， analysis and summary in this paper， and the related domestic and foreign research results were reviewed and refined， on this basis， this paper summarizes the research of vehicle routing problem. Based on the current various standard of classification， this paper discusses and analyzes the classical vehicle routing problem firstly， and summarized the basic methods and modern heuristic algorithm on this basis.

Key words： vehicle routing problem； heuristic algorithm； hybrid；multi-depots； time window； pickup and delivery

1 背景

车辆路径问题（Vehicle Routing Problem，VRP ）是由 Dantzig等人在1959 年提出的一个经典的NP-hard问题[1]。是指对于一系列的装货点及卸货点，规划合理的配送路径，在满足了约束条件之下，载货车辆按照规划的路线依次访问，能够满足一定的需求或达到某些目标。其研究成果已广泛地应用于各个学科之中。VRP已经不止是单纯的理论研究，现实世界中，国内外学者的研究经历了其从最早期无车辆约束的TSP问题发展为对车辆运载能力、车辆行驶里程、客户服务数量进行限制的经典VRP，而后依据客户需求的改变和客户对配送要求的提高，从服务无时限向有时限（也称为时间窗问题）以及从纯送货问题或者纯取货问题向混合取送问题（也称为集货送货一体化）的变化的VRP问题。为了不断满足现实要求，当前针对VRP的大部分研究，集中在对其动态性的讨论上，即从配送过程中信息的确定性向动态接受客户需求（也称为不确定性）的变化。

随着现代物流行业的崛起，企业为了降低运输成本，越来越重视对VRP问题的探究，新型的VRP不断地涌现，使得其更有研究价值和现实意义。

2车辆路径问题研究现状及评述

本文根据现有对VRP问题研究的成果，从综合的角度分析车辆路径路径问题，目前国内外针对车辆路径问题的研究主要集中在其扩展问题上。

2.1 多配送中心的车辆路径问题

根据配送中心数目的多少，配送车辆调度问题可以分为单配送中心车辆调度问题和多中心车辆调度问题，在整个物流管理的体系中，配送地一般都存在多个中心，因此对多配送中心车辆调度问题的研究更加具有现实意义。目前国内对于多配送中心车辆调度问题的研究还是处于一个有限的阶段。

在多配中心车辆路径问题中，车辆路径的安排需要满足以下四点条件：

1）每一辆车都从一个配送中心驶出，并在服务了一定数量的客户后返回初始的配送中心；

2）每一个客户每次只能被一辆车服务；

3）车辆不能够在两个配送中心之间进行运输，并且行驶路径不能够出现回路；

4）车辆的运载量不能够超出容量限制，并且每一个配送中心提供的客户服务数量是有限的。

对配送中心的车辆路径问题一般可以如下的描述：在整个物流配送系统中，存在着多个服务中心为多个客户进行服务，需要制定一条配送行车路径使得所有客户的需求被满足的前提之下，配送成本降至最低。多配送中心的VRP是一个NP难度组合优化问题，因此一般求解是很难得到最优解的。当前，国内外学者普遍采用多阶段的办法来解决此类问题，一般先将多配送中心问题转化为单配送中心问题，再利用启发式算法进行求解。崔文[2]通过多阶段的启发式算法，将此类问题通过聚合―求解―优化的步骤逐步求解出最优路径，提出了通过启发式算法在短时间生成最初的有效路径来代替Lin-Kemighan算法中采用的随机路径作为初始路径。

2.2 开放式车辆路径问题

开放式车辆路径问题（OVRP）是现代运输运筹学中的一个新型研究课题，与经典VRP问题相比较，他的一个显著特点是车辆在完成运输服务后可以将其他的配送中心点选为终点。OVRP一般可以简化为忽视了回程约束的带容量约束车辆路径问题（CVRP），其求解目标是构建一个哈密顿通路以满足所有顾客的需求。在现实中，物流公司可能通过雇佣车辆来完成配送任务，那么车辆是否回到出发点并不受到关注，这段路程的费用也将不计。

OVRP是配送运输管理中广泛存在的问题，在现实生活中有很多应用，特别是在具有外包业务特点的配送服务中具有较大的应用价值，例如校园班车问题、牛奶配送、报纸配送等，在这类问题中，由于企业没有自己的车辆，所以将其配送业务外包给其他的车辆或车队，而且企业并不要求车辆在服务完客户后回到车场点。OVRP问题的首要优化目标一般都是最少车辆数，在此基础上优化行驶距离。在过去的十几年里，尽管学者们通过禁忌搜索，确定性退火技术，大规模领域搜索方法，分枝切面法等多种方法为OVRP问题提供了基本的解决办法，但面对大规模的数据处理，OVRP问题仍然存在着一定的求解难度。Sariklis[6]等人通过两阶段启发式算法来进行求解，第一阶段是先生成客户群，然后在每一个客户群中安排路线，进行局部优化，第二阶段将OVRP问题转化为最小生成树问题并求解。Brandao[7]在求解时，通过最近邻居法和最小K度生成树来划分客户群，并最终用禁忌搜索法优化路径。

2.3 时间窗口约束的车辆路径问题

带时间窗车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）作为物流管理问题中一个重要的分支，他基于以下假设：1.需要必不可少的通信设备，使得顾客和服务中心之间，服务中心和货运车辆之间的信息能够快速便捷的传递；2.配送的计划中，存在预约服务的客户。服务车辆必须在客户规定的时间窗[[Ai，Bi]]对其进行服务，其中[Ai]是客户[i]的允许最早开始时间，[Bi]是其所允许的最迟开始时间。如果车辆到达客户的时间早于[Ai]，那么车辆只得等待直至到达服务的最早时间点，其系统优化目标是最小化客户的平均等待时间。

近年来，对于求解带时间窗车辆路径问题取得较好效果的是启发式算法。Gold等人最早综述了VRPTW的研究状况。上世纪80-90年代，对VRPTW的研究开展综述的是Solomon等人[10]。随后Braysy等人[11]综述了经典启发式、智能启发式算法并提出了展望。最近，Raúl Ba?os[12]等人提出了一种针对多目标VRPTW问题的混合现代启发式算法，得到优化解决方案。

2.4 带集货送货需求的车辆路径问题

车辆调度领域之内的问题一般可以按如下区分为两大类：一种是纯装货或者纯卸货问题，另一种是带装货卸货一体化的车辆调度问题（VRPSPD），而后者更是包括了先送货后取货的车辆路径问题，同时集货送货的车辆路径问题以及混合集货送货的车辆路径问题。

VRPSPD的提出最早可以追溯到1989年，由Min提出的在解决了车辆数量一定并且车辆运载能力有限的情况下，一个中心配送点和22个地方图书馆之间的书籍配送问题。VRPSPD问题可描述为：某一个仓库为其用户群体进行货运服务，任意用户可能同时需要送货和集货服务，并且某一客户的送取货的需求之和不能大于车辆总运载能力Q。

VRPSDP的难点在于服务车辆的装载量难以控制易发生溢出。当每一个客户的送货需求是已知的时候，依据车辆的剩余装载能力来定义插入准则，。

2.5 动态车辆路径问题

依据物流信息在配送之前是否完全可知，VRP按新的分类方式分为静态VRP和动态VRP。动态车辆路径问题的首次完全提出要归功于Wilson和Colvin[13]，当时他们研究的单一车辆问题描述了客户旅程的需求，从始发地到目的地的旅程是动态变化，并通过启发式算法来提升计算效率。车辆路径问题中动态信息最常见的来源就是客户需求的在线到达。具体来说，需求可以是针对货物的调整也可以是是服务需求的变化。

一般认为动态车辆路径问题和静态车辆路径问题的区别在于信息的确定性与未知性，而前者在配送服务过程中，会出现不同类型的动态信息。

动态车辆路径问题一般具有的特征如下：

1）安排配送路径和车辆执行计划的过程中新客户信息能够实时的传达。

2）任何新传达的信息都允许是不精确的。

3）新信息需要被快速的响应。

4）与静态VRP问题相比求解的目标函数更为繁杂。

任何动态车辆路径问题仍是基于静态车辆路径问题提出的，目前针对动态车辆路径问题的求解办法，仍然需要借鉴处理静态车辆路径问题的各类算法，其中大部分算法为元启发算法。

动态车辆路径问题首先要明确需要响应哪些动态信息，并以客户需求变化为依据，选择需要优化的目标函数，例如将配送车辆的总行程作为目标函数进行优化，然后再设置额外的约束条件，例如设定单车最大行程为约束条件。借助各类启发式算法如蚁群优化算法等进行优化，在整个配送过程中，不再是单一直接地插入顾客需求，通过最大熵法分布估计算法计算出具有发展潜力的客户群体和区域。在=当需求发生冲突时衡量各个客户需求的利益，通过惩罚措施来降低费用。

3 结束语

车辆路径问题因其不可预估的经济效益和其在现代物流中的所占据的重要地位已经引起了国内外学者的高度关注，并依据实际需求不断引入新的约束。在理论与应用上，各类精确算法、启发式算法被广泛地应用于解决车辆路径问题，并已经取得了长足的进步。然而，同样被关注的是，从现有的各类研究成果看来，虽然新型约束条件下的VRP模型更加完善也更符合现代物流实际需求，但实际求解算法却很难在精度和效率上做到两全，简化算法测率需要得到更多的重视，特别是，各类启发式算法在求解时的弊端也愈加明显，需要取长补短发挥其他算法的优势。

参考文献：

[1] Dantzing G，Ramser J. The truck dispatching problem[J]. Management Science， 1959， 10（6）： 80-91.

[2]崔西.大规模多配送中心车辆路径问题研究[D]. 济南： 山东大学， 2009.

[3]Sariklis D， Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational ResearchSociety，2000，51： 564-573.

[4] Branda～o J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research， 2004，157：552-564.

[5] Desrochers M， Lenstra J K， Savelsbergh M W，et al. Vehicle Routing With Time Windows： Optimization and Approximation[M]. Amsterdam， The Netherlands： Elsevier Science Publishers， 1988.

路径规划典型算法篇（6）

中图分类号：TP242 文献标识码：A 文章编号：1009-914X（2016）20-0218-01

1 引言

科学技术日新月异，移动机器人的应用范围越来越广。路径规划是移动机器人实现自主导航的关键技术之一[1-5]。按照移动机器人对环境的认知程度，可以将路径规划分为基于先验信息的全局路径规划和基于传感器信息的局部路径规划。A-star算法是全局路径规划的经典算法之一；然而，传统A-star算法在搜索过程中也存在自身的缺陷，如搜索出的路径不易于机器人运动控制、搜索速度慢等。本文针对复杂环境下A-star算法的缺陷进行了启发函数和搜索策略的改进。

2 A-star算法概述

A-star算法作为一种启发式搜索算法的优势就在于从当前搜索节点搜索下一步节点时，由一个启发函数来引导选择代价最小的节点作为下一步搜索节点。这样减少了搜索空间，提高了效率。A-star算法中代价函数如下：

1.1

上式1.1中，表示从起始点经过节点n到达目标点的最低代价的估计值，它由两部分组成：一部分为，是从起始点到当前点的实际代价值；表示从当前点到目标点的估计代价值，称为启发函数。

A-star算法的应用关键在与启发函数和Open、Close列表的设置，好的启发函数可以加快搜索速度，合理的Open、Close列表设置能节省存储空间。Open列表用于存放未被检测过的位置点，Close列表用于存放已被检测完毕的位置点。

3 改进的搜索策略

首先， A-star算法的搜索核心是启发函数，启发函数使其避免了盲目性搜索的繁杂性。传统的A-star算法所使用的启发函数是经典的Manhattan距离或欧几里得距离。

分析A-star算法的搜索过程可知，当启发函数（是最终真实路径的距离）时，此时搜索范围较大，运行效率低下，搜索时间长；当启发函数时，算法的搜索过程将按照最理想的路径点一步步往下搜索，但是现在情况不能满足该种情况的要求；当时，搜索范围较小，运行效率较高，搜索时间较短，但是搜索出的路径不是最短的所以，为了得到较高的运行效率和最优的路径，我们应当选取启发函数的值接近于。因为A-star算法在进行下一步搜索时，只能搜索与其当前位置相临接的位置点，并不是任意、盲目地选取下一点。如图1所示，根据以上分析，本文结合Manhattan距离和欧式距离设置的启发函数如下式。

当时，代价函数改写为

当时，代价函数改写为

上式1.4中，和分别表示机器人当前节点与目标节点之间横坐标和纵坐标的差值，。

其次，在栅格环境中运用传统A-star算法进行路径搜索时，得出的结果会出现经过障碍物顶尖的情况，这在实际情况中是不允许的。分析算法在选取下一点的搜索原理可知，出现该情况的原因是在栅格环境中往左上、左下、右上、右下方向进行搜索时搜索的限制条件没有将与机器人当前位置相邻区域的环境情况考虑在内。本文对搜索过程做如下改进：

①机器人当前位置为，进行下一步的搜索，如果下一步位置为则执行②；如果下一步位置为则执行③；如果下一步位置为则执行④；如果下一步位置为则执行⑤；否则执行⑥；

②判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

③判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

④判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

⑤判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

⑥计算此点的、、值。

⑦更新搜索节点。

4 实验仿真与结论

基于以上优化方法，本文在MATLAB2014b中进行了仿真，假设移动机器人的运动环境已知，为栅格化环境模型。图2为改进后的A-star算法仿真得出的路径规划结果，黑色为障碍物，白色为可行区域，其他颜色表示比较危险的可行区域。

与的传统A-star算法相比较，改进后的A-star算法搜索时间减少了0.04s，搜索的节点数减少了4.9%，路径的关键节点数减少了50%，并且路径没有过障碍物顶尖的现象，改进后的A-star算法会优先选择远离障碍物的安全区域规划路径，最终生成的路径更加符合机器人的运动控制。说明改进后的A-star算法是可行的。

机器人路径规划是一个经典研究领域，在当前复杂的生产、生活背景下，一方面对机器人的实时性提出了更高的要求，另一方面对规划出的路径安全性、与人相容性有了提出了更高的性能指标要求。本文充分考虑了机器人对实时性和安全性的要求，提出了改进的A-star路径规划方法，提高了搜索速度，降低了碰撞发生的可能性，并通过仿真实验验证了新方法的有效性。

参考文献

[1] 蔡自兴，贺汉根。未知环境中移动机器人导航控制理论与方法[M]。北京：科学出版社，2009.

[2] 王殿君。基于改进A*算法的室内移动机器人路径规划[J]。清华大学学报（自然科学版）。2012，Vol.52， No.8.

[3] 马喜峰， 张雷. 基于对称极多项式曲线的移动机器人平滑路径生成[J]. 机器人， 2005， 27（5）： 450-459.

路径规划典型算法篇（7）

1 引言

TETRA为欧洲电信标准协会(ETSI)推荐的数字集群标准,与iDEN、GT800、GOTA并列,为我国四大数字集群标准之一。TETRA标准采用TDMA与FDD技术,将一个载频的25kHz带宽分为4个时隙(信道),可用于承载话音/数据业务、控制信令。TETRA除了具有一般数字集群系统频率效率较高的特点外,在话音功能、数据服务、直通模式、系统容量、市场规模等方面具有比较明显的优势,加上其强大的调度功能,TETRA在国内外得到广泛应用。TETRA也是我国已建的数字集群共网系统普通采用的技术标准。

目前我国已建的TETRA数字集群网络主要有:北京正通政务网、上海电信集群网、深圳公安数字集群网络、广州800M数字集群共网、全国多个城市地铁、机场数字集群专网。随着政府管理水平的提升,对统一的应急通信指挥调度需求日益迫切,TETRA集群业务市场前景广阔,对TETRA无线网络规划技术研究、探讨,具有实际意义。

2 TETRA数字集群网络的服务指标

进行TETRA数字集群网络规划之前,应首先明确相关的网络服务指标,例如:网络接通率、覆盖率、排队等待概率等。这些网络服务指标指出了网络的建设目标,是网络规划的重要输入条件,各参数取值的不同也会直接影响网络规划的结果。表1列出了TETRA数字集群网络的一些主要网络指标。

3 TETRA覆盖规划

无线覆盖规划,主要针对不同区域类型的基站进行链路预算,得到相应的链路允许最大损耗以及基站覆盖半径,以此为依据进行下一步的无线基站规划及选点。

在TETRA网络规划设计之前,一般要先进行传播模型调校工作,使得最终的模型参数与实际测试结果更加吻合,增加覆盖预测的准确度。考虑到Hata理论模型不大适合直接应用到仿真软件的覆盖预测中,建议采用在国内得到广泛应用的仿真软件ASSET标准传播模型“Standard MacroCell Model”。该模型以Hata模型为基础进行扩展,能方便地利用测试数据进行模型校准,且考虑了地貌及无线信号衍射情况,从而增强了模型的灵活性和精确性,适用于150MHz到2GHz的频率范围。在该标准模型中:

其中:

Prx为接收信号强度(dBm);

Ptx为发射信号强度(dBm);

Ploss为传播路径损耗(dB);

并且:

其中:

K1为衰减常数;

K2为距离衰减系数;

K3和K4为移动台天线高度修正系数;

K5和K6为基站天线高度修正系数;

K7为绕射修正系数;

Kclutters为地物衰减修正值;

dkm为测试基站与移动台之间的距离(km);

Heff为测试基站天线的有效高度(m);

Hmeff为移动台天线的有效高度(m)。

进行基站链路预算时,上行和下行链路有各自不同的发射功率损耗和路径衰落。链路预算可分为前向链路预算和反向链路预算,与其他常见无线移动通信系统类似,TETRA数字集群通信系统的覆盖能力主要也是受限于反向链路预算,故工程上一般通过反向链路预算对TETRA基站的覆盖能力进行估算。

采用上述的ASSET标准模型公式,结合某城市的经过调校后的密集市区、普通市区和郊区农村传播模型,得到TETRA集群基站的典型链路预算结果如表2所示。要指出的是,表2中的分析针对的是800MHz TETRA系统,对350MHz或其它频段的TETRA系统,分析方法一致,主要区别在于传播模型参数的取值。

4 TETRA容量规划

进行容量规划之前,首先需明确网络的话务模型。数字集群通信网络主要有调度、电话和数据传输三种功能,各自所占比例不同,用户忙时话务量差别很大。参考国外的统计资料和国内已建数字集群网络的运营经验,取定话务模型如下:

用户分配比例:调度呼叫90%;电话呼叫5%;数据呼叫5%。

调度用户忙时话务量:0.01Erl/户。

电话互联忙时话务量:0.02Erl/户。

数据用户忙时话务量:0.04Erl/户。

综合取定每用户忙时平均话务量为0.012Erl/户。

集群用户忙时排队概率:≤5%。

容量规划一般在用户预测与用户分布分析的基础上进行,具体步骤为:首先根据用户总数和各类区域的话务分布,得到各区域的话务量;然后结合区域内的基站数量和各基站的覆盖范围,估算出各基站需要承载的话务量,并根据话务热点进行权衡调整;最后根据用户需要的服务等级,并考虑一定的冗余,查询Erlang C表得到承载相应话务量时各基站的载波配置。

TETRA容量规划的流程如图1所示:

图1 TETRA容量规划流程图

TETRA集群基站支持1~8载波配置,每个载波有4个时隙(信道),其中第一个载波的第一个信道为主控信道。

按上述取定的话务模型,查Erlang C表得到不同载波配置的TETRA基站容量,如表3所示:

表3 TETRA基站容量表

根据上述容量表,按照图1的容量规划流程,即可计算出各基站的载波配置信息。

5 TETRA无线网络规划实例

图2为某城市的中心市区,属于高密集市区传播环境,人口密集,且有火车站、重要体育场及武警等场所或机关,为该城市TETRA数字集群网络最重要的保障区域之一。

根据前面的链路预算及覆盖规划,该区域集群基站的覆盖半径为1.5km、站间距为2.6km左右。以此为基础,得到该区域集群基站的理想规划位置。在选点阶段,根据现场楼宇的实际情况以及物业情况等,部分站点在允许的搜索半径内对规划的位置进行了调整,图2为调整后的实际站点位置图。

根据前期相关调研结果,该区域每平方公里的数字集群用户数为120~160户左右。基站覆盖半径按1.5km考虑,各基站按理想蜂窝计算得到的覆盖面积为5.8km2。各基站覆盖范围的集群用户数为160*5.8=928户。若基站容量按照20%的冗余,各基站需支持的用户数为928*1.2=1114户。根据前述的集群话务模型及基站容量表,该区域基站的典型配置为6载波。另外,考虑到D基站靠近大型体育场,比赛期间有大量的安保、竞赛组织集群用户;F基站靠近火车站,在重要活动期间同样集群用户密集,这两个站点调整至8载波。也即该区域范围内:A、B、C、E、G基站按规划计算的6载波配置;D、F基站根据实际情况调整为8载波配置。

综上,实际进行TETRA网络规划时,站点位置、基站配置均要在理想规划的基础上,根据实际情况对部分站点进行适当的调整。

6 结束语

无线网络规划为TETRA数字集群网络建设过程中最重要的环节之一。采取合理、科学的无线网络规划方法,将为建设高质量、低成本TETRA集群网络奠定坚实的基础。

参考文献

[1]ETSI EN 300 392-1. Terrestrial Trunked Radio(TETRA);Voice plus Data(V+D);Part 1:General Network Design[S]. 2003.

[2]ETSI EN 300 392-2. Terrestrial Trunked Radio(TETRA);Voice plus Data(V+D);Part 2:Air Interface(AI) [S]. 1998.

[3]郑祖辉,陆锦华,郑岚. 数字集群移动通信系统(第2版)[M]. 北京:电子工业出版社,2005.

【作者简介】

路径规划典型算法篇（8）

交通运输的现代化使人们享受便利的同时，也面临道路拥堵、事故频发等问}。近年来，智能交通系统越来越受到人们的重视，它涉及到交通领域诸多方面，如最优路径选择、车辆路径规划、动态车辆调度、交通流量控制等。其中一个重要的应用是一类典型的以数学理论为基础的组合优化问题，而蚁群算法具有内在的搜索机制及正反馈性，适合求解一系列的组合优化问题。

1 蚁群算法描述

蚁群算法源于20世纪90年代初意大利学者M.Dorigo首次提出的蚂蚁系统。它是基于种群的启发式放生进化系统，是通过对蚁群觅食过程中其行为的研究而得出的一种算法。主要思路是蚂蚁借助自己路径寻优的能力可以找到巢穴与食物之间最短的途径。在寻找过程中主要依靠的是每个蚂蚁在行进过程中留下的挥发性分泌物――信息素，依靠信息素，蚁群的蚂蚁之间可以相互合作，相互配合，因此形成的正反馈可以使每只蚂蚁找到所有路径中最短的路径。

蚂蚁a从节点j移动至k的转移概率可以从式（1）中获取：

（1）

（2）

（3）

2 蚁群算法的应用优势

蚁群算法，又名蚂蚁算法，蚂蚁可以利用信息素的浓度大小从而寻找到觅食的最优路径。该算法的优点可以总结为：

2.1 并行分布式计算

每个蚂蚁都是独立的个体，在觅食过程中属于多起点同时启动，互不影响，从根本上分析该过程属于分布式的多Agent系统，整体蚁群最终任务的顺利完成不会由于某些个体的缺陷而受到影响。该算法具有真实可用性，并且可用于解决对单目标的优化或者对多目标的优化等重要问题。此外，蚂蚁算法还可进行并行计算。

2.2 鲁棒性

蚁群算法的最终结果与蚂蚁最初选择的路径无太大关系，在利用人工仿真蚂蚁进行问题求解过程中，不需要对其进行人工的修整。把问题简单化，可以和其他算法相互结合求解最优问题。

2.3 自组织性

蚁群算法组织指令的来源为系统内部，它不受外界环境的干扰，因此该算法具有自组织性。

2.4 正反馈性

蚂蚁对于最优路径的选择主要依靠路径上信息素浓度的多少，信息素的堆积是正反馈的过程，路径上信息素的含量越多则该路径被选择的几率就会越大，正反馈的作用是使整体能够更快的寻找到最优途径，正反馈在蚁群算法中处于重要地位。

2.5 易于实现

它是一种启发示算法，其计算复杂性为，整个算法的空间复杂度是：。

3 蚁群算法在智能交通领域的应用空间

蚁群算法在解决组合优化问题方面有着明显的优势，从而在智能交通领域也有着广泛的应用空间。

3.1 车辆路径导航

根据行车人员的需要，根据对实时路况信息的统计，系统可以智能的为其推荐最优路径，节省时间，节省资源。

3.2 动态车辆调度

当客户需要调度中心为其进行车辆服务时，调度中心要考虑到客户的情况，要考虑到效率的问题，要考虑到行车路线、行驶时间等问题。蚁群算法便可迅速得到合理的解决方案，使客户和调度中心均可受益。

3.3 车辆路径规划

面对多个客户不同的要求时，配送中心要根据实际情况进行车辆的配送，通过蚁群算法系统获取整体的最优路线，根据路线规划，及时进行车辆出发以满足客户要求，同时充分利用了道路资源和车辆资源。

3.4 公共交通智能化调度

利用先进的技术手段、大型数据库技术等动态地获取实时交通信息，实现对车辆的实时监控和调度，最终建立集运营指挥调度、综合业务通信及信息服务等为一体的智能化管理系统。

3.5 交通流量控制

通过蚁群算法简化复杂的道路交通网络，尽量使交通流量在各个道路上分布均匀，避免因流量过大而造成车辆的阻塞。及时了解交通流量情况，缓解了交通拥挤，降低了交通事故的发生率。

参考文献

[1]M.Dorigo，V.Maniezzo，A.Colom.Ant System：Optimization by a colony of cooperating agents.IEEE trans on SMC，1996，26（01）：28-41

[2]Eric BONABEAUB， Marco DORIGO，Guy THERAULAZ.AWARM intelligence： from natural to artificial systems[M].New York：Oxford University Press，1999

[3]杨海.蚁群算法及其在智能交通中的应用[D].济南：山东师范大学，2008：14-18

作者简介

白晓（1979-），女。工学硕士学位。现供职于厦门软件职业技术学院软件工程系。主要研究方向为软件工程、智能算法。

路径规划典型算法篇（9）

【摘　要】本文通过对比求解最短路径问题的Dijkstra算法和Floyd算法的设计思想、求解过程和应用实例，讨论了两种算法的特点及适用领域。

关键词 最短路径问题；Dijkstra算法；Floyd算法

作者简介：高岚（1979—），女，吉林长春人，硕士，吉林工程技术师范学院信息工程学院，讲师，主要从事软件工程教学研究。

0　引言

最短路径问题是网络分析中最基本的组合优化问题之一，在公交路线网络规划中应用广泛。因此，实际公交线网优化设计中，路径选择算法成为一个重要研究课题，它直接关系到交通网络效率、传输延迟和吞吐量等主要技术性能指标。

早在20世纪初，最短路径这一重要问题就已得到人们的高度重视，当时有许多科学家研究这一问题的求解方法，但直到1959年荷兰计算机科学家Dijkstra（迪加斯特拉）才给出这一问题求解的基本思想，成为一代经典。当时的Dijkstra提出的这一算法主要解决的是从固定的一点到其他各点的最短路径问题。但实际生活中要求解的可能是任意两点间的最短距离，可采用Floyd（弗洛伊德）算法。本文通过将两种算法进行一些对比讨论，得出关于两种算法效率和适用问题的一些结论。

1　最短路径问题

最短路径问题是图论中的基本问题。在赋权图中，找出两点间总权和最小的路径就是最短路径问题。最短路径算法包括指定顶点对之间的最短路径算法和所有顶点间的最短路径算法，前者对于运输的合理化具有重要理论意义，而后者的意义在于选择合理的中转中心，使得总费用最少。在图论中最典型的两种求最短路径算法分别是Dijkstra算法和Floyd算法。

2　Dijkstra算法

2.1　算法基本思想

每次新扩展一个距离最短的点，更新与其相邻点间距离。当所有边的权都为正时，由于不会存在一个距离更短的没有扩展过的点，所以这个点的距离不会再被改变，因而保证了算法的正确性。根据这个原理，采用Dijkstra算法求解最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能破坏已经更新的点距离不会改变的性质。

2.2　Dijkstra算法思想在物流配送中的应用

采用图论中的最短路径算法Dijkstra算法来建立物流配送路径选择模型，主要思想是从代表两个顶点的距离开始，每次插入一个顶点比较任意两点之间的已知最短路径和插入顶点作为中间顶点时两点间的最短路径，得到的最终的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者，即最佳的物流配送选址位置。

3　Floyd算法

3.1　算法基本思想

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

3.2　Floyd算法在选址问题中的应用

某城市考虑建立区域内二次供水中转站。在选址问题中，点表示可供选址，其间连线表示运输费用，其需求点之间运费如图1所示。在选址中，要求该中转站到其他站点的距离最短，即运输费用最少，通过运用求解最短路径的Floyd算法可求出该网点布局的最佳中转站。

由计算可知，a到其他点的费用和为C(a)=33，同理C(b)=27，C(c)=18，C(d)=21，C(e)=33，比较可知c到其他各点的费用最小。因此本例从经济性考虑，选c点为中转站最优。

4　讨论

典型的最短路径求解算法Dijkstra算法和Floyd算法各有所长。Dijkstra算法可为任一源节点找出与其它所有节点的最短路径，是目前公认的较好的最短路径算法，但由于它遍历计算的节点很多，所以效率低。Floyd算法是一种用于寻找给定的加权图中顶点间最短路径的算法，是一种动态规划算法，可以算出任意两个节点之间的最短距离，代码编写简单，但是Floyd算法计算最短路径时时间复杂比较高，不适合计算大量数据。

综上，求解单源点无负权边最短路径可采用Dijkstra算法，而求所有点最短路径应用Floyd算法。对于稀疏图，采用n次Dijkstra算法比较出色，对于稠密图，适用Floyd算法。

5　结束语

本文通过对比两种求解最短路径算法的设计思想、求解过程、应用实例，讨论了算法的特点及适用领域。了解算法求解问题的差异，针对不同类型问题采取对应的求解算法，将大大提升解决问题的效率，对实际生产生活起到重要作用。

参考文献

［1］辛建亭,胡萍.图论在通讯网中的应用[J].2009,3.

［2］凡金伟,吕康.基于Dijkstra算法在物流配送中的应用[J].电脑编程技巧与维护,2009(4):39-45.

［3］邓春燕.两种最短路径算法的比较[J].电脑知识与技术,2008(12):511-512.

［4］徐凤生.求最短路径的新算法[J].计算机工程与科学,2006,2.

［5］殷剑宏,吴开亚.图论及其算法[M].合肥:中国科学技术大学出版社,2005.

［6］陈玉华.浅谈图论在现实生活中的应用[J].云南省教育学院学报,2004.

路径规划典型算法篇（10）

中图分类号：F253 文献识别码：A 文章编号：1001-828X（2017）013-0-01

一、引言

随着我国烟草行业从传统商业向现代流通模式的转变，烟草物流配送正逐步向“集约化管理、规模化经营、专业化物流、标准化服务”方向发展，如何实现物流配送高效、低成本的运作模式，提高烟草企业整体竞争力水平，是许多烟草企业面临的一个关键问题。

文章提出了一种基于时间成本的物流线路优化方法，通过科学规划配送线路、平衡每日订单分布等方式，使卷烟网络分布更加合理，进一步降低固定投入和I务成本，提高供应链管理水平。

二、算法模型

基于时间成本的物流线路优化计算主要运用到三个求解算法，分别是聚类算法、最优路径算法和订单日规划算法。基本求解方案是：第一步按照车辆装载率完成对客户兴趣点聚类；第二步细致优化配送路径；第三步平衡每日订单分布。

1.聚类算法

聚类是空间数据挖掘中的一个重要研究领域，是指将物理的或抽象的对象分组成为由类似对象组成的多个类（簇）的过程。

以绍兴烟草为例，聚类计算时首先采用自下而上的一阶段方法对全地区26000个零售户点进行聚类，获得411个初始聚类结果。再根据实际需求，按照类容量将前408个类作为直接指派的初始类核，以配送车装载率90%作为类容量上限，进行直接指派聚类，最终获得聚类结果。

2.最优路径算法

最优路径算法的目标是寻找给定起点和终点间的最短路径，文章采用Dijkstra（迪杰斯特拉）算法。Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

⑴初始时，S只包含源点，即S=v。U包含除v外的其他顶点，U中顶点u对应的距离值为边上的权（若v与u有边）或 ∞（若u不是v的出边邻接点）。

⑵从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

⑶以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。

⑷重复步骤（2）和（3）直到所有顶点都包含在S中。

3.配送工作量模型和订单日规划算法

进行订单日规划时，文章引入工作量模型概念，将综合作业时间作为线路优化的单一标准，把送货户数、送货量、行驶里程等多维度统一转换成工作时间，解决线路优化时指标过多，计算困难的问题。

综合作业时间=装车交接时间+车辆行驶时间+基本服务时间+客户交接时间+现金缴款时间。装车交接时间=（装车准备时间×车次）+（装车框数×单框装车时间）

订单日规划算法的目标是确定各配送线路的配送车辆和配送日，规划要求满足以下约束条件：车辆数最少；一周内各配送车辆工作时间基本均衡；每天各配送车辆工作时间基本均衡；每天工作时间上限设定6.5小时。

订单日规划算法模型：

约束条件：

（1.1）

（1.2）

（1.3）

（1.4）

i 需要安排的路线序号；取值范围从1到路线的最大数；

j 送货车序号；取值范围从1到指定车辆数；

k订单日的序号；取值范围从1到5，表示一周配送5天；

b每天所有车辆工作时间的上限；

c每辆车一周工作量上限；

d每辆车每天工作量的上限，d为6.5小时。

公式（1.1）一条路线有却只能有某辆车在某一天配送；

公式（1.2）每天所有车的工作量不能超过上限b；

公式（1.3）每辆车每周的工作量不能超过上限c；

公式（1.4）每辆车一天的工作量不能超过上限d。

三、结语

“低成本、高效率、优服务”是烟草物流建设的重要目标，文章提出的基于时间成本的物流线路优化算法，将影响物流成本的多维度指标转化为综合工作时间进行分析计算，为烟草商业企业科学合理的进行物流线路优化，提供了较完整的解决方案。

参考文献：