王進 夏洪山

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

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

中圖分類號：TP311 文獻標識碼：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

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

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

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

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

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

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

2.1數(shù)學模型

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

引入以下參數(shù)：

i：飛行員編號

j：勤務號

ti：飛行員已飛總時間

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

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

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

[T=1nj=1ntj+ti]

tij=|ti+tj-T|

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

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） 每個勤務號只能由一個飛行員組執(zhí)勤

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

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

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

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

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

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

2.2算法求解過程

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

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

for Nj為可飛勤務號j的飛行員

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

else

repeat（不斷回溯）

連接j與Nj中tij最小值

i=i-1

if Nj不為空集

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

break

else

continue

end

end

end

end

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

3 混合編程技術(shù)

3.1混合編程技術(shù)

混合語言編程又叫多語言混合編程，它是指源程序使用兩種或兩種以上計算機編程語言編寫應用程序的過程，克服了單一語言帶來的功能不足。[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)機組調(diào)度系統(tǒng)。

3.2三種編程語言特點分析

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

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

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

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

因為MATLAB提供了多種應用程序接口，其中提供了基于win32平臺的VC++應用程序接口，但是沒有提供與Delphi的應用程序接口。所以，想到使用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程序設計中一個很重要的組成部分，它的用途十分的廣泛。DLL如此廣泛使用的主要原因是：

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

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

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

4） 使用DLL便于應用程序?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） 關閉MATLAB引擎的

//返回1，關閉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 機組調(diào)度編排結(jié)果

4 結(jié)束語

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

參考文獻：

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

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

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

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

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