开学季 | 第一课《车辆路径问题与算法》
|
请问膜拜技术大牛除了献上膝盖还有什么更好的方式？答：可以把大家的膝盖一起献上，又或者好好学习天天向上，利用碎片化时间多为自己充电，一起参与技术的交流与探讨。——四月，我们迎来了蓝芯科技的开学季，我们将在此分享机器人相关技术知识。今天是开学第一课《车辆路径问题与算法》，欢迎大家留言一起探讨。
图1 TSP问题 车辆路径问题（Vehicle Routing Problem,VRP）早是由Dantzig和Ramser于1959年*提出，它是指一定数量有一定数量（n个）的客户，各自有不同数量的货物需求（qi），配送中心或车场（depot）向客户提供货物，由一个车队（m辆车）负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下（例如车辆存在载荷上限Q、里程长度上限L），达到总旅行成本小、耗费时间少等目的[1, 2]。
在理解了车辆路径问题后，接下来介绍几个常用的路径搜索算法。
二、路径搜索算法 在路径搜索算法中，常用的算法用Dijkstra算法和 A*算法。这里不对算法原理进行详细介绍，仅简单给出相应的使用示例。给出一个网格图，如图3所示。在该网格图中，仅横、纵向相邻网格可以通过，其中黑色背景网格不可通过。在网各图中，每移动一格会增加一个单位成本。现给定一个起点（46）和终点（49），通过Dijkstra算法和A*算法分别求解短路径。 图 3网格图示例
2.1 Dijkstra算法
图 4 Dijkstra算法拓展过程
2.2 A*算法在Dijkstra中，当前拓展到的点的距离为从起点到当前点的实际短距离。而A* 算法与 Dijkstra相比增加了一个启发项，即在计算当前点的路线距离时，使用从起点到当前点的实际短距离加上从当前拓展的点到终点的估计距离。因此，在实际距离相同时，估计距离近的点优先继续拓展。使用A*算法对图3 的求解结果如图5 所示。终的路线是
2.3 多访问点的路径搜索算法
因为一共有7个点（1个出发点加6个访问点），所以搜索划分为6个step，方向为从右至左（从终点至起点），如图6所示。
图 6基于 DP框架的step示例 计算过程为，以zui后一列的点为终点，搜索第一个弧（arc），即step(1)的路径，然后再增加一个 arc，即在step(1)的基础上搜索step(2)的路径，以此类推。假设以为终点进行搜索，搜索中的部分过程如图7所示。终搜索完step(6) 时会搜索出完整的路线。需要注意的一点是，一旦发现某条路线不是可行解时（比如一个访问点在路线中多次出现），后面可以不再基于此结果进行搜索。
图7基于 DP框架的部分搜索过程示例
我们这里控制了初始搜索步长len，意为从step(1) 到step(len) 搜索出的路径是按照 DP的方式搜索到的当前精确合适的路线，而从step(len 1)开始，只记录该step下的n条路径中合适的结果。因此，当len的值越大，终搜索的结果越接近精确合适解，但是相应的求解时间也会越长。假设通过该阶段终搜索出的合适结果为，接下来将基于此结果执行变邻域搜索操作。由于是规定的出发点需要保持在输出路径的首先位置，因此我们对序列{2,6,1,5,4,3}进行邻域搜索。VND的框架如图8 所示。
图 8 VND算法框架
在邻域搜索中，常用的变换策略有Reinsert、Exchange和Reverse，如图9所示。
使用VND不断地对序列变换得到新的序列，并求新序列的路径成本。需要注意的是，求路径成本时要将出发点考虑在内，即将出发点添加到序列前，求该完整路径的旅行成本。经过VND过程的处理，输出的路线即作为终规划的路线，例如一个可能的终输出路径果是，需要注意的是，这里的节点相当于是“关键节点”，即只包含的出发点和需要进行配货操作的访问点。而相邻“关键节点”之间的路线，则是根据前述的 Dijkstra计算的两点之间的路线进行行驶。今天的介绍就到这里，希望小伙伴们能对路径规划问题和算法有所了解和收获！ 本文为杭州蓝芯科技有限公司原创文章，转载请注明出处 |
