启发式算法在第三方物流企业配送优化中的应用

VIP免费
3.0 赵德峰 2024-11-19 4 4 972.77KB 90 页 15积分
侵权投诉
目 录
中文摘要
ABSTRACT
第一章 绪 论.................................................................................................................1
§1.1课题研究的背景及意义.................................................................................1
§1.2课题所解决的问题在国内外的研究现状.....................................................1
§1.2.1国内外第三方物流配送中心选址问题的研究现状..........................1
§1.2.2国内外第三方物流配送路径优化的研究现状..................................3
§1.3课题研究的内容及框架.................................................................................6
第二章 第三方物流.......................................................................................................8
§2.1第三方物流简介.............................................................................................8
§2.2第三方物流的基本概念.................................................................................8
§2.2.1第三方物流的概念..............................................................................8
§2.2.2第三方物流的内涵..............................................................................9
§2.2.3第三方物流与物流一体化................................................................12
§2.2.4第三方物流的经济性........................................................................12
§2.3第三方物流配送管理...................................................................................16
§2.3.1物流配送的发展................................................................................16
§2.3.2运输与配送的关系............................................................................17
§2.3.3第三方物流配送管理........................................................................18
§2.4第三方物流配送线路优化的意义及原则...................................................24
§2.5第三方物流配送线路优化的方法...............................................................25
§2.5.1车辆路径问题简介............................................................................25
§2.5.2车辆路径问题的基本问题................................................................26
§2.5.3主要方法技术....................................................................................28
§2.6第三方物流配送中心概述...........................................................................31
§2.6.1配送中心概论....................................................................................31
§2.6.2配送中心概念....................................................................................31
§2.6.3配送中心在现代物流中的地位........................................................33
§2.6.4配送中心的分类................................................................................34
§2.6.5配送中心的功能................................................................................37
§2.6.6配送中心的选址................................................................................39
第三章 启发式算法.....................................................................................................47
§3.1传统启发式算法...........................................................................................48
§3.2现代启发式算法...........................................................................................48
§3.2.1各种算法简介....................................................................................49
§3.2.2现代启发式算法的特点....................................................................53
§3.2.3蚂蚁算法与遗传算法、模拟退火算法的比较................................54
§3.3蚂蚁算法.......................................................................................................55
§3.3.1算法概述............................................................................................55
§3.3.2蚂蚁系统——蚂蚁算法的原型........................................................57
§3.3.3 改进的蚁群优化算法........................................................................65
§3.3.4 蚂蚁算法的特征和优缺点................................................................66
§3.3.5蚂蚁算法的发展现状及应用领域....................................................69
第四章 案例分析.........................................................................................................71
§4.1上海复来物流有限公司简介.......................................................................71
§4.2复来物流十大特色.......................................................................................71
§4.3复来物流业务流程.......................................................................................72
§4.4复来物流服务网络.......................................................................................74
§4.5复来物流报价...............................................................................................75
§4.6复来物流有限公司配送中心选址...............................................................77
§4.7 复来物流有限公司配送路径优化...............................................................79
§4.8 复来物流有限公司配送优化示意图...........................................................80
第五章 结束语.............................................................................................................82
参考文献.........................................................................................................................85
在读期间公开发表的论文和承担科研项目及取得成果.............................................89
致 谢.............................................................................................................................90
第一章 绪 论
1
第一章 绪 论
§1.1课题研究的背景及意义
企业的物流成本是在物流过程中企业为了提供有关的物流服务，所要占用和
耗费一定的活劳动和物化劳动中必要劳动的价值的货币表现，是物流服务价值的
重要组成部分。在整个物流成本中，其中配送成本占了一半左右，因此，通过合
理组织配送降低物流总成本具有很大的潜力。
随着现代物流概念的提出，对物流配送也提出了更高的要求，就是在传统配
送的基础上，更合理地选择配送方式和配送路线，做到运力省、速度快、费用低，
更大程度上实现物流配送优化。物流优化在很大程度上也依赖于配送优化。
如今，科学技术正处于多学科相互交叉和渗透的时代。特别是，计算机科学
与技术的迅速发展，根本上改变了人类的生产与生活。同时，随着人类生存空间
的扩大以及认识与改造世界范围的拓宽，人们对科学技术提出了新的和更高的要
求。其中对高效的优化技术和智能计算的要求日益迫切。
启发式源自英文单词 heuristics，启发式算法意为通过对过去经验的归纳推理
以及实验分析来解决问题的方法，即借助于某种直观推断或试探的方法，它要求
分析人员从与研究问题有关而较基本的模型及算法中寻求其间的联系，从中得到
启发，去发现适于解决该问题的思路和途径。启发式算法求解问题是通过迭代过
程实现的，理论上并不收敛于最优解，因此，它强调的是得到满意解。启发式算
法能够比较快地得到满意解，这对解决 NP-难题来说有着不可估量的作用。
本论文正是应用启发式算法来解决第三方物流企业中配送优化的问题，从而
降低企业的配送成本、实现企业配送优化，进而达到降低物流成本、提高企业效
益的目的。
§1.2课题所解决的问题在国内外的研究现状
§1.2.1国内外第三方物流配送中心选址问题的研究现状
配送中心是现代物流的重要组成部分，其上游是制造商，下游是用户，它在
整个物流系统中起着承上启下的作用。选择合理的配送中心地址可以有效地节约
费用，促进生产和消费两种流量的协调与配合，保证物流系统的高效和平衡发展。
配送中心合理选址是一个重要而复杂的问题，配送中心选址问题已经有很多
模型和方法，但仍需要得到科学的模型化、数量化方法的支持。最常见的选址问
题是在一系列备选地点中确定拟建设的配送中心的最佳位置,目标是使各项费用
启发式算法在第三方物流企业配送优化中的应用
2
合计最小。
目前，国内关于配送中心选址的研究方法大致可以分为定性和定量两大类。
定性的方法主要是层次分析法和模糊综合评价法相结合，对各个方案进行指标评
价，找出各备选方案的排序； 定量的方法主要包括重心法、运输规划法、Cluster 法
与CFL(Capacitated Facility Location)、鲍姆尔-沃尔夫(Baumol-Wolfe)法、0-1 混合
整数规划法、双层规划法等。这些方法各自基于一定的假设前提给出了具体的算
法，具有不同的适用条件，但这些假设前提和实际情况总有出入。总体来看，上
述各种模型都存在以下问题：
1.模型常常假设需求量集中于某一点，而实际上需求来自分散于广阔区域内
的多个消费点；
2.运输费用通常假设运价随运输距离成比例增加，然而，大多数运价是由不
随运输距离变化的固定部分和随运输距离变化的可变部分组成的；
3.模型中配送中心与其他物流网络节点之间的运输路线通常假定为两点之间
直线，实际上这样的情况很少。
总之，各种模型应用于实际问题时尽管会表现出一定的缺陷，但都具有一定
的使用价值。虽然各种模型的适用范围和解法不同，但是任何模型都可以在一定
条件下得出有价值的结果。在实际应用时，要尽量利用模型的优势，同时尽量避
免或改善其局限性使所选择的配送中心地址最为合理，投入运营后的总费用最小。
除了上述数学模型以外，现在又发展出计算机辅助决策方法和模糊聚类分析
等方法。计算机辅助决策方法主要有两种：计算机仿真法、探视法。模糊聚类分
析方法是应用模糊数学中的有关概念与方法引进聚类分析，该方法考虑很多的实
际因素，对客户进行分类，通过建立模糊相似关系来寻找特征值。
国外学者在配送中心选址方面的研究也已经取得了许多成果。九个基本的选
址模型，包括简单选址模型、有容量限制的选址模型、需求变动的选址模型、动
态选址模型等，其目标函数几乎都是使运输费用和固定选址投资费用最小。但这
些常见的选址模型都假定从配送中心到需求点(客户点) 的配送是放射线状的，即
从配送中心出发的运输车辆每次访问一个客户后，就返回到该配送中心。配送过
程中的运输费用表示成这种直接返回的距离的函数。实际上，有些不满载的配送
任务从配送中心到客户点的配送方式都是采用巡回线路的，即若干个需求量较小
的客户在一条配送线路上。因此，传统的费用表示忽视了对车辆巡回线路的考虑，
有可能造成对分销成本估计不准确。在设施相对于客户的位置、货物的配送、运
输货物车辆路线的安排之间存在相互依赖关系，对于某一物流配送中心服务于各
个客户的费用不再是独立的，而是车辆路线安排的结果。
第一章 绪 论
3
在国内，还未见到在这方面有影响的研究成果，而国外学者在对这类设施选
址问题进行了研究，这些研究都是将设施选址和运输路线安排结合起来同时考虑
的，其目标是找出最优的供应点的位置，同时还要使供应点到各个需求点的运输
成本最小。这些模型在得出了最优配送路线的同时，也合理计算了每个客户的运
输费用。求解这类问题一般采用启发式算法：先选址后安排线路、先安排线路后
选址、基于聚类的算法等。但这类问题中或者只考虑客户的需求量在某一个配送
中心满足的情况，即每个客户只能有唯一的一个配送中心服务，或者只考虑在总
费用最小情况下的配送方案，而不考虑客户的选择行为。事实上，某个客户的需
求不但可以由多个物流配送中心共同满足，而且由每个配送中心配送的货物量取
决于客户的选择行为，同时这种选择行为在很大程度上具有较高的随机性。另外，
有些学者也采用了双层规划方法研究选址模型,但此方面的有关成果不多。
综上所述，目前在配送中心选址方面，由于实际情况的复杂性使得难以建立
一个普遍适用的数学模型，所建立的数学模型大都具有 NP-Hard 的性质。对于这
些数学模型的求解方法主要有：分枝定界法，迭代法，运输规划法，启发式算法
以及遗传算法等。本课题打算在这些研究的基础上尝试用启发式算法来求问题的
最优解。
§1.2.2国内外第三方物流配送路径优化的研究现状
物流配送是现代化物流管理中的一个重要环节。它是指按顾客订货的要求，
在配送中心进行分拣、配货后，将配好的货物在规定的时间内送交顾客的活动。
它是物流中一个重要的直接与消费者相连的环节。配送的时间、速度及质量直接
关系到第三方物流企业的速度、质量和效益。进行配送系统优化，主要就是物流
配送路径的优化选择问题，即通过制定合理的配送路径，快速而经济地将货物送
达用户手中。配送路径的选择是否合理，对加快配送速度、提高服务质量、降低
配送成本及增加经济效益都有较大影响。因此，对制定车辆调配计划和配送路线
计划就显得非常重要了。然而物流配送车辆路径优化问题(Vehicle Routing Problem)
是一个 NP 难题，随着顾客数量的增加，可选的配送路径方案数量将以指数速度急
剧增长。
近二十年来,无论在国内外，VRP问题都是一个非常活跃的研究领域。目前用
于解决该问题的现代数学方法主要分为以下几类：
1.精确优化方法
包括制定下界及相关分枝定界算法、K度中心树及相关算法、动态规划、集合
划分和列产生、三索引车辆流方式、二索引车辆流方式等。但精确算法的计算复
启发式算法在第三方物流企业配送优化中的应用
4
杂度很高， 随着运输系统的复杂化和对调度的多目标要求，获得整个系统的精确
优化解越来越困难，花费的时间和费用太大，因此精确解法不能应用于规模较大
的物流配送车路由问题的求解，仅用于运输调度的局部优化问题。
2.启发式方法(Heuristics)
指通过经验法则来求取运输过程满意解的数学方法。启发式方法能同时满足
详细描绘问题和求解的需要，较精确优化方法更为简单实用，缺点是难于知道什
么时候好的启发式解己经被求得。启发式方法中最具代表性的就是由Clarck 和
Wright 提出的节约法(SavingMethod)。许多成功的车辆调度软件就是根据该方法
或其改进方法开发的。西南交大的李军针对有时间窗的车辆路线安排问题提出了
一种利用节约法的启发式算法。典型启发式算法中还包括由Lin 和Kemighan 提出
的，并由Christofidests 和Gilbert laPorte等人所推广的分支交换探索法，该算法始
终保持解的可行性而又力图向最优目标前进。在每一步，都改变一个可行解而减
少总费用，直到这个过程继续到不再可能使费用减少为止。Gillet 和Milled 提出
的扫描法(SweepMethod)先把节点或弧的需求进行分组或划群,然后对每一组按旅
行商问题(TSP)求解，设计出一条经济的路线。此外，常用的启发式方法还有2-阶
段法、不完全树搜索算法等。各种启发式方法的主要区别在于收敛的速度和程度
不同。
3.模拟方法(Simulation)
利用数学公式、逻辑表达式、图表、坐标图形等抽象概念表示实际运输系统
内部状态和输入输出的关系，以便通过计算机对模型进行实验，通过实验取得改
善运输系统或设计新运输系统所需信息。虽然模拟方法在模型构造、程序调试、
数据整理方面工作量大，但由于运输系统结构复杂，不确定情形多，模拟方法仍
以其描述和求解问题的能力优势成为复杂运输调度系统建模的主要方法。
4.交互式优化法
这是一种通用方法，它把人的知识和经验结合到问题的求解过程中去。其思
想是：有经验的决策者应具有确定和修改参数的能力，并且根据知识直感把主观
的估计加到优化模型中去。采用这种方法求解车辆路径问题的早期雏形是由
Krolak，Fe1tS，Marble 和Nelsonl 等人提出的。
精确优化方法是以往广泛采用的方法，另外三种方法则代表了最近研究的方
向。尤其是启发式方法，作为一种逐次逼近的算法，虽然不一定得到最优解，但
是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题，因此，
现己成为解决配送问题的重要方法。与传统的启发式方法相比，近年来一些新的
启发式方法(元启发式方法)，通过对启发式规则和搜索方式的改进，在求解多节
摘要：

目录中文摘要ABSTRACT第一章绪论.................................................................................................................1§1.1课题研究的背景及意义.................................................................................1§1.2课题所解决的问题在国内外的研究现状.....................................................

展开>> 收起<<
启发式算法在第三方物流企业配送优化中的应用.pdf

共90页,预览9页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：赵德峰 分类：高等教育资料 价格：15积分 属性：90 页 大小：972.77KB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 90
评分 收藏
分享
立即下载 VIP免费下载
客服
关注