多車(chē)多點(diǎn)智能路徑規(guī)劃云平臺(tái)的研究與實(shí)現(xiàn)

李淑飛，駱劍鋒

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

0 引言

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

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

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

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

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

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

2.1 平臺(tái)中運(yùn)行的各種功能服務(wù)

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

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

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

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

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

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

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

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

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

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

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

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

3.2 移動(dòng)端技術(shù)

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

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

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

3.4 多車(chē)多點(diǎn)路徑規(guī)劃功能實(shí)現(xiàn)

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

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

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

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

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

4 結(jié)語(yǔ)

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