航空器排列问题的最优排序方法研究

《航空器排列问题的最优排序方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２２卷第５期运筹与管理Ｖｏｌ．２２，Ｎｏ．５２０１３年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１３航空器排列问题的最优排序方法研究李晓亚（中国科学院数学与系统科学研究院应用数学研究所，北京１００１９０）摘要：本文研究了一类航空器排列问题。通过分析n车探险问题及其特例情况，发现n车探险问题为航空器排列问题的一种特例情况，基于此结论，从航空器排列问题的条件结构入手，将n车探险问题特例情况的算法应用到航空器排列问题上，提出航空器排列问题的另一个特例情况，并给出该特例情况下最优排序以及最远飞行距离

2、计算方法。文章最后给出计算实例。关键词：运筹学；动态规划；最优排序方法；航空器排列问题；吉普车问题；n车探险问题；特例情况中图分类号：Ｏ２２１．３文章标识码：Ａ文章编号：１００７-３２２１（２０１３）０５-００２４-０５ResearchonOptimalSequenceofAircraftRangeProblemＬＩＸｉａｏ-ｙａ（InstituteofAppliedMathematics，AcademyofMathematicsandSystemsScience，ChineseAcademyofSciences，Beijing１００１９０，C

3、hina）Abstract：Ｔｈｅａｉｒｃｒａｆｔｒａｎｇｅｐｒｏｂｌｅｍｉｓｄｉｓｃｕｓｓｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｂｙｉｎｔｒｏｄｕｃｉｎｇａｋｉｎｄｏｆｅｘｐｌｏｒａｔｉｏｎｐｒｏｂｌｅｍｗｉｔｈｎｖｅｈｉｃｌｅｓ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓｔｈａｔｎ-ｖｅｈｉｃｌｅｅｘｐｌｏｒａｔｉｏｎｐｒｏｂｌｅｍｉｓａｓｐｅｃｉａｌｃａｓｅｏｆａｉｒｃｒａｆｔｒａｎｇｅｐｒｏｂｌｅｍ．Ｂａｓｅｄｏｎｔｈｅｃｏｎｓｅｑｕｅｎｃｅ，ａｎｄｂｙｃｏｎｓｉｄｅｒｉｎｇａｓｐｅｃｉａｌｃａｓｅｔｈａｔｐｒｏｖｅｓｓｏｌｖａｂｌｅｏｆｎ-ｖｅｈｉｃｌ

4、ｅｐｒｏｂｌｅｍ，ａｋｉｎｄｏｆｓｐｅｃｉａｌｃａｓｅｏｆａｉｒｃｒａｆｔｒａｎｇｅｐｒｏｂｌｅｍｉｓｏｂｔａｉｎｅｄ，ａｌｏｎｇｗｉｔｈｔｈｅｃａｌｃｕｌａｔｉｏｎｍｅｔｈｏｄｆｏｒｏｐｔｉｍａｌｓｅｑｕｅｎｃｅａｎｄｔｈｅｇｒｅａｔｅｓｔｆｌｉｇｈｔｄｉｓｔａｎｃｅ．Ｎｕｍｅｒｉｃａｌｅｘａｍｐｌｅｓａｒｅｄｉｓｐｌａｙｅｄａｔｌａｓｔ．Keywords：ｏｐｅｒａｔｉｏｎａｌｒｅｓｅａｒｃｈ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇ；ｏｐｔｉｍａｌｓｅｑｕｅｎｃｅ；ａｉｒｃｒａｆｔｒａｎｇｅｐｒｏｂｌｅｍ；ｊｅｅｐｐｒｏｂｌｅｍ；ｎ-ｖｅｈｉ

5、ｃｌｅｓｅｘｐｌｏｒａｔｉｏｎｐｒｏｂｌｅｍ；ｓｐｅｃｉａｌｃａｓｅ０引言［１］航空器排列问题是一种经典的队伍排列问题（ｆｌｅｅｔｒａｎｇｅｐｒｏｂｌｅｍ），最早由Ｆｒａｎｋｌｉｎ提出，具体描述为：设有n架航空器组成的飞行队伍｛A１，A２，⋯，An｝，其中Ai最多可带gi加仑（ｇａｌｌｏｎｓ）的燃料，且每英里（ｍｉｌｅ）消耗燃料为ri（ｇａｌｌｏｎｓ）（i＝１，２，⋯，n）。假设航空器可以在途中相互补充燃料，而且可以在途中任意地点抛下任意一个航空器。问如何安排飞行计划，使该飞行队伍实现最远的飞行距离。初始情况下，假设该飞行队伍共有ｇ加仑的燃料可

6、供使用。［２］该航空器排列问题与著名的吉普车问题有很多相似性，后者类似于在二战期间给中国战区运输物资时所遇到的问题，吉普车问题可应用在探险和星际旅行等方面，例如：长距离运输，多级火箭燃料，行军［３］路线，攀登问题等。文献［４］证明了吉普车问题其实是航空器排列问题的一个特例情形，并具体分析了这两种问题的共同点。吉普车问题以及航空器排列问题长期以来得到密切的关注，并衍生出许多有趣的［１～７］变形。针对吉普车问题的求解，普遍采用的是一种类似于“蚂蚁搬家”的算法，其本质上利用的是［３］Ｂｅｌｌｍａｎ的动态规划原理。航空器排列问题作为吉普车问题的一种更为

7、一般的情况，已有文献在求解收稿日期：２０１２-１１-０５基金项目：中国科学院管理、决策与信息系统重点实验室支持作者简介：李晓亚（１９８２-），女，助理研究员，博士，研究方向：运筹学，优化算法与决策分析。第５期李晓亚：航空器排列问题的最优排序方法研究２５［１，４］它时主要采用的也是动态规划方法。利用动态规划原理可以构造求解问题的递归迭代公式，进而给出航空器排列问题最优解的性质描述，利用该递归公式进行求解，为寻找问题的最优解提供了迭代搜索的方向，但大多数情况下对应的计算时间复杂度是指数级别的。在利用动态规划原理求解航空器排列问题的最优排序时，只是套

8、用了动态规划迭代公式，而忽略了航空器排列问题本身在条件结构上有用的信息，这些信息在已有研究中未被提及或强调。另一方面，通过分析航空器排列问题的最远飞行