考慮訂單合并和貨物轉(zhuǎn)運(yùn)的多式聯(lián)運(yùn)路徑優(yōu)化研究

李兆進(jìn)， 劉 雅， 楊 臻

(西安交通大學(xué) 管理學(xué)院，陜西 西安 710049)

0 引言

隨著電子商務(wù)的飛速發(fā)展，零擔(dān)物流企業(yè)每個(gè)時(shí)刻需要服務(wù)的訂單數(shù)量迅速增長(zhǎng)[1]。除了訂單數(shù)量龐大以外，每個(gè)訂單都有不同的起訖點(diǎn)和不同的時(shí)間窗要求。面對(duì)大量分散且具有不同起終點(diǎn)和時(shí)間窗約束的客戶訂單，傳統(tǒng)的單一運(yùn)輸方式不僅很難同時(shí)滿足多個(gè)客戶的需求，而且運(yùn)輸成本居高不下。和單一運(yùn)輸方式相比，多式聯(lián)運(yùn)不僅可以同時(shí)服務(wù)多個(gè)運(yùn)輸訂單和整合多種運(yùn)輸資源，而且可以通過(guò)運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)效應(yīng)降低運(yùn)輸成本。多式聯(lián)運(yùn)由于具有靈活、可靠和高效的優(yōu)點(diǎn)而越來(lái)越受到運(yùn)輸行業(yè)和學(xué)術(shù)界的重視[2]。

早期關(guān)于多式聯(lián)運(yùn)路徑優(yōu)化的研究大多是集中于單一訂單的路徑優(yōu)化研究。在給定的多式聯(lián)運(yùn)網(wǎng)絡(luò)中，通過(guò)不同運(yùn)輸工具的銜接運(yùn)輸，尋找一條將貨物從起點(diǎn)運(yùn)往終點(diǎn)的最短路徑。Xiong[3]在給定的多式聯(lián)運(yùn)網(wǎng)絡(luò)中為單個(gè)運(yùn)輸訂單規(guī)劃了路徑。Liu[4]和Kengpol[5]也對(duì)單個(gè)運(yùn)輸訂單在多式聯(lián)運(yùn)網(wǎng)絡(luò)中的路徑優(yōu)化進(jìn)行了研究。

當(dāng)多式聯(lián)運(yùn)網(wǎng)絡(luò)中的訂單增多時(shí)，路徑優(yōu)化的難度會(huì)急劇增加。Chang[6]開(kāi)發(fā)了一種基于拉格朗日松弛技術(shù)的啟發(fā)式算法來(lái)求解多個(gè)訂單在多式聯(lián)運(yùn)網(wǎng)絡(luò)中的路徑規(guī)劃問(wèn)題。Carlsson[7]研究了以卡車和無(wú)人機(jī)所組成的多式聯(lián)運(yùn)網(wǎng)絡(luò)的多個(gè)運(yùn)輸訂單路徑優(yōu)化問(wèn)題。Ayar[8]也為多訂單運(yùn)輸問(wèn)題構(gòu)建了混合整數(shù)規(guī)劃模型。以上關(guān)于多訂單在多式聯(lián)運(yùn)網(wǎng)絡(luò)中運(yùn)輸路徑優(yōu)化的研究都忽略了運(yùn)輸工具的容量限制。Fazayeli[9]和Bevrani[10]在多式聯(lián)運(yùn)網(wǎng)絡(luò)中對(duì)多個(gè)訂單進(jìn)行路徑優(yōu)化時(shí)考慮了運(yùn)輸工具的容量限制。但運(yùn)輸工具可以提供的最大數(shù)量并沒(méi)有限制。目前考慮網(wǎng)絡(luò)中所提供的運(yùn)輸工具最大數(shù)量的研究有Verma[11]和Wang[12]。在對(duì)多個(gè)運(yùn)輸訂單進(jìn)行運(yùn)輸時(shí)，大多是對(duì)各個(gè)訂單分別運(yùn)輸，Moccia[13]和Demir[14]對(duì)多個(gè)運(yùn)輸訂單進(jìn)行路徑優(yōu)化時(shí)，為了實(shí)現(xiàn)運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)效應(yīng)，允許多個(gè)運(yùn)輸訂單進(jìn)行合并運(yùn)輸。

