李淑飛，駱劍鋒

（東莞職業(yè)技術(shù)學(xué)院計算機工程系，東莞523808）

0 引言

在當(dāng)前流行的車輛導(dǎo)航軟件中，基本上是針對出發(fā)地與目的地兩個地點、且是對當(dāng)前單一車輛進行導(dǎo)航，缺乏對多個目的地統(tǒng)籌規(guī)劃和回程安排，不能合理安排車輛，管理用戶和司機。物流企業(yè)管理軟件功能雖然比較齊全，但也不能實現(xiàn)多條件下多車多點的路徑規(guī)劃及導(dǎo)航。而現(xiàn)實中貨運公司、快遞公司、校車管理、公交車管理等除了能對車輛、客戶等進行管理外，更重要的是要對多輛車和多目的地在限制條件下進行智能規(guī)劃路線，使得路線最短[1]。多車多點智能路徑規(guī)劃云平臺（簡稱云平臺）能把用戶、司機、車輛、路徑規(guī)劃相關(guān)對象合理地管理，在多車多點智能優(yōu)化算法的基礎(chǔ)上，實現(xiàn)資源的整合優(yōu)化調(diào)度和共享[2]。該平臺不但可以實現(xiàn)科學(xué)導(dǎo)航，而且使得車輛在運輸過程中，能兼顧全局，分工合作，使運輸任務(wù)更有效率、更經(jīng)濟、更環(huán)保。

1 智能路徑規(guī)劃云平臺功能架構(gòu)

本云平臺在考慮車輛剛好滿載和不超出車輛限程的情況下，遍歷所有客戶，能通過多車多點限重限程智能路徑規(guī)劃算法規(guī)劃出最優(yōu)路徑和導(dǎo)航，同時能對司機進行管理，合理調(diào)度車輛，是多車輛調(diào)度、多點路徑規(guī)劃、多條件限制及實時路況、收發(fā)業(yè)務(wù)的智能云平臺。該平臺主要分管理員端和移動端App 端，管理員端主要包括司機管理、車輛管理、智能路徑規(guī)劃、客戶信息管理、與車輛通訊五大功能，其核心功能是完成智能路徑規(guī)劃，并將規(guī)劃好后的路徑保存到數(shù)據(jù)庫中。移動App 端主要是司機通過手機登錄到云平臺，在手機App 上查看任務(wù)，并按云平臺規(guī)劃好的路徑進行導(dǎo)航及通訊。多車多點智能路徑規(guī)劃云平臺的功能架構(gòu)如圖1 所示。

圖1 智能路徑規(guī)劃云平臺功能架構(gòu)

2 智能路徑規(guī)劃云平臺的功能設(shè)計

由于多車輛多地點的路徑規(guī)劃復(fù)雜度高、運算量大，為了保證軟件運行不會死機，有效解決大并發(fā)量下系統(tǒng)的處理能力，需要在路徑規(guī)劃求解中首先用神經(jīng)網(wǎng)絡(luò)對客戶進行分區(qū)域分組，然后在分組的基礎(chǔ)再進行路徑規(guī)劃[3]，同時利用負(fù)載均衡技術(shù)，使得軟件運行的壓力分擔(dān)到不同的服務(wù)器上，從而保證平臺穩(wěn)定運行。因此，本平臺除了完成管理員端運行的各種功能服務(wù)[4]外（包括多車多點多條件限制的路徑規(guī)劃核心功能）設(shè)計，還需要設(shè)計手機端App，司機通過App 查詢?nèi)蝿?wù)、進行導(dǎo)航和通訊，同時實現(xiàn)負(fù)載均衡。

2.1 平臺中運行的各種功能服務(wù)

云平臺運行的主要功能服務(wù)包括司機管理、車輛管理、客戶管理、與車輛通訊及智能路徑規(guī)劃算法。

（1）司機管理：此功能管理司機相關(guān)信息，包括司機駕駛的歷史記錄，方便企業(yè)對司機進行績效管理，同時也方便管理員對司機進行綜合考慮，分配任務(wù)時有根據(jù)。

（2）車輛管理：此功能可以了解企業(yè)內(nèi)各輛車的情況，如車輛的負(fù)載量、運行時間、行駛路程等，以便對車輛在一段時間里的行駛路程、行駛時間、載貨量等信息進行分類匯總、統(tǒng)計分析，有利于車輛的合理安排及維護。

