Comunicação em evento científico
Non-overlapping routes for the mixed capacitated arc routing problem
Ana Catarina Nunes (Nunes, Ana Catarina); Miguel Fragoso Constantino (Constantino, Miguel); Luís Gouveia (L. Gouveia); Maria Cândida Mourão (Mourão, Maria Cândida);
Título Evento
VeRoLog 2014 - 3rd meeting of the EURO Working Group on Vehicle Routing and Logistics Optimization
Ano (publicação definitiva)
2014
Língua
Inglês
País
Noruega
Mais Informação
Web of Science®

Esta publicação não está indexada na Web of Science®

Scopus

Esta publicação não está indexada na Scopus

Google Scholar

N.º de citações: 0

(Última verificação: 2024-03-28 20:43)

Ver o registo no Google Scholar

Abstract/Resumo
Real world applications for collecting or delivering products along streets usually lead to arc routing problems with additional and complicating requirements. Among them there is the undesirable overlapping of the routes of different vehicles while performing their services. In this work we focus on the mixed capacitated arc routing problem (MCARP) with a limited number of intersections of the routes as a way to avoid the overlapping. Then, we define the bounded overlapping MCARP (BCARP), which results from the MCARP by adding a constraint ensuring an upper bound on the number of nodes shared by different routes. We also introduce a new model to compute the best feasible value for this upper bound. Mixed integer linear programming formulations are presented for the BCARP, and a heuristic is proposed to obtain feasible solutions for the bigger instances. Computational results are reported for well-known benchmark instances. The BCARP seems more suitable for real applications. In fact, the results show that better shaped service routes are obtained (more compact and with fewer intersections), with a small increase in total traveled time, when compared to the MCARP.
Agradecimentos/Acknowledgements
--
Palavras-chave
capacitated arc routing problems, district design, integer linear programming, heuristics