多港口掛靠班輪航線配船數(shù)學模型及其應(yīng)用

杜 紅， 謝新連， 唐 磊， 趙家保

(大連海事大學 綜合運輸研究所，遼寧 大連 116026)

謝新連(1956-),男,遼寧大連人,教授,博士生導(dǎo)師,主要從事交通運輸規(guī)劃與管理方面的研究。E-mail: xxlian77@yahoo.com.

多港口掛靠班輪航線配船數(shù)學模型及其應(yīng)用

杜 紅， 謝新連， 唐 磊， 趙家保

(大連海事大學 綜合運輸研究所，遼寧 大連 116026)

為滿足班輪運輸定時、定期服務(wù)的要求，提高班輪運輸系統(tǒng)的優(yōu)化配置水平，根據(jù)班輪多港口掛靠與貨物直達運輸航線形式的特點，綜合考慮貨運需求、單船最大載貨量、最小發(fā)船班次、運價水平等多種因素，以研究期內(nèi)船隊營運利潤最大為目標，建立班輪航線配船優(yōu)化數(shù)學模型，并系統(tǒng)地介紹建模原理。通過求解算例，驗證模型的合理性。計算結(jié)果表明：提出的優(yōu)化方法可有效模擬班輪運輸?shù)倪\營組織特征，有助于制定研究期內(nèi)航線配船、發(fā)船班次的最優(yōu)方案決策。模型結(jié)構(gòu)簡潔、易于理解、求解便利、實用性強。

水路運輸；多港口掛靠；班輪運輸；航線配船；數(shù)學模型

班輪公司在運輸組織過程中必然要解決這樣一個問題：如何配置班輪船隊中不同類型的船舶到公司經(jīng)營的各條航線上，使整個船隊取得最佳的經(jīng)濟效益，即班輪航線配船問題。班輪航線配船決策應(yīng)該滿足兩個基本要求：

1. 技術(shù)上可行，要求船舶的各項技術(shù)參數(shù)能夠滿足航線營運的條件。這可以根據(jù)客觀因素及實際經(jīng)驗進行判斷、解決。

2. 經(jīng)濟上合理、最有利。這是一個最優(yōu)化問題，也是班輪航線配船的主要研究內(nèi)容。

由于問題的復(fù)雜性，在實踐中，一直是依靠投資經(jīng)營者的個人經(jīng)驗和主觀判斷來進行班輪船隊航線配船，缺乏科學、系統(tǒng)的決策分析方法。因此，從20世紀90年代起，國內(nèi)外學者們開始對大型班輪船隊進行航線配船和船隊規(guī)劃方面的探索，力求建立一套科學的數(shù)學方法和技術(shù)來解決這個問題。文獻[1-2]探討了更切合實際的航線配船非線性影響及其模型建立問題；文獻[3]建立了適用于在同一航線上配置相同船型的典型班輪運輸模式的班輪船隊規(guī)劃混合整數(shù)非線性規(guī)劃模型。這些研究工作雖然在理論上取得了一些進展，做出了有益的探索，但由于模型解算復(fù)雜，在實用性上還存在一定的差距。

鑒于此，本文基于班輪運輸組織方式的特點和要求，利用便于求解計算大規(guī)模問題的線性規(guī)劃理論，研究、建立一個適于多港口掛靠班輪航線配船優(yōu)化的數(shù)學模型，并通過算例對模型進行驗證和分析。

1 問題描述與假設(shè)

針對一個具有一定規(guī)模的班輪船隊，可通過貨源調(diào)查和預(yù)測掌握研究期內(nèi)其運營航線上任意港口間的貨運需求量及運價水平。要求設(shè)計出最優(yōu)的航線配船和發(fā)船班次方案，在技術(shù)可行的基礎(chǔ)上，使班輪公司獲得的經(jīng)濟效益最佳。

數(shù)學建模中采用的基本假設(shè)：

1. 研究期為一年、一個季度、一個月或其他單位時間。

2. 班輪公司經(jīng)營的航線共G條，均為傳統(tǒng)的多港口掛靠、貨物直達運輸航線，即船舶從起始港出發(fā)沿一個方向航行，中途可以掛靠多個港口，到達終點港卸完所有貨物后重新裝貨，返回始發(fā)港，然后再進行下一個往返航次。[3]每艘船舶在去程和回程中都可以在多個中途港裝、卸貨物，并且不要求去程與回程必須訪問相同的港口。

3. 班輪公司運營的航線網(wǎng)上掛靠港口總數(shù)為n，所有掛靠港口統(tǒng)一編號為1～n，每條航線上去程與回程的掛靠港口順序確定。

4. 研究期內(nèi)共有K種船型可供選擇。

5. 各港口之間的貨運需求量及運價水平已預(yù)測或確定。

