# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
## 2 Preliminaries  
### Notation  
Given a metric space on vertices \(V\), where the travel time between vertices \(x_{1}\in V\) and \(x_{2}\in V\) is denoted by \(w(x_{1},x_{2})\), note that the travel times \(w(x_{1},x_{2})\) for all \(x_{1},x_{2}\in V\) are non-negative, symmetric, and satisfy the triangle inequality. Furthermore, we extended the notation of travel time between two locations to the travel time of a path: \(w(x_{1},x_{2},\ldots,x_{k})=\sum_{i=1}^{k-1}w(x_{i},x_{i+1})\). In the ride-sharing problem, we are given \(n\) cars, denoted by \(D=\{1,2,\ldots,n\}\), each car \(k\) consisting of its location \(d_{k}\in V\) and \(m\) requests \(R=\{r_{1},r_{2},\ldots,r_{m}\}\), each \(r_{i}\) consisting of a source (pick-up location) and destination (drop \begin{table}
\begin{tabular}{c c} \hline \hline
**Problem** & **TA** \\ \hline CS\({}_{sum}\) & \((2c-1)\)\({}^{*}\) (Theorem 1) \\ CS\({}_{sum,s=t}\) & \((2c-1)\)\({}^{*}\) (Theorem 1) \\ CS\({}_{lat}\) & \(c\)\({}^{*}\) (Theorem 2) \\ CS\({}_{lat,s=t}\) & \(c\)\({}^{*}\) (Theorem 2) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Overview of our results for ride-sharing problems with \(c\geq 2\). \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Problem** & **MA** & **TA** & **CA** \\ \hline CS\({}_{sum}\) & 2 \({}^{*}\) (Theorem 3) & 3 \({}^{*}\) (Theorem 1) & 2 \({}^{*}\) (Theorem 6) \\ CS\({}_{sum,s=t}\) & 1.5 \({}^{*}\) (Theorem 4) & 3 \({}^{*}\) (Theorem 1) & 7/5 \({}^{*}\) (Theorem 7) \\ CS\({}_{lat}\) & 2 \({}^{*}\) (Theorem 5) & 2 \({}^{*}\) (Theorem 2) & 5/3 (Theorem 8) \\ CS\({}_{lat,s=t}\)off location) pair \((s_{i},t_{i})\in V\times V\). Each car can serve at most \(c\) requests. We want to find an _allocation:_  
\[M=\{(k,R_{k}):k\in D,R_{k}\subseteq R,|R_{k}|\leq c,R_{1},R_{2},..,R_{n}\text{ are pairwise disjoint}\},\]  
serving the maximum number of requests while minimizing the total travel time or minimizing the total latency. In the basic setting, we suppose \(m=c\cdot n\) (see Section 3.3 for the case \(m<c\cdot n\) and \(m>c\cdot n\)); thus, \(|R_{k}|=c\) holds for all \(k\in D\) of any feasible solution. We now elaborate on these two objectives. **Minimizing total travel time:** For each \((k,R_{k})\in M\) (\(k\in D\)) where \(R_{k}\) contains \(c\) requests, i.e., \(|R_{k}|=c\), we denote the minimum travel time of serving all requests in \(R_{k}\) by \(\text{cost}(k,R_{k})\), i.e., the minimum time (or distance) of visiting all locations \(\{s_{i},t_{i}|\ i\in R_{k}\}\) starting from \(d_{k}\) where \(s_{i}\) is visited before \(t_{i}\). The length of the shortest Hamiltonian path of visiting all locations \(\{s_{i},t_{i}|\ i\in R_{k}\}\) starting from \(s_{r}\) (\(r\in R_{k}\)) with \(s_{i}\) visited before \(t_{i}\) is denoted by \(\text{SHP}(s_{r},R_{k})\). We view \(\text{cost}(k,R_{k})\) as consisting of two parts: one term \(w(d_{k},s_{r})\) expressing the travel time between \(d_{k}\) and the first pick-up location \(s_{r}\) and another term \(\text{SHP}(s_{r},R_{k})\) (\(r\in R_{k}\)) capturing the minimum travel time of visiting all requests starting from \(s_{r}\). (It is true that, in general, the SHP is NP-hard; however, in our case, the parameter \(c\) is a small constant leading to instances of a SHP of bounded size.) The travel time needed to serve requests in \(R_{k}\) (\(k\in D\)) is then given by:  
\[\text{cost}(k,R_{k})=\min_{r\in R_{k}}\{w(d_{k},s_{r})+\text{SHP}(s_{r},R_{k})\}. \tag{1}\]  
We denote the travel time of an allocation \(M\) by:  
\[\text{cost}(M)=\sum_{(k,R_{k})\in M}\text{cost}(k,R_{k}). \tag{2}\]  
In CS\({}_{sum}\) and CS\({}_{sum,s=t}\), the goal is to find an allocation \(M\) that minimizes \(\text{cost}(M)\). **Minimizing total latency:** Here, we focus on the waiting time as perceived by an individual customer, from the moment the car leaves his/her location until the moment the customer reaches his/her drop-off location.