朱晨晨

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

【關(guān)鍵詞】多車場;多車型;遺傳算法

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

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

1 文獻(xiàn)綜述

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

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

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

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

2.1 問題描述

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

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

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

2.2 數(shù)學(xué)模型

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

3 遺傳算法求解設(shè)置

3.1 遺傳算法的求解步驟

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

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

（3）適應(yīng)度函數(shù)：適應(yīng)度函數(shù)取目標(biāo)函數(shù)的倒數(shù)。

（4）選擇：計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度，采用輪盤賭方式選擇個(gè)體。

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

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

3.2 遺傳算法的改進(jìn)

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

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

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

4 算例分析

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

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

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

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

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

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

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

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

5 結(jié)論與展望

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

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

參 考 文 獻(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].重慶：重慶大學(xué)，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]葛顯龍，王旭，鄧?yán)? 基于聯(lián)合配送的開放式動(dòng)態(tài)車輛路徑問題及算法研究[J]. 管理工程學(xué)報(bào)，2013，27（3）：60-68.

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