基于最大熵的多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)選址優(yōu)化

張 博,黃 靜,張永輝,彭 勇

（1.中鐵長江交通設(shè)計集團(tuán)有限公司,重慶 401121; 2.重慶交通大學(xué) 交通運(yùn)輸學(xué)院,重慶 400074）

0 引言

隨著區(qū)域一體化進(jìn)程加速，內(nèi)陸—港口的貨物數(shù)量急劇增長，刺激了中長距離貨物運(yùn)輸企業(yè)的蓬勃發(fā)展。然而，傳統(tǒng)的單一運(yùn)輸方式不足以滿足大面積、長距離的貨物運(yùn)輸需求，為此采用多式聯(lián)運(yùn)方式彌補(bǔ)傳統(tǒng)單一運(yùn)輸方式的不足，相互銜接完成貨物運(yùn)輸。在此背景下，多式聯(lián)運(yùn)終端集運(yùn)有利于提高貨物運(yùn)輸效率、解決交通擁堵和環(huán)境污染等一系列問題。因此，建設(shè)多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)具有較大的理論意義和應(yīng)用價值。

從承運(yùn)人角度，考慮貨物從多個備選的多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)選擇最佳位置中轉(zhuǎn)可歸納為多式聯(lián)運(yùn)終端選址 — 分配問題（Inter-modal Terminal Location Problems，IMTLP），這一問題是經(jīng)典的樞紐設(shè)施選址問題（Hub Facility Location Problems，HFLP）的擴(kuò)展。Arnold 等[1]在樞紐設(shè)施選址問題的基礎(chǔ)上研究了多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)選址問題，給出了具有固定成本和無限容量的p-hub中值問題的擴(kuò)展形式。Sorensen等[2]針對多式聯(lián)運(yùn)終端選址問題模型，設(shè)計了元啟發(fā)式算法、貪婪隨機(jī)自適應(yīng)搜索算法（GRASP）和基于屬性的爬山算法（ABHC）進(jìn)行求解。Lin等[3]通過4個特征將IMTLP和HFLP區(qū)分，基于Sorensen的研究思路，提出了一種改進(jìn)的混合整數(shù)規(guī)劃模型，并研究了兩種近似最優(yōu)解的數(shù)學(xué)求解方法。Lin等[4]將多式聯(lián)運(yùn)終端的選址與貨物分配分離開來，改進(jìn)了混合整數(shù)線性規(guī)劃模型，并采用兩階段規(guī)劃方法進(jìn)行求解。針對目前多式聯(lián)運(yùn)終端選址問題模型的研究，大多數(shù)學(xué)者都是基于混合整數(shù)線性規(guī)劃模型（Mixed Integer Linear Programming，MILP）。

通過對已有文獻(xiàn)的梳理可知，各位學(xué)者針對多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)選址—分配問題從數(shù)學(xué)模型、求解算法等視角進(jìn)行了一系列研究，普遍采用的是傳統(tǒng)的混合整數(shù)規(guī)劃模型，忽略了模型中可能出現(xiàn)的面對未來需求不確定導(dǎo)致最優(yōu)解發(fā)生偏差等問題。有學(xué)者注意到將最大熵原理運(yùn)用到多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)選址問題中[5]，綜合考慮了運(yùn)輸成本和終端固定成本，但未考慮多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)租金成本，未解決集運(yùn)點(diǎn)多個、運(yùn)輸方式多樣、終端離散分布的擴(kuò)展問題?；诖?，該文借鑒最大熵原理，研究了某城市區(qū)域內(nèi)多貨源點(diǎn)時，如何選擇合適的集運(yùn)點(diǎn)以及如何分配將貨源點(diǎn)的貨物給相應(yīng)的集運(yùn)點(diǎn)，使運(yùn)輸成本（直達(dá)運(yùn)輸成本和轉(zhuǎn)運(yùn)成本）和租金成本最低的問題。該問題的解決方法既能滿足多貨源點(diǎn)物流轉(zhuǎn)運(yùn)系統(tǒng)實際需求，又能彌補(bǔ)傳統(tǒng)單一公路運(yùn)輸?shù)牟蛔悖⑻岣呶锪鬓D(zhuǎn)運(yùn)效率，從而增加鐵路—水路—公路運(yùn)輸模式的靈活性。

1 多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)選址問題建模

1.1 問題描述

