Excel中規(guī)劃求解在集裝箱班輪航線系統(tǒng)配船中的應(yīng)用

文/郭海濤 施洪健

航線配船與船隊規(guī)劃是合理配置航運(yùn)企業(yè)有限資源的重大決策，它關(guān)系到企業(yè)的經(jīng)濟(jì)效益，影響到企業(yè)的競爭力和發(fā)展。因此，國內(nèi)外許多學(xué)者對此做了大量研究。例如，文獻(xiàn)[1]研究了新組建船隊的規(guī)劃問題，文獻(xiàn)[2]建立了基于不確定性的動態(tài)船隊規(guī)劃模型，文獻(xiàn)[3]采用粒子群優(yōu)化算法建立了不確定性的航線配船模型。這些研究在理論上都是成功的，但模型都十分復(fù)雜且解法繁瑣， 非專業(yè)人員很難掌握，無法應(yīng)用于企業(yè)實(shí)踐。文獻(xiàn)[4]提出了船隊規(guī)劃的線性規(guī)劃、非線性和動態(tài)規(guī)劃模型，利用線性規(guī)劃與動態(tài)規(guī)劃相結(jié)合的算法，開發(fā)了計算機(jī)軟件包進(jìn)行求解，將研究向?qū)嵱没七M(jìn)了一步。但是受船公司管理人員專業(yè)知識所限，對于軟件包解題規(guī)模和使用范圍認(rèn)識有限，無法準(zhǔn)確理解計算機(jī)語言，難以應(yīng)用于航運(yùn)企業(yè)的系統(tǒng)配船。因此，本文針對傳統(tǒng)航線配船和船隊規(guī)劃方法難以應(yīng)用于實(shí)踐中的問題，建立了航線配船與船隊規(guī)劃數(shù)學(xué)模型，并采用線性規(guī)劃中的整數(shù)規(guī)劃的方法開發(fā)了航線配船與船隊規(guī)劃決策系統(tǒng)，旨在推動excel中規(guī)劃求解在航運(yùn)企業(yè)系統(tǒng)配船中的運(yùn)用。

充分競爭的集裝箱班輪市場，外部環(huán)境若發(fā)生較大的變化，勢必影響既有航線貨運(yùn)量發(fā)展。貨運(yùn)量的改變，直接導(dǎo)致相應(yīng)航線競爭日趨激烈，或在班輪公會的指導(dǎo)下進(jìn)行運(yùn)力控制。[5]作為班輪公司而言，經(jīng)營多條班輪航線，分配在這些航線上的船舶類型、規(guī)模和數(shù)量各異，雖然在各航線開辟時，對航線上的配船方案都是在詳細(xì)地論證之后才確定下來的，但外部環(huán)境改變會導(dǎo)致原有方案不能充分達(dá)到公司的經(jīng)營目的，面對市場航運(yùn)公司必須盡快調(diào)整運(yùn)力分配。

1.問題描述

傳統(tǒng)的航線配船大都采用大船配大線法則，亦即大噸位、高速船配置在航距長、裝卸效率高、貨源充足的航線上。按此法則確定的配船方案雖然在一定程度上體現(xiàn)了經(jīng)濟(jì)上合理的原則，但不能保證其最優(yōu)化。集裝箱班輪航線系統(tǒng)配船優(yōu)化是指最合理地將班輪船隊中不同噸位（箱位）的船舶配置到公司經(jīng)營的各條航線上，做到不僅要保證滿足每條航線的技術(shù)、營運(yùn)方面的要求，而且能夠使船公司取得最好的經(jīng)濟(jì)效益。經(jīng)濟(jì)上合理則存在一個優(yōu)化的問題，這是集裝箱班輪航線系統(tǒng)配船優(yōu)化的主要研究內(nèi)容。[6]

2.模型建立

集裝箱班輪公司經(jīng)營發(fā)展，大多以成本最低或運(yùn)量最大為目標(biāo)函數(shù)，基本上都是以運(yùn)力限制和貨源（運(yùn)量）限制為約束條件。此模型的目標(biāo)函數(shù)追求的是系統(tǒng)總成本的最小化，建立線性關(guān)系，形成分配問題線性規(guī)劃模型。此模型基本上反映了班輪航線的實(shí)質(zhì)。

圖1

K——系統(tǒng)總成本

Kij——每艘i型船在j航線上完成一個往返航次所花費(fèi)的成本（美元/次）

xij ——i型船在j航線上每季度完成的往返航次數(shù)，是決策變量（次/季度）

pj——j航線上1 TEU貨物的機(jī)會成本（美元/ TEU）

yj——j航線上未被船舶承運(yùn)的集裝箱數(shù)量，也是決策變量（TEU）

nij——每艘i型船在j航線上每季度可以完成的最大往返航次數(shù)（次/季度）

mi——i型船的船舶數(shù)量（艘）

Ni——i型 船的集裝箱裝載能力（TEU）

Qj——j航線上得正向運(yùn)量（TEU）

