# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
## 3 The Transportation Algorithm and Its Analysis
### The Transportation Algorithm  
In this section, we present the transportation algorithm. The idea of the algorithm is to assign to each car \(k\in D\)\(c\) requests based only on the travel times between the car locations \(d_{k}\) and the request locations \(s_{r},t_{r}\), thereby ignoring travel times between different request locations. We implemented this idea by replacing each car \(k\in D\) by \(c\) virtual cars \(\{\gamma_{1}(k),\ldots,\gamma_{c}(k)\}\), resulting in car sets \(\Gamma=\{\gamma_{1}(1),\ldots,\gamma_{c}(1),\ldots,\gamma_{1}(n),\ldots,\gamma _{c}(n)\}\) with \(|\Gamma|=c\cdot n\). Next, we assigned \(c\cdot n\) requests to the \(c\cdot n\) cars using a particular definition of the cost \(v_{1}(\gamma_{i}(k),r)\) (or \(v_{2}(\gamma_{i}(k),r)\)) between a request \(r\in R\) and a car \(\gamma_{i}(k)\in\Gamma\):  
\[v_{1}(\gamma_{i}(k),r)= \begin{cases}w(d_{k},s_{r},t_{r})+w(t_{r},d_{k})&\text {if }i<c\\ w(d_{k},s_{r},t_{r})&\text{if }i=c\end{cases}  \tag{5}\]  
\[v_{2}(\gamma_{i}(k),r)= \begin{cases}(c-i+1)w(d_{k},s_{r},t_{r})+(c-i)w(t_{r},d _{k})&\text{if }i<c\\ w(d_{k},s_{r},t_{r})&\text{if }i=c\end{cases} . \tag{6}\]  
Next, we introduce how to assign \(c\cdot n\) requests to the \(c\cdot n\) cars. As is showed in Algorithm 1. ```
1:Construct a graph: Let \(G_{1}\equiv(\Gamma\cup R,v_{1})\) (resp. \(G_{2}\equiv(\Gamma\cup R,v_{2})\)) be the complete bipartite graph with left vertex-set \(\Gamma\), right vertex-set \(R\), and edge weights \(v_{1}(\gamma_{i}(k),r)\) (resp. \(v_{2}(\gamma_{i}(k),r)\)) for \(\gamma_{i}(k)\in\Gamma\) and \(r\in R\). 2:Find a min-weight assignment: Find a minimum weight assignment \(M_{1}\) (resp, \(M_{2}\)) in \(G_{1}\equiv(\Gamma\cup R,v_{1})\) (resp, \(G_{2}\equiv(\Gamma\cup R,v_{2})\)) with weight \(v_{1}(M_{1})\) (resp. \(v_{2}(M_{2})\)). 3:Output: \(\text{TA}(v_{1})\equiv\{(k,\{r_{1},\ldots,r_{c}\}):(\gamma_{1}(k),r_{1}), \ldots,(\gamma_{c}(k),r_{c})\in M_{1}\}\). \(\text{TA}(v_{2})\equiv\{(k,\{r_{1},\ldots,r_{c}\}):(\gamma_{1}(k),r_{1}), \ldots,(\gamma_{c}(k),r_{c})\in M_{2}\}\). ```  
**Algorithm 1** Transportation algorithm (TA(\(v\))). A solution is then found by letting car \(k\in D\) serve the requests assigned to virtual cars \(\{\gamma_{1}(k),\ldots,\gamma_{c}(k)\}\). Let \(R_{k}=\{r_{1},r_{2},\ldots,r_{c}\}\) (\(k\in D\)) denote the requests assigned to a car \(k\), where request \(r_{i}\in R_{k}\) is assigned to \(\gamma_{i}(k)\). In our algorithm, two minimum weight assignments based on these costs are found: \(M_{1}\) with weight \(v_{1}(M_{1})\) and \(M_{2}\) with weight \(v_{2}(M_{2})\). We use \(M_{1}\) to construct a solution for CS\({}_{sum}\) and \(M_{2}\) to construct a solution for CS\({}_{lat}\). Observe that \(v_{1}(M_{1})=\sum_{(\gamma_{i}(k),r)\in M_{1}}v_{1}(\gamma_{i}(k),r)\). This amounts to a solution where each car \(k\in D\) travels according to the following path:  
\[d_{k}\to s_{r_{1}}\to t_{r_{1}}\to d_{k}\to s_{r_{2}}\to t_{r_{2}}\to \cdots\to d_{k}\to s_{r_{c}}\to t_{r_{c}}.\]  
Notice that, due to the triangle inequality, the cost of such a path will not increase by \"short-cutting\" the path, i.e., by traveling from each \(t_{r_{i}}\) directly to \(s_{r_{i+1}}\):  
\[d_{k}\to s_{r_{1}}\to t_{r_{1}}\to s_{r_{2}}\to t_{r_{2}}\to\cdots\to t_{r_{c-1 }}\to s_{r_{c}}\to t_{r_{c}}.\]  
In fact, we use \(\text{TA}(v_{1})\) to denote this resulting solution found by the TA for CS\({}_{sum}\), with cost(TA(\(v_{1}\))) denoting its cost. We conclude:  
\[\text{cost}(\text{TA}(v_{1}))\leq v_{1}(M_{1}). \tag{7}\]A similar observation can be made with respect to \(M_{2}\). The quantity \(v_{2}(M_{2})\) collects the waiting time of all requests by following, for each car \(k\in D\), the path:  
\[d_{k}\to s_{r_{1}}\to t_{r_{1}}\to d_{k}\to s_{r_{2}}\to t_{r_{2}}\to\cdots\to d_{k} \to s_{r_{c}}\to t_{r_{c}}.\]  
As argued above, shortcutting gives us then a feasible solution for an instance of \(\text{CS}_{lat}\) we denote by \(\text{TA}(v_{2})\) with cost \(\text{wait}(\text{TA}(v_{2}))\).