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 in which the only parameter is the capacity of the vehicle and each client only needs one package. We present simple reduction to prove the existence of polynomial-time algorithm for capacity 2. We analyze the efficiency of the algorithm using hierarchical Parallel Random Access Machine (PRAM) model and run experiments with code written in CUDA (for capacities larger than 2).
Code (0)
등록된 구현이 없습니다.
Tasks
GPUSimilar Papers 제목 키워드 기반
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 …
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 ExplorationA reinforcement learning guided hybrid evolutionary algorithm for the latency location routing problem
The latency location routing problem integrates the facility location problem and the multi-depot cumulative capacitated vehicle routing problem. This problem involves making simultaneous decisions about depot locations …
Diversityreinforcement-learningReinforcement LearningKnowledge-Guided Memetic Algorithm for Capacitated Arc Routing Problems with Time-Dependent Service Costs
The capacitated arc routing problem with time-dependent service costs (CARPTDSC) is a challenging combinatorial optimization problem that arises from winter gritting applications. CARPTDSC has two main challenges about t…
Combining Constructive and Perturbative Deep Learning Algorithms for the Capacitated Vehicle Routing Problem
The Capacitated Vehicle Routing Problem is a well-known NP-hard problem that poses the challenge of finding the optimal route of a vehicle delivering products to multiple locations. Recently, new efforts have emerged to …
Deep Learning