邊 展， 張 倩， 徐 奇， 靳志宏

(1.首都經(jīng)濟貿(mào)易大學 工商管理學院，北京 100070; 2.北京工商大學 商學院，北京 100048; 3.大連海事大學 交通運輸工程學院，遼寧 大連 116026)

0 引言

現(xiàn)今汽車貨運業(yè)采用多種運輸形態(tài)提供物流服務，其中一種為點對點運輸，即客戶提供物流信息要求貨運公司派車至指定點取貨再送至另一指定點卸貨，此類問題被稱作取送貨問題(Pickup and Delivery Problem，PDP)[1]。由于JIT概念的興起，每個客戶需求點均有時間窗限制，業(yè)者在消費意識高漲與競爭壓力的促使下，必須提供快速、穩(wěn)定、正確、準時的服務。因此進行具有時間窗限制的取送貨問題(Pickup and Delivery Problem with Time Windows，PDPTW)的研究愈加重要。

由于PDPTW屬于NP-hard問題[2]，運算時間會隨著問題規(guī)模擴大而呈指數(shù)性增長，因此目前國內外研究主要關注于運用各種啟發(fā)式算法對該問題進行求解。Li與Lim[3]提出了整合禁忌搜索與模擬退火啟發(fā)的智能算法，并求解問題規(guī)模為100個點的標準算例。Pankratz[4]開發(fā)了組群遺傳算法，通過運用特殊的編碼解碼技術，實現(xiàn)了基于車輛的遺傳編碼、交叉與變異方法。Bent與Van[5]提出了基于模擬退火算法與鄰域搜索技術的兩階段混合啟發(fā)式算法，分別對車輛數(shù)及路徑進行優(yōu)化。Ropke與Cordeau[6]將PDPTW子問題構建成為有約束的最短路問題，運用分支-價格法及有效不等式進行求解。Hosny與Mumford[7]對比了遺傳算法、模擬退火算法及爬山算法處理單車PDPTW問題的求解性能，問題規(guī)模至多為200個需求點。最近的研究中，Wang等[8]針對在特定時間窗取送貨問題開發(fā)了并行模擬退火算法。Nguyen等[9]提出了一種基于基于禁忌搜索的新型啟發(fā)式算法求解多路徑PDPTW問題，針對同樣的問題，Nalepa和Blocho[10]設計了增強導向性射出搜索算(GES)法進行求解，但研究中均未解決取送貨作業(yè)的配對問題。Phan與Suzuki[11]提出了一種適用于移動網(wǎng)絡系統(tǒng)的進化算法，整合全局與局部搜索過程以加快解的收斂速度，至多求解400個客戶點需求。

國內研究方面，李玲等[12]提出了解決多車庫、多貨物類型PDPTW問題的插入啟發(fā)式算法，可在較短時間內有效求解240個客戶點的算例。賈永基等[13]運用禁忌搜索算法進一步改進了文獻[12]的解，并通過實例驗證了算法的求解性能。在此基礎上，賈永基等[14,15]提出了單車獨占性PDPTW問題(E-PDPTW)，相繼開發(fā)了基于最遠插入法、3-opt交換法的兩階段快速算法，以及滾動時域調度算法，可求解客戶數(shù)量高達1000的大規(guī)模問題。藍伯雄與張躍[16]提出了基于坐標定位法與概率式禁忌搜索的兩階段算法，實驗表明概率式禁忌搜索算法較傳統(tǒng)禁忌搜索算法更高效。郭伏與隆穎[17]運用啟發(fā)式算法與整數(shù)規(guī)劃相結合的方法求解PDPTW問題，但僅適用于帶嚴格時間窗且無隨機節(jié)點產(chǎn)生的情境。隨后，郭伏等[18]對文獻[17]的算法進行了改進，以解決取貨節(jié)點動態(tài)隨機出現(xiàn)的問題。鄭四發(fā)等[19]提出了扇面Dijkstra算法求解PDPTW的最短路徑問題，并通過實驗驗證了該算法較之Dijkstra算法及A-star算法在計算時間上的優(yōu)越性。潘立軍與符卓[20]運用遺傳算法結合基于時差的插入法來求解PDPTW問題，通過與文獻[3]求解結果的對比驗證了算法的求解質量。