某城市貨源點(diǎn)的貨物通過公路直接運(yùn)輸?shù)蕉嗍铰?lián)運(yùn)起運(yùn)地成本較高，為提高運(yùn)輸效率和降低運(yùn)輸成本，考慮建立多式聯(lián)運(yùn)終端集運(yùn)點(diǎn)來緩解運(yùn)輸壓力，從而多個貨源點(diǎn)的貨可以一部分直接運(yùn)到目的地。另外一部分先運(yùn)到集運(yùn)點(diǎn)，然后以更大運(yùn)量的鐵路系統(tǒng)或水路系統(tǒng)運(yùn)到多式聯(lián)運(yùn)起運(yùn)地。該問題的網(wǎng)絡(luò)結(jié)構(gòu)可描述為三層：1個目的地、T個集運(yùn)點(diǎn)和O個貨源點(diǎn)。

1.2 模型假設(shè)

（1）貨源點(diǎn)、候選集運(yùn)點(diǎn)和目的地位置已知。

（2）貨源點(diǎn)的運(yùn)輸量已知，并且都能運(yùn)送到目的地。

（3）多式聯(lián)運(yùn)中轉(zhuǎn)成本和直達(dá)運(yùn)輸成本已知。

（4）總貨物運(yùn)輸預(yù)算已知。

（5）候選集運(yùn)點(diǎn)的單位面積租金成本已知。

（6）經(jīng)過集運(yùn)點(diǎn)轉(zhuǎn)運(yùn)的貨物量不能超出集運(yùn)點(diǎn)的最大處理能力。

（7）貨源點(diǎn)的貨可經(jīng)過多個集運(yùn)點(diǎn)中轉(zhuǎn)。

1.3 符號說明

其中，O為貨源點(diǎn)集合（i∈O），D為目的地集合（j∈D），T為備選集運(yùn)點(diǎn)集合（t∈T），J為虛擬集運(yùn)點(diǎn)集合，表示直達(dá)運(yùn)輸（{0}），K為實際選擇的集運(yùn)點(diǎn)集合（K?T），M為備選集運(yùn)點(diǎn)和虛擬集運(yùn)點(diǎn)集合的并集（J∪T），R為實際選擇的集運(yùn)點(diǎn)和虛擬集運(yùn)點(diǎn)集合的并集（J∪K），N={(i,t,j)i∈O;t∈M;j∈D}，其中集合N的基數(shù)為n。

1.4 數(shù)學(xué)模型

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

式中，citj——從貨源點(diǎn)i經(jīng)集運(yùn)點(diǎn)t到目的地樞紐j的貨物中轉(zhuǎn)運(yùn)輸成本；Xitj——決策變量，從貨源點(diǎn)i經(jīng)集運(yùn)點(diǎn)t到目的地樞紐j的貨物運(yùn)輸量（TEU/月），若t為虛擬集運(yùn)點(diǎn)，則為直運(yùn)量；αt——集運(yùn)點(diǎn)t的單位面積租金成本；st——集運(yùn)點(diǎn)t的面積；yt——決策變量，在t處選擇并使用集運(yùn)點(diǎn)取值為1，否則為0。

式（1）由兩部分組成，第一部分是不經(jīng)過集運(yùn)點(diǎn)和經(jīng)過集運(yùn)點(diǎn)的運(yùn)輸成本，第二部分是集運(yùn)點(diǎn)的場地租金成本。

約束條件為：

式中，qij——從貨源點(diǎn)i到目的地樞紐j的總貨物運(yùn)輸量，式（2）表示對于每個起點(diǎn)—終點(diǎn)對，不經(jīng)過集運(yùn)點(diǎn)和經(jīng)過集運(yùn)點(diǎn)的貨物數(shù)量的和等于從貨源點(diǎn)—目的地樞紐的總貨物運(yùn)輸量。

式中，p0——可允許選擇的最大集運(yùn)點(diǎn)數(shù)量，式（3）表示實際建立的集運(yùn)點(diǎn)數(shù)量不超過允許選擇的最大集運(yùn)點(diǎn)數(shù)量。

式中，bt——集運(yùn)點(diǎn)t的最大處理量，式（4）表示通過多式聯(lián)運(yùn)集運(yùn)點(diǎn)的貨物運(yùn)量不超過集運(yùn)點(diǎn)每月處理的最大數(shù)量。

式（5）表示決策變量的取值為0或1；式（6）是非負(fù)約束，表示貨物運(yùn)量取正值。

1.5 模型轉(zhuǎn)化

最大熵原理是在滿足已知信息的前提下，對未知信息不做任何假設(shè)，而是考慮未知信息所有可能發(fā)生的狀態(tài)，即對于未知概率事件，當(dāng)作等概率事件來處理。

為了將最大熵原理應(yīng)用于該文的問題，首先必須明確系統(tǒng)可能的狀態(tài)，在該文中所有可能的狀態(tài)為：直達(dá)運(yùn)輸貨運(yùn)量和使用集運(yùn)點(diǎn)多式聯(lián)運(yùn)貨運(yùn)量。一般地，數(shù)學(xué)中系統(tǒng)可能存在的狀態(tài)數(shù)量被定義為：

