（运筹学与控制论专业论文）用列生成法解决市内邮件转运路线问题.pdf

摘要 彳慨9 7 邮件转运是邮政局的一项l 常工作。本文针对中国邮 件转运的实际情况提出了市内邮件转运路线问题，建立了 午| 应的数学模型，并构造r 这个问题的列生成算法。在求 解列生成算法的子问题时，构造了动态规划方法和启发式 算法两种不同的方法。针对杭州市市内邮件转运实例，我 们进行了计算，得到了比现行转运方案更好的方案，邮件 转运车辆一天总的行驶距离减少了8 2 9 。 关键词 市内邮件转运路线问题，列生成法，动态规划，启发式算 法，分支定界。 分类号：0 2 2 a b s t r a e t t h et r a n s p or t a t i o no fp o s l a lm a t t e r sis t h er o u t i n ed u t yo f t h e p o s t o f f i c e s t h is p a p e rp r e s e n t sam o d e la n dc o n s t r u c ta c o l u m n g e n e r a t i o n m e t h o dsf o rt h el o c a l p o s t t r a n s p o r t a t i o n p r o b l e m t h ea r t i c l ea l s os e t su pa ne x a c ta l g o r i t b mb as e do n c o l u m ng e n e r a t i o na n da nh e u r is t i cb a s e do nm i n i m a l c o s tm e t h o d w e a p p l i e di t t ot h ei n s t a n c eo fh a n g z h o uc i t yi nc h i n aa n dg o ta b e t t e rs c h e m et h a nt h ec u r r e n t l yi n o p e r a t i o n w eh a v ei m p r o v e d t h es c h e m eb y83 p e r c e n t k e y w o r d s l o c a l p o s t tr a n s p o r t a t i o nr o u t i n gp r o b l e m ，c o l u m ng e n e r a t i o n ， d y n a m i cpr o g r a m m i n g ，h e u r is t i c ，b r a n c ha n db o u n d 1 市内邮件转运路线问题 本章介绍了中国邮政运输系统的现状，提了市内邮件转运路线问题，并 分析r 其在全国邮政运输系统中的重要性。 1 1 问题提出 【 1 国邮政运输系统十分庞大，邮件邮递速度慢n 成本商是邮运系统的现 状。在全国邮运系统中，由于邮件业务主要集t j 在各地区的大中城市，并且各 地区大中城市的邮政局承担了本地区邮件集散中心的任务，所以它们的邮政运 输状况决定着全国邮政运输系统的现状；同时，各地区大中城市的邮政局的业 务收入也是全国邮政业务收入的主要来源，据9 3 年的统计资料，它们的全年业 务收入占全国邮政业务收入的3 3 2 。所以，改善各大中城市邮政局的市内邮 政运输状况，优化市内邮政运输路线，对提商全国邮政运输系统邮件邮递速度 和降低邮运成本有着重要的意义。 在各大中城市的市内邮政运输系统中的邮路，主要包括市内开箱路线、市 内投递路线、市内接发邮路和市内邮件转运路线四种。其畸l ，市内开箱路线是 指各邮政支局和邮政所搜集各自辖区内邮箱中的邮件的路线：市内投递路线是 指各邮政支局和邮政所把辖区内邮件投递到顾客的路线；市内接发邮路是指从 码头、铁路局和机场等各种运输港口把发给本市的邮件运送至本市邮件处理中 心的路线以及把本市发往外地的邮件从本市邮件处理中心运送至码头、铁路局 和机场等各种运输港口的路线；市内邮件转运路线是指把本市邮件处理中心把 邮件运送到各邮政支局、所，以及把各邮政支局、所搜集到的邮件运送到本市 邮件处理中心进行处理。 各大中城市的邮政局每天的市内邮件转运任务由多个转运班次构成。一个 转运班次是指市邮政局在同一时间段内，派出吨位不一的邮车，从中心出发， 沿各条预定的路线依次到达各支局、所收取或发送邮件，然后返回中心。 每一转运班次的运行成本，由驾押人员的工资、邮车的折旧费、维修费和 邮车的燃料费等部分组成。不同的转运路线方案，相应的运行成本是有差别的， 差别的主要表现就集中在邮路的长度一l 。邮路总长度越长，物质损耗就越多， 运行成本也就越高，即可认为运行成本与邮路总长度成正比关系。 1 2 问题的一般性描述 为了降低运输成本，在制定各班次转运计划时，要求转运车辆总行驶路线 最短。每一班次转运方案中的转运路线，都应符合下列要求： ( 1 ) 本班次转运或单纯完成送达邮件任务，或单纯完成接收邮件任务； ( 2 ) 每条转运路线恰用一辆邮车行驶。它的总运行时间受到一定的限制。 也就是说，邮车应在规定时限内完成它的转运任务； ( 3 ) 本转运班次有关支局，应恰有一辆邮车沿选定的一条转运邮路到达此 支局，完成它的邮件收发任务； ( 4 ) 本转运班次有关支局，可根据邮件的时限要求和本身营业时间，提出 要求本班次转运邮车到达本支局的规定时段； ( 5 ) 本转运班次有关支局，可根据当前情况和历史资料，提出本班次内该 支局收发邮件重量和所需装卸时间。 将某一转运班次中，符合下列条件的转运路线称为此班次的可行路线： ( 1 ) 邮车沿此路线完成邮件收送任务的总时间( 包括行驶时问和装卸时间) 不超过本班次的规定时限； ( 2 ) 沿此路线行驶的邮车之吨位应能容纳沿线各有关支局之总邮件； ( 3 ) 沿此路线行驶的邮车到达各支局的时间必须在此支局规定的时段内。 车辆到达支局后，由于受到停车条件的限制，必须马上装卸( 不能等 待) ；完成装卸后车辆必须马上离开支局( 不能滞留) 。 ( 4 ) 沿此路线行驶的邮车到达本班次各有关支局( 除转运中心外) 至多一 次。 市内邮件转运路线问题就是考虑设计一组满足上述要求的车辆路线问题， 其目标是转运车辆行驶的总距离最短，约束条件是转运车辆开始且终止于同一 中心点( 邮政总局) ；每个客户( 支局) 必须服务且仅服务一次；每条路线从中心 点带小的邮件( 或收集到中心点的邮件) 数量不得超出车辆的装载限制。 市内邮件转运路线编排问题与带时间窗u 的车辆路线问题( t h ev e h i c l e r o u t in gp r o b l e mw it ht i m ew i n d o w s v r p t w ) 很树似，所以在下一章我们将对 v r i q 、w 的研究作一些介绍。 2 带时间窗e 1 的车辆路线问题( v r p t w ) 及其研究分析 本章介绍了与市内邮件转运路线问题相近的带时间窗口的车辆路线问题 ( v r p t w ) ；分析了市内邮件转运路线编排问题与v r p t w 两者间的异同；并 将闽际上对v r p t w 的主要研究工作进行了归纳。 2 1 带时间窗口的车辆路线问题( v r p t w ) 在这个问题中，要求车辆从一中心仓库出发，对所有顾客进行服务( 包括 收集( 或派送) 货物) ，并且每个顾客只能用一辆车辆进行服务。车辆对顾客服务 须在顾客允许服务的时段( 也称时间窗口) 内开始，也就是在顾客规定的可开 始服务的最早时刻和最晚时刻之内开始。问题的目标就是设计一组满足上述要 求的总长度最短的路线。 市内邮件转运路线编排问题与v r p l 、w 有相同之处在于：市内邮件转运路线 编排问题与v r p t w 都是特殊的车辆路线问题。它们都是安排车辆对顾客群进行 服务：每个顾客只能用一辆车辆进行服务：车辆都有载重量的限制等；每个顾 客都有接受服务的时间窗口。 市内邮件转运路线问题与v r p t w 不同之处在于：在市内邮件转运路线问题 巾，车辆必须在各点的时间窗口内抵达并进行服务，不予许提前到达；而在v r w 研 中，允许车辆提前到达等待。所以我们可以把市内邮件转运路线问题看成严格 时问窗口的v r p t w 一一v r p s t w ( v e h ic l er o u t i n gp r o b l e mw i t hs t r ic tt i m e w i | l d o w s ) 。 如果市内邮件转运路线问题中各点的时间窗口为( o ，m ) ，m 为一大正数， 此时，市内邮件转运路线问题就转化为一个一般的车辆路线问题( v e h i c l e r o u t i n gp r o b l e m ，v r p ) 。所谓车辆路线问题( v r p ) 是指，要求车辆从一中心 仓库出发，对所有顾客进行服务( 包括收集( 或派送) 货物) ，并且每个顾客只能 用一辆车辆进行服务：问题的目标就是设计一组满足上述要求的总长度最短的 路线。这也就是说，冲是市内邮件转运路线问题的特例。由于v r p 是一个 n p 难的问题，所以，市内邮件转运路线问题与v r p t w 一样，是n p 难的。 4 2 2v r p t w 的研究分析 v r t w 的研究始于6 0 年代，我们进行归纳，认为大致可分为置类： 第一类：主要是在6 0 年代至7 0 年代所作的研究，它们致力于一些简单的 土要基于局域搜索( 1 0 c a ls e a r c h ) 的启发式算法。 第二类：一些近似最优的启发式算法。 它们的计算结果比第一类的启发式算法好( f is h e r ，m i 。( 1 9 9 5 ) ， r h a n g i a h ，s r ，i t 1 o s a ma n dt s u n ( 1 9 9 2 ) ) ，在目标函数线性时，它们经常 能够求得问题的最优解。该类算法主要有：模拟退火( s i m u l a t e da n n e a l i n g ) 、 邻域搜索( t a b us e a r c h ) 和遗传算法( g e n e t i ca 1 9 0 r it h i n s ) 。k c t a n ，l i t l e e a n dk q z h u ( 1 9 9 9 ) 3 1 对这三种算法进行r 归纳和一定的改进，并对s o l o m o n 测试问题进行计算试验，有相当一部分计算结果i 分接近问题的最优解。j u l i e n b r a m e la n dd a v i ds i m c h i l e v i ( 1 9 9 3 ) ”1 还提出，一种基于选址问题( 1 , o c a t i o n p r o b l e m ) 的渐近最优的算法l b f l ，其对s o l o m o n 测试问题的计算结果许多都接 近最优解。 第三类：各种精确算法，这是该领域目前研究的重点。 我们对各种精确算法进行了归类，主要有以卜- 四种： a ) 动态规划方法由k o l e ne ta 1 ( 1 9 8 7 ) ”i 提出，但据目前是试验结果， 最多解决了有1 5 个顾客的问题，效果不是很好。 b ) k - 树法由f i s h e r ( 1 9 9 4 ) 提出，解决了s o l o m o n 测试问题中3 个有 1 0 0 个顾客的问题( c 1 0 1 ，c 1 0 2 ，c 1 0 7 ) 。 c ) 列生成法由o e s r o c h e r se ta 1 ( 1 9 9 2 ) ”3 提出，通过把v r p t w 分解问 题为主问题和子问题，主问题单纯形表迭代提供子问题求解所需的当前 对偶变量的解，然后求解子| 、口j 题生成主问题单纯形表迭代所需列的方 法。d e s r o c h e r se ta 1 还采用( q ，t ) ( 即车辆已经收集( 或派送) 的 货物量和车辆已经行驶的时间) 作为动态规划的状态集，构造了求解子 问题的拟多项式算法。该方法成功地解决了s o l o m o n 测试问题中一些有 1 0 0 个顾客的问题。 d ) l a g r a n g i a n 分解方法j o r n s t e n e ta l ( 1 9 8 6 ) 阳1 ，m a d s e n ( 1 9 8 8 ，1 9 9 2 ) h a l s e ( 1 9 9 2 ) “们等人通过不同l a g r a n g i a n 乘子生成方法构造了一系列 l a g r a n g i a n 分解方法。其思路大致i 列生成方法相似，不同之处在于用 当前l a g r a n g i a n 乘子替代主问题当前单纯形表的对偶变量的解代入子问 题中。这种方法解决了s o l o m o n 测试问题中一些有1 0 0 个顾客的问题。 3 市内邮件转运路线问题的数学模型及其一些性质 本章给出市内邮件转运路线问题的数学模型，讨论了市内邮件转运路线问 题的一些简单性质。 3 1 市内邮件转运路线问题的数学模型 市内邮件转运路线问题可以建立在以下的网络模型之上：令g = ( n ，a ) 为一个网络， 是弧集，n 是顶点( 客户) 集( 包括中心点0 ) 。对a 中每一条弧( i ， j ) 都有个距离c 。j 和持续时间o l j ，对n 中每一个顶点i 都有一个服务时间s ，。 不失一般性，我们假设对客户i 的服务时问包括在每条以i 为起点的弧( i ，j ) 的持续时间以内，即：令t t j = t i j + s i 。 另外，我们假设问题满足三角彳i 等式，即：c i i c i k + c v j ，j ，k n 。这是 因为对不满足三角不等式的问题，可以通过对每条弧的距离同时加上一个常数 c ，让它满足三角不等式，同时问题得最优解不改变。 市内邮件转运路线问题是求一组总距离最短的路线集旷；对任一路线r = ( o i l ，i 。，t 。，0 ) u r + ，它开始且终止于同一中心点0 。一条路线上的所有 客户由一辆车进行服务，每个客户的邮件转运量为q ，该路线上客户邮件量的 总和小于车辆装载量c ) 。每个顾客必须服务且仅服务一次。车辆到达客户i 的 时刻( 即离开客户i 的时刻) ； a ；，b t ，a ；和b ；分别是可以到达客户i 的 最早和最晚时刻。 网络g 上的市内邮件转运路线问题实际上是针对顶点集n 的集合剖分问题， 它可以用一个o - 1 规划来表示。任一条满足市内邮件转运路线问题要求的路线 称为可行路线，它们的全体记为r 。取6 ；，为一个常数，它的值为 统= 托路线糍过客篙洲u 。 c ，为路线r 的距离。路线距离定义为路线上所有弧的距离之和。设x ，为一个0 1 变量： f l采用路线r 1 0否则 这个集合剖分问题用于选择出满足市内邮件转运路线问题要求的最短距离 的路线集合。 m i n ， s t 6 威r = 1 ， j ，= 0 或1 3 2 市内邮件转运路线问题的一些性质 vi n 0 r r 通过分析，我们可以得到市内邮件转运路线问题的一些简单性质，这会有 利于我们对问题实例进行初步的分析。 性质1 ：使用车辆数的上限为j p l ，其中i ) - ( i a j e t 。， b 。，i e n o ) ) 。 这是由于对所有点j ( j l t o j 8 j ，b j _ q ) ： 定义d t 为网络g 2 ( n ，a ) ( 其中n = n a = a ，c i j = l ) 中成本小于t 的点数最多的路 线的点数； 性质3 ：使用车辆数的下限为( ( 1 n 卜i ) d i vd ) 。 顾客数为i n i l ，由于每条路线所经过的点的数日的上限为d ，所以使用车 辆数的下限为顾客数除以每条路线所经过的顾客数的上限d 并取上整数。 性质4 ：如果存在点j ，满足b ；t 。则问题无解。 性质5 ：如果存在点i ，满足o 0( i n ) 。 如果对于点i ，有t 。； a 。，b ； ，则初始解中路线0 i 0 不可行。此时我们对问题作一个变换，令c 。；= m ( m 为一大正整数) ，其目 的是使得如果存在通过点i 的可行路线，则该可行路线就一定会从子问题 中被选出来( 具体讨论见4 7 节) 。由于t 。；g a ；，b 。 ，所以边( 0 ，i ) 不会在 可行路线中出现，所以上述变换不会改变问题的可行解集。 4 5 问题的简化 为了简化问题，在计算问题之前，我们采取一些简化措施，尽量减少问题 的计算量。 4 5 1 边简化原则 a ) 对于两个节点i 、j ，如果i 点的最早开始服务时间a ；加上i 到j 的 车辆行驶时间t 。；超过了的j 点的最晚开始服务时间b ，则可以去掉 边( i ，j ) 。即如果a ；+ l ； b i ，则去掉边( i ，j ) ： b ) 对于两个节点i 、j ，如果i 点的最晚开始服务时间b 。加上i 到j 的 车辆行驶时间t ；小于的j 点的最早开始服务时间a ，则可以去掉边 ( i ，j ) 。即如果b l + t i i a 1 ，则去掉边( i ，j ) ： c ) 对于两个节点i 、j ，如果i 点的载熏量q ；加上j 点的载重量q 。大 于的车辆的总载重量q ，则可以去掉边( i ，j ) 。即如果q ；+ q ； q ，则 去掉边( t ，j ) ： 4 5 2 各点的时间窗口简化原则 各点的时间窗口的长度( b ；一a 。) 与子问题问题的计算复杂程度密切相关， 所以简化各点的时间窗口有助于简化子问题的计算。 a ) 对于点k 的最早开始服务时问a 。可以通过与它相关联的各点最早能 够到达的时间 m i “( i e a i + t i k 来修改，即 a k = m a x a k ，m i n b k ，m i n ( ik ) e e a i + t i k ) ) ： b ) 对于点k 的最早开始服务时间a 。可以通过它相关联的各点允许它最 早能够离开的时间 m i n 挑e a j - t 。j 来修改， 即 a k = m a x a k ，m i n b k ，m i n ( k j ) 。e 8 厂t k j ) ) ) ： c ) 对于点k 的最晚开始服务时间l k 可以通过与它相关联的各点最晚到 达的时间m a x ( ik m b i + l i k ) 来修改，即b k = m i n f b k ，m a x a k ，m a x 眠k ) ；e b i + t i k ) ) ： d ) 对于点k 的最晚开始服务时间b 。可以通过它相关联的各点允许它最 晚离开的时间 m a x f a k ，m a x ( k ，j ) e e f b 厂t k j ) 来修改， 即 b k = m i n ( b k ，m a x a k ，m a x ( k j ) e e b j - t k 3 ) 】) ： e ) 对于点k 的最晚开始服务时间b 。可以通过车辆必须驶回中心仓库的 时间t - t k o 来修改，即b k = m i n b k ，t - t k 0 ： 重复a ) 一e ) ，直至所有点的时间窗口不再改变。 f ) 对i n ，取i 的时间窗口与所有k ( ( k ，i ) e e ) 的时间窗口加上t 。 的交集，作为i 新的时间窗口。即： ( a i ，b i ) 2 ( a t ，b i ) n ( a z + t i 。，bj + t i i ) n i - 1 ( a i i + t i 。i ，b i l + t ，1 。) n ( a i + l + t 1 + l ，i ，b i + l + t i + t ，j ) i - 1 i - 1 ( i n - 1 + t n 1 。，b - 1 + t n1i ) 重复f ) ，直至所有点的时间窗口不再改变。 4 6 子问题求解的一种启发式算法 虽然以( q ，t ) 为状态集的动态规划方法是拟多项式的算法，但是当顾客 点数较多时，它的计算量仍是相当大。所以我们构造一种计算复杂度很小的启 发式算法来替代动态规划方法求解子问题，其思路如下： 对每个点i 计算所有与其相关联的弧( ( i ，j ) 和( k ，i ) ，其中j ，k n ) 的边际代价和：f ： + f k ；，并定义为各点的边际代价。按照各点的边际代价从小 到大进行排序，依次取出点i 生成回路( 0 ，i ，o ) ，并从剩余的点中选出一点 j 依照最小可行插入( 即：插入后路线可行且路线所增加的即约代价最小) 的 原则插入到回路中，形成新的回路。如果新的回路的即约代价为负，则子问题 求解结束，并把该负回路代入主问题；否则，继续按照插入点j 的方法从剩余 的点中选出一点插入到回路中，形成新的回路。如果点i 不能形成负回路，则 按照各点边际代价从小到大的原则取出下一点，并依照点i 生成回路的方法寻 找负回路。如果所有点都不能生成负回路，则问题求解结束。 启发式算法的算法描述： 步一：对所有i ( i n ) 计算 o 1o 2 。峨e ) c k + eu e e ) c ，) ，并按o ，从小 到大对各点排序；令i = l ； 步二：对点i 形成0 i 0 回路r ，令m = n i ： 步三：按最小插入原则选一点j ( j e m ) 插入到回路r 中，形成新的可行回 路r 。 如果点j 存在： 如果r7 的即约代价小于r 的即约代价，转步四：否则转步五： 如果点j 不存在，转步五： 步四：令m = m j ) ，r = r 。 如果r 的即约代价为负，这找到一条即约代价为负的回路r ，算法 结束；否则转步三： 步五：如果产删，则子问题中不存在负回路，算法结束；否则i 汁l ，转步二。 4 7 解的存在性 对于v r p t w 由于车辆可以在顾客允许的服务时间窗口之前到达顾客并等待 服务，所以我们可以很容易地找到v r p t w 解存在的充要条件： 分别对每结点i 从中心结点0 派一辆车进行服务。如果可行，则问题的 解存在：否则问题的解不存在。即：只要q i q ，t o i b ；，则问题有解。因此， v r p l 、w 问题的初始可行解可按照此方法来构造。 4 7 1 市内邮件转运路线问题解存在的充分条件 由于市内邮件转运路线问题与v r p t w 不同，车辆必须在节点的时间窗口内 到达，不能提前到达等待服务，所以市内邮件转运路线问题解存在的充要条件 与v r p t w 不同，所以我们只构造问题的初始解，并采取一定的技巧，使可以通 过求得的问题最终解来判断问题是否可行( 解的存在性) 。市内邮件转运路线问 题存在充分条件很显然，即只要：q i q ，a 。t 。；b ，则问题有解。 4 7 2 关于可行解存在的讨论 引理：如果子问题采用解动态规划方法求解，当子问题中找不到即约代价 为负的路线，而市内邮件转运路线问题线性松弛模型的基变量中仍有不可行路 线，则不可行路线只会是0 i 0 此类的路线。 证明：因为从子问题中产生的入基负回路都是可行的，如果基变量中还存 在不可行路线，那一定是在初始解中产生的。 定理：如果子问题采用解动态规划方法求解，当予问题中找不到即约代价 为负的路线，而市内邮件转运路线问题线性松弛模型的基变量中仍有不可行路 线，则该市内邮件转运路线问题实例没有可行解。 证明：由于在产生初始解时，我们把始发点0 与不可行路线所对应的点( 设 为 ) 之间的距离c 。；改为一大正整数m ，只要路线0 i 0 所对应 的变量不出基，则线性松弛模型主问题的对偶变量y ，一直为m + c 。所以只要 存在过i 点的可行路线，在子问题中它所对应的即约代价一定为负，那么在找 到最优解时，不可行路线0 i 0 必定已被一过的可行路线所替代； 否则，则表示不存在过i 点的可行路线，该实例没有可行解。 5 问题计算 下面针对杭州市内邮件转运系统进行计算，并与现行方案进行比较。 5 1 模型所需数据的处理 在计算每一班次的最优转运邮路时，需要该班次的下列数据 1 各支局之间的邮车行驶距离 2 邮车在各支局的停留装( 卸) 时间 3 各支局之间的邮车行驶时间 4 各支局的收( 发) 邮件估计量 5 邮车的装载量 6 邮车返回邮政枢纽的时间 7 各支局最早、最迟到达时间 5 1 1 各支局之间的邮车行驶距离 根据杭州市内局提供的部分局之间距离数据，结合在标准地图上各局 位置之间的距离测量办法，取得杭州市内邮政转运邮路所覆盖的全部3 0 个 支局之间的车辆行驶距离表( 见附表) 。 从表中数据，可直接获得各班次计算时需要的支局之间的距离数据。 5 1 2 各支局邮车装( 卸) 时间 杭州市内局的转运邮车时刻表( 见附表) ，提供了邮车在各支局装( 卸) 邮件所需的时间。 5 1 3 各支局之间的行驶时间 利用杭州市内局现行的转运邮车时刻表中反映的各支局之间行驶时 间，来估计车辆的行驶速度。这种时刻表是在杭州市内局多年使用中不断 1 9 改进的，因此它确实地反映了邮车运行所需要的时间。用这些时间数据来 估计，f 均车速无疑是可靠的。 将所有支局分为两类：市区和郊区。市区支局有：一支。_ | 支、三支、 四曼、五支、六支、七支、八支、九支、十支、十二支、凤起路、城东、 广场、武林门、杭大、站、翠苑。郊区支局有：浙大、古荡、拱宸桥、 三墩、半山、笕桥、留下、江边、浦沿、长河、西兴、转塘。考虑到市区 支局与市区支局之间，市区支局与郊区支局之间，郊区支局与郊区支局之 间的行驶均速可能有明显差异，因此先按上述三种情况分别测定平均车速， 然后再根据实际测定数据判定它们是否有明显差异。如有则分别处理，如 没有则把它们归并处理。 根据计算，可以得到： 班次市区与市区之间市区与郊区之间郊区与郊区之间差异情况 平均车速平均车速平均车速 班次2 62 0 公里 5 时2 69 5 公里4 , 时3 2 6 1 公里d , 时前二者无 ( 2 2 9 分公里)( 2 2 6 分公里)( 1 8 4 分公里)明显差异 班次2 3 6 2 公里，j 、时 二 ( 25 4 分公里) 班次2 1 3 5 公里4 , 时 2 3 9 0 公里d , 时 三 ( 2 8 1 分公里)( 25 1 分公里) 班次四1 9 8 0 公里，j 、时2 9 4 1 公里，j 、时3 0 1 5 公里d , 时后二者无 与班次 ( 3 0 3 分公里)( 2 0 4 分公里) ( 1 9 9 分公里)明显差异 由 班次1 5 0 8 公里，j 、时2 6 5 5 公里小时 2 97 0 公里d , 时 六 ( 3 9 8 分公里)( 2 2 6 分公里)( 20 2 分公里) 对上表中无明显差异的平均车速进行合并，求它们的平均值，得出下 表： 班次市区与市区之间市区与郊区之间郊区与郊区之间 平均车速、f 均车速平均车速 班次一2 6 4 3 公里，j 、时2 6 4 3 公里小时3 2 6 1 公里，j 、时 ( 2 2 7 分公里) ( 22 7 分公里)( 18 4 分公里) 班次二2 3 6 2 公里d , 时 ( 2 5 4 分公里) 班次三 2 13 5 公里小时2 39 0 公里小时 2 3 9 0 公里，j 、时 ( 2 8 1 分公里)( 2 5 1 分公里)( 2 5 1 分公里) 班次四和1 9 8 0 公里小时 2 95 6 公里，j 、时2 9 5 6 公里小时 班次五 ( 3 0 3 分公里)( 2 0 3 分公里)( 2 0 3 分公里) 班次六1 50 8 公里j j , 时2 65 5 公里小时2 9 7 0 公里d , 时 ( 3 9 8 分公里)( 2 2 6 分公里)( 20 2 分公里) 各支局之间的行驶时间( 见附表) 可由以下公式算得 。6 0 0 c i i ，v i j + t j t i i ：支局i 到支局j 的行驶时间( 分) 。i i ：支局i 到支局j 的行驶距离( 公里) ”i i ：支局i 到支局j 的行驶速度( 公里，j 、时) t l ：邮车在支局装( 卸) 所需时间( 分) 5 1 4 各支局收( 发) 邮件估计量 为了估计各支局各班次每天的邮件收发量，对9 7 年1 月1 4 日至2 0 f 1 和5 月1 臼至7 日的各支局收发情况作了全样本调查。由此计算出的轻、 重、快、慢日收发平均值作为四种邮件目收发量的估计基础。 由于邮件数量有一定的季节特征，因此两周的数据不能全面反映全年 的情况，被抽样的两周有可能刚好都处于邮件数量较少的季节，或者刚好 都处于邮件较多的季节。因此，采用对各种邮件日收发平均值乘上一个比 例系数的办法来估计各种日收发量，即： l h b 件日收( 发) 照估计值一两胤的邮件口收( 发1 量均值 x 比例系数k 这个比例系数k ，采用杭州市内局日邮件总最分布的极值与被抽样两 周的日邮件总量比值。 以收集到的杭州市内局今年1 月1 口至7 月1 6 日的全部日邮件总量 数据( 见附件) 作为调查日邮件总量分布的依据。经过计算，得到 日收邮件总量( 袋)口发邮件总量( 袋) 均值 1 9 3 81 11 8 9 3 2 7 标准方差 5 5 60 53 1 82 3 2 e r 置信区问 3 0 5 00 02 5 3 0o o 置信区间内极值 2 9 6 92 4 1 4 被抽样两周的均值 1 8 6 1 2 l1 5 3 74 3 这样，可计算得比例系数k ： k 2 9 6 9 1 8 6 1 2 1 。2 4 1 4 1 5 3 7 4 3z16 所有邮件的数量要折算成标准袋数量，可按照以下关系折算： 1 袋轻件 = 05 标准袋邮件 1 袋重件 = 1 标准袋邮件 1 袋特快件 一1标准袋邮件 1 捆报纸 一o5标准袋邮件 这样，即可估计出每个班次各支局邮件的收发量( 标准袋) 。例如，第 ：二班次茴兴支局在被抽样两周内轻、重、快、慢四种邮件的平均收量分别 为0 0 7 ，0 0 0 ，o0 7 ，o 0 0 ，平均发量分别为o 2 1 ，00 7 ，o 0 7 ，o8 6 ，则它们 的收、发量估计值计算为： 西兴支局班次三邮件收量估计值 21 6 【o 0 7 0 5 + 0 0 0 + 0 0 7 + o 0 0 k 0 5 1 = 0 1 6 8 西兴支局班次三邮件发量估计值 = i6 0 2 1 0 5 + 0 0 7 + 00 7 + 0 8 6 0 5 i = l0 8 估计各支局的邮件量是为了控制邮车的装载景不超过限度( 2 5 0 标准 袋) 。如果一班次邮车要经过6 个支局，那么邮车 二任何时候的装载量均不 能超过2 5 0 标准袋，而目前的所采用的运筹学算法仅能控制收邮件装载量 或仅控制发邮件装载量，因此在计算中，每个支局只能有一个收邮件量或 发邮件量。当一个支局在某个班次既收邮件，又发邮件时，以收、发量中 火的一个作为该支局的邮件量。 5 1 5 其它数据 杭州市内邮政转运采用的是4 5 吨位的卡车，这种车的邮件装载量q 为2 5 0 标准袋。 各班次转运邮车返回枢纽的时间t 为：班次一约9 6 分，班次2 约6 0 分，班次3 约8 0 分，班次四、班次五共约1 4 6 分，班次六约1 2 3 分。 对第一班次的转运路线，有市区支局的报纸必须在6 0 分钟内送达的 要求，因此要给市区支局加上最迟时间限制，即加上时间窗口【0 ，6 0 。 对任一转运邮路，一般有先近后远的要求，即先发市区支局的邮件， 后发郊区支局的邮件。为此，对市区支局要加适当的时间窗e l 【o ，o 【t 】，0 城东一 八支 转塘一 枢纽3 9 61 1 1 91 7 0 3 2枢纽一 四支 三支一 六支一 九支 枢纽 1 2 44 8 11 5 6 7 3枢纽一 七支 留下一 枢纽 3 2 18 5 9 1 1 0 8 4枢纽一 十二支一 三墩一 拱宸桥一 枢纽 4 0 21 0 2 21 0 5 o 5枢纽一 五支 十支 半山一 笕桥 枢纽3 5 61 0 6 7“0 3 距离总计： 1 5 9 9 启发式算法 车辆路线距离时间邮件量 l枢纽一 二支一 枢纽 5 61 9 74 4 3 2枢纽 四支一 十支一 半山 笕桥一 枢纽3 0 78 5 61 2 8 ，0 3枢纽一 五支一 枢纽 1 7 65 5 o4 6 6 4枢纽 七支一 留下一 枢纽 3 2 18 5 91 1 0 8 5枢纽 城东一 八支一 转塘一 枢纽 3 4 09 2 21 2 6 0 6枢纽一 九支 枢纽 1 46 28 6 7枢纽一 十二支一 枢纽 1 7 。44 4 56 5 5 8枢纽一 三支一 六支一 拱宸桥一 三墩 枢纽 3 9 o1 0 6 41 2 3 3 距离总计： i 7 7 8 2 4 现行方案 车辆路线距离时间邮件量 【 1枢纽一 三支一 十支一 六支一 转塘一 枢纽 4 5 11 2 4 41 2 5 1 2枢纽 二支 八支 城东一 九支一 枢纽 1 3 75 1 11 4 5 7 3枢纽一 四支一 七支一 留下一 枢纽 3 5 79 9 01 7 5 i 4枢纽一 五支一 半l 【i 一 笕桥一 枢纽 3 5 71 0 2 o1 0 2 2 5枢纽 十二支一 拱宸桥一 三墩一 枢纽 4 0 41 0 2 61 0 5 0 距离总计： 1 7 0 6 班次二： 涉及支局：十支，五支，八支，六支，十二支，七支，城东，九支。 t = 7 0 ，q = 7 0 ，q = 1 0 0 子闯题求解方法线性规划解接数规划解车辆数分支定界数运算时 间( 秒) 动态规划方法 5 625 62 40 2 启发式算法 5 6 25 6240l 动态规划方法 车辆路线距离时间邮件量 1枢纽一 十支一 五支一 枢纽1 8 。25 6 28 8 0 2枢纽一 八支一 六支一 枢纽1 3 75 4 87 9 6 3枢纽一 十二支一 七支一 枢纽1 7 06 5 29 2 7 4枢纽一 城东 九支一 枢纽7 32 8 59 5 2 距离总计：5 6 2 启发式算法 i 车辆路线距离时间 邮件量 i 1枢纽一 十支一 五支一 枢纽1 8 25 6 28 8 o 2枢纽一 八支一 六支一 枢纽 1 3 75 4 87 9 6 3枢纽 十二支一 七支一 枢纽1 7 06 5 29 2 7 4枢纽一 城东一 九支一 枢纽 7 32 8 59 5 2 距离总计： 5 6 2 现行方案 车辆路线距离时间邮件量 l枢纽一 九支一 五支 枢纽 1 835 6 59 3 ，2 2 枢纽一 七支一 二支 一 枢纽 1 7 o6 5 29 2 7 3枢纽一 六支一 八支 枢纽 1 3 75 4 87 9 6 4枢纽一 十支一 城东 枢纽 1 9 25 8 89 0 o 距离总计：6 8 2 2 7 班次j ! ： 涉及支局：城东，八支，二支，九支，杭火，浙人，翠苑，十二支，七支，杭 大，十二支，翠苑，浙大，七支，_ | 支，一站，拱宸桥，五支，武林门。 t = 1 0 0 ，q = 5 0 ，q = 8 0 子问题求解方法线性规划解整数规划解车辆数分支定界数运算时问 ( 秒) 动态规划方法 7 20 47 3419 5 启发式算法 7 25 57 341 4 动态规划方法 车辆路线距离时间邮件量 1枢纽 城东一 八支一 二支一 九支一 枢纽1 3 76 0 56 8 8 2枢纽 杭大一 浙大一 翠苑 十二支一 七支一2 2 58 4 57 6 9 枢纽 3枢纽 武林门一 五支一 拱宸桥一 一站一 十支2 4 59 4 35 9 8 一 枢纽 4枢纽 一支一 六支一 广场 四支一 三支一 枢1 2 35 7 67 8 9 纽 距离总计： 7 3 o 启发式算法 车辆路线距离时间邮件量 1枢纽一 三支一 四支一 广