text: 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.
  @cite_30: This paper describes the parallelization of a two-phase metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The underlying objective function combines the minimization of the number of vehicles in the first search phase of the metaheuristic with the minimization of the total travel distance in the second search phase. The parallelization of the metaheuristic follows a type 3 parallelization strategy (cf. Crainic and Toulouse (2001). In F. Glover and G. Kochenberger (eds.). State-of-the-Art Handbook in Metaheuristics. Norwell, MA: Kluwer Academic Publishers), i.e. several concurrent searches of the solution space are carried out with a differently configured metaheuristic. The concurrently executed processes cooperate through the exchange of solutions. The parallelized two-phase metaheuristic was subjected to a comparative test on the basis of 358 problems from the literature with sizes varying from 100 to 1000 customers. The derived results seem to justify the proposed parallelization concept.
  @cite_8: This paper introduces the Localized Optimization Framework (LOF). This framework is an iterative procedure between two phases, Optimization and De-optimization. Optimization is done on the problem parts rather than the problem as a whole, while de-optimization is done on the whole problem. To test our hypothesis, we have chosen a genetic algorithm as an optimization methodology and Vehicle Routing Problem with Time Windows (VRPTW) as a domain space. We call this new scheme the Localized Genetic Algorithm (LGA). We demonstrate that the LGA is, on average, able to produce better solutions than most of the other heuristics on small scale problems of VRPTW. Furthermore the LGA has attained several new best solutions on popular datasets.
  @cite_9: The present study investigates the cost concerns of distribution centers and formulates a vehicle routing problem with time window constraints accordingly. Based on the embedded structure of the original problem, a decomposition technique is employed to decompose the original problems to a clustering problem (main problem) and a set of traveling salesman problems (sub-problems) with time window constraints. This decomposition not only reduces the problem size but also enable the use of simpler solution procedures. A genetic algorithm is developed to solve the clustering problem, while a simple heuristic algorithm is formulated to solve the set of traveling salesman problems. The solution of the original problem is obtained through iterative interactions between the main problem and the set of sub-problems. The performance of the proposed approach is compared with the well-known insertion method and a manual scheduling of a distribution center.
  @cite_3: A parallel version of a new hybrid genetic algorithm for the vehicle routing problem with time windows is presented. The route-directed hybrid genetic approach is based upon the simultaneous evolution of two populations of solutions focusing on separate objectives subject to temporal constraint relaxation. While the first population evolves individuals to minimize total traveled distance the second aims at minimizing temporal constraint violation to generate a feasible solution. Genetic operators have been designed to capture key concepts from successful routing techniques to further enhance search diversification and intensification. A master–slave message-passing paradigm characterizes the parallel procedure. The master component controls the execution of the algorithm, coordinates genetic operations and handles parent selection while the slave elements concurrently execute reproduction and mutation operators. Providing additional speed-up, the parallel algorithm further expands on its sequential counterpart, matching or even improving solution quality. Computational results show the proposed technique to be very competitive with the best-known heuristic routing procedures providing some new best-known solutions.
  @cite_0: 
  @cite_24: This article deals with the vehicle routing problem with time windows (VRPTW). This problem consists in determining a least-cost set of trips to serve customers during specific time windows. The proposed solution method is a memetic algorithm (MA), a genetic algorithm hybridised with a local search. Contrary to most papers on the VRPTW, which minimize first the number of vehicles, our method is also able to minimize the total distance travelled. The results on 56 classical instances are compared to those of the best metaheuristics. The efficiency of the MA is similar for the classical criterion, but it becomes the best algorithm available for the total distance, being much faster and improving 20 best-known solutions.
  @cite_2: In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.
  @cite_31: We present a new and effective metaheuristic algorithm, active guided evolution strategies, for the vehicle routing problem with time windows. The algorithm combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. More precisely, guided local search is used to regulate a composite local search in the first stage and the neighborhood of the evolution strategies algorithm in the second stage. The vehicle routing problem with time windows is a classical problem in operations research, where the objective is to design least cost routes for a fleet of identical capacitated vehicles to service geographically scattered customers within pre-specified time windows. The presented algorithm is specifically designed for large-scale problems. The computational experiments were carried out on an extended set of 302 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 86 of all test instances within reasonable computing times. The power of the algorithm is confirmed by the results obtained on 23 capacitated vehicle routing problems from the literature.
  @cite_17: This paper proposes a new solution to the vehicle routing problem with time windows using an evolution strategy adopting viral infection. The problem belongs to the NP-hard class and is very difficult to solve within practical time limits using systematic optimization techniques. In conventional evolution strategies, a schema with a high degree-of-fitness produced in the process of evolution may not be inherited when the fitness of the individual containing the schema is low. The proposed method preserves the schema as a virus and uses it by the infection operation in successive generations. Experimental results using extended Solomon's benchmark problems with 1000 customers proved that the proposed method is superior to conventional methods in both its rates of searches and the probability of obtaining solutions. Further experiments using the map of the central part of Tokyo with 20000 intersections and real traffic data also gave that the rate of search of the proposed method is higher than that of the conventional method.
summary: Evolutionary algorithms have attracted the scientific attention to solve the VRPTW due to their high search capabilities. Genetic algorithms were applied by Cheng and Wang @cite_9 , @cite_0 and @cite_8 . The evolution strategies were proposed by Gehring and Homberger @cite_30 , @cite_31 and @cite_17 . The sequential and parallel memetic algorithms (MAs), combining the evolutionary algorithms for more distant search with the local optimization and refinements algorithms for local exploitation, were described by Berger and Barkaoui @cite_3 , @cite_24 and Nagata and Br " a ysy @cite_2 . The MA based on the edge-assembly crossover operator (EAX) has been proposed by Nagata and Br " a ysy @cite_2 .