飞机排班数学规划模型

分析了国内航空公司普遍采用的单枢纽线性航线结构以及飞机排班工作流程和要求, 研究了描述飞机排班问题的数学模型构造方法, 引入"航班节"的概念, 将一个具体的飞机排班问题归结为三种典型排班模式中的一种, 即基于飞机调度指令要求的排班问题、基于最少需用飞机数的排班问题、基于飞机使用均衡要求的排班问题。应用结果表明平均每架飞机分配的航班任务时间与期望飞行时间的偏差仅为4 8min, 而且得到飞机排班方案的时间不到23s, 因此此飞机排班模式是解决单枢纽线性航线结构下的飞机排班问题的一种有效方法。     

应用网络流模型解决航班衔接问题

针对单枢纽机场航线结构的特点，以所需飞机数最少为目标，提出了一种描述航班衔接问题的图论模型及优化算法。首先将航班衔接问题转化为航班节的衔接问题，并建立一个描述航班节衔接问题的二部图，将航班衔接问题转化为二部图的最大匹配问题，然后由二部图生成一个具有单源汇网络特征的辅助图，利用Ford-Fulkerson算法求该网络的最大流，进而得到二部图的最大匹配，从而得到了一个需用飞机数最少的航班节衔接方案，为利用计算机自动编制并优化航班衔接方案提供了一种可行方法。并且通过调整过站时间上限，可以得出不同的航班衔接方案，为制订生产计划提供了必要的灵活性。     

基于约束编程的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响.飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP Hard问题.本文把飞机排班问题构建为多商品网络流模型,并应用列生成算法求解;在列生成子问题中,引入约束编程系统实现快速求解航班连线（航班串）并计算各航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性,并与航空公司实际排班进行比较研究.     

考虑多因素的不正常航班飞机计划恢复模型

为降低不正常航班给航空公司带来的负面影响,提出了一个以加权成本最小为目标的考虑 多个影响因素的不正常航班飞机计划恢复模型。模型目标函数考虑的因素包括航班延误与取消、飞机维护以及航班运行过程中与飞机和机场相关的各项改变,并且在约束条件中考虑了过站时间 等因素。针对所提出的模型设计遗传算法进行求解。基于大规模航班数据设计算例对模型和算法进行验证,研究结果表明：遗传算法适用于求解所提出的模型;通过对模型求解可以得到合理的 飞机计划恢复方案;除机场关闭之外,飞机维护任务、过站时间等因素对于航班的执行具有重要影响,因此在飞机计划恢复问题中应该考虑多方面的因素。算例结果证明了模型和算法的正确性 和有效性。     

飞机排班一体化模型与算法研究

为了改善航班计划两阶段完成的次优性,将机型指派、路线选择与机尾号指派综合考虑,构建了飞机排班的整数规划与约束规划杂交一体化模型.通过设计了一种基于约束编程思想的列生成算法对该问题进行求解.最后,通过航空公司实例数据验证了模型算法的正确性和有效性.     

基于延误传播的飞机排班一体化鲁棒优化模型

为了减少航班延误对航班运行计划的影响,在分析航班延误传播特性及其分布的基础上,以总波及延误时间最少和航空公司运营成本最小为优化目标,建立了双目标飞机排班一体化网络流鲁棒优化模型.将该模型应用于国内某航空公司的实际运营数据进行实例分析,利用列生成和分枝定价法求解,结果表明:用本文模型优化后的航班计划使航班延误传播减少了41%;运营总成本比航空公司实际成本减少了11.33%,比没有考虑鲁棒性的飞机排班一体化模型的成本减少了9.93%.      

班轮船舶调度多目标优化模型与蚁群算法

针对班轮船舶调度问题, 在将班轮合理配置到各往返航班上和不存在时间冲突的基础上, 以最小班轮变动成本、最小航线运载量缺口和最小班轮航次总绝对偏差为目标函数, 构造了基于港口时段与往返航班的时空网络, 建立了班轮调度的0-1整数规划数学模型。基于某船务公司实际运载数据, 利用蚁群算法求解模型, 并用邻域搜索技术提高求解效率。计算结果表明: 在运载量满足运营要求的前提下, 班轮运营的日均总变动成本从198 086.3元降低到170 472.2元, 下降了约13.9%;班轮航次数总绝对偏差从4.4次降低到2.4次, 下降了约45.5%, 班轮利用率更加均衡; 运载量缺口仍旧为0。可见, 模型可行, 算法有效。     

