基于密度聚类构建物流配送问题的毁灭移除算法

发布时间：2018-11-27 18:25

【摘要】：研究多车型大规模物流配送问题,针对企业配送门店规模大且聚集的特点,在自适应大规模邻域搜索(ALNS)框架下提出一种新的邻域映射方式:基于密度聚类的毁灭移除算法。ALNS包含毁灭与重建两个阶段,通过不断对当前解进行破坏和重建得到更好解。在毁灭阶段,随机选择一条路线进行密度聚类得到簇集合,然后按簇对路线上的门店进行移除;重建阶段随机选择贪婪插入法或Regret-2插入法将移除的门店插入到合适的路线上得到新配送方案。通过国际基准测试案例验证了所提算法的有效性,与已有算法对比,基于密度聚类的毁灭移除算法的ALNS算法求解结果比案例已知最优解平均误差更低,求解质量更优;应用于实际场景中,该算法能在有限时间内求得较好的配送方案。
[Abstract]:This paper studies the problem of large-scale logistics distribution of multi-vehicle models, aiming at the characteristics of large scale and agglomeration of enterprise distribution stores. In the framework of adaptive large-scale neighborhood search (ALNS), a new neighborhood mapping method is proposed: the destruction removal algorithm based on density clustering. ALNS consists of two stages: destruction and reconstruction. A better solution is obtained by continuously destroying and rebuilding the current solution. In the destruction stage, a random route is chosen to cluster the clusters, and then the stores on the route are removed according to the cluster. In the reconstruction phase, the greedy insertion method or the Regret-2 insertion method are randomly selected to insert the removed stores into the appropriate route to obtain the new distribution scheme. The effectiveness of the proposed algorithm is verified by an international benchmark case. Compared with the existing algorithms, the ALNS algorithm based on density clustering has lower average error and better solution quality than the known optimal solution. The algorithm can get a better distribution scheme in a limited time.
【作者单位】： 中南大学信息科学与工程学院;
【基金】：国家科技支撑计划项目(2015BAH05F02)~~
【分类号】：TP301.6

【参考文献】

相关期刊论文 前3条

1 郝建彬;;“新零售”的曙光[J];互联网经济;2016年11期

2 谭颖;胡瑞飞;殷国富;;多密度阈值的DBSCAN改进算法[J];计算机应用;2008年03期

3 曹二保;赖明勇;聂凯;刘长石;;大规模物流配送车辆调度问题研究[J];湖南大学学报(自然科学版);2007年12期

【共引文献】

相关期刊论文 前10条

1 朱紫玉;;新零售模式下零售企业的战略转型研究[J];北方经贸;2017年08期

2 阳旺;何国超;吴雁;;基于密度聚类构建物流配送问题的毁灭移除算法[J];计算机应用;2017年08期

3 魏成;;“纯电商”如何面对新零售[J];时代金融;2017年09期

4 李敏;张桂珠;;密度峰值优化初始中心的K-means算法[J];计算机应用与软件;2017年03期

5 周海松;黄德才;;密度自适应的半监督谱聚类算法[J];计算机科学;2016年12期

6 何兆怡;;一种基于模拟退火算法的密度聚类方法[J];福建电脑;2016年04期

7 陈盖凯;武涛;李海瑞;王丹;;基于变结构的应急航材调度策略[J];火力与指挥控制;2016年02期

8 蒋礼青;张明新;郑金龙;戴娇;尚赵伟;;快速搜索与发现密度峰值聚类算法的优化研究[J];计算机应用研究;2016年11期

9 肖柯伟;陈志;赵博;;物流配送车辆调度问题智能算法研究进展[J];物流科技;2015年12期

10 吴华;卢君妥;柳长安;杨国田;李志成;;巡检图像的改进密度空间聚类分割算法[J];华中科技大学学报(自然科学版);2015年S1期

【二级参考文献】

相关期刊论文 前4条

1 章兢,周泉;基于免疫克隆算法的物流配送车辆路径优化研究[J];湖南大学学报(自然科学版);2004年05期

2 蔡颖琨,谢昆青,马修军;屏蔽了输入参数敏感性的DBSCAN改进算法[J];北京大学学报(自然科学版);2004年03期

3 马帅,王腾蛟,唐世渭,杨冬青,高军;一种基于参考点和密度的快速聚类算法[J];软件学报;2003年06期

4 周水庚,周傲英,曹晶;基于数据分区的DBSCAN算法[J];计算机研究与发展;2000年10期

【相似文献】

相关期刊论文 前10条

1 黄林鹏;;基于归纳的算法设计思想[J];程序员;2006年04期

2 刘波;;“算法设计与分析”教学探讨[J];高等理科教育;2007年04期

