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.