An Improved Ant Colony System for Solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery

The classical vehicle routing problem (VRP) is one of the most important combinatorial optimisation problems, and has received much attention from researchers and scientists. This problem involves routing a fleet of vehicles, each visiting a set of customers such that every customer is visited exactly once and by exactly one vehicle, with the objective of minimizing the total distance travelled by all the vehicles. The vehicle routing problem with simultaneous pickups and deliveries (VRP_SPD) is an extension to the VRP, where the vehicles are not only required to deliver goods to customers, but also to collect some goods from the customer locations.Ant Colony Optimisation (ACO) is a probabilistic technique that simulates the ants’ food-hunting behaviour, which is used for solving problems that do not have a known efficient algorithm. The Ant Colony System (ACS) is one of the most famous metaheuristic algorithms, which differs from the other ACO methods due to its transition rule and updating pheromone. This paper proposes an improved ACS, mixed with a 3-opt local search for solving the VRP_SPD. The proposed method is different to the common ACS with regards to the coefficient pheromone and heuristic information for the ant visibility measure. This process will avoid the premature convergence and generate better solutions. The proposed algorithm is tested on 34 standard instances available in the literature. The computational result shows that the proposed algorithm improves the four best-known solutions of the benchmark problem, and it is competitive with other metaheuristic algorithms for solving the VRP_SPD.