物流系统模型和算法研究

物流系统模型和算法研究

【摘要】：物流是企业的“第三利润源”，是国民经济发展的动脉和基础产业。加强信息技术在物流系统中的应用，可以有效地降低物流费用。物流系统的模型和算法是计算机科学和物流科学当前研究的热点。物流费用主要包括物流中心的选址费用、物流配送费用和库存费用。本文以降低物流费用为目标，对物流系统的选址、配送和库存三个环节进行了研究。本文的主要工作和主要创新点包括以下几个部分：1．研究了一类特殊的物流中心选址问题——基于交通网络的单应急中心选址问题。应急中心选址不仅要考虑选址费用(建设费用和运输费用) ，更重要的是要考虑中心的覆盖范围和由中心到各需求点的应急时间限制。研究者通常使用重心法、层次分析法或者求解选址模型来解决应急中心选址问题。重心法无法评估应急中心到需求点的应急时间限制以及其它影响应急中心建设的因素；单纯使用层次分析法，需要考查所有候选点，且必须考查候选点到需求点的费用和时间等因素，因此工作量很大；通过建立选址模型并求解的方法，不是对影响选址的因素缺乏全面的考虑，就是模型复杂难以求解。本文以降低应急中心选址费用为目标，结合重心法、层次分析法和本文提出的求解K 短路径算法，提出了一个求解单应急中心选址问题的三阶段算法TSA ，并通过实例阐述了TSA 算法的求解过程。TSA 算法中，

第一阶段使用重心法来缩小选址范围。第二阶段中，本文提出了一个时间复杂度小，且易于编程实现的求解K 短路径算法KSP ，并使用

KSP 算法，排除不满足时间紧迫性限制的候选地点。第三阶段使用层次分析法，根据选址费用和其它影响选址的因素，对剩下的少数候选地点进行分析，确定最终的选址地点。TSA 算法过程简单，计算量小，既考虑了影响选址的诸多因素，又考虑了选址费用、覆盖范围和应急时间限制。是一个解决单一应急中心选址问题的有效算法。2．研究了物流配送方面的三个问题：(1)基于顶点坐标的车辆有容量限制的单配送中心车辆路径安排问题：该问题以最小化车辆行驶距离为目标。通常采用的研究方法包括精确算法、启发式算法和元启发式算法。由于精确算法计算量大，而一般启发式算法结果通常不够精确，因此，目前大多使用元启发式算法研究该问题，其中遗传算法的研究成果占了相当大的比重。但是，遗传算法存在的“早熟”问题没有得到很好的解决。本文设计了一个求解该问题的混合遗传算法SHGA 。SHGA 算法针对简单遗传算法因随机选择交叉个体而易于“早熟”的问题，提出了远亲交叉策略，从而很好地解决了这一问题。为了使算法有较快的收敛速度，SHGA 算法采用了优良个体保留策略，设计了优良个体数函数；利用顶点间的位置关系，设计了个体优化优化策略，对个体进行优化。SHGA 既很好地解决了遗传算法的“早熟”问题，又具有较快的收敛速度。(2)基于交通网络的车辆有容量限制的单配送中心车辆路径安排问题：物流配送通常总是在交通网络中进行的，且配送费用并不能完全由车辆行驶距离来衡量。目前基于交通网络的车辆路径安排的研究成果并不多，并且都是以车辆行驶距离来评价配送费用。本文建立了基于网络的单配送中心车辆路径安排问题的最小配送费用

