Roteirization of vehicles in the delivery/collection problems - Application of a modifed Ant Colony Algorithm

Abstract

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. It can be modelled as the well-known Chinese Postman Problem on mixed graphs (MCPP). The MCPP is a fair model for the delivering and collecting problem 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 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. The results were promising and comparable to some other algorithms. It was found results near of optimal solutions in some cases.

Keywords

• problema de roteamento de arcos
• problema do carteiro chinês
• problema do caixeiro viajante
• metaheurística