多車場多車型車輛路徑問題的優化研究

朱晨晨

【摘 要】針對多車場多車型車輛路徑問題，通過建立虛擬配送中心將多車場路徑優化問題轉化為單一車場路徑優化問題。文章建立了數學模型并利用遺傳算法求解模型，同時根據問題性質對遺傳算法的編碼和解碼方式進行改進。基于企業實例的實證研究表明：文章提出的模型對求解多車場多車型車輛路徑問題具有一定的優勢，能夠為企業實際的物流運輸調度提供決策支持。

【關鍵詞】多車場;多車型;遺傳算法

自1959年車輛路徑問題（Vehicle Routing Problem，VRP）被Dantzig和Ramser[1]在文獻中首次提出以來，越來越多的研究投入該領域[2]。隨著現代物流運輸的發展，車輛路徑問題及其變體的研究越來越深入，它描述的是在一個連通網絡中擁有配送中心和客戶兩類節點，車輛需要從配送中心出發，在滿足客戶需求和實現優化目標的前提下，按照一定的行車路線將貨物交付到客戶手中。

貨物從制造工廠或者配送中心通過運輸網絡流向消費者的這一過程中，運輸路線是否合理對成本、效率至關重要。經典VRP的諸多變體包括具有硬、軟和模糊的服務時間窗口、客戶同時具有取貨和交付需求等。多車場多車型車輛路徑問題是在經典VRP的基礎上添加了“多車場”和“多車型”兩類約束，更加符合現實的物流配送情況，同時使得NP-hard的問題求解難度進一步加大。

1 文獻綜述

多車場多車型車輛路徑問題（Multi-Depot Vehicle Ro-uting Problem with a Heterous Fleet，MDHFVRP），是VRP問題的變體之一。由于VRP為NP-hard難題，多車場和多車型的出現又提升了問題的求解難度。多數學者采用啟發式算法求解MDHFVRP。例如，Cassidy等人[3]在1972年提出了求解MDHFVRP的迭代算法，他們的研究基于學校送餐的實際案例，該案例擁有600所學校、300個配送中心和100輛異質車隊，該算法通過對隨機的初始解不斷迭代從而改進解的質量，從而實現減少車輛運輸時間以盡快配送的優化目標;Wren等人[4]同樣提出了迭代算法求解MDHFVRP，初始解依據節約里程法生成，在他們的方案中，算法會根據客戶的優先級來滿足客戶需求;Saihi等人[5]在1997年引入多級啟發式方法，在第一階段利用邊界客戶建立初步可行解，第二階段利用局部搜索策略對初始可行解進行改進，該方法被證明在擁有360個客戶的大規模問題中具有較好的應用性能;A Willian Ho等人[6]通過兩階段方法求解，算法的第一階段考慮隨機生成的初始解，第二階段通過最近鄰啟發式算法和節約里程法找到初始種群，在不同實例上的計算表明了該算法具有良好性能。

針對大規模的MDHFVRP，多數研究采取先聚類再優化的求解思路，此種方法可以縮小問題規模和降低求解難度。例如，Thangiah等人[7]利用遺傳算法進行客戶分群，將問題轉變為旅行商問題，然后通過插入啟發式算法求解旅行商問題;Luo.J等人[8]則改進了蛙跳算法，對客戶聚類后再進行優化，然后對總體進行調整以生成新的聚類，直到滿足設定的收斂標準為止，該方法被證明可以用來求解大規模的多車場車輛路徑問題。

大量文獻表明，國內外學者對于車輛路徑問題及其變體的研究已經較為深入。但多車場多車型車輛路徑問題因涉及的變量和約束條件較多，使得NP-hard難題更加復雜。對于大規模多車場多車型車輛路徑問題，將其拆分成倉庫優化和路徑優化兩步雖然可以降低求解難度，但是容易導致局部優化。因此，需要針對MDHFVRP進行全局優化，生成整個運輸網絡的優化解。

2 多車場多車型路徑優化問題和數學模型

2.1 問題描述

文章的研究對象可以被描述為多個配送中心擁有多個車型，每種類型的車數量有限，需要對各個需求點提供配送服務，要求通過合理調度車輛，實現總配送成本最少。文章通過建立一個虛擬的配送中心，設定各車場到虛擬配送中心的成本和距離均為0。車輛由虛擬車場出發，經過任一配送中心，服務完客戶后再依次回到原配送中心、虛擬車場。

通過設置虛擬配送中心，多車場車輛調度問題可以轉變成單車場車輛調度問題，從而降低了問題的求解難度，可從全局進行優化，避免陷入局部最優情況。