在此模型中，目標(biāo)函數(shù)追求系統(tǒng)總成本最小。系統(tǒng)總成本包括船舶運(yùn)輸成本和機(jī)會成本。約束條件中，第一個為船隊能力約束，它表示i型船分配到所有航線的船舶數(shù)量不能超過該型船的船舶總數(shù)；第二個約束條件是運(yùn)輸需求約束，j航線上所有船舶完成的運(yùn)輸量加上未被承運(yùn)的部分正好等于該航線的運(yùn)輸任務(wù)。

3.模型求解（見圖1）

步驟1 在excel表格頂部輸入數(shù)據(jù)。

步驟2 確定每個決策變量所對應(yīng)的單元格的位置。

步驟3 選擇單元格輸入格式，找到目標(biāo)函數(shù)的值。

步驟4 選擇一個單元格輸入公式，計算每個約束條件左邊的值。

步驟5 選擇一個單元格輸入公式，計算每個約束條件右邊的值。

4.運(yùn)用舉例

現(xiàn)有某船公司擁有3種噸位的集裝箱船23艘，它們分別是1500 TEU集裝箱船5艘、850 TEU集裝箱船8艘、500 TEU集裝箱船10艘?，F(xiàn)已開辟了4條班輪航線，這些航線始發(fā)港相同，而目的港不同，分別處在不同的國家或地區(qū)。根據(jù)預(yù)測，各條航線每季度的集裝箱貨運(yùn)量有6種可能的情況，具體數(shù)值列在表1中。船舶在每條航線每季度最多能完成的航次數(shù)、每艘船在各航線每往返航次的成本，以及每條航線發(fā)生的機(jī)會成本列在表2中。

表1 各條航線每季度的集裝箱貨運(yùn)量

表2 各航線的每季度最大航次數(shù)、單船單航次成本和各航線機(jī)會成本

利用excel中規(guī)劃求解，把規(guī)劃求解結(jié)果用表3列出，因可能存在的6種貨運(yùn)量，所以每種情況都要通過計算機(jī)利用excel中規(guī)劃求解運(yùn)算。

剩余船舶數(shù)量/艘= 型船的總數(shù)量—船舶數(shù)量約束

表3中的“---”代表數(shù)據(jù)0，意思代表航次數(shù)或未被承運(yùn)的箱量。

表3 各運(yùn)量方案下的航線配船結(jié)果

從表中的配船結(jié)果可以看到，在運(yùn)輸任務(wù)較少時，噸位大的運(yùn)輸船舶優(yōu)化分配到了各條航線，而噸位較小的船舶由于單位運(yùn)輸成本高而未被安排。當(dāng)各條航線運(yùn)量增加時，船隊中所有的船舶都被分配到相應(yīng)的航線上去了，而且部分航線的一些貨載有剩余（見運(yùn)量方案5、運(yùn)量方案6的配船方案），這時表明船隊運(yùn)力已小于運(yùn)量。目標(biāo)函數(shù)值，是某一運(yùn)量條件下的最小運(yùn)輸成本值，隨著運(yùn)量的增加而增加。

5.結(jié)語

航線配船與船隊規(guī)劃問題一直是航運(yùn)業(yè)關(guān)注和研究的熱點(diǎn)，但是實(shí)用可行的優(yōu)化模型非常少。本文在追求實(shí)用性的基礎(chǔ)上建立了一種以船隊營運(yùn)總成本最小為目標(biāo)函數(shù)的優(yōu)化模型。該模型根據(jù)下一季度時間內(nèi)的運(yùn)輸需求，預(yù)測研究這個船隊在此季度內(nèi)的最優(yōu)構(gòu)成和船隊規(guī)劃問題。作者以excel中為規(guī)劃求解，設(shè)計開發(fā)了航線配船與船隊規(guī)劃決策系統(tǒng)。該系統(tǒng)能夠根據(jù)輸入的已知決策參數(shù)，迅速求解出相應(yīng)的最優(yōu)船隊調(diào)配和規(guī)劃方案，為決策者提供快速、準(zhǔn)確的參考數(shù)據(jù)。

[1] Nicholson T A J, Pullen R D.Dynamic programming applied to ship fleet management [ J] . Operational Research Quarterly, 1971, 22( 3) : 2112220.

[2] 蘇紹娟. 不確定動態(tài)船隊規(guī)劃的數(shù)學(xué)模型研究[ J] .中國航海, 2008,31( 2)

[3] 蘇紹娟, 王麗錚, 王呈方. 不確定性航線配船數(shù)學(xué)模型建模方法[ J] . 船海工程, 2007, 36( 4) :

[4] 謝新連, 李樹范, 紀(jì)卓尚 等. 船隊規(guī)劃的線性模型研究與應(yīng)用[ J] . 中國造船, 1989, ( 3) : [ 5] 趙剛. 國際航運(yùn)管理(普通高等教育十五國家級規(guī)劃教材) .2006年01月