航空货运装载问题算法设计与研究.pdf

第31 卷 增 刊 计 算 机 工 程 2005 年7 月 Vol.31 Supplementary Issue Computer Engineering July 2005 ·民航信息系统研究与设计· 文章编号：1000—3428(2005)增刊—028—03 文献标识码：A 中图分类号：TP391 航空货运装载问题算法设计与研究 张 劼，衡红军，杨晓雪 (中国民用航空学院计算机学院，天津 300300) 摘 要 ：用回溯算法解决飞机货舱装载问题。根据货物和舱位情况，使货舱的空间和载量利用最大化。对于航空货物体积小重量轻的特点， 给出一种改进算法，通过理论分析，这些方法可以有效解决该问题。 关键词：票；约束函数；限界函数； 回溯算法 Design and Research for Algorithm of Air Cargo Loading Problem ZHANG Jie, HENG Hongjun, YANG Xiaoxue ( Computer Science College, Civil Aviation University of China, Tianjin 300300) 【Abstract 】Air cargo loading problem by backtrack algorithm is solved. It can maximize the capacity of space and load,according to the instance of the cargo and hold.In terms of the property that air cargo commonly has small volume and light weight. It gives an improving algorithm. From theoretic analysis,the problem can be effectively solved by this algorithm. 【Key words 】Bill; Constraint function; Bound function; Backtrack algorithm 航空运输有其局限性。主要表现在：飞机的舱容有限， wi :第 i 票货物的单件重量； 对大件货物或大批量货物的运输有一定的限制。目前，国内 vi :第 i 票货物的单件体积； 航空公司的飞机以中小型为主，以波音 757 机型为例，即使 cijk :第 i 票第 j 个货物装在舱位 k 。 其 4 个舱全装货物，也只能载 10 多吨，运力跟中型卡车差 目标函数： 不多。所以，如何在飞机有限的空间里，尽可能多地装入不 重量最大化： 超过飞机限重的货物，是一个很关键的问题。 n max ∑ cijk wi 1 模型的建立与分析 i,j ,k 1 需 要 考 虑 的 因 素 ： （1） 货 物 是 否 可 以 分 批 ， 即 体积最大化： 同 一 票 货 物（一票货物是指凭一份航空货运单运输的运往