Name: ANDRÉ MANHÃES MACHADO

Publication date: 27/10/2021
Advisor:

Name	Role
MARIA CLAUDIA SILVA BOERES	Co-advisor *

Examining board:

Name	Role
ANDRÉ RENATO SALES AMARAL	Internal Examiner *
ISAAC PINHEIRO DOS SANTOS	Internal Examiner *
LUCIANO LESSA LORENZONI	External Examiner *
MARIA CLAUDIA SILVA BOERES	Co advisor *

Summary: This work develops a hybrid matheuristic based on the approach Route-First-Cluster-Second (RFCS) by applying Greedy Randomized Adaptive Search Procedure (GRASP), mathematical models and Variable Neighborhood Search (VNS) to tackle two types of vehicle routing problems: the Capacitated Vehicle Routing Problem (CVRP) and the Helicopter Routing Problem (HRP). At first, in the proposed method, a routing is performed using constructive heuristics and the Set Covering Problem (SCP). SCP employs local optima solutions found in previous iterations of VNS to create a partial tour which is filled by a constructive heuristic if needed. Then, the built solution undergoes a local search phase by VNS. This process is repeated as the main loop of the GRASP. As last step of the method, the Set Partitioning Problem (SPP) provides a new improved solution with regard to solutions found in the GRASP. In relation to the study problems, the CVRP consists of designing a set of routes for a fleet of identical vehicles to attend a set of customers at shortest distance travelled, while the HRP aims of serving a set of transportation requests, defined as a pair of boarding and landing locations, using helicopters as the mode of transportation to minimize the cost of meeting the set of transportation requests. Besides, we propose a new HRP model to address unique characteristics of offshore platforms through a novel constraint to solve an issue that remains unnoticed until now: offshore platforms can be visited by helicopters one at a time. We also add the possibility to make multiple trips inside each route and enforce time window to attend passengers. Besides, the model has restrictions regarding to the total time of the flight, the fuel consumption, the total weight during the flight, the number of seats used by passengers. The matheuristic is proposed in two versions. The first one solves the CVRP, and it is tested in seven benchmarks using other heuristics in the literature as a comparison. The second version is applied in two models of the HRP, WHERE the method is tested in 37 instances with up to 1000 requests. Computational experiments showed that the proposed matheuristic for CVRP is competitive in terms of the quality for solutions reported in recent works. Moreover, in relation to the HRP, the matheuristic achieves results equal to or greater than other heuristics in 36 instances.
Key-words: Capacitated Vehicle Routing Problem (CVRP). Helicopter Routing Problem (HRP). Greedy Randomized Adaptive Search Procedure (GRASP). Variable Neighborhood Search (VNS). Set Covering Problem (SCP). Set Partitioning Problem (SPP

Access to document