TY - GEN
T1 - Complexity analysis of the parallel memetic algorithm for the pickup and delivery problem with time windows
AU - Blocho, Miroslaw
AU - Nalepa, Jakub
N1 - Publisher Copyright:
© 2018, Springer International Publishing AG.
PY - 2018
Y1 - 2018
N2 - Estimating the theoretical complexity of a parallel algorithm can give an impression on how it will perform in practice. However, this complexity analysis is very often omitted in the works from the parallel computation field. In this paper, we theoretically analyze the time complexity of our parallel algorithm for the pickup and delivery problem with time windows (PDPTW), which is an NP-hard discrete optimization task. The PDPTW is a hierarchical objective problem—the main objective is to minimize the number of trucks serving the transportation requests, whereas the second objective is to optimize the travel distance. In our approach, the fleet size is optimized using the parallel ejection search, and the distance is minimized using the parallel memetic algorithm. Finally, we report example experimental results showing that our parallel algorithms work very fast in practice.
AB - Estimating the theoretical complexity of a parallel algorithm can give an impression on how it will perform in practice. However, this complexity analysis is very often omitted in the works from the parallel computation field. In this paper, we theoretically analyze the time complexity of our parallel algorithm for the pickup and delivery problem with time windows (PDPTW), which is an NP-hard discrete optimization task. The PDPTW is a hierarchical objective problem—the main objective is to minimize the number of trucks serving the transportation requests, whereas the second objective is to optimize the travel distance. In our approach, the fleet size is optimized using the parallel ejection search, and the distance is minimized using the parallel memetic algorithm. Finally, we report example experimental results showing that our parallel algorithms work very fast in practice.
KW - Complexity analysis
KW - PDPTW
KW - Parallel memetic algorithm
UR - https://www.scopus.com/pages/publications/85030792671
U2 - 10.1007/978-3-319-67792-7_46
DO - 10.1007/978-3-319-67792-7_46
M3 - Conference contribution
AN - SCOPUS:85030792671
SN - 9783319677910
T3 - Advances in Intelligent Systems and Computing
SP - 471
EP - 480
BT - Man-Machine Interactions 5 - 5th International Conference on Man-Machine Interactions, ICMMI 2017
A2 - Gruca, Aleksandra
A2 - Czachorski, Tadeusz
A2 - Harezlak, Katarzyna
A2 - Kozielski, Stanislaw
A2 - Piotrowska, Agnieszka
A2 - Czachorski, Tadeusz
PB - Springer Verlag
T2 - 5th International Conference on Man-Machine Interactions, ICMMI 2017
Y2 - 3 October 2017 through 6 October 2017
ER -