帶時間窗車輛路徑規劃算法研究與實現

孫滬增，李章維，秦子豪，周曉根，張貴軍

1(浙江工業大學 信息工程學院，杭州 310023)

2(美國密歇根大學安娜堡分校 計算醫學與生物信息學系，美國 密歇根州 48109)

E-mail:zgj@zjut.edu.cn

1 引 言

隨著互聯網技術的迅速發展，傳統物流配送產業的優化轉型已迫在眉睫.車輛路徑問題作為物流配送產業研究的熱點問題之一，對物流產業的轉型升級有著指導意義.考慮時間窗因素的車輛路徑問題(VRPTW)，更加符合實際配送問題需求.因此，VRPTW問題得到國內外學術和產業界的廣泛關注[1].

VRPTW是一個NP-hard組合優化問題，傳統的精確算法只能解決規模相對較小的問題，且耗時較長，而現實物流配送往往涉及大規模的客戶群體，因此元啟發式算法由于其較好的收斂性往往成為解決此類問題的首選方案.這也促使了國內外學者對VRPTW問題轉向了元啟發式算法的研究.Alzaqebah等提出了一種通過限制差解的最大數量來避免人工蜜蜂盲目搜索，從而提高VRPTW收斂速度的優化人工蜂群算法[2]；Nalepa等提出了一種能夠平衡搜索空間的探索和利用的自適應模擬算法來解決VRPTW問題[3]；李珍萍等建立了多需求混合整數規劃模型，設計了一種求解模型的聯合優化遺傳算法，為解決實際問題提供了決策依據[4]；李兵飛等設計了一種改進的雙重進化人工蜂群算法來求解速度時變VRPTW問題，并通過實例驗證了模型和求解方法的有效性[5]；Akpinar等提出了一種蟻群系統和大鄰域搜索的混合算法，使得在求解過程大大提高了算法的多樣性[6]；Osaba等提出了一種漸進式離散螢火蟲算法，成功將螢火蟲算法應用到VRPTW問題的求解[7].

以上VRPTW問題的研究主要針對測試數據集來驗證算法的有效性.然而，結合實際路網的算法應用在現有文獻中還鮮有報道.本文針對帶時間窗的車輛路徑問題，設計了一種基于局部增強搜索策略混合的蟻群算法，通過標準數據集的測試驗證了算法對不同類型、不同時間窗寬度VRPTW的適用性；進一步基于浙江省杭州市路網數據集，基于ArcGIS平臺，設計并開發了一套物流配送系統.

2 帶時間窗的車輛路徑問題數學模型

假定模型配送中心只有一個，本文考慮如下VRPTW的數學模型[8,9,14,15]：

(1)

(2)

(3)

(4)

(5)

(6)

目標函數(1)表示完成所有客戶配送成本最?。患s束(2)表示每輛車配送的客戶需求總數不能大于車的最大裝載量；式(5)表示每個客戶點有且僅有一輛車為其服務；式(6)表示所有客戶點有且僅被配送一次；在上述模型基礎上引入如下時間窗約束條件：

(7)

如果違反時間窗約束條件就需要進行懲罰.設客戶i的時間窗范圍為[ai,bi]，Ti為車輛到達客戶i的時間，其中：ai為顧客i允許的最早服務時間，bi為顧客i允許的最遲服務時間.e為懲罰系數；半軟時間窗約束允許車輛到達i的時間早于ai但不允許晚于bi，早于ai配送客戶點i，必須等待至ai再為客戶i服務，因此需要支付一定的懲罰費用p(Ti)=e(ai-Ti)2，遲于bi配送的客戶點i則通過后續的時間窗約束直接剔除.

3 基于混合局部增強搜索策略的蟻群算法

蟻群算法是一種模擬大自然螞蟻群體覓食行為的模擬優化算法.通過螞蟻間信息素交互的正反饋機制，蟻群算法往往能較快地收斂于最優解；但也是由于這種正反饋作用力，算法往往容易陷入局部最優解，無法每次都能快速地收斂于全局最優解[10].因此本文在蟻群系統的基礎上引入了局部搜索等策略，通過對蟻群算法每代最優解進行局部搜索指導，提高了算法的全局搜索能力與收斂速度，進而能夠避免算法早熟、停滯.

3.1 改進的蟻群算法

1)路徑構造過程

