托運(yùn)人聯(lián)盟下的訂單組合及車(chē)貨調(diào)配問(wèn)題研究

閆 芳, 張 鳳

(重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院，重慶 400074)

0 引言

中小型托運(yùn)人企業(yè)作為現(xiàn)代物流產(chǎn)業(yè)的重要組成部分，對(duì)國(guó)民經(jīng)濟(jì)的發(fā)展具有重要的推動(dòng)作用。然而，一方面作為托運(yùn)人的中小型生產(chǎn)及貿(mào)易企業(yè)發(fā)展迅速，企業(yè)數(shù)量增多，另一方面其物流費(fèi)用水平整體偏高，如何有效整合中小型托運(yùn)人企業(yè)的資源以降低整個(gè)中小型托運(yùn)人市場(chǎng)物流總費(fèi)用，是亟待解決的一個(gè)難題[1]。中小型企業(yè)資金及設(shè)備資源有限，仍有較大一部分企業(yè)采用自營(yíng)配送模式，但由于自有運(yùn)輸車(chē)輛較少、訂單規(guī)模及訂單量不確定，導(dǎo)致大量空載、非滿載的運(yùn)輸現(xiàn)象存在，使得物流成本整體偏高。因此，基于物流聯(lián)盟的理念，本文考慮建立托運(yùn)人聯(lián)盟關(guān)系以降低物流總費(fèi)用。

目前國(guó)內(nèi)外針對(duì)物流聯(lián)盟已經(jīng)展開(kāi)了一定的研究，但針對(duì)托運(yùn)人聯(lián)盟的理論研究相對(duì)較少。對(duì)物流聯(lián)盟的研究，一部分文獻(xiàn)基于運(yùn)輸聯(lián)盟成本分?jǐn)偡绞降难芯縖2,3]、配送模式研究[4]、車(chē)輛路徑問(wèn)題研究[5]。另一部分基于承運(yùn)人聯(lián)盟的研究主要側(cè)重解決聯(lián)盟線路優(yōu)化及車(chē)輛調(diào)度問(wèn)題[6～8]、利用合作博弈理論設(shè)計(jì)或改進(jìn)聯(lián)盟利潤(rùn)分配機(jī)制[9～11]。而對(duì)于托運(yùn)人聯(lián)盟問(wèn)題的研究相對(duì)匱乏，相關(guān)研究一部分解決聯(lián)盟成員利潤(rùn)或成本分配問(wèn)題，提出合理的分配機(jī)制，Okan等人[12]從合作博弈文獻(xiàn)中開(kāi)發(fā)出成本分配機(jī)制，并分析了幾種成本分配方案。另一部分研究主要通過(guò)建立模型、設(shè)計(jì)相應(yīng)的算法解決托運(yùn)人聯(lián)盟運(yùn)輸路線優(yōu)化問(wèn)題，如文獻(xiàn)[13～15]。但是，上述研究多考慮單發(fā)貨中心到有限客戶(hù)端，較少考慮跨區(qū)域干線運(yùn)輸，鑒于我國(guó)多級(jí)物流中心轉(zhuǎn)運(yùn)形式較多，如何整合中小型托運(yùn)人企業(yè)同向干線運(yùn)輸任務(wù)以降低物流總費(fèi)用具有重要的研究意義。因此，本文以托運(yùn)人聯(lián)盟為背景，結(jié)合我國(guó)現(xiàn)實(shí)需要，綜合考慮訂單起止點(diǎn)、時(shí)間窗等因素，對(duì)訂單進(jìn)行組合及車(chē)輛調(diào)度問(wèn)題進(jìn)行研究。

1 模型建立

1.1 問(wèn)題描述和基本假設(shè)

本文建立一個(gè)由多托運(yùn)人組成的運(yùn)輸聯(lián)盟，聯(lián)盟內(nèi)所有資源共享，所有訂單的分配與車(chē)輛的調(diào)度由聯(lián)盟決定。現(xiàn)考慮，將同一目的地訂單，在滿足車(chē)輛載重的條件下使用同一輛車(chē)運(yùn)輸，以最大程度提高車(chē)輛裝載率。此外，為保證運(yùn)輸聯(lián)盟的服務(wù)質(zhì)量，還需考慮聯(lián)盟后成員的整體滿意度，該滿意度將量化為運(yùn)輸懲罰成本考慮到目標(biāo)函數(shù)中，運(yùn)輸懲罰成本與訂單可接受的送達(dá)時(shí)間范圍有關(guān)。

