开学季 | 第一课《车辆路径问题与算法》
|
请问膜拜技术大牛除了献上膝盖还有什么更好的方式？答：可以把大家的膝盖一起献上，又或者好好学习天天向上，利用碎片化时间多为自己充电，一起参与技术的交流与探讨。——四月，我们迎来了蓝芯科技的开学季，我们将在此分享机器人相关技术知识。今天是开学第一课《车辆路径问题与算法》，欢迎大家留言一起探讨。
图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 所示。终的路线是 |
