王進(jìn) 夏洪山

摘要：該文研究了機(jī)組調(diào)度系統(tǒng)的基本功能單元和算法，論述了在機(jī)組調(diào)度系統(tǒng)中應(yīng)用Delphi、Visual C++、MATLAB混合編程技術(shù)和方法，分析了混合編程技術(shù)在系統(tǒng)開發(fā)中的獨特優(yōu)勢，完成了基于混合編程的航空公司調(diào)度系統(tǒng)的開發(fā)。

關(guān)鍵詞：機(jī)組調(diào)度；Delphi；MATLAB；Visual C++；混合編程

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）01-0054-04

Union Programming Based Airlines Crew Recovery System

WANG Jin，XIA Hong-shan

（College of Civil Aviation， Nanjing University of Aeronautics and Astronautics， Nanjing 211106，China）

Abstract：This paper introduces function modules and algorithm of crew recovery system. Then discusses the application of Delphi， Visual C++，MATLAB union programming techniques and methods in crew recovery system. We analyze the unique advantage of union programming technology in system development. At last the application of union programming technology is given.

Key words： crew recovery； Delphi； MATLAB ；Visual C++； union programming

機(jī)組調(diào)度實際上就是航空公司機(jī)組人員指派問題[1]，屬于NP-Hard疑難問題，具有復(fù)雜度高和約束條件多的特點。多年來，國內(nèi)航空公司的機(jī)組調(diào)度量歷年增大，導(dǎo)致了調(diào)度過程效率低，成本高，調(diào)度結(jié)果機(jī)組人員不滿意等問題?；诨旌险Z言編程的航空公司機(jī)組調(diào)度系統(tǒng)的開發(fā)，有利于航空公司充分利用人力資源，提高航班運(yùn)營效率，降低航班運(yùn)營成本。

該系統(tǒng)利用混合編程的思想，將Matlab編寫的匈牙利指派算法和VC++編譯成的DLL（動態(tài)鏈接庫），提供給Delphi編寫好的主程序調(diào)用。充分發(fā)揮了各個語言的優(yōu)勢，大大提高了軟件的編寫速度和運(yùn)行效率，增加了算法的穩(wěn)定度。

1 機(jī)組調(diào)度系統(tǒng)

機(jī)組調(diào)度（Crew Recovery），就是根據(jù)勤務(wù)對機(jī)組提出的規(guī)格要求（即機(jī)組配對的結(jié)果），給勤務(wù)安排具體的飛行人員和乘務(wù)人員，生成駕駛機(jī)組（Cockpit Crew）（滿足機(jī)型、技術(shù)、航線、勤務(wù)時間等要求）和乘務(wù)組（Cabin Crew）[2]。

機(jī)組調(diào)度的結(jié)果：生成符合勤務(wù)飛行要求的機(jī)組人員組成名單。即，每一具體機(jī)組的成員名單有哪些人，各機(jī)組什么時候飛哪些航班。

2 系統(tǒng)實現(xiàn)算法—匈牙利指派

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

機(jī)組調(diào)度問題涉及的系統(tǒng)結(jié)構(gòu)復(fù)雜、參數(shù)眾多、具有高度的非線性，屬于多變量輸入、多條件受限系統(tǒng)[3]。根據(jù)飛行計劃編制的基本原則要求，該文將復(fù)雜的問題進(jìn)行了適當(dāng)?shù)暮喕瑢栴}研究的重點集中在飛行人員工作負(fù)荷均衡、機(jī)組人員規(guī)模、人為因素協(xié)調(diào)這三個方面。這里我們給出飛行機(jī)組中的飛行員排班，乘務(wù)員排班同理。

引入以下參數(shù)：

i：飛行員編號

j：勤務(wù)號

ti：飛行員已飛總時間

tj：執(zhí)行勤務(wù)j需要的飛行時間

tij：將飛行員i執(zhí)行完勤務(wù)j后的飛行小時與飛行員人均飛行總小時的差值

xij：指派決策變量，把勤務(wù)i指派給飛行機(jī)組j時等于1，否則等于0

[T=1nj=1ntj+ti]

tij=|ti+tj-T|

以tij最小為目標(biāo)函數(shù)，建立飛行機(jī)組的指派模型為：

min z=[j=1n i=1n tij·xij]