3 肖小克;陈莉;;《算法设计与分析》实践教学探讨[J];福建电脑;2009年10期

4 穆瑞辉;;计算机算法设计研究与思考[J];数字技术与应用;2012年12期

5 潘博;;构建“算法设计与分析”趣味课堂[J];科教文汇(下旬刊);2013年06期

6 王希常,杨志强;一类考场编排算法的设计[J];山东师范大学学报(自然科学版);2002年04期

7 龙腾芳,高金文;“分而治之”方法在算法设计中的应用[J];渤海大学学报(自然科学版);2004年01期

8 吕国英;;《算法设计与分析》教材建设的实施[J];计算机教育;2007年19期

9 徐子珊;;“算法设计与分析”教学中理论与技术的平衡[J];计算机教育;2008年10期

10 郑红;邵志清;符海波;;“算法设计与分析”课程教学改革初探[J];计算机教育;2008年14期

相关会议论文 前10条

1 徐子珊;;《算法设计与分析》课程中的工程教育[A];2005年全国理论计算机科学学术年会论文集[C];2005年

2 舒辉;柳清峰;杜祝平;周蓓;;实践教学模式在本科专业课程教学中的应用[A];中国电子教育学会高教分会2010年论文集[C];2010年

3 彭小宏;阳东升;刘忠;;基于聚类算法的组织协作网设计[A];2006中国控制与决策学术年会论文集[C];2006年

4 罗长政;李熙莹;王镇波;罗东华;;一种大流量交叉路口的背景提取与更新算法[A];第十五届全国图象图形学学术会议论文集[C];2010年

5 杨利;李霖;昌月楼;阳国贵;;对称位向量及启发式并行散列连接算法[A];数据库研究与进展95——第十三届全国数据库学术会议论文集[C];1995年

6 张晋;;嵌入式电脑鼠运行算法的研究[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

7 杨子良;陶宏才;;一种基于向量运算的频繁项集快速挖掘算法[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年

8 刘升;王行愚;牛玉刚;;一种求解复杂约束优化问题的文化算法设计[A];第十七届全国过路控制会议论文集[C];2006年

9 高文超;孙宇清;韩冬雪;;一种改进的素数寻找问题的算法设计与实现[A];中国电子学会第十六届信息论学术年会论文集[C];2009年

10 朱秋云;张琪;姬朝阳;陈亮;魏苑琦;朱绍文;;一种基于概念格的关联规则对半查找算法设计[A];2005年中国智能自动化会议论文集[C];2005年

相关重要报纸文章 前1条

1 ;算法设计的策略[N];电脑报;2003年

相关博士学位论文 前10条

1 史亚;多核学习算法与应用研究[D];西安电子科技大学;2015年

2 谷伟哲;齐次光滑算法及其应用[D];天津大学;2010年

3 张常淳;基于MapReduce的大数据连接算法的设计与优化[D];中国科学技术大学;2014年

4 郭崇慧;地区中长期发展规划若干定量模型、算法及应用研究[D];大连理工大学;2002年

5 蒋蔚;粒子滤波改进算法研究与应用[D];哈尔滨工业大学;2010年

6 孙贺;算法设计中的若干前沿问题[D];复旦大学;2009年

7 陈宁涛;基于二分技术的高效算法设计及其应用[D];华中科技大学;2006年

8 娄晓文;无符号基因组切割再粘贴重组问题的算法研究[D];山东大学;2010年

9 孙群英;密集环境中有源RFID防冲撞算法的研究及应用[D];浙江大学;2011年

10 刘兴林;中文词汇知识获取算法和语义计算研究及应用[D];华南理工大学;2012年

相关硕士学位论文 前10条

1 李欣园;基于选择偏好的组合聚类算法研究与实现[D];内蒙古大学;2015年

2 楼磊磊;医疗保险数据异常行为检测算法和系统[D];浙江大学;2015年

3 赵晨阳;基于蚁群算法的高阶图匹配方法研究[D];西安电子科技大学;2014年

4 程X;基于云平台的聚类算法并行化研究[D];南京邮电大学;2015年

5 杨勋;复杂场景下单目标视觉跟踪算法研究[D];合肥工业大学;2014年

6 曹甜;RFID系统中高效信息收集算法研究[D];太原理工大学;2016年

7 潘宇婷;复杂网络重叠社区挖掘算法研究与设计[D];江苏大学;2016年

8 王子瑜;基于动态的唇形身份识别算法的研究[D];吉林大学;2016年

9 魏天姣;基于图像稀疏表示与非线性压缩感知的相位恢复算法研究[D];燕山大学;2016年

10 韩盼;基于类和区域特征的协同显著性检测算法[D];燕山大学;2016年

，

本文编号：2361671