運(yùn)輸訂單的時(shí)間窗也是多式聯(lián)運(yùn)路徑優(yōu)化問(wèn)題的研究特征。湯銀英[15]考慮了多節(jié)點(diǎn)時(shí)間窗差異的集裝箱多式聯(lián)運(yùn)路徑選擇研究。陳釘均[16]研究了有收貨時(shí)間窗軟約束的綠色多式聯(lián)運(yùn)路徑優(yōu)化。在劉松[17]和鄭紅星[18]的研究中，運(yùn)輸訂單的時(shí)間窗要求也被考慮在內(nèi)。

在多式聯(lián)運(yùn)網(wǎng)絡(luò)中，所規(guī)劃的運(yùn)輸訂單路徑往往是由多種運(yùn)輸方式銜接組成的，當(dāng)貨物的運(yùn)輸從一種運(yùn)輸工具轉(zhuǎn)換成為另一種運(yùn)輸工具時(shí)會(huì)產(chǎn)生轉(zhuǎn)運(yùn)成本?，F(xiàn)有研究在多式聯(lián)運(yùn)網(wǎng)絡(luò)中對(duì)單個(gè)訂單或者多個(gè)訂單進(jìn)行路徑優(yōu)化時(shí)都沒(méi)有考慮運(yùn)輸?shù)霓D(zhuǎn)運(yùn)成本。

雖然目前關(guān)于多式聯(lián)運(yùn)路徑優(yōu)化的研究既有針對(duì)單個(gè)訂單的，也有針對(duì)多個(gè)訂單的，并且在研究中會(huì)考慮運(yùn)輸訂單的時(shí)間窗和運(yùn)輸工具的容量，但很少研究將運(yùn)輸工具的數(shù)量以及運(yùn)輸訂單的合并運(yùn)輸同時(shí)考慮在內(nèi)，尤其是將運(yùn)輸訂單在多式聯(lián)運(yùn)網(wǎng)絡(luò)中發(fā)生轉(zhuǎn)運(yùn)并將轉(zhuǎn)運(yùn)成本也考慮在內(nèi)的研究還沒(méi)有。

由于各類運(yùn)輸工具的運(yùn)輸能力不同，多式聯(lián)運(yùn)物流企業(yè)在組織運(yùn)輸?shù)倪^(guò)程中需要考慮所運(yùn)輸?shù)呢浳锶萘坎荒艹^(guò)所選擇運(yùn)輸工具的最大容量。本文研究屬于多式聯(lián)運(yùn)運(yùn)作層研究，需要實(shí)時(shí)決策。在某時(shí)刻，多式聯(lián)運(yùn)物流企業(yè)在網(wǎng)絡(luò)中可以組織的物流資源數(shù)量有限，因此需要將運(yùn)輸資源可以提供的最大數(shù)量也考慮在內(nèi)?；诖?，本文以零擔(dān)多式聯(lián)運(yùn)網(wǎng)絡(luò)為背景，提出了一種考慮訂單合并和貨物轉(zhuǎn)運(yùn)的多式聯(lián)運(yùn)路徑優(yōu)化問(wèn)題，給定一組運(yùn)輸訂單的起點(diǎn)和終點(diǎn)，本文的研究是以總運(yùn)輸成本最小化為目標(biāo)，將貨物在滿足各訂單時(shí)間窗要求的情況下從各自起點(diǎn)運(yùn)往各自的終點(diǎn)，給出各個(gè)運(yùn)輸訂單的運(yùn)輸路徑、運(yùn)輸路徑上運(yùn)輸工具的銜接方式以及路徑上運(yùn)輸工具的使用數(shù)量。在研究中，網(wǎng)絡(luò)中運(yùn)輸工具的容量限制、可以提供的運(yùn)輸工具最大數(shù)量限制、運(yùn)輸工具的最晚服務(wù)時(shí)間限制以及運(yùn)輸?shù)霓D(zhuǎn)運(yùn)成本都被考慮在內(nèi)。同時(shí)，在為運(yùn)輸訂單進(jìn)行路徑規(guī)劃時(shí)，為了實(shí)現(xiàn)運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)效應(yīng)，將多個(gè)運(yùn)輸訂單進(jìn)行合并運(yùn)輸。

