A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

The Vehicle Routing Problem with Pickup and Delivery (VRPPD) is a variant of the Vehicle Routing Problem where the vehicles are not only required to deliver goods but also to pick up some goods from the customers. Given a fleet of vehicles and a set of customers with known delivery and/or pickup demands for one commodity VRPPD determines a set of vehicle routes originating and ending at a single depot and visiting all customers exactly once. The objective is to minimize the total distance traversed. In this paper, we consider a special case of the VRPPD where each customer has both a delivery and a pickup demand to be satisfied simultaneously. For this problem, we propose an ant colony algorithm employing a new saving-based visibility function and pheromone updating procedure. The numerical tests with the well-known benchmark problems from the literature show that the proposed approach provides competitive results and improves several best-known solutions. (C) 2010 Elsevier Ltd. All rights reserved.