有時間窗物流配送路徑優化問題的混合并購算法＊

趙建民, 劉芳華, 徐慧英, 朱信忠

(浙江師范大學數理與信息工程學院,浙江金華 321004)

0 引 言

隨著市場經濟的發展,物流配送在貨物運輸成本中所占的比例越來越高.物流配送路徑優化問題就是通過合理配送路線,使總運行距離最短或總成本最低.有時間窗物流配送路徑優化問題則是在物流配送路徑優化問題的基礎上,增加了有時間窗約束的條件.解決有時間窗物流配送路徑優化問題的常用算法有:遺傳算法[1-4]、禁忌搜索算法、蟻群算法[5]等.目前,在 Solomon Benchmark problems數據集上實驗獲得最佳效果的方法分別為:進化啟發式算法[6]、概率多元化算法[7]、禁忌算法[8]、混合算法[9]和節約法[10].

并購算法是通過并購、重組操作達到資源整合、優化配置的企業并購行為,是基于企業并購思想之上形成的一種優化方法.企業并購是在市場經濟環境下,根據市場自身規律,企業在誕生、發展、滅亡的過程中形成的市場資源的再整合,也是優化市場資源配置的市場自身調節行為.根據并購操作的不同,又分為單一并購算法 (也簡稱并購算法,http://www.idsia.ch/～luca/macs-vrptw/problems/welcome.htm)和混合并購算法.本文通過建立混合并購算法模型,把混合并購算法應用到有時間窗物流配送路徑優化問題中,獲取有時間窗物流配送路徑問題的最優解或近似最優解.

1 物流配送路徑優化問題的數學模型

1.1 符號定義

有時間窗物流配送路徑優化問題模型涉及到客戶數量、客戶需求量、汽車數量、汽車載重以及時間窗等,為了操作方面,特定義變量如下:

n:客戶數量;dij:客戶點 i到客戶點 j的距離;K:汽車的總數;qk(k=1,2,…,K):車輛 k的最大載重量;gi(i=1,2,…,n):客戶點 i的貨物需求量;wd:單位距離成本懲罰權重;wq:超出最大載重量的單位載量成本懲罰權重;we:客戶點的單位等待時間懲罰權重;wl:客戶點的單位遲到時間懲罰權重;ti:到達客戶 i的時間;[ETi,LTi]:客戶點 i要求的時間窗,其中 ETi是客戶要求被服務的時間窗的始點,LTi是客戶要求被服務的時間窗的終點.

1.2 目標函數及約束條件

有時間窗物流配送路徑問題的目標就是獲取問題的最優解或近似最優解,即使物流配送的成本最小化.但要達到所求的目標,就要滿足相關約束條件.定義變量如下:

目標函數

式 (1)中:minZ表示完成物流配送的最小運行成

滿足以下約束條件:

其中:式 (2)表示某車輛所訪問的客戶需求量之和不能超過車輛的最大載量;式 (3)表示客戶點 i由車輛 k完成的唯一性;式 (4)和式 (5)表示到達客戶的車輛的唯一性.

2 混合并購算法在有時間窗物流配送路徑優化問題中的應用

2.1 混合并購算法簡介

混合并購算法是在并購算法的基礎上形成的,也是基于企業并購思想之上形成的一種優化方法.混合并購算法包括企業生態編碼、初始化企業生態、預處理企業生態、評估劣信度、混合并購操作、重組操作、選擇操作主要行為,其流程圖如圖 1所示.

混合并購算法的主要步驟如下:

步驟 1 參數設置及初始化.企業生態鏈條數 NT;循環迭代次數 Nc=1;最大迭代次數 Nmax;當前參與出售的企業集團標識 Group M ark=ones(NT,1);當前參與出售企業個體標識Single M ark=ones(NT,1);MASingleSum是 som e函數獲取的企業個體總數;GroupChain表示NT個企業生態鏈;GroupSum為當前企業鏈上企業集團的數目;隨機生成 NT條企業生態鏈,每條鏈上有 n個企業個體;當前企業生態所執行的并購操作類型 runType=zeros(NT,1),zeros是賦值為 0的函數.

圖 1 混合并購算法流程圖

步驟 2 預處理操作.針對具體求解的問題,降解約束條件,對企業生態進行預處理操作.

步驟 3 若 Nc≤Nmax,判斷迭代次數是否達到最大迭代次數,如果是,就結束循環,轉至步驟8;否則,繼續循環,轉至步驟 4.

步驟 4 混合并購操作.令 SingleChain =GroupChain(i).則

若 runType(i)=0,則執行單個并購操作:先修正參數 Group M ark(i),Single M ark(i),再對企業生態鏈進行單個并購操作,即把 Single M ark(i)分別預出售給其他企業集團,計算 min{cost(1),cost(2),…,cost(GroupSum(i))},選擇劣信度最小的企業集團 k作為并購的主體.

若 runType(i)=1,則執行多個并購操作:依次選取臨時企業個體集合 T=Tem p,把 Tem p預出售給其他企業集團,計算min{cost(1),cost(2),…,cost(GroupSum(i))},選擇劣信度最小的企業集團 E,最后確認把 Tem p出售給企業集團 E.

步驟5 重組操作.令 S ingleChain =GroupChain(i).則

1)插入法部分:待重組企業個體集合 T=som e(S ingleChain(j)),把 T中的每一個企業個體先后插入至當前企業集團 j內部適當位置,計算min(cost(S ingleChain(j))),保證當前企業集團 j的劣信度最小.

