《邮政运输网络中的邮路规划和邮车调度》

《《邮政运输网络中的邮路规划和邮车调度》》由会员分享，可在线阅读，更多相关《《邮政运输网络中的邮路规划和邮车调度》（30页珍藏版）》请在金锄头文库上搜索。

1、邮政运输网络中的邮路规划和邮车调度一、问题重述邮政运输问题是邮政生产过程四大环节的物质基础。时限与成本是邮政运输问题的两个重要指标，时限是指邮件、报刊处理、传递的最大时间限制，是邮车 调度需要满足的基本要求，成本影响着企业的经营，包括道路成本以及空车成本， 在邮路设计时，在满足时限的前提下，需要使成本最小。时限和成本对于邮路规 划和邮车调度有着重要的影响。中国的邮政运输网络采用以邮区中心局作为基本封发单元和网路组织的基本节 点，负责处理、封发、运输邮件，在此基础上组织分层次的邮政网。邮路是邮政 运输网络的基本组成单元，它是指利用各种运输工具按固定班期、 规定路线运输 邮件，并与沿线有交接频次的

2、邮政局、所交换邮件总包所行驶的路线。本文中要考虑的问题是：某地区的邮政分为地市局、县局和支局三级机构， 该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。该地区地市局为D,周围共有5个县局X1 ,，X5 ,每个县局包含若十个支局 Z1 ,Z73。区级邮政运输网至少负责收发 5个县局以及所在地市的16 个支局Z58, Z59 ,Z73的邮件；各县局邮政运输网必须覆盖本县内区级 邮车不能到达的支局。见图1，红线为区级邮政运输网，黑线为县级邮政运

3、输网。 区级邮政运输网贯穿各个县局，收寄邮件；县级邮政运输网贯穿本县支局。邮件 的流动方向如图2所小，箭头表小邮件的流向，不表小实际路径。该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。该地区的邮 政运输流程如下：Stepl:区级第一班次邮车从地市局 D出发将邮件运送到各县局 Xi和沿途支 局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D;Step2:区级邮车离开后，县局 Xi将当天区级第一班次邮车及前一天的区级 第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应 的县级邮车；Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运 送回县局Xi ；St

4、ep4:区级第二班次邮车从地市局 D出发将邮件运送到各县局Xi和沿途 支局，并将各县局 Xi收寄的邮件和沿途支局收寄的邮件运送回地市 局D。这个问题里，对县局Xi,它的时限包括：区级第一班邮车开走一小时后才可 发出县级邮车，沿途在各支局耗时 5分钟，县级邮车须在区级第二班邮车开走一小时前返回。对于地市局D，它的时限包括：第一班邮车出发时间必须在 6:00 之后，沿途在各支局耗时 5分钟，在各县局需要等到县级邮车返回一小时之后才能离开，返回地市局D必须在11:00之前。当邮车运载能力有限时，每辆邮 车在各个支局、省局装载后都不应超过其运载能力。二、模型假设1 .区级两个班次邮车的行驶路线相同，行

5、驶时间及费用也相同。2 .区级邮政运输网必须至少覆盖该地市附近的16个支局Z58, Z59,和5个县局X1 ,，X5。3 .各县邮政运输网必须覆盖本县内区级运输车不到达的区域。4 .县级邮车平均时速为 30km/h ，区级邮车的平均速度为 65km/h ,邮车在 各支局装卸邮件耗时5分钟，在各县局装卸邮件耗时10分钟，不考虑任何突发 事件。5 .由廿车在邮路上相邻两点邮局问行使时只走最短路径。6 .第一问中假设X1区每天每个支局收发的邮件数保持不变。三、问题一模型与求解3 . 1模型的建立对于这个问题我们只关心完成这个县邮运任务的最少的邮车数量以及在最少的邮车数量实现邮路总长度最短或者总耗时间

6、最短。 针对此问题我们假设第一辆地市区邮政运输车不到达X1内的任何支局。在这个假设下要求县邮车需要到达X1内所有的支局。在这个问题中我们理解的每天邮车只有一个班次指的是允许多辆车在同一时间内出发，但每天只允许出发一次。每辆邮车的最大装载量不超 过63，最长行使时间不超过6小时设X1县内共有N条邮路，分别为X1，Y,1，Y,2 丫1危1, X1，E,1，Y2,2丫2业飞1X1, Yn,1，Yn,2YN,nN，X1 ,几表小N第t条邮路上一共需要收发邮件邮支局的总数且nt 16 (每个支局都要经过)，t丫,j1 Y2，j2 if，i i2andjJ2，这里我们的邮路是指一辆邮车按顺序经过并收发邮件

7、的支局序列，序列两端加上出发总局。Zr(i)，Zs(i)分别表示第i个邮局 接收与发出去的邮件，气，巳分别表示第k条邮路中邮车全程包括收发邮件的总时间与邮车全程中最重时刻的装载量，D(i，j)表示第i个邮局到第j个邮局的最 短距离则，Wk，t表示第k条邮路在第t个邮局时的装载量，Wk，o表示出发时的装载 量则:nk560nkD（Yk，ni1，Yk，ni）D（X1，Yk，1）D（Yk，nk，X1）i 230nktW，tZr（Yk，nj）Zs（Yk，ni）j 1i 1tZSj），tj 11,2nknk，Wk，oZr（Yk，nj），显然j 1有 RkmaXWk，Wk，1，W显然在保证邮路最少的情况下

