学位论文 > 优秀研究生学位论文题录展示

设施定位和车辆路线问题模型及其启发式算法研究

作　者: 胡大伟
导　师: 郭晓汾
学　校: 长安大学
专　业: 载运工具运用工程
关键词: 定位车辆路线问题物流系统优化禁忌搜索算法模拟退火算法遗传算法启发式组合算法库存定位路线问题
分类号: U116.2
类　型: 博士论文
年　份: 2008年
下　载: 550次
引　用: 1次
阅　读: 论文下载

内容摘要

随着物质需求的多样性和不规则性以及贸易呈全球化趋势的发展,作为“第三利润源泉”的物流,其作用和地位显得比任何时候都更为重要,对经济活动的影响也日益明显。目前,许多发达国家和地区已形成了比较成熟的物流管理理念、先进的物流技术和高效的物流运营系统。我国在进入21世纪之后,也逐渐加快了现代物流的发展,以提高生产企业在国际上的竞争能力。为此企业管理者都希望能协调物流系统中的各个环节,以最低的价格、最好的服务来满足顾客的需要,所以物流决策显得极为重要。在传统的物流决策模型中,定位—配给问题(location allocation problems, LAP)和车辆运输路线问题(vehicle routing problem,VRP)是最值得关注的两个方面。但是在LAP模型中仅考虑设施(工厂、库存点、分销中心等)的定位与货物配给之间的相互关系,却忽视了对车辆巡回行程路线的考虑,这就有可能导致分销成本的增长;而在VRP模型中,虽然考虑了车辆在各个客户点间巡回访问的特性,使提高运输效率成为可能,但却没有分析设施的选址问题,这将会使得整个物流系统成本仍有一定的下降空间。因此,本文运用系统分析的思想和方法,研究了物流系统中的设施定位配给和车辆路线组合优化问题——定位车辆路线问题(location routing problem,LRP)。由于LRP及其扩展模型属于NP-hard问题,在具有一定规模节点数情况下目前仍难以求得最优解。因此对LRP模型进行系统化优化求解研究具有重要的理论价值,其理论意义则在于针对NP-hard模型大规模数值计算的解法突破和创新,同时也是发展基于电子商务的城市物流配送理论的重要理论基础,这将为日后面对巨大交易量的电子商务环境下开发自动物流配送调度系统软件具有非常重要的现实意义。本文在分析了物流系统中选址、运输以及库存的互相制约关系基础上,从提高物流系统整体效率为出发点,站在理论研究层面,针对物流集成化数学模型及其启发式解法进行了系统研究,即从系统化的角度分析和研究了复杂物流环境下的LRP优化问题,论文从问题的界定、模型的建立、模型的检验、启发式算法求解途径、组合优化求解思路、算法实现及数据分析等多个方面对LRP问题进行了深入、具体的研究分析,得到了如下研究成果:(1)论文系统性地研究了LRP数学模型,对定位-配给问题、车辆路线问题、定位-车辆路线问题、带库存的定位-车辆路线问题典型数学模型及其构成进行了科学描述,通过小规模测试数据采用LINGO软件对LRP数学模型给予了标定,为今后人们在此方面的进一步研究奠定了模型基础;(2)针对LRP数学模型属性特点,分别采用禁忌搜索算法(Tabu search algorithm,TS)、模拟退火算法(Simulated annealing algorithm,SA)对LRP数学模型进行了优化求解,编制了相应算法程序软件,并采用具有一定规模的仿真测试数据测算了所提出算法求解LRP模型的有效性,同时经过大量数值模拟计算找出了其算法求解LRP模型的优良参数搭配。通过与有关文献对比,证明本文提出的求解思路对于LRP模型求解更具有优良特性;(3)提出了遗传-模拟退火组合算法和遗传-禁忌搜索组合算法求解LRP模型的思路,并进行了相应的算法研究,通过编制计算软件和具有一定规模的数据测试,实现了组合启发式算法求解LRP模型的设想,这对于发展和完善组合优化理论亦具有重要的科学理论价值。(4)分析了在库存管理策略下,库存控制策略对设施选址和路线优化问题的影响,在此基础上建立了更为复杂的定位-路线-库存组合优化模型(Combined Location Routing and Inventory Problems,CLRIP),并设计了求解该模型的一种两阶段启发式算法,通过小规模测试数据测算证明带库存的定位路线组合优化模型比定位-路线问题和库存控制模型独立优化的情形更能有效降低物流系统成本,并为进一步深入研究该问题的解法提供了基本思路。(5)提供了LRP模型从8个节点至200个节点不同规模情形下的系列测试数据源,为今后开展LRP研究者提供了算法科学对比途径,同时为建立LRP模型测试数据库做出了开创性基础工作。

