A Spatio-temporal Based Parallel Insertion Algorithm for Solving Dial-A-Ride Problem
A static dial-a-ride problem with time windows is investigated,without wait while carrying passengers and maximum ride time constraints as the service quality.A parallel insertion heuristic based on the spatial and temporal aspects is presented.The proposed algorithm firstly sorts the requests based on the earliest pickup time and decentralization index alternately and initializes the routes with seed requests.Then a insertion-rejected-reinsertion operation is performed,in which the spatial aspect as the granular is also considered.Simulation results indicate that the proposed algorithm reduces costs effectively,compared with the algorithms only considering the temporal aspect and no seed requests.Also,sensitivity analysis indicates that the required vehicle number is insensitive to the granular extent and the initial vehicle number.
Dial-A-Ride Problem Spatio-Temporal Parallel Insertion Algorithm Rejected-Reinsertion
Jingmei Guo Chao Liu
Institute of System Engineering,School of Information Science and Engineering,Northeastern Universit Institute of Systems Science,Northeastern University,Shenyang,110004
国际会议
长沙
英文
3257-3261
2014-05-31（万方平台首次上网日期，不代表论文的发表时间）