@inproceedings{100c87cb80d14dddaeddf76557fe42a3,
title = "A Parallel Algorithm with the Search Space Partition for the Pickup and Delivery with Time Windows",
abstract = "The pickup and delivery problem with time windows (PDPTW) is an NP-hard optimization problem of serving transportation requests using a limited number of vehicles. Its main objective is to minimize the number of delivering trucks, whereas the secondary objective is to decrease the distance traveled during the service. A feasible routing schedule must satisfy the time window, capacity and precedence constraints. In this paper, we propose to partition the search space in our parallel guided ejection search algorithm (P-GES) to minimize the fleet size in the PDPTW. The introduced techniques help decrease the convergence time of the algorithm without affecting the quality of results. An extensive experimental study (comprising nearly 52,000 CPU hours on an SMP cluster) performed on the Li and Lim's benchmark set shows that the parallel algorithm is effective, and is able to retrieve very high-quality results. We report 10 new world's best solutions obtained using P-GES enhanced with the proposed search space partition approaches.",
keywords = "PDPTW, co-operation scheme, guided ejection, parallel algorithm, search space partition",
author = "Jakub Nalepa and Miroslaw Blocho",
note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, 3PGCIC 2015 ; Conference date: 04-11-2015 Through 06-11-2015",
year = "2015",
doi = "10.1109/3PGCIC.2015.12",
language = "English",
series = "Proceedings - 2015 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, 3PGCIC 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "92--99",
editor = "Fabrizio Messina and Fatos Xhafa and Ogiela, \{Marek R.\} and Leonard Barolli",
booktitle = "Proceedings - 2015 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, 3PGCIC 2015",
address = "United States",
}