1 問(wèn)題描述與模型構(gòu)建

在1.1部分構(gòu)建了描述該問(wèn)題的數(shù)學(xué)模型。為了簡(jiǎn)化模型，在1.2部分對(duì)模型進(jìn)行了轉(zhuǎn)化。

1.1 模型構(gòu)建

決策變量為：xijk:第i個(gè)運(yùn)輸訂單選擇第j條邊上的第k種運(yùn)輸方式，取1；否則取0；yjk:在第j條邊上，選擇第k種運(yùn)輸方式使用的運(yùn)輸工具的數(shù)量；ωiv:如果第i個(gè)訂單在第v個(gè)節(jié)點(diǎn)發(fā)生轉(zhuǎn)運(yùn)，取1，否則取0。

模型目標(biāo)函數(shù)可表示為：

(1)

(15)

目標(biāo)函數(shù)是最小化總的運(yùn)輸成本，其中包括三個(gè)部分：固定運(yùn)輸成本、可變運(yùn)輸成本和轉(zhuǎn)運(yùn)成本。約束(2)為容量約束，表示所安排的運(yùn)輸貨物數(shù)量不能超過(guò)在網(wǎng)絡(luò)中邊上所使用運(yùn)輸工具的最大運(yùn)載能力。約束(3)～(4)和(9)～(10)表示運(yùn)輸訂單在運(yùn)輸網(wǎng)絡(luò)中沒(méi)有運(yùn)輸回路。約束(5)確保運(yùn)輸網(wǎng)絡(luò)的連通性。約束(6)表示貨物到達(dá)時(shí)間必須早于所采用的運(yùn)輸方式的服務(wù)關(guān)閉時(shí)間。約束(7)～(8)為訂單時(shí)間窗約束，運(yùn)輸訂單必須在允許的最早出發(fā)時(shí)間之后從起點(diǎn)出發(fā)，并且在允許的最晚到達(dá)時(shí)間之前到達(dá)終點(diǎn)。約束(11)表示對(duì)于每個(gè)運(yùn)輸訂單來(lái)說(shuō)，貨物最多只能到達(dá)網(wǎng)絡(luò)中的節(jié)點(diǎn)一次。約束(12)表示當(dāng)運(yùn)輸訂單在運(yùn)輸網(wǎng)絡(luò)中發(fā)生運(yùn)輸工具的轉(zhuǎn)換時(shí)決策變量xijk與決策變量ωiv之間的關(guān)系。約束(13)，(14)和(15)表示決策變量xijk、yjk和ωiv的取值范圍。

1.2 模型轉(zhuǎn)化

在多式聯(lián)運(yùn)網(wǎng)絡(luò)中各種運(yùn)輸方式的樞紐點(diǎn)分布在城市的不同位置。當(dāng)貨物在城市內(nèi)發(fā)生運(yùn)輸方式轉(zhuǎn)變時(shí)，會(huì)產(chǎn)生一系列由貨物運(yùn)輸、裝載和卸載操作帶來(lái)的轉(zhuǎn)運(yùn)成本。貨物在城市內(nèi)的樞紐間轉(zhuǎn)運(yùn)過(guò)程描述如圖1所示。

圖1 貨物在樞紐間的轉(zhuǎn)運(yùn)過(guò)程

貨物從城市B的樞紐1運(yùn)輸?shù)匠鞘蠦的樞紐2的每一種操作的成本都和貨物的運(yùn)輸數(shù)量相關(guān)，為了簡(jiǎn)化所構(gòu)建的模型，可將樞紐1到樞紐2的裝卸成本折算為城市內(nèi)的運(yùn)輸成本。那么在城市B內(nèi)，運(yùn)輸樞紐間的轉(zhuǎn)運(yùn)成本就轉(zhuǎn)化為了樞紐間路徑上的運(yùn)輸成本。

