李传发 ，杨舒音 ，李 末 ，孟 妤

（1.大连理工大学机械工程学院，辽宁 大连 116024；2.中机科（北京）车辆检测工程研究院有限公司，北京102100；3.大连益利亚科技发展有限公司，辽宁 大连116000）

1 研究背景

随着着互联网技术的发展，物联网应运而生，其用途十分广泛，遍及智能交通、仓储物流、环境保护、工业检测等多个领域。随着快递等服务业的快速发展，物联网在仓储物流中的应用也是起着非常大的作用，比如中国的一些大型港口已经实现无人化，一些快递的中转地依靠机器人进行快递的分拣。在实际的应用场景中机器人有时需要从起点出发去不同的地点完成多个任务再回到起点，而为了减少机器人在路径上花费的时间，需要算法来规划其路径，使机器人在执行任务时经过最短路径。

本文所提出的算法所要解决的问题即当机器人需要从起点出发，路经多个需要停留作业的地点（目标点），然后回到起点时，规划出机器人所走过的最短路径。此类问题在现实中有很多应用的场景，因为我们有时需要的不只是从起点到终点两点之间的路径寻优，而是从起点到多个目标点的路径寻优。比如外卖的配送、快递的邮寄等，他们都是从一个起点出发，需要经过多个目标点再回到起点。而目前的路径寻优基本是单目标点的寻优即从起点到终点的路径规划，比如经典的A*算法、D*算法以及本文用到的JPS算法[3]等，在这些算法的基础上进行改进后，使得路径的规划……