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

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

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date邮政运输网络中的邮路规划和邮车调度摘要:邮政运输网络中的邮路规划和邮车调度一、问题重述邮政运输问题是邮政生产过程四大环节的物质基础。时限与成本是邮政运输问题的两个重要指标，时限是指邮件、报刊处理、传递的最大时间限制，是邮车调度需要满足的基本要求，成本影响着企业的经营，包括道路成本以及空车成本，在邮路设计时，在满足时限的前提下，需要使成本最小。时限和成本对于邮路规划和邮

2、车调度有着重要的影响。中国的邮政运输网络采用以邮区中心局作为基本封发单元和网路组织的基本节点，负责处理、封发、运输邮件，在此基础上组织分层次的邮政网。邮路是邮政运输网络的基本组成单元，它是指利用各种运输工具按固定班期、规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。本文中要考虑的问题是：某地区的邮政分为地市局、县局和支局三级机构，该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。该地区地市局为D，周围共有5个县局X

3、1，X5，每个县局包含若干个支局Z1， Z73。区级邮政运输网至少负责收发5个县局以及所在地市的16个支局Z58, Z59，Z73的邮件；各县局邮政运输网必须覆盖本县内区级邮车不能到达的支局。见图1，红线为区级邮政运输网，黑线为县级邮政运输网。区级邮政运输网贯穿各个县局，收寄邮件；县级邮政运输网贯穿本县支局。邮件的流动方向如图2所示，箭头表示邮件的流向，不表示实际路径。图1图2该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。该地区的邮政运输流程如下：Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi和沿途支局收寄的邮件运送回地市局D；Step

4、2:区级邮车离开后，县局Xi将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局Xi；Step4: 区级第二班次邮车从地市局D出发将邮件运送到各县局Xi和沿途支局，并将各县局Xi收寄的邮件和沿途支局收寄的邮件运送回地市局D。这个问题里，对县局Xi，它的时限包括：区级第一班邮车开走一小时后才可发出县级邮车，沿途在各支局耗时5分钟，县级邮车须在区级第二班邮车开走一小时前返回。对于地市局D，它的时限包括：第一班邮车出发时间必须在6:00之后，沿途在各支局耗时5分钟，在

5、各县局需要等到县级邮车返回一小时之后才能离开，返回地市局D必须在11:00之前。当邮车运载能力有限时，每辆邮车在各个支局、省局装载后都不应超过其运载能力。二、模型假设1区级两个班次邮车的行驶路线相同，行驶时间及费用也相同。2区级邮政运输网必须至少覆盖该地市附近的16个支局Z58, Z59, ,和5个县局X1，X5。3各县邮政运输网必须覆盖本县内区级运输车不到达的区域。4县级邮车平均时速为30km/h，区级邮车的平均速度为65km/h，邮车在各支局装卸邮件耗时5分钟，在各县局装卸邮件耗时10分钟，不考虑任何突发事件。5邮车在邮路上相邻两点邮局间行使时只走最短路径。6第一问中假设X1区每天每个支局

6、收发的邮件数保持不变。三、问题一模型与求解31模型的建立对于这个问题我们只关心完成这个县邮运任务的最少的邮车数量以及在最少的邮车数量实现邮路总长度最短或者总耗时间最短。针对此问题我们假设第一辆地市区邮政运输车不到达X1内的任何支局。在这个假设下要求县邮车需要到达X1内所有的支局。在这个问题中我们理解的每天邮车只有一个班次指的是允许多辆车在同一时间内出发，但每天只允许出发一次。每辆邮车的最大装载量不超过63，最长行使时间不超过6小时。设X1县内共有条邮路，分别为，表示第条邮路上一共需要收发邮件邮支局的总数且（每个支局都要经过），这里我们的邮路是指一辆邮车按顺序经过并收发邮件的支局序列，序列两端加

7、上出发总局。, 分别表示第个邮局接收与发出去的邮件， 分别表示第条邮路中邮车全程包括收发邮件的总时间与邮车全程中最重时刻的装载量, 表示第个邮局到第个邮局的最短距离则，表示第条邮路在第个邮局时的装载量，表示出发时的装载量则：，显然有显然在保证邮路最少的情况下，邮路最短时我们有多目标规划模型最少空车损失的模型为这里由于问题的规模比较小，我们这里及以后各问题都利用枚举法求最小的。32模型求解321粒子群优化算法（PSO）简介PSO是从模拟鸟群的捕食行为中得到启示的算法。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远

