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

作者：Catay Buelent^*

来源：Expert Systems with Applications, 2010, 37(10): 6809-6817.

DOI：10.1016/j.eswa.2010.03.045

• Vehicle routing
• Metaheuristics
• Ant Colony Optimization
• Reverse logistics

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.

• 出版日期2010-10