A particle swarm optimization algorithm for open vehicle routing problem

This paper presents a real-value version of particle swarm optimization (PSO) for solving the open vehicle routing problem (OVRP) that is a well-known combinatorial optimization problem. In OVRP a vehicle does not return to the depot after servicing the last customer on a route. A particular decoding method is proposed for implementing PSO for OVRP. In the decoding method, a vector of the customer’s position is constructed in descending order. Then each customer is assigned to a route with taking into account feasibility conditions. Finally one-point move has been applied on constructed routes that seem promising to result in a better solution. Experimental evaluations on benchmark data sets demonstrate the competitiveness of the proposed algorithm.

► We introduce a solution method based on PSO algorithm to solve OVRP. The used decoding procedure takes into account solution feasibility. We examine improvement methods to get better solution quality. The approach effectiveness checked by using benchmark data sets.