8、。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索. PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解. 另一个极值是整个种群目前找到的最优解。在附录中我们将详细介绍PSO问题的优化技术。321粒子群优化算法求解带有约

9、束条件的多回路组合优化问题3221邮路的编码本文中，路径使用整数型编码方法表示。把所有的邮路都写成一行，不同的邮路中间用0隔开。条邮路 可以编码成：。例如，对本文中县局X1，该地区支局有16个，若最少需要3辆车运输邮件，编码3 2 1 13 12 11 0 10 8 7 6 5 4 0 14 9 16 15，表示的邮路为：第1辆车：第2辆车：第3辆车：3222粒子适应度函数的定义当给定时，我们直接利用目标函数中的倒数来定义粒子适应度函数发现，当我们随机取初始群体时，由于可行解的数量相对于任意解的数量非常少，一般来讲，所有的粒子都不符合约束条件，这样我们利用目标函数来定义粒子适应度函数，一般最后

10、的结果都是不满足约束条件的解。 所以我们首先要解决的问题是怎么设计粒子适应度函数来实现粒子从非可行解向可行解过度。粒子适应度函数定义：设某粒子由条邮路组成，假设强制完成这所需要的各自所需时间为，各自全程最大负荷为，设函数则，粒子的适应度函数为：。其中，可以看成是一个一个粒子（解）到可行解集合的距离。上述公式引入的目的是避免的值相差太大而引起的信息损失。怎么确定的值呢？我们在给定下随机抽取了大量样本计算了的平均值，我们发觉它们一般都相差10倍左右，（和速度一个数量级），所以我们一般让。具体的值要根据最终优化的目标函数的值的范围而定。在实际的操作中我们发现，这样定义的适应度函数可以非常高效的找到可

11、行解，这样我们就可以首先建立一个大的可行解的数据库，每次从数据库中提取部分解，和随机产生的部分解一起作为初试种群，利用如下适应度函数，就可以进行总时间（总邮路长，总运输费用）的最终寻优了。这里表示空车的损失。322求解结果定义：总成本=空车损失+总运行成本（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-1

