Routing of vehicles in the delivery/collection problems-Application of a modified Ant Colony Algorithm

Delivering and collecting problems concern to situations where goods are delivered (or collected) in practical cases. For example, solid waste collection, postal services and snow removing. They can be modelled as the well-known Chinese Postman Problem on mixed graphs (MCPP). The MCPP is a fair model for delivering and collecting problems because its goal is to cover all links of a mixed graph with minimal cost. The objective of this paper is to develop an algorithm based on Ant Colony Optimization (ACO) and apply it to MCPP solution. The MCPP is initially converted into an equivalent Travelling Salesman Problem (TSP) and then tackled on this second instance. According to our knowledge, this approach for MCPP solution is the first one in literature.