（3）客戶信息管理：客戶是企業(yè)的珍貴資源，必須對客戶信息管理進行很好地管理，如客戶的地理位置、收貨量、通信電話等，這部分功能是路徑規(guī)劃功能的基礎(chǔ)信息，同時也可以對這些信息進行統(tǒng)計分析，有利于企業(yè)了解優(yōu)質(zhì)客戶資源。

（4）與車輛通訊：在考慮司機在駕駛過程中的安全情況下，實現(xiàn)司機與公司的交流溝通，及時解決一些臨時、緊急、特殊事情和突發(fā)事件。

（5）多車多點智能路徑規(guī)劃：用智能算法調(diào)度企業(yè)內(nèi)所有可用車輛，在考慮限重限程的情況下，遍歷所有客戶的最優(yōu)路徑規(guī)劃方案及車輛安排方案。

2.2 云平臺中的負(fù)載均衡

通過司機手機上App 實現(xiàn)負(fù)載均衡的功能，把司機的訪問壓力分散到不同的客戶點服務(wù)器上，同一組的地點由客戶點服務(wù)器算出遍歷這組內(nèi)所有點的路徑規(guī)劃，如果有大量的地點，則可以分開進行路徑規(guī)劃，盡量把規(guī)劃的計算量減少，從而保證服務(wù)器不會由于過大的訪問量而癱瘓[5]。云平臺的性能數(shù)據(jù)庫服務(wù)器，保存著各個客戶點服務(wù)器的性能信息，手機訪問客戶點服務(wù)器前，先從這個數(shù)據(jù)庫中查詢比較空閑的客戶點服務(wù)器信息，再通過這個信息決定訪問哪個客戶點服務(wù)器。

3 智能路徑規(guī)劃云平臺功能技術(shù)實現(xiàn)

本平臺采用多層次平臺架構(gòu)，在管理員端運用Windows 編程完成司機、車輛、客戶等信息管理和路徑規(guī)劃，手機App 端Android 編程登錄并讀取規(guī)劃信息并進行導(dǎo)航。

3.1 服務(wù)器端技術(shù)

在服務(wù)器端主要使用Windows 編程，利用SQL 數(shù)據(jù)庫對各種信息進行存放，再使用百度API 計算出客戶間的最短路徑信息、顯示地圖、路徑信息等；用JavaScript 調(diào)用百度API；用C＃編程實現(xiàn)對JavaScript 中百度API 的路徑數(shù)據(jù)進行提取，并存放到數(shù)據(jù)庫中，移動設(shè)備通過WebService 技術(shù)讀取這些信息，然后在手機App 上重現(xiàn)路徑規(guī)劃的地圖與導(dǎo)航。

3.2 移動端技術(shù)

在移動設(shè)備端采用Android 移動開發(fā)技術(shù)。手機通過百度SDK 實現(xiàn)地圖導(dǎo)航顯示，獲取車輛經(jīng)緯信息、車速、平均車速、路程等功能；通過多線程編程，對由于網(wǎng)絡(luò)傳輸產(chǎn)生信息延遲問題進行處理；通過Web-Service 技術(shù)實現(xiàn)通信，包括讀取數(shù)據(jù)庫中的路徑規(guī)劃方案信息、企業(yè)發(fā)送給司機的信息、權(quán)限信息等，也能向數(shù)據(jù)庫添加車輛經(jīng)緯信息、車速、平均車速、路程等信息；利用ViewDragHelper 類解決中手勢處理過于復(fù)雜的問題，用Text2Speech 技術(shù)，實現(xiàn)文本到語音的轉(zhuǎn)換。

3.3 云負(fù)載均衡技術(shù)

