基于混合模拟退火算法的航空公司勤务编排算法研究

《基于混合模拟退火算法的航空公司勤务编排算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京航空航天大学硕士学位论文基于混合模拟退火算法的航空公司勤务编排算法研究姓名：宋静波申请学位级别：硕士专业：交通运输规划与管理指导教师：夏洪山20090101南京航空航天大学硕士学位论文摘要本文以航班优化及航线经济效益分析系统(FORMAX)为应用背景，对机组排班中的勤务编排问题进行研究，通过优化勤务编排的算法得到正确、合理、高效的勤务。本文将勤务编排分成可行勤务的产生和勤务优化两个子问题进行研究。在分析了勤务编排规则的基础上，给出了分层次的勤务编排模型及各项优化指标。并为了得到最佳优化效果，综合平衡了各

2、项目标函数的权重；然后总结分析了启发式算法和最优解算法的适用性，明确了启发式算法在解决大规模数据量问题时的优势。同时通过对遗传算法和模拟退火算法的仿真比较实验，论证了模拟退火算法较遗传算法具有更高的局部搜索能力；在算法设计阶段，将深度优先算法应用于可行勤务产生的过程中。本文重点研究勤务优化问题，在候选勤务集合中进行初步筛选得到初始勤务，并在初始解的基础上，分析模拟退火算法在解的邻域内寻找最优可行勤务的过程。针对模拟退火算法随机筛选过程中的不足，引入了一种启发式操作，保证了最优解的可行性。最后通过对算法的初步

3、筛选效能、敏感度、时间复杂度、优化效果等角度的比较分析，验证了模拟退火算法产生勤务的高效性。关键词：勤务编排，启发式算法，模拟退火算法，遗传算法，局部搜索I基于混合模拟退火算法的航空公司勤务编排算法研究AbstractThethesispresentsanalgorithmforthedutyplanningoptimizationontheapplicationbackgroundofFORMAX.Itaimstofindanavailableandefficientsolutiontothedutypl

4、anningproblembyimprovingthealgorithmsthatareused.Thethesissplitsthedutyplanningproblemintotwosub-problems:dutygenerationanddutyselection.First,onthebasisofairlinesregulationsandlimitations,thethesisusessub-levelstoconstructdutyplanningmodels,thenanalyzesth

5、eoptimalindex,andbalancesalltheobjectivefunction;second,afterdiscussingtheperformancesofheuristicalgorithmsandexactalgorithms,thethesisdiscoversthatheuristicalgorithmismoreefficienttosolvelargescaleproblems.Bycomparingdifferentperformancesofgeneticalgorith

6、mandsimulatedannealingalgorithm,theconclusionisthatsimulatedannealingalgorithmisgoodatlocalsearch;atlast,thethesisappliesDepth-firstalgorithmtogenerateinitialdutyset,thenusesconstructivealgorithmtogettheinitialduty.Byapplyingsimulatedannealingalgorithm,fea

7、sibleandbestsubsetisselectedamongtheinitialsetoffeasibleduty.Furthermore,inordertoensureallthesolutionsarefeasible;theheuristicoperationisexploredtotransferalltheinfeasiblesolutionsintofeasibleones.Aconclusionisreachedthattheuseofthiskindofalgorithmscanach

8、ievetoobtaingoodresults.Keywords:dutyplanning,heuristicalgorithm,simulatedannealingalgorithm,geneticalgorithm,localsearchII南京航空航天大学硕士学位论文图表清单图1.1传统排班流程及其影响.....................................................