那么在1.1所構(gòu)建的模型目標(biāo)函數(shù)可以轉(zhuǎn)化為:

(16)

約束為(2)～(11)、(13)和(14)。

通過(guò)模型轉(zhuǎn)化，與運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)選擇相關(guān)的決策變量轉(zhuǎn)化成了僅和邊選擇相關(guān)的決策變量，降低了計(jì)算的難度。轉(zhuǎn)化后的模型仍然屬于NP難問(wèn)題。當(dāng)問(wèn)題的規(guī)模較小時(shí)，可以利用商業(yè)軟件CPLEX精確求解。當(dāng)問(wèn)題規(guī)模較大時(shí)，精確算法無(wú)法求出最優(yōu)解，此時(shí)啟發(fā)式算法往往能夠得出滿意的近似解?；诖耍疚拈_(kāi)發(fā)了一種可以快速求出該問(wèn)題近似最優(yōu)解的列生成啟發(fā)式算法。

2 基于列生成的啟發(fā)式算法

基于列生成的啟發(fā)式算法框架如圖2所示，在2.1為每個(gè)運(yùn)輸訂單規(guī)劃一條可行路徑，構(gòu)建初可行列(解)；在2.2利用Dantzig-Wolfe分解方法對(duì)原混合整數(shù)規(guī)劃問(wèn)題進(jìn)行重新建模并生成限制性主問(wèn)題；子問(wèn)題的構(gòu)建和求解在2.3進(jìn)行分析；在2.4通過(guò)變量轉(zhuǎn)換構(gòu)建原混合整數(shù)規(guī)劃問(wèn)題的近似最優(yōu)解。

2.1 初始可行解

為了給每個(gè)運(yùn)輸訂單規(guī)劃初始可行路徑，開(kāi)發(fā)了一個(gè)啟發(fā)式算法，其詳細(xì)步驟如下：

Step1松弛原混合整數(shù)規(guī)劃模型的決策變量xijk和yjk為連續(xù)變量并求解松弛后的原混合整數(shù)規(guī)劃模型。將所有xijk取值為正的定義為1，剩余xijk取值為非正的都定義為0。

圖2 基于列生成的啟發(fā)式算法框架

Step2在Step1中被定義為0的決策變量xijk集合中，為每一個(gè)運(yùn)輸訂單規(guī)劃可行路徑。規(guī)劃可行路徑的方法有兩種，第一種：在被定義為0的決策變量xijk集合中，為每個(gè)運(yùn)輸訂單規(guī)劃一條從起點(diǎn)到終點(diǎn)只經(jīng)過(guò)一個(gè)中間節(jié)點(diǎn)并且滿足容量及時(shí)間窗約束的可行路徑；第二種：在被定義為0的決策變量xijk集合中，為每個(gè)運(yùn)輸訂單規(guī)劃一條從起點(diǎn)到終點(diǎn)只經(jīng)過(guò)兩個(gè)中間節(jié)點(diǎn)并且滿足容量及時(shí)間窗約束的可行路徑。通過(guò)以上兩種方法，為每個(gè)運(yùn)輸訂單規(guī)劃了一條經(jīng)過(guò)一個(gè)或兩個(gè)中間節(jié)點(diǎn)的可行路徑。然后，將規(guī)劃出的可行路徑對(duì)應(yīng)的決策變量xijk定義為1。

Step3調(diào)用CPLEX軟件求解小規(guī)模的原混合整數(shù)規(guī)劃問(wèn)題，小規(guī)模的原混合整數(shù)規(guī)劃問(wèn)題與原混合整數(shù)規(guī)劃問(wèn)題的模型一樣，不同之處在于小規(guī)模原混合整數(shù)規(guī)劃問(wèn)題中，將被定義為1以外的決策變量xijk都限制為0。這樣，在CPLEX求解的過(guò)程中，只需要在決策變量xijk被定義為1的解空間中尋找可行路徑。和原混合整數(shù)規(guī)劃問(wèn)題相比，小規(guī)模原混合整數(shù)規(guī)劃問(wèn)題的求解難度極大降低，CPLEX軟件可以快速求出最優(yōu)解解。