針對多車型，有學者在分析影響多車型車輛運輸成本的因素后，得出車輛滿載時運輸成本最低[9]，葛顯龍等人[10]的研究中也根據最大車載率原則選擇車型。綜合學者們的研究，文章采取“最大滿載率”原則，即對于一段路徑來說，優先選擇對應該路徑上滿足所有客戶總需求的滿載率最大的可用車型。

2.2 數學模型

考慮不同車型的使用費用差異巨大，對運輸總成本的影響程度也不同，因此文章的目標函數選取為車輛運輸的固定成本和可變成本之和。

3 遺傳算法求解設置

3.1 遺傳算法的求解步驟

（1）染色體編碼：1到n的n個自然數的隨機排列表示客戶，基因的數值表示該客戶，該基因在染色體中的位置代表該客戶被服務的順序。采取（n+1）到（n+m）的m個整數表示m個車場。0代表虛擬配送中心。

（2）初始種群：初始種群采用隨機的方式生成，隨機產生1到n的全排列構成染色體Sk，G=（S1，S2，…，Sk）表示初始種群。

（3）適應度函數：適應度函數取目標函數的倒數。

（4）選擇：計算種群中每個個體的適應度，采用輪盤賭方式選擇個體。

（5）交叉：設定交叉概率Pc，從上一代種群中隨機選擇兩個個體作為父代，并產生0～1的一個隨機數，若隨機數小于Pc，則對兩個父代進行交叉操作，否則不交叉。

（6）變異：設定變異概率Pm。產生0～1的一個隨機數，若該隨機數小于Pm，則執行變異操作，否則不變異。

3.2 遺傳算法的改進

（1）編碼方式的改進。傳統的一條染色體表示一個個體的方式雖然比較直觀簡潔，但是當問題涉及變量較多時，會造成染色體數目過多，在執行交叉、變異等遺傳操作時效率低下，占用大量計算空間，甚至會形成不可行解，大大降低了算法的運算效率[11]。文章采用一條染色體表示多個個體的“復合染色體編碼”，此種設置可以減少染色體數量，提高算法的執行速度和計算精度。

（2）解碼方式的改進。文章通過建立“染色體信息矩陣”實現對解的快速解碼，該矩陣包含每條染色體中個體的分割點、該個體對應的子路徑滿載率、服務車場編號、匹配車型等。

例如，在一個多車場多車型車輛路徑問題中，2個車場共擁有2種車型，并有6個客戶需求點，則用1～6的自然數表示6個客戶，7和8分別表示2個車場，1 000和1 500分別為兩種車型的額定裝載量。假定某條染色體的客服排列順序為123456，則對應某個可行解的相關信息會存儲在“染色體信息矩陣”中，矩陣的前三行分別表示分割點、服務車場、匹配車型：? 3? ?6 7? ?81 000 1 500矩陣表達的意義為7號車場為1、2、3號客戶提供服務，并由額定裝載量為1 000的車型進行運輸，8號車場為4、5、6號客戶提供服務，并由額定裝載量為1 500的車型進行運輸。解碼后的兩條路徑分別可以表示成0-7-1-2-3-7-0和0-8-4-5-6-8-0，0為虛擬配送中心。

4 算例分析

H公司位于k市，面向全國客戶銷售貨物A，H公司在k市擁有5個倉庫，用于承接客戶的訂單并組織車輛進行配送。目前的物流配送中存在的問題如下。①車輛滿載率低：H公司在進行車輛調配時缺少明確的選擇原則，存在較大車型承載較少訂單量的情況，導致車輛滿載率低。②運輸距離長：H公司的發貨計劃在滿足車輛裝載量限制的情況下存在相近到貨點的訂單被不同批次的車輛運輸，增加了總運輸距離。

基于以上兩個問題，H公司現有的配送計劃導致了較高的運輸總成本。因此，文章的優化思路為在盡量提高車輛滿載率的情況下，實現總運輸成本的最小化。

本文選擇一天的訂單數據進行仿真試算，該天沒有突發訂單，客戶的地理位置分布均勻，所以試算結果可以較好地表現模型的性能。在仿真試算前，需對初始數據進行處理，使數據更適用于模型。H公司共有7個配送中心，考慮到地理位置的遠近，以及庫存數量較少的配送中心需要從其他配送中心調貨，因此實際上可視為5個配送中心。模型中需要的數據包括各節點的地理位置、運輸車輛的額定裝載量及各客戶的需求量等。考慮到初始數據中各節點是以實際的地理單位表示，文章利用百度地圖將各節點的地理位置表示為經緯度，并利用經緯度距離公式表示兩節點的距離;初始數據中客戶的需求量通過貨物A的件數表示，文章根據貨物A的重量和體積，將各車型的額定裝載量換算成額定裝載件數，并取歷史訂單中利用率最高的5種車型作為文章的可用車型。

