  One-way car-sharing systems are transportation systems that allow customers
to rent cars at stations scattered around the city, use them for a short
journey, and return them at any station. The maximum customers' satisfaction
problem concerns the task of assigning the cars, initially located at given
stations, to maximize the number of satisfied customers. We consider the
problem with two stations where each customer has exactly two demands in
opposite directions between both stations, and a customer is satisfied only if
both their demands are fulfilled. For solving this problem, we propose
mixed-integer programming (MIP) models and matheuristics based on local search.
We created a benchmark of instances used to test the exact and heuristic
approaches. Additionally, we proposed a preprocessing procedure to reduce the
size of the instance. Our MIP models can solve to optimality 85% of the
proposed instances with 1000 customers in 10 minutes, with an average gap
smaller than 0.1% for all these instances. For larger instances (2500 and 5000
customers), except for some particular cases, they presented an average gap
smaller than 0.8%. Also, our local-based matheuristics presented small average
gaps which are better than the MIP models in some larger instances.
