A Particle Swarm Optimization Algorithm for the Open Vehicle Routing Problem

In the open vehicle routing problem (OVRP), a vehicle does not return to the depot after servicing the last customer on a route. The description of this variant of the standard vehicle routing problem appeared in the literature over 20 years ago, but it has still received little attention from researchers for a satisfactory solution. In this paper, a novel real number encoding method of Particle Swarm Optimization (PSO) for Open Vehicle Routing Problem is proposed. The vehicle is mapped into the integer part of the real number; and the sequence of customers in the vehicle is mapped into the decimal fraction of the real number. They are used to optimize the inner or outer routes and modify illegal solutions. In the experiments, a number of numerical examples are carried out for testing and verification. The Computational results confirm the efficiency of the proposed methodology.