Orientador: Rafael Crivellari Saliba Schouery

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: Nesta dissertação abordamos um problema de otimização combinatória motivado por serviços de aluguel de veículos conhecidos por car-sharing. O problema explora a possibilidade de devoluções flexíveis, isto é, permitir que os clientes devolvam os veículos alugados em pátios de estacionamento...

Resumo: Nesta dissertação abordamos um problema de otimização combinatória motivado por serviços de aluguel de veículos conhecidos por car-sharing. O problema explora a possibilidade de devoluções flexíveis, isto é, permitir que os clientes devolvam os veículos alugados em pátios de estacionamento diferentes daquelas em que os veículos foram retirados. Este problema pode ser descrito da seguinte maneira. Considere dois pátios, denominados por A e B, com cada pátio contendo um conjunto indistinguível de veículos. Dado n clientes, onde cada cliente possui exatamente duas demandas em direções opostas, uma demanda de A para B e outra de B para A, mas não necessariamente nesta ordem. Cada demanda especifica o intervalo de tempo em que o veículo será utilizado. O objetivo do problema é encontrar um escalonamento dos veículos aos clientes que maximiza o número de clientes satisfeitos. Um cliente está satisfeito se e somente se ambas as suas demandas são atendidas. Em um primeiro momento, apresentamos uma formulação de programação linear inteira mista para o problema, bem como a adição de desigualdades válidas à formulação. Em seguida, descrevemos algoritmos heurísticos baseados nas meta-heurísticas GRASP, VNS, Busca Tabu e BRKGA. Em nossos experimentos computacionais, a formulação sem e com a adição de desigualdades válidas obtiveram em média menos de 1% de gap de otimalidade entre o valor do limitante inferior e o valor do limitante superior -- resultados obtidos sobre instâncias com até 1000 clientes e pelo menos 10 veículos disponíveis em cada pátio, com tempo de execução limitado em 20 minutos por instância. No entanto, o problema abordado mostrou-se ser de difícil resolução por meio dos algoritmos heurísticos propostos. Em nossos experimentos computacionais, para as instâncias de 1000 clientes e 10 veículos disponíveis em cada pátio, os algoritmos heurísticos não conseguiram obter uma solução ótima, onde obtiveram em média 10% de gap de otimalidade entre o valor da solução incumbente e o valor da solução ótima obtida por meio do resolvedor de programação inteira mista utilizado

Abstract: In this dissertation, we address a combinatorial optimization problem motivated by car rental services, such as car-sharing. The problem explores the flexible drop-off possibility, in other words, allows the customers to begin and end their trip at different locations. This problem can be...

Abstract: In this dissertation, we address a combinatorial optimization problem motivated by car rental services, such as car-sharing. The problem explores the flexible drop-off possibility, in other words, allows the customers to begin and end their trip at different locations. This problem can be described as follows. Consider two locations, denoted by A and B, with an initial distribution of indistinguishable vehicles. Given n customers, where each customer has exactly two demands in opposite directions, a demand from A to B and another from B to A, not necessarily in this order. Each driving demand specifies the time interval in which the vehicle will be used. The goal consists of scheduling a set of vehicles to maximize the number of satisfied customers. A customer is satisfied if and only if both of your demands are fulfilled. First, we propose a mixed integer linear programming formulation for the problem, and the addition of valid inequalities to the formulation. Furthermore, we describe heuristic algorithms based on the metaheuristics GRASP, VNS, Tabu Search and BRKGA. In our computational experiments, the formulation with and without the addition of valid inequalities obtained, on average, less than 1% optimality gap between lower bound and upper bound - results over problem instances with up to 1000 customers and at least 10 vehicles available in each location, with execution time limited to 20 minutes per instance. On the other hand, the problem addressed has proved to be difficult to solve by heuristic algorithms. In our computational experiments, for the instances of 1000 customers and 10 vehicles available in each location, the heuristic algorithms failed to obtain an optimal solution, and obtained on average 10% of optimality gap between incumbent solution and optimal solution

Requisitos do sistema: Software para leitura de arquivo em PDF