车辆路径安排的遗传算法研究--python
车辆路径安排的遗传算法研究
1.1问题描述
1.1.1车辆路径问题
车辆路径问题（Vehicle Routing Problem-VRP）是为⼀些车辆（确定或不确定数量）确定访问⼀些客户的路径，每⼀客户被⽽且只被访问⼀次，且每条路径上的客户需求量之和不超过车辆的能⼒。⽬标是使总成本（如距离、时间等）为最⼩。有时间窗车辆路径问题（V ehicle Routing Problem with Time Windows-VRPTW）是在VRP上加上了客户的被访问的时间窗约束.在VRPTW问题中，除了⾏驶成本之外，成本函数还要包括由于早到某个客户⽽引起的等待时间和客户需要的服务时间。
近年来有许多学者运⽤遗传算法来求解车辆路径问题。从他们的成果来看，遗传算法求解车辆路径问题，与传统⽅法相⽐⾄少有两个优点。①如果使⽤数学规划直接求解VRP问题，在问题规模较⼤时，问题的求解将耗费系统巨⼤的空间与很长的时间资源。汪寿阳等⼈的研究指出，当运⽤整数规划求解⼀个包含50个客户、10个仓库、15辆汽车的实际问题时，规划的分⽀将有54510个，约束将有上千亿个。显然⽤传统的优化⽅法求解这样的问题是不经济的。⽽采⽤遗传算法求解，它的运算规模⽤种规模的⼤
⼩来确定，运算时间也可⽤进化代数来控制，求解⼤规模的VRP问题时优点突出。②使⽤数学规划求解问题时，往往需要预先给出⼀个可⾏解，然后逐步迭代优化，但是VRP 问题的初始可⾏解往往难以获得。但遗传算法应⽤⾃然界优胜劣汰的规律，可以从⾮可⾏解开始计算，在计算过程中逐渐解出可⾏解及最优解，并淘汰不可⾏解
本⽂中采⽤遗产算法，实现了从某⼀总仓库，去往⼋个分仓库，并返回总仓库的车辆运输调度。具体问题如下描述:
1.1.2问题描述
随机⽣成⼀个有8个分仓库的VRP问题，规定各仓库坐标在[0，100]×[0，100]间随机⽣成，指定车容量为8。各分仓库的需求量在[0，4]间随机⽣成，满载系数a=0.85，使单辆车能承担更多的运输任务。取种规模pop_size=20，进化代数gen=50.得VRP问题各项数据如表1-1所⽰。
仓库名称仓库位置仓库需求量
总仓库(91,97)0
仓库1(97,1)  2.32
仓库2(79,52)  3.14
仓库3(67,95)  1.3
仓库4(16,59)  1.94
仓库5(23,85)  3.93
仓库6(17,96)  1.68
仓库7(69,44)  2.86
仓库8(69,19)  1.4
交⼜概率为0.6。各仓库间运输成本c，由各仓库间的直线距离决定，即：
根据各仓库的需求量，计算出需要的货车数。
1.1.3线性模型c=
ij
x−x+y−y
(i j)2(i j)2 m=+
[0.85×8
18.57
]1=3
令表⽰点i到点j的运输成本，本⽂中⽤路程描述。总仓库的编号为0，各分仓库的编号为i（i=1，2，…，8），定义变量如下：
可以得到该问题的车辆调度数学模型：
2.遗传算法
遗传算法基本流程框架如下图所⽰：
c ij x =ijs {1，车s 由i 驶向j
0，否则
y =is {1，点i 的货运任务由车s 完成
0，否则
min Z =
c x i =0∑8
j =0∑8
s =1∑
3
ij ijs
s .t.x =j =1∑
8
ijs y ;i =is 0,1,2,⋯,8;s =1,2,⋯,3
x =i =0
∑
8
ijs y ;j =js 1,2,⋯,8;s =1,2,⋯,3
y =s =1∑
3
is {1;i =1,2,⋯,8
3;i =0
g y ⩽i =0
∑
8
i is 8
x =ijs 0或1;i ,j =0,1,2,⋯,8;s =1,2,⋯,3
2.1遗传编码
车辆路径问题的染⾊体使⽤⾃然数编码，其解向量可编成⼀条长度为8+3+1的染⾊体： [0. 2. 7. 0. 8. 3. 0. 5. 6. 4. 1. 0.]
在整条染⾊体中，⾃然数，表⽰第k个分仓库，0的数⽬为4个，代表总仓库，并把⾃然数编码分为3段，
形成3个⼦路径，表⽰由3辆车完成所有运输任务。这样的染⾊体编码可以解释为：第1辆车从总仓库出发，经过2，7分仓库后，回到总仓库，形成了路径1；第2辆车也从总仓库出发，途经8，3分仓库后，回到总仓库，形成了路径2；第3辆车也从总仓库出发，途经5，6，4，1分仓库后，回到总仓库，形成了路径3，完成所有运输任务，构成了3条路径。 ⼦路径1：总仓库→分仓库2→分仓库7→总仓库； ⼦路径2：总仓库→分仓库8→分仓库3→总仓库；
⼦路径3：总仓库→分仓库5→分仓库6→分仓库4→分仓库1→总仓库。在编码过程中遵守特定的编码规则：1. ⽣成⼀个⾃然数（仓库个数）的全排列2. 将m（车辆数）+1个0插⼊到全排列3. ⾸尾必须是0，且两个0不能相邻
2.2 适值计算
车辆路径问题的适值计算可以将容量约束式转为运输成本的⼀部分，运输 成本变为：
式中，M为⼀很⼤的正数，表⽰当⼀辆车的货运量超过其最⼤承载量时的惩罚系数。根据磁体的实际应⽤，本⽂另M=300。由于在计算适值时，我们⼀般需要最⼤的，因此在输出运输成成本时，我们输出成本的倒数。进⼀步运⽤下式可将运输成本转换成适值函数：
式中，；为第i条染⾊体的适值，；为当前种中最优染⾊体的运输成本，；为第i条染⾊体的运输成本。
i ks min Z =
c x +i =0∑8
j =0∑8
s =1∑
3
ij ijs M
random pythonmax g y −8,0s =1∑
3
[i =0
∑
8
i is ]
f =i Z /Z i ′
i
f i Z i ′
Z i
2.3 选择
本步采⽤赌进⾏选择。⾸先选择适应值最⼤的个体进⼊⼦代。然后由上⼀步计算得到适应值，根据适应值计算各个个体的累计函数，根据累计函数，进⾏赌选择19个个体。赌实现伪代码如下：
赌⼜称⽐例选择⽅法．其基本思想是：各个个体被选中的概率与其适应度⼤⼩成正⽐．(1)计算出体中每个个体的适应度f(i=1，2，…，M)，M为体⼤⼩；(2)计算出每个个体被遗传到下⼀代体中的概率：
（3）计算出每个个体的累积概率；
q[i]称为染⾊体x[i] (i=1, 2, …, n)的积累概率 (4)在[0，1]区间内产⽣⼀个均匀分布的伪随机数r；
(5)若r<q[1]，则选择个体1，否则，选择个体k，使得：q[k-1]<r≤q[k] 成⽴； (6)重复(4)、(5)共19次
2.4遗传操作
2.4.1 交叉
遗传操作调⽤了python中封装的geatpy库，其中交叉运算采⽤部分映射交叉PMX，调⽤的⽅法名为xovpm。部分映射交叉PMX实现过程：
第⼀步，随机选择⼀对染⾊体（⽗代）中⼏个基因的起⽌位置（两染⾊体被选位置相同）：
第⼆步，交换这两组基因的位置：
P x =
(i )f
x ∑j =120(j )
f x (i )
q =
i P x j =1∑
i
(j )
第三步，做冲突检测，根据交换的两组基因建⽴⼀个映射关系，如图所⽰，以2-0-5这⼀映射关系为例，可以看到第⼆步结果中⼦代1存在两个基因2，这时将其通过映射关系转变为基因5，以此类推⾄没有冲突为⽌。最后所有冲突的基因都会经过映射，保证形成的新⼀对⼦代基因⽆冲突：
2.4.2 变异
采⽤互换变异（reciprocal exchange mutation）。互换变异是随机选择两个不同位置上的基因，并将这两个位置的基因相互交换，如图
但是由于经过交叉以及变异后，染⾊体不再遵守路径优化问题的特殊的染⾊体编码形式，还要保证编
码符合要求，具体要求见遗产编码的编码规则。所以需要做进⼀步的冲突检测，使染⾊体符合本⽂的要求。定义染⾊体修正汉顺sort_pop（），是新⽣成的⼦代染⾊体符合编码规则。
3.问题改进与实施
本节通过对相关⽂献的阅读，对该⽂中的路径优化问题进⾏了深⼊的探讨，对在原先的代码的基础上，提出了改进，但并未彻底实现。第四节代码源于第三节的探讨。
3.1带时间窗的路径规划
在上述车辆路径规划中我们并未讨论每个仓库的是否要求在哪⼀个时间段内将物资运输出去，但是在实际的⽣产运输之中，例如某像苏宁等电器商场在顾客购买商品，进⾏电器配送时，顾客可能会产⽣时间需求，既在某⼀时间段[a,b]内将货物运到，因此需要在VRP上进⼀步改进。
3.1.1改进所需的参数：
时间窗⼝，说明车辆必须在之前到达客户i；在前虽然车辆已经到达但仍要的等到$ t_{i j}$ 每条弧（i，j）对应⼀个时间值
3.1.2 线性规划模型增加新约束：
a ,
b [i i ]b i a i a i
s +ik t −ij K 1−x ⩽(ijk )s ,∀i ,j ∈jk N ,∀k ∈V
a ⩽i s ⩽ik
b ,∀i ∈i N ,∀k ∈V

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。