多车多点智能路径规划云平台的研究与实现

李淑飞，骆剑锋

（东莞职业技术学院计算机工程系，东莞523808）

0 引言

在当前流行的车辆导航软件中，基本上是针对出发地与目的地两个地点、且是对当前单一车辆进行导航，缺乏对多个目的地统筹规划和回程安排，不能合理安排车辆，管理用户和司机。物流企业管理软件功能虽然比较齐全，但也不能实现多条件下多车多点的路径规划及导航。而现实中货运公司、快递公司、校车管理、公交车管理等除了能对车辆、客户等进行管理外，更重要的是要对多辆车和多目的地在限制条件下进行智能规划路线，使得路线最短[1]。多车多点智能路径规划云平台（简称云平台）能把用户、司机、车辆、路径规划相关对象合理地管理，在多车多点智能优化算法的基础上，实现资源的整合优化调度和共享[2]。该平台不但可以实现科学导航，而且使得车辆在运输过程中，能兼顾全局，分工合作，使运输任务更有效率、更经济、更环保。

1 智能路径规划云平台功能架构

本云平台在考虑车辆刚好满载和不超出车辆限程的情况下，遍历所有客户，能通过多车多点限重限程智能路径规划算法规划出最优路径和导航，同时能对司机进行管理，合理调度车辆，是多车辆调度、多点路径规划、多条件限制及实时路况、收发业务的智能云平台。该平台主要分管理员端和移动端App 端，管理员端主要包括司机管理、车辆管理、智能路径规划、客户信息管理、与车辆通讯五大功能，其核心功能是完成智能路径规划，并将规划好后的路径保存到数据库中。移动App 端主要是司机通过手机登录到云平台，在手机App 上查看任务，并按云平台规划好的路径进行导航及通讯。多车多点智能路径规划云平台的功能架构如图1 所示。

图1 智能路径规划云平台功能架构

2 智能路径规划云平台的功能设计

由于多车辆多地点的路径规划复杂度高、运算量大，为了保证软件运行不会死机，有效解决大并发量下系统的处理能力，需要在路径规划求解中首先用神经网络对客户进行分区域分组，然后在分组的基础再进行路径规划[3]，同时利用负载均衡技术，使得软件运行的压力分担到不同的服务器上，从而保证平台稳定运行。因此，本平台除了完成管理员端运行的各种功能服务[4]外（包括多车多点多条件限制的路径规划核心功能）设计，还需要设计手机端App，司机通过App 查询任务、进行导航和通讯，同时实现负载均衡。

2.1 平台中运行的各种功能服务

云平台运行的主要功能服务包括司机管理、车辆管理、客户管理、与车辆通讯及智能路径规划算法。

（1）司机管理：此功能管理司机相关信息，包括司机驾驶的历史记录，方便企业对司机进行绩效管理，同时也方便管理员对司机进行综合考虑，分配任务时有根据。

（2）车辆管理：此功能可以了解企业内各辆车的情况，如车辆的负载量、运行时间、行驶路程等，以便对车辆在一段时间里的行驶路程、行驶时间、载货量等信息进行分类汇总、统计分析，有利于车辆的合理安排及维护。

（3）客户信息管理：客户是企业的珍贵资源，必须对客户信息管理进行很好地管理，如客户的地理位置、收货量、通信电话等，这部分功能是路径规划功能的基础信息，同时也可以对这些信息进行统计分析，有利于企业了解优质客户资源。

（4）与车辆通讯：在考虑司机在驾驶过程中的安全情况下，实现司机与公司的交流沟通，及时解决一些临时、紧急、特殊事情和突发事件。

（5）多车多点智能路径规划：用智能算法调度企业内所有可用车辆，在考虑限重限程的情况下，遍历所有客户的最优路径规划方案及车辆安排方案。

2.2 云平台中的负载均衡

通过司机手机上App 实现负载均衡的功能，把司机的访问压力分散到不同的客户点服务器上，同一组的地点由客户点服务器算出遍历这组内所有点的路径规划，如果有大量的地点，则可以分开进行路径规划，尽量把规划的计算量减少，从而保证服务器不会由于过大的访问量而瘫痪[5]。云平台的性能数据库服务器，保存着各个客户点服务器的性能信息，手机访问客户点服务器前，先从这个数据库中查询比较空闲的客户点服务器信息，再通过这个信息决定访问哪个客户点服务器。

3 智能路径规划云平台功能技术实现

本平台采用多层次平台架构，在管理员端运用Windows 编程完成司机、车辆、客户等信息管理和路径规划，手机App 端Android 编程登录并读取规划信息并进行导航。

