基于改進遺傳算法的網(wǎng)約車共乘優(yōu)化調(diào)度模型求解

胡 凱，袁鵬程，胡忠愷 Hu Kai, YUAN Pengcheng, HU Zhongkai

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引 言

網(wǎng)約車共乘優(yōu)化調(diào)度模型（DARP-M） 是近些年來在交通領(lǐng)域上逐漸興起的一類調(diào)度模型，屬于帶能力約束的車輛路徑優(yōu)化問題（Capacitated Vehicle Routing Problem, CVRP），它直接影響車輛總行駛距離和最大滿載條件下的車輛使用數(shù)量。隨著互聯(lián)網(wǎng)的高速發(fā)展以及當(dāng)下疫情現(xiàn)狀，DARP-M 模型在公共交通領(lǐng)域得到了廣泛應(yīng)用，具有重要的理論以及實際應(yīng)用價值。

車輛路徑問題（Vehicle Routing Problem, VRP） 是一個典型的NP-hard 問題，而本文中提出的網(wǎng)約車共乘優(yōu)化模型是在這個問題的基礎(chǔ)上增加了車輛載重約束以及車輛路徑約束，因此在路徑優(yōu)化的過程需要綜合考慮車輛數(shù)量、乘客分配、路徑選擇等因素，使得運行總費用最少。但是在具體求解的過程中，通常會存在一些問題：約束限制了優(yōu)化對象新解的生成，會降低算法的全局搜索能力，且傳統(tǒng)遺傳算法極易陷入局部最優(yōu)解，隨著約束的增加，這一影響愈加明顯。其次，針對約束與DARP-M模型的融合，算法很難在結(jié)構(gòu)、復(fù)雜度、精度上做出整體的簡單高效?；谏鲜鰡栴}，眾多學(xué)者從合乘問題以及構(gòu)建高效解決多約束車輛路徑問題的算法這兩個方面進行入手展開研究。

1 相關(guān)研究

目前合乘問題已得到國內(nèi)外學(xué)者的廣泛關(guān)注并取得了豐富的成果。在如何求解網(wǎng)約車合乘模型的過程中，研究的主要目標是達到最優(yōu)化的運營成本。優(yōu)化原本的運營方式就是在滿足乘客需求的同時，盡可能的最小化路程或成本。陳久梅等提出變鄰域搜索算法來解決開放式帶時間窗車輛路徑問題。Firat、Goekay討論了在最大等待時間和最大乘坐時間約束下的合乘問題的可行性測試。符卓等針對帶軟時間窗的需求依訂單拆分車輛路徑問題及其優(yōu)化算法進行研究，建立了問題的數(shù)學(xué)模型，設(shè)計了求解的禁忌搜索算法。范厚明等針對帶模糊需求與模糊時間窗的車輛路徑問題，為提高種群的多樣性，改進了交叉算子，在引入局部優(yōu)化算法及擂臺法則的基礎(chǔ)上，設(shè)計了適合求解多目標車輛路徑問題的混合遺傳算法。Hame設(shè)計了超鏈接誘導(dǎo)主題搜索（HITS），根據(jù)樞紐分數(shù)對節(jié)點進行排名，并為回溯算法提供了指導(dǎo)，該算法可以有效地找到合乘問題的可行解決方案。王超為求解帶時間窗和同時取送貨的車輛路徑問題（VRPSPDTW），提出一種離散布谷鳥（DCS） 算法。覃運梅在綜合考慮了司機和乘客雙方利益的基礎(chǔ)上，以車輛行駛路程作為優(yōu)化目標，建立了出租車合乘模型。在求解算法方面，Huang Yan提出了一個動態(tài)樹算法，相比于分枝定界算法和整數(shù)規(guī)劃算法能夠更好地調(diào)度動態(tài)請求和動態(tài)路徑調(diào)整，并結(jié)合了上海的出租車真實數(shù)據(jù)進行實驗驗證。Hosni 等將共享出租車匹配問題和出租車最優(yōu)路徑計算問題作為一個混合整數(shù)規(guī)劃來處理，結(jié)合拉格朗日法進行求解，并提出了兩種啟發(fā)式算法來獲得高質(zhì)量的可行解。Quo, Jingmei 等提出了一種基于時間依賴性的啟發(fā)式算法,來保證給定的取貨和交貨順序是否存在可行。潘雯雯等以多車型和需求拆分閾值為新約束，建立需求可拆分的多車型車輛路徑問題（SDHFVRP） 混合整數(shù)規(guī)劃模型；提出以路徑優(yōu)化和路徑改進相結(jié)合的兩階段算法（TPA）。馬傲雯等提出采用時間組替代傳統(tǒng)的距離匹配，采用A 星搜索算法完成車輛的實時訂單順序，并確定該訂單的劃分車輛。Nourinejad 等提出了一種基于分布式拼車系統(tǒng)的匹配算法來解決多乘客和多司機的配對問題，并提高了共享出行中司機和乘客的匹配成功率。Masoud 等提出了一種實時優(yōu)化的乘車匹配算法，在最大化系統(tǒng)中服務(wù)的乘客數(shù)量的同時，通過考慮用戶對出行需求的偏好以及最小化換乘次數(shù)和乘客等待時間，使出行盡可能舒適。Parragh 等在考慮合乘問題時，提出了一種混合列生成和大鄰域搜索算法，并考慮時間窗口等限制，使總路徑成本最小化。熊浩等針對可拆分車輛路徑問題（SDVRP），其求解方法與需求不可拆分的VRP 問題有較大的區(qū)別，本文提供了一種新的求解思路——基于雙層規(guī)劃模型的三階段禁忌算法。揭婉晨等研究含時間窗的多車型電動汽車車輛路徑問題，建立了一個混合整數(shù)規(guī)劃模型，并利用分支定價算法求其最優(yōu)解。穆東等為提高傳統(tǒng)串行模擬退火算法求解時間依賴型車輛路徑問題的效率，提出一種并行模擬退火算法。顏瑞等研究包含時間窗、多車場因素的二維裝箱車輛路徑問題，建立相應(yīng)的數(shù)學(xué)模型，并提出求解該問題的一種新的混合算法，混合算法由量子粒子群算法和引導(dǎo)式局部搜索算法組成。針對帶時間窗車輛路徑問題（VRPTW），提出了混合種群增量學(xué)習(xí)算法（HPBIL），用于同時最小化車輛數(shù)和總行駛距離。

