车辆路径问题中的遗传算法设计.pdfVIP

第 28 卷第 l 期 东华大学学j~[ 自然科学版) \0 1. 28. 目。 1 2002 if 2 月 JOURNAL OF DONG HUA UNIVEHSITY leb. 20ω 阜辆踏位J问题中的过于专署在培议计 唐坤 (东华大学旭日工商管理学院，上海，2刷51) 恼要 丰辆路挂问题在物?血管理的研究中是到大量是在。但由于丰辆路径问题走一个 NP-)wn!问题，优间传统优化方法很 难得到最忧解或满意解。这里使用改造的主又算于和遗传算于，设计了革于自然在生编码的遗传算法，*解丰柄略任问题，获 得了良好的效果。 关键词:物流管现犀统，遗传鼻墙，丰辆~1是问题 中图法分类号: F 253.9 飞 在竞争日益激烈的今天，企业只有以市场为核心 问题，在问题规模较大时，问题的求解将耗费系统 去适应不断变化的环境并及时对市场做出反应，以低 巨大的空间与时间资源。文献[Ull 州，对运用整 的成本、快的i息度，在iE确的时间和地点为消费者或 数规划求解一个包含 50 个客户、 10 个仓库、 15 辆 用户提供满意的产品和服务，才能在宽争中占有 汽车的实际问!!!î时，规划的分校将有 54 510 个，约 优势。 束将有上千亿个。显然用传统的优化方法求解这 物流管理正是以实现上述要求为目标的。合理 样的问题是不绞济的。而遗传算法的求解，它的运 使用与调度运输工具，优化运输路线，降低企业物流 算规模用群体规模的大小来确定f~算时间也可用 成本，是物流管理的重要功能。在现有的物流管理系 i1t化代数来控制，求解大规模的 VRP 问题显得卡分 级济。 (2) 使用线性规划求解问版时，往往需要预 统研究中， 1959 年由 Dantzig 和Ramser 首先提出的东 辆路径问题(Vehicle Routing Problem) 回到1]是较受灾 先输出一个可行解，逐步迭ft 优化，但是 V即问题 洼的一个方面。它是指在客户需求位置已知的情况 的初始可行解往往难以获得。但法f专 P草挝; )点 m 自 下，确延年俐在各个客户间的行程路线，使得运输路 然!Jf.优月生劣汰的规律，可以从非TiJ l于解开始计算， 线敛:\;li或运输成本最低。在 VRP 问题被诋明为是… 在计算过程中逐渐解出可行解及最fit 解 ， j中淘汰不 个 NP-hard 问题，在问题规模较大时，很难得到全局最 可行解。 优解或满意解后，研究的意点巳转移到各种启发式算 由此可见，遗传算法在求解 VRP 问题时，具有 巨大的优蓝蓝性。但长久以来学者们在使用遗传算 议上丽。 法求解 VRP 问题时，使用γ 一套独特的事车子与第 遗传算法(Genetic Algori阳.GA)是由炎国Michi胆 大学 Holland 教授发展起来的[2] 。遗传算法作为一种 法，这些算子与算法li 是1在于遗传算法，何与遗传 数值求解的方法，}t思想源于生物遗传学适者生存的 算法的差异很大。由于这些差异的存在，使他们的