  This paper presents a parallel memetic algorithm for solving the vehicle
routing problem with time windows (VRPTW). The VRPTW is a well-known NP-hard
discrete optimization problem with two objectives. The main objective is to
minimize the number of vehicles serving customers scattered on the map, and the
second one is to minimize the total distance traveled by the vehicles. Here,
the fleet size is minimized in the first phase of the proposed method using the
parallel heuristic algorithm (PHA), and the traveled distance is minimized in
the second phase by the parallel memetic algorithm (PMA). In both parallel
algorithms, the parallel components co-operate periodically in order to
exchange the best solutions found so far. An extensive experimental study
performed on the Gehring and Homberger's benchmark proves the high convergence
capabilities and robustness of both PHA and PMA. Also, we present the speedup
analysis of the PMA.
