有時(shí)間窗物流配送路徑優(yōu)化問題的混合并購算法＊

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

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

0 引 言

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

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

1 物流配送路徑優(yōu)化問題的數(shù)學(xué)模型

1.1 符號定義

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

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

1.2 目標(biāo)函數(shù)及約束條件

有時(shí)間窗物流配送路徑問題的目標(biāo)就是獲取問題的最優(yōu)解或近似最優(yōu)解,即使物流配送的成本最小化.但要達(dá)到所求的目標(biāo),就要滿足相關(guān)約束條件.定義變量如下:

目標(biāo)函數(shù)

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

滿足以下約束條件:

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

2 混合并購算法在有時(shí)間窗物流配送路徑優(yōu)化問題中的應(yīng)用

2.1 混合并購算法簡介

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

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

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

圖 1 混合并購算法流程圖

步驟 2 預(yù)處理操作.針對具體求解的問題,降解約束條件,對企業(yè)生態(tài)進(jìn)行預(yù)處理操作.

步驟 3 若 Nc≤Nmax,判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù),如果是,就結(jié)束循環(huán),轉(zhuǎn)至步驟8;否則,繼續(xù)循環(huán),轉(zhuǎn)至步驟 4.

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

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

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

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

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

2)調(diào)整法部分:依次取出企業(yè)集團(tuán) j中的每一企業(yè)個體,插入至當(dāng)前企業(yè)集團(tuán) j內(nèi)部適當(dāng)位置,計(jì)算 min(cost(S ingleChain(j))),保證當(dāng)前企業(yè)集團(tuán) j的劣信度最小.

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

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

若 runType(i)=1,則執(zhí)行以下操作:根據(jù)得到的新企業(yè)生態(tài)鏈劣信度,如果低于舊的企業(yè)生態(tài)鏈劣信度,則更新企業(yè)生態(tài)鏈,修正參數(shù)runType(i),Group M ark(i),S ingle M ark(i),并記錄符合要求的最佳企業(yè)生態(tài)鏈;否則,只更新當(dāng)前企業(yè)生態(tài)鏈,繼續(xù)下一次循環(huán),轉(zhuǎn)至步驟 3.

步驟 8 程序結(jié)束,獲得最佳企業(yè)生態(tài)鏈.

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

2.2 有時(shí)間窗物流配送路徑優(yōu)化問題應(yīng)用模型

根據(jù)混合并購算法的思想,結(jié)合對有時(shí)間窗物流配送路徑優(yōu)化問題的研究,把混合并購算法應(yīng)用到有時(shí)間窗物流配送路徑優(yōu)化問題中,建立對應(yīng)的問題模型,即企業(yè)生態(tài)編碼、初始化企業(yè)生態(tài)、預(yù)處理企業(yè)生態(tài)、評估劣信度、混合并購操作、重組操作、選擇操作等.

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

2)初始化企業(yè)生態(tài).根據(jù)企業(yè)生態(tài)鏈編碼方法,產(chǎn)生一條企業(yè)生態(tài)鏈,M條這樣的企業(yè)生態(tài)鏈就構(gòu)成了企業(yè)生態(tài).

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

4)評估劣信度.要判斷某條企業(yè)生態(tài)鏈所對應(yīng)的配送路徑方案的優(yōu)劣,完全由劣信度決定.所謂劣信度,就是企業(yè)個體、企業(yè)集團(tuán)或企業(yè)生態(tài)鏈上運(yùn)行成本高低的判斷標(biāo)準(zhǔn),劣信度越低,運(yùn)行成本越低,否則運(yùn)行成本越高.根據(jù)不同的對象,劣信度計(jì)算標(biāo)準(zhǔn)也不一樣;根據(jù)并購操作的選擇不同,劣信度評估的標(biāo)準(zhǔn)也有可能不同.只有在定義企業(yè)個體劣信度評估時(shí),才會根據(jù)單個或多個并購操作,分別定義企業(yè)個體劣信度.

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

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

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

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

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

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

3 實(shí)驗(yàn)與數(shù)據(jù)分析

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

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

表 1 混合并購算法在 Solomon數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

續(xù)表1

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

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

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

4 結(jié) 語

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

[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]劉芳華,趙建民,徐慧英.基于并購算法的物流配送路徑優(yōu)化的研究[J].計(jì)算機(jī)與數(shù)字工程,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]劉小蘭,郝志峰,汪國強(qiáng),等.有時(shí)間窗的車輛路徑問題的近似算法研究[J].計(jì)算機(jī)集成制造系統(tǒng),2004,10(7):825-831.