物流運輸優化問題的線性規劃模型構建

楊自輝 ，符 卓

（1.中南大學 交通運輸工程學院，長沙410075；2.長沙師范學院，長沙 410100）

0 引言

車輛路徑問題是一個非常有挑戰性的組合優化問題，合理的車輛路徑規劃，能有效地降低服務商運作成本，提高服務質量，因此車輛調度優化問題很快成為研究的熱點。多式聯運的車輛運輸問題屬于典型的多目標函數優化問題——既要追求經濟實惠，又要力保高效迅速。

王鳳洲等（2005）認為多式聯運系統是基于系統整合觀和供應鏈思想以及現代信息技術的多種運輸方式的最佳組合，具有自身的特點和獨特的系統特征,相對于傳統的運輸模式來說,是一個革命性的突破,從根本上區別于傳統的物質運輸模式。蔣洋等（2012）提出了針對“多式聯運運輸方案選擇問題”的一種全新的交叉熵算法,并據此給出了相應的計算方法。采用具有節點擴展特性的“網絡圖”對多式聯運網絡進行詳細的描述,進而轉化為“最短路問題”進行求解。結果顯示,運輸成本、轉運費用對運輸方案具有很重要的決定作用,并且提出的交叉熵算法具有很快收斂的性質。馮芬玲,張清雅（2012）綜合考慮環境污染等諸多因素對“多式聯運”可持續發展的影響效應,引入多式聯運社會總成本的概念,以“多式聯運社會總成本最小化”為整體優化目標,建立多式聯運運輸方式協同優化模型。分別采集并處理各種運輸方式的運輸、污染、能源及安全成本數據和運輸數據,并利用模糊綜合評價法確定各個成本的影響權重。結果顯示：在對多式聯運進行決策制定時,應綜合考慮多式聯運的影響因素,選擇合理的運輸方式。馬彩雯,孫光圻（2006）為了在國際多式聯運信息集成的基礎上,實現對國際多式聯運的運輸組織過程的集成管理和協同運作，利用Agent技術,運用一種面向對象的新方法,設計了國際多式聯運“虛擬企業”的信息集成框。孫彬，陳秋雙（2013）針對多式聯運運輸決策中的特點,提出一種基于多Agent的多式聯運承運人選擇和路徑優化方法。結果表明,這一引導機制可以有效加快協商過程的收斂性。雷定猷等（2014）基于可行性與合理性的角度,分析了長大貨物多式聯運路徑優化的影響因素。以“運輸時間最短”、“里程與費用最少”為目標函數,以“線路限界、橋梁承載能力、起重設備的起重能力”為約束條件,建立了長大貨物多式聯運路徑優化原始模型。考慮了約束條件的改造性特征,將原始模型擴展優化,設計了二維序列編碼策略,運用遺傳算法求解擴展模型。

縱觀現有文獻，對于多式聯運運輸優化問題的探討中，并沒有考慮“時間成本”的存在帶來的影響，這樣的分析會帶來一定的計算誤差。在本文所構建的模型中，創造性地通過“權重系數”的銜接，引入“時間成本”的思想，將“時間”量化為“成本”，使得“多決策目標的優化問題”轉化為“古典線性背景下的優化決策問題”。

1 問題的敘述與分析

1.1 問題的一般化敘述

一般化的“物流配送路徑優化”問題可以進行這樣的表述：從物流配送的中心點（又稱為“物流節點”）向多個顧客（又稱為“需求點”）用多輛汽車（決定了本文分析的“路徑數”）送貨。

限制條件為：（1）每輛汽車的載重能力是一定的；（2）具有一定的需求量和需求點位置。

規劃目標：安排合理的汽車路線圖，使運輸總距離最短，運輸花費的總運費最小，并滿足以下限制條件：(1)每個需求點的需求必須滿足；(2)縮短配送時間，降低配送成本。

圖1 整車物流運輸方式

1.2 問題分析

本問題屬于典型的多目標函數優化問題——既要追求經濟實惠，追求成本最小化；又要力保高效迅速，追求時間最小化。目標函數的要求給模型的求解增加了難度，通過一個“時間成本轉換因子”，將時間轉化為成本，這樣就把原來的多目標函數優化問題轉化為單目標函數優化問題了。

（1）運輸資源使用最合理：為了充分運用現有運力資源，物盡其用，而不利用資源體系外的另外車輛，在運力非常緊張、運力與成本或效益有一定相關性的情況下，也可以將運力安排為目標，確定配送路線。

（2）運輸總路程最短：如果運輸成本和路程長短具有較強的相關性，而和其他因素相關性不強時，我們在進行決策時可以選擇“運輸總路程最短”為決策目標。

