最小费用最大流模型在航班衔接问题中的应用

An Application on Minimum Cost and Maximum Flow Model to Flight Connecting Problem in Single Hub and Spoke Network

针对单枢纽航线网络的特点 ,以所需飞机数最少 ,航班在枢纽机场的过站衔接最紧凑为目标 ,提出了描述航班衔接问题的最小费用最大流网络模型 :首先将航班衔接问题转化为航班节的衔接问题并以各航班节在枢纽机场的到港、离港时刻为结点 ,建立了一个描述航班节衔接问题的单源汇网络 ,从而将航班衔接问题转化为该单源汇网络的最小费用最大流问题。利用 dijkstra算法求该网络的最小费用最大流进而得到了一个需用飞机数最少 ,且过站衔接最紧凑的航班节衔接方案 。

To schedule flight connecting is a preliminary work in airliner operation. A good mathematical model and algorithm are necessary in this work. This paper developes an minimum cost and maximum flow model for flight connecting in a hub and spoke network system to minimize the number of aircraft required. First, the flight connecting problem is transferred into flight pairing connecting problem, then a single source and sink network is set to correspond to flight pairing connecting, in which minimum and cost maximum flow problem corresponds to an optimal flight pairing connecting. Finally, the dijkstra algorithm for calculating the minimum cost and maximum flow is used, and an optimal flight connecting scheme is found.