通過引入不同場景下的約束，基本的車輛路徑問題能擴展出大量不同的衍生問題，而基礎(chǔ)的求解框架與優(yōu)化方法會直接影響算法的構(gòu)建難度與求解效果，因此，基于傳統(tǒng)算法改進出通用性強且易于數(shù)據(jù)耦合的優(yōu)化方法具有相當(dāng)重要的意義。

基于上述情況，為高效求解DARP-M 問題，本文提出一種結(jié)構(gòu)簡單、通用性較強的多路徑優(yōu)化方法，并且針對不同車輛的運載能力約束以及路徑約束提出一種帶有較強斂優(yōu)屬性的改進遺傳算法（Improved Genetic Algorithm，IGA），結(jié)構(gòu)上基于遺傳算法（Genetic Algorithm，GA） 的整體框架，為了提高算法的全局搜索能力，依次設(shè)計了初始可行解的生成、較優(yōu)解的接收、靈活的交叉變異策略，詳細地解析了IGA 算法的運算過程以及優(yōu)化原理，然后通過對不同算例進行對比試驗，驗證了此類算法的有效性和魯棒性。

2 DARP-M 的數(shù)學(xué)模型

其中：式（1） 為DARP-M 的總求解目標，即車輛服務(wù)的總成本最少；式（2） 表示每輛車上的乘客不能超過車輛容量限制；式（3） 表示每位乘客都需要得到配送服務(wù)；式（4） 表示每條上車路徑的客戶組成；式（5） 表示每條下車路徑的客戶組成；式（6） 表示上下點必須保證在指定范圍內(nèi)；式（7） 限制每位乘客只能由一個配送車輛完成任務(wù)；式（8） 表示如果是第k輛車參與了接送服務(wù)，則sign n()=1，否則sign n()=0。

DARP-M 場景如圖1 所示：

圖1 DARP-M 場景圖

3 IGA 算法的設(shè)計與實現(xiàn)

本章從算法框架、生成初始可行解、交叉變異操作以及較優(yōu)解的篩選這四個方面進行闡述，重點設(shè)計了結(jié)構(gòu)清晰且各個功能模塊相對獨立的DARP-M 模型框架，在原有的遺傳算法的基礎(chǔ)上，提出了針對多約束模型的IGA 算法。

3.1 基于多約束條件的遺傳算法框架

