# Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems
## 3 The Transportation Algorithm and Its Analysis
### Approximation Analysis of the TA  
Let us denote an optimal allocation in \(\mathrm{CS}_{sum}\) by \(M^{*}=\{(k,R_{k}^{*}):k\in D\}\). Let \(M_{R}^{*}=\{R_{k}^{*}:(k,R_{k}^{*})\in M^{*}\}\) denote the collection of \(c\)-tuples of requests in an optimal solution \(M^{*}\). We now establish the worst-case ratios of the \(\mathrm{TA}(v_{1})\) for \(\mathrm{CS}_{sum}\) and \(\mathrm{CS}_{sum,s=t}\). **Theorem 1**. : _The \(\mathrm{TA}(v_{1})\) is a \((2c-1)\)-approximation algorithm for \(\mathrm{CS}_{sum}\). Moreover, there exists an instance 1 of \(\mathrm{CS}_{sum,s=t}\) for which \(\mathrm{cost}(\mathrm{TA}(v_{1})(I))=(2c-1)\cdot\mathrm{cost}(M^{*}(I))\)._  
Proof. : \[\mathrm{cost}(\mathrm{TA}(v_{1}))\leq v_{1}(M_{1})\] (9) \[\leq\sum_{(k,R_{k}^{*})\in M^{*}}\left(\sum_{r\in R_{k}^{*}}w(d_{ k},s_{r},t_{r},d_{k})-\max_{r\in R_{k}^{*}}w(d_{k},t_{r})\right)\] (10) \[=\sum_{(k,R_{k}^{*})\in M^{*}}\left(\sum_{r\in R_{k}^{*}}w(d_{k}, s_{r},t_{r})+\sum_{r\in R_{k}^{*}}w(t_{r},d_{k})-\max_{r\in R_{k}^{*}}w(d_{k},t_{r})\right)\] (11) \[\leq\sum_{(k,R_{k}^{*})\in M^{*}}(2c-1)\ \mathrm{cost}(k,R_{k}^{*})\] (12) \[=(2c-1)\ \mathrm{cost}(M^{*})\] (13)  
We now comment on the validity of the inequalities above. Inequality (9) follows from applying Inequality (7), and Inequality (10) follows from Lemma 2. The final Inequality (12) follows from the fact that for any \(r\in R_{k}^{*}\), \(w(d_{k},t_{r})\leq w(d_{k},s_{r},t_{r})\leq\mathrm{cost}(k,R_{k}^{*})\). To see that the bound \(2c-1\) is tight even for \(\mathrm{CS}_{sum,s=t}\), consider the instance \(I\) depicted in Figure 1. This instance has \(c\) cars \(D=\{k_{1},k_{2},\ldots,k_{c}\}\) with car locations \(\{d_{1},d_{2},\ldots,d_{c}\}\) and \(c^{2}\) requests \(R=\{1,2,\ldots,c^{2}\}\) with locations \(\{s_{1},s_{2},\ldots,s_{c^{2}}\}\) (the pick-up and drop-off locations are identical for each request). Locations corresponding to distinct vertices in Figure 1 are at Travel Time 1. Observe that an optimal solution is \(M^{*}(I)=\{(k_{1},\{1,2,\ldots,c\}),(k_{2},\{c+1,c+2,\ldots,2c\}),\ldots,(k_{c}, \{c(c-1)+1,c(c-1)+2,\ldots,c^{2}\})\}\) with \(\mathrm{cost}(M^{*}(I))=c\). Let us now analyze the performance of \(\mathrm{TA}(v_{1})\) on instance \(I\). Notice that \(\mathrm{TA}(v_{1})\) may assign requests \(\{i,c+i,\ldots,(c-1)c+i\}\) to car \(k_{i}\). In that case, the total cost of \(\mathrm{TA}(v_{1})\) is \(c(2(c-1)+1))=c(2c-1)\), showing tightness. We proceed by establishing the worst-case ratios of the \(\mathrm{TA}(v_{2})\) for \(\mathrm{CS}_{lat}\) and \(\mathrm{CS}_{lat,s=t}\). Again, we assume that an optimal solution to \(\mathrm{CS}_{lat}\) is denoted by \(M^{*}\), and the collection of \(c\)-tuples of requests in \(M^{*}\) is denoted by \(M^{*}_{R}=\{R^{*}_{k}:(k,R^{*}_{k})\in M^{*}\}\). In the following theorem, we index the requests such that, for each \(k\in D\), \(R^{*}_{k}=\{r_{1},r_{2},\ldots,r_{c}\}\). Theorem 2: _The \(\mathrm{TA}(v_{2})\) is a \(c\)-approximation algorithm for \(\mathrm{CS}_{lat}\). Moreover, there exists an instance \(I\) of \(\mathrm{CS}_{lat,s=t}\) for which \(\mathrm{wait}(\mathrm{TA}(v_{2})(I))=c\;\cdot\;\mathrm{wait}(M^{*}(I))\)._  
Proof: \[\mathrm{wait}(\mathrm{TA}(v_{1}))\leq v_{2}(M_{2})\] (14) \[\leq\sum_{(k,R^{*}_{k})\in M^{*}}\sum_{i=1}^{c}((c-i+1)\cdot w(d_ {k_{r}}s_{r_{i}},t_{r_{i}})+(c-i)\cdot w(d_{k_{r}},t_{r_{i}}))\] (15) \[=\sum_{(k,R^{*}_{k})\in M^{*}}\sum_{i=1}^{c}(c\cdot w(d_{k_{r}}s_{ r_{i}},t_{r_{i}})-(i-1)\cdot w(d_{k_{r}}s_{r_{i}},t_{r_{i}})+(c-i)\cdot w(d_{k },t_{r_{i}}))\] (16) \[\leq\sum_{(k,R^{*}_{k})\in M^{*}}\sum_{i=1}^{c}c\cdot w(d_{k_{r}} s_{r_{i}},t_{r_{i}})\] (17) \[\leq\sum_{(k,R_{k}^{*})\in M^{*}}\left(\sum_{r\in R_{k}^{*}}w(d_{ k},s_{r},t_{r},d_{k})-\max_{r\in R_{k}^{*}}w(d_{k},t_{r})\right)\]0 (18) \[\leq\sum_{(k,R_{k}^{*})\in M^{*}}\left(\sum_{r\in R_{k}^{*}}w(d_{ k},s_{r},t_{r},d_{k})-\max_{r\in R_{k}^{*}}w(d_{k},t_{r})\right)\]1 (19)  
We now comment on the validity of the inequalities above. Inequality (14) follows from applying Inequality (8), and Inequality (15) follows from Lemma 4.