s.t.

[j=1nxij]=1， i=1，2，…，n （1）

[i=1nxij]=1， i=1，2，…，n （2）

ai·xij≥bj i，j=1，2，…，n （3）

[i∈C（j）xij]=c， j∈RosterAdd，c≥2 （4）

[j∈R（i）（xij+xkj）]=1，i，k∈CrewIncomp （5）

xij=0，1，i，j=1，2，…，n （6）

1） 每個勤務(wù)號只能由一個飛行員組執(zhí)勤

2） 每個飛行員組只能執(zhí)行一個勤務(wù)號

3） 飛行員的英語要求約束

ai=[0，不會1，會英語] bj=[0，需要英語能力1，不需要英語能力]

4） 多機(jī)組情況，例如雙機(jī)長和三人機(jī)組，其中RosterAdd是需要多人機(jī)組執(zhí)行的活動串子集，一般情況下C=3

5） 如果兩位飛行員i，k不能一起值勤，則構(gòu)成不相容約束。設(shè)不相容的飛行員的集合是CrewIncomp

6） 指派決策變量xij，把勤務(wù)i指派給飛行機(jī)組j時等于1，否則等于0

2.2算法求解過程

step1：根據(jù)約束條件（1） （2） （3） （4） （5） （6） ，篩選出滿足勤務(wù)j的飛行員進(jìn)行可行連接，在下圖1中用虛線表示：

step2：匈牙利算法求解（偽代碼）

for Nj為可飛勤務(wù)號j的飛行員

if Nj不為空集，連接勤務(wù)j與Nj中tij最小值的飛行員i

else

repeat（不斷回溯）

連接j與Nj中tij最小值

i=i-1

if Nj不為空集

連接勤務(wù)j與Nj中tij值第二小的飛行員i

break

else

continue

end

end

end

end

從上可知，該機(jī)組調(diào)度系統(tǒng)的實現(xiàn)算法設(shè)計到矩陣計算，相對復(fù)雜，使用Delphi或者VC++進(jìn)行開發(fā)需要花費大量的時間，且難度較大，而使用Matlab則簡單快速很多。但同時，該系統(tǒng)又需要強(qiáng)大的圖形界面操作，方便使用者清晰直觀的看到結(jié)果，而Matlab并不具備這一功能，所以需要使用Delphi進(jìn)行前臺開發(fā)。這樣混合編程既可以提高效率又可以增加軟件執(zhí)行的穩(wěn)定度。

3 混合編程技術(shù)

3.1混合編程技術(shù)

混合語言編程又叫多語言混合編程，它是指源程序使用兩種或兩種以上計算機(jī)編程語言編寫應(yīng)用程序的過程，克服了單一語言帶來的功能不足。[4]本系統(tǒng)中的混合編程就是將MATLAB與VC++混合編寫的算法程序編譯成動態(tài)鏈接庫（DLL），供主程序（Delphi）調(diào)用。

該系統(tǒng)實現(xiàn)基于混合語言（MATLAB、VC++、Delphi）編程的思想。利用Delphi搭建系統(tǒng)的框架和提供接口參數(shù)，結(jié)合MATLAB和VC++混合編程實現(xiàn)機(jī)組調(diào)度系統(tǒng)。

3.2三種編程語言特點分析

MATLAB是一種面向工程實踐和科學(xué)運(yùn)算的交互式仿真軟件，它集科學(xué)計算、信號處理、系統(tǒng)仿真與可視化于一體，具有極高的運(yùn)算效率，簡單直接。缺點是程序為解釋執(zhí)行，運(yùn)行速度較慢，而且?guī)缀鯖]有界面功能。

Delphi是一種便捷的可視化編程語言，實現(xiàn)界面和采集數(shù)據(jù)速率很高。但在算法工具和數(shù)值處理等方面，Delphi的工作效率遠(yuǎn)低于MATLAB語言。

VC++是Windows平臺主要的應(yīng)用程序開發(fā)環(huán)境之一。它不僅具有C++語言的高效性和靈活性，又具有可視化編程的便利性和界面的友好性。但在矩陣運(yùn)算、數(shù)值分析方面不如Matlab，在界面編寫和數(shù)據(jù)采集方面不如Delphi簡單。

3.3混合編程技術(shù)應(yīng)用

