一种从地图数据中获取多车辆导航路径的方法

摘要

本发明公开了一种从地图数据中获取多车辆导航路径的方法，用于生成多车辆从配送中心出发途经若干服务点进行服务后回到配送中心的导航路径，其包括数据获取步骤、导航路径生成步骤以及导航路径输出步骤，所述导航路径生成步骤包括初始导航路径生成步骤、第一优化步骤、第二优化步骤。本发明与现有技术相比能够快速地从地图数据中获取优化导航路径。

主权项

一种从地图数据中获取多车辆导航路径的方法，用于生成多车辆从配送中心出发途经若干服务点进行服务后回到配送中心的导航路径，其特征在于，包括以下步骤：1）数据获取步骤：获取地图数据、以及车辆必须经过的所有服务点的服务点数据，该服务点数据至少包括：服务点的位置数据；2）导航路径生成步骤：根据所述地图数据和所述服务点数据生成包含多条子线路的多车辆导航路径，其包括以下子步骤：2‑1）初始导航路径生成步骤：2‑1‑a）：选择一个服务点作为初始点，在车辆从配送中心去往该初始点以及从该初始点返回配送中心的路径中，插入若干服务点作为该路径的途经点以形成一条子线路；2‑1‑b）：重复步骤2‑1‑a）以形成多条子线路，使得所有服务点均被作为子线路的途经点，从而形成初始导航路径；2‑1‑c）：通过所述地图数据以及各服务点的位置数据计算出初始导航路径的路程总长度S1；2‑2）第一优化步骤：2‑2‑a）：在初始导航路径中，选择任意一条子线路的一个途经点，将该途经点随机地与同一条子线路或非同一条子线路的其他途经点进行交换、或者选择任意一条子线路的一段路径段随机地与同一条子线路或非同一条子线路的其他路径段进行交换以形成第一优化导航路径，计算第一优化导航路径的路程总长度S2，2‑2‑b）：若S2