6. 以集裝箱量TEU為單位衡量船舶的承載能力和貨運需求量，并且只考慮整箱裝運，不考慮拼箱運輸?shù)那闆r。

7. 在兩掛靠港口之間的往返運價不一定相同，即Fhij不一定等于Fhji。

8. 預(yù)先確定研究期內(nèi)各型船在各航線上以最佳航速[4]航行時可以完成的往返航次數(shù)。

9. 為了提高服務(wù)質(zhì)量，班輪公司會在經(jīng)營的航線上保持穩(wěn)定的班期，即規(guī)定研究期內(nèi)航線的最小發(fā)船班次。

10. 船舶在給定航線上的往返航次成本不會因航次載貨量變化而受到影響。

2 模型構(gòu)建及求解

2.1數(shù)學模型

對于上述問題，以研究期內(nèi)船隊利潤(總收入-航次營運成本)最大為目標，建立多港口掛靠班輪航線配船數(shù)學模型為

(1)

約束條件為

(2)

h=1,2,…,G;r=1,2,…,nph-1

(3)

h=1,2,…,G;r=1,2,…,ndh-1

(4)

(5)

(6)

xhij≥0h=1,2,…,G;i=1,2,…,n;

j=1,2,…,n

(7)

yhm≥0h=1,2,…,G;m=1,2,…,K

(8)

船舶航次營運成本Chm可由下式確定。[4]

(9)

上述優(yōu)化模型中，式(2)為貨運量約束條件，要求研究期內(nèi)船舶運輸某種貨物的總量不超過其貨運需求量；式(3)和式(4)分別為每個掛靠港口正反兩方向運輸時船舶貨運承載量約束[5-6]，船舶在任何港口裝(卸)完貨物駛向下一個港口時，船上所載貨物總量不能超過其在此航線上的貨運承載量(單船最大載貨量與船舶在此航線上的平均裝載率之積)；式(5)是對航線最小發(fā)船班次的約束，研究期內(nèi)所有船舶在同一航線上完成的總航次數(shù)不能小于班輪公司要求的此航線最小發(fā)船班次；式(6)是對各型船數(shù)量的約束，研究期內(nèi)用于運輸?shù)母餍痛瑪?shù)量之和不能大于船隊中該型船的數(shù)量；式(7)和式(8)是決策變量非負約束。式(1)～式(8)構(gòu)成了一個完整的混合整數(shù)線性規(guī)劃模型。

2.2模型求解

分析表明，模型中有些變量和約束條件沒有實際意義。例如，當i=j時，xhij為每個掛靠港向本港運輸?shù)募b箱數(shù)量；Vij為每個掛靠港到本港的集裝箱運輸需求量。在運用混合整數(shù)規(guī)劃方法求解模型之前，可選擇以下兩種方式對這些變量和約束條件進行處理：

1) 在確定模型參數(shù)時，對于h航線上不能掛靠的港口對(i，j)，預(yù)先設(shè)定Fhij為一適當負值，可保證在最優(yōu)解中h航線上船舶在(i，j)港口對間無運量發(fā)生，即xhij=0；在約束條件(2)中，對于所有航線都不能掛靠的港口對(i，j)，令Vij=0。

2) 從模型中將這些變量和約束條件消除。

采用第二種處理方式可減少模型的變量和約束條件，從而有效提高求解速度。

3 計算案例

3.1參數(shù)準備

某班輪公司經(jīng)營3條沿海內(nèi)貿(mào)集裝箱航線，具體的航線圖見圖1。

(注：1-天津，2-秦皇島，3-大連，4-營口，5-煙臺，6-上海，7-寧波，8-廣州南沙)

設(shè)研究期為1 a，該班輪公司擁有的各型船舶數(shù)量及單船最大載貨量見表1，為計算方便，本例中假設(shè)各型船在各航線上的平均載貨率相同，取θ為0.7；研究期內(nèi)各航線的掛靠港口及最小發(fā)船班次見表2；預(yù)測或確定的各掛靠港之間的貨運需求量及運價見表3；各型船在各航線上的最大往返航次數(shù)及航次費用見表4。其中，由于客觀條件限制，1型船不能在1航線上運營。

表1 各型船數(shù)量及單船最大載貨量

表2 研究期內(nèi)各航線的掛靠港口及最小發(fā)船班次

3.2求解計算及結(jié)果分析

表3 研究期內(nèi)各掛靠港之間貨運需求量及運價

表4 研究期內(nèi)各型船在各航線上的最大往返航次數(shù)及航次費用

y11(本算例中1型船不能配置在航線1上運營)；可以消除的約束條件包括式(2)中當i=j時對應(yīng)的約束條件和(i，j)不是任何航線上的港口對時所對應(yīng)的約束條件。算例中，在消除這類變量和約束條件后，有效變量為30個(見表5)，其中整數(shù)變量變?yōu)?1個；有效約束條件為37個。消除這些變量和約束條件后，可大大提高模型的求解速度。

