基于遗传算法的物流最佳路径的设计与实现计算机专业.doc

题 目 基于遗传算法的物流最佳路径的设计与实现 摘要：在竞争日益激烈的现代社会．企业只有以市场为核心去适应不断变化的环境并及时对市场做出反应．才能在竞争中立于不败之地。物流管理正是以实现上述要求为目标。合理调度车辆等运输工具，优化运输路线，降低企业物流成本，是物流管理的重要功能。由于对物流管理中的车辆调度问题的研究对社会经济发展具有举足轻重的作用，因此，国内外学术界对物流运输系统的调度优化问题十分关注，研究的也比较早，但大部分都是理论上的跟踪型研究，真正为物流企业解决实际问题软件产品却非常少。因此，本设计了基于遗传算法的物流最佳路径。通过此系统，保证了调度的合理性．降低了运输成本．更能适应现代化的物流企业管理。 关键词：遗传算法，物流，最佳路径 The design of drug sales management system ABSTRACT：With the rapid development of science and technology, all kinds of management systems have been applied to each field of the society. Various size enterprises regardless of size, are fully aware of the traditional manual management mode has not adapted to the development of the times, in order to better development, in development for the management system。 Through the medicine Invoicing management system this platform, can realize the medicine Invoicing management informatization, network, systematic, standardized, so that the staff from the complex data query and statistics out, reduce the workload. The main functions of the system include: the categorized management of drugs, medicines management, warehousing management, warehousing management, inventory information browsing, customer management, supplier management。 The front of the system using JSP as a development language, the use of SqlServer as a database management system, the development environment is MyEclipse, server using tomcat, developed a Web technology based on B / S structure medicine Invoicing management system。 Keywords: Medicine Invoicing，JSP，C / S structure 目 录 第一章 绪论 1 第二章 设计需求整体描述 2 2.1设计问题描述 2 2.2 车辆路线问题研究现状 2 2.2.1车辆路线问题型态 2 第三章 整体设计方案 5 3.1遗传算法介绍 5 3.2遗传算法的设计思想 5 3.3遗传算法的设计 6 3.3.5 交叉操作 7 3.3.6变异操作 7 第四章 系统模拟测试 8 结 论 10 参考文献 11 致 谢 12 III 第一章 绪论 物流已被认为是继降低原材料消耗和提高劳动生产率之后的“第三利润源”。通过优化物流系统,可以降低物流成本,从而增强企业的市场竞争能力。因此,研究物流系统中的优化问题,具有十分重要的意义,是国内外研究的一个热点。 库存成本与配送成本是物流系统的核心成本,在物流总成本中占据了很大的比例。如果能降低库存成本与配送成本,就能有效地降低物流成本。 现在，物流配送多指配送中心按照多个客户的不同要求进行组织配送，并满足客户在产品质量、产品数量、到货时间等多方面的要求的同时使配送成本尽可能的低[1,2]，为了能够达到这一目标就要对配送路径进行优化。对配送路径进行优化就是对车辆路径进行优化，这是一个NP问题，以往的很多研究都证明了使用遗传算法求解这一类问题具有很大的优越性[3,4]。与与蚁群算法[5]相比，它能更大概率地搜索到最优解，因为蚁群算法在寻找最优解的过程中，当搜索的一定程度后，容易出现停滞现象，所有的个体发现的解都是同一个，不能再对解空间进行深入的搜索；与禁忌搜索算法[6]相比它的收敛性好一些，因为禁忌搜索算法对初始解得依赖性强，当初始解的质量较差时，收敛速度会大大降低。 遗传算法是一种应用很广泛的智能优化算法,本文对遗传算法进行了分析研究,针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上,本文基于遗传算法,研究了物流系统中的库存优化问题及车辆路径问题。本文将库存仿真优化问题与车辆路径问题都看作是组合优化问题,并应用遗传算法进行求解。 车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。由此定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery。已证明TSP问题是NP难题，因此，VRP也属于NP难题。 车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。 第二章 设计需求整体描述 2.1设计问题描述 车辆路径问题定义 车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。由此定义不难看出，旅行商问题是VRP的特例，已证明TSP问题是NP难题，因此，VRP也属于NP难题。 车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图1）： 图1 路径问题描述 设有一场站，共有M 辆货车，车辆容量为Q，有N位顾客，每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。 一般而言车辆路线问题大致可以分为以下三种类型： 1、相异的单一起点和单一终点。 2、相同的单一起点和终点。 3、多个起点和终点。 2.2 车辆路线问题研究现状 经过几十年的研究发展，车辆路线问题研究取得了大量成果。下面从车辆路线问题的现有研究型态和求解方法两个方面介绍车辆路线问题的研究现状。 2.2.1车辆路线问题型态 在基本车辆路线问题的基础上，车辆路线问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括时窗限制车辆路线问题、追求最佳服务时间的车辆路线问题、多车种车辆路线问题、车辆多次使用的车辆路线问题、考虑收集的车辆路线问题、随机需求车辆路线问题等。 3.3.2解决方法 1、求解方法演进 综合过去有关车辆路线问题的求解方法，可以分为精确算法与启发式解法，其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。1995年，Fisher曾将求解车辆路线问题的算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包括有各种局部改善启发式算法和贪婪法等；第二阶段是从1970年到1980年，属于一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合涵盖法；第三阶段是从1990开始至今，属于较新的方法，包括利用严谨启发式方法、人工智能方法等。 2、启发式算法 由于VRP是NP-hard问题，难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。 简单启发式方法包括节省法或插入法、路线内/间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法是在求解过程中使用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然后以迭代的方式利用交换改善法减少路线距离，直到不能改善为止。1960年，Clarke和Wrigh首先提出一种启发式节省法来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP问题。 两阶段方法包括先分组后定路线和先定路线后分组两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。 1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用来求解VRP ，随后亦有许多位学者也发表了求解VRP的TS 算法。西南交通大学的袁庆达等设计了考虑时间窗口和不同车辆类型的禁忌算法，这种算法主要采用GENIUS方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman对VRP的模拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法（GA）编码解决VRPTW 问题。现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuk提出了用遗传算法进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。Bent和Van Hentenryck则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法（largneighborhood search）将运输费用降到最低。 总结几种人工智能方法可以看出，TS算法所得到的解最接近最优解，但其运算时间也最长，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能较好的逼近最优解，同时使运算时间大大缩短，所以GA算法能兼顾运算时间和效率两方面，是具有较好的发展前途的方法；SA算法求解速度非常快，也能提供一定程度上的优化方案在求解较小规模问