帶有外包數(shù)量折扣的多車型車輛路徑問題探討

陶 莎，朱建波，時茜茜

（南京大學 工程管理學院，南京210039）

0 引言

在物流外包服務的背景下，本文研究帶有外包數(shù)量折扣的多車型路徑優(yōu)化問題。從車隊自身角度，合理的配送方案能降低物流成本，數(shù)量折扣策略能夠吸引客戶和獲得規(guī)模效益。隨著市場競爭日益激烈，站在客戶角度實現(xiàn)協(xié)同和雙贏是物流企業(yè)得以長遠發(fā)展的有效手段。車隊運作管理問題通常是車輛路線問題或其擴展。VRP是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當?shù)男熊嚶肪€，在一定的約束下滿足客戶需求，達到成本和時間的最小化等目標?；旌宪囕v路徑問題[1～3]是VRP的一個擴展問題，研究為配送車隊配置車輛的類型和每種類型車輛的數(shù)量以及安排各車輛的路徑，使車隊在成本最低的目標下完成配送任務。當車輛可變成本與車輛類型無關且每種類型車的可使用數(shù)無限大時，該問題被稱為多車型車輛路徑問題[4～10]。

在物流外包的背景下，本文研究具有以下新特征的FSMVRP問題，簡稱FSMVRPQD。一是，車輛容量和成本各不相同，外包車輛具有固定成本即外包成本；可變成本包括燃油、人力資源等成本，假定可變成本和行駛距離成正比。二是，考慮帶有數(shù)量折扣的多車型車輛路徑問題，并考慮時間窗、容量限制等約束。三是，根據(jù)時間窗和數(shù)量折扣的特點，本文在Liu（2009）提出的基于最短路解碼的混合遺傳算法基礎上，通過修改適應度函數(shù)并在解碼中加入時間窗條件設計求解算法。

1 問題

N={0，1，2…，n，n+1}是包含一個車庫和n個客戶的點集，其中0和虛擬節(jié)點n+1是車庫，其它為客戶節(jié)點，客戶i（i∈N{0 ，n+1}）需求量為ULi，服務時間和時間窗分為為Si和[Ui，Li]。任意兩節(jié)點i∈N到節(jié)點j∈N的運輸距離為Di，j。車隊可派出車輛的類型為TR={1，…，NT}，每類車的可用數(shù)量無限大，類型為k∈TR的車的容量（最大承載量）、平均車速和單位固定成本分別為MCk∈TR、Vk∈TR和RCk∈TR。為類型為k∈TR的車從節(jié)點i∈N到節(jié)點j∈TR的運輸時間。TC為單位距離運輸?shù)倪\輸費用。以完成n個任務的總成本f（可變成本vc與固定成本fc之和）最小化為目的，求解實際每類車的發(fā)車數(shù)量和每輛車的訪問路徑。類型為k∈TR的車輛的外包折扣θk與一次外包的車的數(shù)量有關，即θk(mk)?？偝杀景勺兂杀竞凸潭ǔ杀荆勺兂杀局苯佑蓤?zhí)行配送任務的物流外包企業(yè)承擔，而固定成本（外包成本）則表示客戶支付給物流企業(yè)的運輸成本。本文將物流企業(yè)和客戶的利益綜合考慮，這有利于供應鏈企業(yè)間的合作，達到雙贏。并且，可以考慮以下合理的現(xiàn)實條件：不同類型車輛的容量和固定成本不同，容量越大費用越大；每個客戶只允許一輛車負責配送，即客戶需求不能分割（split）；任一顧客的配送量都小于最大車型的容量；配送企業(yè)將配送任務外包給專門的配送公司，即通過外包租用所需配送能力滿足物流需求。平均單量車的外包成本采取外包數(shù)量越大折扣越低的定價策略。

2 模型

