A Parallel EAX-based Algorithm for Minimizing the Number of Routes in the Vehicle Routing Problem with Time Windows

A parallel EAX-based algorithm for minimizing the number of routes in the vehicle routing problem with time windows is presented. The main contribution is a novel approach concerning the usage of the edge assembly crossover (EAX) operator during exchanging the best solutions between the processes. The objective of the work is to analyze the speedup, achieved accuracy of solutions and scalability of the MPI implementation. For comparisons the selected Gehring and Homberger´s (GH) tests are used. The results of the extensive computational experiments indicate that the new algorithm based on the EAX approach is not only very fast but also very effective. The eight new best-known solutions for the GH benchmarking tests were found by making use of the algorithm.