全文目录

摘要  4-6
ABSTRACT  6-12
第一章绪论  12-19
  1.1 选题的背景和研究意义  12-14
    1.1.1 选题的背景  12-13
    1.1.2 研究意义  13-14
  1.2 LRP 问题概述  14-15
  1.3 LRP 问题国内外研究现状  15-17
  1.4 本文的主要研究内容  17-19
第二章 LRP 模型及其算法分析  19-39
  2.1 组合优化问题及其求解方法概述  19-27
    2.1.1 组合优化问题  19
    2.1.2 组合优化问题的计算复杂性  19-21
    2.1.3 组合优化问题的复杂性  21-23
    2.1.4 组合优化问题的求解方法  23-24
    2.1.5 启发式算法  24-27
  2.2 LRP 数学模型及其分类  27-34
    2.2.1 LRP 有关数学模型  27-33
    2.2.2 LRP 模型分类  33-34
  2.3 LRP 问题精确算法分析  34-35
  2.4 LRP 问题启发式算法分析  35-38
  2.5 本章小结  38-39
第三章 LRP 模型的禁忌搜索算法  39-59
  3.1 禁忌搜索算法概述  39-42
    3.1.1 禁忌对象的选取  40
    3.1.2 禁忌长度的确定  40-41
    3.1.3 候选集的确定  41
    3.1.4 特赦规则  41-42
    3.1.5 终止规则  42
  3.2 LRP 模型禁忌搜索算法设计  42-50
    3.2.1 LRP 数学模型检验  42-45
    3.2.2 禁忌搜索算法设计  45-50
  3.3 LRP 问题的禁忌搜索算法的实现  50-55
  3.4 算法策略和运行参数对禁忌搜索算法性能的影响分析  55-57
    3.4.1 迭代次数  55-56
    3.4.2 禁忌长度  56
    3.4.3 优化解出现的频次  56-57
  3.5 本章小结  57-59
第四章 LRP 模型的模拟退火算法  59-79
  4.1 模拟退火算法概述  59-62
    4.1.1 模拟退火算法概述  59-60
    4.1.2 模拟退火算法参数设计  60-62
  4.2 LRP 模型模拟退火算法设计  62-67
    4.2.1 定位-配给问题的启发式算法  63-67
    4.2.2 车辆路线问题的启发式算法  67
  4.3 LRP 问题的模拟退火算法的实现  67-78
    4.3.1 求解LAP 问题的算法实现  67-68
    4.3.2 求解VRP 问题的算法实现  68-70
    4.3.3 模拟仿真测试分析  70-78
  4.4 本章小结  78-79
第五章 LRP 模型的启发式组合算法  79-103
  5.1 遗传算法概述  79-82
  5.2 遗传算法有关技术问题  82-86
  5.3 遗传和模拟退火组合算法求解 LRP 模型  86-96
    5.3.1 遗传和模拟退火组合算法设计思路  86-87
    5.3.2 基于混合遗传模拟退火算法求解VRP 的具体实现  87-92
    5.3.3 遗传模拟退火组合算法仿真测试及分析  92-96
  5.4 遗传和禁忌搜索组合算法求解两级 LRP 模型  96-102
    5.4.1 数学模型的进一步分析  96-98
    5.4.2 遗传算法和禁忌搜索组合算法设计  98-100
    5.4.3 遗传和禁忌搜索组合算法实例计算  100-102
  5.5 本章小结  102-103
第六章考虑库存时LRP模型及其启发式算法  103-115
  6.1 问题描述  103-105
  6.2 模型基本假设及参数定义  105-106
    6.2.1 决策变量  105-106
    6.2.2 参数定义  106
  6.3 数学模型的建立  106-108
    6.3.1 系统费用分析  106-107
    6.3.2 数学模型的建立  107-108
  6.4 启发式算法设计  108-113
    6.4.1 求解思路  108
    6.4.2 库存控制决策变量的求法  108-109
    6.4.3 算法设计  109-113
  6.5 实例计算和结果分析  113-114
  6.6 本章小结  114-115
结论  115-119
参考文献  119-130
附录  130-150
攻读博士学位期间发表的学术论文、出版专著及完成的科研成果  150-153
致谢  153

设施定位和车辆路线问题模型及其启发式算法研究

内容摘要

全文目录

相似论文