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

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

(大連海事大學(xué) 綜合運(yùn)輸研究所，遼寧 大連 116026)

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

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

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

(大連海事大學(xué) 綜合運(yùn)輸研究所，遼寧 大連 116026)

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

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

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

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

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

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

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

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

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

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

1. 研究期為一年、一個(gè)季度、一個(gè)月或其他單位時(shí)間。

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

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

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

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

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

7. 在兩掛靠港口之間的往返運(yùn)價(jià)不一定相同，即Fhij不一定等于Fhji。

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

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

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

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

2.1數(shù)學(xué)模型

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

(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)

船舶航次營(yíng)運(yùn)成本Chm可由下式確定。[4]

(9)

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

2.2模型求解

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

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

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

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

3 計(jì)算案例

3.1參數(shù)準(zhǔn)備

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

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

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

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

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

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

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

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

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

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

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

表5 最優(yōu)解

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

4 結(jié) 語(yǔ)

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

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

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

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

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

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

[6] 王少成，凡亞軍，楊秋平，等．大連市域內(nèi)公路長(zhǎng)途客運(yùn)主要班車線網(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

高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助課題(20102125110002)

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

1000-4653(2014)02-0113-05

F550；U692.3

A