A Parallel Memetic Algorithm to Solve the Vehicle Routing Problem with Time Windows
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem
The goal of this paper is to propose and test a new memetic algorithm for the capacitated vehicle routing problem in parallel computing environment. In this paper we consider simple variation of vehicle routing problem i…
GPUHybrid Memetic Search for Electric Vehicle Routing with Time Windows, Simultaneous Pickup-Delivery, and Partial Recharges
With growing environmental concerns, electric vehicles for logistics have gained significant attention within the computational intelligence community in recent years. This work addresses an emerging and significant exte…
Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows
The Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW) has attracted much research interest in the last decade, due to its wide application in modern logistics. Since VRPSPDTW is NP-har…
Memetic Search for Green Vehicle Routing Problem with Private Capacitated Refueling Stations
The green vehicle routing problem with private capacitated alternative fuel stations (GVRP-PCAFS) extends the traditional green vehicle routing problem by considering refueling stations limited capacity, where a limited …
Efficient ExplorationPasMoQAP: A Parallel Asynchronous Memetic Algorithm for solving the Multi-Objective Quadratic Assignment Problem
Multi-Objective Optimization Problems (MOPs) have attracted growing attention during the last decades. Multi-Objective Evolutionary Algorithms (MOEAs) have been extensively used to address MOPs because are able to approx…
Evolutionary Algorithms