基于混合编程的航空公司机组调度实现技术研究

王进 夏洪山

摘要：该文研究了机组调度系统的基本功能单元和算法，论述了在机组调度系统中应用Delphi、Visual C++、MATLAB混合编程技术和方法，分析了混合编程技术在系统开发中的独特优势，完成了基于混合编程的航空公司调度系统的开发。

关键词：机组调度；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

机组调度实际上就是航空公司机组人员指派问题[1]，属于NP-Hard疑难问题，具有复杂度高和约束条件多的特点。多年来，国内航空公司的机组调度量历年增大，导致了调度过程效率低，成本高，调度结果机组人员不满意等问题。基于混合语言编程的航空公司机组调度系统的开发，有利于航空公司充分利用人力资源，提高航班运营效率，降低航班运营成本。

该系统利用混合编程的思想，将Matlab编写的匈牙利指派算法和VC++编译成的DLL（动态链接库），提供给Delphi编写好的主程序调用。充分发挥了各个语言的优势，大大提高了软件的编写速度和运行效率，增加了算法的稳定度。

1 机组调度系统

机组调度（Crew Recovery），就是根据勤务对机组提出的规格要求（即机组配对的结果），给勤务安排具体的飞行人员和乘务人员，生成驾驶机组（Cockpit Crew）（满足机型、技术、航线、勤务时间等要求）和乘务组（Cabin Crew）[2]。

机组调度的结果：生成符合勤务飞行要求的机组人员组成名单。即，每一具体机组的成员名单有哪些人，各机组什么时候飞哪些航班。

2 系统实现算法—匈牙利指派

2.1数学模型

机组调度问题涉及的系统结构复杂、参数众多、具有高度的非线性，属于多变量输入、多条件受限系统[3]。根据飞行计划编制的基本原则要求，该文将复杂的问题进行了适当的简化，将问题研究的重点集中在飞行人员工作负荷均衡、机组人员规模、人为因素协调这三个方面。这里我们给出飞行机组中的飞行员排班，乘务员排班同理。

引入以下参数：

i：飞行员编号

j：勤务号

ti：飞行员已飞总时间

tj：执行勤务j需要的飞行时间

tij：将飞行员i执行完勤务j后的飞行小时与飞行员人均飞行总小时的差值

xij：指派决策变量，把勤务i指派给飞行机组j时等于1，否则等于0

[T=1nj=1ntj+ti]

tij=|ti+tj-T|

以tij最小为目标函数，建立飞行机组的指派模型为：

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） 每个勤务号只能由一个飞行员组执勤

2） 每个飞行员组只能执行一个勤务号

3） 飞行员的英语要求约束

ai=[0，不会1，会英语] bj=[0，需要英语能力1，不需要英语能力]

4） 多机組情况，例如双机长和三人机组，其中RosterAdd是需要多人机组执行的活动串子集，一般情况下C=3

5） 如果两位飞行员i，k不能一起值勤，则构成不相容约束。设不相容的飞行员的集合是CrewIncomp

6） 指派决策变量xij，把勤务i指派给飞行机组j时等于1，否则等于0

2.2算法求解过程

step1：根据约束条件（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

从上可知，该机组调度系统的实现算法设计到矩阵计算，相对复杂，使用Delphi或者VC++进行开发需要花费大量的时间，且难度较大，而使用Matlab则简单快速很多。但同时，该系统又需要强大的图形界面操作，方便使用者清晰直观的看到结果，而Matlab并不具备这一功能，所以需要使用Delphi进行前台开发。这样混合编程既可以提高效率又可以增加软件执行的稳定度。

3 混合编程技术

3.1混合编程技术

混合语言编程又叫多语言混合编程，它是指源程序使用两种或两种以上计算机编程语言编写应用程序的过程，克服了单一语言带来的功能不足。[4]本系统中的混合编程就是将MATLAB与VC++混合编写的算法程序编译成动态链接库（DLL），供主程序（Delphi）调用。

该系统实现基于混合语言（MATLAB、VC++、Delphi）编程的思想。利用Delphi搭建系统的框架和提供接口参数，结合MATLAB和VC++混合编程实现机组调度系统。

3.2三种编程语言特点分析

MATLAB是一种面向工程实践和科学运算的交互式仿真软件，它集科学计算、信号处理、系统仿真与可视化于一体，具有极高的运算效率，简单直接。缺点是程序为解释执行，运行速度较慢，而且几乎没有界面功能。

Delphi是一种便捷的可视化编程语言，实现界面和采集数据速率很高。但在算法工具和数值处理等方面，Delphi的工作效率远低于MATLAB语言。

VC++是Windows平台主要的应用程序开发环境之一。它不仅具有C++语言的高效性和灵活性，又具有可视化编程的便利性和界面的友好性。但在矩阵运算、数值分析方面不如Matlab，在界面编写和数据采集方面不如Delphi简单。

3.3混合编程技术应用

因为MATLAB提供了多种应用程序接口，其中提供了基于win32平台的VC++应用程序接口，但是没有提供与Delphi的应用程序接口。所以，想到使用MATLAB与VC++的接口函数，通过MATLAB引擎发送指令和数据，编写出动态连接库（DLL），作为MATLAB与Delphi的接口，然后在Delphi中调用此DLL。

系统中具体执行过程如下图2所示：

3.3.1 DLL在系统中的优势

动态链接库DLL（Dynamic Link Library）[5]是经过编译的可执行代码模块。DLL是Windows程序设计中一个很重要的组成部分，它的用途十分的广泛。DLL如此广泛使用的主要原因是：

1） 由于在运行时应用程序会动态地加载DLL，而应用程序没有使用它时，系统则会在内存中移除它。所以，使用DLL可以节省系统的资源。

2） 使用DLL允许不同的Windows应用程序实现代码、资源和数据的共享。

3） 使用DLL可以隐藏例程的细节，提高应用程序的安全性。

4） 使用DLL便于应用程序实现模块化。特别是对大型软件系统的开发，它的优点就更为明显了。

5） 易于实现使用DLL的软件系统的升级。

3.3.2 DLL在系统中的实现

DLL的实现主要是三个函数：

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引擎函数成功；返回0则说明MATLAB引擎未开启

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

{ if（ep）

{ engClose（ep）；

ep=NULL；

return 1；

}

else

return 0；

}

3） 执行MATLAB命令函数：

//返回1，则执行命令成功；返回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 机组调度编排结果

4 结束语

本文介绍了机组调度系统的基本功能和所使用的算法，实现Delphi、Visual C++、MATLAB混合开发，对系统开发中的混合编程技术的独特优势进行了分析，并且给出了相应的应用，大大降低了编程量，提高了开发效率。

参考文献：

[1] 肖真真.基于任務均衡的航空公司机组人员指派问题研究[D].广汉：中国民用航空飞行学院，2012.

[2] 周琨.航空公司航班运行调度模型与算法研究[D].南京：南京航空航天大学，2012.

[3] 朱金福.航空运输规划[M].西安：西北工业大学出版社，2009.

[4] 胡建华，武鹃.Visual C++ 和MATLAB混合编程的研究[J].工程地质计算机应用，2002（2）：11-13.

[5] 倪华娟.面纸箱设计软件中 Delphi 动态链接库 （DLL） 的实现[D].成都：电子科技大学，2011.