DARP 作為VRP 所衍生的一類車輛調(diào)度問題，更符合當(dāng)下實際需求，DARP-M 模型也是DARP 的衍生模型，而構(gòu)建較好的算法求解框架，是高效求解此類問題的關(guān)鍵。遺傳算法因其使用廣泛且結(jié)構(gòu)簡單而被較多應(yīng)用于求解多約束耦合問題。因此，本文結(jié)合相關(guān)路徑優(yōu)化特征，來構(gòu)建基于遺傳算法的DARP-M 問題求解框架。如圖2 所示，本文所涉及的GA 算法框架大致分為三步，首先是得出符合限制條件的車輛與乘客的分配方式（GM Operation），根據(jù)求得的分配方式得到初始可行解（FDF Operation）。結(jié)合具體的遺傳算法操作，生成的初始可行解和鄰域結(jié)構(gòu)的變換是在考慮約束滿足的條件下來產(chǎn)生新解（GA Operation），較優(yōu)解的篩選就是以可行解的數(shù)值優(yōu)化為目標，在新解加入后不斷進行迭代選優(yōu)?？蚣艿暮诵乃枷刖褪菍⑸蓾M足約束的可行解與目標優(yōu)化相隔開，各個模塊的功能明確且相互獨立，便于程序的設(shè)計和更改。在面對不同問題時，只需要根據(jù)模型特征對初始解的生成進行更改，對交叉變異操作及更優(yōu)解的選取進行改進即可。

圖2 多約束條件下的改進算法框架

3.2 生成初始可行矩陣（GM Operation: Generate Initial Feasible Matrix）

矩陣中每一行之和不能超過車輛容量的限制，且矩陣的每一列之和必須等于1，表示一位乘客只能選擇一輛車，中途不得上下車。

3.3 求出可行的行駛費用（FDF Operation:Find out feasible Driving Fee）

3.4 遺傳算法（GA Operation：Genetic Algorithm）

在上一步中通過循環(huán)得到初始可行解，這里用傳統(tǒng)遺傳算法的步驟對初始可行解進行選擇評估、交叉、變異等操作，并且將之前迭代的最優(yōu)解放入變異操作后的矩陣中，形成一個新的矩陣A。算法中的選擇評估操作即將原本劣等解的位置替換為優(yōu)質(zhì)解，從而達到改進整個種群的目的，交叉以及變異過程見后幾節(jié)。算法的偽代碼如下：

（1） 設(shè)置程序迭代次數(shù)NP；適應(yīng)值Fit；行程費用G；費用最大值maxG; 費用最小值minG;

（2） 前面的運算中已經(jīng)求得了一個費用，記為G；

（3） Fit=1- (G-minG )/ (maxG-minG )；

（4） For i=1∶NP；

（5） 對矩陣A 進行選擇評估操作生成新矩陣nf；

（6） EndFor；

（7） For j=1:NP；

（8） 對矩陣nf 進行交換、變異操作生成新矩陣A；

（9） If 未達到運算次數(shù)；

（10） 執(zhí)行FDF Operation；

（11） 根據(jù)A求得一個新的最小費用，記為G；

（12） If G≤G；

（13） 最小費用不變；

（14） Else；

（15） 將最小費用改為G；

（16） EndIf；

（17） Else；

（18） 計算出路徑信息；

（19） EndFor。

3.5 交叉操作（Overlapping Operation）

將矩陣nf 中兩連續(xù)的子矩陣提取出來，如果兩子矩陣完全相同，則無需進行交叉操作，反之，則將兩個矩陣分別表示成數(shù)組編碼的形式，將各個乘客位置用數(shù)字表示出來，按車輛順序排列。

交叉操作遺傳操作中起著至關(guān)重要的作用，它可以提高各個有效解之間的差異度，以便于快速收斂，考慮是在整數(shù)編碼的操作環(huán)境下，本文使用的是兩種交叉操作方式：單點交叉和兩點交叉。對于這兩種交叉方式的選擇，設(shè)置交叉率為θ，并且隨機生成[0,1 ]之間的隨機數(shù)δ，如果θ≤δ，則使用單點交叉，反之，則使用兩點交叉。單點交叉操作如圖3 所示，兩點交叉操作如圖4 所示。

圖3 單點交叉操作

圖4 兩點交叉操作

3.5.1 單點交叉操作

首先是給定兩組編碼parent、parent，在一行編碼的任意位置隨機選擇一個交叉點（箭頭所指位置），交換兩行編碼在交叉點后的元素，若一行編碼中存在兩個相同的序號，那么在另一行編碼中選擇相同位置的序號，兩兩彼此進行交換，重復(fù)此步驟，直到無重復(fù)序號，得到子代編碼child與child。

3.5.2 兩點交叉操作

首先是給定兩組編碼parent、parent，在一行編碼的任意位置隨機選擇兩個交叉點（箭頭所指位置），交換兩行編碼中在兩交叉點之間的元素，若一行編碼中存在兩個相同的序號，那么在另一行編碼中選擇相同位置的序號，兩兩彼此進行交換，重復(fù)此步驟，直到無重復(fù)序號，得到子代編碼child與child。