為實(shí)現(xiàn)上述目標(biāo)，建立以下車(chē)輛調(diào)度模型，并假定：各個(gè)需求已知且不可拆分；車(chē)輛原始定位已知；聯(lián)盟的總運(yùn)力滿足所有運(yùn)輸需求；托運(yùn)人的貨物已經(jīng)存放在距離其最近的發(fā)貨點(diǎn)；由于下階段的運(yùn)輸任務(wù)未知，故不考慮車(chē)輛的返程問(wèn)題。

1.2 模型構(gòu)建

1.2.1 符號(hào)說(shuō)明

表1 符號(hào)說(shuō)明

1.2.2 模型構(gòu)建

基于以上假設(shè)及符號(hào)，為解決上述問(wèn)題，建立如下混合整數(shù)規(guī)劃數(shù)學(xué)模型:

(1)

約束條件:

上述模型中相關(guān)變量如下：

(1)Xk,i,j,v={1,0}：當(dāng)訂單k由車(chē)輛v從i地運(yùn)往j地時(shí)，取值為1，否則為0。

即當(dāng)運(yùn)往j地的訂單k由i0地發(fā)貨，則沒(méi)有產(chǎn)生調(diào)配成本，取值為0，否則，取值為1。

(3)Zv={1,0}：當(dāng)車(chē)輛v被使用，則取值為1，否則取值為0。

(4)Ri,j,v={1,0}：當(dāng)車(chē)輛v從i地運(yùn)往j地時(shí)，取值為1，否則為0。

(5)Si,j,v:車(chē)輛v從i地運(yùn)往j地的發(fā)車(chē)時(shí)間。

公式(1)為聯(lián)盟后總成本函數(shù)，由運(yùn)輸成本、固定成本、調(diào)配成本、早到懲罰成本、遲到懲罰成本五部分組成，求最小值；公式(2)確保所有運(yùn)輸任務(wù)均被完成；公式(3)車(chē)輛運(yùn)輸要求限制，保證任意一輛車(chē)只能運(yùn)往一個(gè)目的地；公式(4)車(chē)輛載重限制；公式(5) 時(shí)間約束，車(chē)輛到達(dá)時(shí)間等于車(chē)輛出發(fā)時(shí)間與行駛時(shí)間之和；公式(6)保證只有參與運(yùn)輸任務(wù)的車(chē)輛才會(huì)產(chǎn)生車(chē)輛發(fā)車(chē)時(shí)間，如果車(chē)輛未參與任何運(yùn)輸任務(wù)則車(chē)輛發(fā)車(chē)時(shí)間為0；公式(7)保證訂單不可拆分，且僅能由一輛車(chē)從唯一發(fā)貨地運(yùn)往唯一到達(dá)地；公式(8)確保任意發(fā)貨地所需車(chē)輛數(shù)滿足該發(fā)貨地可用車(chē)輛數(shù)要求；公式(9)車(chē)輛數(shù)限制，整個(gè)運(yùn)輸環(huán)節(jié)所需車(chē)輛數(shù)不超過(guò)總車(chē)輛數(shù)；公式(10)～(11)保證任意一輛車(chē)無(wú)論運(yùn)輸多少訂單任務(wù)，只要參與運(yùn)輸便被標(biāo)記；公式(12)表示變量X與訂單的關(guān)系，僅當(dāng)訂單k有運(yùn)往j地的運(yùn)輸任務(wù)時(shí)，變量X取值可能為1，否則為0；公式(13)表示變量X與車(chē)輛的關(guān)系，僅當(dāng)i地有車(chē)輛v時(shí)，變量X取值可能為1，否則一定為0；公式(14)～(15)確定車(chē)輛v從唯一出發(fā)地i運(yùn)往唯一目的地j。

2 算法設(shè)計(jì)