Step4由于小規(guī)模原混合整數(shù)規(guī)劃問(wèn)題的最優(yōu)解可以為每個(gè)運(yùn)輸訂單提供可行路徑，而每個(gè)運(yùn)輸訂單的可行路徑對(duì)應(yīng)列生成算法主問(wèn)題的列。為此，輸出小規(guī)模原混合整數(shù)規(guī)劃問(wèn)題的最優(yōu)解并將最優(yōu)解設(shè)置為列生成算法主問(wèn)題的初始列。

2.2 限制主問(wèn)題(RMP)

在給定的多式聯(lián)運(yùn)網(wǎng)絡(luò)中，假設(shè)對(duì)于每個(gè)運(yùn)輸訂單i，可以枚舉出所有的可行路徑，定義以下參數(shù)和決策變量：

1)參數(shù)

令air：表示第i的運(yùn)輸訂單被第r條路徑服務(wù)時(shí)等于1，否則等于0，其中i∈R。同樣令bjkr：表示第r條可行路徑經(jīng)過(guò)了第j條邊并使用了第k種運(yùn)輸方式時(shí)等于1，否則等于0。那么通過(guò)air和bjkr可以定義每一條可行路徑(列)。對(duì)于一條給定的可行路徑，air和bjkr是確定的。令Cr表示第r條可行路徑的路徑成本。

2)決策變量：

ξr：表示第r條可行路徑被使用時(shí)為1，否則為0；yjk和原混合整數(shù)規(guī)劃模型含義相同。那么原混合整數(shù)規(guī)劃模型重新定義為:

(17)

式(17)為目標(biāo)函數(shù)，要求總的運(yùn)輸成本之和最小，包括兩個(gè)部分：路徑成本和固定運(yùn)輸成本；式(18)表示每個(gè)運(yùn)輸訂單都有一個(gè)可行的路徑；式(19)為容量約束，表示所安排的運(yùn)輸貨物數(shù)量不能超過(guò)在網(wǎng)絡(luò)中邊上所使用運(yùn)輸工具的最大運(yùn)載能力。式(20)表示決策變量ξr為0-1變量，式(21)表示決策變量yjk為整數(shù)變量。把式(20)和(21)表示的約束松弛為(22)和(23)，那么得到松弛的線性規(guī)劃主問(wèn)題。

0≤ξr≤1,?r

(22)

0≤yjk≤ncjk,?j∈E,?k=1,…,mj

(23)

由于松弛后的主問(wèn)題的變量數(shù)目巨大，選擇其中部分變量(至少包含一個(gè)可行解)構(gòu)建一個(gè)限制主問(wèn)題(Restricted Master problem，RMP)，即作為列生成算法的限制主問(wèn)題。

在2.1通過(guò)開(kāi)發(fā)的啟發(fā)式算法為每個(gè)運(yùn)輸訂單規(guī)劃了一條可行路徑，所有運(yùn)輸訂單的可行路徑構(gòu)成了限制主問(wèn)題的初始列。在初始解的基礎(chǔ)上調(diào)用CPLEX軟件求解該限制主問(wèn)題。獲取相應(yīng)約束條件的對(duì)偶變量值并傳遞給子問(wèn)題。

2.3 子問(wèn)題(SP)

令πi和μjk表示為約束(18)和(19)對(duì)應(yīng)的對(duì)偶變量。令ωr表示為路徑r所對(duì)應(yīng)的檢驗(yàn)數(shù)。那么ωr可表示為：

(24)

由于每個(gè)運(yùn)輸訂單只能選擇一條可行路徑，那么如果第i個(gè)需求選擇了第r條路徑，則air=1，ap,r=0，其中i≠p。那么式(24)可以表示為:

(25)

對(duì)于每條可行路徑r，其路徑成本Cr又可表示為:

(26)

那么對(duì)于路徑r的檢驗(yàn)數(shù)ωr可表示為：

(27)