8、,邮路最短时我们有多目标规划模型MinZwNNW2Tkk 1maxRR，Rn 65max，Tn 6 Nst.nt 16tYi1，j1 Y2，j2if， i1 i2andj1 j?w2，w10, w20最少空车损失的模型为MinEN nk 12( (65 WGDg&i) (65 Wk,o)D(X1,Y3 (65 W )D(Ym，X1),Rn 65TN6if , ii2 and j j2k 1 t 1max( R1, R2, maxT,T2, st. Nnt 16 tY1J1 Y2J2这里由于问题的规模比较小，我们这里及以后各问题都利用枚举法求最小的N。3 . 2模型求解3 . 2 . 1 .粒子

9、群优化算法（PSO ）简介PSO是从模拟鸟群的捕食行为中得到启示的算法。设想这样一个场景：一群 鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。 但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一 只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值， 每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最 优粒子在解空间中搜索.PSO初始化为一群随机粒子（随机解）。然后通过叠代

10、找 到最优解。在每一次叠代中，粒子通过跟踪两个 极值来更新自己。第一个就是 粒子本身所找到的最优解.另一个极值是整个种群目前找到的最优解。 在附录中 我们将详细介绍PSO问题的优化技术。3 .2. 1粒子群优化算法求解带有约束条件的多回路组合优化问题 3 . 2. 2 . 1邮路的编码本文中，路径使用整数型编码方法表示。把所有的邮路都写成一行，不同的 邮路中间用0隔开。N条邮路X1,Y,1,Y,2 Yl,mX1, X1Ml，Y2,2 丫2曲飞1, X1,Yn,1,Yn,2 丫队飞 1 可以编码Z1 Z13成：丫,1，丫1,2 丫1,叩。，丫2,1, 丫2,2 丫2应，O ，0，Yn,1, Yn

11、,2 丫啪。例如，对本文中县局 X1, 该地区支局有16个，若最少需要3辆车运输邮件，编码3 2 1 13 12 11 0 10 8 7 6 5 4 0 14 9 16 15,表示的邮路为：第1辆车：X第2辆车：XZ10Z7 ZZ4 X第3辆车：X乙4Z16Z153 . 2. 2 . 2粒子适应度函数的定义当N给定时，我们直接利用目标函数中Tk的倒数来定义粒子适应度函数发现，当我们随机取初始群体时，由丁可行解的数量相对丁任意解的数量非常少， 一般来讲，所有的粒子都不符合约束条件，这样我们利用目标函数来定义粒子适 应度函数，一般最后的结果都是不满足约束条件的解。所以我们首先要解决的问题是怎么设计

12、粒子适应度函数来实现粒子从非可行解向可行解过度。粒子适应度函数定义：设某粒子i由m条邮路组成，假设强制完成这 m所需要的 各自所需时间为T1,T2, ,Tn ,各自全程最大负荷为R1,R2, ,Rn ,设函数x . if xp(x )贝U,粒子i的适网度函数为：01f(i) m1m,1, 2都大丁0。mm其中， f （Tj 6）f（Rj 65）可以看成是一个一个粒子（解）到可行解集合的距离。上述公式引入1, 2的目的是避免 匕，L的值相差太大而引起的信息损失。怎 么确定1, 2的值呢？我们在m给定下随机抽取了大量样本计算了 Rj, Tj的平均值，我们发觉它们一般都相差10倍左右，（和速度一个数

13、量级），所以我们一般让 110 2。1,2具体的值要根据最终优化的目标函数的值的范围而定。在实际的操作中我们发现，这样定义的适应度函数可以非常高效的找到可行解，这样我们就可以首先建立一个大的可行解的数据库，每次从数据库中提取部分解，和随机产生的部分解一起作为初试种群，利用如下适应度函数F(i) 1F (i)mmm ，1 10000f (Tj 6) 1000f (Rj 65) Tjjjj就可以进行总时间（总邮路长，总运输费用）的最终寻优了。F(i)m1 10000 f (Tj1m6) 1000 f(Rj 65) E这里E表示空车的损失。3 . 2 . 2求解结果定义：总成本=空车损失+总运行成本

14、（3元/公里）我们分别给出了空车率损失最少（方案 1）与总成本最少（方案2）的两个万案邮路空车率损运行费最大耗时方案1:空车率损失最小失用运输量邮车1X1-6-5-7-(8)-16-10- X113.785417655.05邮车2X1-13-1-2-3-4-(10)-11- X117.169492645.6667邮车3X1-(10)-9-8-15-(14)-12-14-X133.446417625.05在这种方案下总的由空车率造成的损失为 64.4 （元），为所有路径中最小的。总 运行费用为1326 （元）。方案2 :总成本最小邮路空车率损失运行费用最大运输量耗时邮车1X1-3-2-1-13-12-11- X153.354489595.933邮车2X1-10-8-7-6-5-4- X122.8315634邮车3X1-14-9-16-15- X121.938273613.667在这种方案下总的由空车率造成的损失为 98 （元），总运行费用为1077 （元）可以算出方案1的