A Particle Swarm Optimization for the Vehicle Routing Problem with Clustered Customers

This paper presented a particle swarm optimization algorithm (PSO) sor solving vehicle routing problem (VRP) which involves single depot and clustered customers. Three different solution representations and decoding methods are proposed for solving VRP using PSO. Thisrepresentations are similari the use of particle with 2m dimension to represent m vehicles. In the decoding step, these particle dimensions are transforming to a priority matrix of vehicle to serve each customer. These representations are different on how to create customer priority list: the first representations directly uses the customer list data as the customer priority list; the second preprocesses the customer list data according to its polar angle as the customer priority list; the third uses random-key to build the costomer priority list. The customer priority list and vehicle matrix are utilized for constructing vehicle routes at the end of the decoding step. A computational experiment is conducted by applying the proposed algoritmn on the benchmark data set of capacitated vehicle routing problem(CVRP) and the vehicle routing problem with time windows (VRPTW). The result showed that the proposed algorithm with the third representation isthe most effective to solve CVRP and VRPTW problem