上述模型不僅涉及訂單組合、還涉及到車(chē)貨匹配及調(diào)度，這兩類(lèi)問(wèn)題均為NP-HARD問(wèn)題，因此該模型的求解較為復(fù)雜[16]?？紤]粒子群算法具有結(jié)構(gòu)簡(jiǎn)單、需要調(diào)節(jié)的參數(shù)較少、較容易實(shí)現(xiàn)的特點(diǎn)[17,18]，故本文采用粒子群算法進(jìn)行模型求解。在時(shí)間窗處理方面，本文制定了三種策略，三種策略下的車(chē)輛與貨物匹配問(wèn)題編碼與解碼方式一致，但時(shí)間窗處理方式不同。

2.1 編碼與解碼

針對(duì)車(chē)輛與貨物匹配問(wèn)題，以訂單總數(shù)m與車(chē)輛總數(shù)s之和為編碼段長(zhǎng)度，即粒子維度，提出圖1所示編碼方案。

圖1 車(chē)輛與貨物匹配問(wèn)題編碼

在車(chē)輛與貨物匹配問(wèn)題的編碼方案中，主要包括兩個(gè)部分：即訂單安排優(yōu)先級(jí)順序和車(chē)輛安排優(yōu)先級(jí)順序。其中，1～m段為訂單安排優(yōu)先級(jí)順序編碼段，m+1～m+s段為車(chē)輛安排優(yōu)先級(jí)順序。在訂單安排優(yōu)先級(jí)順序編碼段中，又將m段劃分為k個(gè)包，以確定各個(gè)包內(nèi)的訂單安排順序。下面以10個(gè)訂單5輛車(chē)為例，闡述具體的解碼過(guò)程，如圖2～4所示。

首先將發(fā)往同一目的地的訂單進(jìn)行打包，并對(duì)每個(gè)包里各個(gè)訂單以訂單編號(hào)升序排列以確定初步的訂單順序，具體過(guò)程如圖2所示。

圖2 合并后的訂單順序

第一步，確定訂單安排優(yōu)先級(jí)順序，如圖3(a)所示。

第二步，確定車(chē)輛安排優(yōu)先級(jí)順序，如圖3(b)所示。

圖3 訂單安排優(yōu)先級(jí)順序及車(chē)輛安排優(yōu)先級(jí)順序

第三步，完成車(chē)輛與貨物的匹配。在滿足訂單運(yùn)量與車(chē)輛載重關(guān)系情況下，根據(jù)訂單及車(chē)輛安排優(yōu)先級(jí)順序，為所有訂單匹配合適的車(chē)輛，具體過(guò)程如圖4所示。

圖4 車(chē)輛與訂單的匹配

2.2 時(shí)間窗處理策略

在確定訂單與車(chē)輛的匹配關(guān)系之后，需要確定車(chē)輛的發(fā)貨時(shí)間，發(fā)貨時(shí)間與車(chē)輛的達(dá)到時(shí)間有關(guān)，因此可以根據(jù)訂單可接受的到達(dá)時(shí)間窗確定車(chē)輛的到達(dá)時(shí)間。

針對(duì)時(shí)間窗的處理，主要有三種策略：

(1)策略一：“最晚到達(dá)時(shí)間”里選擇“最早的時(shí)間”作為到達(dá)時(shí)間

(2)策略二：“最早到達(dá)時(shí)間”里選擇“最晚的時(shí)間”作為到達(dá)時(shí)間

2.3 算法流程

標(biāo)準(zhǔn)粒子群算法首先隨機(jī)初始化一群維度一定的粒子，然后所有粒子根據(jù)個(gè)體極值(pbest)和群體極值(gbest)來(lái)更新自身速度與位置，并將按照如下的更新方式再搜索空間中找到最優(yōu)解:

Vi+1(t+1)=ωVi(t)+c1r1(pbesti(t)-

Xi(t))+c2r2(gbest-Xi(t))

(16)

Xi+1(t+1)=Xi(t)+Vi+1(t+1)

(17)

其中，ω為慣性權(quán)重系數(shù)，c1，c2為算法的學(xué)習(xí)因子，r1和r2是介于[0,1]之間的隨機(jī)數(shù)。

本文將采用標(biāo)準(zhǔn)的粒子群算法來(lái)對(duì)上述模型進(jìn)行求解，具體過(guò)程不再贅述。

3 運(yùn)算測(cè)試及結(jié)果分析

