一种求解航空货代拼箱问题的启发式算法

《一种求解航空货代拼箱问题的启发式算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第28卷第7期计算机应用研完V01．28No．72011年7月ApplicationResearchofComputersJul．2011一种求解航空货代拼箱问题的启发式算法桂云苗，龚本刚，程幼明(安徽工程大学管理工程学院。安徽芜湖241000)摘要：为了有效求解大规模的航空货代拼箱决策问题，在拼箱问题的混合整数规划模型基础上，将模型转换为集合覆盖问题，利用常用的拉格朗日松弛方法，提出了一个拼箱问题的启发式求解方法，并给出了修正不可行解的方法和拼箱组合空间调整方法。数值分析结果表明，该启发式算法是有效可行的，而且运算效率比较高，与最优解间误差比较小。关键词：交通管理；拼箱；

2、航空货代；集合覆盖；启发式算法中图分类号：TP301．6文献标志码：A文章编号：1001—3695(2011)07·2446—03doi：10．3969／j．issn．1001-3695．2011．07．011HeuristicalgorithmforconsolidationproblemofaircargoforwardersGUIYun—miao，GONGBen—gang，CHENGYou·ming(CollegeofManagement肠和嘲，AnhuiPdytechnic‰妙，吼抽Anhu／241000．China)Abstract：Inordertosolver

3、ealisticallylarge·scalecargoconsolidationproblems，thispapertransformedtheaircargoforward—ersconsolidationproblemtowell—knownsetcoveringproblembasedonmixedintegerpro伊ammingmodelandusedLagrangiaaRelaxationtodeveloparecursiveheuristicalgorithm。anddiscussedtheproblemsoffeasiblesolutiondetermin

4、ationandsetad·justment．Testedanumericalexperiment．Theresultsshowthatthealgorithmisfeasiblewithhighcomputingefficiency，andthegeneratedsolutionsisveryclosetooptimalsolution．Keywords：tll盛cmanagement；freightconsolidation；aircargoforwarders；setcovering；heuristicalgorithm随着世界国际贸易自由化和全球物流的发展，全球航空

5、货运已经进入蓬勃发展阶段。根据波音公司预测⋯．未来20年全球航空货运年均增长率达到6．3％，比航空客运高出2—3个百分点。中国航空货运发展尤为迅猛，未来将以10．6％的速度持续增长。为了满足中国航空货运的增长需求．提高整个航空货运流程的效率是目前急需解决的问题。因为国际航空货运的经营涉及到货代、机场、海关、航空公司等多方参与者，操作程序也比较复杂，所以相应的管理决策问题相当多而且比较复杂。在众多参与者中．航空货代在整个航空货运流程中扮演着重要的角色，一方面是货主的服务供应者．直接影响着航空货运的成本与顾客满意度；另一方面是航空公司的消费需求者。航空货代的收入一方面来自货物进

6、出口手续代办的佣金；另一方面通过对货物进行拼装，以获得向货主收取运费与航空公司提供费率之间的差价。由于目前航空货运的运价体系同时考虑货物的重鼍和体积，而且运价还有数量折扣，因此航空货代在满足顾客要求的前提下，对货物进行有效的拼装，降低支付给航空公司的运费是一个非常复杂的问题．目前有部分专家和学者研究航空货代的拼箱问题。Jaeger{2’在考虑航空公司航线网络运费成本的基础上，研究了货物运输路线和货物拼箱问题。但未考虑货物实际重量与计费重量之间的转换。Xue等人¨1对香港航空货代的拼箱问题进行了研究，建立了集装箱租赁和货物拼箱的混合整数规划模型。Wu【．1同时考虑航空运价体系

7、的莺量和体积，建立了货物拼箱的混合整数规划模型。国内也有少数专家研究货物拼装问题，但大部分的研究内容集中在海运集装箱的拼装箱问题‘5。1。1问题描述1。1航空货代拼箱的特性民航的航空运价体系同时考虑了重最和体积，即将货物的体积按照标准密度转换成体积重量．比较货物的实际重量和体积重量，取其最大者作为运费的计费重量。目前IATA推荐使用的标准密度为1／6re／立方米。因而航空货代的拼箱过程就是将密度较大的货物与密度较小的货物进行合并，调整货物整体的密度，能够有效地降低支付给航空公司的总运费。航空公司为了促进货代企业大力