本文采用的路徑構造方式與傳統的VRP問題路徑構造方式有所不同.通常的構造方式，每只螞蟻產生的子回路僅是一個可行解的一部分，獲得一個完整的可行解需要各螞蟻產生的子回路組合來生成一些可行解，當然也可能沒有可行解；這種路徑構造方式生成的可行解往往需要通過對大量的子回路組合產生，在一定程度上影響了算法的效率，也無法很好地保證每次迭代可以出現較好的可行解[11].

而本文改進的路徑構造方式為一只螞蟻即可產生一個可行解，結合多種策略可以保證獲得較優的解.每只螞蟻通過并行的方式隨機從各客戶結點出發，根據狀態轉移規則和確定性與隨機性選擇相結合的選擇策略來指導螞蟻選擇下一個需要配送的客戶，并實時更新自身的禁忌表用來指導后續路徑構造過程[12,16].

(8)

(9)

其中：τij為信息素濃度；ηij=demandj/dij為啟發因子，demandj為客戶j的貨物需求量，dij為客戶i,j之間成本；widthj為客戶j的時間窗寬度，時間窗越緊，優先配送級別相對較高；waitj為車輛在配送客戶j時需要等待的時間，當車輛早于客戶j時間窗到達，就需要等待，等待時間越長會影響配送效率、增加配送成本.當車輛在客戶j時間窗內到達，在j的等待時間waitj=0，在算法中取一個極小值；savej為從客戶i配送到客戶j比從客戶i回到配送中心，再從配送中心出發到客戶j的節約量；allowedk為未配送的客戶集合；α,β,γ,θ,ω分別為各影響因素的權重因子；r為[0,1]之間的隨機數；r0為[0,1]之間的常數，用來控制轉移規則.當r>r0時，算法依概率選擇下一個配送的客戶點，當r≤r0時，算法根據輪盤賭策略偽隨機選擇客戶點.

2)信息素更新規則

當所有螞蟻構造完成一次可行解時，算法進行全局信息素更新，根據精英螞蟻策略[13]更新全局信息素，對于精英螞蟻額外進行一次信息素累加，這種策略體現了算法的正反饋特性，但經過幾代計算后易導致某個較好解路徑上的信息素濃度過高，從而陷入局部最優.因此算法引入最大最小信息素策略(MMACA)，把信息素濃度限制在[τmin(t),τmax(t)]區間[13]內，并根據每代產生的最優路徑來動態更新最大最小信息素，使算法具有較好的自適應性.信息素更新規則[14,17]如下：

τij(t+n)=(1-ρ)*τij(t)+Δτij

(10)

(11)

(12)

(13)

采用全局信息素更新策略來指導螞蟻的結點選擇過程，雖然考慮了信息素的反饋，但仍具有一定的延遲性，不能及時地引導蟻群尋找最優路徑.有不少學者結合構造性的貪婪算法來指導局部信息素更新，這樣往往能在算法早期獲得一個較優解，把該解作為模擬退火算法的初始解，進行全局優化搜索，往往可以獲得更優解.算法中結合實際問題利用提前可知的先驗知識來指導結點的選擇，譬如配送完客戶點i之后必須立馬配送客戶點j,這類先驗知識往往可以使算法有較好的運算效率.

3.2 算法描述

為了彌補蟻群算法容易進入局部優解的特點，在算法的不同階段采用不同的策略，從而擴大搜索空間，獲得全局最優解.

3.2.1 局部搜索策略

算法在螞蟻構造路徑的過程中以及迭代出全局較好路徑時對解進行局部搜索，從而有概率通過差解或較優解產生全局最優解.算法中充分利用了1-Relocate、2-Relocate、2-opt、2-opt*、Exchange以及Exchange*局部搜索算子對可行解的子回路以及子回路之間進行路徑改進優化，分別如圖1-圖6所示.

1)1-Relocate算子路徑改進

算法對同一子路徑內的兩客戶結點進行1-Relocate算子改造，將前一客戶結點插入到后一客戶結點之后，若改造后的解符合約束條件，且成本比改造前的子路徑低則保留改造結果，反之則不保留.

圖1 子回路內頂點重定向

2)2-Relocate算子路徑改進

圖2 子回路間點頂點重定向

算法對不同子路徑間的兩客戶結點進行2-Relocate算子改造，將前一客戶結點插入到后一客戶結點之后，若改造后的解符合約束條件，且成本比改造前的子路徑低則保留改造結果，反之則不保留.

3)2-opt算子路徑改進

算法對同一子路徑的兩客戶結點之間的所有結點進行2-opt算子改造，將這些客戶結點反向插入原先的隊列，若改造后的子回路符合約束條件，且成本比改造前的子路徑低則保留改造結果，反之則不保留.

