遗传算法(GA )车辆路径问题) VRP ) —— matlab实现1、车辆路径问题综述2、遗传算法2.1、编码操作2.2、解码操作2.3、目标值计算2.4、交叉操作2.5、变异操作2.6、选择操作2.7、 同步文章导语:车辆路径问题(vehicle routing problem，VRP )是一个比较经典的运筹学优化问题，在离散组合优化中进行了大量的研究，在物流行业具有很强的应用价值车辆路线问题由Dantzig和Ramser于1959年首次提出，配送路径优化问题是NP-hard问题，因此用启发式算法求解该问题成为人们研究的重要方向。 经过全球专家学者的不断研究，车辆路线问题的研究取得了丰硕的成果，在问题模型方面扩展了约束条件、优化目标等，更加符合现实生产生活的场景，在求解方法方面主要通过启发式方法、精确方法、智能算法等，提高求解质量本文基于学习交流的态度，从最基本的车辆路径问题入手，学习如何利用遗传算法求解车辆路径问题。
1、车辆路径问题简介车辆路径问题(vehicle routing problem， VRP )给予有容量限制的车辆集合、物流中心(或收货方)、若干有交货需求的顾客，组织适当的行驶路线，使所有顾客有秩序地通过车辆，满足一定的限制条件，如需求量、服务时间限制、车辆容量限制、车辆容量限制等(1)每条配送路径各客户需求量之和不超过配送车辆载重量； )各配送路径的长度不超过配送车辆一次配送的最大行驶距离； )3)满足每位客户的需求，且只能用一辆配送车辆配送。 (车辆路径优化问题的数学模型不在此讨论) 2、遗传算法遗传算法(Genetic Algorithm，GA )是一种比较经典的智能优化算法，大量研究表明，在求解离散组合优化问题方面表现较好遗传算法思想优胜劣汰，通过交叉操作、变异操作获得多种解，给下一代留下目标函数的最优解，用轮盘赌方式选取下一代个体，反复迭代，优化问题的解。 本文采用Matlab R2010b编程实现，遗传算法求解车辆路径问题的具体内容和步骤如下。 2.1 .码操作车辆路径问题是一个离散优化问题，结合约束条件3，必须满足各客户的需求，且只能由一辆配送车辆配送。 可以按客户整数号码的顺序编码，保证各客户号码可能且只能出现一次。 例如，如果客户数为8，则编码的染色体可以是1-2-3-4-5-6-7-8。 %population_num种群规模； Customer_num客户数population=zeros (population _ num，Customer_num )； fori=1: population _ num population (I， )=randperm(customer_num )； end 2.2 .解码操作的解码操作，在满足限制条件1、2的前提下，需要为将染色体解码为车辆配送路径、计算目标值做准备。 根据排列顺序进行解码，主要判断该顾客加入车辆配送路径后是否满足该车的最大行驶距离，以及是否满足该车的最大载重量。 例如，假设染色体1-2-3-4-5-6-7-8，则第一辆车路径：如果将顾客1加到该车的路径上，则第一辆车的行驶路径为0-1-0，该车从物流中心0出发，将货物运送到顾客1，物流中心表示在计算行驶距离是否满足第一辆车最大行驶距离的同时计算货物运输距离，此外，确认顾客2加入第一辆车的路径是否满足上述两个条件，如果满足，则第一辆车的行驶路径为0-1-2-0，且2.3 )计算目标值基于解密后的车辆行驶路径，计算目标值为总配送距离。 但是，需要判断解码后的行驶路径的数量是否超过了总车辆数，如果没有超过，则在所有车辆路径上合计得到总配送距离，如果超过了总车辆数，则该配送路径是不可能的，其解是不可能的解，该问题是最小化优化问题2.4 .交叉操作交叉操作基于双亲染色体信息，基于交叉概率Pc交换某片段，使母体信息能够遗传给子代。 本质是根据父母的染色体信息生成子(新解)。 交叉操作的实现方式有多种，本文交换染色体片段的交叉操作如下图所示。
2.5 .变异操作变异操作是根据母体的染色体信息，根据变异概率Pm改变某基因的位置，从而改变染色体整体的操作。 该操作引起的染色体变化程度小于交叉操作。 变异操作的实现方式有多种，本文给出了点位基因的变异操作，如下图所示。
2.6 .选择操作选择操作由目标值较好的染色体和随机产生的新染色体组成，在确保优良基因传到下一代的基础上，通过随机产生的新解扩大染色体多样性。 2.7 .算法流遗传算法求解车辆路径问题的算法步骤如下：
3、算法验证实例1 :某物流中心有两台配送车辆，其载重量均为8t，车辆单次配送最大行驶距离为50Km，配送中心(编号0 )与8位客户和8位客户之间的距离dij，8位客户的货物需求量QJ(I
，……，8）见下表1。要求合理安排车辆配送路线，使配送总里程最短。根据以上问题的数据信息，设置好遗传算法的参数，通过遗传算法求解该车辆路径问题得到最有解为【1-3-5-6-4-7-2-8】，最短距离为【69.5】，解码操作得到的车辆路径为【0-1-3-5-6-0】、【0-4-7-2-8-0】。本文通过遗传算法求解实例1，得到与参考文献一致的最短距离，验证了算法的正确性。 4、MATLAB程序 【求解车辆路径问题的遗传算法】的Matlab程序已经发到【智能优化算法】公众号，二维码见文末，也是希望能有一个平台分享优化算法，希望能得到大家的关注。有问题可以随时私信我，我尽可能及时回复，谢谢大家。
5、同步知乎文章
遗传算法求解车辆路径问题 - 南柯一梦的文章 - 知乎
https://zhuanlan.zhihu.com/p/125779424