2)調整法部分:依次取出企業集團 j中的每一企業個體,插入至當前企業集團 j內部適當位置,計算 min(cost(S ingleChain(j))),保證當前企業集團 j的劣信度最小.

步驟 6 劣信度評估.根據并購算法中的劣信度評估及求解的具體問題,分別定義 3個劣信度的計算方法或影響劣信度的要素.用 cost函數計算劣信度.

步驟 7 選擇操作.若 runType(i)=0,則執行以下操作:根據得到的新企業生態鏈劣信度,如果低于舊的企業生態鏈劣信度,則更新企業生態鏈,修正參數 Group M ark(i),runType(i);否則,不更新,修正 S ingle M ark(i),并記錄符合要求的最佳企業生態鏈.

若 runType(i)=1,則執行以下操作:根據得到的新企業生態鏈劣信度,如果低于舊的企業生態鏈劣信度,則更新企業生態鏈,修正參數runType(i),Group M ark(i),S ingle M ark(i),并記錄符合要求的最佳企業生態鏈;否則,只更新當前企業生態鏈,繼續下一次循環,轉至步驟 3.

步驟 8 程序結束,獲得最佳企業生態鏈.

注 1 一般地,將 som e函數定義為:取出企業集團內部的一部分企業個體.企業個體的選擇原則是:計算 max{cost(1),cost(2),…,cost(x)},選擇企業個體劣信度最大的客戶個體 p及其左側(或右側)的所有企業個體,具體數目以不大于當前企業集團內企業個體總數的 1/2為準則.

2.2 有時間窗物流配送路徑優化問題應用模型

根據混合并購算法的思想,結合對有時間窗物流配送路徑優化問題的研究,把混合并購算法應用到有時間窗物流配送路徑優化問題中,建立對應的問題模型,即企業生態編碼、初始化企業生態、預處理企業生態、評估劣信度、混合并購操作、重組操作、選擇操作等.

1)企業生態編碼.采用自然數直接編碼的方法,把一個企業的個體對應至物流配送中的一個客戶.設共有 n個客戶,用 0表示配送中心,用1～n的自然數分別對 n個客戶編號,根據可供使用的汽車總數 K,分成 K組,所形成的編碼就代表一個企業生態鏈,多條企業生態鏈就構成了企業生態 (市場).

2)初始化企業生態.根據企業生態鏈編碼方法,產生一條企業生態鏈,M條這樣的企業生態鏈就構成了企業生態.

3)預處理企業生態.在初始化的同時,用不考慮時間窗和最大載重等因素、只考慮距離因素的并購算法處理物流配送路徑優化問題,可以迅速獲得初始化的最優解,有利于提高混合并購算法的效率.

4)評估劣信度.要判斷某條企業生態鏈所對應的配送路徑方案的優劣,完全由劣信度決定.所謂劣信度,就是企業個體、企業集團或企業生態鏈上運行成本高低的判斷標準,劣信度越低,運行成本越低,否則運行成本越高.根據不同的對象,劣信度計算標準也不一樣;根據并購操作的選擇不同,劣信度評估的標準也有可能不同.只有在定義企業個體劣信度評估時,才會根據單個或多個并購操作,分別定義企業個體劣信度.