圖3 子回路內2-opt

4)2-opt*算子路徑改進

算法對不同子路徑間的兩客戶結點之間的所有結點進行2-opt*算子改造，將前一客戶結點插入到后一客戶結點之后，若改造后的每個子回路都符合約束條件，且總成本比改造前的子路徑低則保留改造結果，反之則不保留.

圖4 子回路間2-opt*

5)Exchange算子路徑改進

算法對同一子路徑內的兩客戶結點進行Exchange算子改造，將兩結點互換位置，若改造后的子回路符合約束條件，并且成本比改造前的子路徑低則保留改造結果，反之則不保留.

圖5 子回路內交換

6)Exchange*算子路徑改進

算法對不同子路徑間的兩客戶結點進行Exchange*算子改造，將兩結點互換位置，若改造后的都符合約束條件，且總成本比改造前低則保留改造結果，反之則不保留.

圖6 子回路間交換

3.2.2 動態更新信息素揮發以及轉移規則參數策略

當算法的當前代最優解和前代最優解連續n代的差值小于信息素揮發率ρ更新的臨界閾值RHO，則說明算法可能陷入了局部最優.將信息素揮發率ρ逐代增加，直至出現新的全局最優解；若經過2n代計算仍然沒有搜索出新的最優解，將信息素揮發率ρ逐代減小，加速算法收斂，最終輸出全局最優解.

在算法早期，設置較大的轉移規則參數r0，進行確定性搜索，使算法加速收斂到較優解；在算法中期，設置較小的r0，進行探索性搜索，擴大搜索空間，擺脫算法容易陷入局部優解的缺點；在算法后期，設置較大的r0，加快收斂速度，在局部空間搜索最優解，提高算法運算效率.即(NCmax為算法最大迭代次數)：

(14)

3.2.3 算法步驟

算法步驟及流程圖如圖7所示：

1)參數初始化：最大迭代次數NCmax、信息素初始濃度τij、最大最小信息素系數C、螞蟻數K、車輛最大載貨量Qk、狀態轉移概率中的權重因子α,β,γ,θ,ω、信息素揮發率ρ、蟻周系統參數O以及客戶點數據等參數.

2)初始化蟻群，令各螞蟻隨機從各客戶結點出發.

3)子回路構造：根據狀態轉移規則和確定性與隨機性選擇相結合的選擇策略公式(8),公式(9)選擇下一節點，通過時間窗和載貨量約束來逐步增加禁忌表中的客戶點.

4)若禁忌表未滿，則跳轉回步驟(3).

5)若禁忌表已滿，得到可行解.對可行解進行局部搜索策略優化解，根據公式(10)，公式(11)，公式(12)更新揮發后的信息素和螞蟻分泌的信息素增量.

6)若產生更優解，保存當前最優解，根據公式(13)動態更新信息素最大最小值.

7)完成一次迭代后根據精英螞蟻策略(11)對全局信息素更新，對全局信息素進行最大最小信息素策略修正，并根據信息素揮發策略動態更新ρ.

8)NC=NC+1，根據轉移規則參數策略動態更新r0，若NC

4 實驗結果與分析

實驗數據集選取Solomon標準測試數據集[15]，客戶點規模為100.算法使用java語言來實現，實驗環境為:Intel(R)Core(TM)i7-6700HQ CPU@2.60 GHz with 8GB RAM,Window10,算法代碼運行平臺使用IntelliJ IDEA 2017.本文對算法的參數進行大量組合測試用來選擇較合理的參數組合，最終選?。害?β,γ,θ,ω,ρ的值為(3.0，4.0，1.0，3.0，2.0，0.8)；NCmax設為50代，信息素揮發率ρ為0.8，蟻周系統常系數O為500.0，信息素初始濃度τij為1.0，MMAS系數C為200.0；1-Relocate、2-opt以及Exchange算子一次迭代的優化次數為5次，2-Relocate、2-opt*以及Exchange*算子一次迭代的優化次數為3次.表1是算法程序對部分測試數據集C101、C105、C106、C107、C108(最優解全為828.937)均運行30次的實驗結果，其中求出最好解的概率SR，求出最優解時的平均迭代次數BI，平均計算時間T.

圖7 算法流程圖

為驗證引入的策略在迭代過程中對算法探索全局最優解的優化改進，本文列出了算法對C108數據集測試30次產生的平均每代最優解圖，如圖8所示.