云平臺中有多個路徑規(guī)劃服務(wù)器和一個性能數(shù)據(jù)庫服務(wù)器，性能數(shù)據(jù)庫服務(wù)器保存著各個路徑規(guī)劃服務(wù)器的性能信息，根據(jù)用戶訪問數(shù)量、用戶使用習(xí)慣、服務(wù)器當(dāng)前性能來統(tǒng)籌規(guī)劃服務(wù)器的使用。通過WebService 技術(shù)統(tǒng)計服務(wù)器訪問數(shù)量，通過對數(shù)據(jù)庫中的訪問來分析出用戶的使用習(xí)慣；而服務(wù)器性能則通過C＃的PerformanceCounter 技術(shù)對各服務(wù)器CPU、內(nèi)存、網(wǎng)絡(luò)接口、硬盤等性能進行監(jiān)視；最后把這些信息和分析的結(jié)果發(fā)送到用戶的移動設(shè)備上的功能模塊。手機在訪問路徑規(guī)劃服務(wù)器前，先從性能數(shù)據(jù)庫服務(wù)器中查詢比較空閑的服務(wù)器信息，再通過這些信息決定訪問哪個服務(wù)器，這樣就把司機的訪問分散到不同的服務(wù)器上，從而實現(xiàn)了云平臺的負(fù)載均衡，如圖2 所示。

3.4 多車多點路徑規(guī)劃功能實現(xiàn)

路徑規(guī)劃是本平臺的核心功能模塊，云平臺首先從數(shù)據(jù)庫中讀取各個客戶點的經(jīng)緯度，利用模糊神經(jīng)網(wǎng)絡(luò)根據(jù)收送貨點是否靠近進行分區(qū)域，如果靠近歸為一類區(qū)，不靠近歸為另一類區(qū)；同時數(shù)據(jù)庫讀取客戶收送貨的重量及車輛的載重信息，根據(jù)這些信息使用多值背包算法進一步對區(qū)域內(nèi)的客戶點進行分組。接下來結(jié)合百度地圖API 和Floyd 最短路徑算法[6]算出各地點間的最短路徑，得出最短路徑矩陣。在繞行遍歷思想中，對于遍歷所有點，再回到起始點，環(huán)繞一周路徑最短[7]，因此利用繞行公式RX（i，j）=ZD（i，0）+ZD（j-1，0）-ZD（i，j）（RX 是繞行貢獻值，ZD 為最短路徑矩陣）計算出所有路徑的繞行貢獻值矩陣；從繞行貢獻值矩陣中篩選出最大繞行貢獻值進入隊列，并按繞行貢獻值降序排序。將繞行貢獻值從隊列中取出，并提出路徑信息進行累加堆棧，入棧時，累加路程值及重量值，一旦路程值或重量值達到限制條件，則出棧，利用貪婪思想盡可能多的組合路徑；最后把規(guī)劃好后的結(jié)果存儲到數(shù)據(jù)庫中，并用百度地圖API 顯示出來。多車多點路徑規(guī)劃算法及流程如圖3 所示。

圖3 路徑規(guī)劃算法流程

3.5 其他功能服務(wù)的實現(xiàn)

司機管理模塊中的工作狀態(tài)信息主要是由司機的手機App 傳輸過來的信息，這個包括司機工作時間長短、駕駛路程、駕駛時間等，App 可以通過百度地圖SDK 來完成信息獲取，獲取后可以通過WebService 技術(shù)，把數(shù)據(jù)添加到數(shù)據(jù)庫，再由司機管理模塊查詢出來。

車輛管理模塊中的車輛運行情況主要是通過百度地圖SDK 來完成信息獲取，包括車輛車速、路程、剩下路程，其他的剩下負(fù)載信息要司機輸入，這些信息也是用WebService 技術(shù)實現(xiàn)傳輸?shù)綌?shù)據(jù)庫中。

4 結(jié)語

本文針對多車多點在多條件限制下設(shè)計了智能路徑規(guī)劃云平臺，該平臺主要包括管理員端和移動App端，在管理員端對司機、車輛和客戶進行管理，同時利用多車多點路徑規(guī)劃算法進行最短路徑規(guī)劃和車輛調(diào)度，司機只需要通過移動App 登錄到云平臺即可查看任務(wù)，按規(guī)劃路徑進行導(dǎo)航。本平臺的關(guān)鍵技術(shù)可以應(yīng)用到物流企業(yè)、公交路線規(guī)劃、無人機導(dǎo)航、無人駕駛、機器人控制、貨拉拉、美團外賣等很多行業(yè)。通過物流公司的多次試驗，該平臺能實現(xiàn)到多個客戶點，在考慮車輛剛好滿載和不超出車輛限程的情況下，智能規(guī)劃出遍歷所有客戶點的最快路線。