由于不同文獻(xiàn)假設(shè)條件不盡相同，且缺乏針對(duì)本文所研究的問(wèn)題的通用或標(biāo)準(zhǔn)測(cè)試算例，因此本文隨機(jī)生成由4個(gè)發(fā)貨地、4個(gè)到達(dá)地、20個(gè)訂單、10輛運(yùn)輸車(chē)輛組成的實(shí)例。

3.1 系統(tǒng)運(yùn)算環(huán)境及參數(shù)設(shè)置

鑒于前人研究結(jié)果，本文在實(shí)際運(yùn)算過(guò)程中通過(guò)對(duì)不同參數(shù)設(shè)置下的算法運(yùn)行結(jié)果曲線以及解的優(yōu)劣性對(duì)比分析，確定出使算法表現(xiàn)效果最佳的參數(shù)如下：種群規(guī)模為400、最大迭代次數(shù)為400、粒子維度30、學(xué)習(xí)因子C1為1.5、學(xué)習(xí)因子C2為1.5、慣性權(quán)重為0.2。

3.2 結(jié)果分析

3.2.1 三種時(shí)間處理策略下最優(yōu)方案比較

三種時(shí)間處理策略下的懲罰成本均為Pe=0.1(千/天)，Pl=0.2(千/天)。策略一“最晚到達(dá)時(shí)間里選擇最早到的時(shí)間為出發(fā)時(shí)間”，最滿意結(jié)果總成本為16.6千元。策略二“最早到達(dá)時(shí)間里選擇最晚到達(dá)時(shí)間為出發(fā)時(shí)間” 最滿意結(jié)果總成本為17.3千元。兩階段策略，最滿意結(jié)果總成本為16.6千元。

對(duì)比上述三種策略，“策略一”和“策略三”與“策略二”相比，雖然訂單與車(chē)輛組合方式不同，但總成本相等且最優(yōu)。因此，三種時(shí)間處理方式，就運(yùn)行結(jié)果而言，“策略一”=“策略三”>“策略二”，本文隨機(jī)選擇“策略一”為最優(yōu)策略，并以此對(duì)論文展開(kāi)后續(xù)分析。

3.2.2 聯(lián)盟與不聯(lián)盟情況比較

聯(lián)盟情況下，比較三種策略下的滿意解，可發(fā)現(xiàn)總成本最低為16600元，總使用車(chē)輛數(shù)為5。不聯(lián)盟情況下，各托運(yùn)人運(yùn)輸車(chē)輛不共享，且車(chē)輛不等待，假設(shè)每輛車(chē)在本此運(yùn)輸階段僅完成一次運(yùn)輸，在不考慮懲罰成本的情況下，車(chē)輛的最低運(yùn)輸成本已經(jīng)達(dá)到了19000元，總使用車(chē)輛數(shù)10，與聯(lián)盟情況相比，聯(lián)盟比不聯(lián)盟情況下的總成本減少了至少12%，使用車(chē)輛數(shù)減少了50%。綜合上述分析，與不聯(lián)盟情況相比，托運(yùn)人聯(lián)盟時(shí)總成本節(jié)約顯著。

3.2.3 調(diào)配成本對(duì)最滿意方案的影響

以策略一“最晚到達(dá)時(shí)間”里選擇“最早到的時(shí)間”策略為最優(yōu)策略，分析在不同調(diào)配成本下總成本的變化情況，表4為不同調(diào)配成本下總成本匯總數(shù)據(jù)。

表4 不同調(diào)配成本下總成本變化情況

根據(jù)表4數(shù)據(jù)，可發(fā)現(xiàn)當(dāng)調(diào)配成本上調(diào)百分比由70%增加到90%的時(shí)候，總成本的變化非常明顯，總成本增加率達(dá)到了20.30%，且增長(zhǎng)率差額也達(dá)到了百分之6.39%。在調(diào)配成本較低時(shí)，車(chē)輛與訂單的最優(yōu)組合方式變化較小，且總成本的變化也是較平穩(wěn)的；在調(diào)配成本較高時(shí)，車(chē)輛與訂單的最優(yōu)組合方式發(fā)生了明顯變化，且總成本增長(zhǎng)率變化明顯。

3.2.4 懲罰成本對(duì)最優(yōu)方案的影響

