# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
### Related Work  
There is a growing amount of literature related to ride-sharing (see [3] for a survey). In a ride-sharing system, a number of cars are provided to serve requests from customers in a fixed period of time. Typically, there are four types of ride-sharing models: one-to-one, meaning that each car serves a single request at a time (see [4; 5; 6; 7]); one-to-many, meaning that each car can serve multiple requests at the same time (see [8; 9]); many-to-one, meaning that one request can be served consecutively by multiple cars ([10]); many-to-many, which is a combination of the previous two models ([11]). The ride-sharing problem is to match requests and cars while either minimizing the cost (see [8; 9]) or maximizing the profit (see [5; 6; 7; 10]). In this paper, we study a ride-sharing problem of the one-to-many type with the objective of minimizing the cost. Different versions of ride-sharing problems have been studied. [PERSON] et al. [12] and [PERSON] et al. [13] estimated what fleet size is appropriate for a city considering the cost of cars, a maximum waiting time for a customer, and the extra expense of moving cars. [PERSON] et al. [14] studied the problem of assigning cars to customers in real-time to minimize the expected total delivery cost. For a dynamic ride-sharing problem, [PERSON] et al. [15] analyzed and showed that a small increase in the flexibility of either the cars or the customers can significantly increase performance. Furthermore, [PERSON] et al. [16] introduced the notion of the stability of a ride-sharing system, and they presented methods to establish stable or nearly stable solutions. Considering the online ride-sharing model, [PERSON] et al. [17] studied the problem of matching requests while they arrive one by one and each of them must be either matched to another request within a prespecified period of time or discarded. Each request can be matched at most once and yields a positive profit. To maximize the total profit while requests arrive in an adversarial model, they provided a randomized four-competitive algorithm. [PERSON] et al. [18] studied a special case of the online version of the ride-sharing problem, such that the vehicles have to return to their depot after serving a number of requests. [PERSON] and [PERSON] [19] designed algorithms for the online ride-sharing problem under both the adversarial model and the random arrival model. [PERSON] and [PERSON] [20] studied the ride-sharing problem with arbitrary capacity while relaxing the assumption of serving all requests. They used an LP-based randomized rounding algorithm to obtain a solution, such that the expected fraction of unassigned requests was at most \(1/e\), while the total cost of serving assigned requests was no more than the optimal solution. This paper deals with a setting where the maximum number of requests needs to be assigned to the cars such that each car serves no more than \(c\) requests while minimizing the total travel time (CS\({}_{sum}\)) or minimizing the total waiting time (CS\({}_{lat}\)). As far as we are aware, this particular ride-sharing problem has not been extensively studied, especially for the latency criterion, i.e., CS\({}_{lat}\). Notice that when \(c=1\), the ride-sharing problems CS\({}_{sum}\) and CS\({}_{lat}\) become minimum weight assignment problems, and an optimal solution can be found in \(O(|D|^{3})\) (see, e.g., [21]). [PERSON] and [PERSON] [9] considered CS\({}_{sum}\) with \(c=2\) and gave a 2.5-approximation algorithm for it. [PERSON] and [PERSON] [22] proposed approximation algorithms for four versions of the problem, while still assuming \(c=2\). Here, we generalize the ride-sharing problem to a problem involving any arbitrary constant \(c\geq 2\). In fact, both CS\({}_{sum}\) and CS\({}_{lat}\) with \(c=2\) are a special case of the so-called two-to-one assignment problem (2-1-AP) investigated by [PERSON] et al. [23].