集裝箱多式聯(lián)運組織優(yōu)化模型研究

0多式聯(lián)運的概念,是一個跨為了便于研究和計算，人們主要關注單一的運輸方式。隨著研究的深入、算法的成熟和交通運輸業(yè)形勢的發(fā)展,以及為了充分利用各運輸方式在技術、經濟方面的特點,人們提出了多式聯(lián)運的概念。所謂多式聯(lián)運,就是采用2種以上的運輸方式,實行“一次托運,包干計費,一票到底,全程負責”的連貫運輸。隨著專業(yè)化運輸?shù)陌l(fā)展,分貨類專業(yè)化運輸已成趨勢,港口蓬勃發(fā)展的專業(yè)碼頭,如煤、礦等大宗物資運輸碼頭、集裝箱專業(yè)化運輸碼頭,單貨種多方式聯(lián)運模型將更為實用,本文采用模擬退火遺傳算法對集裝箱多式聯(lián)運系統(tǒng)的優(yōu)化模型和算法進行探討。1基本網(wǎng)絡的構建假設多式聯(lián)運商或代理人準備建立和開發(fā)一條由某地(O)至某地(D)的集裝箱多式聯(lián)運路線,中途可選擇若干個中轉地作為中間節(jié)點,任意相鄰的2個中轉地之間主要有鐵路運輸、公路運輸、水路運輸3種運輸方式可供選擇,并假設:①運量在2個相鄰中轉地之間不能分割,即在某2個特定的中轉地之間,只能選擇1種運輸方式,中轉換裝只在中轉地發(fā)生;②在相鄰的2個城市之間,各種運輸方式的運輸時間、運輸費用不同,每種運輸方式在2個中轉地之間的通過能力足夠大;③當從一種運輸方式轉換到另一種運輸方式時,需要一定的中轉時間和中轉費用。集裝箱多式聯(lián)運系統(tǒng)基本網(wǎng)絡由節(jié)點以及每相鄰2個節(jié)點之間的1條或多條相互平行的連線(每條連線代表1種運輸方式)所組成。定義:N為網(wǎng)絡上所有節(jié)點的集合,K為網(wǎng)絡中所有運輸方式的集合;A為網(wǎng)絡中所有連線集;一個連線a(a∈A)可表示為(i,j,k),其中:i,j∈N,k∈K,i為起始節(jié)點,j為終止節(jié)點,k為i、j間可用的某種運輸方式。1)當不存在不同運輸方式之間的聯(lián)合運輸時,由此形式的集裝箱運輸網(wǎng)絡稱為基本網(wǎng)絡。如一個集裝箱運輸網(wǎng)絡由A、B、C3個節(jié)點組成,可用的運輸方式有3種:公路運輸、鐵路運輸、水路運輸。A、B2節(jié)點間3種方式全部可用,A、C之間有公路、鐵路2種運輸可用,而B、C之間只有公路1種運輸方式。基本路網(wǎng)的描述如圖1所示。用具有方向性的多條相互平行的直線直接連接相鄰的2節(jié)點,每條連線代表1種可能的運輸方式。沒有不同運輸方式之間的聯(lián)合運輸發(fā)生時,基本網(wǎng)絡可以很好地描述每種運輸方式單獨完成其運輸任務的情形。各條直線上權重為廣義運輸費用。廣義運輸費用主要由運輸過程中的運輸費用和時間費用構成。假設從中轉地i到相鄰中轉地j,其運輸距離為li,j,采用第k種運輸方式時,集裝箱的單位運輸費用為fki,jki,j,運輸量為qi,j,則其運輸費用可表示為qi,jli,jfki,jki,j;設運輸時間為tki,jki,j,單位時間內資金的占用耗費率為ρi,j,運輸工具及貨物等的總價值為pi,j,則運輸時間費用為pi,j[(1+ρi,j)tki,j-1],其廣義運輸費用的估計值為Cki,jki,j,則有:Cki,jki,j=qi,jli,jfki,jki,j+[(1+ρi,j)tki,j-1]。2)當存在不同運輸方式之間的聯(lián)合運輸時,要采用多式聯(lián)合運輸方法。要實現(xiàn)多種運輸方式之間的換裝,T為網(wǎng)絡中所有換裝弧集,換裝弧t∈T。則對基本網(wǎng)絡中節(jié)點作如下處理,如圖2所示。假定各種運輸方式之間的銜接只能在節(jié)點(如港口)發(fā)生,則需要對節(jié)點進行擴展,其基本做法是:將發(fā)生換裝的節(jié)點(a),根據(jù)其流入流量(1,2)和流出流量(3,4),分裂成2個流入節(jié)點(a1,a2)和2個流出節(jié)點(a3,a4),并在其間用換裝線相連,從而形成一個由流入節(jié)點和流出節(jié)點2部分組成的換裝擴展節(jié)點,其換裝線代表由一種運輸方式轉為另一種運輸方式,各條弧上的權重為廣義中轉費用。廣義中轉費用主要由中轉過程中的換裝費用(包括裝卸、儲存和其他消耗等直接費用)和時間費用(包括運輸工具(如大型船舶)及貨物等占用延誤時間、耗用和市場風險等間接費用)構成,集裝箱在中轉過程中的可能損失費用(包括損壞、滅失等)可忽略不計。假設在中轉地i,運輸方式由k轉為l時,集裝箱的單位換裝費用為wk,lik,li,換裝量為qi,則換裝費用為qiwk,lik,li;設中轉時間為tk,lik,li,單位時間內資金的占用耗費率為ρi,運輸工具及貨物等的總價值為pi,則中轉時間費用為pi[(1+ρi)tk,li-1],其廣義中轉總費用的估計值為Ck,lik,li,則有:Ck,lik,li=qiwk,lik,li+pi[(1+ρi)tk,li-1]。2線性關系平衡公式對任意一條弧a(a∈A),其費用函數(shù)為Sa(·),每一換裝弧t(t∈T),其費用函數(shù)為St(·)。運輸對象集裝箱由起點O(O∈N)到終點D(D∈N)。定義V為聯(lián)合運輸網(wǎng)絡中集裝箱的流量,V包括弧流Va(a∈A)和換裝流Vt(t∈T)兩部分,即V=[(va)a∈A(vt)t∈Τ]V為一個n=nA+nT維向量。對于一個給定的單位流量來講,設連線廣義運輸費用函數(shù)和中轉地廣義換裝費用函數(shù)分別為Sa(v)和St(v),則集裝箱運輸?shù)膹V義費用函數(shù)可定義為S=[(Sa(v))a∈A(St(v)t∈Τ]S同樣也是一個n=nA+nT維向量。因此,集裝箱對應于連線a的廣義運輸費用為Sa(v)·va,對應于換裝點t的廣義換裝費用為St(v)·vt。所有集裝箱在整個網(wǎng)絡上的廣義總費用函數(shù)為F=∑a∈ASa(v)?va+∑t∈ΤSt(v)?vt=SΤ?V。令ROD為通過有關運輸方式從起點O到終點D的路徑集合,路徑R∈ROD,hR(hR≥0)表示在路徑R上的集裝箱流量,gOD為起點O到終點D的總流量,則流量平衡公式可表示為∑R∈RΟDhR=gΟD。用δaR={1a∈R0a?R來確定弧流與特定路徑流之間的關系,則va=∑R∈RΟDδaRhR,a∈A同理vt=∑R∈RΟDδtRhRt∈Τ?δtR={1t∈R0t?R綜上所述,基于廣義總費用最小化的集裝箱多式聯(lián)運組織優(yōu)化模型可描述如下:minF=∑a∈ASa(v)∑R∈RΟDδaRhR+∑t∈ΤSt(v)∑R∈RΟDδtRhR3群體復制算子的增加由上述對集裝箱多式聯(lián)運網(wǎng)絡分析可知,求解集裝箱多式聯(lián)運廣義運費最小的多式聯(lián)運方案,實質上可轉化為求上述模型的網(wǎng)絡圖最短路徑問題,也是一個典型的組合優(yōu)化問題,只是這里的路段數(shù)值不是通常所指的路段長度大小,而是指采用該路段所代表的某種運輸方式運輸集裝箱所發(fā)生的廣義費用。對于大規(guī)模復雜網(wǎng)絡求解最短路徑問題,運用遺傳模擬退火算法是目前較好的方法之一。遺傳模擬退火算法是遺傳算法與模擬退火算法的結合,改進了遺傳算法的種群選取(即復制算子)運算。具體步驟如下:步驟1選擇問題的一個編碼,給定群體規(guī)模MAXPOP,k=0;初始時溫度:tk=t0,初始群體POP(k)。步驟2若滿足停止規(guī)則,算法終止,把在任一代中出現(xiàn)的最好的染色體作為算法的執(zhí)行結果,并通過解碼得出問題的最終解。步驟3否則,對群體POP(k)中每一個染色體i的鄰域中隨機選取狀態(tài)j∈N(k),按模擬退火算法中的接受概率Aij(tk)=min{1,exp(-f(j)-f(i)tk}接受或拒絕j,若接受,則i=j。式中:f(i)為狀態(tài)i的目標值;這一階段共需MAXPOP次迭代,選出新群體NewPOP1(k+1);tk為當前溫度;f(i)、f(j)為i、j的目標值。步驟4對新群體NewPOP1(k+1)中的每個染色體計算適用值fi(tk)=exp{-f(i)-fmintk}式中:fmin為新群體NewPOP1(k+1)中的最小值。步驟5按適用函數(shù)決定的概率分布從新群體NewPOP1(k+1)中隨機選取MAXPOP個染色體,形成種群體NewPOP2(k+1)。步驟6按遺傳算法的常規(guī)算子方法進行交配得到CrossPOP(k+1);再變異得到MutPOP(t+1)。步驟7降溫退火,tk+1=d(tk)。步驟8k=k+1,POP(k)=MutPOP(k)若達到規(guī)定的最大代數(shù)目,轉入步驟2;否則,轉入步驟3。4各城市之間可采用的運輸方式及裝配費用情況有一批集裝箱,要從A地運送到H地,可選擇的中轉地共有6個:B、C、D、E、F、G,其多式聯(lián)運網(wǎng)絡圖如圖2所示。各城市之間可供選擇的運輸方式及其廣義運輸費用情況如下表1所列,各種運輸方式之間換裝費用情況如表2所列。求解該問題轉化為一個求解最短徑路問題,根據(jù)前述思想和方法,得該問題的最佳運輸徑路和最佳運輸方式的聯(lián)運方案為:A鐵路(9)→D換裝(2)水