《不相容货物混装运输问题研究》.docx

中南大学数据库实践论文不相容货物混装运输问题研究制定执笔者：江南审核者（教研室主任或研究所所长）：批准者（教学院长）：交通运输1002班马海铭1104100713一摘要本文主要研究相容货物混装运输问题，首先介绍了该类问题的相关知识，而后采用枚举的方法，通过建立0-1规划模型，设计了启发式算法，结合相关条件限制，减少了运算量，规避了枚举法的部分缺点，基本解决了该类情况的最优解问题。二关键词混装货物 铁路运输 运输管理 货物运输三概述12345图1 最大团示意图随着经济社会的发展和产业结构的调整，在铁路运输中，大宗货物运输的比重正逐步降低，而具有高技术含量、高附加值、重量轻、体积小、批数多特征的原属零担货物范畴的市场份额呈增长趋势。为此，混装货物运输获得较大发展。但是，目前混装货物作业计划仍然主要靠货运员人工编制。车站货运员凭借工作经验，根据货物的形状(质量与形态)和受理运单的组成，配装成各种整零车。由于集配计划涉及因素多，工作量大，人工编制不仅繁琐、费时，而且货车载重量难以保证充分利用。由零担货物混装隔离限制的研究可知，混装货物装配方案的最优解一般应优先考虑货车净载重最大，并在此基础上充分考虑利用车辆容积的方案。固本文仅考虑净载重，容积暂不做考虑。而且为了简化实际问题，本文不考虑同一种货物分批次运输问题和因装车数量不同而导致货物种类情况相同的不同方案之间载重量不同的问题。若能通过改进零担货物的配装方法，充分利用车辆的载重量，便可有效提高货车静载重，加快零担货物的输送。随着计算机在铁路系统的广泛应用，利用计算机进行辅助决策，编制合理的配装计划已成为可能。本文从货物相容问题入手，采用枚举的方法，通过建立0-1规划模型，设计了启发式算法，结合相关条件限制，获得了混装货物的最优算法，使得车辆载重利用率大大提高，加快了混装货物的运输，提高了效益。四问题背景按照货物运输要求，某些货物相互之间是不能混装的，如肥皂与大米。设所有适运货物有种（典型值），划分为类（典型值），称为货物品类。假设货物之间能否混装完全取决于相应货物品类能否混装，能够相互混装货物品类，称为相容，反之称为不相容。货物品类之间的相容关系可表示为相容矩阵，其中。今有种货物，货物个数为，每种货物单个重量为。给定一辆车，载重为，试制定装载方案，尽量满载此车。五问题分析不相容货物混装运输问题极为复杂，在这种有着多个条件的问题中，首先要满足最基本的约束条件；其次，要找出判定货物不相容的条件和相应的算法；最后才是对运输的分组组合进行计算和分配，找出最优的分组方案。首先是基本约束条件，本次问题的基本约束条件是每个分组中的货物总重不可以超过货车的载重上限。其次是货物不相容的判定条件。货物品类之间的相容关系具有自反性、对称性，但不能断然推断具有传递性，故不是等价关系。如图1所示。12345图1 最大团示意图上述货物品类相容关系图包含若干个完全子图。如果用团来称呼完全图，那么该相容关系图中存在若干独立最大团，最大团中的货物品类完全可以相互混装。尽管整个货物品类中的相容关系不是等价关系，但最大团内部的相容关系却是等价关系，因为不但具有自反性、对称性，而且传递性也是成立的。不过最大团内部的等价关系是一种极端情况，即所有成员相互等价，整个最大团仅能划分为一个等价类。一般情形下，所有独立最大团相互之间有成员重叠（集合相交）。极端情况下，当这些最大团蜕化为相互间没有任何成员重叠时，整个货物品类集合即可划分为若干等价类，每个等价类对应一个最大团。此时所有货物品类间的相容关系蜕变为等价关系。最后计算载重的浪费，选取利用率最高的方案。六数学模型其中，七算法分析本问题的核心是货物不相容条件的判定，理论上是一个在约束条件下的目标优化问题。故而设计使用多循环最优解算法。流程如下：Y初始化对所有货物品类编号：1、2、Mi=1,取第i个货物品类放入集合At=1选取集合A，将集合A中的元素与第i+1，i+2，M个货物作比较，如果A中的元素与其全相容，则将其放入A中，构成新的集合Bj（j=1,2,M）合并所有相同的BjtM-2Nt=t+1且将集合Bj依次用集合A来表示iM-2i=i+1YN超出标记载重的方案所含有的元素数NN从这个方案中删除一个元素Yf=F=min f输出f=F的Bj，即为最优方案八方法分析枚举法的算法设计简单明了，而且极为严谨，可以找到最佳的分装模式，缺点是计算量极大，占用资源极多，且耗时较长。九算例分析S=1 1 1 1 01 1 1 1 11 1 1 1 11 1 1 1 10 1 1 1 1N=1,2,3,4,5W=1,2,3,4,5G=30经运算得最大团B1=1,2,3,4 B2=2,3,4,5，则f1=G-B1niwi+G-剩余niwi=5 f2=G-B2niwi+G-剩余niwi=6则F=min f=f1=5，所以最优方案为B1=1,2,3,4，即第一、二、三、四类货物混装运输，第五类货物单独运输。十结论关于相容货物混装运输问题，本文仅考虑净载重，容积暂不做考虑。而且为了简化实际问题，本文不考虑同一种货物分批次运输问题和因装车数量不同而导致货物种类情况相同的不同方案之间载重量不同的问题。在此基础上采用了枚举的方法，通过建立0-1规划模型，设计了启发式算法，结合相关条件限制和数据合并即删除，减少了运算量，规避了枚举法的部分缺点，基本解决了该类问题。随着电子计算机在铁路系统的逐步广泛应用，该系统的应用前景将越发广泛。参考文献： 牛荫鸿，李致中. 零担货物混装隔离限制的研究J. 铁道科学与工程学报，1993，02：812.江南，史峰，任少卿. 铁路承认车最优