求解需求可拆分车辆路径问题的聚类算法

doi:10.11772/j.issn.1001-9081.2016.11.3141

计算机应用 ›› 2016, Vol. 36 ›› Issue (11): 3141-3145.DOI: 10.11772/j.issn.1001-9081.2016.11.3141

求解需求可拆分车辆路径问题的聚类算法

向婷, 潘大志

西华师范大学数学与信息学院, 四川南充 637009

收稿日期:2016-05-25 修回日期:2016-06-25 出版日期:2016-11-10 发布日期:2016-11-12
通讯作者: 潘大志
作者简介:向婷(1991-),女,四川巴中人,硕士研究生,主要研究方向:智能计算、数值计算;潘大志(1974-),男,四川三台人,教授,博士,主要研究方向:智能计算、算法设计。
基金资助:
四川省教育厅自然科学基金资助项目（14ZA0127）；西华师范大学博士启动基金资助项目（12B022）。

Clustering algorithm for split delivery vehicle routing problem

XIANG Ting, PAN Dazhi

College of Mathematics and Information, China West Normal University, Nanchong Sichuan 637009, China

Received:2016-05-25 Revised:2016-06-25 Online:2016-11-10 Published:2016-11-12
Supported by:
This work is partially supported by the Natural Science Foundation of Sichuan Provincial Education Department (14ZA0127), the Doctor Startup Fund of China West Normal University (122B022).

摘要/Abstract

摘要： 针对需求可拆分车辆路径问题（SDVRP），提出一种先分组后路径的聚类算法。该算法考虑车辆载重的均衡性和可行解的特征，优先安排载重大于等于车辆限载的客户；然后结合客户间的距离和载重，设定一个拆分阈值限定车辆载重范围，按照就近原则对客户进行聚类分组，当组内客户载重未达到车辆载重最小值而加入新客户后超出限载时，对新加入客户进行拆分和调整，最终完成对所有客户的分组；最后采用蚁群优化算法对各组内客户进行线路规划。实验结果表明，所提算法在求解需求可拆分车辆路径问题时，具有更高的稳定性，得到的结果更优。

关键词: 需求可拆分车辆路径问题, 聚类算法, 蚁群算法, 启发式算法

Abstract: A clustering algorithm which arranges paths after grouping was proposed to solve Split Delivery Vehicle Routing Problem (SDVRP). Considering the balance of vehicle load and characteristics of feasible solution, first, the customers which load were greater or equal to the vehicle load limit were arranged in advance. Then combined with the distance between customers and load, a split threshold was set to limit the load of vehicle to a certain range. According to the nearest principle, all customers were clustered and grouped. If the customer load in a group does not reach the minimum load of vehicle and is beyond the limit load when new customers are added in, the new customers were split and adjusted. Finally, while all the customers were divided into groups, the customers paths for each group was arranged by Ant Colony Optimization (ACO) algorithm. The experimental results show that the proposed algorithm has higher stability, and better results in SDVRP.

Key words: Split Delivery Vehicle Routing Problem (SDVRP), clustering algorithm, Ant Colony Optimization (ACO), heuristic algorithm

中图分类号:

TP14

向婷, 潘大志. 求解需求可拆分车辆路径问题的聚类算法[J]. 计算机应用, 2016, 36(11): 3141-3145.

XIANG Ting, PAN Dazhi. Clustering algorithm for split delivery vehicle routing problem[J]. Journal of Computer Applications, 2016, 36(11): 3141-3145.

参考文献

