Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Integer Linear Programming are known for their difficulty to be solved, generally requiring exponential time. In this article, two matheuristics methods are applied to the Unit Stop Number Problem (USNP), a dial-a-ride problem arising from the deployment of autonomous electric vehicles. Such methods are developed with the objective of improving the resolution time of USNP by combining exact methods with heuristic approaches. For this, the matheuristics methods Randomized-Rounding and Relax-and-Fix were studied, adapted and implemented in C++ programming language. Since such methods are mainly based on the decomposition of the general problem into smaller simpler ones, we explore different strategies of decomposition. The computational results obtained allowed us to analyze the impact of each one of these strategies.