Exact and heuristic algorithms for a car-sharing problem

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 (AU)