因此，算例信息可描述如下：5個配送中心，擁有數量有限的5種車型，額定裝載量分別為2 000、1 750、1 250、1 000、800件，對應的車輛可變成本即每公里運輸成本分別為0.1、0.15、0.2、0.25、0.3元，固定成本分別為100、150、200、250、300元。車輛該天共有192個需求點，存在到貨地點相同的不同訂單。

在經過多次試算后，文章設置遺傳算法的參數如下：種群規模n=60，迭代次數C=200，交叉概率pc=0.8，變異概率pm=0.05。算法通過在Win10系統的計算機上運行Matlab 2018進行，對算例數據運行5次，結果見表1。

取5次運算中的最低成本，為77 085元，共調用103輛車，車隊總運力為139 250件，運力利用率為94.51%。對應的優化運輸路線圖如圖1所示。

現有方案共調用共調用119輛車合計運力為175 650件，實際利用運力為131 605件，利用率74.92%;總路程為274 934 km，總運輸成本為86 405元（見表2）。

通過將現有運輸方案和優化運輸方案進行對比，文章主要實現的優化點有4個：①總運輸成本：現有運輸方案的總成本為86 594元，優化后為77 085元（見表3），降低了10.15%。現有的運輸方案中雖調用了大量的車輛，但是車輛利用率不高，每輛車調用一次就會產生一個固定成本下，使得總運輸成本上升。②滿載率：優化方案中車輛的滿載率作為多車型選擇的優先原則大大提高了優化后車輛的滿載率，減少了車輛空載率過高的現象。③總運輸距離：現有運輸方案的總運輸距離為274 934 km，優化后的總運輸距離為273 915 km。現有運輸方案中，少量多批次的原則造成大量車輛的迂回運輸，經優化后，車輛滿載率的提高使得在滿足額定裝載量限制的條件下，一條路徑可以有更多的客戶被服務，從而減少了車輛的迂回運輸，減少總運輸距離。總距離的減少程度不顯著的主要原因在于本文的優化目標是總運輸成本最少，除了運輸距離外，車輛的固定成本是影響調度方案的重要因素。④調用車輛數：現有運輸方案總共調用了119輛，優化后的運輸方案共調用了103輛，降低了13.4%。

5 結論與展望

針對多車場多車型車輛路徑問題，本文建立數學模型、并設計遺傳算法進行求解，并對企業實際的物流運輸問題，實證研究，算例結果表明文章建立的數學模型和遺傳算法可以得到比現有運輸方案更優的解，能夠為企業節省一定的運輸成本，產生更多的經濟效益。

但現實的物流配送中，時間窗約束是較為關鍵的問題，車輛能夠在硬、軟時間窗條件下完成配送對于客戶滿意度、企業信譽等具有重要影響力，因此在現有問題上加上時間窗因素，將是下一步的研究方向。

參 考 文 獻

[1]Dantzig G B，Ramser J H.The Truck Dispatching Problem[J].Management Science，1959，6（1）：80-91.

[2]何彥東.網購物流終端配送問題研究[D].重慶：重慶大學，2018.

[3]Bettinelli A，Ceselli A，Righini G.A branch-and-

cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows[J].Transportation Research Part C Emerging Technologies，2011，19（5）：723-740.

[4]Wren A，Holliday A.Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points[J].Journal of the Operational Research Society，1972，23（3）：333-344.

[5]Salhi S，Sari M.A multi-level composite heuristic for the multi-depot vehicle fleet mix problem[J].European Journal of Operational Research，1997，103（1）：95-112.

[6]A W H ，B G T S H，B P J ，et al.A hybrid genetic algorithm for the multi-depot vehicle routing problem[J].Engineering Applications of Artificial In-telligence，2008，21（4）：548-557.

[7]Thangiah S R，Salhi S.Genetic clustering：An ada-ptive heuristic for the multidepot vehicle routing problem[J].Applied Artificial Intelligence，2001，15（4）：361-383.

[8]Luo J，Chen M R.Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW[J].Computers & Industrial Engineering，2014，72：84-97.

[9]Moshe，Dror，Michael，et al.Inventory/routing： Reduction from an annual to a short-period problem[J].Naval Research Logistics，1987，34（6）：891-905.

[10]葛顯龍，王旭，鄧蕾. 基于聯合配送的開放式動態車輛路徑問題及算法研究[J]. 管理工程學報，2013，27（3）：60-68.

[11]陳呈頻，韓勝軍，魯建廈，等.多車場與多車型車輛路徑問題的多染色體遺傳算法[J].中國機械工程，2018，29（2）：218-223.