[發(fā)明專利]基于混合量子算法的智慧車輛調(diào)度管理系統(tǒng)及其工作方法

在審

• 申請?zhí)枺?/td>: 201710809954.0
• 申請日: 2017-09-11
• 公開（公告）號: CN107609816A
• 公開（公告）日: 2018-01-19
• 發(fā)明（設(shè)計）人: 寧濤;房麗華;黃明;梁旭;焦璇
• 申請（專利權(quán)）人: 大連交通大學(xué)
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06N3/00
• 代理公司: 大連東方專利代理有限責(zé)任公司21212
• 代理人: 李洪福

技術(shù)領(lǐng)域

本發(fā)明涉及一種智慧車輛調(diào)度管理系統(tǒng)的平臺和方法，尤其是一種基于混合量子算法技術(shù)的智慧車輛調(diào)度系統(tǒng)的平臺及方法，屬于智能計算技術(shù)與互聯(lián)網(wǎng)應(yīng)用管理技術(shù)領(lǐng)域。

背景技術(shù)

隨著世界經(jīng)濟(jì)的飛速發(fā)展和科學(xué)技術(shù)的快速進(jìn)步，物流業(yè)已經(jīng)逐漸發(fā)展成為國民經(jīng)濟(jì)的重要基礎(chǔ)產(chǎn)業(yè)。車輛路徑問題(Vehicle Routing Problem,VRP)作為運(yùn)輸配送系統(tǒng)的關(guān)鍵環(huán)節(jié)已成為引人注意的焦點問題之一，并成為運(yùn)籌學(xué)領(lǐng)域的經(jīng)典優(yōu)化組合問題，也引起了網(wǎng)絡(luò)分析、應(yīng)用數(shù)學(xué)以及圖論等領(lǐng)域?qū)＜业难芯颗d趣。

雖然國內(nèi)外學(xué)者已經(jīng)從模型優(yōu)化、搜索技術(shù)和求解方法等方面對VRP展開了眾多探索性研究，并取得了豐碩的階段性成果，但是VRP的求解仍存在一些問題：

(1)對帶時間窗不確定VRP，研究的模型數(shù)量不少，但研究點比較單一，實際問題中約束條件往往具有不確定性，綜合考慮車輛、客戶需求、路況信息等多種不確定因素的問題需要更深的研究。

(2)對有同時集送貨VRP，當(dāng)問題規(guī)模較大時，已有方法的求解效率明顯降低甚至停滯。主要原因是當(dāng)問題規(guī)模增大時，解的狀態(tài)空間也隨之迅速膨脹。

(3)現(xiàn)有算法解決的問題大多局限于有明確信息的情況下，而客戶點具體位置、客戶重要程度、路況隨時間段變化的通暢程度等客戶方和交通環(huán)境等具體變化因素并未加以考慮。問題的求解過程應(yīng)該對客戶的動態(tài)需求和路況的動態(tài)變化進(jìn)行細(xì)致的研究。

發(fā)明內(nèi)容

為解決現(xiàn)有技術(shù)存在的上述問題，本發(fā)明要設(shè)計一種能夠進(jìn)行大規(guī)模求解、解決不確定車輛路徑問題、能夠?qū)討B(tài)數(shù)據(jù)進(jìn)行實時處理預(yù)測的基于混合量子算法的智慧車輛調(diào)度管理系統(tǒng)及其工作方法。

為了實現(xiàn)上述目的，本發(fā)明的技術(shù)方案如下：基于混合量子算法的智慧車輛調(diào)度管理系統(tǒng)，包括帶時間窗不確定車輛調(diào)度模塊、同時集送貨車輛調(diào)度模塊和動態(tài)車輛重調(diào)度模塊；

所述的帶時間窗不確定車輛調(diào)度模塊包括用戶時間窗設(shè)置模塊和不確定需求變化設(shè)置模塊，用戶時間窗設(shè)置模塊針對用戶提出的收貨時間區(qū)間以及用戶的重要等級來設(shè)置配送的優(yōu)先級和設(shè)置初始方案；不確定需求變化設(shè)置模塊針對配送需求的模糊不確定問題設(shè)置不同的配送方案；

所述的同時集送貨車輛調(diào)度模塊包括送貨需求調(diào)度模塊和集貨需求調(diào)度模塊，送貨需求調(diào)度模塊對有同時集送貨的配送情況設(shè)置合理的送貨配送方案，集貨需求調(diào)度模塊對有同時集送貨的配送情況設(shè)置合理的集貨配送方案；

所述的動態(tài)車輛重調(diào)度模塊包括動態(tài)變化設(shè)置模塊和重調(diào)度操作模塊，動態(tài)變化設(shè)置模塊針對配送過程中可能出現(xiàn)的不同動態(tài)干擾因素進(jìn)行分析以及設(shè)計相應(yīng)的配送方案，調(diào)度操作模塊主要對配送過程必須修改初始調(diào)度方案的情況進(jìn)行實時重調(diào)度方案的生成和更新。

基于混合量子算法的智慧車輛管理系統(tǒng)的工作方法，包括以下步驟：

A：求解帶時間窗不確定車輛調(diào)度問題

為了避免在搜尋過程中量子粒子群陷入局部最優(yōu)解，在原有粒子群的基礎(chǔ)上創(chuàng)建兩個子相量子粒子群。兩個子相量子粒子群開始時在相反的方向以不同的速度進(jìn)行局部尋優(yōu)，而主相量子粒子群粒子速度的更新借助于當(dāng)前被所有子相搜索到的全局最優(yōu)點。實現(xiàn)的具體步驟如下：

A1：對粒子群的規(guī)模、慣性權(quán)值、加速系數(shù)、壓縮因子、所有粒子的初始位置和初始速度、允許的最大迭代次數(shù)、粒子群的子相數(shù)目以及每個子相的滾動優(yōu)化結(jié)束指標(biāo)和計數(shù)器進(jìn)行初始化；所述的粒子群的規(guī)模為粒子群的粒子數(shù)目；

A2：根據(jù)目標(biāo)函數(shù)對每個粒子的初始適應(yīng)值進(jìn)行評價、對每個粒子的初始個體歷史最優(yōu)位置以及個體最優(yōu)適應(yīng)值進(jìn)行保存，同時對初始全局歷史最優(yōu)位置以及最優(yōu)適應(yīng)值進(jìn)行保存；

A3：優(yōu)化第i個子相粒子；

A4：判斷i是否超過粒子群相數(shù)，如果超過，則令i＝0，并轉(zhuǎn)到步驟A5；否則，令i＝i+1，然后轉(zhuǎn)到步驟A3；

A5：如果適應(yīng)值的誤差已經(jīng)達(dá)到設(shè)定的適應(yīng)值誤差限或者執(zhí)行的迭代次數(shù)超過允許的最大迭代次數(shù)，則優(yōu)化終止，同時對全局歷史最優(yōu)適應(yīng)值和最優(yōu)位置進(jìn)行輸出；否則，轉(zhuǎn)到步驟A3，并繼續(xù)優(yōu)化。

B：求解有同時集送貨需求的車輛調(diào)度問題

B1：生成初始解P(t)

基于混沌理論生成初始解，假設(shè)用Popu表示種群規(guī)模，用Sum表示客戶數(shù)量，用K表示配送車輛數(shù)目，則量子個體的編碼長度表示成n(Sum+K-1)，按如下步驟進(jìn)行初始化：

B11：先生成Popu/10個初始解，然后根據(jù)二進(jìn)制編碼方法將其映射為量子個體，從而產(chǎn)生種子量子個體；