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

陶 莎，朱建波，時茜茜

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

0 引言

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

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

1 問題

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

2 模型

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

3 進化算法

設計算法1求解上述非線性規劃模型。算法1是一種進化算法，在適應度計算和解碼兩步驟中分別對固定成本和可變成本進行優化。算法1采用最短路徑算法實現解碼，解碼過程詳見算法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)}，按染色體的客戶編號順序將客戶劃分成若干組，每組的客戶由一輛配送車負責配送，要求滿足每組顧客的總卸載量不能超過所選類型車的容量以及每組客戶中每個客戶被服務時間滿足客戶的時間窗要求這兩個條件。并且要求該染色體對應的解是滿足以上兩個條件的所有方案中總可變成本最小的方案。可變成本直接采用總運輸距離衡量。

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

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

圖G(Ch)上的最短路徑是對客戶序列的最優劃分，將其定義為染色體對應的解。為便于理解下面舉一個具體的解碼例子。假設有六個客戶和兩種車型，設染色體編碼序列為Ch={g(1),g(2),g(3),…,g(n)}={2，1，6，5，4，3}圖1a。圖1b是相關的已知數據，弧(i，j)上的數字是距離Di，j，節點邊的數字分別表示節點i的需求量（卸載量）ULi、服務時間Si和時間窗[Li，Ui]。按照上述的過程構建對應的無環有向圖G(Ch)如圖1c。例如弧(g(1)，g(3))=(2，6)表示依次訪問節點 (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)可表示某一車輛的可行路徑。弧對應的權重即是280+30+120=430。對于有向圖G(Ch)每一條車庫節點0到染色體的最后一個節點g(n)=3的路徑都是滿足n個客戶需求車輛配置和路徑選擇的可行方案，其中的最短路徑確保得到成本最低的方案，同時也是該染色體對應的解，如圖1d所示。因此可以看出用這種方法進行染色體解碼，解碼后對應解的信息包括使用的車類型、數量和路徑（訪問的節點和依次的順序）。

圖1 染色體解碼示例

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

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

算法2：染色體解碼算法

FSMVRPQD的優化目標是成本的最小化。采用目標值求倒數將目標函數轉化為適應度函數。采用進化代數作為終止規則。

4 算例仿真

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

表1 車輛及折扣信息

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

圖2 不同參數設定的實驗結果及運行時間統計

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

表2 最終配送方案

圖3 優化結果和進化代數關系圖

5 總結

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

[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].計算機集成制造系統,2007,13(10).

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

[9]汪勇,丁凡,吳志華.協同進化遺傳算法求解帶時間窗的車輛路徑問題[J].統計與決策,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).