運(yùn)載飛艇的任務(wù)規(guī)劃與航線設(shè)計(jì)

賴曉桑 潘 杰 齊文豫蓉 楊 軍

北京理工大學(xué)珠海學(xué)院 廣東 珠海 519000

1 引言

近代以來,公路運(yùn)輸、鐵路運(yùn)輸?shù)目焖侔l(fā)展,為工業(yè)社會(huì)人員、資源、能源流動(dòng)帶來了巨大的便利,飛機(jī)的出現(xiàn)更是克服了地形地貌造成的運(yùn)輸難題,大型客運(yùn)、貨運(yùn)飛機(jī)以及機(jī)場等地面設(shè)施構(gòu)建成了龐大的空中交通運(yùn)輸網(wǎng)絡(luò),成為現(xiàn)代社會(huì)交通體系的重要組成部分,是最迅捷、最安全的交通運(yùn)輸方式。然而,隨著城市的發(fā)展和人口的增加,交通運(yùn)輸量劇增,陸地的交通運(yùn)輸網(wǎng)絡(luò)已經(jīng)難以滿足人類社會(huì)的交通運(yùn)輸需求,而以飛機(jī)為主體的現(xiàn)代化航空運(yùn)輸網(wǎng)絡(luò)由于運(yùn)載量非常有限,未能充分利用大氣層容納量來分擔(dān)陸地交通的壓力,對(duì)陸面交通擁堵的緩解杯水車薪。此外,飛機(jī)在單位運(yùn)載量之下油耗遠(yuǎn)高于火車、汽車,難以發(fā)展成為承擔(dān)大比例交通運(yùn)輸需求的交通工具。因此,在大城市,現(xiàn)代城市仍面臨著嚴(yán)峻的交通堵塞問題。相比之下,飛艇具有巨大的運(yùn)載量和極長的留空時(shí)間,起降方便,不受陸面交通容量的限制,適合作為短途和中長途運(yùn)輸?shù)闹饕煌üぞ?。加之飛艇無需依靠發(fā)動(dòng)機(jī)產(chǎn)生升力,同等運(yùn)載量下的能耗和廢氣排放量遠(yuǎn)低于現(xiàn)代飛機(jī),運(yùn)營成本極低。早在二十世紀(jì),飛艇一度是天空的主角,由于當(dāng)時(shí)的飛艇使用氫氣產(chǎn)生浮力,極易發(fā)生爆炸事故,加之當(dāng)時(shí)處于戰(zhàn)爭年代,飛艇易被擊落的特點(diǎn)使得它的發(fā)展?jié)撃苓h(yuǎn)遠(yuǎn)低于飛機(jī),因此,飛艇逐漸退出了歷史的舞臺(tái)。隨著世界各大城市交通擁堵現(xiàn)象日趨嚴(yán)重,交通壓力與日俱增,國內(nèi)外正在積極探索現(xiàn)代交通運(yùn)輸體系的改革和轉(zhuǎn)型方案,尤其是飛艇大規(guī)模商用的可行性正在被越來越多的研究者注意到?，F(xiàn)代使用氫氣產(chǎn)生浮力的氦氣飛艇可以克服飛艇的安全問題,當(dāng)今的自動(dòng)控制技術(shù)也增強(qiáng)了飛艇對(duì)抗強(qiáng)風(fēng)的能力,為飛艇重返天空,再度成為空運(yùn)主角提供了可行性。可見,飛艇在未來的航空運(yùn)輸體系當(dāng)中必將扮演重要的角色。任務(wù)規(guī)劃和航線設(shè)計(jì)是航空運(yùn)輸領(lǐng)域兩個(gè)重要的運(yùn)籌學(xué)問題,顯著關(guān)系著航空運(yùn)輸?shù)男矢叩汀１疚耐ㄟ^合理的指標(biāo)選取,構(gòu)建了使得運(yùn)輸成本達(dá)到最低的飛艇任務(wù)規(guī)劃模型,并通過分析航線設(shè)計(jì)所需要克服的困難,給出了可以近似計(jì)算飛艇最優(yōu)航線的算法。

2 運(yùn)載飛艇的任務(wù)規(guī)劃

