邮政运输网络中的邮路规划和邮车调度(共18页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
邮政运输网络中的邮路规划和邮车调度
情为你奉上
专心---专注---专业
，，这里我们的邮路是指一辆邮车按顺序经过并收发邮件的支局序列，序列两端加上出发总局。, 分别表示第个邮局接收与发出去的邮件， 分别表示第条邮路中邮车全程包括收发邮件的总时间与邮车全程中最重时刻的装载量, 表示第个邮局到第个邮局的最短距离则，表示第条邮路在第个邮局时的装载量，表示出发时的装载量则：
，显然有
显然在保证邮路最少的情况下，邮路最短时我们有多目标规划模型
最少空车损失的模型为
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
这里由于问题的规模比较小，我们这里及以后各问题都利用枚举法求最小的。
3．2模型求解
3．2．1．粒子群优化算法（PSO）简介
PSO是从模拟鸟群的捕食行为中得到启示的算法。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索. PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解. 另一个极值是整个种群目前找到的最优解。在附录中我们将详细介绍PSO问题的优化技术。
3．2．1粒子群优化算法求解带有约束条件的多回路组合优化问题
3．2．2．1邮路的编码
本文中，路径使用整数型编码方法表示。把所有的邮路都写成一行，不同的邮路中间用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辆车：
3．2．2．2粒子适应度函数的定义
当给定时，我们直接利用目标函数中的倒数来定义粒子适应度函数发现，当我们随机取初始群体时，由于可行解的数量相对于任意解的数量非常少，一般来讲，所有的粒子都不符合约束条件，这样我们利用目标函数来定义粒子适应度函数，一般最后的结果都是不满足约束条件的解。 所以我们首先要解决的问题是怎么设计粒子适应度函数来实现粒子从非可行解向可行解过度。
粒子适应度函数定义：设某粒子由条邮路组成，假设强制完成这所需要的各自所需时间为，各自全程最大负荷为，设函数
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
则，粒子的适应度函数为：
。
其中，可以看成是一个一个粒子（解）到可行解集合的距离。
上述公式引入的目的是避免的值相差太大而引起的信息损失。怎么确定的值呢？我们在给定下随机抽取了大量样本计算了的平均值，我们发觉它们一般都相差10倍左右，（和速度一个数量级），所以我们一般让。具体的值要根据最终优化的目标函数的值的范围而定。在实际的操作中我们发现，这样定义的适应度函数可以非常高效的找到可行解，这样我们就可以首先建立一个大的可行解的数据库，每次从数据库中提取部分解，和随机产生的部分解一起作为初试种群，利用如下适应度函数
，
就可以进行总时间（总邮路长，总运输费用）的最终寻优了。
这里表示空车的损失。
3．2．2求解结果
定义：总成本=空车损失+总运行成本（3元/公里）
我们分别给出了空车率损失最少（方案1）与总成本最少（方案2）的两个方案
方案1：空车率损失最小
邮路
空车率损失
运行费用
最大运输量
耗时
邮车1
X1-6-5-7-(8)-16-10- X1

417
65

邮车2
X1-13-1-2-3-4-(10)-11- X1

492
64

邮车3
X1-(10)-9-8-