多車場多車型車輛路徑問題的優(yōu)化研究

朱晨晨

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

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

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

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

1 文獻綜述

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

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

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

2 多車場多車型路徑優(yōu)化問題和數(shù)學模型

2.1 問題描述

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

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

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

2.2 數(shù)學模型

考慮不同車型的使用費用差異巨大，對運輸總成本的影響程度也不同，因此文章的目標函數(shù)選取為車輛運輸?shù)墓潭ǔ杀竞涂勺兂杀局汀?/p>

3 遺傳算法求解設置

3.1 遺傳算法的求解步驟

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

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

（3）適應度函數(shù)：適應度函數(shù)取目標函數(shù)的倒數(shù)。

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

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

（6）變異：設定變異概率Pm。產(chǎn)生0～1的一個隨機數(shù)，若該隨機數(shù)小于Pm，則執(zhí)行變異操作，否則不變異。

3.2 遺傳算法的改進

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

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

例如，在一個多車場多車型車輛路徑問題中，2個車場共擁有2種車型，并有6個客戶需求點，則用1～6的自然數(shù)表示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公司在進行車輛調(diào)配時缺少明確的選擇原則，存在較大車型承載較少訂單量的情況，導致車輛滿載率低。②運輸距離長：H公司的發(fā)貨計劃在滿足車輛裝載量限制的情況下存在相近到貨點的訂單被不同批次的車輛運輸，增加了總運輸距離。

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

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

因此，算例信息可描述如下：5個配送中心，擁有數(shù)量有限的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個需求點，存在到貨地點相同的不同訂單。

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

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

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

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

5 結論與展望

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

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

參 考 文 獻

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

[2]何彥東.網(wǎng)購物流終端配送問題研究[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]葛顯龍，王旭，鄧蕾. 基于聯(lián)合配送的開放式動態(tài)車輛路徑問題及算法研究[J]. 管理工程學報，2013，27（3）：60-68.

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