# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
###### Abstract  
Motivated by applications in ride-sharing and truck-delivery, we study the problem of matching a number of requests and assigning them to cars. A number of cars are given, each of which consists of a location and a speed, and a number of requests are given, each of which consists of a pick-up location and a drop-off location. Serving a request means that a car must first visit the pick-up location of the request and then visit the drop-off location. Each car can only serve at most \(c\) requests. Each assignment can yield multiple different serving routes and corresponding serving times, and our goal was to serve the maximum number of requests with the minimum travel time (called CS\({}_{sum}\)) and to serve the maximum number of requests with the minimum total latency (called CS\({}_{lat}\)). In addition, we studied the special case where the pick-up and drop-off locations of a request coincide. Both problems CS\({}_{sum}\) and CS\({}_{lat}\) are APX-hard when \(c\geq 2\). We propose an algorithm, called the transportation algorithm (TA), which is a \((2c-1)\)-approximation (resp. \(c\)-approximation) algorithm for CS\({}_{sum}\) (resp. CS\({}_{lat}\)): these bounds are shown to be tight. We also considered the special case where each car serves exactly two requests, i.e., \(c=2\). In addition to the TA, we investigated another algorithm, called the match-and-assign algorithm (MA). Moreover, we call the algorithm that outputs the best of the two solutions found by the TA and MA the CA. We show that the CA is a two-approximation (resp. \(5/3\)) for CS\({}_{sum}\) (resp. CS\({}_{lat}\)), and these ratios are better than the ratios of the individual algorithms, the TA and MA.  
ride-sharing; approximation algorithms; transportation problem +
Footnote †: journal: _Algorithms_  
definition  
number of requests. Furthermore, it also results in the minimum pollution or emissions. A solution for a given instance is a collection of trips with the minimum total travel time where a car visits all locations of the requests assigned to that car, while visiting the pick-up location of a request before the corresponding drop-off location. We call the ride-sharing problem with the objective of minimizing the total travel time \(\text{CS}_{sum}\) and the special case of \(\text{CS}_{sum}\) where the pick-up and drop-off locations are identical for each request \(\text{CS}_{sum,s=t}\);
* **Minimize total latency:** In this problem, we considered assigning the maximum number of requests to cars, each with no more than \(c\) requests, to minimize the total waiting time, which is the sum of the travel times needed for each individual request (customer or parcel) to arrive at the destination. Passengers or clients care about reaching their destinations as soon as possible. Here, the goal is to obtain a solution that is a collection of trips where the travel time summed over the individual requests is minimum. We call the ride-sharing problem with the objective of minimizing the total latency \(\text{CS}_{lat}\) and the special case of \(\text{CS}_{lat}\) where the pick-up and drop-off locations are identical for each request \(\text{CS}_{lat,s=t}\).