式（1）表示目標是總成本的最小化，總成本包括固定成本和可變成本；式（2）計算固定成本，RCk(mk)是外包平均單位時間外包類型為k的車的費用；式（3）計算可變成本；式（4）是速度、時間和距離之間的關系表達式；式（5）表示類型為k的車離開配送中心的次數(shù)，即使用量；式（6）表示類型為k的車返回配送中心的次數(shù)。顯然，車輛離開配送中心的次數(shù)等于車輛返回配送中心的次數(shù)，即所有派出車輛都要返回；式（7）和（8）對訪問順序進行約束；式（9）為基于訪問順序的卸載量約束；式（10）和（11）表示客戶點的進入次數(shù)和離開次數(shù)最多為1次，即顧客點只被服務1次；式（12）表示每個顧客點的車輛進入次數(shù)等于離開次數(shù)；式（13）是時間窗約束，表示每個客戶點被訪問的時間必須在時間窗內；式（14）是車容量約束；式（15）為各類型車外包優(yōu)惠折扣定義式，其中λ（0＜λ≤1）是折扣數(shù)，Ω為折扣限定的外包的車輛數(shù)量區(qū)間，式（15）表示外包車輛越多折扣越小，即單位車輛外包的固定成本越低。

3 進化算法

設計算法1求解上述非線性規(guī)劃模型。算法1是一種進化算法，在適應度計算和解碼兩步驟中分別對固定成本和可變成本進行優(yōu)化。算法1采用最短路徑算法實現(xiàn)解碼，解碼過程詳見算法2。

算法1：FSMVRPQD的進化算法

采用客戶序列編碼，即對客戶集合{1，…，n}，染色體Ch={g(1)，g(2)，g(3)，…，g(n)} 中 n 個基因對應客戶編號的一個排序。在對一個染色體進行解碼時需要確定線路及其對客戶的訪問順序，以及該線路對應的車輛。Liu等(2009)針對運送多種物品提出一個最短路解碼方法。在該文方法的基礎上，加入車輛多類型和時間窗等條件設計基于最短路徑算法的解碼方法。對于染色體Ch={g(1)，g(2)，g(3)，…，g(n)}，按染色體的客戶編號順序將客戶劃分成若干組，每組的客戶由一輛配送車負責配送，要求滿足每組顧客的總卸載量不能超過所選類型車的容量以及每組客戶中每個客戶被服務時間滿足客戶的時間窗要求這兩個條件。并且要求該染色體對應的解是滿足以上兩個條件的所有方案中總可變成本最小的方案。可變成本直接采用總運輸距離衡量。

首先，通過如下方式根據(jù)染色體構建一個無環(huán)有向圖G。設配送車類型的編號按車容量大小升序排列，即MCk＜MCk+1，k=1，…，NT-1。對于代表一個客戶序列的染色體Ch，G(Ch)是一個有向圖，其節(jié)點V(G)={g(i)|1≤i≤n}，其有向邊集合E(G)滿足當且僅當滿足式（16）和式（17）時，(i，j)∈E(G)。

即當配送車的容量約束和客戶點時間窗約束均被滿足時，令 (i，j)∈E(G)，k是車的類型。每條弧 (i，j)是一個可行的配送路線，表示車離開節(jié)點0（車庫）且依次連續(xù)訪問節(jié)點i+1，i+2，…，j。總卸貨量為為類型k的車到達m節(jié)點的時刻，計算如式（17）中表示。邊上權重wi，j表示為k類型車在從車庫出發(fā)依次訪問i+1，i+2，…，j后回到車庫的運輸代價。由于滿足上述兩個約束的車的類型可能不止一種，因此限定小型車優(yōu)先。這一限定的含義是，如果上述的配送任務可以由一個容量較小的車輛完成，則其它更大容量的車就無需考慮。假定容量越小的車的固定成本越低，車速越快。在可以滿足客戶需求的前提下也更能節(jié)約空間（若派更大容量的車完成任務則有更大的容量浪費）。顯然，優(yōu)先選擇成本小的車型。因此，弧上的權重通過式（18）計算，其中k=argmink{q|q∈TR，Eq.(16-17)} 。