由表1可知，在較短的最大迭代數限制下，基本的蟻群算法基本無法得到全局最優解，而本文改進的蟻群算法幾乎都在50代之內收斂到了最優解，并且在運算效率上優于基本蟻群算法，而從圖8中分析得出，算法在迭代過程中多次陷入局部最優解，但本文引入的策略可以有效地增強算法全局搜索能力，使算法擺脫局部最優，最終收斂到全局最優.

表1 在50代之內算法數據集測試表

Table 1 Algorithm data set test within 50 generations

求解算法基本蟻群算法SR/%BIT/s本算法SR/%BIT/sC10110.0322100.011C1050.0--100.022C1060.0--100.011C1070.0--100.0135C1080.0--96.67258

圖8 測試C108數據集30次每代最優解平均值趨勢圖

5 案例應用

基于上述算法，針對浙江省杭州市實際路網數據，利用ArcGIS平臺開發了物流配送管理系統，實現運輸任務、運輸規劃等功能.系統以該地區地理信息數據為基礎，通過對數據進行轉彎要素、道路等級以及方向要素、網絡連通性[6,16]、屬性賦值等手段來構建實際路網模型，并通過Dijkstra算法[10,17]得到配送中心和各商場之間的最短距離和最短時間，從而獲取最短距離和最短時間的OD成本矩陣；本文以圖9為例說明，針對某物流公司日常需要將貨物從配送中心運送到25家商場的實際VRPTW問題，圖中配送中心和所有商場分布用數字1～25表示，配送中心和商場的貨物需求量、時間窗口以及卸貨所需時間等信息如表2所示；配送中心和所有商場之間的最短時間OD成本部分數據如表3所示.算法的主要目標是為物流公司生成一組貨車車隊，車隊中的每輛卡車分配一組所要服務的商場，并確定送貨的順序，從而將總配送成本控制在最低.

圖9 商場及配送中心分布圖

表2 配送中心和25個客戶點信息

Table 2 Distribution center and 25 customer information

0～12節點0123456789101112需求量/磅0170615331580128913021775101417611815170910451414開始時間9:0014:5414:209:2513:429:0613:0110:0610:3912:2711:1811:5413:13結束時間17:0015:1514:389:5714:049:2613:3310:2711:0612:5511:3912:1613:40卸貨時間/分010813101213810121081213～25節點13141516171819202122232425需求量/磅1863179113731962187210561950136415251767105315931469開始時間9:1212:4011:2912:059:3810:1010:489:0414:5514:1513:449:2510:06結束時間9:3613:0111:4712:259:5710:3911:149:2815:1514:4314:029:5610:27卸貨時間/分10118108121310101210128

篇幅有限，表3只給出了其中15個商場與配送中心之間的OD成本矩陣，從上述數據中可以發現實際路徑問題中客戶點i配送到客戶點j的成本與客戶點j配送到客戶點i是有差別的，這比常規VRP問題中僅僅靠計算各客戶點坐標之間的歐式距離作為成本更符合實際情況.

1)無時間窗約束車輛配送問題應用

本案例應用中25家商場散落在城市的四周，貨車必須經過復雜的城市路網才能配送下個商場，使用的貨車的最大裝載量為15000磅；貨車司機的費用為每小時75元，貨車的燃料消耗、日常維護等費用為每千米6元；由于長期駕駛會導致疲勞駕駛，公司規定一次配送司機駕駛時間不能超過7小時(不包含等待服務時間)；算法對于沒有時間窗同時符合上述要求的最優配送方案如圖10所示.此方案配送一次公司的費用成本約為1866.9元，其中第一輛貨車配送路線“1”為：0-21-20-24-25-23-10-22-9-0，貨車裝載量為12295磅，司機花費約6.77小時完成此次配送；其中第二輛貨車配送路線“2”為：0-19-18-17-8-1-2-3-15-0，貨車裝載量為12831磅，司機花費約6.47小時完成此次配送；其中第三輛貨車配送路線“3”為：0-16-13-4-7-6-11-12-5-14-0，貨車裝載量為13455磅，司機花費約6.15小時完成此次配送.

表3 配送中心和15個客戶點之間的最短時間OD成本矩陣(分鐘)

Table 3 Minimum time OD cost matrix between distribution center and 15 customer(min)