通過分析可以發(fā)現(xiàn)，啟發(fā)式算法雖可較快速求解，但容易陷入局部最優(yōu)解，導致所求得解的質量較差。本研究針對PDPTW問題構建時空網(wǎng)絡并建立數(shù)學模型，開發(fā)基于列生成法與啟發(fā)式規(guī)則的混合算法進行求解，以期克服單純啟發(fā)式算法的缺點，在較短時間內為調度人員提供同時滿足客戶需求與貨運限制的車輛路徑組合。

1 取送貨問題描述及模型構建

1.1 問題描述

PDPTW相關概念定義如下：

(1)任務：貨運公司接到客戶訂單(貨運需求)后，即產(chǎn)生一個取貨任務與一個送貨任務。在路網(wǎng)中，一取貨任務代表一取貨點，一送貨任務代表一送貨點。

(2)巡回路徑：每輛貨車從場站出發(fā)后執(zhí)行一連串的任務，最終再回到場站的路徑稱為巡回路徑，簡稱路徑。

(3)優(yōu)先級約束：針對每一貨運需求，取貨任務的服務順序須于送貨任務前。

(4)聯(lián)結約束：每一貨運需求的取送貨任務均由同一輛車服務。

(5)時間窗約束：每個取送貨任務均有允許服務的時間范圍，車輛僅能于該范圍內執(zhí)行任務，若早于時間范圍到達，則需等待至最早開始時間；若晚于時間范圍，則不可執(zhí)行該客戶的任務。

(6)車輛容量約束：配送車輛有載重上限，作業(yè)過程中不可違反車輛容量限制。

PDPTW問題可以描述為：客戶需求包括取貨作業(yè)與送貨作業(yè)兩部分，車輛由場站空駛出發(fā)，到達客戶指定的取貨點收取貨物后運送至客戶指定的送貨點，各作業(yè)任務均有時間窗限制，任務完成后車輛回到場站。本研究探討的PDPTW問題為單車種、單場站、多車輛取送貨問題，求解總行駛距離成本最小的車輛路徑組合。

本研究基于以下假設條件：

(1)每輛車載重容量相同，且車輛數(shù)有上限。

(2)貨物需求點已知，每個貨運需求即代表一組取貨與送貨的配對。

(3)服務時間為0，即車輛開始執(zhí)行服務后即完成任務離開。

(4)每個任務均有貨物載重量。若為取貨任務則貨物載重量為正值，若為送貨任務則貨物載重量為負值。

(5)每輛車從場站出發(fā)，最后回到場站。

(6)每輛車均為混合式取送貨，也即在車輛離開場站至回到場站的路徑中，允許執(zhí)行不同訂單的取貨或送貨任務，但同一訂單的取貨任務必在送貨任務前執(zhí)行，且車輛一離開場站須直接執(zhí)行取貨任務。

1.2 模型構建

本研究將PDPTW問題構建為集合劃分問題，建立如下模型：

(1)

(2)

(3)

xr∈{0,1},?r∈R

(4)

其中二元變量xr代表一條可行路徑，該路徑需滿足各任務的時間窗約束、優(yōu)先級約束、聯(lián)結約束以及行車過程中的車輛容量約束。當路徑r被選擇時，xr=1；反之xr=0。

R為所有路徑的集合，Cr為路徑的行駛距離成本，N為所有任務點的集合，包含取貨作業(yè)任務與送貨作業(yè)任務。

式(1)為最小化所有路徑的總行駛距離成本。

式(2)為集合劃分約束式，表示每一個任務都需被服務，且僅可服務一次，若路徑r包含任務i，則air=1，反之a(chǎn)ir=0。

式(3)為車輛數(shù)目約束，K為可使用車輛數(shù)的上限。

2 算法設計