運(yùn)載飛艇的任務(wù)規(guī)劃問題關(guān)鍵在于根據(jù)兩地間需要運(yùn)輸?shù)呢浳锴闆r合理配置飛艇班次,使得運(yùn)輸成本達(dá)到最低。為了兼顧飛艇貨艙型號(hào)的多樣性和運(yùn)輸貨物種類的多樣性,記貨物種類C（C=1,2,…）所對(duì)應(yīng)的體積為VC,數(shù)量為xC,每件質(zhì)量為mC;飛艇班次T（T=1,2,…）對(duì)應(yīng)的貨艙內(nèi)部尺寸為UT,最大載重量為MT,往返一次的成本為fT。由上可建立使得運(yùn)輸成本z達(dá)到最低的飛艇任務(wù)規(guī)劃模型如下:

式中:xC,T表示T班次的飛艇貨艙中C類貨物的數(shù)量。

3 運(yùn)載飛艇的航線設(shè)計(jì)

對(duì)于多地點(diǎn)間的飛艇貨運(yùn),合理的航線規(guī)劃對(duì)有效節(jié)省運(yùn)輸成本至關(guān)重要。記飛艇途徑的所有地點(diǎn)集V={v1,v2,…,vmax}、鏈接兩點(diǎn)間的邊所構(gòu)成的邊序列集E以及表示各點(diǎn)間距離的鄰接矩陣W所構(gòu)成的無向賦權(quán)圖為G=（V,E,W）,其中鄰接矩陣W可表示為:

式中:wvi,vj表示地點(diǎn)vi到地點(diǎn)vj的距離,由于任意地點(diǎn)到它本身的距離為零,因此該矩陣主對(duì)角線上的元素值全部為零。

運(yùn)載飛艇的航線設(shè)計(jì)問題可表述為尋找一個(gè)方案使得遍歷所有目標(biāo)地點(diǎn)的航線達(dá)到最短,這是一個(gè)典型的旅行商問題,其求解關(guān)鍵在于從所有的可行航線（解空間）中找到最短航線（最優(yōu)解）。由排列數(shù)公式可知,當(dāng)?shù)攸c(diǎn)集的元素?cái)?shù)量為n時(shí),可選擇的航線方案數(shù)量為n的階乘。當(dāng)n的數(shù)量較小時(shí),易于通過遍歷計(jì)算所有可選航線的長度找出最短航線。當(dāng)n的數(shù)量較大時(shí),可選航線的數(shù)量非常巨大,以當(dāng)代計(jì)算機(jī)的算力無法在短時(shí)間內(nèi)逐一計(jì)算每個(gè)航線的長度,此時(shí)該問題無法精確求解,只能通過優(yōu)化算法求出一個(gè)近似最優(yōu)解。下述為通過改良圈算法計(jì)算近似最優(yōu)解的步驟:

（1）利用隨機(jī)數(shù)發(fā)生器生成所有地點(diǎn)的一個(gè)全排列v1v2…vn作為初始航線;

（2）利用隨機(jī)數(shù)發(fā)生器生成兩個(gè)隨機(jī)數(shù)x,y（1＜x＜n,1＜y＜n,x≠y）;

（3）將初始航線中自vx到vy的路徑逆序放置,得到改良航線,過程可表示為

（4）分別計(jì)算初始航線與改良航線的長度;

（5）若初始航線長度大于改良航線,則改良航線取代初始航線,成為新的初始航線,否則,初始航線維持不變;

（6）重復(fù)步驟（2）至（5）,直至無法得到更短的改良航線,此時(shí)經(jīng)過多次迭代改良的航線為近似最短航線。

4 結(jié)論

飛艇在未來的航空運(yùn)輸體系當(dāng)中必將扮演重要的角色。任務(wù)規(guī)劃和航線設(shè)計(jì)是航空運(yùn)輸領(lǐng)域兩個(gè)重要的運(yùn)籌學(xué)問題,顯著關(guān)系著航空運(yùn)輸?shù)男矢叩?。本文通過合理的指標(biāo)選取,設(shè)置容積、最大載重量等約束條件,構(gòu)建了使得運(yùn)輸成本達(dá)到最低的飛艇任務(wù)規(guī)劃模型,并通過圖論對(duì)飛艇的航線設(shè)計(jì)問題進(jìn)行機(jī)理分析,給出了可以近似計(jì)算飛艇最優(yōu)航線的算法。