在列生成算法中，子問(wèn)題的設(shè)計(jì)是為了尋找滿足每個(gè)運(yùn)輸訂單運(yùn)輸需求且具有負(fù)檢驗(yàn)數(shù)的“列”(可行路徑)，那么子問(wèn)題(SP)可以構(gòu)建為:

(28)

(38)

式(28)為目標(biāo)函數(shù)，表示最小化檢驗(yàn)數(shù)。約束(29)～(37)和約束(3)-(11)具有相同的含義。約束(38)表示決策變量bjkr為0-1變量。對(duì)于每個(gè)運(yùn)輸訂單i，子問(wèn)題以最小化檢驗(yàn)數(shù)為目標(biāo)函數(shù)，在給定的多式聯(lián)運(yùn)網(wǎng)絡(luò)中為運(yùn)輸訂單尋找一條運(yùn)輸成本最小并符合運(yùn)輸訂單時(shí)間窗要求的可行路徑r。子問(wèn)題是一個(gè)最短路徑問(wèn)題，可以利用動(dòng)態(tài)規(guī)劃算法求解。

2.4 構(gòu)造近似最優(yōu)解

在限制主問(wèn)題和子問(wèn)題之間不斷地迭代的過(guò)程中，當(dāng)子問(wèn)題無(wú)法生成具有負(fù)檢驗(yàn)數(shù)的“列”時(shí)，原問(wèn)題達(dá)到最優(yōu)。通過(guò)求解受限制的松弛主問(wèn)題，得到原混合整數(shù)規(guī)劃問(wèn)題的下界。此時(shí)決策變量ξr和yjk都是連續(xù)變量，將決策變量都轉(zhuǎn)換為整數(shù)變量并求解此時(shí)的限制主問(wèn)題，可以得到原混合整數(shù)規(guī)劃問(wèn)題的近似最優(yōu)解。

3 算例測(cè)試及結(jié)果分析

3.1部分對(duì)算例的生成方法和參數(shù)的設(shè)置進(jìn)行描述。算例的測(cè)試結(jié)果在3.2部分進(jìn)行分析。

3.1 生成隨機(jī)算例

根據(jù)多式聯(lián)運(yùn)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量和運(yùn)輸訂單數(shù)量的不同生成大量不同規(guī)模的隨機(jī)算例。和Fazayeli[9]的研究類似，網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量設(shè)置為10個(gè)和20個(gè)，運(yùn)輸訂單的數(shù)量從10到200個(gè)之間變化。根據(jù)運(yùn)輸訂單數(shù)量分為小規(guī)模和中等或大規(guī)模算例。小規(guī)模算例為10或20個(gè)節(jié)點(diǎn)，訂單數(shù)量分別為10、20個(gè)，每種規(guī)模的訂單生成20個(gè)算例；中等或大規(guī)模算例為10或20個(gè)節(jié)點(diǎn)，訂單數(shù)量分別為50,、100和200個(gè)，每種訂單規(guī)模生成20個(gè)算例，共計(jì)200個(gè)算例。

在多式聯(lián)運(yùn)網(wǎng)絡(luò)中，存在3種運(yùn)輸方式：公路運(yùn)輸、鐵路運(yùn)輸和航空運(yùn)輸。和這三種運(yùn)輸方式對(duì)應(yīng)的運(yùn)輸工具分別是：全貨機(jī)、卡車和火車。三種運(yùn)輸工具的運(yùn)輸容量分別是15噸，22.4噸和44.8噸，其中火車的運(yùn)輸容量是指一個(gè)車皮的容量。三種運(yùn)輸工具的固定運(yùn)輸成本分別是966元、483元和322元，可變成本分別是2.9元/噸·公里、2.1元/噸·公里和1.4元/噸·公里。