00.0012.5912.278.3011.8110.5217.3213.7217.3716.0420.7216.2710.708.887.674.75112.660.004.364.596.219.8414.549.7516.7426.1130.7816.9511.329.3811.928.44212.434.370.004.582.486.1211.837.7617.0825.1129.7913.237.596.208.748.4338.474.594.570.004.748.2514.1010.0214.0221.9226.5915.499.856.378.134.26411.916.202.484.720.003.869.695.6117.2324.5729.2411.085.453.726.268.58510.199.926.208.013.950.009.786.1820.9421.8526.5310.733.123.383.538.92617.3814.8411.9614.209.799.780.006.8326.7129.0433.727.658.7712.0310.8316.21713.599.757.8110.055.645.996.570.0022.5625.2529.927.914.978.247.0312.42817.5816.3516.6313.6016.8020.4426.1522.070.0031.7336.4127.5521.9119.0019.8514.66916.4225.8324.9821.6424.5222.3929.1925.5932.910.0015.5728.1422.5721.5519.5418.721020.1329.5328.6925.3428.2326.1032.8929.3036.6214.740.0031.8526.2725.2623.2422.431116.3116.6912.9715.2110.8010.577.697.9227.7127.9632.630.009.1812.8211.6115.341210.6611.337.619.855.443.448.805.1122.3522.3227.009.300.004.963.308.79138.929.396.186.393.703.7211.537.9419.3921.5726.2512.494.700.002.635.97147.6011.928.728.066.233.8710.777.1720.2519.5524.2311.733.302.630.005.85155.038.348.364.068.539.1216.0212.4315.1218.6723.3415.888.725.915.800.000123456789101112131415

圖10 無時間窗配送方案

2)帶時間窗約束車輛配送問題應用

然而實際VRP問題一般都帶有時間窗約束，在算法中加入表2的各商場的時間窗約束后求出的最優配送方案如圖11所示.此方案配送一次公司的費用成本約為2106.1元，其中第一輛貨車配送路線“1”為：0-20-24-25-10-9-23-22-21-0，貨車裝載量為12295磅，司機花費約6.55小時完成此次配送，由于提前到達商場而等待商場開始服務的等待時間約為1.38小時；第二輛貨車配送路線“2”為：0-13-3-8-15-16-14-12-0，貨車裝載量為11744磅，司機花費約4.87小時完成此次配送，由于提前到達商場而等待商場開始服務的等待時間約為0.45小時；第三輛貨車配送路線“3”為：0-5-7-11-6-4-2-1-0，貨車裝載量為9664磅，司機花費約6.53小時完成此次配送，由于提前到達商場而等待商場開始服務的等待時間約為2.13小時；第四輛貨車配送路線“4”為：0-17-18-19-0，貨車裝載量為4878磅，司機花費約2.41小時完成此次配送，由于提前到達商場而等待商場開始服務的等待時間約為0.6小時.

圖11 帶時間窗配送方案

從上述兩種配送方案中進行分析，車輛總數從3輛車變成了4輛，且原先較早配送的節點可能由于時間窗約束變成較遲配送的節點，譬如0號配送中心到21號商場的時間比0號配送中心到20號商場要短，但由于21號商場要求貨物配送服務的時間窗為[14:55,15:15],20號商場的時間窗為[9:04,9:28]，所以導致20號商場優于21號商場先進行配送服務，同時由于0號配送中心的統一發車時間為上午9點，那么20號商場的貨物配送服務是非常緊急的，因此其中一輛貨車優先去20號商場進行配送服務；而車輛從3輛增加到4輛的主要原因是由于部分商場的時間窗比較相近，一輛車無法在時間窗約束下滿足這些商場的需求，因此必須派出不同的車輛分別進行配送，譬如17號商場的要求服務時間和3號商場是十分相近的，但由于第二輛貨車在選擇對3號商場進行配送任務后是無法趕到17號商場進行令商場滿意的配送服務，因此物流公司需要增派一輛貨車對這些時間窗與其他車輛配送的商場節點相近的商場進行令客戶滿意的配送服務.

6 結 論

本文對帶時間窗的車輛路徑問題進行研究，在傳統數學模型的基礎上設計了一種基于蟻群系統和局部增強搜索策略的蟻群算法，針對蟻群算法搜索空間小、容易陷入局部最優的特點，加入了多種局部搜索算子來改進算法全局探索的能力，同時引入了動態更新信息素揮發以及轉移規則參數策略，來使算法在運行的不同階段動態進行自適應參數選擇，進而通過與標準測試數據集比對表明算法在較短時間內得出滿意解，最后將算法應用到實際案例中，驗證了算法在解決具有較大規模的實際車輛路徑問題的有效性.