模型建立于蚁群算法.doc

确定型模型的建立
1、模型的基本假设与前提
①模型中包含一个回收中心和多个回收客户点，每辆车都由回收中心出发，经由各个客户点完成回收任务后，再次回到回收中心。
②回收中心的容量没有限制。
③每个回收客户点的回收量已知。
④回收中心同各回收客户点相对位置坐标己知，且路径长度对称。
⑤每个回收客户点仅被一辆车服务一次。
⑥每辆车的载重能力和总容积限制已知，单个回收客户点的回收量不能超出单车载重能力和容积约束的1/2。
⑦对于每一辆车，只有当其路径上所有回收量大于最小载重量和最小容积时才能出车。
⑧每辆车每次任务的总行驶里程不能超过车辆允许最大行驶距离。
⑨回收的货物可以混装。
⑩单位运输成本同运输距离呈线性关系。
2、模型参数及变量定义
P:所有节点集合，P={i}，i=0表示回收中心，i=1，2，…，n表示回收客户
点
S:回收客户点集合，且P=SU{0}
V:所有车辆集合，V={k}，k=1，2，…，m
D:各节点间距离矩阵，D=
:各节点间距离，且,,
:第k辆车的固定成本，即增加一辆车所产生的费用
：第k两车的单位距离费用
：第k辆车的额定最大载重量
：第k辆车的额定最小载重量
：第k辆车的额定最大容积
：第k辆车的额定最小容积
：第k辆车允许的最大行驶距离
：第i个回收客户点出货物的总重量
：第i个客户点处货物的总体积
：0-1变量，当第k辆车从i至j进行回收时，值为1，否则为0
：0-1变量，当第k辆车服务第i个回收客户点时，值为1，否则为0
（3）目标函数
（1）
(4)约束条件
n=3,m=2 （2） （3）
（4）
（5）
(6)
(7)
(8)
(9)
（10）
(11)
目标函数（1）表示车辆使用、运行成本最小；约束条件（2）保证每个客户点均被服务；（3）、（4）保证驶入和驶出某个客户点的车辆为同一辆，保证每个节点仅被服务一次；（5）、（6）为车辆最大、最小载重限制；（7）、（8）为车辆最大、最小容积约束；（9）为车辆最大行驶距离约束；（10）、（11）为变量、取值。
不确定型模型的建立
1、模型的基本假设与前提
①模型中包含一个回收中心和多个回收客户点，每辆车都由回收中心出发，经由各个客户点完成回收任务后，再次回到回收中心。
②回收中心的容量没有限制。
③每个回收客户点回收物品的重量和体积均为随机变量，且服从的分布己知。
④回收中心同各回收客户点相对位置坐标己知，且路径长度对称。
⑤每个回收客户点仅被一辆车服务一次。
⑥每辆车的载重能力和总容积限制已知，允许单个回收客户点的回收量在一定置信水平下满足单车辆的载重能力和容积限制。
⑦对于每一辆车，只有当其路径上所有回收量大于最小载重量和最小容积时才能出车。
⑧允许每辆车每次任务的总行驶里程在一定置信水平下满足车辆允许最大行驶距离。
⑨单位运输成本同运输距离呈线性关系，回收的货物可以混装。
2、模型参数及变量定义
P:所有节点集合，P={i}，i=0表示回收中心，i=1，2，…，n表示回收客户
点
S:回收客户点集合，且P=SU{0}
V:所有车辆集合，V={k}，k=1，2，…，m
D:各节点间距离矩阵，D=
:各节点间距离，且,,
:第k辆车的固定成本，即增加一辆车所产生的费用
：第k两车的单位距离费用
：第k辆车的额定最大载重量
：第k辆车的额定最小载重量
：第k辆车的额定最大容积
：第k辆车的额定最小容积
：第k辆车允许的最大行驶距离
：第i个回收客户点出货物的总重量
：第i个客户点处货物的总体积
：0-1变量，当第k辆车从i至j进行回收时，值为1，否则为0
：0-1变量，当第k辆车服务第i个回收客户点时，值为1，否则为0
:目标函数的置信水平
:单车辆载重能力约束置信水平
:单车辆容量约束置信水平
:单车辆总行驶里程约束置信水平
:目标函数在置信水平为刀时所取的最小值
Pr{.}:{.}中事件成立的概率
(3)构建需求不确定情况下车辆配置及路径优化问题的机会约束模型:
目标函数: （1）
约束条件: （2）
（3）
（4）
（5）
（6）
（7）
（8）
（9）
（10）
目标函数(1)表示目标函数(车辆使用、运行成本最小，同时使车辆回收货物小于/大于车辆额定载重/容积时)在置信水平为厂时所取的最小值;约束条件(2)表示目标函数取得最小值的概率应不小于置信水平;约束条件(3)保证每个客户点均被服务，且每辆车均从回收中心出发;(4)(5)保证驶入和驶出某一客户点的车辆为同一辆，保证每个节点仅被服务一次;(6)表示满足单车辆载重限制的概率应不小于置信水平;(7)表示满足车辆容量限制的概率应大于置信水平;（8）表示车辆最大行驶路程约束的概率应大于置信水平;(9)(10)为变量、取值。