由于客戶運(yùn)輸訂單信息的隱私性，隨機(jī)生成客戶運(yùn)輸訂單，運(yùn)輸訂單的起點(diǎn)和終點(diǎn)在多式聯(lián)運(yùn)網(wǎng)絡(luò)中隨機(jī)分布。由于多式聯(lián)運(yùn)網(wǎng)絡(luò)中運(yùn)輸工具的最大容量為44.8，運(yùn)輸訂單的運(yùn)輸量在區(qū)間[1,44.8]內(nèi)隨機(jī)生成。運(yùn)輸訂單的最早出發(fā)時(shí)間在區(qū)間[1,24]隨機(jī)分布。為了每個(gè)運(yùn)輸訂單的需求都被滿足，在多式聯(lián)運(yùn)網(wǎng)絡(luò)中，為每個(gè)運(yùn)輸訂單都規(guī)劃一條可行路徑。運(yùn)輸訂單所要求的最晚到達(dá)時(shí)間根據(jù)所規(guī)劃的可行路徑計(jì)算得出。對(duì)于在所規(guī)劃運(yùn)輸訂單可行路徑上邊的運(yùn)輸工具服務(wù)關(guān)閉時(shí)間，設(shè)置為運(yùn)輸訂單到達(dá)該邊起點(diǎn)的最晚時(shí)間。剩余未在運(yùn)輸訂單可行路徑上的運(yùn)輸工具服務(wù)關(guān)閉時(shí)間在區(qū)間[24,1000]隨機(jī)生成。對(duì)于小規(guī)模算例來(lái)說(shuō)，每個(gè)邊上可提供的某種運(yùn)輸工具的最大數(shù)量在區(qū)間[5,15]隨機(jī)生成；對(duì)于中等或大規(guī)模算例來(lái)說(shuō)，每個(gè)邊上可提供的某種運(yùn)輸工具的最大數(shù)量在區(qū)間[10,20]隨機(jī)生成。

3.2 算例測(cè)試結(jié)果分析

對(duì)于小規(guī)模的算例，CPLEX軟件可以直接求出精確解，可以利用精確解來(lái)評(píng)估所開(kāi)發(fā)的列生成啟發(fā)式算法。小規(guī)模算例的求解結(jié)果如表1所示。在表1中，“Opt”表示通過(guò)CPLEX求解得出的最優(yōu)解目標(biāo)函數(shù)值，“T1”表示得到最優(yōu)解所花費(fèi)的計(jì)算時(shí)間(單位/秒)?！癓B”表示通過(guò)列生成啟發(fā)式算法計(jì)算出的原混合整數(shù)規(guī)劃問(wèn)題的下界，“T2”表示得到下界所花費(fèi)的計(jì)算時(shí)間(單位/秒)?！癠B” 表示通過(guò)列生成啟發(fā)式算法計(jì)算得出的原混合整數(shù)規(guī)劃問(wèn)題的近似最優(yōu)解目標(biāo)函數(shù)值，“T3”表示得到近似最優(yōu)解所花費(fèi)的計(jì)算時(shí)間(單位/秒)?！癎AP1”表示精確解與列生成啟發(fā)式算法求解的原混合整數(shù)規(guī)劃問(wèn)題下界之間的差異。“GAP2”表示列生成啟發(fā)式算法求解的原混合整數(shù)規(guī)劃問(wèn)題近似最優(yōu)解與精確解之間的差異。

在表1中，GAP1的平均值為2.80%，GAP2的平均值為0.28%，通過(guò)列生成啟發(fā)式算法求解得出的原混合整數(shù)規(guī)劃問(wèn)題下界和近似最優(yōu)解目標(biāo)函數(shù)值十分接近精確解。這說(shuō)明對(duì)于小規(guī)模算例來(lái)說(shuō)，列生成啟發(fā)式算法可以為原混合整數(shù)規(guī)劃問(wèn)題提供高質(zhì)量的下界和近似最優(yōu)解。T1的平均值為19.25秒，T2的平均值為7.98秒，T3的平均值為8.37。對(duì)于小規(guī)模算例來(lái)說(shuō)，精確求解需要花費(fèi)平均19.25秒，而通過(guò)列生成啟發(fā)式算法可以在10秒內(nèi)為原混合整數(shù)規(guī)劃問(wèn)題計(jì)算出高質(zhì)量的下界與近似最優(yōu)解。小規(guī)模算例的測(cè)試結(jié)果表明，所開(kāi)發(fā)的列生成啟發(fā)式算法性能優(yōu)越。