过站保障车辆集中式调度的单亲遗传算法

针对飞机过站保障车辆集中式调度问题,提出递阶式编码结构单亲遗传算法.该算法采用保障作业编号构成控制基因染色体、车辆编号构成参数基因染色体,分别体现过站保障作业时序约束和车辆指派规则约束,使算法对问题具有良好的适用性;设计控制基因染色体片段段内换位变异和参数基因染色体片段段间换位变异相结合的遗传算子,并引入车辆可调度能力空间概念提出解码算法,实现对解空间搜索能力优化;以过站保障造成的航班延误惩罚费用和车辆行驶费用之和最小为优化目标,建立算法适应度函数,可衡量过站保障和车辆使用综合效率.采集某机场过站航班数据验证所给算法有效性并对比分析车辆就近指派和使用率均衡两种调度策略,结果表明,算法收敛性良好,且就近指派策略相对于使用率均衡策略,在过站保障延误方面改进较小,但在车辆行驶时间方面改进达40%.      

多跑道航班起降调度优化算法

为了提升大型繁忙机场的运行效率, 考虑了多跑道的运行条件和安全要求等因素, 以最小航班总延误为目标函数, 以最大位置偏移为约束条件, 引入滚动时域控制策略, 建立了航班动态排序模型。针对多跑道航班调度问题的特点, 分别采用基于滚动时域控制策略的遗传算法和现有的先到先服务算法求解模型。计算结果表明: 当航班正常时, 采用现有的先到先服务算法, 航班总延误为1 712s, 采用基于滚动时域控制策略的遗传算法, 航班总延误为1 080s, 与先到先服务算法相比, 延误时间减小37.0%;当航班不正常时, 采用现有的先到先服务算法, 航班总延误为1 658s, 采用基于滚动时域控制策略的遗传算法, 航班总延误为969s, 与先到先服务算法相比, 延误减小41.5%。可见, 基于滚动时域控制策略的遗传算法有效。     

需求不确定状态下的航班机型分配问题研究

机型分配问题是飞机、机组排班问题的基础,是整个航班计划中的关键环节。文章针对市场需求高度不确定的情况,建立了两阶段随机混合整数规划模型,其中第一阶段考虑机族层次的分配,确保每个航节均分配1种且仅有1种机族,第二阶段根据进一步的市场需求信息及预测,考虑每个航节所分配的机族内具体机型的分配问题。针对建立的模型,设计了Benders分解算法,并通过算例验证了该模型较传统确定型模型更具有效性,能够为航空公司的机型分配提供决策支持。     

A Hybrid Heuristics for Irregular Flight Recovery

Adverse weather conditions, congestion at airports, and mechanical failures often disrupt regular flight schedules. The irregular flight recovery problem aims to recover these schedules through reassignments of flights and cancellations. In this article, we develop the classic resource assignment model for the irregular flight recovery problem, and a new hybrid heuristic procedure based on greedy random adaptive search procedure (GRASP) and simulated annealing algorithm is presented to solve this problem. As compared with the original GRASP method, the proposed algorithm demonstrates quite a high global optimization capability. Computational experiments on large-scale problems show that the proposed procedure is able to generate feasible revised flight schedules of good quality in less than five seconds.     

��Ͻ�ͨ������Ƽ����߿�¡�˻��㷨����о�

研究混合交通网络设计问题,以交通网络总阻抗最小为目标,在建设资金的约束条件下给出了双层规划模型。将模拟退火算法中的退火策略引入到免疫克隆算法中,设计了求解模型的免疫克隆退火算法。算例验证了算法的可行性,并通过与模拟退火算法比较证明了设计算法的有效性。最后,在给定不同建设资金的约束条件下进行了灵敏度分析,并讨论了投资成本与网络总阻抗、建设资金约束与网络设计决策的关系。     

Mixed Transportation Network Design Based on Immune Clone Annealing Algorithm

This paper focuses on the mixed transportation network design problem. A bi-level programming model, constrained by investment budget, is developed to minimize the total impedance of transportation network. The immune clone annealing algorithm, which is designed by combining annealing tactic of simulated annealing algorithm and immune clone algorithm, is introduced to solve the proposed bi-level model. Compared with simulated annealing algorithm, the feasibility and effectiveness of the model and the algorithm is demonstrated through a numerical experiment. The sensitivity analysis on different investment budget constraints is provided, as well as the relation between investment cost and the total impedance of network, investment budget constraint, and decision on network design.     