圖G(Ch)上的最短路徑是對客戶序列的最優(yōu)劃分，將其定義為染色體對應的解。為便于理解下面舉一個具體的解碼例子。假設有六個客戶和兩種車型，設染色體編碼序列為Ch={g(1),g(2),g(3),…,g(n)}={2，1，6，5，4，3}圖1a。圖1b是相關的已知數(shù)據(jù)，弧(i，j)上的數(shù)字是距離Di，j，節(jié)點邊的數(shù)字分別表示節(jié)點i的需求量（卸載量）ULi、服務時間Si和時間窗[Li，Ui]。按照上述的過程構建對應的無環(huán)有向圖G(Ch)如圖1c。例如弧(g(1)，g(3))=(2，6)表示依次訪問節(jié)點 (0，g(2)，g(3)，0)=(0，1，6，0)的路徑，先后分別計算使用類型1和類型2的車是否滿足容量和時間窗的要求。計算可知類型1車不滿足容量要求。而對于類型2車有：

①UL1+UL6=320+300≤900，滿足容量約束；

因此，弧 (g(1)，g(3))=(2，6)∈G(Ch)可表示某一車輛的可行路徑?；臋嘀丶词?80+30+120=430。對于有向圖G(Ch)每一條車庫節(jié)點0到染色體的最后一個節(jié)點g(n)=3的路徑都是滿足n個客戶需求車輛配置和路徑選擇的可行方案，其中的最短路徑確保得到成本最低的方案，同時也是該染色體對應的解，如圖1d所示。因此可以看出用這種方法進行染色體解碼，解碼后對應解的信息包括使用的車類型、數(shù)量和路徑（訪問的節(jié)點和依次的順序）。

圖1 染色體解碼示例

編碼過程較為簡單，任意一個解將每輛車訪問的節(jié)點按順序串聯(lián)（去掉車庫0）即可編碼成為相應染色體。

將上述內容總結整理，給出解碼的算法2。

算法2：染色體解碼算法

FSMVRPQD的優(yōu)化目標是成本的最小化。采用目標值求倒數(shù)將目標函數(shù)轉化為適應度函數(shù)。采用進化代數(shù)作為終止規(guī)則。

4 算例仿真

在500×500空間范圍內隨機生成100個需求點及其分布，設置1號點為車庫，并隨機生成各點的需求量（卸載量）和時間窗（時間上限、下限）。小、中、大三種車型的車速、容量、成本以及外包折扣信息如表1所示。

表1 車輛及折扣信息

在CPU為英特爾酷睿i3-380M、內存為2GB、操作系統(tǒng)為Windows 7的計算機上運行C#實現(xiàn)的算法1和算法2求解上述算例。為了研究各參數(shù)對實驗結果以及運行時間的影響，設定不同的參數(shù)進行實驗，在每種參數(shù)設定下運行10次，圖3為實驗結果及運行時間統(tǒng)計的對比分析圖。圖2中的a1、b1、c1子圖分別是變異概率Pm、交叉概率Px和種群規(guī)模Ps設置不同值時的運行結果，三條折線分別是不同參數(shù)值下10次實驗結果的最大值、平均值和最小值；a2、b2、c2子圖分別是各參數(shù)設置下10次實驗的平均運行時間。從圖2可以看出，在其它參數(shù)值確定的前提下，最優(yōu)成本隨著Pm增大大體呈下降趨勢，在設定值為0.35時，10次實驗的最大、最小和平均值均最低；Px對本實驗的結果沒有明確的影響，隨著Ps的增大，成本也大體呈下降趨勢。此外，從a2和b2看出，曲線沒有明顯的趨勢和規(guī)律，并且最大與最小的實驗平均時間僅僅相差3秒和2.2秒，相對于總體平均運行時間88.22和88.34可以忽略，因此可以判斷Px和Pm對運行時間均沒有顯著影響。圖c3中直觀地可以看出折線類似于一條單調上升的直線，事實上數(shù)據(jù)表明隨著Ps以公差為10的等差數(shù)列遞增，平均運行時間也以約100s的差值遞增，可以推斷運行時間與Ps大小呈正比關系。