表1 小規(guī)模算例的求解結(jié)果

精確求解隨著算例規(guī)模的增大，求解時(shí)間呈指數(shù)形式增長(zhǎng)。對(duì)于中等或大規(guī)模算例來(lái)說(shuō)，大多數(shù)算例在短時(shí)間內(nèi)無(wú)法求出精確解。那么可以通過(guò)列生成啟發(fā)式算法求解得出的下界來(lái)評(píng)估啟發(fā)式算法得出的近似最優(yōu)解。為此，本文設(shè)置7200秒為求解時(shí)間閾值，超過(guò)設(shè)定時(shí)間閾值的結(jié)算結(jié)果不在統(tǒng)計(jì)范圍之內(nèi)。表2為中等或大規(guī)模算例的計(jì)算結(jié)果?！癎AP3”表示列生成啟發(fā)式算法求解的原混合整數(shù)規(guī)劃問(wèn)題近似最優(yōu)解目標(biāo)函數(shù)值與下界之間的差異。

在表2中，可以看出，在設(shè)定的求解時(shí)間閾值范圍內(nèi)，中等或大規(guī)模算例利用CPLEX精確求解只能求出部分算例。當(dāng)精確解無(wú)法求出時(shí)，可以利用所開(kāi)發(fā)的列生成啟發(fā)式算法求解問(wèn)題近似最優(yōu)解。GAP3的平均值為0.64%，表明所開(kāi)發(fā)的列生成啟發(fā)式算法求出的近似最優(yōu)解與下界之間差異很小。T2的平均值為211.32秒，T3的平均值為501.87秒。相對(duì)于用CPLEX精確求解來(lái)說(shuō)，所開(kāi)發(fā)的列生成啟發(fā)式算法求解效率較高。

表2 中等或大規(guī)模算例計(jì)算結(jié)果

4 結(jié)論

文章提出一種考慮訂單合并和貨物轉(zhuǎn)運(yùn)的多式聯(lián)運(yùn)路徑優(yōu)化問(wèn)題，在給定的多式聯(lián)運(yùn)網(wǎng)絡(luò)中，運(yùn)輸工具容量和可提供運(yùn)輸工具的最大數(shù)量有限，以總的運(yùn)輸成本(固定運(yùn)輸成本、可變運(yùn)輸成本和轉(zhuǎn)運(yùn)成本)最小化為目標(biāo)，將一組具有不同起終點(diǎn)的運(yùn)輸訂單，在滿足訂單時(shí)間窗要求的情況下，將貨物從各自的起點(diǎn)運(yùn)往終點(diǎn)。為了獲得運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)效應(yīng)，將訂單進(jìn)行合并運(yùn)輸。針對(duì)該問(wèn)題，構(gòu)建了混合整數(shù)規(guī)劃模型并根據(jù)問(wèn)題性質(zhì)轉(zhuǎn)化模型。為了快速求解模型，開(kāi)發(fā)了一種基于列生成的啟發(fā)式算法。通過(guò)大量算例測(cè)試，結(jié)果表明所開(kāi)發(fā)的列生成啟發(fā)式算法在很短的時(shí)間內(nèi)為原混合整數(shù)規(guī)劃模型提供了高質(zhì)量的近似最優(yōu)解。對(duì)于在某個(gè)時(shí)刻面對(duì)大量運(yùn)輸訂單的零擔(dān)物流企業(yè)，該啟發(fā)式算法能夠在較短的時(shí)間內(nèi)為企業(yè)提供高質(zhì)量的近似最優(yōu)解、提高企業(yè)決策效率和節(jié)省運(yùn)輸成本。

本文研究仍然有不足之處，研究問(wèn)題僅以總運(yùn)輸成本為最小化目標(biāo)。在物流運(yùn)輸過(guò)程中，時(shí)間也是重要的因素。在未來(lái)的研究中，可以考慮以運(yùn)輸成本最小化和運(yùn)輸時(shí)間最小化的雙目標(biāo)優(yōu)化問(wèn)題。