随机需求下公交网络设计的期望值模型与求解算法研究

科学规划公交系统是解决城市交通拥挤问题的有效手段,公交网络设计问题更是公交体系规划的重点与难点。公交需求作为公交网络设计的输入条件,在现实中具有不确定性。鉴于此,假设不确定乘客需求具有随机特性,来研究随机需求下公交网络设计问题的优化方法。以乘客成本与运营成本最小化为优化目标,构建了多目标规划的期望值模型。将遗传算法与模拟退火算法相结合,设计了求解模型的遗传模拟退火算法。最后,通过算例验证了提出的模型与算法的有效性。     

城市交通连续平衡网络设计问题的GASA混合算法

通过建立城市交通连续平衡网络设计问题的双层规划模型,提出的一种基于遗传算法和模拟退火算法的GASA混合算法,经实例验证其与单一算法相比,具有较高的精确度,且最优解的性能指标有很大改善,在解决大型网络设计问题方面具有明显优势。     

Sensitivity Analysis of Simulated Annealing for Continuous Network Design Problems

In this paper, parameters choices of simulated annealing for continuous network design problems are discussed. A bi-level programming model for continuous network design problem is introduced. Objective function of the upper level is defined as the sum of the total travel time on the network and the total investment costs of link capacity expansions. The lower level problem is the user equilibrium assignment model, which is solved by the Gradient projection algorithm. Sensitivity analysis method is the first time used to analyze and compare the influence of the different selection of parameters to the implementation of simulated annealing algorithm. Suggestions of parameter selection are also given. Analysis demonstrates that the efficiency and precision of these methods can be improved clearly with the proposed suggestions.     

�������������������ģ���˻��㷨�����ȷ���

研究了求解城市交通连续网络设计问题的模拟退火算法参数选择原则。采用双层规划模型来描述固定需求下的城市交通连续网络设计问题,其中上层问题的目标函数为整个网络的总阻抗和总投资额之和,下层问题则是用户平衡配流模型。利用模拟退火算法求解上层模型,下层模型则采用基于路径的GP算法进行求解。本文首次采用了灵敏度分析方法分析参数选择对模拟退火算法求解连续网络设计问题影响,比较了各个参数对算法结果及时间的影响,确定了参数的选择原则。根据上述分析方法得到的参数选择原则来设定参数的取值,能够提高算法的执行效率和收敛精度。     

路网最优费率的双层规划模型及算法

为寻求系统、科学的路网最优费率测算方法, 提出用双层规划模型描述路网管理者、收费道路经营者和车辆用户三者在费率决策中的博弈关系, 其中上层以路网用户盈余最大化为目标, 下层是弹性需求下的多车型随机用户均衡模型, 设计了遗传-模拟退火混合优化的求解算法。计算发现路网收费收入目标的高低将直接影响测算所得费率的高低, 进而影响各车型OD出行量, 且时间价值低的车型用户比时间价值高的车型用户受费率变化的影响要更为显著, 表明双层模型在费率决策过程中能兼顾相关各方的利益, 建模时考虑车型分类能更合理地反映现实情况; 与遗传算法、模拟退火算法相比, 遗传-模拟退火算法计算结果最优。     

终端区飞机排序的混合人工鱼群算法

为了保障飞行安全, 对终端区着陆飞机进行有效的排序, 建立了以航班延误总时间最小为目标函数的规划模型, 以人工鱼群算法为基础, 融合了遗传算法的选择操作和模拟退火算法的依概率接受的思想, 形成混合人工鱼群算法, 对着陆飞机排序问题进行了仿真计算, 并与先到先服务算法、模拟退火算法以及蚁群算法进行了对比研究。仿真结果表明: 与先到先服务相比, 使用人工鱼群算法使得单跑道、双跑道延误分别减少了9.3%和48.0%, 计算时间小于3s;与蚁群算法和模拟退火算法相比, 求解的延误与时间最小, 因此, 提出的混合算法可行。     

多级物流配送网络设计的优化模型及算法

由于生产企业单层次的配送网络结构与大范围物流配送存在很大的不适应性,文中提出了一种符合生产实际需要的多级物流配送网络结构设计,由此建立了可以描述一般性多级配送网络设计问题的通用优化模型,并设计了该优化模型的模拟退火算法.算例研究表明,采用该优化方法运算快捷,所得结果合理,能为生产企业的物流配送网络设计提供良好的决策支持.