蚁群算法
1、觅食示意图

2、 蚂蚁觅食原理
如图所示, 设A 是巢穴, E 是食物源, HC 为一障隘物. 由于障随物存在, 蚂蚁只能经由H 或C 由A 到达E, 或由E 到达A.
设每个时间单位有30 只蚂蚁由A 到达B, 有30 只蚂蚁由E 到达D 点, 蚂蚁过后留下的激素物质量(以下我们称之为信息) 为1. 为方便, 设该物质停留时间为1.
在初始时刻, 由于路径BH、BC、DH、DC 上均无信息存在, 位于B 和E 的蚂蚁可以随机选择路径. 从统计的角度可以认为它们以相同的概率选择BH、BC、DH、DC.
经过一个时间单位后, 在路径BCD 上的信息量是路径BHD 上信息量的二倍.
t= 1 时刻, 将有20 只蚂蚁由B 和D 到达C, 有10 只蚂蚁由B 和D 到达H. 随着时间的推移, 蚂蚁将会以越来越大的概率选择路径BCD, 最终完全选择路径BCD. 从而找到由蚁巢到食物源的最短路径.
3、基本蚂蚁算法的特点可以概括如下:
(1)、较强的鲁棒性，对蚂蚁算法的模型稍加修改，便可以应用于其它问题。
(2)、分布式计算，蚂蚁算法是一种基于种群的进化算法，可以避免过早的收敛，
本质上具有并行性，其搜索过程不是从一点出发，而是从多个点同时进行，这种分布式多智能体的协作是异步并发进行的，分布并行的模式将大大提高整个算法的运行效率和快速反应的能力。
(3)、易于与其它方法结合，蚁群算法很容易与多种启发式算法结合，以改善算法的性能，如同遗传算法、禁忌搜索算法、人工免疫算法等算法的结合都衍生出多种混合算法。
(4)、正反馈，从而能迅速找到好的解。
(5)、强启发式，能在早期的寻优中迅速找到合适的解决方案.
4、具体算法
设蚁群中蚂蚁的数量为m , dij ( i , j = 1 , 2 , ⋯, n) 表示点i 和点j 之间的距离.
bi ( t) 表示t 时刻位于点i 的蚂蚁的个数. 显然 ∑ bi ( t) =m.
τij ( t) 表示t 时刻在点i , j 连线上残留的信息量.
初始时刻,各条路径上信息量相等,设τ ij (0) = C( C 为常数) . 蚂蚁k ( k = 1 ,2 , ⋯, m) 在运动过程中,根据各条路径上的信息量决定转移方向.
在t 时刻蚂蚁k 由点i 转移到点j 的概率 (11)
ηij —先验知识或称为能见度, 在TSP 问题中为点i 转移到点j 的启发信息;
α—在路径ij上残留信息的重要程度;
β—启发信息的重要程度;
tab —记录蚂蚁k 当前所走过的城市, 称为记忆列表, 集合tab随着进化过程作动态调整.
经过n 个时刻, 所有蚂蚁都完成了一次遍历. 此时, 计算每一只蚂蚁所走过的路径, 并保存最短路径Lmin = min { Lk ， k = 1 , 2 , ⋯, m} .
在蚂蚁完成一次循环以后, 各路径上的信息量进行如下调整
(12)
(13)
为蚂蚁k 在本次循环中在点i 和点j 之间留下的信息量, 一般有两种更新方式：
（1）、每只蚂蚁每前进一步都会释放信息素并更新经过路径上的信息素浓度
（2）、只在结束整个循环后才更新.
5、步骤
(l)、参数初始化:令t=0，循环次数=0，设置最大循环次数，将l只蚂蚁随机地放到n个城市，将每条边(i，j)上的信息素设为一个常数，且，将出发点城市设置到禁忌表中;
(2、)按状态转移式(11)选择下一个城市;
(3)、修改禁忌表，即选择好之后将蚂蚁移动到下一个城市，并把该城市移动到蚂蚁个体的禁忌表中;
(4)、循环执行第(2)步和第(3)步，直到每只蚂蚁都生成一条路径;
(5)、计算第s只蚂蚁所走路径的总长度Ls;
(6)、根据式(12)和式(13)更新所有路径上的信息量;
(7)、若循环次数从，则循环结束并输出计算结果，否则清空禁忌表并转到第(2)步。