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

賴曉桑 潘 杰 齊文豫蓉 楊 軍

北京理工大學珠海學院 廣東 珠海 519000

1 引言

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

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

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

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

3 運載飛艇的航線設(shè)計

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

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

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

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

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

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

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

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

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

4 結(jié)論

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