管理论文免疫算法在应急物流配送车辆优化调度中的应用.doc

免疫算法在应急物流配送车辆优化调度中的应用 免疫算法在应急物流配送车辆优化调度中的应用是小柯论文网通过网络搜集，并由本站工作人员整理后发布的，免疫算法在应急物流配送车辆优化调度中的应用是篇质量较高的学术论文，供本站访问者学习和学术交流参考之用，不可用于其他商业目的，免疫算法在应急物流配送车辆优化调度中的应用的论文版权归原作者所有，因网络整理，有些文章作者不详，敬请谅解，如需转摘，请注明出处小柯论文网，如果此论文无法满足您的论文要求，您可以申请本站帮您代写论文，以下是正文。 摘要：应急物流是处理各类突发事件对物资、人员的需求进行紧急保障的一种特殊物流活动。文章根据应急物流的特点，将免疫算法用于应急物流车辆调度研究中，同时通过算例，证明用免疫算法优化车辆行驶路径的有效性和可行性。关键词：应急物流；免疫算法；车辆优化调度中图分类号：f224文献标识码：a文章编号：1002-3100(2008)11-0024-04abstract: emergency logistics is a kind of special logistical activity solving all kinds of unexpected events which are demanded seriously to the goods and manpower. according to the characteristics of the emergency logistics, this text applies the immune algorithm in the emergency logistics distribution vrp. at the same time, an example is given to prove the efficiency and usability in the vehicle rooting problem.key words: emergency logistics; immune algorithm; vehicle rooting problem0引言在我国，自然灾害、事故灾难、公共卫生和社会安全等突发事件时有发生。而在各种突发事件后，救援人员的及时到达，人员财产的快速转移和救援物资的运送发放等对于提高应急响应能力、解决救援事件、降低生命财产损失具有重要的意义。其中，应急物流的vrp（vehicle rooting problem）优化问题是确保工作顺利进行的关键。vrp是在一系列已知装货点和卸货点组成的运输网络中，组织适当的行车线路, 使车辆运输的物资有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最少、使用车辆数量尽量少等）。应急物流vrp与普通物流vrp决策目标之间有明显的差异。由于应急物流的特殊性，人们往往更注重时间方面的及时性和最终的救灾效果，而忽视了这一物流过程中的物流经济性。对于应急物流vrp优化问题的研究可以在满足应急物流时间要求（时间窗限制）的前提下，更合理的安排车辆的调度运行，最大程度的节省物流成本。人工免疫系统是从生物免疫系统中获得灵感，并与计算机技术相结合以解决工程实际问题的计算机模型。本文将免疫算法应用于应急物流配送的车辆优化调度中，以便在考虑时间作为第一关键因素的前提下，最大程度地节省物流成本，从而找到一条最优路径。1问题描述及模型建立为了简化问题的复杂度并兼顾应急物流配送的特点，便于模型的建立，特作以下假设：（1）物资储备中心与各受灾地点、各受灾地点之间的运输距离作为已知量。（2）每个受灾地点对救灾物资的需求是可以提前运达，但是不能晚于规定时间送到。即问题为有单边的硬时间窗的车辆调度优化问题。（3）所有的受灾地点的需求，在物资数量方面和运输时间方面都能够得到满足；同时单个需求节点的需求量小于单车最大载重量。（4）在受灾时期，路况、交通条件的变化采用路况系数，分正常和高峰两种情况。目标函数（1）表示产生的费用最小，约束式（2）表示l型车k服务需求点i时的需求量不允许超过其车辆的载重量；式（3）表示每个需求点只允许访问一次；式（4）、（5）表示任何一个受灾地区需求节点只有1台车停靠卸货；式（6）表示i,j为k所服务客户，且i为j前趋；式（7）表示排除的车辆数等于返回的车辆数；式（8）表示救灾物资送到各个需求节点的时间必须在时间窗范围内；式（9）表示l型车行驶经过i,j的时间，并考虑路况；式（10）表示l型车从i行驶至j时的费用。2免疫算法免疫算法是借鉴了免疫系统学习性、适应性以及记忆机制等特点而发展起来的一种优化组合方法，在使用免疫算法解决优化问题时，各个步骤都与免疫系统有对应关系。如抗原对应要解决问题数据输入（如目标、约束）；抗体对应问题的解；亲和力对应解的评估等。具体对应关系如表1所示。在用免疫算法求解优化问题时，待求的问题对应为抗原，候选解即是抗体，抗体中的每一位称为一个基因，应用亲和力来描述抗体和抗原之间的匹配程度，用排斥力来描述两个抗体之间的相似程度。2.1抗体表示抗体采用自然数编码。用0表示物资储备中心，用1，2，8表示各节点。例如n=8时，抗体为01230456078，抗体编码的表示可理解为：车辆从车场0出发，经过：子线路1：物资储备中心0?邛节点1?邛节点2?邛节点3?邛物资储备中心0；子线路2：物资储备中心0?邛节点4?邛节点5?邛节点6?邛物资储备中心0；子线路3：物资储备中心0?邛节点7?邛节点8?邛物资储备中心；抗体通常是在解空间中用随机的方法产生的，初始化抗体群规模即抗体群中抗体的个数，根据经验，一般取网络节点个数的2倍作为抗体群规模。2.2亲和力函数本文采用目标函数值作为免疫算法的抗原。抗体与抗原之间的亲和力反应了抗体与抗原之间的匹配程度，也可以说是通过亲和力来描述抗体的优化程度。本文取目标函数的倒数，即：式中，fv为目标函数。抗体越优化，抗体v对应解的目标函数值就越小，它的亲和力就越大；称抗体群中亲和最大的抗体为本带抗体群的最优抗体。2.3排斥力函数抗体a与b之间排斥力的计算函数定义为：抗体a和b之间不相同的基因数量越大，它们的排斥力就越大。2.4免疫算子（1）对换算子对于vrp问题来说，父代个体p1和p2分别采用浮点数编码方案：p1：012304560780 p2: 025604780130采用基于路径表示的顺序交叉ox操作，两代父代个体交叉时，通过选择父代个体1的一部分，保存父代个体2中城市编码的相对顺序生成子个体。通过该方法生成子代个体：o1：027804560130 o2：035604780120（2）重组算子对交叉后的群体，以某一概率改变某一个或者一些基因位上的基因值为其他的等位基因，变异本身是一种局部随机搜索，与选择算子结合在一起，保证了免疫算法的有效性，使免疫算法具有局部的随机搜索能力，同时使得免疫算法保持种群的多样性，以防止出现未成熟收敛。本文采用单点基因位换位算子和多对基因位换位算子的操作。2.5浓度调节适应度浓度调节适应度是在亲和力的基础上引入浓度调节机制，抗体b的浓度调节适应度函数gb定义如下：gb其他参考文献baker, sheridan. the practical stylist. 6th ed. new york: harper & row, 1985.flesch, rudolf. the art of plain talk. new york: harper & brothers, 1946.gowers, ernest. the complete plain words. london: penguin books, 1987.snell-hornby, mary. translation studies: an integrated approach. amsterdam: john benjamins, 1987.hu, zhuanglin. 胡壮麟, 语言学教程 m. 北京: 北京大学出版社, 2006.jespersen, otto. the philosophy of grammar. london: routledge, 1951.leech, geoffrey, and jan svartvik. a communicative grammar of english. london: longman, 1974.li, qingxue, and peng jianwu. 李庆学、彭建武, 英汉翻译理论与技巧 m. 北京: 北京航空航天大学出版社, 2009.lian, shuneng. 连淑能, 英汉对比研究 m. 北京: 高等教育出版社, 1993.ma, huijuan, and miao ju. 马会娟、苗菊, 当代西方翻译理论选读 m. 北京: 外语教学与研究出版社, 2009.newmark, peter. approaches to translation. london: pergmon p, 1981.quirk, randolph, et al. a grammar of contemporary english. london: longman, 1973.wang, li. 王力, 中国语法理论 m. 济南: 山东教育出版社, 1984.xu, jianping. 许建平, 英汉互译实践与技巧 m. 北京: 清华大学出版社, 2003.yan, qiga