基于網絡單純形法的海運集裝箱空箱調運研究＊

黃純輝 張慶年 周興建 劉春玲

（武漢理工大學交通學院1） 武漢 430063） （武漢紡織大學供應鏈系統研究中心2） 武漢 430073）

集裝箱空箱運輸產生的本質是由于貨物運輸的不平衡，所以，不同的港口對于集裝箱空箱的需求量就不一樣，集裝箱空箱的存在，不僅有運輸成本問題，而且還存在港口庫存問題，所以，對于集裝箱班輪公司而言，海運集裝箱的合理調配既是滿足公司正常運輸生產的需要，也是在集裝箱班輪運輸市場上同競爭對手競爭的需要［1］.

本文結合海運集裝箱調運的現狀，以集裝箱空箱運輸成本最低的思想，建立相應的模型，對目前海運集裝箱空箱調運過程中成本居高不下的實際問題進行理論上的探索.

1 國內外相關研究

1.1 國內關于集裝箱空箱調運的研究

施欣［2］結合對集裝箱海運空箱調運過程的剖析，建立了相應的系統優(yōu)化模型，進行了系統仿真.劉恒江等［3］以航線經營人為主體，對集裝箱空箱調運系統（CAE－CS）進行了分析，構建空箱調運的Petri網模型，然后利用EXSPECT仿真軟件進行模擬仿真，證明利用Petri網分析和解決空箱調運問題的有效性.周紅梅等［4］借鑒了鐵路空車調度優(yōu)化模型的研究，建立了海運集裝箱空箱調運優(yōu)化模型.劉大镕等［5］構造了基于機會約束規(guī)劃的陸上空箱調運模型，把需求分為確定性需求和隨機性需求，從而考慮了需求的不確定性，并提出了在單箱情況下處理不確定數據的有效方法，但該文把空箱供給看作一個已知量，從而消除了空箱供給的不確定性.

1.2 國外關于集裝箱空箱調運的研究

Cranic等［6］描述了這類問題的基本結構和主要特點；接著提出了2個單箱種和多箱種的動態(tài)確定性模型，為這類問題提供了一般的建?？蚣?；最后在此基礎上提出了單箱種情況下處理供給和需求不確定性的數學模型.White［7］首先利用運輸規(guī)劃理論開展空載運輸工具優(yōu)化調配研究.他們通過構造一個空間時間模型來描述現實中的集裝箱空箱調運問題，并給出了誘導式網絡流算法及相應的計算例子，對時間段內的空箱調運方案進行優(yōu)化，其時間間隔是不確定的，研究的結論是非?？扇〉?

2 基本模型

2.1 模型的構建

令O（k），k∈K代表起運地的集裝箱空箱k，其中K為不同類型的集裝箱空箱；D（k），k∈K為目的地的集裝箱空箱k；T（k），k∈K為轉運地集裝箱空箱k，i∈O（k），k∈K，集裝箱碼頭i對集裝箱空箱k供應量，i∈D（k），表示集裝箱碼頭i對集裝箱空箱k的需求量；uij，（i，j）∈A為弧（i，j）的容量（即弧（i，j）能承擔的最大運量），（i，j）∈A為在?。╥，j）集裝箱空箱k的最大運量；變量，（i，j）∈A，k∈K為集裝箱空箱k在?。╥，j）的運量；），（i，j）∈A，k∈K為?。╥，j）運輸單位流量集裝箱空箱k的成本.

多種集裝箱空箱最小成本的模型

目標函數（1）是總的費用，約束條件（2）是對集裝箱碼頭i∈V和每一類貨物k∈K的運量限制.約束條件（3）表示每一類貨物k∈K通過每一條弧（i，j）的流量不超過容量.約束條件（4）（流量約束），表示對于每一條?。╥，j）∈A，通過弧（i，j）的總運量不大于運量.

對于任意的，k∈K，i∈O（k）和，滿足下面的條件

否則問題是行不通的.

雖然集裝箱有不同的類別，但是班輪公司使用的集裝箱大部分仍然是普通集裝箱，又稱干貨集裝箱（dry container）以裝運件雜貨為主，通常用來裝運文化用品、日用百貨、醫(yī)藥、紡織品、工藝品、化工制品、五金交電、電子機械、儀器及機器零件等.這種集裝箱占集裝箱總數的80%以上［8］.鑒于此，在實際應用中，構建單集裝箱空箱線性最小成本流模型.根據上述多種集裝箱空箱線性最小成本流的原理，構建下面單集裝箱空箱線性最小成本流問題模型，同時，為了便于后面相關算例的驗證，模型必須滿足如下假設.