以“最晚到達(dá)時(shí)間里選擇最早到的時(shí)間策略” 為最優(yōu)策略，分析在不同懲罰成本下總成本的變化情況，表5為不同懲罰成本下總成本及增長(zhǎng)率變化情況。

表5 不同懲罰成本下總成本及增長(zhǎng)率變化情況

由表5可知，當(dāng)懲罰成本上調(diào)百分比為30%、60%、90%、120%、150%、200%時(shí)，隨著懲罰成本成比例的增加，總成本也成比例的增加；但當(dāng)懲罰成本上調(diào)百分比增大到300%、400%時(shí)，總成本增長(zhǎng)比率變大。在懲罰成本上調(diào)百分比低于300%即懲罰成本低于4時(shí)，最滿意方案不發(fā)生變化，總成本也隨之成比例增加；但當(dāng)懲罰成本高于4時(shí)，最優(yōu)方案發(fā)生改變，且總成本不再成比例增加，這說(shuō)明，此時(shí)懲罰成本最優(yōu)方案產(chǎn)生了較大影響，因?yàn)橹挥型ㄟ^(guò)改變?cè)顫M意方案，才能夠降低總成本。綜合上述分析，在懲罰成本較低，對(duì)最滿意方案的決策影響較?。划?dāng)懲罰成本較高時(shí)，對(duì)最滿意方案決策的影響較大。

3.3 粒子群算法有效性分析

為證明本文所提算法的求解性能，現(xiàn)增加多組小規(guī)模算例，且分別采用LINGO軟件以及本文所提粒子群算法求解，并將其求解結(jié)果及運(yùn)行時(shí)間進(jìn)行分析比較。本文依據(jù)訂單量、托運(yùn)人數(shù)、車(chē)輛數(shù)、到達(dá)地?cái)?shù)等參數(shù)隨機(jī)生成了10組小規(guī)模算例，其中，算例編號(hào)中分別代表(訂單數(shù)-托運(yùn)人數(shù)-車(chē)輛數(shù)-出發(fā)地?cái)?shù)-達(dá)到地?cái)?shù))，計(jì)算結(jié)果如表7所示。

表7 lingo與粒子群算法對(duì)比

從表7可明顯看出，就運(yùn)行結(jié)果而言，無(wú)論采用粒子群算法還是采用LINGO軟件，其求解結(jié)果一致，從而證明了粒子群算法求解結(jié)果的有效性；就運(yùn)行時(shí)間而言，在N=T=50及N=T=300時(shí)，采用粒子群算法求解時(shí)，不同算例規(guī)模下的運(yùn)行時(shí)間基本接近，分別為4s、2m，而采用lingo求解時(shí)，不同算例規(guī)模下運(yùn)行時(shí)間差異較大，平均運(yùn)行時(shí)間約7分鐘?？梢?jiàn)，即使是在小規(guī)模算例求解中，采用粒子群算法也具有較高的求解質(zhì)量以及較快的求解速度。

4 結(jié)論與展望

本文的主要工作如下：①建立了一個(gè)以訂單與車(chē)輛匹配為基礎(chǔ)，同時(shí)考慮調(diào)配成本及懲罰成本的車(chē)輛調(diào)度模型；②提出了針對(duì)該模型的粒子群算法解決方案；③比較了三種時(shí)間處理策略下的聯(lián)盟的最佳方案，并選擇了最佳的時(shí)間處理策略；④分析了調(diào)配成本對(duì)最滿意方案的影響以及懲罰成本對(duì)最滿意方案的影響；⑤通過(guò)與LINGO對(duì)比，分析本文所提算法的表現(xiàn)。

算例結(jié)果表明，本文提出的模型與算法一方面可有效解決中小型托運(yùn)人企業(yè)空載率較高的問(wèn)題，另一方面托運(yùn)人聯(lián)盟有助于整合有限運(yùn)輸能力，在實(shí)現(xiàn)資源共享的同時(shí)，降低聯(lián)盟后總運(yùn)輸費(fèi)用。 本文僅針對(duì)托運(yùn)人聯(lián)盟后的訂單與車(chē)輛匹配及調(diào)配問(wèn)題進(jìn)行研究，未考慮聯(lián)盟成員的成本分配問(wèn)題，在以后的研究中將再做討論。