陶 莎，朱建波，時(shí)茜茜

（南京大學(xué) 工程管理學(xué)院，南京210039）

0 引言

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

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

1 問(wèn)題

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

2 模型

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

3 進(jìn)化算法

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

算法1：FSMVRPQD的進(jìn)化算法

采用客戶序列編碼，即對(duì)客戶集合{1，…，n}，染色體Ch={g(1)，g(2)，g(3)，…，g(n)} 中 n 個(gè)基因?qū)?yīng)客戶編號(hào)的一個(gè)排序。在對(duì)一個(gè)染色體進(jìn)行解碼時(shí)需要確定線路及其對(duì)客戶的訪問(wèn)順序，以及該線路對(duì)應(yīng)的車輛。Liu等(2009)針對(duì)運(yùn)送多種物品提出一個(gè)最短路解碼方法。在該文方法的基礎(chǔ)上，加入車輛多類型和時(shí)間窗等條件設(shè)計(jì)基于最短路徑算法的解碼方法。對(duì)于染色體Ch={g(1)，g(2)，g(3)，…，g(n)}，按染色體的客戶編號(hào)順序?qū)⒖蛻魟澐殖扇舾山M，每組的客戶由一輛配送車負(fù)責(zé)配送，要求滿足每組顧客的總卸載量不能超過(guò)所選類型車的容量以及每組客戶中每個(gè)客戶被服務(wù)時(shí)間滿足客戶的時(shí)間窗要求這兩個(gè)條件。并且要求該染色體對(duì)應(yīng)的解是滿足以上兩個(gè)條件的所有方案中總可變成本最小的方案?？勺兂杀局苯硬捎每傔\(yùn)輸距離衡量。

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

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

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

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

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

圖1 染色體解碼示例

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

將上述內(nèi)容總結(jié)整理，給出解碼的算法2。

算法2：染色體解碼算法

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

4 算例仿真

在500×500空間范圍內(nèi)隨機(jī)生成100個(gè)需求點(diǎn)及其分布，設(shè)置1號(hào)點(diǎn)為車庫(kù)，并隨機(jī)生成各點(diǎn)的需求量（卸載量）和時(shí)間窗（時(shí)間上限、下限）。小、中、大三種車型的車速、容量、成本以及外包折扣信息如表1所示。

表1 車輛及折扣信息

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

圖2 不同參數(shù)設(shè)定的實(shí)驗(yàn)結(jié)果及運(yùn)行時(shí)間統(tǒng)計(jì)

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

表2 最終配送方案

圖3 優(yōu)化結(jié)果和進(jìn)化代數(shù)關(guān)系圖

5 總結(jié)

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

[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]姜昌華,戴樹貴,胡幼華.求解車輛路徑問(wèn)題的混合遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2007,13(10).

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

[9]汪勇,丁凡,吳志華.協(xié)同進(jìn)化遺傳算法求解帶時(shí)間窗的車輛路徑問(wèn)題[J].統(tǒng)計(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).