3.1 服务器端技术

在服务器端主要使用Windows 编程，利用SQL 数据库对各种信息进行存放，再使用百度API 计算出客户间的最短路径信息、显示地图、路径信息等；用JavaScript 调用百度API；用C＃编程实现对JavaScript 中百度API 的路径数据进行提取，并存放到数据库中，移动设备通过WebService 技术读取这些信息，然后在手机App 上重现路径规划的地图与导航。

3.2 移动端技术

在移动设备端采用Android 移动开发技术。手机通过百度SDK 实现地图导航显示，获取车辆经纬信息、车速、平均车速、路程等功能；通过多线程编程，对由于网络传输产生信息延迟问题进行处理；通过Web-Service 技术实现通信，包括读取数据库中的路径规划方案信息、企业发送给司机的信息、权限信息等，也能向数据库添加车辆经纬信息、车速、平均车速、路程等信息；利用ViewDragHelper 类解决中手势处理过于复杂的问题，用Text2Speech 技术，实现文本到语音的转换。

3.3 云负载均衡技术

云平台中有多个路径规划服务器和一个性能数据库服务器，性能数据库服务器保存着各个路径规划服务器的性能信息，根据用户访问数量、用户使用习惯、服务器当前性能来统筹规划服务器的使用。通过WebService 技术统计服务器访问数量，通过对数据库中的访问来分析出用户的使用习惯；而服务器性能则通过C＃的PerformanceCounter 技术对各服务器CPU、内存、网络接口、硬盘等性能进行监视；最后把这些信息和分析的结果发送到用户的移动设备上的功能模块。手机在访问路径规划服务器前，先从性能数据库服务器中查询比较空闲的服务器信息，再通过这些信息决定访问哪个服务器，这样就把司机的访问分散到不同的服务器上，从而实现了云平台的负载均衡，如图2 所示。

3.4 多车多点路径规划功能实现

路径规划是本平台的核心功能模块，云平台首先从数据库中读取各个客户点的经纬度，利用模糊神经网络根据收送货点是否靠近进行分区域，如果靠近归为一类区，不靠近归为另一类区；同时数据库读取客户收送货的重量及车辆的载重信息，根据这些信息使用多值背包算法进一步对区域内的客户点进行分组。接下来结合百度地图API 和Floyd 最短路径算法[6]算出各地点间的最短路径，得出最短路径矩阵。在绕行遍历思想中，对于遍历所有点，再回到起始点，环绕一周路径最短[7]，因此利用绕行公式RX（i，j）=ZD（i，0）+ZD（j-1，0）-ZD（i，j）（RX 是绕行贡献值，ZD 为最短路径矩阵）计算出所有路径的绕行贡献值矩阵；从绕行贡献值矩阵中筛选出最大绕行贡献值进入队列，并按绕行贡献值降序排序。将绕行贡献值从队列中取出，并提出路径信息进行累加堆栈，入栈时，累加路程值及重量值，一旦路程值或重量值达到限制条件，则出栈，利用贪婪思想尽可能多的组合路径；最后把规划好后的结果存储到数据库中，并用百度地图API 显示出来。多车多点路径规划算法及流程如图3 所示。

图3 路径规划算法流程

3.5 其他功能服务的实现

司机管理模块中的工作状态信息主要是由司机的手机App 传输过来的信息，这个包括司机工作时间长短、驾驶路程、驾驶时间等，App 可以通过百度地图SDK 来完成信息获取，获取后可以通过WebService 技术，把数据添加到数据库，再由司机管理模块查询出来。

车辆管理模块中的车辆运行情况主要是通过百度地图SDK 来完成信息获取，包括车辆车速、路程、剩下路程，其他的剩下负载信息要司机输入，这些信息也是用WebService 技术实现传输到数据库中。

4 结语

本文针对多车多点在多条件限制下设计了智能路径规划云平台，该平台主要包括管理员端和移动App端，在管理员端对司机、车辆和客户进行管理，同时利用多车多点路径规划算法进行最短路径规划和车辆调度，司机只需要通过移动App 登录到云平台即可查看任务，按规划路径进行导航。本平台的关键技术可以应用到物流企业、公交路线规划、无人机导航、无人驾驶、机器人控制、货拉拉、美团外卖等很多行业。通过物流公司的多次试验，该平台能实现到多个客户点，在考虑车辆刚好满载和不超出车辆限程的情况下，智能规划出遍历所有客户点的最快路线。