因為MATLAB提供了多種應(yīng)用程序接口，其中提供了基于win32平臺的VC++應(yīng)用程序接口，但是沒有提供與Delphi的應(yīng)用程序接口。所以，想到使用MATLAB與VC++的接口函數(shù)，通過MATLAB引擎發(fā)送指令和數(shù)據(jù)，編寫出動態(tài)連接庫（DLL），作為MATLAB與Delphi的接口，然后在Delphi中調(diào)用此DLL。

系統(tǒng)中具體執(zhí)行過程如下圖2所示：

3.3.1 DLL在系統(tǒng)中的優(yōu)勢

動態(tài)鏈接庫DLL（Dynamic Link Library）[5]是經(jīng)過編譯的可執(zhí)行代碼模塊。DLL是Windows程序設(shè)計中一個很重要的組成部分，它的用途十分的廣泛。DLL如此廣泛使用的主要原因是：

1） 由于在運(yùn)行時應(yīng)用程序會動態(tài)地加載DLL，而應(yīng)用程序沒有使用它時，系統(tǒng)則會在內(nèi)存中移除它。所以，使用DLL可以節(jié)省系統(tǒng)的資源。

2） 使用DLL允許不同的Windows應(yīng)用程序?qū)崿F(xiàn)代碼、資源和數(shù)據(jù)的共享。

3） 使用DLL可以隱藏例程的細(xì)節(jié)，提高應(yīng)用程序的安全性。

4） 使用DLL便于應(yīng)用程序?qū)崿F(xiàn)模塊化。特別是對大型軟件系統(tǒng)的開發(fā)，它的優(yōu)點就更為明顯了。

5） 易于實現(xiàn)使用DLL的軟件系統(tǒng)的升級。

3.3.2 DLL在系統(tǒng)中的實現(xiàn)

DLL的實現(xiàn)主要是三個函數(shù)：

1） 打開MATLAB引擎

//返回1，開啟成功；返回-1，打開失敗

extern "C" _declspec（dllexport） int WINAPI MatOpenEng（far char *cc）

{ if（ep） return 0； //0表示退出

if（！（ep=engOpen（cc））） return -1；

else return 1；

}

2） 關(guān)閉MATLAB引擎的

//返回1，關(guān)閉MATLAB引擎函數(shù)成功；返回0則說明MATLAB引擎未開啟

extern"C" _declspec（dllexport）int WINAPI MatCloseEng（void）

{ if（ep）

{ engClose（ep）；

ep=NULL；

return 1；

}

else

return 0；

}

3） 執(zhí)行MATLAB命令函數(shù)：

//返回1，則執(zhí)行命令成功；返回0表明，MATLAB引擎未開啟

extern"C" _declspec（dllexport）int WINAPI MatExec（void）

{ if（！ep）

return 0；

else

{engEvalString（ep，"crewassign"）； //cc中放MATLAB命令

return 1；

}}

3.3.3 機(jī)組調(diào)度編排結(jié)果

4 結(jié)束語

本文介紹了機(jī)組調(diào)度系統(tǒng)的基本功能和所使用的算法，實現(xiàn)Delphi、Visual C++、MATLAB混合開發(fā)，對系統(tǒng)開發(fā)中的混合編程技術(shù)的獨特優(yōu)勢進(jìn)行了分析，并且給出了相應(yīng)的應(yīng)用，大大降低了編程量，提高了開發(fā)效率。

參考文獻(xiàn)：

[1] 肖真真.基于任務(wù)均衡的航空公司機(jī)組人員指派問題研究[D].廣漢：中國民用航空飛行學(xué)院，2012.

[2] 周琨.航空公司航班運(yùn)行調(diào)度模型與算法研究[D].南京：南京航空航天大學(xué)，2012.

[3] 朱金福.航空運(yùn)輸規(guī)劃[M].西安：西北工業(yè)大學(xué)出版社，2009.

[4] 胡建華，武鵑.Visual C++ 和MATLAB混合編程的研究[J].工程地質(zhì)計算機(jī)應(yīng)用，2002（2）：11-13.

[5] 倪華娟.面紙箱設(shè)計軟件中 Delphi 動態(tài)鏈接庫 （DLL） 的實現(xiàn)[D].成都：電子科技大學(xué)，2011.