11 dez
14:00 Doctoral defense Room 53 of IC2
Exact and heuristic algorithms for coverage routing problems
Lucas Porto Maziero
Advisor / Teacher
Fábio Luiz Usberti - Co-supervisor: Celso Cavellucci
Brief summary
Routing problems have several real-world applications, each with particular constraints such as time windows, green logistics, resource availability and customer accessibility. When it comes to resource availability and accessibility to customers, coverage routing problems are proposed to deal with real scenarios in which difficult-to-reach regions have customers that need to be served, but cannot be visited on site. Coverage routing problems aim to find minimum-cost routes whose customer demands are met by serving them locally or remotely with a vehicle. In this thesis, computational methodologies are proposed for two coverage routing problems: Covering Salesman Problem (CSP) and Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP). Furthermore, two new coverage routing problems are introduced: Capacitated Covering Salesman Problem (CCSP) and Electric Capacitated Covering Tour Problem (ECCTP). CSP is a generalization of the Traveling Salesman Problem in which the objective is to find a minimum cost cycle such that all vertices are visited or covered by the cycle. In this thesis, valid inequalities from the literature are transported to the CSP. Furthermore, a new set of valid inequalities is proposed that makes use of unique aspects of the problem. The first branch-and-cut framework, with exact routines and heuristics to separate valid inequalities, is proposed to solve CSP. Computational experiments carried out on an instance benchmark show that the proposed ramework was able to overcome state-of-the-art methodologies in the literature, in addition to obtaining optimal solutions for several previously unsolved instances. CCSP is introduced in this thesis with the intention of addressing coverage constraints in capable vehicle routing problems. The objective of CCSP is to serve customers using a fleet of vehicles, minimizing the distance covered by vehicles. Vehicles can serve customers locally or remotely. Computational methodologies based on integer linear programming (ILP) and the Biased Random-Key Genetic Algorithm (BRKGA) metaheuristic are proposed to solve CCSP. Furthermore, a PLI formulation from CCSP is extended to solve MDCTVRP. The results of the computational experiments show that the new formulation for MDCTVRP outperformed the best existing exact approach so far. Specifically, optimal solutions were obtained for several previously unsolved instances. In order to address a real scenario involving green logistics, ECCTP is introduced in this thesis. ECCTP is a new variant of the vehicle routing problem where customer demands can be met by electric vehicles with limited range and electric vehicles can recharge at alternative charging stations. Vehicles can serve customers locally or remotely. A mixed PLI formulation and a metaheuristic (BRKGA) are proposed to solve ECCTP.
Examination Board
Fábio Luiz Usberti IC / UNICAMP
Pedro Belin Castellucci UFSC
Pedro Henrique Del Bianco Hokama IMC / UNIFEI
Washington Alves de Oliveira FCA/UNICAMP
Kelly Cristina Poldi IMECC / UNICAMP
Guilherme Pimentel Telles IC / UNICAMP
Pedro Augusto Munari Junior CCET/UFSCar
Franklina Maria Bragion de Toledo ICMC / USP