多车场满载车辆路径问题遗传算法.pdfVIP

№．2 陕西科技大学学报 Apr．2011 V01．29 J()URNAL()FSHAANXlUNlVERSITY()FSCIENCE＆TECHN()LOGY·69· + 文章编号：1000一5811(2011)02一0069一06 多车场满载车辆路径问题遗传算法 范昌胜1，郭 强2，岳爱峰3 (1．陕西广播电视大学工程管理部．陕西西安710068；2．西北工业大学理学院，陕西西安710129；3．山 东师范大学图书馆，山东济南 250014) 摘 要：研究了多车场多配送中心车辆的路径问题，以提高物流配送效率．在分析了问题有效 解的基础上，制定了相应的染色体分段编码，给出了合适的适应值函数，使杂交变异得到的新 基因具有更好的健壮性．为了克服传统遗传算法早熟的缺点，作者结合模拟退火算法和小生境 遗传算法，以无序的方式进行杂交和随机点的基因变异，保证了进化后的种群多样性．并且杂 交选择方式使得算法收敛性较佳．通过实例检验，在可行解的集合内该方法收敛于近似最优解． 关键词：物流；遗传算法；满载运输；车辆路径问题；优化 中图法分类号：022 文献标识码：A O 引 言 VRP(Vehicle Routing 所示为有两个车场两个配送中心的车辆路径问题．研究求解约束条件下VRP问题的有效算法具有现实 意义． 一般地，很难找到VRP问题的最优解，或者花费很多的时间才可寻找到最优解[2：．即使在规模比较 小的情况下，求解也比较困难．研究车辆路径问题(VRP)的方法，有针对小规模问题的精确算法、启发式 算法和人工智能优化算法[3‘121．启发式算法在求解车辆路径问题中占有重要地位．近些年来，模拟退火[1引、 遗传算法邛d“、禁忌有哪些信誉好的足球投注网站算法[5]、蚁群算法一们以及它们之间结合形成的混合算法等仿生学智能优化算 法、13“5。的兴起，为解决VRP提供了新的工具．禁忌有哪些信誉好的足球投注网站被普遍认为是解决VRP问题的最快的算法，而遗 传算法则在快速有哪些信誉好的足球投注网站能力和全局最优性上有着明显的优势．本文将问题的数学模型做了更贴近实际的改 进，将模拟退火算法和小生境遗传算法结合求解，不仅克服了遗传算法容易早熟、不稳定等缺点，而且可以 很好地控制其早熟．在染色体编码上，与目前出现的编码方式不同[6]，充分利用车辆路径问题解的特点，采 用分段编码，使杂交变异方便有效，加快获得近似最优解． 1完整的问题描述与数学模型 多车场、多个配送中心、整车配送、多用户的VRP问题描述：(1)物流配送网络是由相互连通的多个 车场、多个配送中心和多用户组成，车场的车足够用，配送中心的货物足够多；(2)车辆从车场出发到配送 中心装货，完成整车配送任务后可返回任意车场；(3)要求完成任务前后每个车场车辆数目保持不变；(4) 优化目标为车辆完成所有配送任务的总运输成本(或路程)最低． 1．1数学描述 将车场、配送点、用户点都视为同一个网络上的节点，并视为连接相邻两个节点之间弧上的权值，一般 *收稿日期：2011一01一08 作者简介：范昌胜(1979一)，男，山东省汶上县人，讲师．硕士，研究方向：运筹与网络规划、最优化方法及其应用 万方数据 ·70· 陕西科技大学学报 第29卷 网络上的多车场多配送中心车辆路径问题的描述如下： 定义用户节点口，，耽’．．·，％，两相邻节点队与口j间的单位货物运费为Rd(元／单位)；节点G为车场， m 科p ‘=l 』一埘+l ，h+’-r+p+崎 m+户+口)，同时满足∑口』≥∑巩；其余节点为中间点，即，，l+p+口≤靠．在完成配送任务的前提下， 研究如何合理安排每辆车的行驶路径，使得总运费最少． 1．2 数学模型 根据问题的描述，建立的数学模型如下： mm芝 = SZ ，L 1、， ．∑H 。∑H ～V —V