[1] DROR M, TRUDEAU P. Split delivery routing[J]. Naval Research Logistics,1990,37(3):383-402.
[2] DROR M, TRUDEAU P. Savings by split delivery routing[J]. Transportation Science,1989,23(2):141-145.
[3] ARCHETTIC C,FEILLET D,GENDREAU M, et al. Complexity of the VRP and SDVRP[J]. Transportation Research Part C:Emerging Technologies, 2011,19(5):741-750.
[4] ARCHETTIC C,MANSINI R,SPERANZA M G. Complexity and reducibility of the skip delivery problem[J].Transportation Science,2005,39(2):182-187.
[5] ARCHETTIC C,SAVELSBERGH M W,SPERANZA M G. Worst-case analysis for split delivery vehicle routing problems[J].Transportation Science,2006,40(2):226-234.
[6] ARCHETTIC C,SPERANZA M G,HERTZ A. A tabu search algorithm for the split delivery vehicle routing problem[J].Transportation Science, 2006, 40(1):64-73.
[7] GENDREAU M, HERTZA A, LAPORTE G. A tabu search heuristic for the vehicle routing problem[J].Management Science,1994,40(10):1276-1290.
[8] ARCHETTIC C,SAVELSBERGH M W,SPERANZA M G. An optimization-based heuristic for the split delivery vehicle routing problem[J]. Transportation Science, 2008, 42(1):22-31.
[9] 隋露斯,唐加福,潘震东,等.用蚁群算法求解需求可拆分车辆路径问题[C]//2008年中国控制与决策会议论文集. 沈阳:东北大学出版社,2008:997-1001.(SUI L S,TANG J F,PAN Z D,et al. Ant colony algorithm to solve split delivery vehicle routing problem[C]//Chinese Control and Decision Conference 2008. Shenyang:Northeastern University Press, 2008:997-1001.)
[10] 孟凡超,陆志强,孙小明.需求可拆分车辆路径问题的禁忌搜索算法[J].计算机辅助工程,2010,19(1):78-83.(MENG F C,LU Z Q, SUN X M.Taboo seach algorithm of split delivery vehicle routing problem[J]. Computer Aided Engineering,2011,19(1):78-83.)
[11] 谢毅.需求可拆分的物流车辆路线问题研究[D].上海:同济大学, 2006.(XIE Y. Research on split delivery vehicle routing problem[D].Shanghai:Tongji University,2006.)
[12] 刘旺盛,黄娟.需求可拆分的车辆路径问题的分段求解[J].集美大学学报(自然科学版),2011,16(1):38-44.(LIU W S,HUANG J. Two-stage algorithm for split delivery vehicle routing problem[J].Journal of Jimei University (Natural Science),2011,16(1):38-44.)
[13] 刘旺盛,杨帆,李茂青,等.需求可拆分车辆路径问题的聚类求解算法[J].控制与决策,2012,27(4):535-541.(LIU W S,YANG F,LI M Q,et al. Clustering algorithm for split delivery vehicle routing problem[J].Control and Decision,2012,27(4):535-541.)
[14] 熊浩,鄢慧丽.需求可拆分车辆路径问题的三阶段禁忌算法[J].系统工程理论与实践,2015,35(5):1230-1235.(XIONG H,YAN H L.A three-phase tabu seach heuristic for the split delivery vehicle routing problem[J].Systems Engineering-Theory & Practice,2015,35(5):1230-1235.)

[1]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[2]	孙建军, 徐岩. 基于加权改进模糊C均值聚类的欠定混合矩阵估计[J]. 计算机应用, 2020, 40(6): 1769-1773.
[3]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[4]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[5]	刘育良, 陈淮莉. 负载影响下纯电动汽车配送路径规划及充电策略[J]. 计算机应用, 2020, 40(10): 2831-2837.
[6]	隗千千, 董兴业, 王焕政. 染缸排产建模及滑动时间窗启发式调度算法[J]. 计算机应用, 2020, 40(1): 292-298.
[7]	张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用, 2020, 40(1): 96-102.
[8]	黄永鑫, 唐雪飞. 基于近邻传播聚类和TANE算法的高校数据中函数依赖的发现[J]. 计算机应用, 2020, 40(1): 90-95.
[9]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[10]	王东先, 孟学雷, 乔俊, 汤霖, 焦志臻. 基于改进蚁群算法的铁路乘务交路计划的编制[J]. 计算机应用, 2019, 39(9): 2749-2756.
[11]	毛伊敏, 刘银萍, 梁田, 毛丁慧. 基于模糊谱聚类的不确定蛋白质相互作用网络功能模块挖掘[J]. 计算机应用, 2019, 39(4): 1032-1040.
[12]	郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.
[13]	郭良敏, 朱莹, 孙丽萍. 障碍空间中基于并行蚁群算法的k近邻查询[J]. 计算机应用, 2019, 39(3): 790-795.
[14]	杨继东, 孙兆琦, 王飞龙. 基于视觉抓取的并联桁架机器人最优路径控制[J]. 计算机应用, 2019, 39(3): 913-917.
[15]	丁成, 王秋萍, 王晓峰. 基于广义反向学习的磷虾群算法及其在数据聚类中的应用[J]. 计算机应用, 2019, 39(2): 336-342.

求解需求可拆分车辆路径问题的聚类算法

Clustering algorithm for split delivery vehicle routing problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics