Problema de Compartilhamento de Veículos com Restrições Físicas e Sociais Permitindo Determinados Tipos de Ciclos: uma abordagem heurística

Abstract

Over the years, there has been an unbridled growth in the number of personal vehicles throughout the country, and this is one of the main factors responsible for environmental and mobility problems, especially in big cities. One solution to this problem, used by a large part of the population, is the sharing of vehicles between people with similar itineraries. Although it is a very usual solution, the manner applied today can present risks to the security of those involved, since many shares are made with unknown individuals. Through the analysis of physical location and social of individuals, this work proposes a new solution for solving this problem. To this end, a study on the Problem of Vehicle Sharing with Physical and Social Restrictions is presented and methods for its through a heuristic approach. Applied techniques search for solutions that seek to minimize the distances between the involved ones, trying also to maximize the social relations between them. Two test groups were created to analyze the presented algorithm. The first experiment compared the results obtained with the exact method of Rodrigues (2018). For the 39 tested instances, the proposed heuristic presents, on average, a GAP of 37% using half the time spent by the exact algorithm.