基于改进遗传算法的配送路径优化方案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“遗传算法路径优化”。
基于改进遗传算法的配送路径优化方案
摘要:为了很好地解决物流车辆的线路优化问题（简称VRP），借鉴DNA算法局部寻优能力强的优点，提出新编码方法，以及车辆的行使路线的新的测序方式，很好地解决遗传算法的早熟、局部寻优能力差的问题。通过测试，发现交替使用遗传算法和DNA算法进行全局寻优和局部寻优可以相对较准确、快速的实现车辆线路的寻优。
关键词:遗传算法；DNA算法；VRP
一、引言
物流被誉为经济活动中的“未开发的黑大陆”、企业的“第三利润源泉”。物流的目标在于以最小的费用满足消费者的最大需求，而运输的费用占整个企业物流的40％左右。在运输过程中，配送是其中一个重要的直接与消费者相连接的环节，物流配送车辆的线路优化问题，更是物流配送优化中的关键环节，正确合理的安排车辆的配送线路，可以有效的减少车辆的空驶率，实现合理线路运输，从而降低运输成本，节约运输时间，提高经济效益，达到物流科学化管理。
二、遗传算法与DNA算法
遗传算法是一种基于自然选择和自然遗传机制的自适应的随机搜索算法，它是一种有效的解决最优化问题的方法。
遗传算法求解工程实际最优化问题的基本步骤是：首先对可行域中的个体进行编码；然后在可行域中随机挑选指定群体大小的一些个体组成作为进化起点的第一代群体，并计算每个个体的目标函数值，即该个体的适应度。利用选择机制从群体中随机挑选个体作为繁殖过程前的个体样本。选择机制保证适应度较高的个体能够保留较多的样本；而适应度较低的个体则保留较少的样本，甚至被淘汰。在繁殖过程中，遗传算法提供了交叉和变异两种算法对挑选后的样本进行交换和基因突变。交叉算法交换随机挑选的两个个体的某些位，变异算子则直接对一个个体中的随机挑选的某一位进行突变。这样通过选择和繁殖就产生了下一代群体。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。
遗传算法是一种自适应随机搜索方法,具有极强的并行机制，在解决整体的搜索问题时，具有很强的鲁棒性和全局寻优能力。但遗传算法忽视了个体潜力的开发而只重视群体整体性能的提高。也就是说，遗传算法能够以较大的概率找到最优区域而不是最优点。因此遗传算法在应用中也有一些不尽人意的地方，主要表现在算法收敛慢、效率低、容易早熟、局部寻优能力差等。
三、基于DNA算法对VRP的局部寻优
为追求DNA计算局部寻优解的质量，我们在算法中加入基于启发式知识的方向搜索策略。在网络拓扑图中，求解某几个节点的最短回路，不需要对整个网络进行问题求解，可以只提取出与节点紧密相关的节点与弧段构成子网络，在子网络中进行问题求解，降低问题规模，提高算法效率。即基于方向策略的限制搜索区域方法[7]，比如搜索从北京到沈阳的最短路径，完全可以把南京、重庆等节点排除在搜索空间以外。该方法是一种有损局部寻优算法，即排除了概率极小的子网络外最优路径的可能。
在单条路径寻优中，以该点集作最小凸包，并以该凸包区域作适当扩充的缓冲区，落在缓冲区内的节点与弧段构成子网络进行搜索计算。DNA计算模型即构建在该子网络上进行，在保证有效搜索的基础上多余的边(辅助边)尽量少。
我们这里的VRP可描述为：已知n 个代售点之间的相互费用大小(在编码时用DNA片段的长度来表示)，现有一辆配送车必须访遍n个代售点 ,最后又必须返回起始送货点。如何安排车对这些代售点的有向行使路线，可使其行驶路线的总费用最少？以图论术语来说，假设有一个图G =(V,E,W)，其中，V是顶点集，E是边集，W是顶点和边的权值集，设D=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，VRP就是求出一条通过所有顶点完成配送任务并且总费用最少的有向路径。
（一）算法思想
依据上述思想，为了便于利用DNA计算，我们设计如下的求解该VRP的基本算法：
步骤1 ：搜索出所有闭合路径。
步骤2 ：找出那些开始于0、结束也是0的固定顶点的闭路经，也就是说，保留那些经过0的固定顶点的闭路经。
步骤3：找出那些经过所有节点至少一次的闭合路径，也就是说，保留0的所有广义Euler闭迹。
步骤4：找出最短的广义Euler闭迹，这就是我们所需的解。
步骤5：确定出配送车路线。
（二）VRP的DNA计算编码以及实施
1、构建VRP的DNA计算编码
先选取节点和弧段的基本寡聚核苷酸片断，通常是根据相应权值的大小先同等放大为正整数，再分别求出节点和弧段的最小公倍数作为基本寡聚核苷酸长度的制定标准。
由于DNA编码片断的数目随着路径条数的增加呈指数增长，如此复杂的编码也将成为DNA计算的技术瓶颈。本文采用基本寡聚核苷酸（K个）连接组合（单独长为4的一条就能形成K4/2种组合，因此所需的寡聚核苷酸的种类大大减少）从很大程度上简化这个过程，尽量减少DNA生物操作而更多地通过合理的编码进行处理，从而大大减少了误差的来源，这也是DNA计算研究的难以解决的问题之一。
2、VRP的DNA计算实施改进
步骤1：将以上各节点和弧段编码好的核苷酸放在不同的试管中加入底物（具有各自相同同位素标记的DNA分子）、适量的引物（固定点所对应的寡聚核苷酸片断的补链）、DNA聚合酶及缓冲液进行PCR扩增，这样在聚合酶的作用下可以使得DNA链成指数增加，各自产生大量的寡聚核苷酸。
步骤2：将第一步中合成的各节点所对应的寡聚核苷酸片断和边所对应的寡聚核苷酸片断混合在一起，加入缓冲液、DNA连接酶使之进行连接反应，这样可以生成所有闭路径，保留这些那些以0点开始和结束DNA链。
步骤３：将第2步的产物进行纯化，然后对于纯化后的产物进行分离。在分离过程中我们首先以表示边权的寡聚核苷酸片断的补链为模板构造探针，然后利用构造的探针对纯化后的产物进行分离。与该探针杂交的DNA链中一定含有该寡聚核苷酸片断，再将之加热变性后保留这些DNA链。这些被保留的DNA链一定包含所有边，也就是说我们找到了所有广义Euler闭迹。
步骤４：对第３步的产物进行琼脂糖浆凝胶电泳，跑在最前面的就是最优的DNA链。
步骤５：将上述步骤的标记产物直接由相关仪器进行读取，从而确定所求VRP的配送路线。
四、总结和展望
VRP是一种NP难题，本文结合遗传算法和DNA算法的各自优势，交替进行全局寻优和局部寻优，从而具有良好的全局性和局部性，在通过对算法本身经过创新改进后对解决VRP等NP难题将有不错的成效。
本文提出采用以基本单位的寡聚核苷酸相连接从而形成不同长度的片断对节点和弧段进行编码，从而避免在融合的过程当中形成发夹结构从而产伪解，而且也减少了生物操作（变性、退火等），使得到所需的DNA寡聚核苷酸源片断变得更加容易。其次，本文提出新的测序方式，即事先就各自进行带标记的核苷酸基片进行PCR复制，从而在检测目标时只需通过强度检验就可以知道寡聚核苷酸片断的连接顺序，映射得到车辆的行使路线，减少了测序操作。
参考文献：
[1] 丁立言,张铎.物流管理[M].北京:清华大学出版社,1999:15-16
[2] 周康,同小军,许进.路径排序问题基于表面的DNA算法[J]华中科技大学学报:自然科学版,2005,33(8),100-103