用上述混合整數(shù)線性規(guī)劃模型求解該問題，得到的最優(yōu)解見表5。按照表5的方案安排船隊，除掛靠港1(天津)到掛靠港7(寧波)的部分貨運需求外，該方案可滿足表4中列出的各掛靠港間的運輸需求。可驗證計算結(jié)果能夠保證式(2)～式(6)成立。得到的此優(yōu)化計算結(jié)果(y值)是僅根據(jù)研究期內(nèi)貨運需求量確定的，而各航線上的具體發(fā)船間隔需根據(jù)貨流分布特征進一步確定。

從優(yōu)化結(jié)果的形式上看，本算例具有多個最優(yōu)解，但各最優(yōu)解的目標函數(shù)值(z值)及船隊航線配船方案(y值)都相同(見表5)，區(qū)別僅在于掛靠港6(上海)到掛靠港4(營口)之間的貨運量xhij不同。顯然，當兩掛靠港間的貨物以不同航線運輸?shù)\價相同且船舶沒有在所有港口都滿載時，貨流可能在不同航線(具有重疊航段)的船舶間適當轉(zhuǎn)移，這種轉(zhuǎn)移并不改變運輸總收入和總成本，這是最優(yōu)解不唯一的原因。這種最優(yōu)解的多值性也表明，按照優(yōu)化結(jié)果設(shè)置的航線配船方案對貨流在一定范圍內(nèi)的變化具有適應(yīng)性。

表5 最優(yōu)解

表6 研究期內(nèi)各型船平均閑置情況

4 結(jié) 語

根據(jù)班輪多港口掛靠與貨物直達運輸航線形式的特點，建立班輪航線配船混合整數(shù)線性優(yōu)化模型。模型以追求研究期內(nèi)班輪船隊利潤最大為目標，較全面地考慮貨運需求、單船最大載貨量、最小發(fā)船班次、運價水平等影響班輪航線配船的主要因素，更客觀地反映了班輪運輸組織的特征和規(guī)律。對于大型班輪船隊，雖然模型的變量和約束條件較多、規(guī)模較大，但可以通過變量消減達到快速求解的目的。最后通過模擬和優(yōu)化某班輪公司船隊在研究期內(nèi)的航線配船方案，驗證提出模型的可行性，模型結(jié)構(gòu)簡潔、易于理解，且實用性強。

[1] XIE X，JI Z，YANG Y．Nonlinear Programming for Fleet Planning[J]．International Shipbuilding Progress，1993，40 (421)：93-103．

[2] 趙剛．班輪航線配船模型的分析與改進[J]．系統(tǒng)工程學報，1997，12(1)：80-86．

[3] 楊秋平，謝新連，裴光石．班輪運輸船隊規(guī)劃模型與仿真[J]．西南交通大學學報，2011，46(6)：1046-1054．

[4] 謝新連．船舶運輸管理與經(jīng)營[M]．2版．大連：大連海事大學出版社，2009：189-195．

[5] 謝新連，王少成，楊秋平，等．一種公路客運線網(wǎng)優(yōu)化設(shè)計方法[J]．大連海事大學學報，2009，35(4)：59-62．

[6] 王少成，凡亞軍，楊秋平，等．大連市域內(nèi)公路長途客運主要班車線網(wǎng)優(yōu)化研究[J]．公路，2009(10)：171-175．

MathematicalModelofShip-RouteAllocationforMulti-CallLinerServiceanditsApplication

DUHong,XIEXinlian,TANGLei,ZHAOJiabao
(Integrated Transport Institute, Dalian Maritime University, Dalian 116026, China)

In order to meet the requirements of liner services with fixed schedules, and to optimize the liner shipping system, a mathematical optimization model for liner shipping allocation is established based on the multi-call liner route pattern, by comprehensively taking into account related factors, such as cargo demand, the capacity of a single ship, the minimum sail frequency and the tariff level. The objective of the model is to maximize the total profits of a liner fleet during an interested period. The modeling principle is introduced and the liner fleet of a shipping company is taken as an example to demonstrate the rationality of the model. The results indicate that the model correctly reflects the organization characteristics of liner shipping and optimizes the ship allocation and sail frequency. The form of the model is concise and easily understood, the solving process is fast and the model is very practical.

waterway transportation; multi-call; liner shipping; ship allocation; mathematical model

2014-01-02

高等學校博士學科點專項科研基金資助課題(20102125110002)

杜 紅(1989-),女,山東濰坊人,碩士生,主要從事交通運輸規(guī)劃與管理方面的研究。E-mail:duhong.19890214@163.com.

1000-4653(2014)02-0113-05

F550；U692.3

A