基于最大熵的多式聯運終端集運點選址優化

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

（1.中鐵長江交通設計集團有限公司,重慶 401121; 2.重慶交通大學 交通運輸學院,重慶 400074）

0 引言

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

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

通過對已有文獻的梳理可知，各位學者針對多式聯運終端集運點選址—分配問題從數學模型、求解算法等視角進行了一系列研究，普遍采用的是傳統的混合整數規劃模型，忽略了模型中可能出現的面對未來需求不確定導致最優解發生偏差等問題。有學者注意到將最大熵原理運用到多式聯運終端集運點選址問題中[5]，綜合考慮了運輸成本和終端固定成本，但未考慮多式聯運終端集運點租金成本，未解決集運點多個、運輸方式多樣、終端離散分布的擴展問題。基于此，該文借鑒最大熵原理，研究了某城市區域內多貨源點時，如何選擇合適的集運點以及如何分配將貨源點的貨物給相應的集運點，使運輸成本（直達運輸成本和轉運成本）和租金成本最低的問題。該問題的解決方法既能滿足多貨源點物流轉運系統實際需求，又能彌補傳統單一公路運輸的不足，并提高物流轉運效率，從而增加鐵路—水路—公路運輸模式的靈活性。

1 多式聯運終端集運點選址問題建模

1.1 問題描述

某城市貨源點的貨物通過公路直接運輸到多式聯運起運地成本較高，為提高運輸效率和降低運輸成本，考慮建立多式聯運終端集運點來緩解運輸壓力，從而多個貨源點的貨可以一部分直接運到目的地。另外一部分先運到集運點，然后以更大運量的鐵路系統或水路系統運到多式聯運起運地。該問題的網絡結構可描述為三層：1個目的地、T個集運點和O個貨源點。

1.2 模型假設

（1）貨源點、候選集運點和目的地位置已知。

（2）貨源點的運輸量已知，并且都能運送到目的地。

（3）多式聯運中轉成本和直達運輸成本已知。

（4）總貨物運輸預算已知。

（5）候選集運點的單位面積租金成本已知。

（6）經過集運點轉運的貨物量不能超出集運點的最大處理能力。

（7）貨源點的貨可經過多個集運點中轉。

1.3 符號說明

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

1.4 數學模型

目標函數為：

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

式（1）由兩部分組成，第一部分是不經過集運點和經過集運點的運輸成本，第二部分是集運點的場地租金成本。

約束條件為：

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

式中，p0——可允許選擇的最大集運點數量，式（3）表示實際建立的集運點數量不超過允許選擇的最大集運點數量。

式中，bt——集運點t的最大處理量，式（4）表示通過多式聯運集運點的貨物運量不超過集運點每月處理的最大數量。

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

1.5 模型轉化

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

為了將最大熵原理應用于該文的問題，首先必須明確系統可能的狀態，在該文中所有可能的狀態為：直達運輸貨運量和使用集運點多式聯運貨運量。一般地，數學中系統可能存在的狀態數量被定義為：

式中，E——系統可能的狀態數量；Q——貨源區域內貨物總量，根據最大熵原理，目標是使E最大限度地滿足多式聯運集運點服務系統。滿足lnE最大化的Xitj的取值同樣會使E最大化，考慮到lnE的求解更加容易，所以可將問題轉化為將lnE最大化，因此將式（7）重新定義為：

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

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

命題1 如果多式聯運系統中每個貨源節點的需求為Qr(r∈N)，則相應的概率定義為：

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

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

運用斯特林公式的近似結果可得：

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

命題2 在多式聯運系統其他信息未知的情況下，式（14）中的概率分布滿足均勻分布：

相應的熵可以表示為：

其中，n為集合N的基數。

命題3 熵或缺失信息量（H）的概率分布與任何已知關于多式聯運系統的信息量不能超過式（16）中的熵，即：

綜上所述，最大熵的目標函數可以簡化為經過與不經過集運點運輸成本之和，將斯特林公式的近似值應用于式（8），得到：

將末端物流系統集運總成本添加為約束（18），其中第一部分是經過與不經過集運點運輸成本，第二部分是集運點的場地租金成本，其總費用不超過預算總額C：

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

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

2 求解算法

2.1 MEFLP問題分解

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

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

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

式（23）為FLP問題目標函數，其約束包括約束（4）和（6）。

式（24）為MCP問題目標函數，其約束包括約束（3）和（7）。

2.2 FLP子問題求解

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

2.3 MCP子問題求解

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

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

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

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

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

2.4 MEFLP問題綜合求解

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

3 算例分析

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

圖1 最佳集運點的位置

從計算結果可以看出：

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

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

（3）優化結果未出現木耳、南彭與走馬的原因分析如下：木耳集運點離果園港較近，從成本角度考慮，與直達運輸區別較小；南彭集運點為公路運輸，不適宜大運量的貨物進行中轉；走馬集運點也為公路運輸，與團結村集運點距離較近。但相比較而言，團結村和珞璜分別為鐵路運輸和水路運輸，更具有選擇優勢。

4 結論

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

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

（1）考慮多貨源點多目的地設施選址—模式分配問題，實際問題中往往存在多個貨物運輸的目的地，從而滿足不同的需求和經濟效益。

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