（安全技术及工程专业论文）行李车货物装载方法研究.pdf

j 塞蛮道盍堂亟堂焦i 金塞旦sib 至 a b s t r a c t a b s t r a c t ：a l o n gw i t ht h ef i v eb i ga c c e l e r a t i o n st h es p e e do ft h ep a s s e n g e rt r a i n i n c r e a s e ss t e pb ys t e p ，h o wt oe n s u r et h es a f e t yo ft h el u g g a g ev a nb e c o m e sa n i m p o r t a n tp r o b l e mu r g e n t l yt os o l v e m o r e o v e r ，t h ee x p r e s st r a i nw a ss t a r t e do nm a y 18 “2 0 0 4 u n d e rh i g hs p e e dr u n n i n gk e e p i n gt h es a f e t ya n ds t a b i l i z a t i o na l s oi sa l l i m p o r t a n tp r o b l e m t h es a f e t ya n ds t a b i l i z a t i o no ft h el u g g a g ev a nw i l ls t r a i g h t l y i n f l u e n c et h es a f e t yo f t h ep a s s e n g e rt r a i n t h e r ea r em a n yf a c t o r st oi n f l u e n c et h es a f e t yo ft h el u g g a g ev a n ，o fw h i c ht h e f r e i g h tl o a d i n gs t a t ea n ds t o w a g ea r et h em o s td i r e c tf a c t o r s w i t ht h ev a r i e t yo ft h e t r a n s p o r tm a r k e td e m a n dt h ew e i g h to ft h el u g g a g ei n c r e a s e dg r a d u a l l y a tt h es a m e t i m ep a r to ft h el e s s - t h a n - c a r l o a dl i g h td i s t r a c t e dt op a c k a g et r a n s p o r t 、i 廿lt h ed r o p o f fa n dc a n c e l l a t i o no ft h el e s s t h a n c a r l o a df r e i g h t a g e i tb r o a d e n e dt h ek i n d so ft h e f r e i g h ta n de n h a n c e dt h et r a n s p o r td e m a n d a l lt h et h i n g sr e s u l t e di nt h ec o m p l i c a t i o n o ft h es t o w a g e i ti st i m et os e tu pas u i to fs c i e n t i f i ca n dr a t i o n a ll o a d i n gm e a s u r e st o e n s u r et h es a f e t yo fl u g g a g e t h i sp a p e rs t a r t e df r o mt h ea n g l eo fl u g g a g el o a d i n ga n ds t u d i e do nt h ef r e i g h t s t o w a g eo ft h ec o m m o nl u g g a g ev a na n de x p r e s st r a i n b a s e do nt h er e s e a r c ho ft h e f r e i g h tl o a d i n gs t a t u s ，t h ea u t h o ra n a l y z e de x i s t i n gp r o b l e ma tp r e s e n t ，s e tu pt h e o p t i m a lm a t h e m a t i c a lm o d e la f t e rc o m p a r i n gd i f f e r e n to p t i m a la l g o r i t h m sa n dd e s i g n e d c o r r e s p o n d i n ga l g o r i t h m f i n a l l yt h ep a p e rp r o v e dt h ev a l i d i t yo ft h ea l g o r i t h mb y e x a m p l e k e y w o r d s ：e x p r e s st r a i n ；s a f e t y ；l u g g a g ev a n ；l o a d i n g ；g e n e t i ca l g o r i t h m c l a s s n 0 ：u 2 9 4 3 ：u 2 9 8 1 致谢 本论文的工作是在我的导师孙全砍教授的悉心指导下完成的。几年来孙老师 无硷在学习还是生活上都给了我蔓大的帮助。导师治学严谨、待人温和，渊博的 学讽，独到的学术见解以及对工作的全身心投入都将影响和激励我今后的工作和 学习。在此衷心感谢三年来孙老师对我的关心和指导，向导师致以深深的谢意和 诚挚的祝福! 在论文的完成过程中，刘作义教授、 的内容都提m 了很多宝贵的意见和建议， 心指导和帮助。 李笑红教授以及张璃老师从开题到论文 感谢德们在学术和科研项目上对我的热 在论文撰写期间，王理达、冯枫等同学对我的论文研究工作给予了热情的帮 助，在模型的建立和求解过程中多次提出建议，在此向他们表达我的感激之情。 论文的完成过程中应用了大最的参考资料，如果没有这些学术上的前辈们的 智慧，我将滩以完成这篇论文。在此，特别向所有参考文献的作者和文献的出版 者致以衷心的感谢! 同时还要感谢其他老师以及各位同帮好友给我的大力支持和热心帮助! 最后我甍特别感谢我的父母，是他们的默默关心、支持和鼓励囊陪伴着我， 帮助我克服各种困难，顺刹完成学业。 1 1 本文的研究背景及意义 1 绪论 随着铁路的五次大提速，许多旅客列车的速度已经达到1 6 0 k m h 。旅客列车挂 运行李车作为行包运输组织方式之一，随着列车速度的提高，如何保证行李车的 运行安全成为亟待解决的一个重要问题。否则行李车一旦出现了问题，将直接影 响旅客列车的安全。此外，中铁行包快递有限责任公司成立后，除了继续采用旅 客列车挂运行李车来运送行包外，于2 0 0 4 年5 月1 8 日开始组织开行了整列装载 行李、包裹和邮件的行邮专列，该专列由新型的x l a ，r 行李车组成，速度也达到了 1 6 0 k m h 。在此速度下如何确保行邮专列的安全稳定也成为急需解决的重要问题。 影响行李车运行安全稳定的因素有很多，其中行包在车内的装载方法和状态 直接影响着行李车的运行安全稳定。过去，行包运输只是旅客运输的附加产品， 运量较小，且主要以行李为主，单件重量小于5 0 k g ，属于轻浮货物。随着行包运 输市场需求的变化，现在行包运输的货物品类逐步转变为以包裹即小件货物为主。 超重包裹的单件重量采用旅客列车挂运行李车的方式可以达到2 0 0 k g ，采用行邮专 列方式可达到3 0 0 k g 。同时，随着铁路零担货物运输的逐渐减少和最终取消，部分 零担货物也将逐渐转移到行包运输上来，使得行包运输的货物种类进一步扩大， 运输需求进一步增加。由于行包单件重量的提高，行包的装卸方式要求由原来的 人力装卸转变为机械化装卸，特别是旅客列车提速后，在途停站时间越来越短， 为了在规定的停站时间内完成行包的装卸作业，必须使行包运输集装化及装卸机 械化。同时为了提高行邮专列的装卸效率，也必须采用机械化装卸。另一方面， 为了适应行包运输货物种类的变化及组织方式的多样化，提高服务质量，新型的 行李车也投入了运用。行包货物种类的扩大、装卸方式的改变及行李车种类的增 加，导致装载方法的复杂化，这就需要制定一套与之相适应的科学合理的行李车 装载技术条件和方法，以保证行包运输的安全。 本文就是从行包装载的角度出发，对旅客列车加挂行李车以及行邮专列的装 载方法进行研究，考虑行包装载时的各种影响因素，建立优化行包装载数学模型， 并设计相应的算法，从而更好地解决实际中存在的问题。 1 2 国内外货物装载研究现状 1 2 1 国外货物装载研究情况 对于货物装载问题，国外于上个世纪六七十年代就开展了一定的研究，之后 相继出现了一些经典的算法，各种算法各有特点和侧重，目前常用的方法有数学 规划法、图论法、启发式算法等。 g e h r i n g i 】提出按阶段填充、在深度方向按层布局的启发式算法，不仅考虑了 空间利用率，而且考虑了重心平衡。 c h r i s t o f i d e s 和w h i t l o c k 2 1 提出了一种利用树搜索来解决布局中一刀切问题的 算法。该算法将动态规划和运算规则融于树的搜索中，通过施加“使布局模式最 优化”这一限制条件来缩小树的大小，适用于中等规模的一刀切问题优化布局方 案的确定。 m 锄c h p j 设计树搜索算法，理论上对三维箱体布局有效，但由于三维箱体 布局属n p 完全问题，随着布局箱体增多，解空间暴增，计算效率较低。 1 2 2 国内货物装载研究情况 就国内而言，对于货物装载问题研究开展的时间较短，对该问题的研究比较 少，由于其涉及到不同学科领域，所以理论研究相对薄弱，下面就国内的一些研 究情况作简要介绍。 姜义东、查建中 4 1 等人针对集装箱内货物装载布局问题，提出一种利用三叉树 结构来表达三维矩形物体布局状态空间分解的方法。通过将布局空间依次分割， 每次放入相对于当前布局空间来说是满足特定条件的最优布局块，并将该布局块 定位于当前布局空间后部的左下角来完成不同大小三维矩形物体的布局方案的确 定，给出试验结果。经过算例比较，说明其有效性。基于该算法，在大量数值实 验的基础上，定量地表达了空间利用率、待装货物总体积和待装货物类型数三者 之间的关系，对集装箱货物运输有一定借鉴作用。这种方法虽然避免了空间干涉 现象，但无法处理更复杂的约束，如后到先放、尽量平铺、重心约束等，这些约 束往往是至关重要的。 何大勇 s i 等在姜义东研究的基础上运用遗传算法做了改进，其优点是能处理多 目标、多约束的问题；缺点是在货物很多时，应用遗传算法对每件货物进行整数 编码构成的染色体，基因数量多，规模巨大；加上众多约束条件，导致算法收敛 非常慢，甚至大多数情况下得不到可行解。 2 潘俊杰、王一新f 6 j 在研究中通过探讨在行包体积和重量的约束下利用遗传算法 求解铁路旅客行李车的配装问题。通过体积和重量的关系将问题转化为一维背包 问题。在遗传算法的评价函数中考虑了货物的优先等级，即利用运输货物的时效 性来确定优先级来进行计算。该方法能够在很多货物中选取出适合条件的货物装 入行李车中，但是货物只给出重量并不一定能够保证轻重搭配，选取的货物有可 能装不进行李间的指定区域。 尹传忠、卜雷1 7 】等人结合行包运输行李车三维装载优化问题的具体特点，建立 其优化数学模型并提出应用遗传算法进行求解，以获得行包装载优化方案，达到 充分利用行李车装载质量或容积的目的。该算法能够在获得优化解的同时缩短计 算时间，能够在满足各种约束下按装车优先级合理地装在行李车中，达到目标。 但是按照文中所指地行李间的装载区域与目前现有的行李车内装载区域并不能完 全一致，实现的装载结果并不能满足装载在行李车的有效装载区域中。 阎威武【8 】等人在研究集装箱装载时通过考虑一些实际应用中的约束条件，提出 了一种三维集装箱装载的启发式算法。在算法中采用了三空间分割、平均高度装 载、货物合并、空间合并等策略，考虑了方向、重量、优先顺序等约束条件，逐 步淘汰差的装载方案，最后达到满意的实载。 10 2 3 目前研究存在的问题 目前对行李车的货物装载问题的研究较少，主要研究集中在对集装箱、托盘 以及零担货物的装载方面。虽然对于装箱问题研究的较多，但是主要是针对一维、 二维的装箱问题的研究，对三维的装载问题研究较少，究其原因一是一维、二维 装箱问题有着大量的实际应用背景，二是由于三维装载问题复杂性和难度都较大， 且目前的研究算法都是基于一定的假设下进行，对于实际中带有复杂约束条件的 应用还存在一定的困难，因此要求对货物的装载进行进一步的研究，充分考虑现 实的多目标、多约束情况，以更好的解决现场实际的操作。 10 3 本文的研究目标及主要内容 1 3 1 研究目标 通过对目前各种行李车内行包货物的装载方式的研究，以及对新开行的行邮 专列进行深入的研究，构建起能够有效改善目前行李车装载现状的一种可行的方 法，从而提高行李车装载的效率以及行李车的安全稳定性。 3 1 3 2 研究内容 本文的主要研究内容包括求解装载问题的方法研究、行李车及行邮专列装载 现状研究、旅客列车加挂行李车内货物装载方法研究、行邮专列行李车内行包装 载方法研究等等。 ( 1 ) 求解装载问题的方法研究 在第二章中，首先对启发式算法作了概述，然后介绍了在装载问题中经常用 到的一些算法，并对其性能作了简单分析，之后着重介绍了遗传算法的理论。 ( 2 ) 行李车及行邮专列装载现状研究 在第三章中，对北京、上海等地几个比较典型的车站以及行包基地的货物装 载情况的现状简要介绍，阐述了我国目前普通行李车以及行邮专列中行包运输的 情况，并对其中存在的一些问题进行了分析说明。 ( 3 ) 旅客列车加挂行李车货物装载方法研究 在第四章中，根据普通行李车待装货物的性质和特点，对旅客列车加挂行李 车的货物装载优化方法进行研究，建立货物装载优化数学模型，并针对模型的约 束条件构造适合求解模型的相应的遗传算法，从而有效地完成行李车货物的装载。 ( 4 ) 行邮专列行包装载方法研究 在第五章中，基于行邮专列的特殊性质以及行邮专列待装货物的特点，建立 适合行邮专列货物装载优化的数学模型，并构造相应的遗传算法对模型进行求解， 形成行邮专列货物装载的优化方法。 1 4 本文的研究方法及技术路线 1 4 1 主要研究方法 在研究过程中，基于装箱理论并借鉴针对具体问题，如零担货物选择装箱问 题、集装箱配载问题、普零货物车辆配装问题以及二维装载优化问题、三维装载 优化问题等的研究方法，结合行李车装载货物的性质和包装特点建立装载优化数 学模型。同时针对优化数学模型，构造求解模型的有效算法遗传算法，设计 针对具体问题具体特点的解结构个体编码表示方法、判断解方案优劣程度的评价 函数、使算法得到优化迭代的遗传算子等，并通过实例计算对模型和算法的有效 性和可行性进行验证和分析。 1 4 2 研究技术路线 本文在研究采取如下技术路线，首先对行李车货物装载现状进行总体研究分 析，找出其中存在的问题，然后再对两种不同方式行李车的装载实现过程分别进 行研究。 对于两种不同的行李车运用模式，分别先根据各自待装载货物的特征和性质 来确定应采取的装载方法，建立相应的优化装载模型并构造求解模型的有效算法， 最后结合实际应用的范例对所建立的数学模型及算法进行有效性和可行性验证。 2 装载问题中的算法应用 在求解优化问题的过程中，按照对可行解空间进行搜索的搜索策略，将求解 优化问题的主要搜索方法分为三类：枚举法、解析法及随机法。 装载问题是一个典型的n p 完全问题，即在有限的时间内找不到问题的最优 解，用传统的搜索方法求解这类问题。就会出现“组合爆炸”的现象。在实践中， 人们一般用启发式算法来求解，因此从六七十年代开始研究装载问题提出的各种 算法都是近似算法。 启发式算法的严格定义为：考虑某类问题p ，设其所有实例集合为d p ，对于 每一实例，d ，有一个相应的待用解集合s k i ) ，若对任意给定的实例i d p ，算 法a 总能找到一个待用解集o & ( d ，则称算法a 为问题p 的一个启发式算法。 就优化机制与行为来分类，目前装载问题中常用的启发式算法主要分为：经 典算法、构造型算法、计算智能算法和混合型算法等。其中计算智能算法包括； 遗传算法、模拟退火算法、禁忌搜索等方法。 2 1 启发式方法概述 在计算机科学、人工智能、智能工程、运筹学及其它一些工程学科中，我们 经常遇到启发式算法这个词。在不同学科中，对该词的定义可能不同，并且对它 的研究也是分头进行的。但是，通过研究发现，启发式算法具有许多共同的特点。 启发式算法是和问题求解及搜索相关的，也就是说，启发式算法是为了提高 搜索效率才提出的。p e a r lj 1 9 8 4 年在其专著“h e u r i s t i c s ：i n t e l l i g e n ts e a r c hs t r a t e g i e s f o rc o m p u t e rp r o b l e ms o l v i n g ”中对启发式算法进行了详细的讨论。他认为，所谓 启发式算法是指一组指导算法搜索方向的、建议性质的规则集，通常按照这个规 则集，计算机可在解空间中寻找一个较好解，但不能保证每次都能找到较好的解， 更不能保证找到最优解。换句话说，所谓启发式算法就是那些从大量的实验数据 来看，算法的实际计算性能较好，但理论上证明这些算法的最坏解题性能并不好， 或者理论上并不能证明这些算法具有良好的解题性能。 这种算法的本质是部分地放弃算法“一般化、通用化”的概念，把所要解的 问题的具体领域知识加进算法中去，以提高算法的效率。但在实际应用时，效率 也许低的惊人，甚至根本解不出来。但我们为每类问题找出一些特殊规则和宽度 优先法结合起来使用，那结果就可能完全不一样了。 由于启发式算法的设计不依赖于纯数学中优化理论的突破和发展，因此其研 6 究和应用在最近2 0 年来获得了突飞猛进的发展。尤其是在复杂的组合优化问题上， 各种各样的启发式算法更是层出不穷，但正是由于启发式算法缺乏严格的理论推 导和数学证明，决定了它的设计具有很强的随意性及创造性。 段国林、查建 9 1 等人在研究中将启发式算法的设计方法归纳为7 类； ( 1 ) 构造法。一个优化问题的解是由若干个构造元素组成的，构造性启发式 算法通过一个一个地增加解的构造元素来求得一个可行解。“贪婪法”在每一步 都寻找最大的改进，其中包含了大量构造性的启发式算法。在大多数构造性启发 式算法中，直到算法结束才会找到可行解。构造性算法的循环次数与问题解的构 造元素个数成正比，而与解空间的大小无关，因此，其计算速度通常很快。 ( 2 ) 改进法。该算法从一个可行解开始，通过在其邻域内的搜索来改进解的 质量。一般来讲，在整个搜索过程中，解一直处于可行状态。将构造法和改进法 结合起来使用是很常见的，先利用构造法得到初始解，然后利用改进法搜索邻域 内的最优点。 ( 3 ) 数学规划法。该方法在问题的数学优化模型及其精确求解方法的基础上， 修改求解方法以期得到问题有效的启发式算法。 ( 4 ) 分解法。该方法指求解一系列容易求解的小问题，一个问题的输出是下 一个问题的输入，然后将这些解归纳，合并成一个解。许多规划问题的启发式算 法都使用了分解法。 ( 5 ) 分割法。将一个问题分割为几个子问题，然后独立地解决每个子问题， 这些子问题的解再合并成整个问题的解。 ( 6 ) 解空间限制法。限制解的构造，以使问题变得容易求解。在某种意义上， 所有的启发式算法都是限制法。典型的限制法只允许算法在具有特殊性质的解中 搜索。 ( 7 ) 松弛法。这种方法与限制法相反，它是指为了得到容易处理的问题而扩 展解空间。 虽然把启发式算法分为以上7 类，但是在实际应用中很难明确划分使用的是 哪一种方法。根据开发者的经验和技巧可以将上述几种方法结合起来使用。 2 2 装载问题求解方法分类 根据装载问题在各个应用领域的具体特点，结合各领域中的经验，可以设计 出具有领域特色的启发式装载求解算法。现有的大多数装载算法都是启发式的， 它的设计充分发挥了设计者的创造性，启发式装载算法设计简单，灵活，计算速 度快，是目前最重要的一种实用的问题求解方法。启发式装载求解算法大体分为 7 以下几类： ( 1 ) 数学规划法 数学规划法包括分枝定界法、动态规划法、整数规划法和线性规划法等等。 该方法利用某一优化问题的数学模型，通过修改该模型的精确求解过程而得到有 效的启发式算法。几种方法中分枝定界法应用较为广泛。该方法的基本思想是通 过枚举解空间中的有限个解来获得n p 完全问题的局部最优解。它由分枝和定界两 个步骤组成，分枝用于将规模较大的原始问题逐步分解为规模较小且易于求解的 子问题；定界主要用于评价各分枝的优劣来减小搜索范围。二维切割问题中，“一 刀切”问题是该方法的经典应用。 由于数学规划法在进行问题求解时要将闯题抽象为一定的数学模型，所以当 实际问题涉及到一些不易于用数学模型表达的约束条件时，采用各种近似方法得 到的数学模型往往与原问题产生较大的偏差，影响问题的求解效果，并且当问题 规模增大、解空间急剧增加时，它们的时间复杂性变得很坏。 ( 2 ) 数值优化方法 数值优化方法具有较为成熟的理论和算法，广泛应用于工程设计领域并取得 了许多有效成果。装载问题是它的一个分支，但是数值优化方法依赖于数学模型， 且只能找到局部最优解，它只适用于小规模物体的装箱问题，对于大规模的装箱 问题用数学模型很难描述，即使使用简化的数学模型来描述，由于局部最优解数 目的急剧增加其求解质量也将严重变坏。此外，数值优化方法所得到的解的质量 在很大程度上还依赖于初始解的选择。 ( 3 ) 构造法 装载算法中使用最多的方法是构造性算法。它通过一个一个增加解的构造元 素来求得一个可行解。构造性算法的循环次数与问题解的构造元素个数成正比， 而与解空间的大小无关，因此其计算速度通常很快。 构造法基本上由两类规则组成。第一类为定序规则，用来确定待装物体放入 空问的先后顺序；第二类为定位规则，用来确定每一个物体在空间内摆放的位置。 由于定序规则和定位规则的不同，就产生不同的构造方法。 启发式算法具有简便、灵活和计算速度快的优点，但它的明显缺陷是产生的 解与最优解的差异很难评价。由于构造法对于装箱问题这类复杂的组合最优化问 题具有很强的实用性并能在较短的时间内给出一个令人较满意的解，因此人们还 会进一步加强对构造法的研究。 ( 4 ) 改进法 装箱启发式算法中的另一类算法为改进法。改进法从一个可行解开始，通过 其邻域内的搜索操作如：交换、合并、增加、删除结构元素来改进解的质量。目 8 前的各种求解方法都可以用来作为改进算法。 ( 5 ) 现代优化方法：遗传算法、模拟退火算法 遗传算法是一种基于生物进化原理的搜索算法。在解决高维空间、高复杂度 以及非线性问题的优化中具有全局最优、效率高及易于并行计算等优点，有很强 的解决问题的能力，但也有着收敛速度慢和容易陷入局部最优解的缺点。 由于一般组合优化问题与物质的退火过程具有很大的相似性，因此，模拟退 火算法被广泛的用来解决组合优化问题。在这方面已有一些成功的应用实例，模 拟退火算法可以用来解决连续、离散等优化问题，尤其是解空间状态不良的问题。 尽管模拟退火方法是一种可能得到优化问题的全局最优解的问题求解方法，并且 已经逐步成为用于优化问题求解的通用的方法，但是这是以其极其漫长的退火过 程为代价的。 基于目前国内外对装载问题的研究现状，下文中将着重介绍遗传算法的理论 以及实现技术。 2 3 遗传算法基础理论 2 3 1 遗传算法的发展 遗传算法起源于对生物系统所进行的计算机模拟研究，由美国m i c h i g a n 大学 的j h h o l l a n d 教授及其学生们受到生物模拟技术的启发创造出来，是一种基于生 物遗传和进化机制而适合于复杂系统优化计算的自适应概率优化技术。 2 0 世纪6 0 年代，h o l l a n d 教授提出可以借鉴生物遗传机制，以群体方法进行 自适应搜索来研究和设计人工自适应系统，同时充分认识到交叉、变异等运算策 略在该系统中的重要性。 1 9 6 7 年，h o l l a n d 教授的学生j d b a g l e y 在博士论文中首次提出了“遗传算法一 一词并发表了遗传算法应用方面的第一篇论文，发展了遗传算子并创立了自适应 遗传算法的概念，在个体编码上使用双倍体的编码方法；7 0 年代初，h o l l a n d 教授 提出模式定理( s c h e m at h e o r e m ) 而奠定了算法的理论基础。 1 9 7 5 年，h o l l a n d 教授出版了第一本系统论述遗传算法与人工自适应系统的专 著一自然系统和人工系统的自适应性( a d a p t a t i o ni nn a t u r ea n da r t i f i c i a l s y s t e m s ) ： k a d el o n g 基于遗传算法的思想在计算机上进行了大量的纯数值函 数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义 的结论。 8 0 年代，h o l l a n d 教授开创基于遗传算法的机器学习新概念，实现分类器系统 9 ( c l a s s i f i e rs y s t e m ) 。1 9 8 9 年，d j g o l d b e r g 出版专著搜索、优化和机器学习中 的遗传算法( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) ， 系统地总结了算法的主要研究成果，全面完整地论述了算法的基本原理及其应用， 奠定了现代遗传算法的科学基础。 1 9 9 1 年，l d a v i s 编辑出版了遗传算法手册( h a n d b o o ko fg e n e t i c a l g o r i t h m s ) ，列举算法的大量应用实例，为推广和普及算法应用起着重要指导作 用。1 9 9 2 年，j r k o z a 提出遗传编程( g e n e t i cp r o g r a m m i n g ) 概念，将遗传算法 应用于计算机程序的优化设计及自动生成。 2 3 2 数学描述 假设有一个待优化的问题： f = f ( x ，y ，z ) ，f r ，( x ，y ，z ) c 式中：x ，y ，z 自变量，它可以是数值量，也可以是逻辑量，甚至可以是 符号量。每一组x 。y 。，z 。c 构成问题的一个解； c _ 既可以看成自变量x ，y ，z 的定义域，也可以看成问题的约束条件，或 所有满足约束条件的解构成的解空间； f 一属于实数域r 的一个实数，也可看成对一组解( x 。y 。z 。) c 的质量优 劣的度量； f 一表示由解空间c 到实数域r 的一个映射，对它的唯一要求是它必须有定 义，即对于一个确定的解( x l ，y 。，z 。) g o ，都可算出一个确定的f 1 与之对应。 优化目标是：找到( 】【o ，y o ，z o ) c ，使得f - - f ( x o ，y o ，z o ) 一m a 】【，在求解多方 案问题时，应该找到一系列的解，得到最优解，次优解等等。 2 3 3 模式定理 遗传算法通过对群体中多个个体的迭代搜索来逐步找出问题的最优解。在搜 索过程中遗传算法处理了一些具有相似编码结构模板的个体。若把个体作为某些 相似模板的具体表示的话，对个体的搜索过程实际上就是对这些相似模板的搜索 过程。这样就引入了一个描述这种相似模板的概念模式，定义如下： 基于三值字符集 o ，l ，) 所产生的能描述具有某些结构相似的0 、1 字符串 集的字符串称作模式。 在模式h 中具有确定基因值的位置数目称为该模式的模式阶，记为o ( h ) 。 模式h 中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离 1 0 称为该模式的模式定义长度，记为6 。 当考虑交叉、变异时，群体i ( t + 1 ) 中模式h 的代表串的数量期望值 驯刚恸( m 0 冬箬卜鲁- 0 ( 啦! 式中t 一迭代代数 m ( h ，t + 1 ) - 模式h 在群体z ( t + i ) 中的代表串的数量 6 ( 田一模式h 的长度 o ( h ) 一模式h 的阶 f ( t ) 一群体中所有个体适应值的平均值 f ( h ，t ) 一模式h 的代表串的数目 从而得到模式定理： 遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、短的定义长度， 并且平均适应度高于群体平均适应度的模式将按指数级增长。 根据模式定理可知，遗传算法根据模式的适应值、长度和阶次来为模式分配 搜索次数，为那些适应值较高、长度较短、阶次较低的模式分配的搜索次数按照 指数率增长，而为那些适应值较低、长度较长，阶次较高的模式分配得搜索次数 按照指数率衰减。 2 3 4 隐含并行性 隐含并行性定理：设为一小正数， g ( 1 - 1 ) + l ，个体数目= 2 “，则遗 传算法一次处理的存活概率不小t - l - s ，且定义长度不大于的模式数为0 ( n 3 ) 。 隐含并行性定理说明遗传算法表面上每代仅仅对n 个个体作处理，但实际上 并行处理了大约o ( n 3 ) 个模式，并且无需额外的存贮，这就是遗传算法具有高效 搜索能力的所在，即隐含并行性。 2 4 遗传算法的基本实现技术 2 4 i 标准遗传算法的流程 标准遗传算法的基本流程如图2 - 1 所示，算法主要步骤如下； ( i ) 随机产生一组初始个体构成初始群体，并评价每一个体的适应度； 骚： ( 2 ) 判断算法收敛准则是否满足，如满足输出搜索结果，否则执行以下的步 ( 3 ) 根据适应度的大小以一定方式执行复制操作； ( 4 ) 按交叉概率执行交叉操作； ( 5 ) 按变异概率执行变异操作； ( 6 ) 转向( 2 ) 。 。开耍臼 l 随机产生视始种 群 。一 * f结1 、l 、“。一一。 图2 一l 标准遗传算法的基本流程 f i g u r e 2 一lb a s i cf l d fc h a r to fn o r m r lg e n e t i ca l g o r i t h m 2 4 2 编码方法 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转 换到遗传算法所能处理的搜索空间的转换方法就称为编码。遗传算法的编码方法 主要有二进制编码方法、浮点数编码方法、符号编码方法、多参数编码方法等。 2 4 3 适应度函数 遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数为 依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对目 标函数的唯一要求是，针对输入可计算出能加以比较的非负结果。这一特点使得 遗传算法应用范围很广。 在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度 函数设计直接影响到遗传算法的性能。 目标函数映射成适应度函数 在许多问题求解中，其目标是求取费用函数的最小值，而不是最大值，而遗 传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数 的值要取正值。由此可见，在不少场合，将目标函数映射成求最大值形式且函数 值非负的适应度函数是必要的。 适应度函数定标 在遗传进化过程中，虽然群体中个体多样性尚存在，但偏偏会出现群体的平 均适应度已接近最佳个体适应度，这种情况下，个体间竞争力减弱，最佳个体和 其它大多数个体在选择过程中有几乎相等的选择机会，从而使有目标的优化过程 趋于无目标的随机漫游过程。对于这种现象，可以通过放大相应的适应度函数值 来提高个体间竞争力。这种对适应度的缩放调整称作适应度定标。目前，定标方 式大致有以下几种：线性定标、截断、乘幂标。 适应度函数的设计和遗传算法中的选择操作直接有关，所以它对遗传算法的 影响还表现在其它方面：1 ) 适应度函数影响遗传算法的迭代停止条件；2 ) 适应 度函数与问题约束条件。 遗传算法由于仅靠适应度来评估和引导搜索，所以求解问题所固有的约束条 件不能明确地表示出来。作为对策，可采取一种惩罚方法。该方法的基本思想是 设法对个体违背约束条件的情况给予惩罚，并将此惩罚体现在适应度函数设计中。 这样，一个约束优化问题就可转换为一个附带考虑代价或惩罚的非约束优化问题。 2 4 4 遗传操作 遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群 体后，遗传操作的任务就是对群体的个体按照它们对环境适应的程度施加一定的 操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问 题的解一代又一代地优化，并逼近最优解。 遗传算法遗传操作包括以下三个基本遗传算子：选择算子交叉算子、变异 算子。 ( 1 ) 选择算子 遗传算法中的选择操作是用选择算子来确定如何从父代群体中按某种方法选 取哪些个体遗传到下一代群体中的一种遗传运算。选择操作建立在对个体的适应 度进行评价的基础上。选择操作的主要目的是为了避免基因缺失、提高全局收敛 性和计算效率。 常用的几种选择算子包括：比例选择、最优保存策略、排序选择、联赛选择 等。 ( 2 ) 交叉算子 遗传算法中所谓交叉运算，是指对两个父代个体的部分结构加以替换重组而 生成新个体的操作。交叉运算是遗传算法区别于其他进化算法韵重要特征。交叉 算子主要包括单点交叉算予、两点交叉算子、多点交叉算子、均匀交叉算子及算 术交叉算子。 ( 3 ) 变异算子 为了改善遗传算法的局部搜索能力以及维持群体的多样性，防止出现早熟现 象，在遗传算法中引入了变异算子。变异运算是指将个体染色体编码串中的某些 基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。 一般说来，变异算子操作的基本步骤如下：1 ) 在群体中所有个体的码串范围内随 机地确定基因座；2 ) 以事先设定的变异概率以来对这些基因座的基因值进行变异。 遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局 部搜索能力而作为辅助算子。遗传算法通过交叉和变异算予这对相互配合又相互 竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合，是指当 群体在进化中陷入搜索空间某个超平面而仅靠交叉不能摆脱时，通过变异操作可 有助于这种摆脱。所谓相互竞争，是指通过交叉已形成所期望的积木块时，变异 操作有可能破坏这些积木块。因此，如何有效地配合使用交叉和变异操作，是目 前遗传算法的一个重要内容。 2 5 小结 本章对启发式算法进行了简要介绍，并对目前所存在的装载问题的求解方法 进行了分类比较，介绍了各种算法的优缺点。之后着重就遗传算法的理论部分进 行了介绍，主要包括了算法的发展、模式定理、并行性定理等数学基础理论，同 时还对算法的基本实现技术，包括参数编码、适应度函数设计和算子设计等方面 1 4 进行研究，从而为后续章节的中心内容研究奠定坚实的理论基础。 3 行李车及行邮专列装载现状 当今世界铁路运输业蓬勃发展，中国铁路交通发展迅猛。在2 1 世纪，中国铁 路将逐渐跨入以“客运高速化，货运重载和快捷化”为特征的新时代。随着铁路 现代化发展，传统的运输系统将不断面临许多新难题：行车速度越来越高，安全 问题也越来越显得突出。目前旅客列车挂运行李车是行包运输组织方式之一，随 着旅客列车速度的逐渐提高，如何保证行李车的运行安全是亟待解决的一个重要 问题。1 9 9 8 年以来，铁路部门为了适应市场需要，推出了“行包专列”这一新的 经营模式。该模式的推出，使行包专列运输既不同于传统的铁路行包运输，又有 别于仍然占有重要地位的传统旅客、货物运输。此外，中铁行包快递有限责任公 司成立以后，于2 0 0 4 年5 月1 8 日在京哈、京沪、京广间组织开行了整列装载的 行邮专列。行邮专列由x l 。行李车组成，最高速度达到1 6 0 k m ， h 。铁路列车的速度 在不断提高，行邮专列的开行范围将进一步扩展，开行数量也还将不断增加，在 提速的同时保证列车运行的安全性和稳定性具有更重要的现实意义。 影响行李车运行安全和稳定性的因素有很多，但是行包在车内的装载方法和 状态对行李车安全的影响最为直接。过去行包运输运量较小，主要以行李和包裹 为主，品类比较单一，重量和体积比较小，符合行李车装载的基本条件和要求。 随着社会经济的不断发展，行包运输的市场需求也在不断地发生变化。习前，行 包运输的市场需求随着货物高附加值、时效性等性能的变化而持续增加。以2 0 0 5 年为例，铁路共发送行包9 4 7 万吨，完成行包周转量1 9 0 1 6 亿吨公里，分别比2 0 0 4 年增长6 8 ，6 7 。铁路行包运输在行包运量和运输收入方面的增长，一方面反 映了社会小宗快运货物运输具有极大的发展市场，另一方面也反映了铁路行包运 输具有极大的市场发展潜力。运量增加的同时，行包运输的货物品类也在变化， 转变为以批量的小件货物为主，货物品类繁杂、而且有不断扩大的趋势。单件超 重货物也经常出现。超重包裹的单件重量采用旅客列车挂运行李车的运输方式时 可达到2 0 0 公斤，采用行邮专列运输方式时可达到3 0 0 公斤。因此，在提速的大 背景下，提高行李车载重量利用率和行李车装卸作业效率，保证行李车运行的稳 定性和安全性，探讨行李车装卸方式的改革方式与方法是非常必要也是亟待解决 的重要问题。 3 1 行邮专列货物装载状况 行邮专列是指使用行李车和邮政车编组，利用行包基地和货运及客运站场、 1 6 设备，整列装载行李、包裹和邮件的列车。 行邮专列分为跨局的和路局管内的特快、快速、普通行邮专列。特快行邮专 列沿途不进行整车甩挂和货物装卸作业；其他行邮专列则可以根据需要在沿途技 术作业站进行货物( 单件重不超过l o o k g ) 装卸作业。 3 1 1 行邮专列车辆及使用情况 行邮专列目前使用的是x l 。型行李车。行包专列所用的行李车型与旅客列车 加挂的行李车有所区别，车体内部不包含行李员工作室，同时取消了消防通道。 每列车两端各有一辆保温车，保温车中含有行李员的工作间。整列车在发送途中 不拆解，中途偶尔有短时间的装卸作业，每对车最多进行一次中途作业。 x l 。是最新型行李车，车辆持续运行速度可以达到1 6 0 k m h 。为满足载重量和 装载容积的要求，车辆采用整体承载有中梁薄壁筒形结构。车内一位端设有配电 室，二位端为行李间，行李间采用四对大拉门设计，车体两侧各设有两个拉门， 车内不设置通道和离水格，以最大限度地满足货物装卸的需要。行李间内部装载 有效长度2 3 8 4 m ，装载有效宽度2 8 8 m ，行李间内部最大装载高度为2 4 6 m 。行邮 专列的x l 。行李车的车辆基本参数参见表3 1 所示。 表3 - ix b 行李车基本参数 t a b l e 3 1b a s i cp a r a m e t e r so fx l l u g g a g ev s n 车辆自重( t ) 3 9 3 载重( t )2 3 容积( 朋3 ) 1 6 0 构造速度( k i n h ) 1 6 0 车辆长度( m ) 2 6 6 车内装载有效长度( m )2 3 8 4 车内宽度( m ) 2 8 8 车内最大装载高度( m ) 2 4 8 车辆高度( m ) 2 8 4 x l m 行包专列作为新型车辆，根据行邮专列的运营特点，增加了载重量和有效 容积，经现场实地测量并计算，x l 。型行李车车辆内部实际有效装载容积为1 6 0 立方米。为保证装载安全，车辆内部还设有烟火报警系统，视频监视系统和行车 安全监测系统，同时实行全列集中供电，集中控制，各节车辆也可单独控制。为 满足乘务人员的工作生活需要，设置了生活间、休息室等，改善了乘务人员的工 作环境。为满足鲜活货物的运输需要，设制冷、加温机组，保鲜室采用聚氨酯发 1 7 泡作为隔热材、采用嵌入式移门保证气密性。 3 1 2 行邮专列装载货物品类及包装 根据行包运输市场需求状况及发展趋势，结合铁路旅客列车运行条件和行邮 专列运输状况，铁路在保留旅客列车加挂行李车运输方式的条件下，又先后建设 并成立了北京、上海、哈尔滨、广州和乌鲁木齐等五个行包基地，以便进一步发 展铁路的行包运输业务。由于不同地区存在经济发展水平和地理区域条件的差异， 各地区行邮专列所装载货物的品类及包装既存在一定的差异之处，也存在一定的 共同点。 ( 1 ) 行邮专列装载货物主要品类 根据有关规定，行邮专列所运输的货物单件不能超过3 0 0 k g ，体积不超过4 甜， 长度不超过5 m ，使用托盘的集装件最大重量为6 0 0 k g 。随着行包市场的发展和运 输需求的增长，行邮专列运输的货物品类由低端向高精尖不断发展，并且逐步规 范化，其中主要品类有电子产品、电脑、配件、小型机械、仪器、食品、药品、 日用品、服装、纸类、书籍、蔬菜、轮胎、邮包、以及邮政的包裹等，见表3 2 至表3 - 5 所示。 表3 _ 2行邮专列部分装车清单列表 t a b l e 3 2 p a r to ff r e i g h ti nt h ee x p r e s st r a i n 品名 总件数 重量k g ( 体积一) 牛奶，芦笋，石粉，( 健身器材) 1 4 1 89 4 5 0 ( 4 5 ) ( 配件) ，服装，书刊，电脑 8 2 8 1 4 9 2 5 ( 1 6 2 ) 蔬菜，书刊，水果，( 家具)1 0 3 0 1 7 3 7 0 ( 9