式中，E——系統(tǒng)可能的狀態(tài)數(shù)量；Q——貨源區(qū)域內(nèi)貨物總量，根據(jù)最大熵原理，目標(biāo)是使E最大限度地滿足多式聯(lián)運(yùn)集運(yùn)點(diǎn)服務(wù)系統(tǒng)。滿足lnE最大化的Xitj的取值同樣會使E最大化，考慮到lnE的求解更加容易，所以可將問題轉(zhuǎn)化為將lnE最大化，因此將式（7）重新定義為：

lnE的最大值對應(yīng)于缺失信息量（或不確定性或熵）在概率分布構(gòu)造中的應(yīng)用，因此缺失信息量（H）得到的概率分布為：

其中，lnE*是lnE的最大值，式（9）可由以下命題得證。

命題1 如果多式聯(lián)運(yùn)系統(tǒng)中每個貨源節(jié)點(diǎn)的需求為Qr(r∈N)，則相應(yīng)的概率定義為：

式中，Pr表示概率，則等式（8）可表示為：

證明1根據(jù)定義，式（8）可寫為：

運(yùn)用斯特林公式的近似結(jié)果可得：

綜合式（10）和（13），可以得出：

命題2 在多式聯(lián)運(yùn)系統(tǒng)其他信息未知的情況下，式（14）中的概率分布滿足均勻分布：

相應(yīng)的熵可以表示為：

其中，n為集合N的基數(shù)。

命題3 熵或缺失信息量（H）的概率分布與任何已知關(guān)于多式聯(lián)運(yùn)系統(tǒng)的信息量不能超過式（16）中的熵，即：

綜上所述，最大熵的目標(biāo)函數(shù)可以簡化為經(jīng)過與不經(jīng)過集運(yùn)點(diǎn)運(yùn)輸成本之和，將斯特林公式的近似值應(yīng)用于式（8），得到：

將末端物流系統(tǒng)集運(yùn)總成本添加為約束（18），其中第一部分是經(jīng)過與不經(jīng)過集運(yùn)點(diǎn)運(yùn)輸成本，第二部分是集運(yùn)點(diǎn)的場地租金成本，其總費(fèi)用不超過預(yù)算總額C：

忽略最大熵函數(shù)中的常數(shù)項lnQ!，則由基本的熵公式推導(dǎo)出了最大熵設(shè)施選址問題（MEFLP）模型為：

式中，Λe表示函數(shù)，約束為（2）～（6）和（19）。

2 求解算法

2.1 MEFLP問題分解

MEFLP問題是典型的NP問題，很難尋找到一個最優(yōu)解。因此，嘗試將該問題分成兩個子問題分別求解，這通過放松MEFLP問題的約束（4）和（19）實現(xiàn)。

約束為（2）、（3）、（4）、（5）、（6）和（19）。

式（22）中，ψt＞ 0 ,?t∈M;β＞0分別表示集運(yùn)點(diǎn)處理能力和預(yù)算約束的拉格朗日乘數(shù)，目標(biāo)函數(shù)包括兩部分成本（運(yùn)輸成本和場地租金成本），并且容量約束（18）是一個強(qiáng)制約束，為了解決寬松約束的MEFLP問題，將其分解為兩個子問題，即設(shè)施選址子問題（FLP）和模式分配子問題（MCP）。

式（23）為FLP問題目標(biāo)函數(shù)，其約束包括約束（4）和（6）。

式（24）為MCP問題目標(biāo)函數(shù)，其約束包括約束（3）和（7）。

2.2 FLP子問題求解

成本敏感性參數(shù)β是集運(yùn)點(diǎn)變量yt的函數(shù)，反之亦然，如果參數(shù)ψt,β已知，則假定yt為1的前提下，就可以求解FLP問題。

2.3 MCP子問題求解

命題4 （存在性）。假設(shè)集合K是已知的，如果MCP問題的可行解S是由約束（3）（4）（6）（7）和（13）共同決定的，即：

那么在集合S中至少存在MCP問題的一個解。

命題5 （唯一性）。如果集合S中存在MCP問題的解，那么這個解一定是唯一存在的。

命題4和命題5保證了MCP問題解的存在性和唯一性，可以構(gòu)造一個拉格朗日方程，對于給定的預(yù)算C，可以得出與約束（18）相關(guān)的拉格朗日參數(shù)β（成本敏感性參數(shù)）如下：

函數(shù)Φ（β）是連續(xù)且對于參數(shù)β可微，因此，參數(shù)β的求解可以采用牛頓拉夫森方法。