3.6 變異操作（Mutation Operation）

變異操作是指在編碼中隨機引入突變來增加種群的多樣性，消除算法在無希望地區(qū)的停滯，探索新搜索區(qū)域的過程。變異率為λ，當(dāng)隨機數(shù)δ≤λ 時，對數(shù)組進行變異操作。本章介紹的變異操作也有兩種，分別是局部變異和整體變異。局部變異是以不改變車輛搭載乘客的數(shù)量下進行的，只有在局部變異無效后，才會使用整體變異。局部變異流程如圖5 所示，整體變異流程如圖6 所示。

圖5 局部變異流程圖

圖6 整體變異流程圖

3.6.1 局部變異操作

局部變異即將數(shù)組中任意抽出四個數(shù)字作為兩組進行兩兩交換。但是在進行變異的過程中，還應(yīng)注意保護優(yōu)質(zhì)解，由于變異的特性，之前可能求得的優(yōu)質(zhì)解，會在經(jīng)過變異后丟失。針對這一情況，選擇在每一次變異后對編碼進行還原，計算適應(yīng)值，設(shè)置具體的突變次數(shù)，將適應(yīng)度最好的保留下來進行下一次的運算。如圖5 所示，突變次數(shù)設(shè)為4 次。

3.6.2 整體變異操作

在執(zhí)行變異操作時，會出現(xiàn)在突變次數(shù)內(nèi)無法收斂的情況，這時就需要改變每位輛車搭乘乘客的數(shù)量。如圖6 所示，父代編碼用三種顏色來表明乘客搭乘的情況。圖例中二號和三號乘客乘坐第一輛車，一號和六號乘客乘坐第二輛車，其余四位乘客搭乘第三輛車，通過不斷改變乘客乘坐車輛的信息來達到變異的目的，在每一次變異后對編碼進行還原，計算適應(yīng)值，突變次數(shù)與上文一致，將適應(yīng)度最好的保留下來進行下一次的運算，如果整體變異后子代仍然無法優(yōu)于父代，或數(shù)值上等于父代，則結(jié)束變異，保留父代進入下一次的運算。

3.7 還原操作（Restore Operation）

圖7 部分變異后的還原操作

在部分變異操作無效后，需要整體變異來達到收斂效果，但整體變異打亂了車輛搭乘乘客的數(shù)量，因此，整體變異后的矩陣還原是按照乘客被分配的車輛來進行還原。圖8 表示的是經(jīng)過整體變異后矩陣還原的過程。

圖8 整體變異后的還原操作

4 算例分析

4.1 算例描述

假設(shè)存在兩個位置節(jié)點，分別作為提供合乘服務(wù)車輛的起點和終點，可提供服務(wù)的車輛有3 輛，其中2 輛是容量為3 人的出租車，一輛是容量為5 人的橋車，同時向8 位乘客提供共乘服務(wù)，并且這8 位乘客有3 個與可能的接送位置相對應(yīng)。配送中心位置、乘客數(shù)量、乘客可能的接送位置等數(shù)據(jù)參考DARP 相關(guān)文獻。配送中心坐標分別為(0,0 )和(20,20 )，而客戶可能的接送位置坐標都是隨機且獨立的分布在[0,2 0 ]× [0,2 0 ]的矩形區(qū)域中。不同車輛的成本在上文已經(jīng)提到，這里a取12，a取8，h取0.7 元/公里，h取1.05 元/公里，各個節(jié)點的位置坐標如表1 所示：

表1 各節(jié)點位置坐標

4.2 算法參數(shù)的靈敏度分析

算法參數(shù)的合理設(shè)置對算法的有效性和計算效率有相當(dāng)重要的影響，本文中涉及到的參數(shù)：迭代次數(shù)、種群規(guī)模（Group Scale, GS）、交叉率、變異率以及不同參數(shù)相互組合的結(jié)果。此外，還有新加入的參數(shù)：平均運行時間（Average Running Time，ART）、運算結(jié)果平均值（Average Operation Result，AOR）、最優(yōu)值（Bes）t、迭代次數(shù)（Iters）、結(jié)果與最優(yōu)值的偏移度（Deviation Degree，DDE），DDE=(AOR-Best )/Best )*100%。

4.2.1 迭代次數(shù)（Iters）

