遗传算法求解带时间窗的车辆路径规划问题
1.遗传算法
遗传算法简介
遗传算法（Genetic Algorithm，简称GA）是⼀类借鉴⽣物界的进化规律（适者⽣存，优胜劣汰遗传机制）演化⽽来的基于种的随机化搜索⽅法。它是由美国的J.Holland教授1975年⾸先提出，其主要特点是直接对结构对象进⾏操作，不存在求导和函数连续性的限定；具有内在的隐并⾏性和更好的全局寻优能⼒；采⽤概率化的寻优⽅法，能⾃动获取和指导优化的搜索空间，⾃适应地调整搜索⽅向，不需要确定的规则。遗传算法的这些性质，已被⼈们⼴泛地应⽤于组合优化、机器学习、信号处理、⾃适应控制和⼈⼯⽣命等领域。遗传算法是现代智能计算中的关键技术之⼀。
遗传算法基本思想
在现实⽣活中，⽣物的染⾊体通过基因控制了⽣物的性状，⽽⽣物的性状决定了⽣物在环境中的适应度，适应度⾼的⽣物，其基因更容易流传下来，随着时间的不断流逝，整个种的适应度随之提⾼。
遗传算法和现实⾮常类似，⾸先将问题的解通过⼀定的⽅法，编码到染⾊体中，通过适应度函数，得到每个个体的适应度，通过选择，将适应度⾼的个体保留到下⼀代中，不断迭代，即可获得满意解。
遗传算法流程
2.带时间窗的车辆路径规划问题介绍
车辆路径规划问题介绍
车辆路径规划问题，经过60年来的研究与发展，研究的⽬标对象，限制条件等均有所变化，已经从最初的简单车辆安排调度问题转变为复杂的系统问题。最初的车辆路径规划问题可以描述为：有⼀个起点和若⼲个客户点，已知各点的地理位置和需求，在满⾜各种约束的条件下，如何规划最优的路径，使其能服务到每个客户点，最后返回起点。通过施加不同的约束条件，改变优化的⽬标，可以衍⽣出不同种类的车辆路径规划问题。同时车辆路径规划问题属于典型的NP-hard问题，其精确算法能求解的规模很⼩，故启发式算法也就成了研究热点。
VRPTW简介
oled tftVRPTW(Vehicle routing problem with time windows)即带时间窗的车辆路径规划问题，其对于每⼀需求点加⼊了时间窗的约束，即对于每⼀个需求点，设定服务开始的最早时间和最晚时间，要求车辆在
时间窗内开始服务顾客。
需求点的时窗限制可以分为两种，⼀种是硬时间窗(Hard Time Window)，即要求车辆必须在时间窗内开始服务顾客，早到必须等待，迟到就拒收，另⼀种是软时间窗(Soft Time Window)，不⼀定要在时间窗内开始服务顾客，但是在时间窗外开始服务必须要惩罚，以惩罚代替等待与拒收是软时间窗和硬时时间窗的最⼤的区别。
VRPTW的数学模型如下：
（2.2）保证了每个顾客只被访问1次
（2.3）保证了装载的货物不超过容量
（2.4）（2.5）（2.6）确保了每辆车从depot出发最后回到depot
（2.7）（2.8）确保在时间窗内开始服务
在中详解介绍了如何⽤禁忌搜索（Tabu Search）算法求解VRPTW。
3.算法具体实现
染⾊体设计
水三相点瓶蒸汽发电机在论⽂：A simple and effective evolutionary algorithm for the
*vehicle routing problem *中，作者提出了在⽤GA解决VRP时的⼏点注意事项，如下图所⽰：
简单来说染⾊体的设计可以遵循以下两点：
1. 使⽤和TSP问题中类似的染⾊体、编码，没有分隔符
2. 使⽤split⽅法将染⾊体转化为问题的解
在使⽤GA求解VRPTW的过程中，常见的问题就在于交叉后产⽣的⼤量不可⾏解，这⾥采⽤分割的思想，⼀个染⾊体所存的解是split函数操作后所产⽣的最优分割。这样所得到的解都为可⾏解，⼤⼤减少了⽆效搜索。
在所有分割⾥，能最⼩化⽬标函数的即为最优分割。其实这就是⼀个编码和解码的过程。
下⾯我们来具体介绍⼀下这个split⽅法:
⼤家可能会觉得获得最优分割是⼀个很困难的事情，其实引⼊图论的思想，利⽤Bellman-Ford算法，
在O(n^2)内就能获得最优分割。
image
上⾯两个图展⽰了如何把原问题转化为⼀个图论中的问题：
将每个基因位设为⼀个点，假如将i到j连接，其路径满⾜容量约束和时间窗约束，则视为从i到j存在⼀条权值为路径长度的边。则最优分割即为从染⾊体开头的基因的点到结尾的基因的点的最短路。利⽤Bellman-Ford算法，可在O(n^2)中求出最优分割。
流程图如下：
800电话是免费的吗image
体多样性
遗传算法中常见的问题就是早熟，过早收敛。为了避免这种情况的发⽣，就要保证⼦代个体中各个个体的不同。
如何判断个体之间是否相同有很多算法，⼩编这⾥采⽤通过适应度的不同来判断的⽅法：
image
保安对讲机
即两个个体的适应度相差⼤于⼀个值，即视为不同的个体。
crossover
crossover，即交叉操作，这⾥使⽤实数编码中常⽤的OX（Order Crossover）交叉算⼦。
OX 交叉算⼦的过程如图：
image
1. 随机选择两个点i,j，其中0<=i<=j<=N,N为染⾊体长度。
2. 将亲代P1从i到j的基因填⼊⼦代相同的位置。
3. 将亲代P2的基因不重复地依次填⼊⼦代中。
交换p1,p2，即可产⽣两个⼦代。
4
mutation
mutation，即突变操作，这⾥简单地随机交换染⾊体中的两个基因，过程如下图：
image
5
selection
选择的⽅法有很多，这⾥使⽤⼆进制锦标赛选择，每次从亲代中选择两个个体进⾏⽐较，将适应度⼤的个体保留到亲代中即可。
4.代码
代码由⼩编独⽴完成，有不周到之处还请多指教！
家用水处理器分为以下⼏个类：
image
Chromosome类为染⾊体类，提供了和Solution类的相互转换，即编码和解码过程，Customer类储存了具体的顾客，Conf类是参数的设
定，Solution类储存了解，GA_Stategy中实现了遗传算法⽤的函数。
运⾏结果如图：
image
参考⽂献：
[1]Anderson E, Phillips C, Sicker D, et al. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 2004, 31(12):1985-2002.**
[2]Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 1987, 35(2):254-265.**
有问题欢迎交流：邮箱
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议