Full text
| |
| Author(s): |
Rafael Kendy Arakaki
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2020-03-05 |
| Examining board members: |
Fábio Luiz Usberti;
Franklina Maria Bragion de Toledo;
Mário César San Felice;
Christiano Lyra Filho;
Paulo Morelato França
|
| Advisor: | Fábio Luiz Usberti |
| Abstract | |
Arc routing problems aim to find minimum cost routes that visit a subset of arcs of a graph, with one or more side constraints. This thesis studies three NP-hard arc routing problems: (1) the capacitated arc routing problem (CARP); (2) the open capacitated arc routing problem (OCARP); and (3) the covering Chinese postman problem (CCPP). We present mathematical formulations and heuristic and exact methods to computationally solve these problems: (i) a greedy and randomized constructive heuristic is proposed for the CARP; (ii) a hybrid genetic algorithm metaheuristic and two linear integer programming lower bound methods, one based on branch-and-cut and one based on flow networks, are proposed for the OCARP; and (iii) an exact branch-and-cut method with valid inequalities and a constructive heuristic are proposed for the CCPP. Extensive computational experiments using benchmark instances were performed to demonstrate the performance of the proposed methods in comparison to the previous methods, regarding both quality of solutions and processing time. Our results show that the proposed methods are state-of-the-art. The studied problems have many relevant practical applications: the CARP has applications on urban waste collection and snow removal; the OCARP has applications on the routing of meter readers and the cutting of metal sheets; and last, the CCPP has applications on automated meter readers routing. The solution of these problems leads to the reduction of logistics costs, improving businesses competitiveness (AU) | |
| FAPESP's process: | 16/00315-0 - Formulations and Algorithms for Arc Routing Problems |
| Grantee: | Rafael Kendy Arakaki |
| Support Opportunities: | Scholarships in Brazil - Doctorate |