企業個體劣信度評估只局限于某個企業集團中.在物流配送路徑優化問題中,它的劣信度包括3個部分,分別是在任一個車輛配送路徑方案中,當前配送客戶與其他客戶間的運輸距離成本 cs,完成當前客戶配送的等待時間成本 ce,完成當前客戶配送的遲到時間成本 cl.這 3個部分的成本之和就構成了企業個體的劣信度.根據并購操作的不同,對距離成本的定義有所不同.如果是單個并購操作,距離成本則定義為:在車輛配送路徑方案中,當前客戶偏離其他客戶的距離成本;如果是多個并購操作,距離成本則定義為:在車輛配送路徑方案中,當前客戶偏離其他客戶的距離成本,以及偏離與之相鄰客戶的距離成本.則企業個體的劣信度評估函數為 cs+ce+cl.

企業集團劣信度評估,就是對企業集團內部生態鏈進行劣信度評估.在物流配送路徑優化中,它的劣信度包括 4個部分,即是在任一個車輛配送路徑方案中,完成客戶配送所需的運輸距離成本 cs,運輸超載成本 cq,完成所有客戶配送的等待時間成本之和 ce,完成所有客戶配送的遲到時間成本之和 cl.企業集團的劣信度評估函數為 (cs+ce+cl)exp(cq).

企業生態鏈劣信度評估,則只針對一個生態鏈而已.在物流配送路徑優化問題中,它的劣信度也包括 4個部分,分別是在物流配送方案中,完成所有客戶配送所需的運輸距離成本 Cs,運輸超載成本之和 Cq,完成所有客戶配送的等待時間成本之和 Ce,完成所有客戶配送的遲到時間成本之和cl.則企業生態鏈的劣信度評估函數為 (Cs+Ce+Cl)exp(Cq),也即是一個完整的物流運輸配送方案的運行成本 (式 (1)).

5)混合并購操作.混合并購操作只針對每一條企業生態鏈上的企業集團和個體.如果是單個并購操作,則遵循以企業集團劣信度從高到低、企業個體劣信度從高到低的原則,逐步出售.收購的企業集團則是按從低到高的原則去收購出售的企業個體.如果是多個并購操作,則由所有企業集團的某些企業個體組成出售的個體集合,分別出售給企業集團劣信度變化最小的企業集團.

6)重組操作.采用插入法和調整法相結合的方法.但插入法在運用上與單一并購算法中的重組操作略有不同.插入法操作的對象不再是集團內部所有個體,而是隨機抽取集團內部相鄰的部分個體 (不大于內部個體總數的 1/2)集合.每次操作隨機選擇一個對象,以插入后當前企業集團劣信度最低為準則,選擇判斷插入位置.由于后插入的每一個客戶都可能對其他客戶產生影響,為了降低影響,需對其再進行調整.所謂調整法,就是對鏈上每個客戶所在的位置按以下規則進行調整:如果該位置上客戶的當前企業集團劣信度不是最低的,則將其調整至最佳位置.當然,調整的次數越多,重組效果越好,但重組效率隨之降低,本文只做一次調整.

7)選擇操作.無論是單個并購操作還是多個并購操作,在每次并購、重組之后,判斷每一條企業生態鏈劣信度是否降低.如果降低,則更新企業生態鏈,否則,不更新.如果當前操作是單個并購操作,且操作還沒有達到終止條件,算法不能再收斂,單個并購算法就有可能“陷入局部最優”,因此可把單個并購操作修改為多個并購操作,繼續循環;如果當前操作是多個并購操作,在每次并購、重組之后,判斷每一條企業生態鏈劣信度是否降低.如果降低,則把多個并購操作修改為單個并購操作,否則,不更新并繼續循環.同時,在當前企業生態中,記錄劣信度最低的企業生態鏈,暫時作為當前最佳物流配送方案.

3 實驗與數據分析