迭代次數(shù)在算法中起到至關(guān)重要的作用，迭代次數(shù)過高會延長算法的運行時間，而迭代次數(shù)過低就會提前結(jié)束搜索結(jié)果,首先經(jīng)過多次使用程序計算得出最優(yōu)值，而后通過改變迭代次數(shù)獨立運算10 次，取得平均運算時間和平均運算結(jié)果,涉及到的參數(shù)：種群規(guī)模為20，交叉率0.8，變異率0.5，運算結(jié)果見表2，由表2 可以得出迭代次數(shù)與運算結(jié)果的平均值是呈現(xiàn)正比的關(guān)系，一般來說，在程序運行到20～30 次之內(nèi)，就基本上已經(jīng)達到最優(yōu)值或者趨近于最優(yōu)值，但隨著迭代次數(shù)的增加，平均運行時間也隨之大幅增加，由最后的結(jié)果可知，算例在30 次迭代之內(nèi)都接近得到最優(yōu)解，因此，本文設(shè)置迭代次數(shù)Iters=30。

表2 不同迭代次數(shù)下的運行結(jié)果

4.2.2 種群規(guī)模（Group Scale, GS）

設(shè)置種群規(guī)模，同樣取上述幾個參數(shù)值進行測試，表3 中給出了在不同的種群規(guī)模下，對算例進行獨立10 次運行的平均計算結(jié)果，迭代次數(shù)設(shè)為10，交叉率0.8，變異率0.5。由表3 可知，隨著種群規(guī)模的增大，運行結(jié)果也不斷趨于最優(yōu)，但優(yōu)化速度越來越慢，且運行時間大幅增加，考慮到解的質(zhì)量和運行時間，本文中種群規(guī)模取20。

表3 不同種群規(guī)模下的運行結(jié)果

4.2.3 交叉率與變異率

交叉率數(shù)值的大小用于決定交叉操作是單點交叉還是兩點交叉，這對于是否能夠保留親本特征是比較重要的。變異是遺傳算法的主要步驟之一，本文中的部分變異操作能夠篩選出局部最優(yōu)解的情況，而整體變異則能夠跳出局部最優(yōu)，以不同方向來尋找最優(yōu)解。本節(jié)通過設(shè)置了若干個不同的交叉率以及變異率，表4 是對算例在不同情況下運行10 次的平均測試結(jié)果，迭代次數(shù)為20，種群規(guī)模為10。由測試的運行時間與DDE 值可以看出，變異率與運行時間呈正相關(guān)，與偏移度呈負相關(guān)，當(dāng)交叉率為0.8，變異率為0.5 時，算法的求解時間與解的質(zhì)量較優(yōu)。

表4 不同交叉變異率下的運行結(jié)果

4.3 算例優(yōu)化結(jié)果

通過上述改進的遺傳算法以及參數(shù)設(shè)置，對案例進行求解分析。實驗環(huán)境為lntel（R） Core（TM） i5-6300HQ CPU@2.30GHz，操作系統(tǒng)為64 位Windows10，使用Matlab R2016a 進行編程。運算中迭代次數(shù)（Iters） 為30，種群規(guī)模為20，交叉率為0.8，變異率為0.5，運行時間為105.152s?；诎l(fā)出合乘請求的節(jié)點數(shù)據(jù)和提供服務(wù)的車輛數(shù)據(jù)等要求，求解本文構(gòu)建的DARP-M 模型，得出最優(yōu)合乘路徑有3 條如表5 所示。車輛的總運輸成本為128.794 元，包括三輛車的固定費用28 元。具體的路線圖以及適應(yīng)度進化曲線圖如圖9 及圖10 所示。

表5 具體的行駛路線情況

圖9 行駛路線圖

圖10 適應(yīng)度進化曲線

5 總 結(jié)

國內(nèi)外新冠肺炎病毒（COVID-19） 的爆發(fā)，對城市居民的日常生活造成了嚴重影響。在如今后疫情時代的大背景下，基于車輛路徑問題，提出了所要研究的DARP-M 模型，本文針對這一模型提出了IGA 算法，并綜合考慮了網(wǎng)約車車輛的運輸成本、車輛固定成本、路徑限制等。利用Matlab 編程對算例求解，可為疫情下的合乘車輛路徑優(yōu)化提供理論依據(jù)?；诒疚乃罁?jù)的背景是后疫情時代，對于乘客的要求沒有考慮在內(nèi)，每位乘客的允許等待時間都是不一致的，車輛必須要在要求的時間范圍內(nèi)接送乘客，此外，司機以及乘客的健康狀況沒有考慮在其中，在實際的情況下，乘客在體溫過高時，就不適宜再進行合乘服務(wù)了，需要額外分配的車輛進行接送，這個可以考慮作為下一步的研究方向。