◆汪慧琳

（郑州大学地球科学与技术学院 河南 450001）

如今，支持北斗三号系统信号的 28 纳米芯片已得到广泛应用，国内外主流芯片厂商均推出兼容北斗的通导一体化芯片，支持北斗定位的手机越来越多。通过获取手机本身芯片提供的位置，地图软件就可以使用BDS进行实时定位、路径规划等功能。通常的地图软件都具备让用户选择起点-终点，从而进行两点之间最佳路径规划的基础功能。现在国内的地图软件（高德地图、百度地图、腾讯地图等）也具备设置多个途经点（主要是驾车模式）的路径规划，在手机端一般可以设置5个途经点（包括起点和终点），在PC端可设置途经点数较多的是高德地图（包括起、终点共8个）。但目前仍未有一款地图软件，能根据用户的预期途经点（地点数大于8）及用户的时间期望（愿意用于出行的时间）给用户提供智能出行规划。一种常见的情况是：用户在面临需要规划路线的情况时，容易陷入纯粹的局部最优规划（贪心算法）——总是去往离当前位置最近的位置，这往往会比真正的最优规划多出许多里程。另一种常见的情况是：由于用户时间有限，不能经过所有期望地点。

本文旨在通过优化智能算法得出两种路径规划方式，一是让用户在经过所有预期途经点的条件下尽可能地减少交通里程，二是让用户在时间有限的条件下尽可能地减少交通时间。当基于北斗导航系统的路径规划能够为用户提出更优化的方案时，将会提升用户体验。……