列生成法的優(yōu)點在于求解過程中每次僅考慮部分變量，通過子問題產(chǎn)生一些對主問題可改善目標值的變量，以增進求解效率[21]。已有學者嘗試運用列生成法解決PDPTW問題，Dumas等[1]利用列生成法求解多臺車的PDPTW問題，考慮了異種車隊與多場站等限制，將子問題建構成帶約束的最短路徑問題，運用動態(tài)規(guī)劃進行求解，算法可解決50個需求任務。Xu等[22]運用以列生成法為基礎的啟發(fā)式算法解決多車輛的PDPTW問題，考慮了每個起訖點有多時間窗限制、載重限制、司機工時限制等額外限制式，算法可求解隨機產(chǎn)生的200個需求任務。Sigurd等[23]探討活豬運輸?shù)膯栴}，將子問題設計成一非環(huán)狀的層級圖，提出的算法至多可求解500個需求任務。通過分析現(xiàn)有研究可知，目前文獻中基于列生成法的算法可求解的PDPTW問題規(guī)模有限，且算法耗時較長。

因此，本文提出一種新的基于列生成法的PDPTW問題求解流程即CGA算法，改進子問題求解算法，以期在較短時間內求解大規(guī)模PDPTW問題，算法流程圖如圖1所示。

圖1 基于列生成法的CGA算法流程圖

CGA算法中，由于主問題的變量數(shù)目龐大，因此選擇其中的部分變量(至少包含一組可行變量)構建受限主問題。求解受限主問題至獲得最優(yōu)解，并將此時受限主問題的對偶變量傳遞給子問題。求解子問題生成具有減少成本的列，將成本最小的列加入到受限主問題中，繼續(xù)求解受限主問題。重復上述過程，直至子問題無法生成具有減少成本的列為止，此時，滿足對偶可行性，原線性規(guī)劃問題達到最優(yōu)。當受限主問題的解不是整數(shù)解時，采用分支定界法求得整數(shù)解。最后，判斷每一位客戶是否恰由一輛車服務，若是，則算法結束，否則運用啟發(fā)式算法解決該問題。

2.1 主問題

運用列生成法時，主問題僅需松弛本研究構建的集合劃分模型中的整數(shù)約束，使其成為線性規(guī)劃問題即可。而相比于集合劃分問題，集合覆蓋問題更易于求解，除非一個任務由兩輛車服務較由一輛車服務的成本小，否則重復覆蓋的情形不會發(fā)生。因此，本研究將列生成法的主問題構建為松弛整數(shù)約束后的集合覆蓋問題，表示如下：

(5)

(6)

(7)

xr≥0,?r∈R

(8)

其中，式(6)即為集合覆蓋問題的約束式，表示每一個任務i至少被服務一次。式(8)為松弛整數(shù)約束后的非負限制。

2.2 受限主問題

本研究以“同一訂單需求為一條路徑”作為主問題的初始可行變量，即一條路徑包含一組取貨與送貨作業(yè)。為使初始的受限主問題為可行解，設定K為訂單數(shù)量，當受限主問題的變量增加至一定數(shù)目時，將K重設回車輛數(shù)的上限，以滿足車輛數(shù)量約束。受限主問題表示如下：

(9)

(10)

(11)

xr≥0,?r∈J

(12)

其中，J為已使用變量的集合，J?R。

2.3 子問題

本研究運用單純形法獲得受限主問題的最優(yōu)解及其所對應的對偶變量，根據(jù)對偶理論，設受限主問題中式(10)、式(11)對應的對偶變量分別為πi、π0，則其對偶問題為：

(13)

(14)

πi≥0,?i∈N

(15)

π0≤0

(16)

(17)

2.3.1 路網(wǎng)構建

假設圖G為一路網(wǎng)，V表示節(jié)點的集合，A表示連線的集合。因此，G可以定義為G=(V,A)，路網(wǎng)結構詳述如下：

(1)節(jié)點

令訂單數(shù)為n，則節(jié)點集合V包含起點(0)、各訂單的取貨任務點N+={1,2,…,n}、各訂單的送貨任務點N-={n+1,n+2,…,2n}以及訖點(2n+1)，訂單需求集合N為N={N+∪N-}。

每個節(jié)點具備多個屬性：節(jié)點編號i，最早可開始服務時間ei，最晚需開始服務時間li，需求載重量qi，若i∈N+，則qi為正數(shù)；若i∈N-，則qi為負數(shù)。

(2)連線

連線即為兩個不同節(jié)點相連而成，(i,j)∈A，其中i,j∈V且i≠j。起點(0)與所有取貨點相連，訖點2n+1與所有送貨點相連。任意兩個任務節(jié)點i與j間只要滿足ei+tij≤lj即可相連，其中，tij為任務節(jié)點i到任務節(jié)點j的行駛時間。

