副题名

外文题名

论文作者

戴树贵着

导师

潘荫荣指导

学科专业

系统分析与集成

学位级别

博士论文

学位授予单位

华东师範大学

学位授予时间

2007

关键字

物流 物资管理 经济规划 数学模型 遗传算法

馆藏号

F252

馆藏目录

2009F25217

物流是企业的“第三利润源”，是国民经济发展的动脉和基础产业。加强信息技术在物流系统中的套用，可以有效地降低物流费用。物流系统的模型和算法是计算机科学和物流科学当前研究的热点。 物流费用主要包括物流中心的选址费用、物流配送费用和库存费用。本文以降低物流费用为目标，对物流系统的选址、配送和库存三个环节进行了研究。 本文的主要工作和主要创新点包括以下几个部分： 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．研究了有保质期商品随机性的库存问题。该问题一般通过建立最佳化模型和计算机仿真两种方法来研究。目前用建立最佳化模型来研究该问题的成果通常假定订货提前期为确定值和/或需求量与需求时间间隔为常数或特定函式，而在实际的库存系统中，这些量都是随机的；而用计算机仿真方法来研究该问题的成果一般没有考虑销售商为消化库存而採取的促销行为。 本文以最大化销售商的利润为指标，基于离散事件仿真原理，建立了有保质期商品的订货-库存-销售仿真模型。模型同时考虑了生产商的订货批量价格折扣和随机的订货提前期、销售商的降低促销、顾客的随机的需求量和随机的需求间隔时间及顾客对降价商品的增加需求量等诸多因素。此外，通过对该模型的扩展，还建立了多种相关商品的库存系统仿真模型。通过数据实验，分析了两个模型的有效性。 本文的仿真模型很好地解决了有保质期商品的库存问题，为销售商选择最佳的订货-库存-销售策略提供了有效的工具。