遗传算法在物流配送优化中的应用研究(4).doc

word文档整理分享 PAGE 参考资料 遗传算法在物流配送优化中的应用研究 摘要：本文在对物流配送车辆优化问题进行简单描述的基础上，对有时间窗的车辆优化调度问题进行了分析。并对所采用的遗传算法的基本理论做了论述。对于有时间窗的非满载VRP问题，将货运量约束和软时间窗约束转化为目标约束，建立了非满载VRP模型，设计了基于自然数编码，使用最大保留交叉、改进的反转变异等技术的遗传算法。经实验分析，取得了较好的结果。 关键字：物流配送、车辆优化调度、 遗传算法 、时间窗 1 引言 随着生活水平的提高，消费者对货品送达时间的要求已越来越严格，企业如何安排车辆的配送路线，才能以最快且运输成本最小的配送路线来满足客户的需求，进而提升客户满意程度成为越来越重要的问题。因此，对于有时间窗限制的车辆选径问题(vehicle routing problem with time windows,VRPTW)逐渐受到研究人员的重视。其主要内容是：以成本最小的目标安排多辆车有序地前往需求量给定的各配送点而构成的配送路线，其中每辆车必须从同一车站出发并最后返回车，每个配送点只能安排一个车次在限定的时间窗内配送，且每一条配送路线不得超过车辆的装载容量和车辆的最后返回时间；如果车辆提前到达配送点，则需要等待，直到在时间窗内才能配送。在日常生活、企业管理、车辆运输中VRPTW问题有着广泛的应用，如邮政投递、产品配送以及生产计划等。本文详细论述如何采用遗传算法解决有时间窗的物流配送车辆优化调度问题并通过实验数据分析所采用改进的遗传算法的性能。 2 概述 2.1 研究背景 作为“第三利润源泉”的物流对经济活动的影响日益明显，越来越得到了人们的重视，成为当前“最重要的竞争领域”，而配送是物流中一个重要的直接与消费者相连的环节。《物流术语》GB/T18354-2006中对配送的定义为：在经济合理区域范围内，根据客户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。配送实际上一个局部物流，是大物流在小范围内的整合，配送是物流系统的终端，是直接面对服务对象的物流活动，配送功能完成的质量好坏极其达到的服务水平，会直接影响到客户对整个物流服务的满意程度。配送的核心部分是配送车辆的集货、货物分拣及送货过程，而车辆配送路径的合理优化，对于整个物流运输速度、成本、效益影响至关重要。根据中国仓储协会对146个企业的调查显示，用于运输的费用占整个物流费用的比例分别为：在生产企业原料物流中占58%，在生产企业成品物流中占73%，在商业物流中占52%[1]。配送的流程一般如下图所示。 用户 工厂 进货 送货 集货 存储 配货 车辆 配装 图1 配送流程图 在物流配送系统中，物流配送中心的成立可有效的简化配送程序与减少配送的频率，以i个供应商和j个零售商为例，传统的配送模式是假设j个零售商的需求都是由i个供应商自行配送，则一共有i×j次的运送，如图2所示。假设零售商与供应商之间通过一个物流配送中心来配送，则只需i+j次配送，如图3所示，如此一来即可减少(i×j-(i+j))的配送次数，当供应商与零售商数目越多，节省的配送次数也就会越多。 供应商（S） 零售商（R） 图2 传统的物流配送模式 物流中心配送作业的重点是如何将车辆有效的使用并决定其最经济的行驶路线图，使商品能在最短的时间内送到顾客的手中。国外将此类问题称之为Vehicle Routing Problem，简称为VRP问题。该问题一般定义为:对一系列装（卸）货点，组织适当的行车线路，使车辆有序的通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)［３］。 供应商（S） 供应商（S） 零售商（R） 物流 中心 图3 以物流中心为主的配送模式 2.2 研究的意义 目前有关VRP的研究，多致力于单一车种或多车种优化调度问题，很少涉及结合时间窗口的VRP问题。所谓时间窗口是指配送车辆或顾客希望服务或被服务的时间范围。由于消费者需求趋于多样化，对送货时间的要求日趋严格，尤其是运送有时效性的商品，例如海鲜、花卉、蔬菜、水果等讲究新鲜度的货物，除了因缺货造成的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。因此，在配送运输上，时间因素是十分重要的。 有时间窗的VRP问题也称为VRPTW(Vehicle Routing Problem wi