Métodos de otimização para o problema de carpooling

Abstract

Neste trabalho propõe-se a aplicação de métodos de otimização para solução do problema de carpooling, no qual consiste em pessoas com destinos em comum que se locomovem juntas em veículos compartilhados. Apresenta-se modelos aproximados, heurística gulosa, meta heurística simulated annealing, variable neighborhood descent (VND) e variable neighborhood search (VNS), além de um modelo exato. Estes buscam maximizar a quantidade de usuários no sistema como passageiros. Leva-se em consideração as informações dos usuários, dentre elas quais são os proprietários de veículos, as janelas de tempo disponível para se alcançar o destino final de cada motorista, a capacidade de cada veículo e o tempo de início da viagem. Apresenta-se a formulação dos métodos utilizados bem como a aplicação de tais métodos para um problema com 66 usuários com destino à uma universidade. Os métodos apresentaram quais usuários são motoristas e quais são as caronas, bem como o trajeto que maximiza a quantidade de passageiros. Os métodos aproximados utilizados foram programados na linguagem de programação C/C++. Apresenta-se análises comparativas entre os métodos nos diferentes cenários propostos. Os métodos apresentam soluções satisfatórias para o problema de carpooling.

This work proposes the application of optimization methods to solve the problem of carpooling, which consist of people with common destinations that move together in shared vehicles. We present approximate models, greedy heuristics, meta-heuristics simulated annealing, variable neighborhood descent (VND) and variable neighborhood search (VNS), in addition to an exact model, which seek to maximize the number of users in the system as passengers. Users' information is taken into account, including vehicle owners, windows of time available to reach the final destination of each driver, the capacity of each vehicle and the time of commencement of the trip. Presents the formulation of the methods used as well as the application of such methods to a problem with 66 users destined to a university. The methods presented which users are drivers and which are the rides, as well as the route that maximizes the number of passengers. The approximate methods used were programmed in the C / C ++ programming language. We present comparative analyzes between the different scenarios proposed. The methods present satisfactory solutions to the problem of carpooling.