Problem of utility-aware ridesharing on road networks
The problem of utility-aware ridesharing on road networks (URR) is to providing the optimal rider schedules for vehicles to maximize the overall utility. It has been proved that URR problem is NP-hardness by reducing it from the Knapsack problem. There are three efficient approximate algorithms[1].
Background[edit]
Ridersharing allows drivers to share any empty seats with riders.
Algorithms[edit]
- Bilateral arrangement algorithm
Try to assign every rider to the vehicle with the highest utility. If it is available , we simply insert it; otherwise, we try to replace one rider already assigned to the same vehicle. Do it until all the riders are assigned.
- Efficient greedy algorithm
Select greedily a rider-and-vehicle pair with maximum utility efficiency.
- Grouping-based scheduling algorithm
Use the area's construction information and classification of trips to arrange trips with different priorities. In this way, time complexity can be reduced efficiently.
References[edit]
This article "Problem of utility-aware ridesharing on road networks" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Problem of utility-aware ridesharing on road networks. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
