Please wait a minute...
Front. Inform. Technol. Electron. Eng.  2014, Vol. 15 Issue (3): 200-210    DOI: 10.1631/jzus.C1300177
    
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
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

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 wordsVehicle routing problem with split deliveries and pickups (VRPSPDP)      Two-stage heuristic method      Hybrid heuristic algorithm      Solomon benchmark datasets     
Received: 03 July 2013      Published: 05 March 2014
CLC:  TP3  
  TU121  
Cite this article:

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.

URL:

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


求解集送货可拆分车辆路径问题的两阶段启发式方法

研究目的:集送货可拆分车辆路径问题具有配送和收集需求同时可拆分、客户点需求量可超过单车装载量、客户点被单车访问可超过一次等特点,针对测试该问题的公共数据集寻求有效求解方法,是一项富有挑战性的工作,目前缺乏有效、方便的求解算法。本文探讨求解集送货可拆分车辆路径问题的有效算法。
创新要点:提出两阶段启发式方法,即可行解获取的初始启发式算法和改进初始解的混合启发式算法,为研究车辆路径问题需求拆分和访问次数的松弛提供了有效的求解思路。引用描述该问题实质的逻辑关系模型,结合定义和化简的概念,本文算法为集送货可拆分车辆路径问题的研究,提供了分步计算的实用算法。
方法提亮:组成两阶段启发式方法的各种逻辑关系模型简洁、准确地描述了集送货可拆分车辆路径问题,同时具备可扩展性和可组合性。这些特性的灵活应用,形成本文提出的两阶段优化算法。
重要结论:利用Solomon数据集和可扩展的Solomon数据集进行实验计算,并与禁忌搜索算法(TSA),粒子群算法(PSO)以及并行启发式方法(PHA)比较,结果表明,对于不同规模数据集,本文算法有效节省了总配送成本、提升了平均装载率。

关键词: 集送货可拆分的车辆路径问题(VRPSPDP),  两阶段启发式方法,  混合启发式算法,  Solomon数据集 
[1] Ehsan Saeedi, Yinan Kong, Md. Selim Hossain. Side-channel attacks and learning-vector quantization[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 511-518.
[2] Gopi Ram , Durbadal Mandal , Sakti Prasad Ghoshal , Rajib Kar . Optimal array factor radiation pattern synthesis for linear antenna array using cat swarm optimization: validation by an electromagnetic simulator[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 570-577.
[3] Yu-jun Xiao, Wen-yuan Xu, Zhen-hua Jia, Zhuo-ran Ma, Dong-lian Qi. NIPAD: a non-invasive power-based anomaly detection scheme for programmable logic controllers[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 519-534.
[4] Lin-bo Qiao, Bo-feng Zhang, Jin-shu Su, Xi-cheng Lu. A systematic review of structured sparse learning[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 445-463.
[5] Mei-juan Jia, Hui-qiang Wang, Jun-yu Lin, Guang-sheng Feng, Hai-tao Yu. DGTM: a dynamic grouping based trust model for mobile peer-to-peer networks[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 559-569.
[6] Yuan-ping Nie, Yi Han, Jiu-ming Huang, Bo Jiao, Ai-ping Li. Attention-based encoder-decoder model for answer selection in question answering[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 535-544.
[7] Hamid Reza Boveiri. An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 498-510.
[8] Rong-Feng Zhang , Ting Deng , Gui-Hong Wang , Jing-Lun Shi , Quan-Sheng Guan . A robust object tracking framework based on a reliable point assignment algorithm[J]. Front. Inform. Technol. Electron. Eng., 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. Efficient vulnerability detection based on an optimized rule-checking static analysis technique[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 332-345.
[10] . A quality requirements model and verification approach for system of systems based on description logic[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 346-361.
[11] Ali Darvish Falehi, Ali Mosallanejad. Dynamic stability enhancement of interconnected multi-source power systems using hierarchical ANFIS controller-TCSC based on multi-objective PSO[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 394-409.
[12] Wen-yan Xiao, Ming-wen Wang, Zhen Weng, Li-lin Zhang, Jia-li Zuo. Corpus-based research on English word recognition rates in primary school and word selection strategy[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 362-372.
[13] Gaurav Bansod, Narayan Pisharoty, Abhijit Patil. BORON: an ultra-lightweight and low power encryption design for pervasive computing[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 332-345.
[14] Li Weigang. First and Others credit-assignment schema for evaluating the academic contribution of coauthors[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 180-194.
[15] Dong-wei Xu, Yong-dong Wang, Li-min Jia, Yong Qin, Hong-hui Dong. Real-time road traffic state prediction based on ARIMA and Kalman filter[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 287-302.