基于MATLAB 7.0開發平臺,編程實現了有時間窗物流配送路徑優化問題的混合并購算法,進行了算法原型系統的構建和模擬運行,并進行了數據的實驗和分析.實驗采用 Solomon所設計的 Solomon Benchmark problems數據集 (http://www.idsia.ch/～luca/macs-vrptw/problems/welcome.htm).其中,每一個問題類型都有 100個客戶,共有 C1,C2,R1,R2,RC1,RC2等 6大類的 56種問題類型.

實驗參數說明:(RT,EC,wq,wd,we,wl)=(迭代次數,企業生態鏈數目,單位超載載量成本懲罰權重,單位距離成本懲罰權重,等待時間懲罰權重,遲到時間懲罰權重).硬件環境:CPU:Genuine Intel 1.86 GHz;內存 :1 G;運行時間 :600 s以內為宜.最后把實驗結果與目前已知的最優解[11]進行比較,結果如表 1所示.其中:Data代表問題類型;K代表需求的汽車數;TD代表汽車總的行駛路程;ET代表等待時間;LE代表遲到時間;N表示第一目標與已知最優解的相對誤差;T表示第二目標與已知最優解的相對誤差.其中,Data,K是設置變量,TD,ET,LE是通過獲取最小成本最優解 (式 (1))對應的物流配送方案得出的.

表 1 混合并購算法在 Solomon數據集上的實驗結果

續表1

通過對實驗數據分析得出:1)混合并購算法在解決 C類問題上效果最為明顯,第一目標和第二目標都達到了最優解,比近似算法[12]的最優解還要好,而且在 C104類問題上獲得了更優解;2)混合并購算法在求解 R2和 RC2類問題上效果也比較好,第一目標達到了最優解,第二目標也基本接近最優解,與近似算法獲得的最優解差不多;3)混合并購算法在解決 R1和 RC1類問題上效果不甚理想,雖然部分問題類型在第一目標上也達到了最優解,但與近似算法的最優解或目前最優解相比,都還有進一步改進的空間.原因是這兩種問題類型的客戶點分布分散,客戶之間的相互影響不大,且時間窗寬窄不一,增大了求解難度.

通過對算法模型分析得出:1)混合并購算法是在并購算法的基礎上形成和發展的,能有效地解決單一并購算法“陷入局部最優”的不足;2)混

合并購算法的時間復雜度不高于其他傳統算法的時間復雜度,如遺傳算法、蟻群算法;3)混合并購算法在求解有時間窗物流配送路徑優化問題時,大部分問題類型獲得了最優解或近似最優解;4)混合并購算法是一種求解物流配送路徑優化問題的新算法,拓寬了求解問題的渠道和方法.

4 結 語

混合并購算法是在單一并購算法的基礎上改進而成的,不僅繼承了單一并購算法的優點,而且有效地解決了單一并購算法“陷入局部最優”的不足.通過模擬實驗,獲得了有時間窗物流配送路徑優化問題的最優解或近似最優解,體現混合并購算法的可行性、有效性、收斂性.雖然在 Solomon數據集上得到了很好的效果,但仍有進一步改進的空間.

[1]BakerB M,Ayechew M A.Agenetic algorithm for the vehicle routing problem[J].Computers&Operations Research,2003,30(5):787-800.

[2]Hanshar F T,Ombuki-Ber man B M.Dynamic vehicle routing using genetic algorithms[J].Applied Intelligence,2007,27(1):89-99.

[3]Alvarenga GB,Mateus G R,de Tomi G.A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows[J].Computers&Operations Research,2007,34(6):1561-1584.

[4]Beatrice O,Brian J R,Franklin H.Multi-objective genetic algorithms for vehicle routing problem with time windows[J].Applied Intelligence,2006,24(1):17-30.

[5]Chen Chiaho,Ting Chingjung,Chang Peiahan.Applying a hybrid ant colony system to the vehicle routing problem with time windows[J].Journal of the Eastern Asia Society of Transportation Studies,2005(6):2822-2836.

[6]Homberger J,Gehring H.Two evolutionary metaheuristics for the vehicle routing problem with time windows[J].I NFOR,1999,37(3):297-318.

[7]Rochat Y,Taillard E.Probabilistic diversification and intensification in local search for vehicle routing[J].Journal of Heuristics,1995,1(1):147-167.

[8]Taillard E,Badeau P,GenderauM,et al.A tabu search heuristic for the vehicle routing problem with soft time windows[J].Transportation Science,1997,31(2):170-186.

[9]Thangiah S R,Osman IH,Inayagamoorthy R,et al.Algorithms for the vehicle routing problemswith time deadlines[J].Amer J MathManagement Sci,1994,13(3/4):323-355.

[10]劉芳華,趙建民,徐慧英.基于并購算法的物流配送路徑優化的研究[J].計算機與數字工程,2009,37(8):25-28.

[11]Bent R,Van Hentenryck P.A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time W indows[J].Transportation Science,2004,38(4):515-530.

[12]劉小蘭,郝志峰,汪國強,等.有時間窗的車輛路徑問題的近似算法研究[J].計算機集成制造系統,2004,10(7):825-831.