基于LRP模型及其优化算法的物流配送系统的研究与应用

VIP免费
3.0 陈辉 2024-11-19 5 4 4.4MB 66 页 15积分
侵权投诉
摘 要
随着经济的不断发展，现代物流作为一种先进的组织方式和管理技术，被公
认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，
也是企业降低流通费用、缩短流通时间、整合企业价值链、加快企业资金周转的
重要途径。对物流配送中的各个环节，诸如物流设施定位、运输车辆的调度和配
送路线的选择等问题进行有效管理和决策分析，有助于物流配送企业有效的利用
现有资源，降低消耗。
本文结合物流配送系统的实际特征，对物流配送系统的优化问题进行了研究，
建立了更加符合物流系统实际特征的定位—运输路线安排问题（Location-Routing
Problem, LRP）模型。由于 LRP 优化问题非常复杂，因此本文将整个问题分解为
定 位 — 配 给 问 题 （ Location-Allocation Problem, LA ）和车辆路线安排问题
（Vehicle-Routing Problem, VRP）进行讨论。
首先，本文对定位—配给问题进行了研究,运用改进的 K均值聚类算法对 LA
问题进行求解。由于基本的 K均值聚类算法随机地选取初始质心，因此算法的性
能受初始质心的影响很大。针对此问题本文提出一种最小相似度的选择方法，经
仿真实验表明该算法具有良好的求解效果。
接着，本文对车辆路线安排问题进行了研究，建立了基于客户满意度的 VRP
模型，并运用改进的遗传算法对 VRP 问题进行求解。通过仿真实验，研究分析了
遗传算法的遗传算子和控制参数对算法求解结果质量以及算法收敛速度的影响，
实验结果表明经本文改进的遗传算法相对于标准遗传算法具有更好的全局搜索能
力和更快的收敛速度。
关键词：物流配送系统 LRP 模型 遗传算法 聚类算法
ABSTRACT
With the economy continues to develop, as an advanced organization method and
management technology, modern logistics has been recognized as “the third profit
source” for an enterprise. It integrates the value chain of enterprises, reinforces the
control capability and accelerates fund turnover by the reduction of circulation cost and
time. It would contribute effectively to the distribution conduction if provides sound
management and decision-making analysis for the logistics distribution procedure, such
as logistic facility location, vehicle dispatch, delivery route selection. Therefore, it leads
to the effective use of available source, labor cost reduction and efficiency improvement
in the logistics enterprises.
This paper studies the optimization problem of the logistics and establishes the model
of vehicle routing problem which can reflect the actual characteristics of the logistics
distribution system after the research of the actual characteristics of the logistics
distribution system. Because the LRP optimization problem is very complex, this article
breaks down the whole problem for the location allocation problem and vehicle routing
problem.
This paper starts with the further study of the location allocation problem, and applies
improved K-means clustering algorithm to LA problem. As the impacted of randomly
selected initial value to the performance of K-means clustering algorithm is negative.
This paper proposes a new algorithm to select initial value. This experiment shows that
the improved algorithm has better performance.
Then this paper studies the vehicle routing problem, establishes the model of vehicle
routing problem based on customer satisfaction and applies improved genetic algorithm
to VRP problem. By making stimulation experiment, this project studies and analyzes
the setting of parameters affects the capability and results. This experiment shows that
the improved genetic algorithm has better capability of global search and faster speed of
convergence.
Keywords: Logistics, LRP, Genetic Algorithm, Clustering Algorithm
目录
中文摘要
ABSTRACT
第一章 绪论 .....................................................................................................................1
§1.1 论文研究的背景及意义 ....................................................................................... 1
§1.2 国内外研究的现状 ............................................................................................... 2
§1.3 论文研究的内容 ................................................................................................... 3
§1.4 论文的组织结构 ................................................................................................... 3
第二章 物流配送系统的研究 .........................................................................................4
§2.1 物流配送系统概述 .............................................................................................. 4
§2.1.1 物流配送系统的目标 ....................................................................................5
§2.1.2 物流配送面临的问题 ....................................................................................5
§2.2 物流配送信息系统 .............................................................................................. 6
§2.2.1 物流配送信息系统的框架 ............................................................................6
§2.2.2 物流配送信息系统的功能模块 ....................................................................7
§2.3 物流配送系统的优化问题 .................................................................................. 8
§2.3.1 配送中心的选址问题 ..................................................................................8
§2.3.2 车辆路线安排问题 ......................................................................................9
§2.4 LRP 模型及其算法的概述 ................................................................................ 9
§2.4.1 定位—配送路线安排问题（LRP）的概述 .............................................. 9
§2.4.2 LRP 求解算法概述 ................................................................................... 12
§2.5 本章小结 ............................................................................................................ 14
第三章 定位—配给问题的研究 ...................................................................................15
§3.1 定位—配给问题的描述 .................................................................................... 15
§3.1.1 定位—配给问题的描述 ............................................................................15
§3.1.2 问题中参数的定义 ....................................................................................15
§3.2 聚类分析综述 .................................................................................................... 16
§3.2.1 簇的分类 ....................................................................................................16
§3.2.2 聚类算法的分类 ........................................................................................18
§3.2.3 聚类分析中的准则函数 ............................................................................18
§3.2.4 K 均值聚类算法 ........................................................................................19
§3.3 求解 LA 问题的算法设计 .................................................................................19
§3.3.1 聚类分析阶段 ............................................................................................20
§3.3.2 配送中心定位阶段 ....................................................................................21
§3.4 实例求解与算法实现 ........................................................................................ 24
§3.4.1 问题的提出 ................................................................................................24
§3.4.2 数据的预处理 ............................................................................................25
§3.4.3 算法核心代码的说明与实现 ....................................................................27
§3.4.4 结果分析 ....................................................................................................31
§3.5 本章小结 ............................................................................................................ 33
第四章 车辆路线安排问题的研究 ........................................................................... 34
§4.1 多目标车辆路线安排问题的描述及其数学模型 ............................................. 34
§4.1.1 基于时间窗的 VRP 模型 ..........................................................................34
§4.1.2 基于客户满意度的 VRP 模型 ..................................................................36
§4.1.3 车辆路线安排问题的数学模型 ................................................................37
§4.2 遗传算法综述 ..................................................................................................... 38
§4.2.1 编码与解码 ................................................................................................38
§4.2.2 适应度函数 ................................................................................................39
§4.2.3 遗传算子 ....................................................................................................40
§4.2.4 控制参数 ....................................................................................................42
§4.2.5 自适应机制 ................................................................................................43
§4.2.6 遗传算法的终止条件 ................................................................................44
§4.3 在车辆路线安排问题中遗传算法的设计与改进 ............................................ 45
§4.3.1 编码策略 ....................................................................................................45
§4.3.2 选择算子设计 ............................................................................................46
§4.3.3 交叉算子设计 ............................................................................................47
§4.3.4 变异算子设计 ............................................................................................49
§4.3.5 自适应机制的改进 ....................................................................................50
§4.3.6 遗传算法的流程 ........................................................................................51
§4.4 实验分析与算法实现 ........................................................................................ 52
§4.4.1 问题的提出 ................................................................................................52
§4.4.2 算法核心代码的设计与实现 ....................................................................53
§4.4.3 结果分析 ....................................................................................................55
§4.5 本章小结 ............................................................................................................ 57
第五章 总结与展望 .......................................................................................................58
§5.1 总结 .................................................................................................................... 58
§5.2 展望 .................................................................................................................... 59
参考文献 .........................................................................................................................60
在读期间公开发表的论文和承担科研项目及取得成果.................................................... 62
致 谢 ...............................................................................................................................63
第一章 绪论
1
第一章 绪论
§1.1 论文研究的背景及意义
自上世纪 80 年代以来，科学技术水平不断提高，专业化分工的进一步深化。
在欧美一些发达国家开始了一场对物流各种功能和要素的整合，物流活动由此开
始走向信息化、网络化、系统化、专业化。90 年代以后，各种专业化的物流配送
企业在欧美发达国家大量涌现并呈现出快速的发展趋势，在原来第三方物流（3PL）
的基础上形成了专门提供一整套供应链解决方案的第四方物流供应商（4PL）
[1]
。
由此形成了物流产业，并成为发达国家服务业中的一个重要组成部分。与此同时，
高度信息化、现代化的物流系统可以为电子商务提供了便捷的市场通道，真正实
现电子商务的快捷、高效，促进了整个社会经济的快速、健康发展。在物流系统
当中，运输、配送是居其核心地位，是物流配送合理化的关键所在。
我国物流整体规划的现状令人堪忧，其中“中外物流的差异不是在硬件上，而
是需求的差异，要改变这种状况，需要一段时期的市场培育”。首先政府要起到引
导作用，中国企业有跟国情相关的中国企业的需求，政府可借鉴的是国外在政策、
规划制定前的“调查分析”。目前缺少的是“定量分析"，即中国企业在物流方面
的需求到底是什么?中国企业的物流成本到底有多少?没有量化的数据可供参考，
也就难于制订出详细的、可操作性的政策规划。随着信息化在日常生活中的不断
渗透，物流也不仅仅是直观意义上的物资的存储和运输，而是更为合理的供应链
环节上源与下游沟通和合作的“信息枢纽"。当前物流配送系统的发展已不能适应
电子商务发展，主要表现为缺乏一个高效率的物流配送系统对货物的转移提供低
成本、适时、适量的转移服务，致使配送成本过高、客户响应速度过慢。由此引
起了各个领域专家学者对物流配送有关问题的研究热潮。随着改革开放的进程向
纵深发展，集成化物流管理的概念已经被越来越多的企业所接受，建立协调的、
有效的配送系统、提高分销效率成为了企业生存与发展的必由之路。因此，对物
流的研究具有非比寻常的意义。
在物流配送系统中，配送中心的选址问题和车辆路线安排问题一直是该领域研
究的热点问题，各国学者构建了很多这类问题的优化模型，并给出了相应的求解
算法。在这其中，定位—运输路线安排问题（Location-Routing Problem，LRP）最
符合物流配送系统的实际特征，因此对它的研究具有实际意义。
基于 LRP 模型及其优化算法的物流配送系统的研究与应用
2
§1.2 国内外研究的现状
20世纪70年代末期，“物流"概念从日本引入我国，但由于当时计划经济环境的
限制，在理解和应用上来说，物流概念基本局限在物资的储存、调拨和相应的运
输上，没有形成具有自己经济运行特点的物流概念。由于缺乏物流活动组织化和
经济运行的环境，在物流概念引进的近20年时间里，我国物流的发展相当缓慢。
随着经济发展和改革开放的深入，各种理解逐渐趋于一致，认为物流是生产、流
通和消费领域物质资料从供应者到用户间的物理性流动，主要是创造时间价值和
场所价值有时也创造一定加工价值的活动。从这些不同的表述上可以得出一个共
同的概念“物流是指物品从供应地向接收地的实体流动过程。近年来配送活动有
日渐增长的趋势，如何配合路径规划的相关方法，减少不必要的车次以及人员的
浪费，以及有效降低因为路线重复或选线错误所造成的成本浪费，是亟待解决的
问题。
近些年来，国外许多学者对物流配送系统的优化问题进行了研究，构建了许多
解决实际问题的优化模型，并给出了相应的求解算法。关于定位—运输路线安排
问题的研究开始于20世纪70年代，Watson-Gandy和Dohrn将运输车辆多点停留特性
与定位—运输网络结合起来开展了研究。但由于LRP问题的难度很大，对该类问题
的研究进展缓慢。20世纪90年代以来，国外的学者对物流配送系统优化中的车辆
路线安排问题以及定位—配给问题的研究取得了一定的进展。此外，国外从实用
化角度开展的研究也比较多，研究者将模型和算法方面取得的进展应用于很多具
体问题。也由此诞生了一些为企业车辆路径提供服务的专业化公司，开发了各具
特色的车辆路径软件，比较著名的有：IBM的VSPX系统，美孚的HPCAD系统，另
外还有日本富士通的VSS系统等
[2]
。
我国对物流配送系统的优化问题研究起步较晚，根据所能掌握的资料，国内最
先对VRP进行系统研究的是郭耀煌教授，他及其学生从1989年起对多车场、多车
型等类型问题进行了研究。西南交大的李军针对有时间窗的车辆路线安排问题提
出了一种利用节约法的启发式算法；浙江大学蔡延光等人运用模拟退火算法和遗
传算法求解多重车辆调度问题，并将其集成为智能算法库，作为设计智能运输调
度系统的依据；东北大学的张潜等人提出一种先用优先级综合聚类分析法将客户
分类，再用带有控制开关系统的改进遗传算法求解多目标VRP的优化方法；张乐
诚等人研究了随机时间约束的车辆路径问题：长沙理工大学陈曦等人将变异粒子
群算法运用于车辆路径优化问题；唐小明等人研究了多指标的车辆模糊优化调度：
西南交通大学的张建勇等人近年来对模糊车辆路径问题做了大量的研究
[3]
。
摘要：

摘要随着经济的不断发展，现代物流作为一种先进的组织方式和管理技术，被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低流通费用、缩短流通时间、整合企业价值链、加快企业资金周转的重要途径。对物流配送中的各个环节，诸如物流设施定位、运输车辆的调度和配送路线的选择等问题进行有效管理和决策分析，有助于物流配送企业有效的利用现有资源，降低消耗。本文结合物流配送系统的实际特征，对物流配送系统的优化问题进行了研究，建立了更加符合物流系统实际特征的定位—运输路线安排问题（Location-RoutingProblem,LRP）模型。由于LRP优化问题非常复杂，因此本文将整个问...

展开>> 收起<<
基于LRP模型及其优化算法的物流配送系统的研究与应用.pdf

共66页,预览7页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：66 页 大小：4.4MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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