Arc routing problems with scheduling and covering constraints

• Grant number: 19/00197-5
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• Start date: May 16, 2019
• End date: August 25, 2019
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Fábio Luiz Usberti
• Grantee: Rafael Kendy Arakaki
• Supervisor: Mutsunori Yagiura
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: Nagoya University, Japan
• Associated to the scholarship: 16/00315-0 - Formulations and Algorithms for Arc Routing Problems, BP.DR

Abstract

Arc routing problems aim at determining the lowest cost routes visiting a subset of edges from a graph, with one or more additional constraints. The solution of these problems leads to lower logistics costs, improving business competitiveness. This project concerns the study of two problems of the arc routing class: (1) arc routing with covering constraints; (2) arc routing with time-windows (scheduling constraints). Both are NP-hard combinatorial optimization problems. The objective of this project is the development of mathematical formulations and efficient metaheuristics in order to obtain exact and approximate solutions for these problems.