圖2 不同參數(shù)設定的實驗結果及運行時間統(tǒng)計

根據(jù)上面的分析，綜合考慮實驗結果和運行時間兩因素，設置各參數(shù)值為Ps=60、Px=0.7、Pm=0.35和Pg=10000，算法運行5次，平均運行時間為46分50秒，其中4次實驗經(jīng)過10000代進化均收斂于最優(yōu)成本780，圖3為4次最優(yōu)實驗的優(yōu)化結果和進化代數(shù)的關系圖?？梢钥闯觯趦?yōu)化過程的開始階段，曲線下降較快，隨著進化過程的進行，曲線變化趨于平緩，但隨著進化過程的進行，算法的收斂趨勢明顯。雖然4次實驗的最優(yōu)值相同，但配送方案并不相同。這是因為FSMVRPQD用外包成本衡量GA的適應度，而外包成本僅由外包車量的數(shù)量和種類決定，與車的配送路徑無關。針對這一特點，當多個方案的最優(yōu)值相同時，可以選擇可變成本最小的方案。因此，比較4次最優(yōu)實驗的總行駛距離，達到最優(yōu)解的代數(shù)4653的實驗結果方案的總行駛距離最小，達到24177，可以選為最終配送方案。最終配送方案見表2，得到車輛總數(shù)為14，總外包成本為780。

表2 最終配送方案

圖3 優(yōu)化結果和進化代數(shù)關系圖

5 總結

相對于典型多車型車輛路徑問題的研究成果，同時考慮時間窗約束和數(shù)量折扣，是一種降低外包成本、提高車隊利潤和降低空載率的策略。本文建立該問題的非線性規(guī)劃模型并設計基于最短路解碼的進化算法，在解碼過程和適應度計算過程中綜合考慮車隊和客戶的可變成本和固定成本，是對車隊和客戶兩方利益的整體考慮，不僅為車隊提供優(yōu)化的配送方案，而且降低了客戶的外包成本。通過引入局部搜索方法進一步提高算法性能，考慮車輛類型對運輸費用的影響、以及外包時間懲罰和折扣的影響是未來值得研究和探討的問題。

[1]Belfiore,Pchty.Yoshizaki,Scatter Search for A Real-Life Heterogeneous Fleet Vehicle Routing Problem With Time Windows and Split Deliveries in Brazil[J].European Journal of Operational Research,2009,199(3).

[2]Brand?o J.A Tabu Search Algorithm for The Heterogeneous Fixed Fleet Vehicle Routing Problem[J].Computers&Operations Research,2011,38(1).

[3]Choi E,Tchaikovsky.A Column Generation Approach to The Heterogeneous Fleet Vehicle Routing Problem[J].Computers&Operations Research,2007,34(7).

[4]Repoussis P P.Solving The Fleet Size and Mix Vehicle Routing Problem With Time Windows via Adaptive Memory Programming[J].Transportation Research Part C:Emerging Technologies,2010,18(5).

[5]Liu S Huang W,Ma H.An Effective Genetic Algorithm for The Fleet Size and Mix vehicle Routing Problems[J].Transportation Research Part E:Logistics and Transportation Review,2009,45(3).

[6]J Renaud,Boctor F F.A Sweep-Based Algorithm for The Fleet Size and Mix Vehicle Routing Problem[J].European Journal of Operational Research,2002,140(3).

[7]姜昌華,戴樹貴,胡幼華.求解車輛路徑問題的混合遺傳算法[J].計算機集成制造系統(tǒng),2007,13(10).

[8]沈玲.基于混合遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[J].物流工程與管理,2009,33(2).

[9]汪勇,丁凡,吳志華.協(xié)同進化遺傳算法求解帶時間窗的車輛路徑問題[J].統(tǒng)計與決策,2010,10(1).

[10]Xu M H,Liu,Y Q,Huang Q L,et al.An Improved Dijkstra's Shortest Path Algorithm for Sparse Network[J].Applied Mathematics and Computation,2007,185(1).