2.4 MEFLP問題綜合求解

MEFLP問題被分解為子問題，子問題可精確求解，目前存在的求解方法例如分支定界、拉格朗日啟發(fā)式算法或完全枚舉法等可以解決中小型實例問題。

3 算例分析

為了驗證模型和算法的有效性和合理性，以重慶市主城區(qū)和周邊區(qū)縣的貨源點(diǎn)到果園港碼頭一個月內(nèi)的物流數(shù)據(jù)為例構(gòu)建算例，根據(jù)該文提出的模型及方法，可得到圖1所示的最佳集運(yùn)點(diǎn)的分布示意圖。

圖1 最佳集運(yùn)點(diǎn)的位置

從計算結(jié)果可以看出：

（1）在只允許選擇一個集運(yùn)點(diǎn)考慮或者不考慮租金成本的情況下，最佳為集運(yùn)點(diǎn)2（即團(tuán)結(jié)村）；在允許選擇多個集運(yùn)點(diǎn)考慮或不考慮租金成本情況下，最佳為集運(yùn)點(diǎn)2和3（即團(tuán)結(jié)村和珞璜）；可見案例中租金成本對選擇最佳集運(yùn)點(diǎn)的影響不大，這主要是因為5個備選集運(yùn)點(diǎn)的租金成本相差不大，對總成本的影響甚微；且合理建設(shè)多個集運(yùn)點(diǎn)可以實現(xiàn)更多成本節(jié)約，提高轉(zhuǎn)運(yùn)效率。

（2）在兩個集運(yùn)點(diǎn)情況下，不同貨源點(diǎn)通過集運(yùn)點(diǎn)中轉(zhuǎn)流量均增大，整個貨運(yùn)中轉(zhuǎn)流量由58%增為71%，成本敏感性參數(shù)β由 0.002 100 062 降為 0.001 291 056，說明β減小時式中更多貨物總量被分配到更大運(yùn)量的運(yùn)輸模式，即采用鐵路或水路中轉(zhuǎn)的方式進(jìn)行運(yùn)輸，從而整個系統(tǒng)的中轉(zhuǎn)流量增加，而參數(shù)ψ2和ψ2,3都為0，主要原因是貨運(yùn)總需求小于其集運(yùn)點(diǎn)的最大處理能力。

（3）優(yōu)化結(jié)果未出現(xiàn)木耳、南彭與走馬的原因分析如下：木耳集運(yùn)點(diǎn)離果園港較近，從成本角度考慮，與直達(dá)運(yùn)輸區(qū)別較??；南彭集運(yùn)點(diǎn)為公路運(yùn)輸，不適宜大運(yùn)量的貨物進(jìn)行中轉(zhuǎn)；走馬集運(yùn)點(diǎn)也為公路運(yùn)輸，與團(tuán)結(jié)村集運(yùn)點(diǎn)距離較近。但相比較而言，團(tuán)結(jié)村和珞璜分別為鐵路運(yùn)輸和水路運(yùn)輸，更具有選擇優(yōu)勢。

4 結(jié)論

為解決多貨源點(diǎn)多集運(yùn)點(diǎn)設(shè)施選址—模式分配問題，該文構(gòu)建了以運(yùn)輸成本和集運(yùn)點(diǎn)租金成本最小為目標(biāo)的混合整數(shù)規(guī)劃模型，將最大熵方法應(yīng)用于該文的問題，解決了模型中可能出現(xiàn)的面對未來需求不確定導(dǎo)致最優(yōu)解發(fā)生偏差等問題，并使用拉格朗日松弛方法將問題分解為兩個子問題，即設(shè)施選址子問題（FLP）和模式分配子問題（MCP），最后采用完全枚舉法結(jié)合具體算例進(jìn)行求解。結(jié)果表明：選擇以鐵路運(yùn)輸為主的團(tuán)結(jié)村集運(yùn)點(diǎn)和以水路為主的珞璜集運(yùn)點(diǎn)總成本較少，符合實際運(yùn)輸情況。

該文可根據(jù)建立的模型有效解決多貨源點(diǎn)多集運(yùn)點(diǎn)設(shè)施選址—模式分配問題，但仍存在不足，可在后續(xù)的研究中進(jìn)一步討論，主要包括：

（1）考慮多貨源點(diǎn)多目的地設(shè)施選址—模式分配問題，實際問題中往往存在多個貨物運(yùn)輸?shù)哪康牡?，從而滿足不同的需求和經(jīng)濟(jì)效益。

（2）考慮算法的優(yōu)化，當(dāng)實際問題規(guī)模較大、條件更復(fù)雜時，完全枚舉法已不能滿足求解需要，可嘗試采用智能優(yōu)化算法提高求解效率。