求 遗传算法 求解物流中心车辆配送路径优化问题的 vc源代码
[问题点数：100分，结帖人liyelun]
求 遗传算法 求解物流中心车辆配送路径优化问题的 vc源代码
[问题点数：100分，结帖人liyelun]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2012年4月 VC/MFC大版内专家分月排行榜第一
2012年5月 VC/MFC大版内专家分月排行榜第二2012年3月 VC/MFC大版内专家分月排行榜第二2011年7月 VC/MFC大版内专家分月排行榜第二2011年1月 VC/MFC大版内专家分月排行榜第二2010年12月 VC/MFC大版内专家分月排行榜第二2010年9月 VC/MFC大版内专家分月排行榜第二2010年6月 VC/MFC大版内专家分月排行榜第二2010年5月 VC/MFC大版内专家分月排行榜第二2010年4月 VC/MFC大版内专家分月排行榜第二
匿名用户不能发表回复！|求关于matlab的基于遗传算法的路径优化问题的代码！！！_百度知道
求关于matlab的基于遗传算法的路径优化问题的代码！！！
好是VRP问题的，例如知道几辆车、顾客点、需求数等。。，求最短路径本人最近才学不久，包括距离矩阵等，希望是完整的一套代码，最好是个实际例子
我有更好的答案
算法编写和你的约束条件有关系的
为您推荐：
其他类似问题
遗传算法的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。您现在的位置是： &
基于Matlab物流配送路径优化问题遗传算法的实现
□ 弓晋丽 程志敏
摘　要:在物流管理学中。研究物流配送路径优化问题并选取恰当的配送路径。可以加快对客户需求的响应速度．提高服务质量，增强客户对物流环节的满意度。降低服务商运作成本。但由于物流配送路径优化问题是一个NP—hard问题，使用传统优化方法很难得到最优解或满意解。本文基于Matlab进行了物流配送路径优化问题遗传算法的编码．利用Matlab强大的数值计算能力较好地解决了这个难题并进行了实例验证．对物流企业实现科学快捷的配送调度和路径的优化有实际意义。
特别说明：本文献摘要信息，由维普资讯网提供，本站只提供索引，不对该文献的全文内容负责，不提供免费的全文下载服务。
金月芽期刊网 2018赞助商链接
当前位置： >>
北大仓物流配送路径优化的研究
哈尔滨工业大学工学硕士学位论文（工程硕士）北大仓物流配送路径优化的研究THE RESEARCH OF BEI DA CANG LOGISTICS DISTRIBUTION ROUTES OPTIMIZATION200８年３月国内图书分类号：-I-哈尔滨工业大学工学硕士学位论文国际图书分类号：工程硕士学位论文北大仓物流配送路径优化的研究Classified Index: U.D.C.:Dissertation for the Master Degree in EngineeringTHE RESEARCH OF BEI DA CANG LOGISTICS- II -哈尔滨工业大学工学硕士学位论文DISTRIBUTION ROUTES OPTIMIZATION- III -哈尔滨工业大学工学硕士学位论文摘要物流配送路径优化问题一直是国内外学者普遍探索的重要课题。 传统的 物流配送难以满足实效性要求，本文主要解决物流配送路径优化问题。 本文的研究就是围绕物流配送路径优化问题展开的， 指出了路径优化方 面存在的问题，提出本文所要解决问题方案。酒类产品配送呈现小批量、多 频次、及时性等特点，配送路径更加复杂。本文立足于对物流配送路径优化 问题的研究，指出该问题属于典型的 VRPTW 问题，结合时间窗约束和配送 车辆容量限制约束构造了时间惩罚函数和容量限制惩罚函数， 建立了该问题 的数学模型。分析了遗传算法的重要控制参数，描述遗传算法的基本步骤和 基本操作流程，通过引入刘海交叉法，构造了一种具有较强全局搜索能力的 引申刘海交叉法，改进了原有的标准遗传算法，利用 MATLAB 编制了相应 的计算程序，实现问题的迅速求解。结合北大仓啤酒有限公司的物流配送业 务，用实例验证了改进遗传算法在求解此类问题时的可行性及优越性，验证 了该计算程序的准确性及通用性。 本文的创新点之一就是将顾客满意度函数和惩罚函数作为首要的约束 条件体现在模型当中，在模型选优的过程中直接作用，从而将配送中心以往 不能量化的信誉损失间接的予以量化， 这在很大程度上强化了配送中心的长 远利益，也提高了顾客服务水平，即准时化、高效率化等；创新点之二就是 在模型的求解过程中对遗传算法的应用，为了便于求解模型，将遗传算法做 了改进，应用 MATLAB,使之更适应于本文的研究。关键词物流配送；路径优化；遗传算法；车辆调度- IV -哈尔滨工业大学工学硕士学位论文AbstractThe optimization of distribution routes has been an important research project at home and abroad. The traditional logistic distribution can’t solve the problem of strict timeliness, the thesis mainly focused on the optimization of e distribution routines. This thesis research is centers on the logistic distribution routes optimization question to launch, had pointed out the way optimization aspect exists the question, proposed this article needs to solve the question plan. The wines product allocation presents characteristics and so on small batch, multi-frequencies, timeliness, the routes is more complex. This article bases on to the logistic distribution routes optimization question research. it is pointed out that the problem is attributable to typical VRPTW.Combining with the restrictions of time windows and distribution vehicle capability limit, the time penalty function and capability limit penalty function were constructed and the corresponding mathematical model was established.The important control parameters of genetic algorithln were analyzed and the basic steps and operation process were described in the thesis. An extending Liuhai crossover method with strong global searehing ability was constructed by introducing Liuhai crossover method, which ameliorates the original standard genetic algorithm. And the solving strategy for the optimization of distribution routes of goods was brought forward. The calculation process can be realized quickly by the calculation procedure by MATLAB.The feasibility and superiority of ameliorate d genetic algorithm applied in such problems were collated by bei da cang beer limited company's logistic distribution service, and the accuracy and currency of the calculation program were proved. One of this article innovation is takes the customer degree of satisfaction function the most important constraints to manifest in the middle of the model, in the model chooses in the superior process the direct action, will thus allocate and dispatch the center formerly not to be able the quantification prestige to lose indirectly gives the quantification, this strengthened the allocation center long-term benefits to a great extent, also raised the customer service level,-V-哈尔滨工业大学工学硕士学位论文namely accurate current events, high
Second innovation are in the model solution process to the genetic algorithm application, for ease of the solution model, the genetic algorithm will have made the improvement, applies MATLAB, causes it to adapt in this article research. This article research is according to the actual need construction model, not only considered from enterprise own economic agent, moreover also from the customer to the service request's angle embarking consideration question, determines the best routes. Keyword: Logistics Distribution, Optimization of routing, Genetic Algorithm s, Vehicles dispatch- VI -哈尔滨工业大学工学硕士学位论文目录摘 要 .................................................................................................................... IV Abstract ....................................................................................................................... V 第 1 章 绪论 .............................................................................................................. 10 1.1 课题背景 .................................................. 10 1.2 研究意义 .................................................. 11 1.3 研究现状 .................................................. 12 1.3.1 国内、外物流发展状况 .................................. 12 1.3.2 国内、外物流配送路径优化研究现状 ...................... 14 1.4 本论文的研究目的 .......................................... 16 1.5 本论文的主要工作和框架结构 ................................ 16 1.6 本章小结 .................................................. 17 第 2 章 物流配送路径优化研究的相关理论 .......................................................... 18 2.1 物流配送路径优化概述 ...................................... 18 2.2 物流配送路径优化目标 ...................................... 18 2.3 物流配送的路径优化方法的选择 .............................. 19 2.3.1 物流配送路径优化的方法 .............................. 2.3.2 各种优化方法比较分析 ................................ 2.3.3 优化方法的选择 ...................................... 2.4 遗传算法的概述 ............................................. 2.4.1 遗传算法的发展历程 .................................... 2.4.2 遗传算法的特点与应用 .................................. 2.4.3 遗传算法求解一般步骤 .................................. 2.4.4 遗传算法求解一般流程 .................................. 2.5 遗传算法的重要参数 ......................................... 2.5.1 遗传空间 .............................................. 2.5.2 编码 .................................................. 2.5.3 染色体 ................................................ 2.5.4 种群和种群规模 ........................................ 2.5.5 遗传算子 .............................................. 2.5.6 适应度和适应度函数 ....................................- VII -20 24 25 25 26 27 27 28 29 29 29 29 29 30 31哈尔滨工业大学工学硕士学位论文2.5.7 进化代数 .............................................. 31 2.6 本章小结 .................................................. 31 第 3 章 北大仓啤酒有限公司的物流业务描述 ...................................................... 32 3.1 北大仓啤酒有限公司物流的构成 .............................. 32 3.1.1 物流的三个主要环节 .................................. 32 3.1.2 物流的成本构成 ...................................... 32 3.2 北大仓啤酒有限公司物流的流程 .............................. 33 3.2.1 物流采购 .............................................. 33 3.2.2 物流加工 .............................................. 34 3.2.3 物流配送 .............................................. 34 3.3 北大仓物流配送存在的问题 .................................. 35 3.4 北大仓物流配送流程的优化 .................................. 35 3.5 本章小结 .................................................. 36 第 4 章 北大仓啤酒有限公司物流配送优化原型设计 .......................................... 37 4.1 北大仓啤酒有限公司需求分析 ................................ 37 4.1.1 北大仓物流配送的拓扑结构 ............................ 37 4.1.2 北大仓物流配送优化的设计思路 ........................ 37 4.2 数学描述 .................................................... 38 4.2.1 北大仓物流配送路径优化问题的数学描述 .................. 4.2.2 时间窗约束的数学描述 .................................. 4.3 数学建模 .................................................. 4.3.1 构造惩罚函数 ........................................ 4.3.2 建立数学模型 ........................................ 4.4 算法设计 .................................................. 4.4.1 构造染色体 .......................................... 4.4.2 种群初始化 .......................................... 4.4.3 性能评价 ............................................ 4.4.4 自然选择 ............................................ 4.4.5 染色体交叉 .......................................... 4.4.6 染色体变异 .......................................... 4.4.7 结果输出 ............................................ 4.5 程序实现 .................................................. 4.5.1 主要代码 .............................................- VIII -38 39 40 40 41 43 43 43 43 44 45 47 48 48 48哈尔滨工业大学工学硕士学位论文4.5.2 运行步骤 ............................................. 50 4.6 本章小结 .................................................. 51 第 5 章 遗传算法在北大仓物流配送路径优化的验证 .......................................... 52 5.1 北大仓物流配送路径优化问题的提出 ............................ 52 5.2 北大仓物流配送路径优化问题的求解过程 ........................ 53 5.2.1 设定参数 ............................................. 53 5.2.2 搜索最优解 ........................................... 54 5.2.3 输出结果 ............................................. 54 5.3 北大仓物流配送路径优化问题的结果分析 ........................ 55 5.3.1 核对配送过程 ......................................... 57 5.3.2 验证求解结果 ......................................... 58 5.4 本章小结 .................................................. 60 结论 ............................................................................................................................ 61 参考文献 .................................................................................................................... 63 附录：改进遗传算法的程序清单 ............................................................................ 66 哈尔滨工业大学硕士学位论文原创性声明 ............................................................ 73 哈尔滨工业大学硕士学位论文使用授权书 ............................................................ 73 哈尔滨工业大学硕士学位涉密论文管理 ................................................................ 73 致 谢 ........................................................................................................................ 74- IX -哈尔滨工业大学工学硕士学位论文第 1 章 绪论近年来，物流业在我国得到了快速的发展，成为经济发展的重要动力，综观 国内外的发展状况，物流的价值将会在各个领域得到进一步体现。 最初的物流配送(Physical Distribution)的概念[1，2]，是美国学者克拉克在二十世纪初提出的。 传统意义的物流，是指发生在商品流通领域中的在一定劳 动组织条件下凭借载体从供应方到需求方的商品实体定向移动。之后在二站期 间，围绕战争供应问题，形成了“后勤”(Logistics)理论，将战时物资生产、 采购、运输、补给等活动作为一个整体进行统一部署，以求战略物资补给的费用 更低，速度更快，服务更好。后来， “Logistics”一词在企业中被广泛应用。随 着经济社会的不断发展， 现代物流已逐渐从传统的单一销售服务，发展成为以现 代科技、管理和信息技术为支柱的综合物流系统。1984 年，美国物流管理协会 正式将物流概念改为 Logistics,并将物流定义为“为了符合顾客的需求，将原 材料、半成品、完成品以及相关的信息从发生地向消费地流动的过程，以及为使 保管能有效、低成本的进行而从事的计划、实施和控制行为” 。 相对于传统物流而言， 现代物流的特征是在传统物流的基础上，运用先进的 计算机电子技术和先进的网络信息技术，以及诸如供应链管理等先进的管理方 法，综合组织物流中的各环节，把制造、运输、销售等环节统一起来管理，使物 流资源得到最有效的利用， 以平衡物流的服务优势和服务成本，以期使用户得到 最大的满足，实现服务增值。[3]1.1 课题背景本文的研究主要以齐齐哈尔北大仓集团有限公司的物流配送业务为背景。 北大仓集团有限公司是黑龙江省大中型骨干企业之一， 是齐齐哈尔市十大重 点企业集团之一和地方财政主要支柱之一，是以生产 A 级绿色食品“北大仓”牌 白酒和“明月岛”牌啤酒为主导产品的跨行业、跨地区、融工业、商业、房地产 开发业务等多种行业为一体的综合性发展的企业集团。 北大仓集团啤酒有限公司 是集研发、 生产、 销售为一体的中型专业生产啤酒公司。 公司目前下辖甘南分厂、 富裕分厂两大生产基地及齐齐哈尔七区九县十六个销售营业部， 各销售部负责辖 区销售点的产品配送， 已经形成一个生产基地――销售营业部――客户点的三级 配送网络。 为了能够实现快速配送，北大仓集团啤酒有限公司拥有几十辆载重不 同的车辆，负责基地到销售部的销售、调拨、运输任务。销售部也管辖一定数量 的车辆，负责完成客户网点的配送任务。公司下设物流部门，管理物流配送中的 各个环节。 物流部门设置了专职的调拨中心，负责每天基地→基地和基地→销售 部之间的货物调拨。 那么如何将车辆有效的使用并决定其最经济的行驶路线图， 在最短的时间内 把产品送到顾客的手中，提高顾客的满意度，将是物流部门的工作重点。显然配 送服务的要求将越来越高， 为了实现配送成本的降低，必须对配送过程进行合理 规划。这就涉及到时间、财务、环境及服务质量四方面的因素，首先从时间上要 考虑准时性、 快速响应； 财务上要考虑运输涉及的各种开支 （员工薪酬、 消耗等） ；- 10 -哈尔滨工业大学工学硕士学位论文环境上要尽可能减少不必要的行驶，避免交通拥挤、空气以及噪音污染；最后从 服务质量上，要求满足顾客要求，达到顾客满意度最大化。这些都可以通过改进 运输方式、线路规划等来改善。 目前， 物流配送活动中的配送运输路径确定问题，成为近二十多年来车辆路 径问题的重点研究对象和应用领域。在配送运输中，由于配送用户多，城市交通 路线又复杂，如何组成最佳路线，如何使配装和配送路线有效搭配等，是配送运 输的特点， 也是难度较大的工作。 于是采用科学的、 合理的方法来确定配送线路， 成为提高物流配送车辆效益、 实现物流配送科学化的重要途径，也是配送活动中 非常重要的一项工作。 可见， 物流配送业务的重点是如何将车辆有效的使用并决定其最经济的行车 路线， 使得货物能以最少的成本在最短时间内送到顾客的手中，国外将此类问题 称为车辆优化调度问题(Vehicle Routing Problem)，简称 VRP 问题。随着消费 者需求的多样化发展， 对于该问题的分类向多元化，如送货时间要求的日趋严格 引出了有时间窗的车辆优化问题(Vehicle Routing Problem with Time Windows), 简称 VRPTW 等。 本课题针对北大仓啤酒有限公司产品配送过程中现实存在的到货期限过长、 影响集团信誉等问题， 提出采用即时配送方式；在标准遗传算法的基础上引入刘 海交叉法， 构造出一种改进遗传算法，用于求解北大仓啤酒有限公司产品配送的 路线优化问题；编制相应的 MATLAB 计算程序，实现该问题的迅速求解；通过具 体北大仓啤酒有限公司配送数据， 验证利用这种改进遗传算法在求解该问题时的 可行性及优越性。 以此拓宽遗传算法的应用范围，便于在更多领域内发挥其优越 性；将严格要求配送时效性的北大仓啤酒有限公司产品从普通货物中分离出来， 单独考虑其配送的最佳方式， 从行业的角度更新物流配送的划分方式，使物流配 送理念植根于具体的货物品类中，为其它品类货物的配送起到抛砖引玉作用。1.2 研究意义本论文以北大仓啤酒有限公司提供的啤酒配送数据为依据，对配送路径问 题进行数学分析，通过适用性较强的遗传算法解决车辆的配送线路的生成问题。 主要解决配送优化中可能存在的以下问题： 1、解决时间限制问题。通常情况下，客户对车辆到达时间有限制的，主要 有硬时间窗、软时间窗和软硬相结合的混合时间窗，而在实际的物流配送中，混 合时间窗的相对多一些， 配送车辆如果能在最佳时段内将货物送到客户，则客户 满意度最大，否则客户的满意度降低。随着服务质量要求的提高，客户对其要求 也越来越严格，时间限制成为首要的约束条件。 2、目标性。对配送中心而言，以往只是一味的按照某一目标，在主要以时 间为约束的条件下确定方案，产生很多不良效果，如不满足准时送货的目标、会 令顾客不满意等， 因此有人通过建立多目标函数来优化方案，通过综合各个约束 条件，尤其是多目标之间的协调性，从中选出相对较优的方案，相应的在计算方 面较单一目标计算的复杂度难些。但是本文通过引入顾客满意度这一约束变量， 使配送中心可以在单一目标下， 满足准时送货的要求来进行决策，将多个目标综 合到总配送费用最小的目标中， 从而避免了多个冲突目标之间协调性把握不准确 的问题，降低了计算的难易程度，这将是本论文的一个突出的创新点。 3、实效性。在实际选优过程中，顾客对服务的满意程度往往是各不相同，- 11 -哈尔滨工业大学工学硕士学位论文如对服务时间要求不同， 相应的满意程度也不同。因此就要求我们在满足配送费 用最小化的同时，还要充分考虑顾客的最大满意程度。 本论文对物流配送企业实现计算机配送路径优化、 降低成本和提高物流经营 管理水平、更快的响应、最终能显著的增加企业的竞争力具有重要的参考价值。 应该说，在实践当中具有较强的理论意义和实践价值。1.3 研究现状物流业在国民经济和地区经济中发挥着带动和支持整个国民经济的作用。 当 前， 在信息技术的支持下， 发达国家的现代物流已经成为国民经济发展的重要支 柱产业、提高经济效益的重要源泉、产业升级和企业重组的关键推动力、以及区 域创新和经济发展支撑环境的关键因素之一。 物流业在国民经济和地区经济中发 挥着带动和支持整个国民经济的作用。 物流业实际的发展情况也证明了其在一国 国民经济中的重要地位。根据《国际统计年鉴 2005》 提供的资料测算，2005 年各国物流业增加值占 GDP 的比重，美国为 22.72%，日本为 21.15%, 法国和意 大利分别为 20.33%和 24.87%。 物流业也是国家和地区财政收入的主要来源。2005 年 1 月至 9 月，我国社 会物流总值为 35.6 万亿元，同比增长 25.1%；物流业增加值为 6878 亿元，同比 增长 14.7%，占服务业全部增加值的比例从上年的 19.5%提高到 21.3% ；物流相 关行业固定资产投资 6334 亿元，同比增长 28.2%，略高于全国平均投资增长水 平，成为财政收入的重要来源。 物流业的发展能创造众多的就业岗位，对社会的发展和稳定具有重要作用。 2000 年各国批发零售业与货运业从业人员占第三产业就业人口的比重，美国为 35.29%，日本为 45.54%，加拿大为 41.35%，德国为 35.14%，意大利为 39.66%。 西方发达国家，流通产业就业人数己经超过一、二产业，成为吸纳劳动力最多的 部门。 我国关于批发零售业与货运业从业人员占第三产业就业人口的比重虽然没 有准确的统计， 但物流产业的快速发展，带动经济发展与就业需求已经成为实现 和谐社会的重要途径。[4]1.3.1 国内、外物流发展状况从总体上看，我国的现代物流还处于发展的初期阶段 ，从物流企业的性质 上来看，现有的物流企业大致可分为以下几类： 1 、 中央直属的专业性物流企业，即专营生产资料的物资储运总公司和外运 公司。像中石化、中铁运输、烟草行业等，物流主要针对系统内部，商流与物流 从形式上是分离的，受行业行政控制。这些专业物流企业一般有资金优势，但是 由于缺乏市场竞争压力， 无论是现在物流的意识和现代技术的应用都存在较大差 距，效率和成本问题比较突出。 2、地方专业性物流企业，即地方商业系统的储运公司及粮食仓储系统，完 全受当地行政领导。 这些物流企业的发展现状与当地政府有密切关系，一些沿海 发达城市， 在一些外资企业带来的先进管理思想和技术的影响下，物流的现代化 程度相对较高。一些地区建立了“物流园区” ，吸引物流人才和技术，第三方物 流得到蓬勃发展。- 12 [5]哈尔滨工业大学工学硕士学位论文3、兼营性物流企业，即集物流与商流为一体的物流企业，比重大，且数量 正在不断增多。由于规模和资金方面的差异，造成良莠不齐的局面，大部分顶多 只能说是运输公司，普遍处于传统物流的阶段。 从物流业总体水平来看，与国外发达国家相比差距还很大［6］。以物流成本为例， 西方发达国家由于经济运行的节奏加快，量流动资本处于沉淀状态的份额 极小，周转速度普遍较快，从而可以为企业带来巨大的增值空间，物流总成本占 GDP 的比重，美日等国家物流成本占 GDP 的比重不断在降低。据统计，美国的 这一比重 2000 年为 10.2% , 2001 年为 9.5% , 2002 年为 8.7% ；日本的比重 也基本维持在 9%左右。 2004 年我国物流总费用相当于 GDP（现价）的 21.3%。2005 年 1 月至 9 月， 同比增长 13.6% ；社会物流总费用占 GDP 的比例 20.9%。造成成本巨大差异的 背后， 是我们人才的制约、 管理的粗放等差距， 先进的管理思想和技术没有普及， 说明我国的物流业尚处于传统物流阶段。 对于国内物流企业来说，基础信息化仍然是当前需求的主要内容，据 2006 年有关调查， 72%的企业仍把办公自动化建设列为未下一年的重点，86.1%的企业 有将上 MRP2 的意愿，60%的企业把 ERP 列为下一阶段建设的重点。这表明在相 当长的时期内，需求的特点仍是在规范流程中实现信息的采集、传输、存储、共 享，建立决策、控制依赖于信息、数据的机制，与真正的应用还有距离。 其在近几年“物流热”的影响下，在国内关于物流的研究还是有一些。如关 于库存与运输问题，有随机库存-运输联合优化问题研究[50]，从宏观上给出了库存-运输联合优化问题的定义、特点和分类，同时指出了己有研究中存在的不足 和一些潜在的研究领域，这些都有利于对此类问题的研究的进一步深入和扩展。 还有，关于算法问题，有基于遗传算法的物流配送网络优化[51][52][53]，分析了物流配送网络优化模型的各个关键组成部分， 包括优化目标， 决策变量和约束条件， 分析了如何利用和设计合适的遗传算法来解决物流配送网络的优化问题等。 国外的物流发展起步早，经验成熟，尤其是信息化管理程度高，对我国物流 发展有很大的借鉴意义。 1、物流电子商务蓬勃发展。2004 年电子商务市场规模超过 10000 亿美元， 电子物流将是 21 世纪物流发展的大趋势。 2、规模效应显著体现。规模的扩大通过企业合并，企业间的合作与联盟， 大型的物流企业和物流经济区不断增加。美国的物流模式为物流中央化，该模式 强调“整体化的物流管理系统” ，物流管理包括分配计划、运输、仓储、市场研 究、为用户服务五个过程。 3、物流服务的增值效果明显。建立 QR、ECR 和 JIT 系统[54]。QR (QuickResponse)，即快速反应。80 年代，在美国以低价销售为特征的沃尔玛，K-MARK 等平价商场大行其道，主要原因是物流信息及渠道的畅通。专业服务的介入，使 在生产商看来非常繁琐耗时的信息处理工作变得十分简单。ECR(Efficient Customer Response)，即高效客户信息反应系统，源于 1992 年 FMI（美国食品 营销协会） 发表的一份报告。 其原因是传统商店的经费高于会员制全销俱乐部等 新商业形式，比如，超级市场的经费率为 21.8%，而会员制的全销俱乐部只有- 13 -哈尔滨工业大学工学硕士学位论文7.5%，平价药店为 16%。其仓库商品的周转次数每年达 20 次左右，若利用客户 信息反馈这种有效手段， 可增加到 24 次。 JIT(just in time), 即及时制造系统， 可从零售商店很快地得到销售反馈信息，组织生产，达到零库存的目标，物流配 送不仅实现了内部的信息网络化，而且增加了配送货物的跟踪信息，从而大大提 高了物流企业的服务水平,降低了成本，增强了竞争力。 4、第三方物流发展迅速[55]。第三方物流服务公司大都是传统的“类物流”业为起点而发展起来的，如仓储业、运输业、空运、海运、货运代理和企业内的 物流部等，他们根据顾客的不同需要，通过提供各具特色的服务取得成功。 5、用新的科学技术改造物流装备和提高管理水平。 信息化―采用无线互联网技术， 卫星定位技术(GPS) ， 地理信息系统(GIS) , 射频标识技术（RF）等。 自动化―导引小车（AGV）技术，搬运机器人（Robot System）技术等。 智能化―电子识别和电子跟踪技术，智能运输系统（ITS） 。 集成化―信息化、机械化、自动化、智能化于一体。 信息技术在流通领域的广泛应用， 极大地提高了发达国家流通的效率和竞争 力。例如，沃尔玛将信息技术广泛运用于分销系统和存货管理，曾投入七亿美元 建立了一个卫星交互式通讯系统， 并在每一台货物运输车辆上都安装卫星移动计 算机系统， 可以实现世界范围内 5000 多家门店的单店管理， 110 家配送中心， 有 85%以上的商品自己配送。沃尔玛公司凭借先进的信息、补货系统，可将一件商 品从出厂到摆上货架的时间平均控制在 5―7 天，而一般公司需 30 天。信息技术 是沃尔玛领先于其对手的核心竞争力之一。 物流的发展与现代信息技术是息息相 关的，信息化是现代物流的灵魂，现代信息技术推动了传统物流的发展。 可以看出， 西方先进发达国家物流现代化的途径就是信息化，通过信息化建 设加大地缩短了服务响应时间，提高了物流的效率，从而达到降低成本的目标， 建立了企业核心竞争力。 我国物流业最需要借鉴西方发达国家的经验就是从微观 应用层面，推广使用现代物流的管理和技术，实现可持续的发展道路。1.3.2 国内、外物流配送路径优化研究现状自从 Danting 和 Ramser 于 1959 年首先提出车辆路径问题（VRP）及相应的 数学规划模型和求解算法以来， 由于其应用的广泛性和经济上的重大价值，一直 受到国内外学者的广泛关注。 在经典 VRP 的基础上， 配送车辆路径问题在学术研究和实际应用上产生了许 多不同的延伸和变化型态，包括带能力约束的车辆路径问题（CaPacitated vehide Routing Problems , CVRP） 、带时间窗的车辆路径问题（Vehicle Routing Problems with Time Windows, VRPTW） 、追求最佳服务时间的车辆路径问题 （Vehide Routing Problems with Defined Time, VRPDT） 、多车种车辆路径问 题（Fleet Size and mix Vehicle Routing Problems, FSVRP） 、车辆多次使用 的车辆路径问题（Vehicle Routing Problems with Multiple Use of Vehicle, VRPM） 、随机需求车辆路径问题（Vehicle Routing Problem with Stochastic Demand , VRPSD） 、动态车辆路径问题（Dynamc Vehicle Routing Problems , DVRP） 、考虑收集的车辆路径问题（Vehicle Routing Problems with Backhauls , VRPB） 、满载／非满载 VRP、双向 VRP 等[58]。本文对当前国内外不同的 VRP 研究- 14 -哈尔滨工业大学工学硕士学位论文进行综合，详细介绍有时间窗的物流配送路径优化问题的国内外研究现状。 有时间窗的 VRP (VRPTW）是对经典 VRP 加上时间窗限制（即加上客户要求 访问的时间窗口） 可以看作是经典 VRP 的一个特殊类。 ， 1985 年， Savelsbergh 证 明了 VRPTW 是一个 NP (Von-linear Problem，非线性规划）疑难问题，很难求 得问题的最优解。目前，国内外专家和学者对其求解主要集中在启发式算法上， 求得问题的近似最优解（可行解） 。 1964 年， Clark 和 Wright 提出 Clarke-Wright 算法 由 （成本节约法） 以后， Golden, Nelson, Paessens 等人通过使用适当的数据结构，降低了它的复杂度。 C-W 法随后成为许多专家和学者针对 VRPTW 的研究基础[59]。1968 年，Rao 等人在Balinski VRP 集分割的基础上引入了列生成方法进行求解。这种算法本质上是 最短路径算法，同时结合了分枝定界算法。Desrocher 曾用它求解有 100 个客户 的 VRPTW。1981 年，Fishe 等人针对带能力约束、时间窗以及无停留时间的 VRP， 提出了三下标车辆流方程。 基于 Benders 的分解方法， 他们提出了一种启发式算 法， 保证在有限的步骤内找到优化解。Fishe 等人用它计算了有了 0-199 个客户 的 VRP。Martello 和 Desrochers 则分别提出了相应的改进算法。1991 年 Thangiah 和 1993 年 Joey 分别用遗传算法求解 VRPTW，但是都存在“早熟收敛” 的问题[60][61]。1994 年，P.wark 等人提出了重复匹配的方法，该算法在其模型里[62]同时考虑了时间约束和能力约束，因此适用于这类具有强约束 VRP。重复匹配算法也可求解较大规模的问题（199 个客户） 。 在我国，一些专家和学者也开始尝试 VRPTW 的研究。1998 年，李大卫等人 对适用 TSP 的最近距离搜索启发式算法进行修正，构造出评价函数，并据此提出 一个求解 VRPTW 的启发式算法。2000 年，谢秉磊等人将货运量约束和时间窗约 束转化为目标约束， 设计了基于自然数编码的可同时处理软、硬时间窗约束的遗 传算法，实验分析获得了较好的结果[63]。2001 年，周贤伟和李光远根据车辆装载 GPS 设备的特性，建立了货物运输 VRPTW 的数学模型，并设计了求解的遗传 算法[64]。2002 年，张丽萍等人通过引入新颖交叉算子，构造了一种改进遗传算法。 该算法摆脱了对群体多样性的要求， 不存在传统遗传算法常见的 “早熟收敛” 问题，可用于解决 VRPTW[57]。2003 年，宋厚冰和蔡远利针对 VRPTW，在标准遗传算法的基础上，将分组信息与每一个染色体结合，并辅以补交换局部搜索技术， 构造了一种改进遗传算法，使得求解结果更接近最优解[56]。同年，宾松和符卓通过引用一种新的编码方法及交叉和变异概率的自适应机制， 构造了改进遗传算 法来求解带软时间窗的 VRPTW[55]。2004 年，刘小兰等人为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽的 VRP 的缺陷，介绍了 VRPTW 的通用数学 模型。通过分析各主要变量之间的关系，构造了一种简单、快速的确定性初始算 法，并通过引入“短路径优先策略”，构造了改进的大规模邻域搜索算法，该策 略也可嵌入到求解时间窗比较窄的 VRP 中，达到加速搜索的目的- 15 [49]。哈尔滨工业大学工学硕士学位论文1.4 本论文的研究目的随着经济全球化和信息技术的迅速发展， 企业依靠降低物质消耗和提高劳动 生产率来提升竞争优势的空间越来越小，被誉为“第三利润源泉”的现代物流正 在世界范围内广泛兴起。完善的物流将起到减少人力，减少企业内部运作环节， 提高生产效率，降低成本，增强竞争力的作用。 在整个配送环节中，车辆配送路线的合理优化，对于整个物流速度、成本、 效益影响至关重要。 目前，北大仓物流有限公司产品配送路径的选择主要是依靠 劳动者的经验手工制定的。 随着企业规模的不断壮大，销售营业部的数量和客户 间的路径也日益增多， 安排配送路径的复杂度越来越高。 手工配送不但耗时费力， 在配送路径的合理性上，也很难满足企业的业务需求。 为了进一步提高企业的物流配送效率、降低物流成本，最大限度地提升北大 仓物流有限公司的配送能力和市场竞争力， 根据具体的齐齐哈尔北大仓啤酒有限 公司的实际业务应用背景， 提出了利用改进的遗传算法来解决路径优化问题，应 用 MATLAB，尽可能缩短配送时间或配送距离，达到客户时效性的要求，从而 在降低配送成本的同时改善顾客服务的水平，是本文的研究工作目的。1.5 本论文的主要工作和框架结构作者阅读大量文献后， 对车辆路径问题按照涉及到的实际配送路径规划中的 不同约束条件进行分析和总结。 在此基础上提出了本文研究的车辆路径问题，即 在不违背车辆容量、最大路径、时间等约束条件的前提下，合理规划配送时的车 辆路径安排， 以尽可能小的成本满足客户对货物和服务时间区间的要求，用改进 遗传算法优化车辆路径问题，解决车辆调度任务。 应用改进的遗传算法对模型求解的最佳路径，优化配送路径，是本论文的核 心部分。 针对本文要解决的问题，构建以配送费用最小为目标的配送路径优化模 型，把顾客满意度引入模型中，作为一个重要的约束条件来处理，通过模型的构 建， 来解决实际当中可能遇到的问题， 进而优化问题。 在求解过程中， 通过改进， 将遗传算法的逻辑思维应用到的 MATLAB 编程当中，得到最合理的配送方案， 避免了多目标的计算复杂性，同时达到了多目标的效果。 本论文的主要工作如下： （1）针对北大仓物流有限公司产品配送过程中现实存在的到货时间过长、 货损严重等问题， 提出构建北大仓物流有限公司产品配送路线优化问题的数学模 型。 （2）在原有刘海交叉法的基础上，构造一种引申的刘海交叉法，并提出相 应的改进遗传算法。 （3）应用这种改进遗传算法，求解北大仓物流有限公司产品配送路线优化 中的实际问题。 （4）编制相应的 MATLAB 计算程序，实现北大仓物流有限公司产品配送 路线优化问题的迅速求解。 （5）通过具体实例，验证应用这种改进遗传算法求解北大仓物流有限公司 产品配送路线优化问题的有效性及优越性。 本论文各章节的主要内容如下： 第一章：本章介绍了本课题研究的背景，分析了北大仓物流配送路线优化研- 16 -哈尔滨工业大学工学硕士学位论文究的重要性， 描述了物流配送的发展状况， 阐述 VRPTW 问题的国内外研究现状， 并对本文的主要工作及研究内容做出了简要的概括。 第二章：主要介绍物流配送路径优化需要应用的主要技术和理论，阐述选择 理由。介绍了物流配送车辆路径问题、各种优化方法的介绍、比较分析；结合北 大仓啤酒有限公司物流配送实际，分析了算法选择的理由，介绍了遗传算法的概 况、特点、重要参数以及遗传算法的求解步骤和流程。 第三章：简要描述北大仓啤酒有限公司物流的基本情况，分析及各环节存在 的现状和存在的问题。将北大仓啤酒有限公司的物流分为物流采购、物流加工、 物流配送三个主要环节，分析北大仓物流配送环节普遍存在较多的问题。 第四章：根据北大仓啤酒有限公司的实际业务情况，讨了北大仓物流配送路 线优化问题， 首先针对该问题的主要内容以及时间窗约束给出了数学描述，构造 了车辆容量惩罚函数和时间惩罚函数，建立了该问题的数学模型；针对遗传算法 固有的控制参数选择困难及早熟收敛等缺陷， 在标准遗传算法基础上引入适用于 旅行商问题的刘海交叉法， 构造出一种引申的刘海交叉法，提出了相应的改进遗 传算法；编制了 MATLAB 计算程序，实现了北大仓物流配送路线优化问题的迅 速求解。 。 第五章：通过把改进的遗传算法应用到北大仓物流配送路径优化问题中，验 证改进的遗传算法。 结合北大仓物流配送路线优化问题的具体实际，阐述了该问 题的求解过程；借助 MATLAB 计算程序，实现了最优配送路线的搜索过程；根 据时间窗约束及容量限制约束对所求结果进行了核对； 利用标准遗传算法在同等 条件下重新求解了该问题； 在两个求解结果的比较过程中，验证了本文所提出的 改进遗传算法在求解该问题时的优越性， 证实了为求解该问题所编制 MATLAB7 . 0 程序的通用性和迅速性。 第六章：结论。通过对全文内容的归纳和总结，得出了本研究的主要结论， 指出了北大仓物流配送路径优化问题的进一步研究方向。1.6 本章小结通过本章节的研究，进一步明确了选题的背景、目的与意义，通过国内外的 物流以及 VRP 研究现状介绍，确定了本文的研究目的和研究内容。可以看出，现 代物流的发展，必须对物流配送路径进行优化，实现低成本、高效率、高品质的 物流配送服务。- 17 -哈尔滨工业大学工学硕士学位论文第 2 章 物流配送路径优化研究的相关理论本章主要对物流配送优化的相关技术和理论进行介绍， 解决北大仓啤酒有限 公司物流配送路径的优化问题。2.1 物流配送路径优化概述根据物流长期发展所形成的通用经验， 发现物流配送的一个重要目标就是要 在满足客户要求的前提下， 投入尽量少的配送成本（主要是各种运输线路上的损 耗） 。在网络化的今天，由于信息流通便捷，各部门协同工作的能力越来越强， 实现诸如“整合运输”“最低库存”“快速反应”的客观条件越来越充实；因此， 、 、 如何充分利用现有条件， 达到物流配送的最小成本消耗己经成为一个备受关注的 问题。特别是“整合运输”等一系列新的货物运输概念的提出，更使得原来的单 线的， 仓库→单个客户→仓库的配送模式被完全推翻，取而代之的是每个运输单 位运输不同的货物到不同的客户手中；而不是像往常那样，每个配送单位分配单 名客户，把货物运到客户手中就立即返回，造成路程上的大量浪费。 物流配送问题可以描述为： 如何选择最优配送路径，使得投入的运输成本最 低，又能满足客户的时间要求。实际上，由于客户数目的巨大，这一问题的可行 解数目非常巨大， 甚至不可能用类似于枚举法的方法在能够接受的时间范围内得 到最优解或者较优解，因此该问题己经成为一个公认的物流难题。2.2 物流配送路径优化目标物流配送路径合理与否直接影响着物流运输的成本和效益，因此，采用科学 的合理的方法确定配送路线， 是物流配送过程中非常重要的一项操作。确定配送 路线可以采取各种数学方法和在数学方法基础上发展和演变出来的经验方法。 无 论采取何种优化方法， 首先要明确物流配送路径的优化目标，目标的选择根据配 送的具体要求、配送中心的水平、实力及客观条件而定，一般有以下几种： 1、效益最高：在选择以效益为目标时，通常以企业当前的效益为主要考虑 因素，同时兼顾长远的效益。效益是企业整体经营活动的综合体现，可以用利润 来表示，因此，可以在计算时以利润数值最大化为目标值。但由于效益是企业经 营的总体反映，在拟定数学模型时，很难与配送路线之间建立函数关系，所以一 般很少采用这一目标。 2、成本最低：成本计算比较困难，但和以效益为目标相比有所简化。成本 和配送路线之间有密切关系， 且在成本对最终效益起决定作用的情况下，采用以 成本最低为目标实际上等于选择了以效益为目标，比较可行实用。 3、路程最短：如果成本和路程相关性较强，则可以选择路程最短为目标， 这样可以避免许多不易计算的因素。但需要注意的是，有时候路程最短并不意味 着成本最低，如果道路条件、道路收费等因素影响了成本，这时单以最短路程为 最优解则不合适了。 4、单位运输量最大：单位运输量是指单位距离内所运送的货物总重量。单 位运输量在长途运输中常作为选择目标。 5、准时性最高：准时性是配送中重要的服务指标，以准时性为目标确定配 送路线就是要将各客户的时间要求和到达各客户点的先后顺序进行协调安排， 这- 18 -哈尔滨工业大学工学硕士学位论文样有时难以顾及成本问题，甚至需要牺牲成本来满足准时性要求。 6、运力利用最合理：在运力非常紧张、运力与成本或效益有一定相关的情 况下，为了节约运力、充分运用现有运力，而不需外租或新购车辆，也可以运力 安排为目标，确定配送路线。 针对不同的物流配送问题， 要根据具体情况选择优化目标。本文研究的物流 配送问题根据北大仓啤酒有限公司自身物流的特点， 将优化目标设定为： 路程短、 准时性高、运力利用合理。2.3 物流配送的路径优化方法的选择国外将物流运输车辆调度问题归结为 VRP (Vehicle Routing Problem，即 车辆路径问题)[24][25]、VSP (Vehicle Scheduling Problem，即车辆调度问题)和MTSP(Multiple Traveling Salesman Problem，即多路旅行商问题)。该问题于 1959 年由 Dantzig 和 Ramser 提出后[26]，很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定 者的极大重视， 并一直是运筹学与组合优化领域的前沿与热点问题。在现实生产 和生活中，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、 电力调度问题、 管道铺设问题、 计算机网络拓扑设计问题等都可以抽象为物流运 输车辆调度问题。 本文所研究的物流配送车辆路径问题的求解方法对解决上述问 题也是有效的。可见，本文将物流配送车辆路径问题作为研究对象，具有一定的 理论和现实意义。 经典的物流配送路径优化问题（即经典 VRP）可描述如下：有多个货物需求 点 （或称顾客） 已知每个需求点的需求量及位置， ， 至多用 m 辆汽车从配送中心(或 中心仓库)送货，每辆汽车载重量一定，安排汽车路线，要求每条路线不超过车 辆载重量和每个需求点的需求必须且只能由一辆车来满足， 目标是使运距最短或 者运输费用最少。 早在 1962 年 Balinski 等人首先提出 VRP 的集分割，直接考虑 可行解集合， 在此基础上进行优化， 建立了最简单的 VRP 模型 。 1981 年， Eilon 等人提出将动态规划法用于固定车辆数的 VRP，通过递归方法求解 。1974 年， Wren,Gillett 等人提出 Sweep 算法(扫描法) 。1981 年，Christofides 等人提 出了 k 度中心树和相关算法，对固定车辆数 m 的 M-TSP 进行度中心树松弛 后来， M.L.Fishe 对这种方法做了进一步改进可求解有 134 个客户的 VRP 年，Gendreau 等人将禁忌搜索方法应用于 VRP[12] [11] [10] [9] [8] [7]。。 1991。它是针对 VRP 比较好的启发式算法，可以成功地应用于许多经典的 VRP。其后 E.Taillard 等人通过按角度 和路径重心对原问题的空间进行分割，结合禁忌搜索和模拟退火对子问题求解， 实现了对问题求解的并行化[13]。1996 年，J.Lawrence 将遗传算法用于 VRP 的研- 19 -哈尔滨工业大学工学硕士学位论文究，并可有效求解带时间窗限制的 VRP[14]。鉴于传统的遗传算法是个大范围、粗粒度的寻优算法，Barnier 将其与约束满足问题(CSP)的技术相结合，通过遗传 算法来处理 CSP 参数的子域， 从而减小搜索空间，降低 CSP 问题目标函数和遗传 算法约束的复杂度。 由于有时间窗约束的路径优化问题一直被众人作为核心内容研究， 围绕其进 行扩展研究， 因此适应求解有时间窗限制的路径优化的方法自然也适合其他扩展 问题的求解。 本章将回顾国内外学者对求解该类问题时的相关方法， 作为本文求解算法的 基础。2.3.1 物流配送路径优化的方法随着信息技术的不断进步， 企业运营节奏的加快，有关的研究方法也随之进 步。可以说问题由简单到复杂，研究方法则由精确解法发展到传统启发式算法， 再到现代启发式算法，下面就路径优化的研究方法进行综述。 1、物流配送路径优化问题的精确算法[27]（1）动态规划法(Dynamic Programming)。动态规划法被用到求解物流配送 路径优化问题是 Eilon 等人在 1971 年提出的。Kolen 等在 1987 年第一个将动态 规划法用到带时间窗限制的路径优化问题上。该算法解题的基本思路是将一个 n 阶段的决策问题转化为依次求解 n 个具有递推关系的单阶段的决策问题， 从而简 化计算过程[32]。因其复杂性在于各阶段决策之间的相互联系，而且计算时间与计算机内存空间均随变量的增加而呈指数增加，所以虽然此方法可求得最优解， 但仅适用于较小规模的寻优问题。 （2）分枝定界法(Branch and bound)。此方法是一种隐枚举法或部分枚举 法，它不是一种有效算法，是枚举法基础上的改进，是求解整数规划的较好方法[32]。Kolen 曾利用此方法求解有时间窗约束的车辆巡回问题，其实验的节点数范围为 6～15。当节点数为 6 时，计算机演算所花费的时间大约 1 分钟(计算机机 型为 VAX11/785)，当节点数扩大至 12 时，计算机有内存不足的现象产生，所以 分枝定界法比较适用于求解小型整数规划问题。Held 和 Karp 指出分枝定界法的 求解效率与界限设定的宽度有极大的关系。 （3）切平面法(Cutting planes)。此方法与分枝界限法类似，也是在求解 与整数规划相对应的线性规划上，不断地增加新的约束，也就是另外加入线性约 束条件， 以切掉对应于非整数规划的所有可行解的集合，以使问题可达到整数线 性规划求解的形式，从而获得最优解。求解时间过长，不适用于大规模问题。 2、物流配送路径优化问题的传统启发式算法[28][29][30]传统的启发式算法在求解路径优化问题时通常是从初始解出发， 以邻域搜索 的方式实现解的改进， 并在较短的时间内获得一个可以接受的解。下面详细介绍 几种最常用的传统启发式算法。 （1）节约算法(Saving Method)。节约算法最早由 Clarke 等于 1964 年提出- 20 -哈尔滨工业大学工学硕士学位论文该方法并用于求解车辆巡回问题。 其思想在于按节约值(较短路径与原路径之差) 从大到小排序，在车辆的容量限制下，依序将对应的两个顾客点排入路径中，直 到所有的顾客都被插入路径为止[33]。Solomon 于 1983 年将此方法用于求解有时间窗约束的车辆巡回问题， 关键在于当节约值较大的两客户点被排入路径时，除 需考虑车辆容量限制外， 更需要考虑到时间窗的限制， 也就是时间窗上界较早者， 应优先被配送，并检验其时间可行性。 而两节点间的节约值的计算公式如下：s?i, j ? ? d (i, o) ? d (o, j ) ? d (i, j )（2-1）其中:d(i，o)代表客户 i 至配送中心的距离， d(i，j)则代表客户 i 至客户 j 的距离。 计算两节点 i 与 j 间的节约值 s(i，j)时，应先计算原路径中各往返路径的 总和 s(i，j),再以之与较短路径的总路径和相比较；两节点的原路径与较短路 径如图 2-1 所示。此方法的优点是可提高车辆的利用率。 di dj di djd 原路径d0 较短路径图 2-1 路径优化前后 Chart 2-1 Around way optimization （2）邻接算法(Nearest-Neighbor)。邻接算法是 Solmon 于 1983 年所提出 的求解带时间窗限制的方法，它是一种序列构造路线法[35]。算法从一条只含一个配送点的路线出发(通常取这个点为―“距离”配送中心最近的点)。在未分配 点中筛选出可加入点(所谓可加入点，是指一个未分配点，将它作为一条路线的 终点仍然保持路线的可行性)， 并从可加入点中选取一个点作为当前路线的终点， 使得路线的成本最小。 如此不断对路线进行扩充， 直到路线不存在可加入点为止。 这时，如果所有点均已分配，则算法结束；否则，生成一条新的初始路线，重复 前面的路线扩充程序。 需要指出，对距离加上双引号是为了说明这样的距离未必 指实际的距离，而是关于距离和时间等因素的函数。 （3） 插入算法。 它原本是 Mole 和 Jameson 于 1976 年所提出， 用于求解 VRP 问题的方法， 其结合邻接算法与节约算法的观念，依序将顾客点插入路径中以构 建配送路线。Solomon 于 1983 年将此方法应用于求解 VRPTW 问题，因为时间因 素加入，而使原问题的顾客的等待时间缩短。它的流程与邻接算法相似，也是从 初始路线出发，序列构造路线。并在不存在可行插入时新增一条初始路线。插入 算法的关键是选择最合适的未分配点在路线中进行最佳位置的插入。 （4）扫除算法。扫除算法最早由 Gillett 和 Miller 在 1974 年提出，是一 种“先分组后路线”(cluster-firstroute -second)的算法[36]。1987 年，将其推广应用于 VRPTW 问题的路线构造。所谓分组，即指分派给每辆车一组点。一种- 21 -哈尔滨工业大学工学硕士学位论文简单的分组方法是将以车站为原点的坐标平面划分为多个扇形区域， 并初步将每 个扇形区域的点分派给一辆车。而所谓的“路线” ，是指在每个区域内，采用扫 除法选择未分配点，然后应用插入算法扩充路线。如果在进行了一次“分组―路 线”的路线构造后，还存在未分配点，则再进入“分组―路线”程序。如此反复， 直到所有点均已分配为止。 3、物流配送路径优化问题的现代启发式算法 相对于传统启发式算法， 现代启发式算法不要求在每次迭代中均沿目标值下 降方向， 而允许在算法中适当接受目标值有所上升甚至不可行的解，其目的是能 够跳出局部搜索邻域。下面，对应用于 VRPTW 的现代启发式算法进行综述： （1） 禁忌搜索算法(TABU SEARCH,TS)。禁忌搜索算法最早由 Glover 在 1986 年提出， 是局部搜索算法的扩展。该算法通过利用一个禁忌表记录已经到达过的 局部最优点， 并在后面的搜索中，根据某种限制循环的规则和禁忌表中记录的信 息在当前搜索邻域中取一个合适的解[33]。典型的禁忌是禁止在最近的次迭代中选取某些边，以控制在最近的 t 次迭代中不会出现同样的解。有时，根据某种事 先设定的规则， 选用某个禁忌对象可能会使搜索邻域更快地接近全局最优点，这 种规则被称为特赦规(Aspiration Criteria)。 1994 年，Garcia 等首先将禁忌算法应用于 VRPTW 问题[37]。为了减少搜索的计算量，有专家提出了一些限定邻域的方法。另一方面，为了加速搜索进程，可 采用平行计算技术。 较多算法都以车辆数最少为优化的第一目标。 在禁忌搜索中， 通过一些变化(diversification)与强化(intensification)规则来引导搜索将 显著提高其搜索效率。 1995 年，Rochat 和 Taillard 定义了所谓的“适应性记忆信息”(adaptive memory),即在搜索过程中， 将最好的解所包含的一些路线保存下来所汇集而成的 路线信息。 其目的是通过对适应性记忆信息中所有路线进行筛选与组合后，为禁 忌搜索提供一个新的起始解。之后，在 1997 年，Taillard 应用这种思想求解带 软时间窗的问题。为了避免低效率的循环或过度限制搜索邻域， Chiang 和 Russell 对禁忌表长度实施动态控制，即当同样的解重复次数较多时增加禁忌表 的长度，而当搜索不到可行解时减少禁忌表长度。 （2） 遗传算法(Genetic Algorithm,GA)。 遗传算法最早是由 Holland 在 1975 年提出，并首先被 DeJong 用来解决复杂问题[37]。由于遗传算法是借用适者生存规律进行局部搜索改进的一类算法， 最优化问题的求解过程是从众多解中选出最 优解，而生物进化的适者生存规律使得最具有生存能力的染色体以最大可能生 存。 二者的共同点使得遗传算法可以在优化问题中得以应用。该算法通过染色体 的配对和变异过程实现种群的进化，每一次进化则对应解的一次迭代。当迭代次 数达到最大次数限制或群体中的个体无显著差异时，迭代终止。 1991 年，Thangiah 首先将遗传算法用于求解 VRPTW 问题。该文将遗传算法 用于点的分组。其中，每一种分组方案被编码为一个染色体，适应性函数值定义 为根据相应的分组方案所构造的路线总成本， 而交配则指通过随机选取染色体的 两个位串(即两个组)进行的点的互换， 最后以小概率事件改变其中某些位的值来 实现变异。 1999 年， Homberger 和 Gehring 提出了应用遗传算法求解 VRPTW 问题的进化- 22 -哈尔滨工业大学工学硕士学位论文策略。具体地，将所谓的策略参数与解向量一同编码，并通过重组和变异来实现 进化。对于 VRPTW 问题，策略参数包括某种局部搜索方法的使用频率，以及在车 辆数和总路长这两个目标之间交替改进的一个二进制参数。同年，Gehring 和 Homberger 采用一种协同自治的方式在车辆数优化方法与总路长优化方法之间 建立一种协作关系。具体地，算法应用遗传算法最小化车辆数量，应用禁忌搜索 算法最小化总路长， 并通过制定解的更新规则建立这两个优化方法之间的协作关 系。可见遗传算法在路径优化问题上的应用性很广，而且有一定的延伸性，值得 做进一步改进，使算法更合理。 （3） 模拟退火算法(Simulated Annealing, A)。 1996 年， Chiang 和 Russell 提出带时间窗的配送路径问题的模拟退火算法。 模拟退火算法实际上是一种随机 松弛技巧，它模拟了退火过程。在搜索的初始阶段，算法跳向远点，随着时间的 延伸或“降温” ，跳跃幅度逐渐减小，最终转向局部搜索下降方法。2000 年，Tan 等基于 2-interchange 法和单调降的降温表提出一种快速模拟退火算法。 当到达 最低温度后， 通过参考初始温度和到达最好解时的温度设置一个新的温度，然后 重新启动模拟退火搜索过程。2001 年，Li 等在应用插入算法和扫除算法初始化 路线后，将邻域搜索方法与模拟退火程序相结合实现路线改进。 （4）蚁群算法(Ant Colony Optimization, ACO)。蚁群算法模拟了蚁群搜 索食物的行为。 在寻找食物时， 蚂蚁会在它所经过的路径通过排放一种外激素(在 算法中称为信息素)做出标记，排放的量则根据路径长度和食物的等级决定。这 些外激素为其它蚂蚁提供信息，并吸引他们前去搬运食物。对于 VRPTW 问题，每 一条边(i，j)对应两个值，即吸引力认η 11 和信息素τ 11。通常，η 11 表示两点 间距离的倒数，在整个求解过程中是一个固定量，而τ 11 则表示在搜索过程中选 择一条边的价值， 它在迭代过程中是一个需要不断调整的量。在路线的构造过程 中，将根据η 11 和τ 11 确定的概率分布随机选取下一点对路线进行扩充，而信息 素则根据边的选用情况进行局部和全局性的更新。具体地，局部性更新是在蚂蚁 选用一条边之后，即刻对这条边的信息素τ 11 下调，以减少这条边再次被选取的 概率，从而提高解的多样性；全局性更新则是针对当前所获得的最好解，对其某 种邻域内的边的信息素τ 11 上调，以增加这些边被选取的概率。1999 年， Gambardella 应用蚁群算法对 VRPTW 进行路线改进。算法中，首先构造两组相互 协作的人工蚁群， 其中第一个蚁群用于最小化车辆数，第二个蚁群用于最小化总 路长， 并以共用解的方式建立协作关系。上述优化方法都曾解决过不同难易程度 的配送路径优化问题，是根据实际发展需要而发展起来的，总结如图 2-2 所示。 从框架结构图中可以看出：VRP 求解是由简单到复杂，而求解方法则由精确 到合理，适用性由小规模到大规模，可见其发展是随着实际需要发展的，有一定 的必然性，在优化方法的选择上自然也需要改进和发展。VRP 求解方法最优化算法传统启发式算法现代启发式算法法动 态 规 划法分 枝 定 界切 平 面 法节 约 算 法邻 接 算 法扫 除 算 法法禁 忌 搜 索遗 传 算 法法模 拟 退 火蚁 群 酸 法- 23 -哈尔滨工业大学工学硕士学位论文图 2-2 物流配送路径优化方法框架图 Chart 2-2 Logistic distribution way optimization method frame chart2.3.2 各种优化方法比较分析综上所述，各种优化方法在一定时期、一定情况下都有其各自的优点，都有 解决某一类问题的优越性，但随着发展的需要，对优化方法要求也越来越高，下 面对各种方法进行比较分析， 通过表格的形式来展现各自的特点， 如表 2.1 所示。 通过表格的分析比较， 可以看出各种方法的特点，物流配送路径优化问题的 精确算法有一个共同的特点就是可以求得最优解， 但由于它引入了严格的数学方 法，所以用它们求解中小规模的 VRP 时在精度上优于其他算法。而 VRP 即又是 NP 难题，精确算法无法避免指数爆炸，所以不适应现在的复杂的路径优化问题， 尤其是对多配送点的大型配送服务， 相对求得最优解比较费时费力， 且难以实现。 而传统的启发式算法比精确算法相对好些， 但仍不太适用于现在实际遇到的 问题，和现代启发式算法相比，有些不足，但可以将传统的与现代启发式算法结 合使用， 通常可以在有限时间里找到满意的次优解或可行解，这是精确算法难以 达到的，因此现代启发式算法方便适用，能解决实际当中所遇到各种复杂问题。 表 2-1 各种优化方法的比较分析类别 基本方法 优点 缺点 计算时间长且占用内 可以求最优解 存量随变量的增加成 指数倍增长 求得最优解 计算时间长且内存使 用常有不足现象发生 计算时间长且所需内 存大 解是较优的可行解， 不一定是最优解 排序时有局限性 1964 年 1983 年 1976 年 1974 年 1986 年 1975 年 1996 年 1999 年 产生时 间 1971 年 适用性动态规划 物流配送路径 优化问题的精 确算法 法 分枝定界 法 切平面法适用于规模较 小的问题 用于解组合优 化的小型问题 适用于解小规 模问题 可以解决大规 模问题 适用节点少的 适用于小规模 问题 适用于小规模 问题 适用于带软时 间窗的 VRP 问 题 适用于复杂优 化问题 适用于对已有 路径进行改造 试用于多目标可以求得最优解 提高车辆利用率， 可以解 决大规模问题 考虑邻近节点成本问题 结合节约法和最邻近法、 等待时间缩短 穿插插入法， 将二者有机 结合 可以通过规则提高搜索 效率 具有鲁棒性且全局搜索 能力强，所需时间少 采用随机松弛技巧 可以将目标构造成两组 相互协调的蚁群节约算法物流配送路径 优化问题的传 统启式算法发邻接算法插入算法速度慢、解非最优 扫描每一个点，速度 慢 可能搜索到局部最优 解 可能会有早熟收敛现 象 搜索结果不能保证是 最优的 需要不断调整变量扫除算法禁忌搜索 算法 物流配送路径 优化问题的现 代启发式算法遗传算法 模拟退火 算法 蚁群算法- 24 -哈尔滨工业大学工学硕士学位论文2.3.3 优化方法的选择遗传算法是一种仿真自然界“优胜劣汰、适者生存”演进规则的搜寻法则， 它虽然是一种随机的搜寻方式， 但并非完全盲目的进行，而是根据每一代群体所 累积的信息来对搜寻空间做修正并产生较合理的解，同传统的寻优算法相比较， 遗传算法具有以下特点 （1）遗传算法对问题参数的代码集起作用而不是对参数本身起作用。遗传 算法处理的对象是染色体， 因而要求把所要优化问题的基本参数转化成定长的有 限符号的染色体。 （2）遗传算法是从初始群体开始搜索的，而不是从单点开始搜索的。许多 传统优化方法都是从搜索空间的单点出发，通过某些转换规则确定下一点。这种 点到点的搜索方法在多峰值优化问题中， 首先找到的可能不是最优峰值而遗传算 法是以点集开始的寻优过程， 初始群体是随机地在搜索空间中选取的，这样在搜 索过程中达到最优峰值的概率远大于点到点的概率。 （3）遗传算法在搜索过程中只使用适应度函数信息，而不用导数及其他辅 助信息。对于不同类型的优化问题，传统方法需要不同形式的辅助信息，没有一 种优化方法能适应各类问题的要求。遗传算法在优化过程中，放弃使用这些辅助 信息，具有广泛适应性。 （4）遗传算法使用概率转换规则而不用确定性规则。遗传算法使用概率转 换规则来调整其搜索方向， 各代群体间没有统一的联系规律。但使用概率转换规 则并不意味着这种方法属于随机算法范畴， 它只是使用随机转换作为工具来调整 搜索过程趋向于目标函数不断改进的区域。 与传统方法相比，遗传算法的优越性主要表现在：首先，在遗传算子的作用 下， 遗传算法具有很强的搜索能力， 能以很大概率找到问题的全局最优解； 其次， 由于它固有的并行性， 能有效地处理大规模的优化问题。其应用研究总的来说有 三大类：优化计算、机器学习和神经网络。其中优化计算是最直接的应用，而且 应用面也最广。对于复杂的函数优化问题，包括非线性、不连续、多峰值函数的 优化， 传统的数学优化方法难于处理或易陷于局部极小解，而遗传算法则比较有 效。 用遗传算法处理与函数优化相区别的组合优化问题，也有更大的机会发现全 局最优解。 再者遗传算法容易与现存模型结合并建立仿真界面，颇富弹性且易发 挥，而且由于其结构是开放式的，与问题无关，所以容易和其它算法结合。 基于以上这些优越性，本文选用遗传算法作为求解模型的基础，结合 MATLAB，使得模型及算法更合理，计算更方便快捷，从而求得较合理的解，在实 际应用中更具普遍性，实用性。2.4 遗传算法的概述近年来， 随着人工智能应用领域的不断扩大，传统的基于符号处理机制的人 工智能方法在知识表示、 信息处理和解决知识爆炸等方面所遇到的困难越来越明 显，从而使得寻求一种适合大规模问题并具有自组织、自适应、自学习能力的算 法成为有关学科的一个研究目标[31][32][33][34]。遗传算法(Genetic Algorithm,简称 GA)，是一种有效的解决最优化问题的搜索算法。它是由美国 J.Holland 教授 于 20 世纪六、七十年代研究形成的一个较完整的理论和方法，是模拟达尔文的- 25 -哈尔滨工业大学工学硕士学位论文遗传选择和自然淘汰的生物进化过程的计算模型[30]。遗传算法是一种自适应全局优化概率随机搜索方法，它对优化对象既不要求连续，也不要求可微，目前已 被广泛应用于组合优化、人工智能、人工生命领域，并取得了良好效果。2.4.1 遗传算法的发展历程生命科学与工程科学的相互交叉和渗透产生了基于人工智能的进化优化算 法。 这类算法的核心思想源于这样一个基本认识：生物进化过程本身是一个自然 的、并行发生的、稳健的优化过程。这一优化过程的目标是对环境的自适应性， 生物种群通过遗传变异来达到进化的目的。 遗传算法是一种宏观意义下的仿生算法， 它模仿的机制是一切生命与智能的 产生与进化过程，通过模拟达尔文“优胜劣汰、适者生存”的原理鼓励产生更好 的结构， 同时通过模仿孟德尔遗传变异理论在迭代过程中保持己有的结构，并寻 找更好的结构。遗传算法也是通过繁殖、变异、竞争和选择这四种基本形式实现 的。 20 世纪 40 年代，有学者开始研究如何利用计算机进行生物模拟的技术。 60 年代，Holland[15]教授认识到了生物的遗传与自然进化现象与人工自适应系统的相似关系， 提出在研究和设计人工自适应系统时，可以借鉴生物遗传的 机制，以群体的方式进行自适应搜索。 1967 年，Holland 教授的学生 Bagley 在其博士论文中首次提出了“遗传算 法”一词[16]，后来他还发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法，创立了自适应遗传算法的概念。 70 年代初，Holland 教授提出了遗传算法的基本定理-模式定理（Schema Thcorem)，从而奠定了遗传算法的理论基础。 1975 年，Holland 出版第一本系统论述遗传算法和人工自适应系统的专著 《自然系统和人工系统的自适应性（Adaptation in Natural and Artificial systems） 》[15]。1975 年，De Jong 在其博士论文中结合模式定理进行了大量的纯数值函数优 化计算试验， 树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结 论[17]。他还建立了著名的 De Jong 五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。 1989 年，D.E.Goldberg 出版了专著《搜索、优化和机器学习中的遗传算法 （Genetic Algorithrns in search, Optimization and Machine Learning） 》[18]。该书系统的总结了遗传算法的主要研究成果，奠定了现代遗传算法的科学基础。 1991 年，L.Davis 编辑出版了《遗传算法手册（Handbook of Genetic Algorithms) 》一书，书中包括了遗传算法在科学计算、工程技术和社会经济中 的大量应用实例[19]。- 26 -哈尔滨工业大学工学硕士学位论文自上世纪 70 年代起，我国学者也将遗传算法广泛的应用于生产实践的各个 领域，并取得许多重要的科研成果。2.4.2 遗传算法的特点与应用遗传算法是一种新型的、 起源于自然遗传学和计算机科学的优化方法，其实 质是将优胜劣汰， 适者生存的原理及遗传机理抽象出来的，形成了一种非常便于 计算机实现的算法。 遗传算法的特点可归纳为： 1、遗传算法是对一组参数编码进行优化，而非参数本身，这使得原问题的 表达和求解比较灵活。 2、遗传算法是在一群点上搜索最优解而不是从单一点上进行搜索，保证了 解的全局最优。 3、遗传算法直接使用适应函数而不需要其导数，这样就可以考虑许多与实 际问题有关的约束条件。 4、遗传算法采用了概率转移规则，而不是确定性规划，但这里的概率转移 规则并不是简单的随机游走。 这样就使算法能以很快的速度找出最优解。 实际上， 遗传算法的计算量与解题规模是线性增长关系，避免了维数灾难的问题。 遗传算法不依赖问题的具体领域，广泛应用于许多学科[19，21，22]方向：函数优化问题、组合优化问题、生产调度问题、自动控制问题、机器人学、图像处理、 人工生命、遗传编程、机器学习等。2.4.3 遗传算法求解一般步骤不同的编码方法和不同的遗传算子可以构成不同的遗传算法， 它们有一个共 同的特点，即对生物进化过程中的选择、交叉、变异的模仿，以此完成对问题最 优解的自适应搜索。Goldberg 总结了统一的最基本的遗传算法-基本遗传算法[18]。基本遗传算法只使用选择、交叉、变异这三种基本遗传算子构成完备的算子集合，其遗传进化操作过程简单、容易理解，是其它遗传算法的基础，它不仅 给各种遗传算法提供了一个基本框架，同时也具有很高的应用价值。 基本遗传算法的构成要素主要包括： 染色体的编码方法、 个体适应度的评价、 遗传算子（比例选择算子、单点交叉算子和基本位变异或均匀变异算子） 、运行 参数（包括群体大小、算法终止进化代数、交叉概率、变异概率） 。它可以定义 为一个 8 元组： SGA= (Code,E,Po,N,S,C,M,T) (2-2) 式中： Code:个体编码方法 E:个体适应度评价 Po: 初始群体 N:群体规模 S: 选择算子 C:交叉算子 M: 变异算子 T:运行终止代数 对于一个需要进行优化计算的实际应用问题， 一般可以按下述步骤来构造求 解该问题的遗传算法[20]:- 27 -哈尔滨工业大学工学硕士学位论文Step1：确定决策变量及其各种约束条件，即确定个体的表现型 X 和问题的 解空间； Step2：建立优化模型，即确定出目标函数的类型（是求目标函数的最大值 还是求目标函数的最小值?),及其数学描述形式或量化方法； Step3：确定表示可行解的染色体编码方法，即确定出个体的基因型 X’和 遗传算法的搜索空间； Step4：确定解码方法，即确定出由个体基因型 X’到个体表现型 X 的对应 关系或转换方法； Step5：确定个体适应度的量化评价方法，即确定由目标函数值 f(x）到个 体适应度的转换规则； Step6：设计遗传算子，即确定选择运算、交叉运算、变异运算等具体的操 作方法； Step7：确定遗传运算的有关运行参数，即确定遗传算法的 N、T、Po、Pm 等 参数。2.4.4 遗传算法求解一般流程遗传算法在整个进化过程中的遗传操作是随机性的， 但它所呈现出的特性并 不是完全随机的， 它能有效利用历史信息来推测下一代期望性能有所提高的寻优 点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体，即找到所求 问题的最优解。 遗传算法的基本流程，如图 2―3 所示。通过了解遗传算法的基本步骤和基 本流程， 能够清楚利用遗传算法进行求解计算时的计算原理及操作步骤，明确遗 传算法的具体搜索过程[47]。问题确定表示问题解答的染色体初始化染色体种群计算每个染色体的适应度满足终止条件 否 根据适应度值选择染色体复制是交叉 输出最优解 变异图 2-3 遗传算法的基本流程 Chart 2-3 Genetic algorithm basic flow- 28 -哈尔滨工业大学工学硕士学位论文2.5 遗传算法的重要参数利用遗传算法进行搜索优化问题的最优解时， 主要由遗传算法的重要参数来 控制具体的寻优过程。2.5.1 遗传空间遗传空间由三个有序的子空间（S，O，F）构成，S 表示染色体子空间，其 中每个元素均由长度为 l 的串构成；O 表示算子子空间；F 表示环境子空间，由 适应度全体构成。2.5.2 编码遗传算法并不直接处理问题空间的参数， 而是将问题空间的参数转换成染色 体的形式后对染色体进行遗传操作，这种从参数到染色体的转换过程即为编码。 经典的编码方法是二进制编码，但在很多实际情况下，这种编码串偏长，难以直 接描述出问题的真实性质。近 10 年来，针对特殊问题人们提出了各种非 0-1 串 的编码方法，例如约束优化的实数编码，组合优化的整数编码等，设计了专门的 遗传算子完成遗传操作。 张晓绩等人研究二进制和十进制编码在搜索能力和保持 群体稳定性上的差异后认为， 二进制编码比十进制编码的搜索能力强，但前者不 能保持群体稳定性[23]。康立山等人进行的实验表明利用十进制编码的算法比利[45]用二进制编码的算法平均效率高。2.5.3 染色体染色体又称为个体， 是生物学中的概念，在遗传算法中通常用一个所谓的串 来表示，有时也采用一个向量来表示。 X=（ x1 x2 ...xi ） 式中：X―染色体； (2-3 )x1 x2 ...xi ―基因；I ―基因数。 其中，基因是染色体 X 的基本单元，染色体上的一个有效信息段叫做基因 组，一般一个基因组对应于解中的一个优化参数。在遗传算法中，根据问题的不 同染色体一般可分为二进制的 0-1 串、整数串、实数串、复数串等。2.5.4 种群和种群规模种群是个体的集合， 应用遗传算法求解具体问题时，从随机选择的多个初始 解开始迭代搜索， 这多个初始解的集合以及每次迭代生成的一组新解就构成一个 种群。 种群规模是群体所含个体的数量，通常用 n 表示。种群中的个体在整个演化- 29 -哈尔滨工业大学工学硕士学位论文过程中是不断变化的，但种群规模不变，它的取值非常关键。当 n 过小时，可 提高算法的运行速度， 却降低了种群的多样性， 有可能引起遗传算法的早熟现象， 而当 n 过大时，可能降低算法的运行速度，所以一般建议的取值范围为 20～ 100 。2.5.5 遗传算子遗传算子作用在基因串上，是模拟种群进化过程的主要手段。 （1）选择算子 选择算子作用在一个基因串上，它根据一定的选择策略，以较大的概率从父 代群体中选择适应值较大的个体复制到子代中，等待交叉和变异对其进一步演 化。目前，有多种不同的选择策略，如轮盘选择、线性排名选择、锦标赛选择等， 各种策略在原理上是一致的。即在旧的群体中“随机”选择个体生成一个新的群 体，这种“随机”选择并非完全随机，它是基于一个个体相对于整个群体的适应 值，根据个体的适应值确定选择的系数，按比例复制生成新个体加入新种群中。 其中，轮盘选择策略最为常用，其实施步骤也比较简单。 轮盘选择法、 线性排名选择法及锦标赛选择法都是基于概率的选择方法，其 优点在于对适应值低的个体也给予被选择的机会，以维持群体的多样性。但是， 适应值高的个体也可能被淘汰，造成演化的暂时倒退。为弥补这一不足，可以将 父代的最优个体无条件地传给其子代，这种方法被称为精华保存法，在选择算法 后保留当前最好个体（精华保存）的遗传算法能以概率 1 收敛到全局最优解[46]。（2）交叉算子 交叉算子通常作用在两个基因串上，它把两个基因串中的某一部分相互交 换，产生两个新的个体，交叉算子可分为点式交叉算子和均匀交叉算子。 点式交叉算子首先随机地在两个父体串上选择一个（单点式交叉算子）或多 个（多点式交叉算子）交叉点，然后交换（单点式交叉算子）或间断交换（多点 式交叉算子）父体串的对应子串。 均匀交叉算子是按照概率交换两个父串的每一位， 即先随机产生一个与父串 具有同样长度的二进制串，其中 0 表示不交换，1 表示交换。这个二进制串称为 杂交模板， 然后根据该模板对两个父串进行杂交操作， 所得的两个新串即为子串。 点式交叉算子能以较大的概率保护优良的模式， 均匀交叉算子则具有较强的 搜索能力。 这两种交叉算子都是针对二进制编码交叉操作的常用算子，对一些数 值问题常采用十进制（序数）编码，此时就需要根据这两种交叉算子设计专门的 十进制交叉算子。 交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率 一般应取较大值，通常其取值范围在 0.4～0.99 之间。 （3）变异算子 生物细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些差错， 这样就会导致生物的一部分基因发生某种变异，从而产生新的个体，表现出新的 生物性状。 虽然发生变异的可能性很小，但它是产生新物种的一个不可忽视的原 因。 为了模仿生物遗传和进化过程中的这个变异环节，在遗传算法中引入了变异 算子。 变异算子作用在一个染色体上， 它是遗传算法用以模拟生物在自然界的遗传 环境中由于各种偶然因素引起基因突变而引入的一种算子，它按照一定的概率，- 30 -哈尔滨工业大学工学硕士学位论文随机选取染色体中的一个基因，改变其值，生成一个新的个体。 变异算子将可变性引入群体，从而提供了跳出局部最优值的一种手段。同自 然界一样，每个基因发生变异的概率一般很小，但若取值过小，就会降低变异操 作产生新个体的能力以及抑制早熟现象的能力，因此建议变异概率的取值介于 0. 之间。应该注意的是，变异算子在改善遗传算法局部搜索能力的同 时，还要维持群体的多样性，防止出现早熟现象。2.5.6 适应度和适应度函数适应度是表示遗传空间中某一个体对于环境的适应程度或者在环境压力下 的生存能力，适应度的大小取决于个体的遗传特性。为区别不同的解，在遗传算 法的演化过程中引用了一个评价函数，即适应度函数，作为适应度的惟一量度。 常用的适应度函数有原始适应度函数、标准适应度函数、约束问题的适应度函数 等。 适应度函数值越大其对应解越接近问题的解，适应度函数的最大值对应于问 题的最优解。2.5.7 进化代数设定进化代数是遗传算法最简单、最常用的一种运行结束准则，它表示算法 运行到指定代数之后就停止运行， 并将当前种群中的最佳个体作为所求问题的最 优解输出。一般将指定的进化代数记为 T，其取值范围在 50～500 之间。 通过上述遗传操作的重要参数来控制遗传算法的具体寻优过程， 进而搜索所 求问题的最优解。2.6 本章小结本章通过对物流配送优化所涉及的技术和理论进行了介绍， 介绍了各种配送 路径优化方法，并比较优缺点，说明选择遗传算法的理由；重点介绍遗传算法的 发展历史，遗传算法的特点以及遗传算法的编码、遗传算子等重要参数，具体说 明了这些参数在进行遗传操作过程中所起到的作用；结合遗传操作过程，阐述了 遗传算法的基本步骤和流程。根据本文研究需要，选择最佳的优化方法，为后文 模型的计算做铺垫。- 31 -哈尔滨工业大学工学硕士学位论文第 3 章 北大仓啤酒有限公司的物流业务描述北大仓啤酒有限公司从物流的组织结构来看，经历了以下四阶段：1999 年 以前，营销网络以批发部形式存在，物流主要从仓库到批发网点，没有形成对零 售客户的直接送货上门；第二阶段以“城乡一体、统一运行”为标志，实现了啤 酒由销售部配送到户；第三阶段以“电话订货、网上配货、现代物流”为标志， 实现了商流物流分离、物流集中配送等，物流的专业化逐步体现，信息化建设水 平逐步提高；第四阶段以“效率”“服务”为核心，实现从形式到功能的转变， 、 也是当前和今后一段时期的努力方向，标志着建设现代物流体系的正式启动。3.1 北大仓啤酒有限公司物流的构成北大仓啤酒有限公司的物流从原材料采购―企业加工―销售营业部―客户 是一个完整的供应链，物流配送是供应链的一部分，从构成上看，是涉及到企业 从啤酒成品到客户的物流过程。3.1.1 物流的三个主要环节目前北大仓啤酒有限公司物流体系从流向来看，主要包括三个部分：物流采 购、物流加工、物流配送。物流采供主要是从北大仓啤酒有限公司购进各种种类 的啤酒，运输啤酒入库的过程；物流加工主要是仓储、分拣、包装等加工过程； 物流配送主要是按照订单，将指定的啤酒配送到每一个客户的过程。物流采购 物流加工 物流配送 客户北大仓啤酒有限公司销售营业部图 3―1 北大仓啤酒有限公司物流总流程 Chart 3 - 1 Bei da cang beer limited company logistics thetotal logistics3.1.2 物流的成本构成目前， 国内外比较有代表性的对物流成本管理的概念有：按照我国的标准物 流术语，物流成本（Logistics cost）是指物流活动中所消耗的物化劳动和和活劳 动的货币表现。 日本物流学界认为，物流成本是公司内部所有花费在物流上的费 用总和；欧美学者则认为，物流成本主要由三部分组成：一是库存费用、二是运 输费用、三是管理费用。 参考以上定义， 我认为北大仓啤酒有限公司物流的成本主要由物流采购、物 流加工、物流配送构成的库存费用、运输费用和管理费用的总和。通过近几年的 物流成本统计情况来看，物流的三个主要环节费用如下图。其中物流采购，与运 输距离有关；采用集中仓储、分拣、配送模式，成本构成相对稳定，占成本比例 最大的是物流配送环节，也是研究的主要目标。- 32 -哈尔滨工业大学工学硕士学位论文70 60 50 40 30 20 10 0 物流采购 物流加工 物流配送 物流采购 物流加工 物流配送图 3―2
年平均物流成本构成 Chart 3 C 2 2002 - 2006 annual means logistics the cost constitution 根据有关数据统计，2006 年酒类产品的配送费用在 0.10~0.15 元／瓶之间， 包括两部分。一部分为仓储费用，包括仓储费用（租金或折旧） ，配送箱、托盘、 叉（拖）车费用，包装费，配送中心办公杂费，配送中心水电费，分拣设备折旧 费，仓库分拣人员工资等，约占总费用的 37％。另一部分为运费，包括来货运 输费、装卸费、商品损耗费、配送车油料费、配送车维修费、配送车营运费、配 送车使用税、配送车保险费、配送车年审费用、配送车养路费、配送车路桥费、 配送车折旧费及配送装卸人员工资等，约占总费用的 63％。优化配送网络以后， 一般运费会节省 20％左右。3.2 北大仓啤酒有限公司物流的流程张绪昌教授曾定义物流流程的概念：物流流程是通过物流活动来实现的，创 造物质时间和空间效应的经济活动过程。 物流的流程大致可以分为三个环节：物流采购、物流加工、物流配送。3.2.1 物流采购酒类供应链是围绕企业，通过对信息流、物流、资金流的控制，从采购酒类 产品，入库，最后由物流部通过销售网络把产品送到客户手中的将制造商、零售 商、 直到最终用户连成一个整体的功能链结构模式。物流采供就是将制造商生产 的产品到入库的物流过程。需求分析 数据汇总 车辆调度客户需求销售营业部物流部物流采购图 3―3 物流采购流程 Chart 3 - 3 thing logistics the purchase flow- 33 -哈尔滨工业大学工学硕士学位论文3.2.2 物流加工物流加工环节有仓储保管、装卸搬运、包装等功能。流程如下：产品入库仓储保管分拣系统包装打印清单、装车送货图 3―4 物流加工主要流程 Chart 3 - 4 thing logistics the processing main flow 1、仓储保管