Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as an Incentive

This paper deals with a combinatorial optimization problem that models situations of both dynamic ride-sharing and taxi-sharing. Passengers who want to share a taxi or a ride, use an app to specify their current location, destination and further information such as the earliest departure time, the latest arrival time and the maximum cost they are willing to pay for the ride. Car owners also specify their origin, destination, the leaving time and the maximum accepted delay. Taxi drivers report their location and the time they will start and end the service. All drivers need to define a price per kilometer. The problem is to compute routes, matching requests to vehicles in such a way that ride-sharing is allowed as long as some restrictions are satisfied, such as: the capacity of the vehicle, maximum trip cost of each passenger and maximum delay. The problem is dynamic since new requests arrive on-line and routes can be modified in order to attend them. To solve this dynamic problem, the day is divided in time periods. For each period, an instance of a static problem is created and solved by a greedy randomized adaptive search procedure (GRASP). Experiments with instances based on real data were made to evaluate the heuristics and the proposed method. In our simulations with taxis, passengers paid, on average, almost 30% less than they would pay on private rides.