基于聚类的大规模即时配送问题研究
发布时间：2020-10-26 03:16
车辆路径问题(VRP)是企业开展物流活动过程中的重要问题之一,随着配送时效在物流经济活动中发挥着重要的作用和客户时间意识增强,快速响应、安全可靠的车辆路径问题研究显得愈加重要,特别是随着电商的蓬勃发展和推动,区域内大规模客户订单的即时配送问题出现频率越来越高,并逐渐成为城市配送研究的重要方向,因此该类问题的研究变得更有必要。但现有的理论应用到该问题存在难点:精确算法或者启发式算法的求解时间随着研究问题的规模增大呈指数式增加,显然求解时间太长,并不适用,本文采用两阶段算法,先聚类后排程,降低问题求解规模的同时使用高效的算法实现客户订单配送,不仅可以提供更快捷、准时、有效的配送服务,而且有助于企业节约成本,合理利用车辆和人力资源,因此该问题研究具有现实意义和必要性。本文在查阅国内外VRP和聚类理论研究文献后,结合即时配送行业背景和H公司存在的问题,将两阶段启发式算法引入到大规模即时配送问题研究中:第一阶段,订单聚类处理,分别用贪婪聚类(最近邻算法)和最大最小距离聚类对区域内的所有订单划分,降低问题规模、计算量,提高求解效率,同时对两种聚类方式从类内聚合度CP、类间间隔性SP等两个聚类有效指标上进行分析,初步评定聚类效果好坏;第二阶段,前一阶段聚类处理将车辆问题转化成TSP问题,为了量化控制时间对客户满意度的影响,论文引入时间惩罚系数,进而建立带时间窗的车辆调度模型(TSPSTW),使用全局搜索能力较强的遗传算法求解模型,以动态交叉、变异算子替代传统静态算子,使得求解更快、结果更优,从而为快速、有效地优化时间窗问题创造条件。客户订单聚类和配送均通过MATLAB仿真实现,以算例C401为例,仿真运行算例TSPSTW模型,得到订单配送计划表,包括配送路线、总成本、总里程、订单时刻表等,依此得到所有订单的配送计划。从运行效率上,只需7-8分钟完成501个订单聚类和配送,进一步验证了两阶段算法的高效性,最后结合聚类指标和配送经济指标对比两种聚类方案的优劣,为H公司选择适合的调度计划提供参考。
【学位单位】：东华大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：F252
【部分图文】：
1 绪论1.1 研究背景及意义随着经济发展和消费结构快速升级，人们的时间意识愈加敏感，近年来“懒人经济”和“生活快节奏”很大程度上催生了即时配送行业的发展，传统意义上的，今天订货，隔天到货的配送模式已经逐渐满足不了当下客户对时间苛刻的要求。根据中国最近 3 年即时配送行业客户规模的数据(图 1-1)，用户规模去年高达 3.24 亿，比 2016 年增长 40.3%，自从 2014 年起，以每年超过 30%的增长率激增，这反应了我国用户对即时配送的需求持续走高；从即时订单比例来看，电商行业代表企业京东2016年四个季度的即时订单比例(图1-2)以超过20%的增长率呈现稳健增长的态势，这种良好的趋势会在未来很长一段时间维持，可以预见该行业具有很好的发展前景。
图 1-3 A 门店 7 月下单高峰期水平曲线(2) 难点二：大规模 VRP 问题对算法提出了极高的要求。传统 VRP 算法引到大规模订单闪送问题存在理论应用难点。拿一般的 VRP 问题求解，难以在效时间内得到有效解，精确算法只能有效求解小规模车辆路径问题，但当订单模达到上百个时，求解时间呈指数式递增，显然实用性不大；启发式算法虽能理大规模复杂的车辆问题，但直接求解，也花费时间长，违背客户时间要求。(3) 难点三：两阶段算法求解大规模车辆问题有着独特的优势和很强的实用，但第一阶段聚类方法的好坏严重影响有效解。国内专家引用划分法 K-means法居多，主要因为该算法对于大规模数据型数据有独特的优势，运算速度快，输入数据顺序不敏感，但是该算法有明显的局限性，对聚类数的选取大多依赖为经验，缺乏科学的理论依据。2.2 论文思路结合即时配送行业背景，配送时效在物流活动中愈加重要，快速响应、安全靠的车辆路径问题研究逐渐成为城市配送领域的热点问题。但是，传统 VRP
法求解模型；选择时，按照群体个体适应度大小排列保护最优个体并使用轮盘赌的选择；值得注意的是，使用动态交叉、变异算子取代静态算子，并通过实验验证，发现收敛更快、结果更优。(3) 指标分析以类内聚合度、类间间隔性作为聚类指标选取指导原则，分别对比了两种聚类结果的CP、SP指标，初步判断聚类效果好坏，然后结合配送成本、资源利用率等经济指标判断两种方案的优劣情况，最后为H公司提供合理的调度方案。(4) 利用 Matlab 软件求解，并进行分析。通过聚类和路径仿真实验，获取运行时间数据，以贪婪聚类为例，平均每类客户订单排程只需 17 秒左右，从而说明该算法在求解大规模即时配送问题具有高效性，基本满足大规模订单闪送问题。1.3.2 论文组织结构
【参考文献】
本文编号：2856405
【学位单位】：东华大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：F252
【部分图文】：
1 绪论1.1 研究背景及意义随着经济发展和消费结构快速升级，人们的时间意识愈加敏感，近年来“懒人经济”和“生活快节奏”很大程度上催生了即时配送行业的发展，传统意义上的，今天订货，隔天到货的配送模式已经逐渐满足不了当下客户对时间苛刻的要求。根据中国最近 3 年即时配送行业客户规模的数据(图 1-1)，用户规模去年高达 3.24 亿，比 2016 年增长 40.3%，自从 2014 年起，以每年超过 30%的增长率激增，这反应了我国用户对即时配送的需求持续走高；从即时订单比例来看，电商行业代表企业京东2016年四个季度的即时订单比例(图1-2)以超过20%的增长率呈现稳健增长的态势，这种良好的趋势会在未来很长一段时间维持，可以预见该行业具有很好的发展前景。
图 1-3 A 门店 7 月下单高峰期水平曲线(2) 难点二：大规模 VRP 问题对算法提出了极高的要求。传统 VRP 算法引到大规模订单闪送问题存在理论应用难点。拿一般的 VRP 问题求解，难以在效时间内得到有效解，精确算法只能有效求解小规模车辆路径问题，但当订单模达到上百个时，求解时间呈指数式递增，显然实用性不大；启发式算法虽能理大规模复杂的车辆问题，但直接求解，也花费时间长，违背客户时间要求。(3) 难点三：两阶段算法求解大规模车辆问题有着独特的优势和很强的实用，但第一阶段聚类方法的好坏严重影响有效解。国内专家引用划分法 K-means法居多，主要因为该算法对于大规模数据型数据有独特的优势，运算速度快，输入数据顺序不敏感，但是该算法有明显的局限性，对聚类数的选取大多依赖为经验，缺乏科学的理论依据。2.2 论文思路结合即时配送行业背景，配送时效在物流活动中愈加重要，快速响应、安全靠的车辆路径问题研究逐渐成为城市配送领域的热点问题。但是，传统 VRP
法求解模型；选择时，按照群体个体适应度大小排列保护最优个体并使用轮盘赌的选择；值得注意的是，使用动态交叉、变异算子取代静态算子，并通过实验验证，发现收敛更快、结果更优。(3) 指标分析以类内聚合度、类间间隔性作为聚类指标选取指导原则，分别对比了两种聚类结果的CP、SP指标，初步判断聚类效果好坏，然后结合配送成本、资源利用率等经济指标判断两种方案的优劣情况，最后为H公司提供合理的调度方案。(4) 利用 Matlab 软件求解，并进行分析。通过聚类和路径仿真实验，获取运行时间数据，以贪婪聚类为例，平均每类客户订单排程只需 17 秒左右，从而说明该算法在求解大规模即时配送问题具有高效性，基本满足大规模订单闪送问题。1.3.2 论文组织结构
【参考文献】
相关期刊论文 前7条
1 孙小军;;求解带时间窗车辆路径问题的混合智能算法[J];大连理工大学学报;2015年02期
2 谭峻强;杨萍;何晓彤;谭振江;;用动态规划法解决最优路径问题的相关研究[J];信息系统工程;2015年01期
3 李波;邱红艳;;基于双层模糊聚类的多车场车辆路径遗传算法[J];计算机工程与应用;2014年05期
4 洪联系;;带时间窗口动态车辆路径规划模型及其求解算法[J];计算机工程与应用;2012年04期
5 葛金辉;;有时间窗的车辆路径问题及改进禁忌搜索算法[J];吉林大学学报(理学版);2011年01期
6 傅成红;符卓;;一种毗邻信息改进的车辆路径问题禁忌搜索算法[J];系统工程;2010年05期
7 朱锦新;;基于空间聚类和蚁群算法的车辆路径问题的研究[J];盐城工学院学报(自然科学版);2009年04期
本文编号：2856405
本文链接：https://www.wllwen.com/jingjilunwen/jingjiguanlilunwen/2856405.html