假設1 相同航線上幾家獨立的集裝箱班輪公司，在航線和航期表固定、一定計劃周期內所有航班都正好完成1次運輸、每航次的貨船容量（即重箱運輸量）已知的情形下，開展單箱種（20ft）空箱的調運.

假設2 計劃期開始時各港口空箱的供給量和需求量已知，且據此可確定本期的供給港和需求港.

假設3 當客戶對空箱的需求僅僅依靠調運已不能滿足時，班輪公司將從集裝箱租賃公司租用空箱，這些空箱在任何時間、任何港口都沒有數量限制，并且能夠即刻得到.

假設4 班輪公司在各航線上的空箱運輸費率、在各港口的租箱費等成本參數已知.所假設公司各方面情況接近且計劃期長度有限.因此認為在特定港口的同一計劃期內租箱費用相同、恒定.

集裝箱空箱線性最小成本流問題模型，可以通過網絡單純形算法或其它的線性規(guī)劃算法來求解.

2.2 網絡單純形法算法步驟

步驟1找到一個初始的基本合適的結果x（0）.設h＝0.

步驟2確定與x（h）相關的減少成本cr（h）.

步驟3如果≥0，（i，j）∈A，停止運算，x（h）就是最優(yōu)的結果；否則，選擇變量xvw使xr（h）vw＜0.

步驟4從基礎變量中選擇一個變量xpq，是xpq作為替代xvw的中間變量；令h＝h＋1，返回步驟2.

3 算 例

某公司是一多試聯運承運人，當客戶將貨物從起運地運至目的地時，該公司提供一個或多個空集裝箱來裝貨.一旦到達目的地，貨物卸下，空箱運至新接貨點的客戶.該公司的管理只需要周期性的重新分配空集裝箱（實際中是1周1次）.空箱的運輸費用是很高的（是總的運作費用的35%）.幾十個空的20ft的標箱需要在港口1、港口2、港口3、港口4、港口5、港口6、港口7進行調運.各個碼頭的空集裝箱的數量和需要的數量和運費，見圖1.

圖1 空箱問題的代表圖

圖2 某公司空箱分配問題的最優(yōu)解

基于運用網絡單純形法的理論，結合lingo數據包的計算，最優(yōu)的結果可以在圖2中獲得，圖中虛線部分表示沒有集裝箱空箱運輸，實線部分表示有空箱運輸.具體的空箱流見表1.可以明晰的看出各種港口之間集裝箱空箱的流量.根據各港口之間的空箱流，可以得出最優(yōu)解是3 900，即最小運輸成本是3 900.

表1 某公司集裝箱空箱分配問題的求解值TEU

4 結束語

基于網絡線性規(guī)劃的海運集裝箱空箱調運優(yōu)化模型，解決了集裝箱班輪運輸公司在不同的時期內，在不同的港口之間集裝箱空箱的調運成本最低的問題，所以其也是基于時間延遲的動態(tài)模型，本文建立了多種集裝箱空箱的調運成本最低的模型，所列舉的算例驗證了同一種集裝箱空箱調運成本最低的優(yōu)化模型，雖然做了一定的簡化處理，但是仍能證明海運集裝箱空箱調運優(yōu)化定量分析的可操作性.

［1］Crainic T G.Long－h(huán)aul freight transportation，In：hall，R.W（Ed.）［M］.Handbook of Transportation Science，Kluwer Academic Publishers，Norwell，MA，2003.

［2］施 欣.集裝箱海運空箱調運優(yōu)化分析［J］.系統工程理論與實踐，2003，23（4）：70－89.

［3］劉恒江，施 欣.基于Petri網的集裝箱空箱調運仿真分析［J］.交通運輸工程學報，2002，2（3）：97－102.

［4］周紅梅，方 芳.航運集裝箱空箱調運優(yōu)化模型的研究［J］.武漢理工大學學報：交通科學與工程版，2003，27（3）：384－387.

［5］劉大镕，賀 斌，蔣良奎，等.隨機（單箱種）陸上空箱調運模型［J］.上海海運學報，2000（3）：8－18.

［6］Cranic T G，Gendreau M，Dejax P.Dynamic and stochastic models for the allocation of empty container［J］.Operations Research，1993，41（1）：102－126.

［7］White W W，Bomberawlt A M A.Network algorithm for empty freight car allocation［J］.IBM System Journal，1969，15（2）：147－16.

［8］史艷秋.迅速發(fā)展的中國集裝箱工業(yè)［J］.鐵道貨運，2005（11）：11－14.