多車多點智能路徑規劃云平臺的研究與實現

李淑飛，駱劍鋒

（東莞職業技術學院計算機工程系，東莞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 登錄到云平臺即可查看任務，按規劃路徑進行導航。本平臺的關鍵技術可以應用到物流企業、公交路線規劃、無人機導航、無人駕駛、機器人控制、貨拉拉、美團外賣等很多行業。通過物流公司的多次試驗，該平臺能實現到多個客戶點，在考慮車輛剛好滿載和不超出車輛限程的情況下，智能規劃出遍歷所有客戶點的最快路線。