（交通运输规划与管理专业论文）时变网络下有能力限制的行包径路选择问题研究.pdf

e夏銮堕盔堂亟 圭堂 位迨 塞 中文摘要 普包是由编挂在旅客列车上的行李车运送的一类行包货物。普包径路选择问 题是按照客户对递送时间和费用的要求，合理安排每批货物的运送车次和中转车 站，实现货物的快速、安全送达，是普包运输组织的核心问题。 普包径路选择问题的重点和难点是：如何合理地设计普包运输网络，能同时 包含时间维和空间维的信息，且网络规模合理、易于求解；如何合理地确定中转 站点和在中转站的车次接续方案；如何保证普包径路能满足能力约束条件。在分 析已有研究应用于普包径路问题的局限性的基础上，本文引入时变网络描述普包 运输网，并将普包径路选择问题分解为无能力约束的单- - o d 对普包最短路问题和 考虑行李车载重能力约束的多商品流问题两个子问题分别求解。论文主要完成了 以下研究工作： ( i ) 构建了能够体现节点中转信息的打予交普包运输网。 在对普包径路选择问题的时变特性进行分析后，构建了时变普包运输网。并 通过对节点状态的定义，在时变网上表达出中转信息。 ( 2 ) 研究了无能力约束的单- - o d 对的普包货物最短路问题。 将问题的求解分为两个阶段：首先，为避免后续计算的大量无效搜索，不考 虑普包运输网络的时变特性，寻找0 d 对间的可行路径：其次，在可行路径的求解 基础上，建立单一o d 对普包货物最短路问题模型，用改进的动态规划算法对模型 进行求解。 ( 3 ) 研究了有能力约束的普包径路选择问题。 考虑行李车载重能力约束，将普包径路选择问题描述为有能力约束的多商品 流问题，建立了广义费用最小的多商品流模型，并借鉴车流径路调整的方法设计 了求解算法。 ( 4 ) 实例验证。 结合普包运输组织实际，对时变网络下有能力约束的普包径路选择问题的模 型与算法进行了实例验证。 关键词：时变网能力约束普包径路中转 j e立窑暹盔 堂 亟 堂缱途塞 a b s t r a c t r e g u l a rp a c k a g ei sak i n do fg o o d sw h i c hi sd e l i v e r e db yp a s s e n g e rt r a i n r o u t i n g a r r a n g e m e n ti sa ni m p o r t a n tc o n t e n ti np a c k a g eo r g a n i z a t i o n a c c o r d i n gt oc u s t o m e r s r e q u i r e m e n t , m a k ea r e a s o n a b l ep l a nf o re a c h g o o d sw h i c h i se f f i c i e n c yi st h eb a s i cr u l e t h e r ea r es o m ek e yp o i n t si np a c k a g er o u t i n gp r o b l e mr e s e a r c h , s u c ha s , h o wt o d e s i g nan e t w o r kw h i c hc a nc o v e rm o r ei n f o r m a t i o nb u td on o ti n c r e a s et h es c a l eo ft h e p r o b l e m ；h o wt os e e kt h et r a n s f e rs c h e m e ；h o wt od e a lw i t ht h ec a p a b i l i t yr e s t r i c t i o ni n r o u t i n ga r r a n g e m e n t f o l l o w i n gt h ea n a l y z eo fc u r r e n tr e s e a r c h , t h i sp a p e r w i l ld e s i g na t i m e - v a r i e t y n e t w o r kt od e s c r i b et h ep a c k a g e r o u t i n gp r o b l e m ，s e p a r a t er o u t i n g a r r a n g e m e n tw i t hc a p a b i l i t y r e s t r i c t i o ni n t ot w oi s s u e s ：t h es h o r t e s tp a t ho f s i n g l e c o m m o d i t yw i t hn oc a p a b i l i t yr e s t r i c t i o na n dm u l t i - c o m m o d i t y w i t hc a p a b i l i t yr e s t r i c t i o n t h ep a p e rc o n t a i n s ； ( 1 ) h a v e nd e s i g nat i m e - v a r i e t yp a c k a g en e t w o r kw h i c hc a ns h o wt h ei n f o r m a t i o n a b o u tt r a n s f e r d e s i g naf i m e - v a r i e t yp a c k a g en e t w o r ka f t e ra n a l y z i n gt h ec h a r a c t e r i s t i co fp a c k a g e r o u t e g i v ea ne x p r e s s i o no ft r a n s f e ri n f o r m a t i o nb ym a k i n gad e f i n i t i o no ft h ep o i n t ( 2 ) r e s e a r c ho nt h es h o r t e s tp a t ho fs i n g l ec o m m o d i t yw i t hn oc a p a b i l i t yr e s t r i c t i o n d i v i d et h e p r o c e s si n t o t w o s t e p s ：f i r s t l y , d on o t c o n s i d e rt h et i m e v a r i e t y c h a r a c t e r i s t i co fp a c k a g ed e l i v e r yn e t w o r k , l o o k i n gf o ra l lt h ep o s s i b l er o u t e st oa v o i dm a s s o fi n e f f i c i e n tr e s e a r c h ；s e c o n d l y , m a k eam o d e lf o rt h es h o r t e s tp a t hp r o b l e mo fs i n g l e c o m m o d i t y , u s e m o d i f i e dd r a m a t i ca l g o r i t h m st os o l v et h em o d e l ( 3 ) r e s e a r c ho nt h er o u t i n gp r o b l e mo fp a c k a g ew i t hc a p a b i l i t yr e s t r i c t i o n c o n s i d e rt h ec a p a b i l i t yr e s t r i c t i o no ft r a i n s , t a k ei ta sm u l t i - c o m m o d i t yp r o b l e m , m a k e am o d e la n dd e i g na na l g o r i t h m sb yu s i n gt h em e t h o di nf l o wr o u t e sa d j u s t i n g ( 4 ) p r o v eb ye x a m p l e 。 a c c o r d i n gt ot h ep a c k a g eo r g a n i z a t i o ni nr e a l i t y , m a k eap r o g r a mt ot e s tt h em o d e l a n da l g o r i t h m s k e y w o r d s ：t i m e - v a r i e t y , c a p a b i l i t yr e s t r i c t i o n ，r o u t i n gp r o b l e m ，t r a n s f e r 致谢 整个毕业论文的完成过程有些曲折，收获也因此变得更多。要感谢很多人在 这个过程中给我的帮助。 感谢我的导师刘军教授。在刘老师门下学习三年，是一个感受人格魅力的过 程。在这个过程中我收获到的不仅是知识上的，还有态度上的。治学态度、处事 态度、为人态度，这些导师带给的影响潜移默化却受益终身。 感谢我的师姐王莹。一真以来她都在尽心尽力的帮助我，她的鼓励总是给我 力量，让我在迟疑时不放弃。 感谢实验室各位老师在学业上给我的指导。感谢董晓岩师兄、刘广志师兄、 陈建鑫师弟在论文中给我的指导。感谢同门间融洽的相处氛围。 感谢我活泼的妈和深沉的爸，我爱我家。 感谢我的朋友们，一群丰富的人让我的生活充满色彩。 感谢自己，因为看到了成长。 感谢所有坚守自己信念的人。 i e壅变通盔堂亟堂位论塞绪逾 1 绪论 本章开篇对普包的基本情况作了介绍，明确了普包径路问题的特点。在分析 了问题产生的背景和研究意义后，点明了研究过程中的重点难点问题。对已有成 果进行综述后，指出适用性与局限性。随后提出了本文的研究思路，并对论文的 研究内容和技术路线作了安排。 i 1 问题的提出 按照运输组织方式不同，铁路行包企业为社会提供的快递服务产品可分为专 列运输产品和客运普包运输产品。其中的客运普包运输产品是由编挂在旅客列车 上的行李车运送，运送对象除了少量具有社会公益服务性质的旅客随身行李外， 主要是符合承运标准的小批量、高附加值、对运到时限有要求的货物。普包货物 的承运过程一般是：首先由营业部受理货主的运货业务，在每日的营业时间内将 承运货物集中到营业部的仓库中。在每日营业时间结束后( 一般是每日1 7 点后) ， 将货物运往当地的发送车站。在发送站，多批到站相同或去向相同的普包集结， 装入客运行李车，分别编挂到旅客列车上，按照相应车次的到发时间和径路运行。 对于不能直达的普包，到达中转站后，再与其他行包重新组合，装配成新的行李 车继续运送，直至到达终到站。 不同于专列服务产品的直达运输，多数客运普包运输产品涉及中转作业。普 包径路可以理解为由一系列站点和站点问车次组合而成。由于旅客列车的运行线 路是图定的，每个车次沿途停靠站、站点上的到发时间、站点间的走行时间都已 知。普包径路选择问题就变成了如何在客车网上，为货物在发送站和到达站问确 定中转站及如何确定站点间车次衔接的问题。径路优化是在满足客户对递送服务 要求前提下，合理安排货物的装载行李车和相应的中转车站( 需要中转时) ，使货 物经济、安全地送达。普包径路的确定是普包运输组织中的重要内容。 需要指出的是，在客车网上并不是所有的列车都能编挂行李车，不同旅客列 车编挂的行李车类型和数量也不同，存在行李车载重能力或容积的限制；同样， 在客车网上并不是所有站点都能办理行包作业。可以办理业务的站点存在办理能 7 e塞至遭盔堂亟 堂焦 盐塞绪 途 力约束。由于在中转站中转需要基本的作业时间，对于停站时分不能满足的办理 站，也无法选择作为货物中转站。可见，在确定普包径路时还要考虑到各种限制 情况，否则得到的结果无法指导实际。 总的来说，普包货物运输兼具客运和货运的特点，其径路选择问题存在一定 的特殊性，主要体现在： ( 1 ) 普包运输网由旅客列车开行方案构成的，不是物理意义上的铁路运输 网。普包是随旅客列车行李车运行的，而旅客列车的走行径路是图定 的，普包运输网上两点的连通是指有车次可达。 ( 2 ) 普包径路选择是有能力约束的径路问题，不是一般意义上的最短路问 题。因为存在行李车载重能力约束、办理站办理能力约束等，不是所 有的普包货物都能按最短路运输。 ( 3 ) 普包运输中的中转情况不能忽略。在普包运输中，由中转带来的时间 或费用上的消耗在总消耗中占有相当的比例。 径路的优化选择对合理调配行包货流，降低运输成本，缩短运输时间等都具 有重要的作用。本文将对普包径路选择问题展开研究。 1 2 研究背景和研究意义 长期以来，普包货物都被视为客运服务的附属品，缺乏有针对性地系统研究。 国外的货物运输又很少采用在旅客列车上编挂行李车的组织方式，没有理论可供 借鉴。普包的运输组织理论体系还处在建立过程中，而外部环境的变化还不断为 普包运输组织提出新的要求。 如何确定普包径路是普包运输组织中的重要内容，对该问题的研究背景可以 归纳为以下几点： ( i ) 普包运输服务产品是一类重要的铁路快捷货运产品 为了迎合市场对小件货物快递业务的需求，1 9 9 3 年铁路部门开办了“铁路行 包运输”服务项目。2 0 0 3 年l t 月底中铁行包快递有限责任公司成立，统一管理经 营铁路行包运输业务和行李车运输资源，标志着铁路行包运输迈向了专业化发展 道路。2 0 0 6 年铁道部旗下的两家快递公司中铁行包与中铁快运重组合并为新中铁 快运股份有限公司，进一步整合资源，形成以铁路为主，区域公路运输、航空运 嚣 b塞銮垣 友 堂 亟堂熊途塞缝迨 输为辅的综合行包运输网络。经营网络遍及全国3 1 个省、自治区和直辖市，f i n f - n 务网络基本覆盖全国地、县、市以上的城市。2 0 0 4 年国内小件快递完成1 5 6 0 万件，营业额8 3 5 亿元。预计到2 0 1 0 年，营业额将达到1 0 0 亿“3 。 目前铁路行包企业提供的快递服务产品有两类，时限快递业务。北京到2 1 个城市的次日送达业务，承诺当日承运，次日1 7 时前送达。一般快递业务。在 有行包办理站的城市，承诺4 8 小时送达；对没有行包办理站，有行包代办点的城 市，承诺7 2 小时送达。按照运送货物的列车种类不同，铁路行包运输产品可分为 由专列运送的行包货物和由编挂在旅客列车上的行李车运送的普通行包货物。 相比于由5 条专列构成的通道运输网，客运普包运输网络的覆盖面积广。目 前全路共开行跨局直通旅客快车3 8 4 对，除1 9 对直达特快旅客列车和7 对跨局旅 客快车未编挂行李车外，在3 8 5 对跨局旅客快车( 占跨局旅客快车的9 3 2 ) 上 编挂了行李车9 6 2 辆。全路在3 9 7 对管内旅客列车( 占管内旅客列车的5 2 9 ) 编 挂了4 9 3 辆行李车。全路每天编挂的1 4 5 5 辆行李车可运送2 7 2 万吨普包货物。 普包的运能资源丰富，可以完成更大范围内的运输服务。同时普包的运费收入也 是行包业务收入的主要来源，占到总收入的5 0 左右。 ( 2 ) 普包运输组织相对复杂，既有组织方法存在问题 普包运输依托于铁路丰富的网络资源，但同时也受到诸多因素的制约。如运 能分布不均衡及可控性羞会导致运能不足和虚糜现象同时存在。根据对铁路行包 运输的调研统计数据雎1 ，8 4 的客运行李车的始发装车量在5 吨以下，同时有8 的客运行李车的始发装车量超过了标记载重。随着铁路客运全面提速，旅客列车 中问站的停站时间大大缩短，如直通列车的停站时间一般为2 至4 分钟，由此造 成了中间站行包装卸困难，始发和中转行包大量积压。 专列的运输组织是根据货物流动规律制定开行方案的，而普包运输组织是在 旅客列车开行方案的基础上，凭借编制人员技术水平和经验，以协商和讨论的方 式确定的。较专列定点定时定线的组织方式，普包运输组织问题更为复杂。采用 传统行李包裹运送方式实现的普包运输服务，长期以来都被视为客运服务的附属 品，缺乏根据其特点总结的组织理论，实际操作中只能根据经验进行决策，很难 保证组织的优化，也无法根据市场需求变化及时调整。 由于受干线运输能力紧张。客车停站时问缩短、枢纽站办理能力有限等多方 e窿至通 盔笠亟堂位途塞绪迨 面因素制约，普包运输中存在大量的中转情况。实际操作中常会出现以下的问题： 所选中转站的办理能力紧张，使得到此站中转的货物无法及时装车，而产生滞 留。所选中转站没有直达目的地的车次，而不得不进行多次中转。所选车次 的运能不足，使得货物无法装车，需要在中转站等待。所选车次在时间上不能 很好衔接，导致货物在中转站长时间等待。这样就很难保证全局组织的优化，也 无法根据市场需求变化及时调整。 ( 3 ) 快递市场的发展对铁路快捷货物运输组织提出更高的要求。 近几年，得益于我国宏观经济良好的发展态势，国内快递市场需求保持高速 增长。铁路部门自1 9 9 3 年开办“铁路行包运输”服务项目以来，取得了快速的发 展，逐步成为铁路运输新的经济增长点。但是，在市场需求不断增加的同时，业 内的竞争也日趋白热化。铁路行包运输企业只有不断为客户提供能带来收益的高 质量运输服务产品才能在市场中占得先机。随着铁路改革的逐步深入，以突出快 速、准时为特征的快淹货运成为中国铁路货物运输组织发展的重要方岛d j 【4 】。 普包服务产品作为一类重要的铁路快捷运输产品，其组织优化对合理利用资 源，提高快捷货物运输组织效率，提升行包运输服务水平，增加企业收益等方面 都有重要影响。对其相关问题的研究，无论是从学术层面还是应用层面都有一定 的价值。论文的研究意义体现在： ( 1 ) 为实际的普包运输组织提供理论支持和方法指导。用旅客列车编挂的行 李车运送货物是一种较为特殊的货物运输方式。在国外很少见，相关研究也不多。 而在我国，普包运输一向被视为客运服务的附属品，缺乏对其组织理论系统的研 究。本文对酱包径路问题的研究是从普包运输组织实践出发，对其径路选择的特 点进行了分析总结，在忿基础上提出优化思路秘方法，能够在一定程度上指导实 际的普包运输组织。 ( 2 ) 进一步丰富了铁路快捷货物运输组织理论。普包是铁路快捷运输服务产 品中的一种，是有时限要求的铁路货物运输。本文在对其径路问题的研究过程中 无论是思路还是方法，都突出了“时间”这一因素，切合了市场对于铁路快捷货 物运输组织“快速、准时”的要求，进一步丰富了铁路快捷货物运输组织理论。 ( 3 ) 将时变网络引入对普包径路问题的描述中，在不降低计算效率的前提下， 使得网络上能够表达出时间维的信息，并能对节点状态进行描述。对其它含时间 1 0 e巫銮通叁堂亟堂位迨塞缝迨 信息或是涉及中转换乘的路径选择问题提供借鉴意义。 1 3 普包径路选择问题分析 在本章开篇问题的提出中，对普包径路选择的特殊性进行了简要的分析，将 普包径路理解为一系列站点和站点间车次的组合；将普包径路选择问题归纳为在 客车网上，考虑能力约束的径路选择问题。这样来看，在普包径路问题的研究过 程中，要解决的基本问题就有：如何描述普包运输网，如何确定货物的中转站， 如何选择接续车次，如何考虑能力约束等。以下将对问题进行进一步的分析： ( 1 ) 普包运输网的描述 在客车网上，即使是同一物理径路，也会存在多个车次。不同旅客列车车次 从物理径路起点出发的时刻，到达终点的时刻，走行时间均可能不同。对于涉及 中转的普包货物，在中转站选择不同的车次接续方案，相应的路径就不同。为了 更好的解决普包径路选择问题，需要在普包运输网上表征出普包径路选择所需的 所有列车信息。如何合理地设计普包运输网络，能同时包含时间维和空间维的信 息，且网络规模合理、易于求解，是普包径路选择问题中的难点之一。 ( 2 ) 中转方案的确定 在普包运输组织中存在大量的中转情况，货物进行一次中转可能涉及装卸、 搬运、仓储等作业，这样会带来成本和时间上的消耗，还可能导致货物破损丢失 等现象的发生，所以在普包组织中要尽量减少中转次数。这也从一个侧面说明研 究普包问题时，货物在节点的中转情况是不能被忽略的。在确定普包径路时，由 于旅客列车走行线路和到发时问是固定的，如何确定中转站点，如何确定在中转 站的车次接续方案，是普包径路问题中的又一个难点。 ( 3 ) 能力约束的处理 在普包运输中，运能资源并不是按照货物的分布规律分配的。如果不考虑能 力约束，一般货物都会选择在枢纽站进行中转，随快车运行，因为这样的选择往 往在时间上或成本上是能实现最优的。但是按照这样的原则进行运输组织，往往 会导致货物都集中到某几个站点进行中转或者集中到某几个车次上进行运输。一 旦站点的办理能力不能满足需求，货物将不得不积压在站点等待运输或是改到其 j e塞銮垣盔堂亟堂位迨塞绪迨 他站点继续中转；同样，如果行李车的载重能力不能满足需求，货物需要选择其 他车次接续方案或者转向其他站点进行中转。与此同时，另一些办理站或车次的 能力没有被充分秘用，可见，如果不考虑能力约束去确定普包径路，会造成运能 紧张和运能虚糜并存的情况，加剧运能和运量之间的矛盾，降低普包货物的组织 效率，造成资源的浪费。而如何保证普包径路能满足能力约束条件，是普包径路 选择问题中需要解决的问题。 针对普包径路选择问题中的重难点问题，本文尝试设计基于列车时刻表信息 的时变普包运输网，建立有能力约束的径路选择问题模型。 时变网络是指网络中弧上的权值随时间变化，不同时间，弧的“长度”不同。 对普包运输来说，同一物理径路存在多个车次，普包货物从同一点在不同的时间 出发( 也就是跟随不同的旅客列车运输) ，走行时间和费用均不相同。如果在静 态网络中表达两点间存在不同“长度”的弧，需要在两点问虚拟多条弧，使每一 条对应一个“长度”。而在时变网络中不需要这样做，两点间有且只有一条弧， 只是弧的状态与时间有关。通过时变网络可以直接表达出时间维的信息，这对于 解决涉及时问的大规模网络问题是很有意义的。 可见，酱包径路问题的特殊性与时变网络的特点相对应，所以本文提出用时 变网描述普包运输问题。 1 。4 径路选择问题的研究现状 结合本文选题，在研究普包径路选择阿题前分别以“径路优化”“中转”“换 乘”“流量分配”“时变”等关键词对国内外文献进行检索。在对文献整理分析 后了解到，在交通运输领域中，对径路优化选择问题的研究广泛而深入。总的来 说，已有方法有很多思想可以被借鉴到对普包径路选择问题的研究中，但却都不 完全适用。以下从静态网络下的径路选择和时变网络下的径路选择两个角度，对 现有研究进行综述。 1 4 1 静态网络下径路选择问题研究现状 传统的最短路径问题中是在指定运输网络的两结点问找出一条阻抗最小的路 e夏銮适太堂亟堂焦i 金塞缝迨 径。根据阻抗的不同定义，最短路径可以指一般意义上的距离最短，也可以引申 到其它的量度，如时间、费用等。但不管怎样，阻碍强度的值都是静态的、确定 的。按照研究对象不同，对静态网络下径路选择问题分铁路旅客运输中转径路、 货车车流径路、行包运输径路三部分归纳研究现状。 ( i ) 铁路旅客运输中转径路的研究现状综述 文献 5 中对客运径路中换乘问题的处理，是基于“我国铁路客运网中，旅客 换乘越多，换线也越多的；对于一条路径，换线越多，则换乘也越多”的假设。 用换线数来模拟换乘数，将距离与换线数据按一定的逻辑关系组合为一项单目标。 对于车站间的距离信息和线路信息，文中提出划分为子网，将铁路网看作是由几 个子网络叠合而成。但是这类变线模型不能获得旅客换乘次数较少但所乘列车变 线次数较多的中转径路。 文献 6 在“路网模型”和“换线模型”的基础上，建立了“换乘模型”。结 合路网信息和列车信息，构造了路网和换乘网络，建立了中转径路模型。在这个 模型中，中转径路的优化计算要涉及两个网络。 文献 7 中基于铁路网络、列车开行方案和列车运行时刻表分别设计了换乘网 络。在这三类网络基础上，按照包含信息量的不同，又细分为6 类网络，可根据 所研究问题的具体情况选择不同的网络。其中，完全换乘网络是以车站为节点， 以列车停靠点为虚拟点，同一列列车相邻停靠点之间沿列车前进方向为区问弧。 同一车站不同歹j 车的停靠点之间为换乘弧，用以描述车站不同列车之间的换乘时 间或费用。文中指出，完全换乘网络不仅具有优化乘车费用和换乘次数的功能， 还具有优化换乘时问的功能。 总的来看，对旅客列车中转径路问题的研究主要集中在对换乘网络的设计上， 从“路网模型”、“换线模型”发展到“完全换乘网络”，不管是将铁路网划分 为几个子网络，还是在一个网络上虚拟点和弧，都是为了使构造的网络中包含更 多的列车信息。因为只有纳入全部列车信息综合考虑旅客的各种换乘情形，才能 彻底解决中转径路的优化计算问题。其中的完全换乘网络是可以刻画出普包中转 问题的。文献 8 中的完全中转网就借鉴了这一模型。但是应该看到，在完全中转 网络中，对于同一车站，不同列车的停靠点的子网络是一个完全图，会产生很多 停靠点之间的中转弧。对于小规模网络，这一问题并不明显。一旦站点数量增多， 1 3 e 峦 銮亟 盔 堂亟 茔位论塞绮迨 点对间的虚拟弧将急剧增加，使得网络规模过大，导致难以在有效时间内求解。 对旅客列车中转径路的研究不能直接应用于解决普包径路问题的另一原因还在于 客运径路问题中并没有能力约束。 ( 2 ) 行包运输径路的研究现状综述 文献 8 和 9 中对普包运输方案的研究都涉及了普包径路问题。其中： 文献r 8 借鉴了文献 7 中基于列车运行时刻表的完全换乘网，设计了基于列 车运行时刻表的完全中转网来描述和刻画普包运输方案编制中的中转问题，体现 了普包中转时间、中转费用和中转次数，建立了广义运输费用最小的普包运输方 案的优化编制数学模型。 文献 9 3 建立了含时间和空间要素的动态普包运输服务网络，节点具有二维坐 标，分别对应一个行包办理站和计划周期内的一个离散时刻点。弧段对应于在特 定时间段内普包的运送过程，或者普包在某个站点的停留延迟。如果是办理站间 的弧段就代表旅客列车信息，表示普包由旅客列车挂运的行李车进行运送。节点 与下一个时间段中行包办理站部分坐标相同的节点问的弧段为延迟弧，表示货物 的停留。 在已有对普包径路问题的研究中，所设计的网络都能对普包的中转情况进行 刻画，建立的模型中考虑了能力约束，并以多因素的优化为目标。但是不管是完 全中转网还是时间一空间二维动态网，对于小规模问题尚可处理，一旦问题规模扩 大，计算效率就成为突出问题。这一点从论文验证的实例规模中也可以看出。由 此可见，对普包运输网络的优化设计是普包径路问题的一个难点。 ( 3 ) 车流径路优化的研究现状综述 传统的路网上车流径路选择问题是从如何使机车、车辆得到更好运用的角度， 寻求在满足线路通过能力及车站技术条件( 改编能力、通过能力) 的限制下，使 所有车流消耗的换算车小时或换算车公里最小的径路。在此基础上相关研究进一 步深化，从单目标优化发展到多目标优化，从单独优化发展到与编组计划整体优 化。其中： 文献 1 0 把货物列车车流径路和编组方案统一起来进行优化。构造了编组网 络图，节点来表示车站或编组站，两个节点的弧表示组成列车的车组采用连结。 将列车编组计划问题转变为一个编组网络图计算问题来解决。 韭窟至适太堂亟堂位迨 塞垡迨 文献 1 1 中考虑了真实路网中的车流具有不同权重的情况，建立了带权重车 流的径路优化o - i 模型。为了提高模型的求解质量，给出了路网任意两节之问可 能路径集的确定准则及算法。最后探讨了在给定0 d 矩阵下，路网中存在一处或多 处瓶颈时。关于不可行流的处理方法。 文献 1 2 将车流组织问题与路网能力联系在一起，建立路网上条件有区段能 力约束的车流组织问题优化模型，并提出求解模型的运筹学算法。并提出为了保 证与技术站改编能力相协调的而对优化方案进行调整的方法。 文献 1 3 是基于满意度原理的多目标优化方法，针对一般车流径路问题求解 中追求目标最优的难度和不足，改进了在一定运输需求条件下对路网上双向、空 重车流径路同时进行优化的多目标满意优化模型，并通过建立独立满意度和综合 满意度来衡量优化解的品质。 无论是从研究深度还是从研究广度，现有对车流径路的研究有很多。在设定 优化目标、处理能力约束等方面。一些思想可以被借鉴到对普包径路问题的研究 中。但是由于铁路车流组织对于时间的要求不高，更多的是强调充分利用运能， 与普包运输的组织理念不同，在解决有时限要求的运输问题时存在局限。 1 4 2 时变网络下径路选择问题研究现状 时变网络是指网络中弧的权值随时间变化，即弧的权值是时间的函数，到达 弧尾结点的时刻不同，相应的弧的旅行时间不同，也称为时间依赖网络。 在传统的最短路径问题中，假设网络中的权值是静态的、确定的，这些假设 在许多应用领域不是真的。时变、随机网络最优路径问题将网络中弧的权值建模 成随时间变化的、随机的，因此突破了传统的最短路径问题的局限性，能够描述 现实网络系统的时变性和随机性。对时变网络的研究起因于智能交通系统、计算 机网络系统、通信系统、紧急服务运输系统等众多应用领域对具有时变性、不确 定性和多样性的最短路径算法的需求。由于各种网络系统的规模越来越大、越来 越复杂，大规模网络的最优( 或最短) 路径的求解效率成为入们追求的目标，静态 网络下的经典最短路算法已不能满足， 目前对于时变条件下径路选择问题的研究相对较少。在交通领域里，相关研 究主要集中在智能交通系统。 e 夏 銮壅态堂亟堂位迨塞缝迨 文献 1 4 1 中e l i s edm ，h a r dsm 对在随机时变网络的最短时问的最短路进行了 研究，提出了两种不同的算法，并对这两种算法进行了比较。后来他们在文献 1 5 1 又提出了一些在随机时变网络下的不同路径之间进行比较的原则。 文献 1 6 中a t h a r t a s i s oz ，d i m i t f i o s k 和h a n l s m 对在时变条件下考虑最短时间 的最短路在智能交通系统中的应用进行了分析。 文献 1 7 中d a r d e l ep 对离散随机时变超图网络下的考虑最短时间的最短路进 行了研究，给出了求解的方法。 文献 1 8 中给出了时变条件下，适用于非先进先出情况最短路的算法，利用 标号法求解最短路的算法。作者随后在文献 1 9 中又给出了求解双目标最短路的 算法。 文献 2 0 给出了f i f o 时间依赖网络和非f i f 0 时间依赖网络下最小时间路径 模型的形式化表达、理论基础和算法。 在道路交通系统的砑究背景下构造的时变网络应用于行包运输还是存在局限 性。例如，多数现有关于时变网络的研究都是基于先进先出的原1 ) 2 1 j ( f i r s t - i n - f i r s t - o u t ) ， 而通过铁路运输的普包货物组织并不遵循这样的原则。又例如在道路交通中节点 处的等待是没有意义的，所以现有时变网络上不用表征节点处的消耗。而在铁路 运输中，旅客换乘、货物中转都需要描述节点状态。因此，现有对时变网络下最 短路问题的研究不能完全套用到普包径路选择问题上。 1 4 3 现有研究总结 综上所述，无论是静态网络下的径路优化研究还是时变网络下的径路优化研 究，对于解决普包径路问题都存在一定的局限性，主要表现在： ( 1 ) 在网络刻画方面。静态网络中不能同时将时间要素和空间要素直接体现 出来。为了在网络中包含更多信息，就需要通过虚拟点和弧，这样又会导致网络 规模太大，影响求解效率。 ( 2 ) 约束条件方面。客运径路问题中没有能力约束，车流径路问题中虽然考 虑了能力运输，但是没有时间信息，不能体现行包货物对于时限的要求。 ( 3 ) 中转信息表征方面。静态网络中通过虚拟点和弧表示中转，对于大规模 路网问题，点对的增加会使得弧的数量激增，影响求解效率。而在既有的对时变 1 6 网络的研究中，并未考虑节点处的等待时间和能力约束，不能反映普包货物在中 转站的中转情况。 1 5 论文的研究思路和内容 在了解了现有研究对普包径路问题的适用性和局限性后，这里提出本文研究 普包径路选择问题的思路：构建时变普包运输网，建立有能力约束的普包径路选 择问题模型，为全路普包货物安排径路使得总广义费用最小。 本文将时变网下的普包径路选择问题分为两个子问题：首先，在不考虑能力 约束的情况下，为每一个o d 对普包货物找最短路：然后考虑行李车能力约束，对 不能走最短路的货物进行调整，为全路货物安排径路。这两个子问题，一个是站 在“货”的角度，一个是站在“车”的角度。在算法上，第二个包含对第一个的 调用。之所以分为这两个问题，主要是考虑到：并不是所有车次都存在能力紧张 问题，只是个别方向、车次上运能与运量问矛盾突出。考虑能力约束后，只有部 分货流需要调整。而一般货流的调整都限于小范围内，不会对其他方向上的货物 产生太大的影响。既然这样，可以先为每批货物都求出最短路，然后判断哪些货 物受到了能力的限制，只对这部分货流进行调整即可。在求最短路的一步中，先 不加入能力约束，因为酱包服务产品的目标市场是高附加值、小批量货物，一般 单批货物不会超过旅客行李车的载重：在为全路货物安排径路时再加入能力约束。 将问题分成两个子问题进行求解，会大大减少计算量，节省内存空间，提高计算 效率。 基于以上思路，针对在分析普包径路问题特点时归纳的关于该问题研究的几 个重点、难点，论文将要研究的主要内容有： ( 1 ) 构建时变普包运输网 对普包径路选择问题的时变特性进行更为详细的分析，构造时变普包运输网。 说明所构造的网络中是如何实现对现有时变网的改造，体现出中转等待情况的。 ( 2 ) 时变网络下普包最短路模型与算法研究 这一部分是没有能力约束的单- - o d 对普包货物最短路问题。不加入能力约束， 建立单- - o d 对普包货物最短路问题模型，为每批货物求广义费用最小的径路。 1 7 ( 3 ) 有能力约束的普包径路选择问题模型与算法 这一部分是考虑行李车载重能力约束的多商品流问题。判断超过载重限制车 次所涉及的货流，按广义费用和最小进行调整，建立行李车载重能力下多商品流 广义费用和最小模型，为全路普包货物安排合理径路。 1 6 论文研究的技术路线 塞銮适本堂亟主堂焦迨塞 蟹 迨 图1 1 ：论文的研究技术路线图 耋圭 ，jir；i， 9 2 时变网络下普包最短路模型与算法研究 本章首先对普包径路选择过程中体现出的时变特性进行了分析，为之后用时 变网络构建普包运输网奠定基础。随后设计了时变普包径路网，并对该网络中是 如何体现中转信息迸行了分析说明。然后针对单一0 1 9 对普包货物，建立了基于广 义费用最小的径路模型，并求解算法分为两个步骤，为每批普包货物找最短路。 2 1 普包径路选择的时变特性分析 假设一批普包货物k 从起点o ( k ) 运至终点a ( k ) ，从车站。发送到达车站d 。 车站o d 间的列车开行情况如图所示，节点代表车站，弧表示有旅客列车经过。 、。 o o p 弋 图2i ：中转方案示意国 从图中可看出，车站o d 间无直达旅客列车，需要在中问站点进行中转，并存 在几种不同的中转方案。以在站中转一次的所有中转方案为例。根据旅客列车 时刻表，车站d 一、一d 间开行的所有旅客列车的车次信息如下表所示。 表2 1 ：列车时刻表信息 车次起点及出发时刻 终点及到达时刻在途时阃( h ) 0 l3 6 ：0 09 ：0 0 o 2 2 8 ：0 01 0 ：0 0 d 35 l l ：0 01 6 ：0 0 d 42 1 2 ：0 01 4 ：0 0 可以看到；在站d ，货物选择装载在6 ：0 0 出发的车次或8 ：0 0 出发车次，对应 的在途运行时间不同，分别是3 4 , 时和2 4 , 时。到达站i 后，选择l l ：0 0 出发或1 2 ：0 0 出发，在途运行时间也不同，分别是5 小时和2 小时。 p 二o ! o 【8 0 0i o o o j z o o1 4 蛔 图2 2 ：中转万蒹z 将列车运行时间看作路径长度，则从上图看出，由于同一对站点问不同车次 的旅客列车到发时间和运行时间不同，同一对节点问的路径在不同时问对应的路 段长度不同。由此，我们可以认为弧的权值是随时间变化的。不同时间，弧的长 度不同，到达弧尾结点的时刻不同。而这也正是时变网络的定义。基于此，本文 尝试构造时变的普包径路网来研究普包径路选择问题。 基于旅客列车时刻表信息构造的时变普包径路网络中包含了旅客列车的全部 信息，可以描述实际中确定普包径路的过程。另一方面，相比于一般的静态网络， 时变普包运输网能同时包含时间维和空间维的信息，且网络规模合理、易于求解。 时变普包径路网以车站为节点，以有客车开行的铁路线为弧，将两点间的列车信 息转化为路径的时变广义长度，其路网规模与实际的铁路物理网布局一致，但每 条弧能表征两点间所有车次信息，并能体现中转信息。这样在确定普包径路时， 能同时体现距离信息和时间维信息，又避免了虚拟大量的点和弧，使得问题的规 模大大缩小，降低了求解的复杂度。 普包径路问题具有时变的特性。基于上述分析，建立基于时刻表的时变网络 来描述普包运输网。通过对点和弧表征含义的定义，在时变网络中还能体现出普 包的中转。 2 1 2 2 时变普包运输网络设计 2 2 1 时变普包运输网络设计依据 普包是由编挂在旅客列车上的行李车运送的，在已知各o d 对普包流量的前 提下，设计普包径路网络时要掌握下列资料信息： ( 1 ) 旅客列车的开行方案 根据旅客列车运行图可以获得旅客列车的车次、始发站，终到站、中间停靠 站、到达每个站点的时刻和从每个站点出发的时刻、每个区问的运行时间等信息。 ( 2 ) 客运行李车的编挂方案 不同等级的旅客列车可以编挂的行李车数量和类型不同，而不同类型的客运 行李车运载能力是由车辆标记载重和容积两方面体现的，它决定了哪些普包货物 可以装载到同一行李车上。 ( 3 ) 普包运输生产组织原则 按照铁路旅客运输办理细则规定：行包运输组织工作应根据流量、流向， 本着先行李后包裹、先中转后始发和长短途列车分工、安全、经济的原则，合理、 均衡地组织运输。行李应随旅客所乘列车装运或提前装运；包裹应尽量以直达列 车或中转次数少的列车装运。途中有几个中转站中转次数楣同时，应首先在有始 发列车接运的车站中转。如途中有几个站都有始发列车接运，原则上应在最后一 个中转站中转，但其他站应适量分担。途中都没有始发列车时，应在最后一个中 转站中转。途中有2 个以上径路时，在中转次数相同的情况下均可办理。特殊情 况下，铁道部可指定车站增加中转次数。装运整车包裹时，只限一个到站，但准 许部分中转( 北京站除外) 。中转包裹的到站，仅限在该站有始发管内列车的停车 站，其数量不得超过整车件数的3 0 。铁路行包中转作业要在合理利用车辆载重 力和有效装载容积的基础上，将来自各方向始发站不够条件组织专列直达运输的 货物，向相应的中转站装运，在中转站及时、合理地组织新的直达或中转运输， 继续运行至到站的作业。 行包公司的业务组织原则中规定各行包营业部在每日1 7 点将货物运往车站， 从1 7 点开始计时，当日的货物必须在当日从火车站发出，沿途各站的装载准备时 间为7 分钟。 2 2 2 时变普包运输网络的构建 时变普包运输网就是根据旅客列车信息、客车行李车编挂方案和普包运输组 织的相关原则等信息，以车站为节点，以车站站问物理径路为弧建立的。其网络 规模和实际路网规模一致，只是弧的权值是随时间变化的。这样在时变普包运输 网上，节点之间有且仅有一条弧，表示节点之间有车次连通。弧上权值可以代表 任何含义( 如时间、距离、风险等) ，通过权值的变化来表征状态的变化。 对普包运输网络来说，还要考虑对节点信息的表达。以节点处的时间信息为 代表，用2 1 节的例子来说明时变普包运输网上是如何表达节点信息的。 对衔接车次进行组合，可得到od 间普包货物的一组径路，如下表所列： 表2 2 ：o d 间径路信息表 始发站站顺站顺 出发车次到达出发车次到达出发 时刻时刻时刻时刻时刻 径路add l3 6 ：0 09 ：0 01 1 ：0 01 6 ：0 0 径路bd d 23 8 ：0 01 0 ：0 0l l ：0 0 1 6 ：0 0 径路cd d 1 4 6 ：0 09 ：0 01 2 ：0 01 4 ：0 0 路径ddd 24 8 ：0 01 0 ：0 01 2 ：0 01 4 ：0 0 比较径路方案a 和径路方案c ，方案a 中从车次l 接续到车次3 的中转等待时间为 2 4 , 时，到达站d 时间为1 6 ：0 0 。方案c 中从车次l 接续到车次3 的中转等待时间为3 小时，到达站d 时间为1 4 ：0 0 。可见，货物的中转等待时间长，全程运送时间并不 一定长。同理的，在途运输时间短，不一定全程运送时间就短。普包运送时间是 在途运输时间与中转等待时间的和。由于在中转站进行中转时存在等待时问，在 确定普包径路时，中转等待时间是不能忽视的。一般的静态网络都是通过虚拟点 和弧来表达中转概念的，这样路网规模就会大大增加。而现有时变网络多是针对 道路系统设计的，道路交通中不存在路口等待情况，所以网络中没有体现中转信 息。本文在设计时变普包径路网络时，要解决这一问题。 为此，进一步对普包径路进行分析。从表中可以看到：径路a 方案和径路b 方 案到达站点d 的时问相同，均是1 6 ：0 0 。径路c 方案和径路d 方案到达站点d 的时问楣 同，均是1 4 ：0 0 。从终点站开始逆序向前进行分析：径路a 和径路b 从站点到站点 d 都是接续到1 l ：0 0 开行的车次3 上，在1 6 ：0 0 至u 达站d 。其中径路a 方案中由车次