模型，模型考虑了物流配送的固定费用、空载费用和增加费用，设计了一个求解模型的混合单亲遗传算法HPGA 。该算法中提出了基于最短路径的优化策略，通过在两个顶点之间插入基于配送费用的最短路径上的顶点，并在其它位置删除这些顶点，对个体进行优化，从而提高了算法的收敛速度。(3)车辆有容量限制的多配送中心车辆路径安排问题：目前这方面的研究成果并不多，并且通常是把多配送中心车辆路径安排问题转化为单配送中心车辆路径安排问题来解决，求解结果不够精确。蚁群算法具有较强的鲁棒性、易于与其它方法结合等优点，已成功应用于求解单配送中心车辆路径安排问题。但是，目前未见有使用蚁群算法求解多配送中心车辆路径安排问题的研究成果报导。本文提出了一个求解多配送中心车辆路径安排问题的混合蚁群算法HACA 。HACA 算法中，设计了蚂蚁转移策略和可行解构造算法，从而成功地将蚁群算法应用于多配送中心车辆路径安排问题的求解。此外，为了提高算法的求解性能，引入K 邻域结构来限制蚂蚁的转移目标，使用2_Opt优化策略来优化蚂蚁路径和可行解，并设计了信息素更新策略。HACA 算法有效地解决了蚁群算法在多配送中心车辆路径安排问题中的应用问题，并且具有很好的求解性能。本文还分别通过数据实验验证了以上三个算法的有效性，并讨论了参数设置对这些算法性能的影响。3．研究了有保质期商品随机性的库存问题。该问题一般通过建立优化模型和计算机仿真两种方法来研究。目前用建立优化模型来研究该问题的成果通常假定订货提前期为确定值和／或需求量与需求时间间隔为常数或特定函数，而在实际的库存系统

中，这些量都是随机的；而用计算机仿真方法来研究该问题的成果一般没有考虑销售商为消化库存而采取的促销行为。本文以最大化销售商的利润为指标，基于离散事件仿真原理，建立了有保质期商品的订货-库存-销售仿真模型。模型同时考虑了生产商的订货批量价格折扣和随机的订货提前期、销售商的降低促销、顾客的随机的需求量和随机的需求间隔时间及顾客对降价商品的增加需求量等诸多因素。此外，通过对该模型的扩展，还建立了多种相关商品的库存系统仿真模型。通过数据实验，分析了两个模型的有效性。本文的仿真模型很好地解决了有保质期商品的库存问题，为销售商选择最佳的订货-库存-销售策略提供了有效的工具。【关键词】：物流选址问题车辆路径安排问题库存系统仿真遗传算法蚁群算法离散事件系统

【学位授予单位】：华东师范大学

【学位级别】：博士

【学位授予年份】：2007

【分类号】：O22

【目录】：摘要6-8ABSTRACT8-15第1章绪论15-251.1选题背景和研究意义15-161.2国内外研究现状16-191.3本文的主要研究内容和主要创新点19-211.4本文的组织结构21-25第2章基于网络的单应急中心选址问题的TSA 算法25-482.1本章的研究内容262.2国内外研究现状26-282.3重心法和层次分析法简介28-302.4基于网络的单应急中心选址模型30-312.5基于网络的单应急中心选址算法TSA31-412.6数据实验41-462.7本章小结46-48第3章车辆有容量限

制的单配送中心车辆路径安排问题混合遗传算法48-703.1车辆路径安排问题简介48-503.2单配送中心车辆路径安排问题算法的研究现状50-523.3遗传算法简介52-543.4求解车辆有容量限制的SDVRP 的混合遗传算法SHGA54-613.5数据实验61-673.6本章小结67-70第4章基于交通网络的单配送中心最小配送费用模型及其混合单亲遗传算法70-824.1基于交通网络的VRP 的研究现状70-714.2基于交通网络的单配送中心最小配送费用模型71-724.3带优化处理的混合单亲遗传算法HPGA72-764.4数据实验76-814.5本章小结81-82第5章求解多配送中心车辆路径安排问题的混合蚁群算法82-1005.1MDVRP 模型82-835.2MDVRP 算法的研究现状83-855.3蚁群算法和2_Opt优化策略简介85-885.4使用经典蚁群算法求解MDVRP 时必须解决的问题88-895.5求解MDVRP 的混合蚁群算法HACA89-925.6数据实验及HACA 算法性能分析92-985.7本章小结98-100第6章有保质期的商品的库存系统仿真模型100-1246.1库存控制问题简介100-1016.2本章研究的问题及其特点101-1026.3有保质期/易腐商品的库存控制问题的研究现状102-1046.4离散事件系统仿真简介104-1066.5单一有保质期商品的订货-库存-销售仿真模型106-1176.6多种相关商品的库存仿真模型117-1226.7本章小结122-124第7章总结与展望124-1267.1总结124-1257.2展望125-126致谢126-127攻读博士学位期间发表的论文及参加的科研项目127-128附录128-129 本论文购买请联系页眉网站。