（3）運輸活動獲得的效益最高：在運輸的實際問題中，我們常常以“企業當下的效益情況”為主要制約因素，同時要考慮到“企業的長遠發展”。

（4）時間效率最高：有時在實際問題的決策過程中，很難同時考慮到“成本”的問題，甚至需要犧牲其余各項成本來滿足“時間效率最高”的苛刻要求，當然，考慮到實際決策問題的制約因素，對“時間效率最高”的要求必須建立在“控制成本最低”的基礎上。

（5）運輸消耗的成本最低：在實際計算過程中，成本的計算并不太容易，但和“以運輸效益為最終決策目標”相比可以簡化問題，采用“最低成本”為決策目標相當于選擇了以“效益最高”為決策目標。

2 物流運輸優化問題的線性規劃模型的建立

2.1 模型的一般描述

假設有一個“多式聯運運輸方式”選擇為具有多個決策目標的優化問題，我們將研究的問題一般化，具體敘述如下：

運輸一批貨物，起始地記為O，目的地記為P，途徑的城市個數為n（n＞2），把兩個城市算作一個“城市對”，那么，每個城市對之間可供選擇的運輸方式有m（m＞1）種，根據排列組合的原理，可知一共有mn-1種交通組合方式。對于這些交通組合方式，如果兩城市間是相鄰的，那么所有運輸方式的時間以及費用都是不相同的，我們還假設當從某一種運輸方式轉變到另一種運輸方式時，需要消耗一定的中轉時間和費用。所以，可以知道本研究問題的關鍵是明確如何選擇運輸方式，實現以下兩個決策目標：（1）運輸費用總成本最小；（2）運輸消耗時間最短。

我們用一個虛擬的“運輸網絡圖”對上述一般化的問題進行具體描述，見圖2所示：

圖2 物流運輸問題的多式聯運描述圖

（1）設始發點為O，終點為P，從事發點到終點途徑的各個城市分別擴展為n個城市節點，如圖所示，任何兩個物流節點之間有m種運輸方式，故在此可以假設每個節點有m條運輸線路流入，也有m條運輸線路流出。如對于節點A，其左側有1個節點O，即物流中心或配送中心，共有n種運輸方式輸入節點，故將A虛擬成m個節點，每個節點分別代表一個流入，同理A右側也有m個節點，A21、A22、A23、…、A2m、分別表示m種運輸方式輸出節點。同理可以將其他物流節點也類似虛擬。

（2）相關符號表示的含義敘述如下：

q：貨物從城市i到城市i+1，選擇第k種運輸方式的運輸量；

W：綜合考慮運輸時間和運輸成本時，運輸時間對運輸成本的單位時間費用權重調整值。

（3）I表示所有要經過的城市的集合。

2.2 物流運輸優化問題的線性規劃模型

在我們上面討論的“多式聯運運輸方式選擇多決策目標的優化問題”中，其目標是要降低運輸總費用，故該問題的線性規劃模型為：

3 結論及模型的推廣應用

在解決多目標函數問題時，通過“時間成本轉換因子”將“具有多個決策目標的優化問題”轉換為“經典的只有單一決策目標的線性規劃問題”，解決了具有多個決策目標優化問題在模型設定時的難點，將模型的決策目標、約束條件一般化、線性化，由此大大降低了模型在求解過程中的難度。本模型的創新之處主要在于提供一種將時間轉化為成本的思想，將“決策目標多樣化的優化問題”轉化為“經典的只有單一決策目標的線性規劃問題”。本文討論得出的模型可以應用于各類關于“多式聯運運輸優化問題”的探討和優化。當然，在模型的實際應用中可視實際情況對于目標函數以及約束條件加以修改限制，用來求解企業實際需要的運輸優化問題。

[1]孫彬，陳秋雙.基于多Agent的多式聯運運輸決策與動態協調[J].計算機集成制造系統，2013，（12）.

[2]雷定猷,游偉,張英貴,皮志東.長大貨物多式聯運路徑優化模型與算法[J].交通運輸工程學報，2014，（1）.

[3]馬彩雯,孫光圻.基于多Agent的國際多式聯運“虛擬企業”信息集成框架[J].大連海事大學學報，2006，（2）.

[4]王鳳洲，陸曉倩，吳秋明.基于系統整合觀的多式聯運系統特征分析[J].系統辯證學學報，2005，（4）.

[5]馮芬玲,張清雅.基于環境的多式聯運運輸方式協同組織優化模型[J].鐵道科學與工程學報，2012，（6）.

[6]蔣洋，張星臣，王永亮.多式聯運運輸方案選擇的交叉熵方法[J].交通運輸系統工程與信息，2012，（5）.