Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2014, Vol. 15 Issue (3): 200-210    DOI: 10.1631/jzus.C1300177
    
求解集送货可拆分车辆路径问题的两阶段启发式方法
Yong Wang, Xiao-lei Ma, Yun-teng Lao, Hai-yan Yu, Yong Liu
School of Management, Chongqing Jiaotong University, Chongqing 400074, China; School of Transportation Science and Engineering, Beihang University, Beijing 100191, China; Department of Civil and Environmental Engineering, University of Washington, Seattle, WA 98195-2700, USA
A two-stage heuristic method for vehicle routing problem with split deliveries and pickups
Yong Wang, Xiao-lei Ma, Yun-teng Lao, Hai-yan Yu, Yong Liu
School of Management, Chongqing Jiaotong University, Chongqing 400074, China; School of Transportation Science and Engineering, Beihang University, Beijing 100191, China; Department of Civil and Environmental Engineering, University of Washington, Seattle, WA 98195-2700, USA
 全文: PDF 
摘要： 研究目的：集送货可拆分车辆路径问题具有配送和收集需求同时可拆分、客户点需求量可超过单车装载量、客户点被单车访问可超过一次等特点，针对测试该问题的公共数据集寻求有效求解方法，是一项富有挑战性的工作，目前缺乏有效、方便的求解算法。本文探讨求解集送货可拆分车辆路径问题的有效算法。
创新要点：提出两阶段启发式方法，即可行解获取的初始启发式算法和改进初始解的混合启发式算法，为研究车辆路径问题需求拆分和访问次数的松弛提供了有效的求解思路。引用描述该问题实质的逻辑关系模型，结合定义和化简的概念，本文算法为集送货可拆分车辆路径问题的研究，提供了分步计算的实用算法。
方法提亮：组成两阶段启发式方法的各种逻辑关系模型简洁、准确地描述了集送货可拆分车辆路径问题，同时具备可扩展性和可组合性。这些特性的灵活应用，形成本文提出的两阶段优化算法。
重要结论：利用Solomon数据集和可扩展的Solomon数据集进行实验计算，并与禁忌搜索算法（TSA），粒子群算法（PSO）以及并行启发式方法（PHA）比较，结果表明，对于不同规模数据集，本文算法有效节省了总配送成本、提升了平均装载率。
关键词： 集送货可拆分的车辆路径问题（VRPSPDP）;  两阶段启发式方法;  混合启发式算法;  Solomon数据集    
Abstract: The vehicle routing problem (VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups (VRPSPDP) is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.
Key words: Vehicle routing problem with split deliveries and pickups (VRPSPDP)    Two-stage heuristic method    Hybrid heuristic algorithm    Solomon benchmark datasets
收稿日期: 2013-07-03 出版日期: 2014-03-05
CLC:  TP3  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Yong Wang
Xiao-lei Ma
Yun-teng Lao
Hai-yan Yu
Yong Liu

引用本文:

Yong Wang, Xiao-lei Ma, Yun-teng Lao, Hai-yan Yu, Yong Liu. A two-stage heuristic method for vehicle routing problem with split deliveries and pickups. Front. Inform. Technol. Electron. Eng., 2014, 15(3): 200-210.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C1300177    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2014/V15/I3/200

[1] Ehsan Saeedi, Yinan Kong, Md. Selim Hossain. 边信道攻击和学习向量量化[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 511-518.
[2] Gopi Ram , Durbadal Mandal , Sakti Prasad Ghoshal , Rajib Kar . 使用猫群算法优化线性天线阵列的最佳阵因子辐射方向图：电磁仿真验证[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 570-577.
[3] Yu-jun Xiao, Wen-yuan Xu, Zhen-hua Jia, Zhuo-ran Ma, Dong-lian Qi. 一种非侵入式的基于功耗的可编程逻辑控制器异常检测方案[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 519-534.
[4] Lin-bo Qiao, Bo-feng Zhang, Jin-shu Su, Xi-cheng Lu. 结构化稀疏学习综述[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 445-463.
[5] Mei-juan Jia, Hui-qiang Wang, Jun-yu Lin, Guang-sheng Feng, Hai-tao Yu. DGTM：基于动态分组的移动P2P网络信任模型[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 559-569.
[6] Yuan-ping Nie, Yi Han, Jiu-ming Huang, Bo Jiao, Ai-ping Li. 基于注意机制编码解码模型的答案选择方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 535-544.
[7] Hamid Reza Boveiri. 基于渐进式蚁群优化的多处理器任务分配[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 498-510.
[8] Rong-Feng Zhang , Ting Deng , Gui-Hong Wang , Jing-Lun Shi , Quan-Sheng Guan . 基于可靠特征点分配算法的鲁棒性跟踪框架[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 545-558.
[9] Deng Chen, Yan-duo Zhang, Wei Wei, Shi-xun Wang, Ru-bing Huang, Xiao-lin Li, Bin-bin Qu, Sheng Jiang. 基于改进规则检查静态分析技术的高效脆弱性检测方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 332-345.
[10] . 一种基于描述逻辑的体系质量需求建模与验证方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 346-361.
[11] Ali Darvish Falehi, Ali Mosallanejad. 使用基于多目标粒子群算法多层自适应模糊推理系统晶闸管控制串联电容器补偿技术的互联多源电力系统动态稳定性增强器[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 394-409.
[12] Gaurav Bansod, Narayan Pisharoty, Abhijit Patil. BORON：面向普适计算的超轻量低功耗加密设计[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 332-345.
[13] Wen-yan Xiao, Ming-wen Wang, Zhen Weng, Li-lin Zhang, Jia-li Zuo. 基于语料库的小学英语认识率及教材选词策略研究[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 362-372.
[14] Dong-wei Xu, Yong-dong Wang, Li-min Jia, Yong Qin, Hong-hui Dong. 基于ARIMA和Kalman滤波的道路交通状态实时预测[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 287-302.
[15] Hui Chen, Bao-gang Wei, Yi-ming Li, Yong-huai Liu, Wen-hao Zhu. 一种易用的实体识别消歧系统评测框架[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 195-205.