為保證優(yōu)先級約束，同一配對的任務不能先送貨再收貨，也即(n+i,i)，(2n+1,0)，(2n+1,i)，(2n+1,n+1)，i=1,2,…,n等不可相連。

(3)連線成本

(18)

由式(18)可知，路徑r的成本與主問題中路徑r的減少成本相等，因此由子問題求得的最短路徑成本即為該路徑于對偶問題中對偶可行性約束式的左邊項目。

2.3.2 問題求解

Dijkstra’s算法通常被應用于求解最短路問題，由于本研究中連線成本可能出現(xiàn)負數(shù)，而Dijkstra’s算法不能應用于負成本連線的網(wǎng)絡上，因此提出修正的Dijkstra’s算法，除了考慮傳統(tǒng)Dijkstra’s算法中成本Ci與前置點Pi兩重標號外，還包含執(zhí)行時間Ti、累積載重Li及訂單集合PickupSeti三重標號，其中，Ti記錄車輛開始服務節(jié)點的時間，Li記錄服務完i后車輛的累積載重量，PickupSeti記錄服務完i后已取未送的訂單。算法流程如圖2所示。

圖2 子問題的求解算法流程圖

圖3 算法A流程圖

算法A用于更新節(jié)點標號，除成本外，還需針對每個節(jié)點進行優(yōu)先級約束、聯(lián)結約束、時間窗約束及車輛容量約束的檢查。此外，若Li不為0，則車輛不可回到訖點。算法A的具體流程如圖3所示。其中，Cap為車輛載重上限。

也正是由于算法A中的多重約束，將導致其中的某些路徑須執(zhí)行某些特定節(jié)點方可返回場站。即使訖點尚未有上游點，在其他節(jié)點均已被固定的情況下，訖點也會被固定進而結束算法，即可能無法求得一條起訖點之間的可行路徑，因此進一步提出改善算法B，運用最省插入法修補路線，產(chǎn)生完整路徑，并使用交換法改善該完整路徑的減少成本，以產(chǎn)生負成本的路徑。因此算法B可分為兩部分：B1為修補路線算法，用于算法A執(zhí)行后，訖點無上游點的情形；B2為改善成本算法，用于路線修補完整、算法A執(zhí)行完畢且訖點有上游點的情形。

令D為送貨點已插入或取貨點已移除的訂單集合，U為送貨點已嘗試插入但未插入或取貨點已嘗試移除但未移除的訂單集合，算法B1的具體流程如圖4所示。

圖4 算法B1流程圖

算法B2的具體流程如圖5所示。

圖5 算法B2流程圖

2.4 重復覆蓋問題的啟發(fā)式算法

通過對主問題及子問題的求解，最后有可能導致一個客戶點被多輛車服務也即重復覆蓋問題的出現(xiàn)，本研究運用移除法解決該問題：逐一找出重復覆蓋節(jié)點的路徑，計算移除該節(jié)點后的可減少的路徑成本，保留減少路徑成本最少的節(jié)點，刪除剩余節(jié)點，使該節(jié)點僅被一輛車服務。算法流程如圖6所示。

圖6 重復覆蓋節(jié)點的啟發(fā)式算法

3 數(shù)值實驗

3.1 近似最優(yōu)解算法

為驗證本文所提出CGA算法的求解性能，進一步構建近似最優(yōu)解算法OPT。該算法同樣基于列生成法，流程架構與CGA相同，區(qū)別在于子問題的求解方法不同。

為確保求解結果的最優(yōu)性，OPT算法不考慮成本約束，因此每一次迭代所更新的不同路徑中可能出現(xiàn)相同的節(jié)點，也即同一節(jié)點由兩條或以上的不同路徑到達。令k為迭代次數(shù)，S(k)為在第k次迭代中所有更新點的集合。

S(k)除記錄更新節(jié)點標號之外，還需記錄在第k次迭代中某節(jié)點為第幾個相同的節(jié)點的編號，S(k)={(更新的節(jié)點i，此節(jié)點i在第k次迭代同節(jié)點i中更新的順序)}。為判斷每一節(jié)點在每次迭代中是否更新，將節(jié)點分為“已試”與“未試”兩種；為判斷所有屬于S(k)的節(jié)點是否已檢驗時間窗限制，進一步分為“已驗”與“未驗”。算法流程如圖7所示。

圖7 OPT算法流程圖

3.2 算例求解與分析

本研究使用Li和Lim[3]提出的PDPTW的LC1、LC2、LR1、LR2、LRC1、LRC2六種基準實驗構建算例。其中，客戶分布狀態(tài)為集聚型LC、隨機型LR與混合型LRC；LC1、LR1、LRC1的時間窗范圍較小，LC2、LR2、LRC2的時間窗范圍較大。此外，小規(guī)模算例的客戶點數(shù)量分別為6、8、10、16、20、24、26；大規(guī)模算例的客戶點數(shù)量分別為100、200、400、600，從上述六種基準實驗每種隨機選出3例，共計72例。

首先通過小規(guī)模算例，借由求解結果與算法OPT的比較，驗證算法CGA的求解性能；其次，為進一步探究算法CGA的效果，分別對大規(guī)模算例的平均行駛距離成本、平均車輛數(shù)及平均求解時間進行求解；最后，以CGA為基礎，進一步提出三種不同的求解步驟(如表1所示)，并運用統(tǒng)計學軟件SPSS做單因素方差分析，探索不同屬性的算例應運用何種算法可獲得較優(yōu)的解。

表1 大規(guī)模算例的算法分類

本文運用Visual C++6.0進行算法編寫，以Microsoft Visual Studio 2008進行編譯，在計算機(Intel Core I5 CPU，4.0 GB memory，2.50 GHz)上運行。

3.2.1 小規(guī)模算例的CGA與OPT求解

分別運用算法CGA與OPT對小規(guī)模算例進行求解，求解結果如表2所示。

表2 運用CGA與OPT求解小規(guī)模算例的結果比較

由總行駛距離的GAP值可知，對于客戶點數(shù)量小于20的網(wǎng)絡規(guī)模，算法CGA與算法OPT所求得的總行駛距離成本相同；當客戶點大于20時，兩種算法求得的總行駛距離成本不同，但GAP值均在5%以內。

兩種算法求解的車輛數(shù)相同，但求解時間卻從客戶點數(shù)量16開始呈現(xiàn)非線性增長。由此可知，當客戶點數(shù)量小于26的路網(wǎng)規(guī)模時，本文算法CGA可求得與OPT相近的近似最優(yōu)解；隨著客戶點數(shù)量的增多，CGA求解效率較OPT更為顯著。

3.2.2 大規(guī)模算例的CGA求解

為進一步驗證算法CGA的有效性，運用CGA算法對72例大規(guī)模算例進行求解，并根據(jù)算例屬性的不同將求解結果按照“客戶點類型”、“客戶點數(shù)量”劃分為2個大類10個子類，針對10個子類分別匯總“平均行駛距離成本”、“平均車輛數(shù)”、“平均求解時間”。

表中BB即分支定界法，由于其求解效率受算例規(guī)模的影響較大，因此為了明確列生成法之于PDPTW問題的求解效果，本研究將求解時間劃分為包含分支定界法的總求解時間以及剔除分支定界法的求解時間。

表3 運用CGA求解大規(guī)模算例的結果

由表3可以看出，不同客戶點類型的求解結果存在顯著差異。集聚型LC客戶點由于分布相對集中，“平均行駛距離成本”較其他兩種分布節(jié)約了許多。除混合型LRC外，其他兩種類型均在時間窗范圍較小的客戶分布(LC1與LR1)下求得較低的距離成本，這是由于時間窗范圍越小，求解過程中易出現(xiàn)無法滿足時間窗約束僅執(zhí)行少量訂單的情況，導致訖點易出現(xiàn)上游點，進而執(zhí)行算法B2改善目標函數(shù)值；時間窗范圍越大，求解過程中時間窗約束越容易滿足，可執(zhí)行的訂單取貨機會就越多，反而會出現(xiàn)不滿足送貨點時間窗約束的情況，導致訖點無上游點，進而無法執(zhí)行算法B2。

較隨機型LR而言，LC與LRC在“平均車輛數(shù)”方面優(yōu)勢明顯，而時間窗范圍與“平均車輛數(shù)”沒有明顯的相關關系。

如前文所述，分支定界法的求解效率易受客戶點數(shù)量影響，因此僅探討表3中不包含分支定界法的“平均求解時間”。明顯地，由表3最后一列數(shù)據(jù)可知，針對同一類客戶點分布類型，時間窗范圍越小，算法耗時越短。

通過表3可知，不同客戶點數(shù)量的求解結果亦存在顯著差異?！捌骄旭偩嚯x成本”、“平均車輛數(shù)”、“平均求解時間”基本隨著客戶點數(shù)量的增多而呈現(xiàn)上升的趨勢。對于客戶數(shù)量在200以內的算例，本研究所提出的算法CGA可在2分鐘內獲得求解結果；而對于客戶規(guī)模更大的算例，均可在20分鐘內求解完畢，求解時間均在可接受的范圍內。

綜合以上數(shù)值實驗結果可知，本研究提出的算法CGA可有效求解取送貨問題，且求解效果顯著。

3.2.3 大規(guī)模算例的單因素方差分析

本節(jié)運用SPSS分別針對六種類型的客戶點及四種規(guī)模的客戶點數(shù)量進行“平均行駛距離成本”、“平均車輛數(shù)”、“平均求解時間”的單因素方差分析。其中，事后檢驗通過Tukey法及Dunnett’s C兩種方法進行。

“平均行駛距離成本”的單因素方差分析結果如表4所示。

表4 平均行駛距離成本的檢驗結果

*表示在水平0.05上具有顯著性差異。

由表4可知，C1、C2、C3三種算法對于時間窗較小的客戶點類型，即LC1、LR1、LRC1有顯著差異，而對于四種不同的客戶點規(guī)模均有顯著差異。這是由于C1與C2有較多機會執(zhí)行子問題算法B2以改善成本，而C3只有在訖點無上游點時才會執(zhí)行B2。當客戶時間窗范圍較小時，求解過程中僅執(zhí)行少量訂單，使訖點較易產(chǎn)生上游點；而時間窗范圍較大時，可執(zhí)行的取貨訂單增多，極有可能不滿足送貨點的時間窗限制，導致訖點無上游點。

“平均車輛數(shù)”的單因素方差分析結果如表5所示。

表5 平均車輛數(shù)的檢驗結果

*表示在水平0.05上具有顯著性差異。

由表5可知，C1、C2、C3三種算法僅對LR2的客戶點類型無顯著差異，但平均車輛數(shù)的差值卻較大；而對于四種不同的客戶點規(guī)模均有顯著差異，C1與C2求得的平均車輛數(shù)接近且均少于C3，這是由于子問題求解過程中，算法A結束后，若訖點有上游節(jié)點，C3無法通過B2進行路徑改善，因此每條路徑覆蓋節(jié)點較少，使用車輛數(shù)增多。

本研究使用剔除分支定界法的“平均求解時間”作單因素方差分析，結果如表6所示。

表6 平均求解時間的檢驗結果

*表示在水平0.05上具有顯著性差異。

由表6可知，C1、C2、C3三種算法僅對六種客戶點類型無顯著差異，但由不包含分支定界的平均求解時間可知，除了LC2的C2較C1求解耗時長之外，其余C1的耗時明顯長于C2、C3；C1、C3兩種算法對于100與200的客戶點規(guī)模均有顯著差異，但C3的求解速度最快，這是由于C3中若訖點有上游點則不執(zhí)行B2導致的。

綜上所述，C1、C2兩種算法在求解結果上未有顯著差異，但C1的求解耗時稍長，因此可根據(jù)實際需求適當選擇算法。

4 結論

本文探討了帶時間窗的取送貨優(yōu)化問題，考慮實際配送作業(yè)情況與現(xiàn)實約束條件，基于時空網(wǎng)絡構建了以總行駛距離成本最小化為目標的取送貨作業(yè)優(yōu)化模型，開發(fā)了啟發(fā)式算法與列生成法相結合的混合優(yōu)化算法進行求解，并借助于C++進行編譯實現(xiàn)。同時，利用不同規(guī)模的數(shù)值實驗驗證了模型以及優(yōu)化算法的有效性，為進一步的實用化奠定了基礎。未來的研究將關注于基于貨運量的多車型任務分配及調度的聯(lián)合優(yōu)化問題。