Uma heurística relax-and-fix para o Vehicle Routing Problem with Pickup and Delivery with Time Windows aplicado a um problema de transporte marítimo

O presente trabalho tem como objetivo apresentar um método de solução para um problema marítimo enfrentado por uma empresa do ramo de fertilizantes químicos. Este problema está associado ao planejamento operacional do processo de coleta de matéria-prima em portos europeus e sua entrega realizada em portos brasileiros para abastecer plantas misturadoras. O problema foi introduzido por Kretschmann (2018), o qual realizou uma formulação matemática baseada no Vehicle Routing Problem with Pickup and Delivery with Time Windows (VRPPDTW). Contudo, o metódo de solução desenvolvido por Kretschmann (2018), baseado no branch-andbound, não permitiu a solução dos problemas reais da empresa. O foco deste trabalho concentrouse no desenvolvimento de um método heurístico baseado em relax-and-fix especificamente desenvolvido para resolver instâncias reais. A utilização da heurística permitiu a obtenção de soluções melhores em relação ao sistema vigente empregado pela empresa. Adicionalmente, a heurística reduziu o processo de planejamento de 60 dias para 2 horas em média.This study aims to present a solution method for a maritime problem faced by a chemical fertilizer company. This problem is associated to the operational planning of the raw material collection process in European ports and its delivery in Brazilian ports to supply mixing plants. The problem was firstly introduced by Kretschmann (2018), which performed a mathematical formulation based on the Vehicle Routing Problem with Pickup and Delivery with TimeWindows (VRPPDTW). Unfortunately, the solution method developed by Kretschmann (2018), based on branch-and-bound, did not allow solving the company’s real problems. The focus of this work was the development of a heuristic method based on relax-and-fix specifically designed to solve real instances. The use of heuristics allowed to obtain better solutions in relation to the current system employed by the company. In addition, heuristics reduced the planning process from 60 days to 2 hours on average