12、5-(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的总成本为1390.4（元），方案2的总成本为1175（元）因此可以看出方案2

13、比方案1在考虑了运输成本时更好，可以节约成本215.4（元）。所以我们认为，只考虑空车损失是不优化的，我们认在邮车数量确定下没有必要考虑空车损失。图3： 方案1邮路图 方案2邮路图 四、问题二模型与求解41模型的建立对于这个问题我们只关心完成这个区邮运任务的最少的邮车数量以及在最少的邮车数量实现邮路总长度最短或者总耗时间最短。假设市局对D于Xi县运送邮件的邮车已经安排好了，地市局第一班次邮车到达Xi并卸装完邮件的时间为，从Xi返回到地市局的时间为，通过Xi县的地市局第一班次邮车邮路总时长为，那么Xi县可用于运输的时间为则：如图所示：6:006:00+18:00-118:00第一班区级邮车出发第

14、一班邮车到达并卸完邮件县级邮车出发县级邮车返回第二班区级邮车卸载邮件并离开第二班邮车返回D1T21县级邮车可运输的最长时间图4：县级邮车可用时间与区级邮车邮路运行时间关系图这说明地市局的邮车在邮路上运行的时间越短对县局越有利。从而我们的优化原则简化为：首先，把地市支局与县局（不包括县支局）放在一起，看成一个多回路组合优化问题，其目标是尽可能用最少的车，总邮路最短而且每条邮路的时间要限制在5个小时内。其次，在地市支局与县局邮路优化好了之后，就能利用上面公式算出每个县局可用于运输的时间，从而各县的优化问题都转化成了一个带有时间限制的多回路组合优化问题。带有时间限制的多回路组合优化问题比问题一在形式

15、上简单。这里我们不分别对市，县给出模型，我们只以某县为例给出一个统一的模型。对于市局的优化问题上，只需目标函数与约束条件要多考虑收发邮件在每个县局多5分钟与速度是65千米/小时且每辆车的可利用时间为5小时。设：某县待收发邮件的支局为共有个，县局为，需要辆车运输（对应条邮路），且可用于运输的时间为则。分别为：，表示第条邮路上一共需要收发邮件邮局的总数且（每个支局都要经过），这里我们的邮路是指一辆邮车按顺序经过并收发邮件的支序列，两端是出发总局。分别表示第条邮路中邮车全程包括收发邮件的总时间与邮车全程中最重时刻的装载量, 表示第个邮局到第个邮局的最短距离则，则：显然在保证邮路最少的情况下，邮路最短

16、时我们有模型同样我们对的优化采用枚举发，邮路长度采用POS算法，所有的情况都与问题一的求解一样，只是不考虑邮车最大负重的影响。寻找可行解数据库的时候我们利用适应度函数为：。在有可行解数据库的支持下寻找最有解的适应度函数为：。4.2求解结果：区级邮车路线到达县邮路路程耗时邮车1X1，X2D-62-9-10-X1-12-X2-18-63-66-67-D2524.8769邮车2X3D-68-65-64-X3-31-30-34-35-71-D2694.9718邮车3X4D-72-73-42-41-X4-36-70-69-D1863.6115邮车4X5D-61-59-52-X5-53-58-60-D26

17、94.8051总路程976千米，总耗时18.265小时。县级邮车路线县编号可用时间邮路编号邮路路程（千米）耗时（小时）X15.1231邮车1X1-14-X1361.2833邮车2X1-3-4-2-1-13-X11374.9883邮车3X1-5-6-7-8-16-15-11-X11345.05X25.1231邮车1X2-17-19-26-20-X21415.0333邮车2X2-22-23-24-25-21-X21274.65X35.0282邮车1X3-27-X3682.35邮车2X3-28-29-32-33-X31344.8X46.3885邮车1X4-37-38-39-40-43-X41405.

18、0833X55.1949邮车1X5-54-55-56-57-X51324.7333邮车2X5-51-46-44-X51445.05邮车3X5-50-49-48-45-47-X51334.85县级邮路总长度1326千米，总耗时47.871小时。总结于下表：总邮车数区级：4辆15辆县级：11辆总路程=2区级路程+县级路程3278千米邮路示意图：图5：不跨县运输最短路程邮路图由于公路可以重复行使，因此会出现一个邮局有多条邮路经过的情况。为了更清楚的表示出在一条邮路上哪些点是装卸邮件的，图中所示直线只代表两点间的最短距离，不代表公路。五、问题三模型与求解5.1模型的建立该问题以第二道题为基础，在使邮路

19、尽量少、尽量短的基础上考虑如何通过重新规划区域进一步优化邮路。当允许在一定程度上打破行政区域限制的时候，首先考虑边界地带支局的划分。这里采用聚类的方法来重新划分5个行政区域，不包含地市局D的重新划分。设支局Zi到县局Xj的距离为Zi到Xj的最短路径距离，。我们将距离作为重新划分行政区域的依据。聚类过程如下：(1) 计算支局Zi到各县局的距离；(2) 找到距离取最小值时所对应的，将 Zi与Xj归为一类；(3) 转 (1)，计算下一支局与各县局的最短距离，直到所有支局都划分到各个县局；通过考查最短距离，聚类结果如下图所示：图6：聚类结果可见，原来区域的划分基本没有改变，但是对于边界地带的支局，则被

20、分到了不同的区域。Z56和 Z57由原来的X5区域划分到了X1区域；Z27由原来的X2划分到了X3；Z34由原来的X4区域划分到了X3区域；Z44由原来的X5区域划分到了X4区域。从聚类图上，我们可以得到四个有益的建议：(1) 通过第二题的解答，我们知道由X3有一条单独邮路通往Z27，如果能够用X2区域内的某条邮路将Z27覆盖，则会减少X3内的邮路数量，同时要使X2区域内的邮路保证时间限制。(2) 对于Z44，因为其与X5的距离很远，因此，在X5区域内为了能够将邮件输送到Z44而特意开辟出了X5-51-46-44这样一条辐射型邮路。若可以将该支局转移到县局X4进行邮件处理，X5地区东部的若干个

21、支局将可以用一条邮路串连起来，从而减少邮路量。此时，也要保证X4区域内的邮路依旧满足时间限制，我们可以通过调整区级前往X4区域的邮车路线来实现，适当缩短路线以增大X4区域内邮车的可运输时间。(3) 对于Z34，它与X4的最短距离为71，最短路径为X4-36-35-34，而Z34与X3的最短路径为X3-31-30-34，距离为62，但由于X3-31-30-34已经在区级邮路上，因此Z34是否适合划分到X3并不确定。(4) Z56和 Z57由原来的X5区域划分到了X1区域，Z56、Z57到X5的最短距离分别为64，55，到X1的最短距离分别为57，52，距离差异并不大。并且对于X5，其邮路至少要3

22、条，Z56 、Z57两点已在最短路径上，而若将Z56 、Z57两加入到X1中，形成的新的邮路是否满足时间要求不确定。因此调整Z56和 Z57到X1区域是否可以使总路程变短，需要通过程序演化计算得出。5.2求解结果区级邮车路线到达县邮路路程耗时邮车1X1，X2D-62-9-10-X1-12-X2-18-63-66-67-D2524.8769邮车2X3D-68-65-64-X3-31-34-35-70-69-D2694.9718邮车3X4D-72-73-42-41-X4-37-36-71-D1863.6115邮车4X5D-61-59-52-X5-58-60-D2654.6603总路程972千米。

23、县级邮车路线县编号可用时间邮路编号邮路路程（千米）耗时（小时）X15.1231邮车1X1-14-X1361.2833邮车2X1-3-4-2-1-13-X11374.9883邮车3X1-5-6-7-8-16-15-11-X11345.05X25.1231邮车1X2-17-19-26-20-X21415.0333邮车2X2-27-22-23-24-25-21-X21385.1X35.0282邮车1X3-28-29-30-32-33-X31344.8833X46.3885邮车1X4-44-43-40-39-38-X41615.7833X55.3397邮车1X5-54-55-56-57-53-X514

24、05.0833邮车2X5-50-49-48-47-45-46-51-X51375.15县级邮路总长度1158千米。总结于下表：总邮车数区级：4辆13辆县级：9辆总路程=2区级路程+县级路程3102千米在打破县界的情况下，经过优化得到总邮车数减少了2辆，并且可以缩短176千米，节省528元运费。其中路线变化如下图所示：变化的邮路示意图：图7：允许跨县运输后优化结果中改变的邮路图六、问题四模型与求解6.1模型的建立首先分别对X1至X5五个县找新的中心，方法为在一个县的区域内选择一个点使其他的点到他的最短路径之和最小。结果显示为X1区的新中心为Z4，X2的新中心为Z21，X3的新中心为Z31，X4的

25、新中心不变，X5的新中心为Z51。从新应用问题2中的算法进行计算。然后分别对更改的四个新中心求出到地市局的距离然后与原县局到地市局的距离进行比较。结果如下表所示：县中心距离X1原址X192新中心Z487X2原址X289新中心Z21109X3原址X398新中心Z3166X5原址X5124新中心Z5193从表中可以看出，除X2以外其他三个新中心到地市局的距离都小于旧址到地市局的距离。但X1县的变化很小，X3和X5变化较大。由于X1和X2共用一辆区级邮车，如果X1迁址，那么将会加大此辆区级邮车的路程，从而减少了县级邮车可利用的时间。从而将不满足时间限制条件。因此应首先考虑X3和X5的迁址。进一步优化

26、后的结果仍要覆盖原区县邮路覆盖的所有邮局。于是目标变为在一个小区域求解在一定约束条件下的最短路径问题。设Xi县的原邮路条数（区级邮车数加上县级邮车数）为，模型为 新方案邮车数辆等于 条新邮路需覆盖原邮路上的所有点（邮局）6.2求解结果区级邮车路线到达县邮路路程耗时邮车1X1，X2D-62-9-10-X1-12-X2-18-63-66-67-D2524.8769邮车2X3（31）D-68-31-30-32-34-35-70-69-D1733.4115邮车3X4D-72-73-42-41-X4-37-36-71-D1863.6115邮车4X4（52）D-61-59-52- 58-60-D2033.

27、6231总路程814千米。 县级邮车路线县编号可用时间邮路编号邮路路程（千米）耗时（小时）X15.1231邮车1X1-14-X1361.2833邮车2X1-3-4-2-1-13-X11374.9883邮车3X1-5-6-7-8-16-15-11-X11345.05X25.1231邮车1X2-17-19-26-20-X21415.0333邮车2X2-27-22-23-24-25-21-X21385.1X3（31）6.5885邮车131-29-65-64-X3-33-28-311666.033X46.3885邮车1X4-44-43-40-39-38-X41615.7833X5（52）6.3769邮

28、车152-53-54-55-56-57-521635.85邮车252-50-49-48-47-45-46-51-521335.0167县级邮路总长度1209千米。总结于下表：总邮车数区级：4辆13辆县级：9辆总路程=2区级路程+县级路程2837千米迁址后的优化结果显示，邮车运输的总路程长度每天可以减少265千米，即可节约运费795元/天。2.3县局迁址建议书作为邮件运输行业，我们的目标是以最少的成本完成邮件运输任务。因此合理的优化的选址及邮路设计工作是非常必要的。其中选择邮局地址尤为重要，特别是那些具有中转功能的邮局地址。对于本市来说，从邮局分布图上可以看出，地市局与各个县局相距都比较远，这就

29、为地市局的邮件运输工作带来了不便。因此为了能够尽可能的减少邮件运输成本，希望可以对部分县局的位置进行调整，以达到全局优化的目的。图中的县X3是选址最不合理的县局。X3县内的支局主要分布在偏东北方向，而县局却设在了西南方向。这导致了它到各个支局的距离非常大，造成了邮件运输过程中的费用损失。因此非常不合理。县X3中的点Z31是整个县的中心，即所有其他点到他的距离之和最短。又因为它与地市局的距离较X3近很多，因此将县局迁址到此会节省相当一部分的邮件运输费用。迁址后的最佳邮路为：区级邮路：D-68-31-30-32-34-35-70-69-D 总路程173千米 县级邮路：31-29-65-64-X3-

30、33-28-31 总路程166千米 这样会比原来的旧地址旧邮路每天节省160千米的路程，即可节省480元运费。 本市除了可以在X3县迁址外，还可以在X5县迁址。因为在X5县，支局分布比较松散，一条过县局的南北向直线将其分为东、西方向两个部分。在这条直线附近支局Z52与地市局的距离最近，如果以这个点为县局新址的话，也可以减少相当的运输成本。以Z52为新址的最优邮路为：区级邮路：D-61-59-52- 58-60-D 总路程203千米县级邮路1：52-53-54-55-56-57-52 总路程163千米县级邮路2：52-50-49-48-47-45-46-51-52 总路程133千米比原来的县局旧

31、地址旧邮路每天可以节省105千米的路程，即可节省315元运费。如果将这两处县局地址更改后，每天可节省795元运输费用，相当可观。图8：迁址后改变的邮路图九、拓展性问题研究 拓展1：可以考虑区级邮车两次的线路不同，这样有很大可能可以降低成本。因为对于各个支行来说每天收发一次就够了。如果两次路线相同，那么那些区级邮车经过的支行每天就会被收发两次，造成资源浪费。拓展2：对于问题2可以将多增加一辆车的成本加入到目标函数中直接进行整体优化，比如，区级邮车增加一辆的成本为100元，县级邮车增加一辆的成本为50元，那么目标函数就变为表示区级邮车数，表示i县邮车数。拓展3：我们总是希望区级第一班次邮车以最快的

32、速度到达县局，第二班次邮车能够尽量晚的离开县局，这样就保证了县局能有更多的时间运输，可以节省县局车辆。为达到这样的目的，我们可以假设第二班次区级邮车可以先走耗时长的路径到达县局，然后走耗时短的路径返回地市局。这就使得第二班次邮车可以逆着第一班次邮车的路线走。这是对于县局Xi它可用的时间为：参考文献1郭文忠、陈国龙，求解TSP问题的模糊自适应粒子群算法，计算机科学Vol.33, No.6, 20062高海兵、周驰、高亮，广义粒子优化模型，计算机学报 Vol.28, No.12, Dec.20053肖健梅、黄有方、李军军、王锡淮，基于离散微粒群优化的物流配送车辆路径问题，系统工程 Vol.23,

33、No.4, Apr.20054黄岚、王康平、周春光、庞巍，董龙江，彭利，粒子群优化算法求解旅行商问题，吉林大学学报，Vol.41, No.4, 477480, 20035程录庆、胡涛，车辆路由问题在邮路规划中的应用研究，中国管理信息化，Vol.9, No.1, Jan.20036费蓉、崔杜武，中国邮递员问题的动态规划算法研究，计算机研究与发展，42（2）：294299，20057陈龙、王国胤、刘心松、聂能，一种启发式邮政运输调度优化方法，电子学报，Vol.28, No.8, Aug.20008钱颂迪等运筹学，清华大学出版社，2004年9月附录1粒子群优化算法（PSO）简介PSO是从模拟鸟群的捕

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

35、己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值。在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置: （1） （2） 是粒子的速度, 是当前粒子的位置。如前定义是介于（0，1）之间的随机数. 是学习因子。 为惯性权重。这里我们只给出PSO算法的一个基本框架在附录中我们将详细介绍对于TSP问题的优化技术。PSO的基本算法步骤如下：(1) 初始化粒子群，即随机设定各粒子的初始位置和初始速度；(2) 计算每个粒子的适应度值；(3) 对每个粒子，比较它的适应度值和它经历过的最好位置的适应度值，如果更好，更新；(4)

36、 对每个粒子，比较它的适应度值和群体所经历最好位置的适应度值，如果更好，更新；(5) 根据(1.1)式和(1.2)式调整粒子的速度和位置；(6) 如果达到结束条件(足够好的位置或最大迭代次数)，则结束；否则转步骤(2)。PSO算法的改进本文中，我们利用文献1中提到的交换子和交换序的概念，对基本PSO算法进行改进。定义1：设个节点的TSP问题的解序列为。定义交换子为交换解中的点和，则为解经过交换算子操作后的新解。定义2：一个或多个交换子的有序队列就是交换序，记作。，其中是交换子，它们之间的顺序是有意义的。交换序作用于一个解上，意味着交换序中的所有交换子一次作用于该解上。定义3：若干个交换序可以合

37、并成一个新的交换序，定义为两个交换序的合并算子。定义4：不同的交换序作用于同一解上可能产生相同的新解，所有有相同效果的交换序的集合成为交换序的等价集。定义5：在交换序等价集中，拥有最少交换子的交换序成为该等价集的基本交换序。例如，现有一解(9 8 7 6 5)，交换子为，则通过交换子操作后的新解为(9 5 7 6 8)；若交换序为，则通过交换序操作后的新解为(5 9 6 7 8)。现在重新构造基本PSO算法中的速度公式：(1.6)其中为随机数。表示交换序中所有交换子以概率保留；表示基本交换序中所有交换子以概率保留；表示基本交换序中所有交换子以概率保留。求解步骤描述如下：(1) 初始化粒子群，即

38、给群体中的每个粒子赋一个随机的初始解和一个随机的交换序；(2) 如果满足结束条件，转步骤(5)；(3) 根据粒子当前位置，计算其下一个位置，即新解； 计算和之间的差，其中是一个基本交换序，表示作用于得到； 计算，其中也是一基本交换序； 根据(1.3)式计算速度，并将交换序转换为一个基本交换序； 计算搜索到的新解： (1.7) 计算的适应度值，与个体经历的最好位置的适应度值比较，若更好，则更新；(4) 计算所有个体的适应度值，与群体经历的最好位置的适应度值比较，若更好，则更新，转步骤(2)。(5) 显示求出的结果值。在本文中，我们解决所有问题的思路是优先考虑区级邮路，因为其路程相对县级邮路较长，邮路遍及5各县局，是主要传输的路径；其次再考虑县级邮路，使其在数量和长度上都达到最小量。即先寻求区级邮路最优解，在此基础上求解县级邮路最优解。5参数调节在算法运行中，参数时，可以较快的找到可行解和最优解-