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

Por exemplo, coleta de lixo sólido, serviços postais e remoção de neve. Eles podem ser modelados como o conhecido

Problema do Carteiro Chinês em grafos mistos (PCCM). O PCCM é um modelo justo para problemas de entrega

e coleta, pois seu objetivo é cobrir todos os links de um grafo misto com um custo mínimo. O objetivo deste

artigo é desenvolver um algoritmo baseado na Otimização por Colônia de Formigas (OCF) e aplicá-lo para solução

do PCCM. O PCCM é inicialmente convertido em um Problema do Caixeiro Viajante (PCV) equivalente e então

resolvido para esta segunda instância. Segundo o nosso conhecimento, essa abordagem para solução do PCCM é a

primeira na literatura.

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 rst one in literature.

Revista Brasileira de Computação Aplicada