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 ${\mathrm{CS}}_{sum}$) and to serve the maximum number of requests with the minimum total latency (called ${\mathrm{CS}}_{lat}$). In addition, we studied the special case where the pick-up and drop-off locations of a request coincide. Both problems ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{lat}$ are APX-hard when $c\ge 2$. We propose an algorithm, called the transportation algorithm (TA), which is a $(2c-1)$-approximation (resp. c-approximation) algorithm for ${\mathrm{CS}}_{sum}$ (resp. ${\mathrm{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 ${\mathrm{CS}}_{sum}$ (resp. ${\mathrm{CS}}_{lat}$), and these ratios are better than the ratios of the individual algorithms, the TA and MA.

1. Introduction

In the multi-capacity ride-sharing problem, we are given a set of cars (or trucks) D, each car $k\in D$ located at location $d_k$, and a set of requests R, each request $r\in R$ consisting of a source $s_r$ (pick-up location) and a destination $t_r$ (drop-off location). Travel times are given between each pair of locations. Each car $k\in D$ has capacity c. Serving a request means that a car first visits the pick-up location of the request (customer or parcel) and then the drop-off location. Each car can serve multiple requests at the same time. This offers the opportunity to share rides, which may reduce the travel time or traffic congestion. This paper is concerned with two objectives when assigning the maximum number of requests ($min\left\{\right|R|,c·|D\left|\right\}$ requests): one is to assign requests to the cars such that each car serves at most c requests while minimizing the total travel time, and the other problem is to assign requests to the cars such that each car serves at most c requests while minimizing the total waiting time (called total latency) incurred by customers that have submitted the requests. We now provide more insight into these two objectives:

• Minimize total travel time: In this problem, we considered assigning the maximum number of requests to cars, each with no more than c requests, to minimize the total travel time, which is the sum of the travel times a car drives to serve its requests. Viewed from the ride-sharing company or drivers, minimizing the total travel time is the most important, since it results in minimizing the costs while serving the maximum 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 ${\mathrm{CS}}_{sum}$ and the special case of ${\mathrm{CS}}_{sum}$ where the pick-up and drop-off locations are identical for each request ${\mathrm{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 ${\mathrm{CS}}_{lat}$ and the special case of ${\mathrm{CS}}_{lat}$ where the pick-up and drop-off locations are identical for each request ${\mathrm{CS}}_{lat,s=t}$.

1.1. Motivation

Many ride-sharing companies (see [1]) provide a service (carpooling, ride-sharing, etc.) where customers submit their requests and then wait for the company to assign them a car. Consider a large number of requests in a working day morning, each consisting of a pick-up and a drop-off location. The company has a number of available cars whose locations and capacity c are known. The value of capacity c can be seen as the capacity of each car over time, i.e., the number of requests a car can accommodate in a relevant period of time. This value may well differ from the instantaneous capacity of a car (say the number of seats), as a pair of requests served by the same car may not be served simultaneously as one request is dropped off before the other request is picked up. In order to achieve a balanced allocation of requests to cars, each car receives no more than c requests. The task then is to assign the maximum number requests to available cars with respect to the capacity constraint.

It is a fact, however, that in many practical situations, “each request is allowed to occupy at most two seats in a car” (see Uber [1]). A regular vehicle has 4–8 seats; thus, only a limited number of requests can be combined in a single vehicle; this can be modeled by taking $c\le 4$.

Consider the application of our problem in the area of collective transport. For instance, the company TransVision [2] provides transport service for specific groups of people (patients, commuters, etc.), and they organize collective transport by collecting requests in a particular region of The Netherlands in advance, combine these requests, and assign them to some regular transport companies. To access their service, customers must make their request the evening before the day of the actual transport; the number of requests for a day often exceeds 5000. In this application, each server (car, bus, etc.) may pick up more than four requests during its working period; hence, a value of $c>4$ can be appropriate.

We can capture the above scenarios by the following problem: There is a set of customers who have specified their pick-up locations and drop-off locations to the vehicle provider, and the provider has a set of cars (also with drivers) that have a specified location and capacity c. The task, in this paper, is to assign customers to vehicles without exceeding the vehicles’ capacities and plan a service route for each of the vehicles based on optimization criteria, either minimizing the total travel time in ${\mathrm{CS}}_{sum}$ or minimizing the total latency in ${\mathrm{CS}}_{lat}$.

The problems ${\mathrm{CS}}_{sum,s=t}$ and ${\mathrm{CS}}_{lat,s=t}$ are natural special cases of ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{lat}$, respectively, and can be used to model situations where parcels have to be delivered to clients (whose location is known and fixed). For instance, one can imagine a retailer sending out trucks to satisfy clients’ demands where each truck is used to satisfy multiple clients.

1.2. 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. Alonso-Mora et al. [12] and Pavone 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. Agatz 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, Stiglic 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, Wang 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, Ashlagi 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. Lowalekar 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.  [19] designed algorithms for the online ride-sharing problem under both the adversarial model and the random arrival model.

Mori and Samaranayake [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 (${\mathrm{CS}}_{sum}$) or minimizing the total waiting time (${\mathrm{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., ${\mathrm{CS}}_{lat}$. Notice that when $c=1$, the ride-sharing problems ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{lat}$ become minimum weight assignment problems, and an optimal solution can be found in $O\left(\right|D{|}^3)$ (see, e.g., [21]). Bei and Zhang [9] considered ${\mathrm{CS}}_{sum}$ with $c=2$ and gave a $2.5$-approximation algorithm for it. Luo and Spieksma [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\ge 2$.

In fact, both ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{lat}$ with $c=2$ are a special case of the so-called two-to-one assignment problem (2-1-AP) investigated by Goossens et al. [23]. Given a set G of n green elements and a set R of $2n$ red elements, we call a triple a set of three elements that consists of a single green element and two red elements. Each triple has a non-negative cost-efficient, and the goal of the 2-1-AP problem is to find a collection of triples such that each element is covered exactly once while minimizing the sum of the corresponding cost coefficients. In the context of our ride-sharing problem with $c=2$, the green elements represent the cars, and the red elements represent the requests. The arguments presented in [23] allowed us to conclude that both ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{lat}$ are APX-hard, already for $c=2$.

For the special case of 2-1-AP where the cost of each triple $(i,j,k)$ is defined as the sum of the three corresponding distances, i.e., $\mathrm{cost}(i,j,k)=d_{ij}+d_{jk}+d_{ki}$, where the distances d satisfy the triangle inequality, Goossens et al. [23] gave an algorithm with the approximation ratio of $4/3$. The definition of the cost coefficients in ${\mathrm{CS}}_{sum}$, as well as in ${\mathrm{CS}}_{lat}$ differs from the above expression for $cost(i,j,k)$; we refer to Section 4 for a precise definition.

1.3. Our Results

We formulated and analyzed an algorithm, called the transportation algorithm (TA), that outputs a feasible solution to each of the four problems described above. This transportation algorithm belongs to a type of heuristics, called hub heuristics, which have been analyzed in the context of the multi-index assignment and multi-index transportation problems (see [24,25]). We identified the worst-case ratios of the TA for the four problems and show them to be tight (see [26] for the appropriate terminology). An overview of these results is shown in

Table 1. Overview of our results for ride-sharing problems with $c\ge 2$.

Problem	TA
${\mathrm{CS}}_{sum}$	$(2c-1)$${}^{*}$ (Theorem 1)
${\mathrm{CS}}_{sum,s=t}$	$(2c-1)$${}^{*}$ (Theorem 1)
${\mathrm{CS}}_{lat}$	c${}^{*}$ (Theorem 2)
${\mathrm{CS}}_{lat,s=t}$	c${}^{*}$ (Theorem 2)

, where “${}^{*}$” means that the corresponding worst-case ratio is tight.

For the case $c=2$, we propose a so-called match-and-assign algorithm, the MA. We also define an algorithm, the CA, that consists of outputting the better of the solutions found by the TA and MA. An overview of the results for $c=2$ is shown in

Table 2. Overview of our results for ride-sharing problems with $c=2$.

Problem	MA	TA	CA
${\mathrm{CS}}_{sum}$	2 ${}^{*}$ (Theorem 3)	3 ${}^{*}$ (Theorem 1)	2 ${}^{*}$ (Theorem 6)
${\mathrm{CS}}_{sum,s=t}$	1.5 ${}^{*}$ (Theorem 4)	3 ${}^{*}$ (Theorem 1)	7/5 ${}^{*}$ (Theorem 7)
${\mathrm{CS}}_{lat}$	2 ${}^{*}$ (Theorem 5)	2 ${}^{*}$ (Theorem 2)	5/3 (Theorem 8)
${\mathrm{CS}}_{lat,s=t}$	2 ${}^{*}$ (Theorem 5)	2 ${}^{*}$ (Theorem 2)	3/2 ${}^{*}$ (Theorem 9)

(see also [22]). Notice that for ${\mathrm{CS}}_{sum,s=t}$, ${\mathrm{CS}}_{lat}$, and ${\mathrm{CS}}_{lat,s=t}$, the worst-case ratio of the combined algorithm (CA) is strictly better than each of the two worst-case ratios of the individual algorithms f which CA is composed.

The paper is organized as follows. In Section 2, we give a precise problem description. In Section 3, we present the transportation algorithm (TA) and analyze its performance for both ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{lat}$. In Section 4, we consider the special case where each car serves exactly two requests. We propose the match-and-assign algorithm (MA) and analyze the performance of the MA and CA (the better solution of the MA and TA) for both ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{lat}$. Section 5 concludes the paper.

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,\cdots ,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,\cdots ,n\}$, each car k consisting of its location $d_k\in V$ and m requests $R=\{r_1,r_2,\cdots ,r_m\}$, each $r_i$ consisting of a source (pick-up location) and destination (drop-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:

$$\begin{array}{c}\hfill M=\{(k,R_k):k\in D,R_k\subseteq R,|R_k|\le c,R_1,R_2,..,R_n\mathrm{are}\mathrm{pairwise}\mathrm{disjoint}\},\end{array}$$

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·n$ (see Section 3.3 for the case $m<c·n$ and $m>c·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 $\mathrm{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 $\mathrm{SHP}(s_r,R_k)$. We view $\mathrm{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 $\mathrm{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:

$$\mathrm{cost}(k,R_k)=\underset{r\in R_k}{min}\{w(d_k,s_r)+\mathrm{SHP}(s_r,R_k)\}.$$

(1)

We denote the travel time of an allocation M by:

$$\mathrm{cost}\left(M\right)=\sum _{(k,R_k)\in M}\mathrm{cost}(k,R_k).$$

(2)

In ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{sum,s=t}$, the goal is to find an allocation M that minimizes $\mathrm{cost}\left(M\right)$.

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. 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 total waiting time of all requests in $R_k$ by $\mathrm{wait}(k,R_k)$, i.e., the sum of the times to reach all drop-off locations $t_r$ ($r\in R_k$) following a path that visits all locations $\{s_i,t_i|i\in R_k\}$ starting from $d_k$ while $s_i$ is visited before $t_i$. We view $\mathrm{wait}(k,R_k)$ as consisting of two parts: one term $c·w(d_k,s_r)$ expressing the waiting time between $d_k$ and the first pick-up location $s_r$; another term $\mathrm{SHWP}(s_r,R_k)$ capturing the sum of waiting times from the first pick-up location $s_r$ to every other drop-off location, minimized over all feasible ways of traveling through the locations in $R_k$. The latency needed to serve requests in $R_k$ ($k\in D$) is then given by:

$$\mathrm{wait}(k,R_k)=\underset{r\in R_k}{min}\{c·w(d_k,s_r)+\mathrm{SHWP}(s_r,R_k)\}.$$

(3)

We denote the latency of an allocation M by:

$$\mathrm{wait}\left(M\right)=\sum _{(k,R_k)\in M}\mathrm{wait}(k,R_k).$$

(4)

Thus, in ${\mathrm{CS}}_{lat}$ and ${\mathrm{CS}}_{lat,s=t}$, the goal is to find an allocation M that minimizes $\mathrm{wait}\left(M\right)$.

Another variant of the ride-sharing problem considering the latency objective is counted with respect to the pick-up location rather than the drop-off location in ${\mathrm{CS}}_{lat}$. In this setting, the drop-off location clearly becomes irrelevant to the objective, and our approximation results for ${\mathrm{CS}}_{lat,s=t}$ become valid for this variant.

3. The Transportation Algorithm and Its Analysis

We describe the transportation algorithm in Section 3.1 and analyze its performance for ${\mathrm{CS}}_{sum}$, ${\mathrm{CS}}_{sum,s=t}$, ${\mathrm{CS}}_{lat}$, and ${\mathrm{CS}}_{lat,s=t}$ in Section 3.2.

3.1. 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\left(k\right),\dots ,{\gamma }_c\left(k\right)\}$, resulting in car sets $\Gamma =\{{\gamma }_1\left(1\right),\cdots ,{\gamma }_c\left(1\right),\cdots ,{\gamma }_1\left(n\right),\cdots ,{\gamma }_c\left(n\right)\}$ with $\left|\Gamma \right|=c·n$. Next, we assigned $c·n$ requests to the $c·n$ cars using a particular definition of the cost $v_1({\gamma }_i\left(k\right),r)$ (or $v_2({\gamma }_i\left(k\right),r)$) between a request $r\in R$ and a car ${\gamma }_i\left(k\right)\in \Gamma$:

$$v_1({\gamma }_i\left(k\right),r)=\left\{\begin{array}{cc}w(d_k,s_r,t_r)+w(t_r,d_k)\hfill & ifi<c\hfill \\ w(d_k,s_r,t_r)\hfill & ifi=c\hfill \end{array}\right..$$

(5)

$$v_2({\gamma }_i\left(k\right),r)=\left\{\begin{array}{cc}(c-i+1)w(d_k,s_r,t_r)+(c-i)w(t_r,d_k)\hfill & ifi<c\hfill \\ w(d_k,s_r,t_r)\hfill & ifi=c\hfill \end{array}\right..$$

(6)

Next, we introduce how to assign $c·n$ requests to the $c·n$ cars. As is showed in Algorithm 1.

Algorithm 1 Transportation algorithm ($\mathrm{TA}\left(v\right)$).

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\left(k\right),r)$ (resp. $v_2({\gamma }_i\left(k\right),r)$) for ${\gamma }_i\left(k\right)\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\left(M_1\right)$ (resp. $v_2\left(M_2\right)$). 3: Output:$\mathrm{TA}\left(v_1\right)\equiv \{(k,\{r_1,\cdots ,r_c\}):({\gamma }_1\left(k\right),r_1),\cdots ,({\gamma }_c\left(k\right),r_c)\in M_1\}$. $\mathrm{TA}\left(v_2\right)\equiv \{(k,\{r_1,\cdots ,r_c\}):({\gamma }_1\left(k\right),r_1),\cdots ,({\gamma }_c\left(k\right),r_c)\in M_2\}$.

A solution is then found by letting car $k\in D$ serve the requests assigned to virtual cars $\{{\gamma }_1\left(k\right),\dots ,{\gamma }_c\left(k\right)\}$. Let $R_k=\{r_1,r_2,\cdots ,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\left(k\right)$.

In our algorithm, two minimum weight assignments based on these costs are found: $M_1$ with weight $v_1\left(M_1\right)$ and $M_2$ with weight $v_2\left(M_2\right)$. We use $M_1$ to construct a solution for ${\mathrm{CS}}_{sum}$ and $M_2$ to construct a solution for ${\mathrm{CS}}_{lat}$.

Observe that $v_1\left(M_1\right)={\sum }_{({\gamma }_i\left(k\right),r)\in M_1}{v}_1({\gamma }_i\left(k\right),r)$. This amounts to a solution where each car $k\in D$ travels according to the following path:

$$\begin{array}{c}\hfill 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}.\end{array}$$

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}}$:

$$\begin{array}{c}\hfill 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}.\end{array}$$

In fact, we use $\mathrm{TA}\left(v_1\right)$ to denote this resulting solution found by the TA for ${\mathrm{CS}}_{sum}$, with $\mathrm{cost}\left(\mathrm{TA}\left(v_1\right)\right)$ denoting its cost.

We conclude:

$$\mathrm{cost}\left(\mathrm{TA}\left(v_1\right)\right)\le v_1\left(M_1\right).$$

(7)

A similar observation can be made with respect to $M_2$. The quantity $v_2\left(M_2\right)$ collects the waiting time of all requests by following, for each car $k\in D$, the path:

$$\begin{array}{c}\hfill 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}.\end{array}$$

As argued above, shortcutting gives us then a feasible solution for an instance of ${\mathrm{CS}}_{lat}$ we denote by $\mathrm{TA}\left(v_2\right)$ with cost $\mathrm{wait}\left(\mathrm{TA}\left(v_2\right)\right)$. We have:

$$\mathrm{wait}\left(\mathrm{TA}\left(v_2\right)\right)\le v_2\left(M_2\right).$$

(8)

Recall that our problem does not force the driver to return to the original position. This implies that the cost of a driver when serving a set of request $R_k$ does not include the time from the last drop-off location to the driver’s original location. This explains why in the expression for $v_1\left(M_1\right)$ (also, $v_2\left(M_2\right)$), we can subtract the corresponding travel time from the total travel time. We now give two lemmas concerning $v_1\left(M_1\right)$ (which we need to prove Theorem 1) and two more lemmas concerning $v_2\left(M_2\right)$ (which we need to prove Theorem 2).

Lemma 1.

For any $c\ge 2$, we have:

$$\begin{array}{c}\hfill v_1\left(M_1\right)=\sum _{(k,R_k)\in \mathrm{TA}\left(v_1\right)}\left(\sum _{r\in R_k}w(d_k,s_r,t_r,d_k)-\underset{r\in R_k}{max}w(d_k,t_r)\right).\end{array}$$

Proof. 

We claim that $v_1\left(M_1\right)$ is minimized if and only if, for each car $k\in D$ and $({\gamma }_c\left(k\right),r_c)\in M_1$, $r_c=arg{max}_{r\in R_k}w(d_k,t_r)$. If this claim holds, then based on the definition of the cost $v_1(·,·)$, we have $v_1(k,R_k)={\sum }_{r\in R_k}w(d_k,s_r,t_r,d_k)-w(d_k,t_{r_c})={\sum }_{r\in R_k}w(d_k,s_r,t_r,d_k)-{max}_{r\in R_k}w(d_k,t_r)$, and thus:

$$\begin{array}{c}\hfill v_1\left(M_1\right)=\sum _{(k,R_k)\in \mathrm{TA}\left(v_1\right)}\left(\sum _{r\in R_k}w(d_k,s_r,t_r,d_k)-\underset{r\in R_k}{max}w(d_k,t_r)\right).\end{array}$$

It remains to prove the claim. Consider any $R_k=\{r_1,r_2,\cdots ,r_c\}$ for car $k\in D$. We prove that $v_1\left(M_1\right)$ is minimized if and only if $w(d_k,t_{r_c})\ge w(d_k,t_{r_x})$ for all $r_x\in R_k$.

Necessary condition: Since $v_1(k,R_k)$ is minimized, we have $w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x})+w(d_k,s_{r_c},t_{r_c})\le w(d_k,s_{r_c},t_{r_c})+w(d_k,t_{r_c})+w(d_k,s_{r_x},t_{r_x})$ based on the definition of $v_1$ (see Equation (5)), then $w(d_k,t_{r_x})\le w(d_k,t_{r_c})$ holds.

Sufficient condition: Since $w(d_k,t_{r_c})\ge w(d_k,t_{r_x})$, then $w(d_k,s_{r_c},t_{r_c})+w(d_k,t_{r_c})+w(d_k,$$s_{r_x},t_{r_x})\ge w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x})+w(d_k,s_{r_c},t_{r_c})$, and that means $v_1\left(M_1\right)$ is minimized as $r_c=arg{max}_{r\in R_k}w(d_k,t_r)$.    □

From the above lemma and the fact that $M_1$ is a minimum weight assignment in $G_1\equiv (\Gamma \cup R,v_1)$, we have the following lemma:

Lemma 2.

For $c\ge 2$ and for each allocation M, we have:

$$\begin{array}{c}\hfill v_1\left(M_1\right)\le \sum _{(k,R_k)\in M}\left(\sum _{r\in R_k}w(d_k,s_r,t_r,d_k)-\underset{r\in R_k}{max}w(d_k,t_r)\right).\end{array}$$

We now provide two lemmas concerning $v_2\left(M_2\right)$. In the statement of these lemmas, we index the requests such that, for each $k\in D$, $R_k=\{r_1,r_2,\cdots ,r_c\}$.

Lemma 3.

For any $c\ge 2$, for each car $k\in D$ and $\forall r_x,r_y\in R_k$ with $x<y$, $w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x})\le w(d_k,s_{r_y},t_{r_y})+w(d_k,t_{r_y})$.

Proof. 

We claim that $v_2\left(M_2\right)$ is minimized if and only if for each car $k\in D$ and $\forall r_x,r_y\in R_k=\{r_1,r_2,\cdots ,r_c\}$ with $x<y$, $w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x})\le w(d_k,s_{r_y},t_{r_y})+w(d_k,t_{r_y})$. Consider $\forall r_x,r_y\in R_k=\{r_1,r_2,\cdots ,r_c\}$ with $x<y$ for car $k\in D$. We prove that $v_2\left(M_2\right)$ is minimized if and only if $w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x})\le w(d_k,s_{r_y},t_{r_y})+w(d_k,t_{r_y})$.

Necessary condition: Since $v_2\left(M_2\right)$ is minimized, based on definition of cost $v_2(·,·)$, we have:

$$\begin{array}{cc}& (c-x+1)w(d_k,s_{r_x},t_{r_x})+(c-x)w(t_{r_x},d_k)+(c-y+1)w(d_k,s_{r_y},t_{r_y})+(c-y)w(t_{r_y},d_k)\\ & \le (c-x+1)w(d_k,s_{r_y},t_{r_y})+(c-x)w(t_{r_y},d_k)+(c-y+1)w(d_k,s_{r_x},t_{r_x})+(c-y)w(t_{r_x},d_k).\end{array}$$

$$⟺(y-x)(w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x}))\le (y-x)(w(d_k,s_{r_y},t_{r_y})+w(d_k,t_{r_y}))$$

Thus, $w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x})\le w(d_k,s_{r_y},t_{r_y})+w(d_k,t_{r_y})$, since $x<y$.

Sufficient condition: According to the above statement, the condition $w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x})\le w(d_k,s_{r_y},t_{r_y})+w(d_k,t_{r_y})$ implies that $v_2\left(M_2\right)$ is minimized.    □

Since $M_2$ is a minimum weight assignment in $G_2\equiv (\Gamma \cup R,v_2)$, we have the following lemma:

Lemma 4.

For $c\ge 2$ and for each allocation M, we have:

$$\begin{array}{c}\hfill v_2\left(M_2\right)\le \sum _{(k,R_k)\in M}\sum _{i=1}^c\left((c-i+1)·w(d_k,s_{r_i},t_{r_i})+(c-i)·w(d_k,t_{r_i})\right).\end{array}$$

3.2. 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}\left(v_1\right)$ for ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{sum,s=t}$.

Theorem 1.

The $\mathrm{TA}\left(v_1\right)$ is a $(2c-1)$-approximation algorithm for ${\mathrm{CS}}_{sum}$. Moreover, there exists an instance I of ${\mathrm{CS}}_{sum,s=t}$ for which $\mathrm{cost}\left(\mathrm{TA}\left(v_1\right)\left(I\right)\right)=(2c-1)·\mathrm{cost}\left(M^{*}\left(I\right)\right)$.

Proof. 

$$\begin{array}{cc}\hfill & \mathrm{cost}\left(\mathrm{TA}\left(v_1\right)\right)\le v_1\left(M_1\right)\hfill \end{array}$$

(9)

$$\begin{array}{cc}\hfill & \le \sum _{(k,R_k^{*})\in M^{*}}\left(\sum _{r\in R_k^{*}}w(d_k,s_r,t_r,d_k)-\underset{r\in R_k^{*}}{max}w(d_k,t_r)\right)\hfill \end{array}$$

(10)

$$\begin{array}{cc}\hfill & =\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)-\underset{r\in R_k^{*}}{max}w(d_k,t_r)\right)\hfill \end{array}$$

(11)

$$\begin{array}{cc}\hfill & \le \sum _{(k,R_k^{*})\in M^{*}}(2c-1)\mathrm{cost}(k,R_k^{*})\hfill \end{array}$$

(12)

$$\begin{array}{cc}\hfill & =(2c-1)\mathrm{cost}\left(M^{*}\right)\hfill \end{array}$$

(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)\le w(d_k,s_r,t_r)\le \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,\cdots ,k_c\}$ with car locations $\{d_1,d_2,\cdots ,d_c\}$ and $c^2$ requests $R=\{1,2,\cdots ,c^2\}$ with locations $\{s_1,s_2,\cdots ,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^{*}\left(I\right)=\{(k_1,\{1,2,\cdots ,c\}),(k_2,\{c+1,c+2,\cdots ,2c\}),\cdots ,(k_c,\{c(c-1)+1,c(c-1)+2,\cdots ,c^2\})\}$ with cost($M^{*}\left(I\right))=c$.

Let us now analyze the performance of $\mathrm{TA}\left(v_1\right)$ on instance I. Notice that $\mathrm{TA}\left(v_1\right)$ may assign requests $\{i,c+i,\cdots ,(c-1)c+i\}$ to car $k_i$. In that case, the total cost of $\mathrm{TA}\left(v_1\right)$ is $c\left(2\right(c-1)+1))=c(2c-1)$, showing tightness.    □

We proceed by establishing the worst-case ratios of the $\mathrm{TA}\left(v_2\right)$ 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,\cdots ,r_c\}$.

Theorem 2.

The $\mathrm{TA}\left(v_2\right)$ 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}\left(\mathrm{TA}\left(v_2\right)\left(I\right)\right)=c·\mathrm{wait}\left(M^{*}\left(I\right)\right)$.

Proof. 

$$\begin{array}{cc}\hfill & \mathrm{wait}\left(\mathrm{TA}\left(v_1\right)\right)\le v_2\left(M_2\right)\hfill \end{array}$$

(14)

$$\begin{array}{cc}\hfill & \le \sum _{(k,R_k)\in M^{*}}\sum _{i=1}^c\left((c-i+1)·w(d_k,s_{r_i},t_{r_i})+(c-i)·w(d_k,t_{r_i})\right)\hfill \end{array}$$

(15)

$$\begin{array}{cc}\hfill & =\sum _{(k,R_k^{*})\in M^{*}}\sum _{i=1}^c\left(c·w(d_k,s_{r_i},t_{r_i})-(i-1)·w(d_k,s_{r_i},t_{r_i})+(c-i)·w(d_k,t_{r_i})\right)\hfill \end{array}$$

(16)

$$\begin{array}{cc}\hfill & \le \sum _{(k,R_k^{*})\in M^{*}}\sum _{i=1}^{c}c·w(d_k,s_{r_i},t_{r_i})\hfill \end{array}$$

(17)

$$\begin{array}{cc}\hfill & \le \sum _{(k,R_k^{*})\in M^{*}}c·\mathrm{wait}(k,R_k^{*})\hfill \end{array}$$

(18)

$$\begin{array}{cc}\hfill & =c·\mathrm{wait}\left(M^{*}\right)\hfill \end{array}$$

(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. Inequality (17) follows from (we prove it later):

$$\begin{array}{c}\hfill \sum _{i=1}^c\left(-(i-1)·w(d_k,s_{r_i},t_{r_i})+(c-i)·w(d_k,t_{r_i})\right)\le 0.\end{array}$$

The final Inequality (18) follows from the fact that ${\sum }_{i=1}^{c}w(d_k,s_r,t_r)\le \mathrm{wait}(k,R_k^{*})$.

Notice that:

$$\begin{array}{ccc}& & \sum _{i=1}^c\left(-(i-1)·w(d_k,s_{r_i},t_{r_i})+(c-i)·w(d_k,t_{r_i})\right)\hfill \\ & & \le \sum _{i<\frac{c+1}{2}}(c-2i+1)·w(d_k,t_{r_i})-\sum _{i\ge \frac{c+1}{2}}(2i-c-1)·w(d_k,s_{r_i},t_{r_i})\hfill \\ & & =\sum _{i<\frac{c+1}{2}}\left((c-2i+1)·w(d_k,t_{r_i})-(2(c+1-i)-c-1)·w(d_k,s_{r_{c+1-i}},t_{r_{c+1-i}})\right)\hfill \\ & & \le 0\hfill \end{array}$$

where the first inequality follows from the triangle inequality; the second inequality follows from $w(d_k,t_{r_x})\le w(d_k,s_{r_y},t_{r_y})$ for all $r_x,r_y\in R_k^{*}$ with $x<y$ since $w(d_k,s_{r_x},t_{r_x})+w(d_k,t_{r_x})\le w(d_k,s_{r_y},t_{r_y})+w(d_k,t_{r_y})$ by Lemma 3.

To see that the bound c is tight even for ${\mathrm{CS}}_{lat,s=t}$, consider the instance depicted in Figure 1. Observe that an optimal solution is $M^{*}\left(I\right)=\{(k_1,\{1,2,\cdots ,c\}),(k_2,\{c+1,c+2,\cdots ,2c\}),\cdots ,(k_c,\{c(c-1)+1,c(c-1)+2,\cdots ,c^2\})\}$ with $\mathrm{wait}\left(M^{*}\left(I\right)\right)=c^2$. Let us now analyze the performance of $\mathrm{TA}\left(v_2\right)$ on instance I. $\mathrm{TA}\left(v_2\right)$ may assign requests $\{i,c+i,\cdots ,(c-1)c+i\}$ to car $k_i$. In that case, the total waiting time of $\mathrm{TA}\left(v_2\right)$ is $c·(1+3+\cdots +(2(i-1)+1)+\cdots +2(c-1)+1))=c(c·(1+2c-1)/2)=c^3$, showing tightness.    □

3.3. Discussion

Clearly, the $\mathrm{TA}$ is a polynomial-time algorithm, and it is easy to implement; moreover, it can be generalized to handle a variety of situations. We now list three situations and briefly comment on the corresponding worst-case behavior:

• Ride-sharing with car-dependent speeds or relatedride-sharing. In this situation, the cars have speed $p_1,p_2,\cdots ,p_n$. The travel time of serving requests in $R_k$ is denoted by $\mathrm{cost}(k,R_k)/p_k$, and the total travel time of an allocation M is denoted by ${\sum }_{(k,R_k)\in M}\mathrm{cost}(k,R_k)/p_k$. Analogously, the total latency of an allocation M is denoted by ${\sum }_{(k,R_k)\in M}\mathrm{wait}(k,R_k)/p_k$. Without going into the details, we point out that the $\mathrm{TA}$ can be modified by appropriately redefining $v_1(k,r)$ and $v_2(k,r)$ in terms of the cost above; we claim that the corresponding worst-case ratios of $\mathrm{TA}$ as shown in Table 1 remain unchanged;
• Ride-sharing with car-dependent speeds or relatedride-sharing. In this situation, the cars have speed $p_1,p_2,\cdots ,p_n$. The travel time of serving requests in $R_k$ is denoted by $\mathrm{cost}(k,R_k)/p_k$, and the total travel time of an allocation M is denoted by ${\sum }_{(k,R_k)\in M}\mathrm{cost}(k,R_k)/p_k$. Analogously, the total latency of an allocation M is denoted by ${\sum }_{(k,R_k)\in M}\mathrm{wait}(k,R_k)/p_k$. Without going into the details, we point out that the $\mathrm{TA}$ can be modified by appropriately redefining $v_1(k,r)$ and $v_2(k,r)$ in terms of the cost above; we claim that the corresponding worst-case ratios of $\mathrm{TA}$ as shown in Table 1 remain unchanged;
• Car redundancy: $c·n>m$. In this situation, our problem is to find an allocation that serves all requests with the minimum total cost (total travel time or total latency). Clearly, some cars may serve less than c requests, or even do not serve a request. To apply $\mathrm{TA}$ for this situation, we need to add a number of requests to fill the shortage of requests, without affecting the total travel time or latency. We created an instance of our problem by adding a number of dummy requests $R_d$ with $|R_d|=c·n-m$, where the travel time between a request in $R_d$ and a car in D is zero, i.e., $v_1({\gamma }_i\left(k\right),r)=0$ and $v_2({\gamma }_i\left(k\right),r)=0$ for all $i\in \left[c\right],k\in D$, $r\in R_d$. Since the cost of assigning dummy requests is zero in any feasible solution, removing dummy requests of a solution for the newly created instance with $c·n=\left|R\right|$ will give us a solution to the original instance;
• Car deficiency: $\mathbf{c}·\mathbf{n}<\mathbf{m}$. In this situation, our problem is to find an allocation that serves the maximum number of requests ($c·n$ requests) with the minimum total cost (total travel time or total latency). It follows that some requests will not be served. To apply the $\mathrm{TA}$ for this situation, we created an instance of our problem by adding a number of dummy cars $D_d$ with $|D_d|=m-n·c$, where the travel time between a car in $D_d$ and a request in R is H (H is a sufficiently large number), i.e., $v_1(k,r)=H$ and $v_2(k,r)=H$ for all $k\in D_d$, $r\in R$. Removing dummy cars (and their corresponding requests) gives us a solution to the original instance. Since we found an assignment with the minimum total weight and we removed the set of requests assigned to the dummy cars, we claim that the TA selected $c·n$ requests with the minimum total weight. In fact, the proofs in Section 3.1 imply that the $\mathrm{TA}\left(v_1\right)$ is a $(2c-1)$-approximation algorithm for CS${}_{sum}$ and the $\mathrm{TA}\left(v_2\right)$ is a c-approximation algorithm for ${\mathrm{CS}}_{lat}$.

4. The Case $\mathbf{c}=\mathbf{2}$: Algorithms and Their Analysis

In this section, we consider the ride-sharing problems ${\mathrm{CS}}_{sum}$, ${\mathrm{CS}}_{sum,s=t}$, ${\mathrm{CS}}_{lat}$, and ${\mathrm{CS}}_{lat,s=t}$ with capacity $c=2$ and each car serving exactly two requests, i.e., $m=2n$ (see [22]). In Section 4.1, we propose and analyze the match-and-assign algorithm ($\mathrm{MA}$). Next, in Section 4.2, we analyze the combined algorithm ($\mathrm{CA}$), i.e., the better of the two algorithms, the $\mathrm{MA}$ and $\mathrm{TA}$.

For convenience, we explicitly write the quantity $\mathrm{SHP}(s_i,\{i,j\})$ in ${\mathrm{CS}}_{sum}$ by a parameter $u_{ij}$ as follows:

$$\begin{array}{ccc}\hfill u_{ij}& \equiv & min\{w(s_i,s_j,t_i,t_j),w(s_i,s_j,t_j,t_i),w(s_i,t_i,s_j,t_j)\}\hfill & & & foreachi,j\in R\times R,i\ne j.\hfill \end{array}$$

(20)

Notice that the $u_{ij}$’s are not necessarily symmetric. Obviously, $u_{ij}\ge w(s_i,s_j)$ and $u_{ji}\ge w(s_i,s_j)$. For ${\mathrm{CS}}_{sum,s=t}$, we have $u_{ij}=u_{ji}\equiv w(s_i,s_j)$.

The travel time needed to serve requests in $R_k=\{i,j\}$ ($k\in D$) is then given by:

$$\mathrm{cost}(k,\{i,j\})=min\{w(d_k,s_i)+u_{ij},w(d_k,s_j)+u_{ji}\}.$$

(21)

For convenience, we also explicitly write the quantity $\mathrm{SHWP}(s_i,\{i,j\})$ in ${\mathrm{CS}}_{sum}$ by a parameter ${\mu }_{ij}$ as follows:

$$\begin{array}{ccc}\hfill {\mu }_{ij}& \equiv & min\{w(s_i,s_j,t_i)+w(s_i,s_j,t_i,t_j),w(s_i,s_j,t_j)+w(s_i,s_j,t_j,t_i),\hfill & & & w(s_i,t_i)+w(s_i,t_i,s_j,t_j)\}foreachi,j\in R\times R,i\ne j.\hfill \end{array}$$

(22)

Notice that the ${\mu }_{ij}$’s are not necessarily symmetric. For ${\mathrm{CS}}_{lat,s=t}$, we have ${\mu }_{ij}={\mu }_{ji}\equiv w(s_i,s_j)$.

The latency needed to serve requests in $R_k=\{i,j\}$ ($k\in D$) is then given by:

$$\mathrm{wait}(k,\{i,j\})=min\{2w(d_k,s_i)+{\mu }_{ij},2w(d_k,s_j)+{\mu }_{ji}\}.$$

(23)

4.1. The Match-and-Assign Algorithm and Its Analysis

We came up with a match-and-assign algorithm, the $\mathrm{MA}(\alpha ,v)$, the idea being that, first, requests are matched into request pairs, after which the request pairs are assigned to the cars. Finding request pairs is performed by using a carefully chosen time $v_3\left(\{i,j\}\right)$ between a pair of requests $\{i,j\}$, as well as a travel time $v_4(k,\{i,j\})$ between each request pair $\{i,j\}$ and a car $k\in D$:

$$v_3\left(\{i,j\}\right)\equiv \frac{v_{ij}+v_{ji}}{2},v\in \{u,\mu \}.$$

(24)

$$v_4(k,\{i,j\})\equiv min\{\alpha w(d_k,s_i)+\frac{v_{ij}-v_{ji}}{2},\alpha w(d_k,s_j)-\frac{v_{ij}-v_{ji}}{2}\},\alpha \in \{1,2\},v\in \{u,\mu \}.$$

(25)

Now, we introduce the match-and-assign Algorithm 2.

The resulting quantity is $v_3\left(M_3\right)+v_4\left(M_4\right)$; we now prove two lemmas concerning this quantity, which will be of use in the approximation analysis.

Algorithm 2 Match-and-assign algorithm ($\mathrm{MA}(\alpha ,v)$).

1: Matching step: Construct a graph: Let $G_3\equiv (R,v_3)$ be the complete weighted graph where an edge between vertex $i\in R$ and vertex $j\in R$ has weight $v_3\left(\{i,j\}\right)$; Find a min-weight matching: Find a minimum weight perfect matching $M_3$ in $G_3\equiv (R,v_3)$ with weight $v_3\left(M_3\right)$. 2: Assignment step: Construct a graph: Let $G_4\equiv (D\cup M_3,v_4)$ be the complete bipartite graph with left vertex-set D, right vertex-set $M_3$, and edges with weight $v_4(k,\{i,j\})$ for $k\in D$, and $\{i,j\}\in M_3$; Find a min-weight assignment: Find a minimum weight assignment $M_4$ in $G_4\equiv (D\cup M_3,v_4)$ with weight $v_4\left(M_4\right)$. 3: Output:$\mathrm{MA}=M_4$.

Lemma 5.

For each $\alpha \in \{1,2\}$ and $v\in \{u,\mu \}$, we have:

$$\begin{array}{c}\hfill v_3\left(M_3\right)+v_4\left(M_4\right)=\sum _{(k,\{i,j\})\in M_4}min\{\alpha w(d_k,s_i)+v_{ij},\alpha w(d_k,s_j)+v_{ji}\}.\end{array}$$

Proof. 

Without loss of generality, for any $\{i,j\}\in M_3$, suppose $v_{ij}-v_{ji}\ge 0$ (the other case is symmetric).

$$\begin{array}{ccc}\hfill & & v_3\left(M_3\right)+v_4\left(M_4\right)=\sum _{\{i,j\}\in M_3}\frac{v_{ij}+v_{ji}}{2}+\hfill & & & =\sum _{(k,\{i,j\})\in M_4}min\{\alpha w(d_k,s_i)+\frac{v_{ij}-v_{ji}}{2},\alpha w(d_k,s_j)-\frac{v_{ij}-v_{ji}}{2}\}\hfill \\ & & =\sum _{(k,\{i,j\})\in M_4}min\{\alpha w(d_k,s_i)+v_{ij},\alpha w(d_k,s_j)+v_{ji}\}.\hfill \end{array}$$

The first equality follows from the definition of $v_3$ and $v_4$ (see Equations (24) and (25)). □

Lemma 6.

For $\alpha \in \{1,2\}$, $v\in \{u,\mu \}$, and for each allocation M, we have:

$$\begin{array}{c}\hfill v_3\left(M_3\right)+v_4\left(M_2\right)\le \sum _{(k,\{i,j\left\}\right)\in M}\frac{\alpha w(d_k,s_i)+\alpha w(d_k,s_j)+v_{ij}+v_{ji}}{2}.\end{array}$$

Proof. 

For an allocation M, let $M_R=\{R_k:(k,R_k)\in M\}$. Observe that:

$$v_3\left(M_3\right)\le \sum _{\{i,j\}\in M_R}\frac{v_{ij}+v_{ji}}{2},$$

(26)

since $M_3$ is a minimum weight perfect matching in $G_3\equiv (R,v_3)$.

We claim that:

$$v_4\left(M_4\right)\le \sum _{(k,\{i,j\left\}\right)\in M}\frac{\alpha w(d_k,s_i)+\alpha w(d_k,s_j)}{2}.$$

(27)

When summing (26) and (27), the lemma follows.

Hence, it remains to prove (27). Consider an allocation M, and consider the matching $M_3$ found in the first step of the $\mathrm{MA}$. Based on M and $M_3$, we construct the graph $G^{\prime }=(R\cup D,M_1\cup \{(\{i,k\},\{j,k\}):(k,\{i,j\})\in M\})$. Note that every vertex in graph $G^{\prime }$ has degree two. Thus, we can partition $G^{\prime }$ into a set of disjoint cycles called C; each cycle $c\in C$ can be written as $c=(i_1,j_1,k_1,i_2,j_2,k_2,\cdots ,k_h,i_1)$, where $\{i_s,j_s\}\in M_3$, $(k_s,\{j_s,i_{s+1}\})\in M$ for $1\le s<h$ and $(k_h,\{j_h,i_1\})\in M$. Consider now, for each cycle $c\in C$, the following two assignments called $M_{\ell }^c$ and $M_r^c$:

• $M_{\ell }^c=\{(\{i_1,j_1\},k_1),(\{i_2,j_2\},k_2),\cdots ,(\{i_h,j_h\},k_h)\}$,
• $M_r^c=\{(k_1,\{i_2,j_2\}),(k_2,\{i_3,j_3\}),\cdots ,(k_h,\{i_1,j_1\})\}$.

Obviously, both $M_{\ell }\equiv {\bigcup }_{c\in C}{M}_{\ell }^c$ and $M_r\equiv {\bigcup }_{c\in C}{M}_r^c$ are a feasible assignment in $G_4=(D\cup M_3,v_4)$. Given the definition of $v_4(k,\{i,j\})$ (see Equation (25)), we derive for each pair of requests $\{i,j\}$ and two cars $a,b$: $v_4(a,\{i,j\})+v_2(b,\{i,j\})\le \alpha w(d_a,s_i)+\frac{v_{ij}-v_{ji}}{2}+\alpha w(d_b,s_j)-\frac{v_{ij}-v_{ji}}{2}=\alpha (w(d_a,s_i)+w(d_b,s_j)).$ Similarly, it follows that: $v_4(a,\{i,j\})+v_4(b,\{i,j\})\le \alpha (w(d_a,s_j)+w(d_b,s_i))$. Thus, for each $c\in C$:

$$\sum _{(k,\{i,j\})\in M_{\ell }^c}{v}_4(k,\{i,j\})+\sum _{(k,\{i,j\})\in M_r^c}{v}_4(k,\{i,j\})\le \sum _{\begin{array}{c}\{i,k\},\{j,k\}\in c\\ (k,\{i,j\left\}\right)\in M\end{array}}\alpha (w(d_k,s_i)+w(d_k,s_j)).$$

(28)

Note that $M_4$ is a minimum weight assignment in $G_4=(D\cup M_3,v_4)$, and both $M_{\ell }$ and $M_r$ are a feasible assignment in $G_4=(D\cup M_3,v_4)$. Thus:

$$\begin{array}{ccc}& & v_4\left(M_4\right)\le \sum _{c\in C}min\{v_4\left(M_{\ell }^c\right),v_4\left(M_r^c\right)\}\hfill \\ & & \le \frac{1}{2}\sum _{c\in C}\left(\sum _{(k,\{i,j\})\in M_{\ell }^c}{v}_4(k,\{i,j\})+\sum _{(k,\{i,j\})\in M_r^c}{v}_4(k,\{i,j\})\right)\hfill \\ & & \le \sum _{(k,\{i,j\left\}\right)\in M}\frac{\alpha w(d_k,s_i)+\alpha w(d_k,s_j)}{2}.\hfill \end{array}$$

The last inequality follows from (28), and hence, (27) is proven. □

Lemma 7.

For any two requests i and j, we have:

$$max\{u_{ij},u_{ji}\}-min\{u_{ij},u_{ji}\}\le w(s_i,s_j);$$

and:

$$u_{ij}\le 2u_{ji}.$$

Without loss of generality, suppose $u_{ij}\ge u_{ji}$, $u_{ij}\le w(s_i,s_j)+u_{ji}$. Since $w(s_i,s_j)\le min\{u_{ij},u_{ji}\}$, we have $u_{ij}\le 2u_{ji}$ for any two requests i and j.

Theorem 3.

The $\mathrm{MA}(1,u)$ is a two-approximation algorithm for ${\mathrm{CS}}_{sum}$. Moreover, there exists an instance I for which $\mathrm{cost}\left(\mathrm{MA}\left(I\right)\right)=2\mathrm{cost}\left(M^{*}\left(I\right)\right)$.

Proof. 

We assume w.l.o.g. that, for each $(k,\{i,j\})\in M^{*}$, $\mathrm{cost}(k,\{i,j\})=w(d_k,s_i)+u_{ij}$. We have:

$$\begin{array}{cc}\hfill & \mathrm{cost}\left(\mathrm{MA}(1,u)\right)=\sum _{(k,\{i,j\left\}\right)\in \mathrm{MA}}min\{w(d_k,s_i)+u_{ij},w(d_k,s_j)+u_{ji}\}\hfill \end{array}$$

(29)

$$\begin{array}{cc}\hfill & =v_3\left(M_3\right)+v_4\left(M_4\right)\hfill \end{array}$$

(30)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}\frac{w(d_k,s_i)+w(d_k,s_j)+u_{ij}+u_{ji}}{2}\hfill \end{array}$$

(31)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}\frac{2w(d_k,s_i)+w(s_i,s_j)+3u_{ij}}{2}\hfill \end{array}$$

(32)

$$\begin{array}{cc}\hfill & \le \frac{1}{2}\sum _{(k,\{i,j\})\in M^{*}}(2w(d_k,s_i)+4u_{ij})\hfill \end{array}$$

(33)

$$\begin{array}{cc}\hfill & \le \frac{1}{2}\sum _{(k,\{i,j\})\in M^{*}}4\mathrm{cost}(k,\{i,j\})\hfill \end{array}$$

(34)

$$\begin{array}{cc}\hfill & =2\mathrm{cost}\left(M^{*}\right).\hfill \end{array}$$

(35)

Equation (29) follows from (2) and (21). Equation (30) follows from Lemma 5. Inequality (31) follows from Lemma 6. Inequality (32) follows from the triangle inequality, and $u_{ji}\le 2u_{ij}$ for each request pair $\{i,j\}\in R^2$ based on Lemma 7. Inequality (33) follows from $w(s_i,s_j)\le u_{ij}$. Notice that $\mathrm{cost}\left(\mathrm{MA}\left(I\right)\right)\le 2\mathrm{cost}\left(M^{*}\left(I\right)\right)$ is actually tight by the instance depicted in Figure 2. □

Theorem 4.

The $\mathrm{MA}(1,u)$ is a $3/2$-approximation algorithm for ${\mathrm{CS}}_{sum,s=t}$. Moreover, there exists an instance I for which $\mathrm{cost}\left(\mathrm{MA}\left(I\right)\right)=3/2\mathrm{cost}\left(M^{*}\left(I\right)\right)$.

Proof. 

$$\begin{array}{cc}\hfill & \mathrm{cost}\left(\mathrm{MA}(1,u)\right)=\sum _{(k,\{i,j\left\}\right)\in \mathrm{MA}}min\{w(d_k,s_i)+u_{ij},w(d_k,s_j)+u_{ji}\}\hfill \end{array}$$

(36)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}w(s_i,s_j)+\frac{w(d_k,s_i)+w(d_k,s_j)}{2}\hfill \end{array}$$

(37)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}3/2\mathrm{cost}(k,\{i,j\})\hfill \end{array}$$

(38)

$$\begin{array}{cc}\hfill & \le 3/2\mathrm{cost}\left(M^{*}\right)\hfill \end{array}$$

(39)

Equation (36) follows from (20). Inequality (37) follows from Lemma 5 and 6, and $u_{ij}=u_{ji}=w(s_i,s_j)$.

To see that the equality may hold in $\mathrm{cost}\left(\mathrm{MA}\left(I\right)\right)\le 3/2\mathrm{cost}\left(M^{*}\left(I\right)\right)$, consider the subgraph induced by the nodes $(d_1,s_3)$, $(s_1,s_2)$, and $(d_2,s_4)$ in Figure 3 with cars $\{k_1,k_2\}$ and requests $\{1,2,3,4\}$. Observe that an optimal solution is $\{(k_1,\{1,3\}),(k_2,\{2,4\})\}$ with $\mathrm{cost}\left(M^{*}\left(I\right)\right)=2$. Note that ${\mathrm{MR}}^{*}=\{\{1,3\},\{2,4\}\}$. Let us now analyze the performance of $\mathrm{MA}(1,u)$ on this instance. Based on the u values as defined in (20), $\mathrm{MA}(1,u)$ can find, in the first step, matching $M_3=\{\{1,2\},\{3,4\}\}$ because $v_3\left(M_3\right)=v_3\left({\mathrm{MR}}^{*}\right)=2$. Then, no matter how the second step assigns the request pairs to cars, the total waiting time of $\mathrm{MA}(1,u)$ will be three. □

Theorem 5.

The $\mathrm{MA}(2,\mu )$ is a two-approximation algorithm for ${\mathrm{CS}}_{lat}$. Moreover, there exists an instance I of ${\mathrm{CS}}_{lat,s=t}$ for which $\mathrm{wait}\left(\mathrm{MA}\left(I\right)\right)=2\mathrm{wait}\left(M^{*}\left(I\right)\right)$.

Proof. 

$$\begin{array}{cc}\hfill & \mathrm{wait}\left(\mathrm{MA}(2,\mu )\right)=\sum _{(k,\{i,j\left\}\right)\in \mathrm{MA}}min\{2w(d_k,s_i)+{\mu }_{ij},2w(s_k,s_j)+{\mu }_{ji}\}\hfill \end{array}$$

(40)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}\frac{2w(d_k,s_i)+{\mu }_{ij}+2w(d_k,s_j)+{\mu }_{ji}}{2}\hfill \end{array}$$

(41)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}\frac{4min\{w(d_k,s_i),w(d_k,s_j)\}+{\mu }_{ij}+2w(s_i,s_j)+{\mu }_{ji}}{2}\hfill \end{array}$$

(42)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}min\{4w(d_k,s_i)+2{\mu }_{ij},4w(d_k,s_j)+2{\mu }_{ji}\}\hfill \end{array}$$

(43)

$$\begin{array}{cc}\hfill & =\sum _{(k,\{i,j\})\in M^{*}}2\mathrm{wait}(k,\{i,j\})\hfill \end{array}$$

(44)

$$\begin{array}{cc}\hfill & =2\mathrm{wait}\left(M^{*}\right)\hfill \end{array}$$

(45)

Inequality (41) follows from Lemmas 5 and 6. Inequality (42) follows from the triangle inequality. Inequality (43) follows from $w(s_i,s_j)\le min\{{\mu }_{ij},{\mu }_{ji}\}$.

To see that the equality may hold in $\mathrm{wait}\left(\mathrm{MA}\left(I\right)\right)\le 2\mathrm{wait}\left(M^{*}\left(I\right)\right)$, consider the instance I depicted in Figure 4. This instance has two cars $D=\{k_1,k_2\}$ with car locations $\{d_1,d_2\}$ and four requests $R=\{1,2,3,4\}$. If two points are not connected by an edge, their travel time equals five. Observe that an optimal solution is $\{(k_1,\{1,3\}),(k_2,\{2,4\})\}$ with $\mathrm{wait}\left(M^{*}\left(I\right)\right)=4$. Note that $M_R^{*}=\{\{1,3\},\{2,4\}\}$. Let us now analyze the performance of the $\mathrm{MA}(2,\mu )$ on instance I.

Based on the $\mu$ values as defined in (22), the $\mathrm{MA}(2,\mu )$ can find, in the first step, matching $M_3=\{\{1,2\},\{3,4\}\}$ because $v_3\left(M_3\right)=v_3\left(M_R^{*}\right)=8$. Then, no matter how the second step assigns the request pairs to cars, the total waiting time of the $\mathrm{MA}(2,\mu )$ will be eight. □

4.2. The Combined Algorithm and Its Analysis

The ${\mathrm{CA}}_{sum}$ runs the $\mathrm{MA}(1,u)$ and $\mathrm{TA}\left(v_1\right)$ and then outputs the better of the two solutions. We now state the main result for ${\mathrm{CS}}_{sum}$.

Theorem 6.

The ${\mathrm{CA}}_{sum}$ is a two-approximation algorithm for ${\mathrm{CS}}_{sum}$. Moreover, there exists an instance I for which $\mathrm{cost}\left({\mathrm{CA}}_{sum}\left(I\right)\right)=2\mathrm{cost}\left(M^{*}\left(I\right)\right)$.

Proof. 

It is obvious that, as $\mathrm{cost}\left({\mathrm{CA}}_{sum}\right)=min\{\mathrm{cost}\left(\mathrm{MA}(1,u)\right),\mathrm{cost}\left(\mathrm{TA}\left(v_1\right)\right)\}$, Theorems 1 and 3 imply that the ${\mathrm{CA}}_{sum}$ is a two-approximation algorithm for ${\mathrm{CS}}_{sum}$. We now provide an instance for which this ratio is achieved.

Consider the instance I depicted in Figure 2. This instance has two cars $D=\{k_1,k_2\}$ with car locations $\{d_1,d_2\}$ and four requests $R=\{1,2,3,4\}$. Locations corresponding to distinct vertices in Figure 2 are at Travel Time 1. Observe that an optimal solution is $M^{*}\left(I\right)=\{(k_1,\{1,3\}),(k_2,\{2,4\})\}$ with cost($M^{*}\left(I\right))=2$. Note that $M_R^{*}=\{\{1,3\},\{2,4\}\}$. Let us now analyze the performance of the $\mathrm{MA}(1,u)$ and $\mathrm{TA}\left(v_1\right)$ on instance I.

Based on the $u_{ij}$ values as defined in (20), the $\mathrm{MA}(1,u)$ can find, in the first step, matching $M_3=\{\{1,2\},\{3,4\}\}$ with $v_3\left(M_3\right)=v_3\left(M_R^{*}\right)=3$. Then, no matter how the second step assigns the request pairs to cars (since two cars stay at the same location), the total cost of $\mathrm{MA}(1,u)$ will be four.

The $\mathrm{TA}\left(v_1\right)$ may assign Requests 1 and 2 to Car 1 and Requests 3 and 4 to Car 2 since:

$$\begin{array}{c}\hfill v_1\left(\{(k_1,1),(k_1,2),(k_2,3),(k_2,4)\}\right)=v_1\left(\{(k_1,1),(k_1,3),(k_2,2),(k_2,4)\}\right)=6.\end{array}$$

Thus, the total cost of the $\mathrm{TA}\left(v_1\right)$ is four.

To summarize, the instance in Figure 2 is a worst-case instance for the ${\mathrm{CA}}_{sum}$. □

Theorem 7.

The ${\mathrm{CA}}_{sum}$ is a $7/5$-approximation algorithm for ${\mathrm{CS}}_{sum,s=t}$. Moreover, there exists an instance I for which $\mathrm{cost}\left({\mathrm{CA}}_{sum}\left(I\right)\right)=7/5\mathrm{cost}\left(M^{*}\left(I\right)\right)$.

Proof. 

We assume w.l.o.g. that, for each $(k,\{i,j\})\in M^{*}$, $\mathrm{cost}(k,\{i,j\})=w(d_k,s_i)+u_{ij}$. We have:

$$\begin{array}{cc}\hfill & 5\mathrm{cost}\left({\mathrm{CA}}_{sum}\right)\le 4\mathrm{cost}\left(\mathrm{MA}(1,u)\right)+\mathrm{cost}\left(\mathrm{TA}\left(v_1\right)\right)\hfill \end{array}$$

(46)

$$\begin{array}{cc}\hfill & \le 4(v_3\left(M_3\right)+v_4\left(M_4\right))+v_1\left(M_1\right)\hfill \end{array}$$

(47)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}\left(4w(d_k,s_i)+3w(d_k,s_j)+4w(s_i,s_j)\right)\hfill \end{array}$$

(48)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}\left(7w(d_k,s_i)+7w(s_i,s_j)\right)\hfill \end{array}$$

(49)

$$\begin{array}{cc}\hfill & =\sum _{(k,\{i,j\})\in M^{*}}7\mathrm{cost}(k,\{i,j\})\hfill \end{array}$$

(50)

$$\begin{array}{cc}\hfill & =7\mathrm{cost}\left(M^{*}\right)\hfill \end{array}$$

(51)

Inequality (47) follows from Lemma 5 and inequality (7). Inequality (48) follows from Lemmas 2 and 6. Inequality (49) follows from the triangle inequality. Inequality (50) follows from $\mathrm{cost}(k,\{i,j\})=w(d_k,s_i)+u_{ij}$.

We now provide an instance for which this ratio is achieved. Consider the instance I depicted in Figure 3. This instance has four cars $\{k_1,k_2,k_3,k_4\}$ with car locations $\{d_1,d_2,d_3,d_4\}$ and eight requests $R=\{1,2,\cdots ,8\}$. If two points are not connected by an edge, their travel time equals five. Observe that an optimal solution is

$$\{(k_1,\{1,3\}),(k_2,\{2,4\}),(k_3,\{5,6\}),(k_4,\{7,8\})\}$$

with $\mathrm{cost}\left(M^{*}\left(I\right)\right)=10$. Note that $M_R^{*}=\{\{1,3\},\{2,4\},\{5,6\},\{7,8\}\}$. Let us now analyze the performance of $\mathrm{MA}(1,u)$ and $\mathrm{TA}\left(v_1\right)$ on instance I.

Based on the $u_{ij}$ values as defined in (20), the $\mathrm{MA}(1,u)$ can find, in the first step, matching $M_3=\{\{1,2\},\{3,4\},\{5,6\},\{7,8\}\}$ because $v_3\left(M_3\right)=v_3\left(M_R^{*}\right)=8$. Then, no matter how the second step assigns the request pairs to cars (since two cars stay at the same location), the total cost of $\mathrm{MA}(1,u)$ will be 14.

$\mathrm{TA}\left(v_1\right)$ may assign Requests 1 and 3 to Car 1 and Requests 2 and 4 to Car 2 and, similarly, Requests 5 and 7 to Car 3 and Requests 6 and 8 to Car 4 because:

$$\begin{array}{c}\hfill v_1\left(\{(k_3,5),(k_3,7),(k_4,6),(k_4,8)\}\right)=v_1\left(\{(k_3,5),(k_3,6),(k_4,7),(k_4,8)\}\right)=6.\end{array}$$

Thus, the total cost of the $\mathrm{TA}\left(v_1\right)$ is 14.

To summarize, the instance in Figure 3 is a worst-case instance for the ${\mathrm{CA}}_{sum}$. □

The ${\mathrm{CA}}_{lat}$ runs the $\mathrm{MA}(2,\mu )$ and $\mathrm{TA}\left(v_2\right)$ and then outputs the better of the two solutions. We now state the main result for ${\mathrm{CS}}_{lat}$. The following lemma is useful to analyze the performance of the CA for ${\mathrm{CS}}_{lat}$.

Lemma 8.

For each $(k,\{i,j\})\in D\times R^2$,

$$\begin{array}{ccc}& & min\{2w(d_k,s_i,t_i)+w(t_i,d_k,s_j,t_j),2w(d_k,s_j,t_j)+w(t_j,d_k,s_i,t_i)\}\hfill \\ & & +2w(d_k,s_i)+2w(d_k,s_j)+{\mu }_{ij}+{\mu }_{ji}\hfill \\ & & \le min\{8w(d_k,s_i)+5{\mu }_{ij},8w(d_k,s_j)+5{\mu }_{ji}\}.\hfill \end{array}$$

Proof. 

We first prove $2w(d_k,s_i,t_i)+w(t_i,d_k,s_j,t_j)+2w(d_k,s_i)+2w(d_k,s_j)+{\mu }_{ij}+{\mu }_{ji}\le 8w(d_k,s_i)+5{\mu }_{ij}$. We distinguish three cases based on ${\mu }_{ij}$: (1) ${\mu }_{ij}=w(s_i,t_i)+w(s_i,t_i,s_j,t_j)$; (2) ${\mu }_{ij}=w(s_i,s_j,t_i)+w(s_i,s_j,t_i,t_j)$; (3) ${\mu }_{ij}=w(s_i,s_j,t_j)+w(s_i,s_j,t_j,t_i)$.

Consider Case (1): ${\mu }_{ij}=w(s_i,t_i)+w(s_i,t_i,s_j,t_j)$. We have:

$$2w(d_k,s_i)+{\mu }_{ij}=2w(d_k,s_i)+2w(s_i,t_i)+w(t_i,s_j)+w(s_j,t_j).$$

According to the triangle inequality, we know that:

$$w(d_k,t_i)\le w(d_k,s_i)+w(s_i,t_i),$$

$$w(d_k,s_j)\le (d_k,s_i)+w(s_i,t_i)+w(t_i,s_j).$$

Based on the definition of $\mu$, we know:

$${\mu }_{ij}=2w(s_i,t_i)+w(t_i,s_j)+w(s_j,t_j),$$

$${\mu }_{ji}\le 2w(s_j,t_j)+w(t_j,s_i)+w(s_i,t_i)\le 3w(s_j,t_j)+2w(s_i,t_i)+w(t_i,s_j).$$

Using the above inequalities, we have:

$$\begin{array}{ccc}\hfill & & 2w(d_k,s_i,t_i)+w(t_i,d_k,s_j,t_j)+2w(d_k,s_i)+2w(d_k,s_j)+{\mu }_{ij}+{\mu }_{ji}\hfill & & & \le 8w(d_k,s_i)+10w(s_i,t_i)+5w(t_i,s_j)+5w(s_j,t_j)\hfill \\ & & =8w(d_k,s_i)+5{\mu }_{ij}.\hfill \end{array}$$

The other two cases (2) and (3) are obtained similarly.

Analogously, we have $2w(d_k,s_j,t_j)+w(t_j,d_k,s_i,t_i)+2w(d_k,s_i)+2w(s_k,s_j)+{\mu }_{ij}+{\mu }_{ji}\le 8w(d_k,s_j)+5{\mu }_{ij}$. □

Theorem 8.

The ${\mathrm{CA}}_{lat}$ is a 5/3-approximation algorithm for ${\mathrm{CS}}_{lat}$.

Proof. 

$$\begin{array}{cc}\hfill & 3\mathrm{wait}\left({\mathrm{CA}}_{lat}\right)\le 2\mathrm{wait}\left(\mathrm{MA}(2,\mu )\right)+\mathrm{wait}\left(\mathrm{TA}\left(v_2\right)\right)\hfill \end{array}$$

(52)

$$\begin{array}{cc}\hfill & \le 2\left(v_3\left(M_3\right)+v_4\left(M_4\right)\right)+v_2\left(M_2\right)\hfill \end{array}$$

(53)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}min\{8w(d_k,s_i)+5{\mu }_{ij},8w(d_k,s_j)+5{\mu }_{ji}\}\hfill \end{array}$$

(54)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}5min\{2w(d_k,s_i)+{\mu }_{ij},2w(d_k,s_j)+{\mu }_{ji}\}\hfill \end{array}$$

(55)

$$\begin{array}{cc}\hfill & =5\mathrm{wait}\left(M^{*}\right).\hfill \end{array}$$

(56)

Inequality (51) follows from Lemma 5 and Inequality (8). Inequality (54) follows from Lemmas 4, 6, and 8. □

Theorem 9.

The ${\mathrm{CA}}_{lat}$ is a 3/2-approximation algorithm for ${\mathrm{CS}}_{lat,s=t}$. Moreover, there exists an instance I for which $\mathrm{wait}\left({\mathrm{CA}}_{lat}\left(I\right)\right)=3/2\mathrm{wait}\left(M^{*}\left(I\right)\right)$.

Proof. 

We assume w.l.o.g. that, for each $(k,\{i,j\})\in M^{*}$, $\mathrm{wait}(k,\{i,j\})=2w(d_k,s_i)+w(s_i,s_j)$. We have:

$$\begin{array}{cc}\hfill & 2\mathrm{wait}\left(\mathrm{CA}(2,\mu )\right)\le \mathrm{wait}\left(\mathrm{MA}(2,\mu )\right)+\mathrm{wait}\left(\mathrm{TA}\left(v_2\right)\right)\hfill \end{array}$$

(57)

$$\begin{array}{cc}\hfill & =\sum _{(k,\{i,j\left\}\right)\in \mathrm{MA}}min\{2w(d_k,s_i)+{\mu }_{ij},2w(s_k,s_j)+{\mu }_{ji}\}\hfill \end{array}$$

(58)

$$\begin{array}{cc}\hfill & +\sum _{(k,\{i,j\})\in \mathrm{TA}\left(v_2\right)}min\{2w(d_k,s_i)+{\mu }_{ij},2w(s_k,s_j)+{\mu }_{ji}\}\hfill \end{array}$$

(59)

$$\begin{array}{cc}\hfill & =v_3\left(M_3\right)+v_4\left(M_4\right)+v_2\left(M_2\right)\hfill \end{array}$$

(60)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}\left(w(s_i,s_j)+w(d_k,s_i)+w(d_k,s_j)+3w(d_k,s_i)+w(d_k,s_j)\right)\hfill \end{array}$$

(61)

$$\begin{array}{cc}\hfill & \le \sum _{(k,\{i,j\})\in M^{*}}\left(3w(s_i,s_j)+6w(d_k,s_i)\right)\hfill \end{array}$$

(62)

$$\begin{array}{cc}\hfill & =\sum _{(k,\{i,j\})\in M^{*}}3\mathrm{wait}(k,\{i,j\})\hfill \end{array}$$

(63)

$$\begin{array}{cc}\hfill & =3\mathrm{wait}\left(M^{*}\right).\hfill \end{array}$$

(64)

Equation (59) follows from (23). Equation (60) follows from Lemma 5. Inequality (62) follows from the triangle inequality. Equation (63) follows from $\mathrm{wait}($$k,\{i,j\})=2w(d_k,s_i)+{\mu }_{ij}$.

We now provide an instance for which this ratio is achieved. This instance has four cars $\{k_1,k_2,k_3,k_4\}$ with car locations $\{d_1,d_2,d_3,d_4\}$ and eight requests $R=\{1,2,\cdots ,8\}$. Consider the instance I depicted in Figure 5. If two points are not connected by an edge, their travel time equals five. Observe that an optimal solution is:

$$\begin{array}{c}\hfill \{(k_1,\{1,3\}),(k_2,\{2,4\}),(k_3,\{5,6\}),(k_4,\{7,8\})\}\end{array}$$

with $\mathrm{wait}\left(M^{*}\left(I\right)\right)=8$. Note that $M_R^{*}=\{\{1,3\},\{2,4\},\{5,6\},\{7,8\}\}$. Let us now analyze the performance of the $\mathrm{MA}(2,\mu )$ and $\mathrm{TA}\left(v_2\right)$ on instance I.

Based on the ${\mu }_{ij}$ values as defined in (22), the $\mathrm{MA}(2,\mu )$ can find, in the first step, matching $M_3=\{\{1,2\},\{3,4\},\{5,6\},\{7,8\}\}$ because $v_3\left(M_3\right)=v_3\left(M_R^{*}\right)=4$. Then, no matter how the second step matches the pairs to cars, the total waiting time of the $\mathrm{MA}(2,\mu )$ will be 12.

The $\mathrm{TA}\left(v_2\right)$ may assign Requests 1 and 3 to Car 1 and assign Requests 4 and 2 to Car 2 and, similarly, assign Requests 5 and 7 to Car 3 and assign Requests 6 and 8 to Car 4 because:

$$\begin{array}{c}\hfill v_2\left(\{(k_3,5),(k_3,7),(k_4,6),(k_4,8)\}\right)=v_2\left(\{(k_3,5),(k_3,6),(k_4,7),(k_4,8)\}\right)=8.\end{array}$$

Thus, the total waiting time of the $\mathrm{TA}\left(v_2\right)$ is 12.

To summarize, the instance in Figure 5 is a worst-case instance for the combined algorithm ${\mathrm{CA}}_{lat}$. □

5. Conclusions

We analyzed a polynomial-time algorithm, called the transportation algorithm (TA), for four different versions of a ride-sharing problem where each car serves at most c requests. We proved that the TA is a $(2c-1)$-approximation (resp. c-approximation) algorithm for ${\mathrm{CS}}_{sum}$ and ${\mathrm{CS}}_{sum,s=t}$ (resp. ${\mathrm{CS}}_{lat}$ and ${\mathrm{CS}}_{lat,s=t}$). Furthermore, for the special case where capacity $c=2$ and $m=c·n$, we proposed another algorithm, called match-and-assign (MA), which firstly matches the requests into pairs and then assigns the request pairs to the cars. We proved that (for most problem variants) the worst-case ratio of the algorithm defined by the better of the two corresponding solutions is strictly better than the worst-case ratios of the individual algorithms.

For future directions, it would be interesting to extend the MA for the ride-sharing problem for any constant capacity c. It would also be interesting to obtain meaningful lower bounds on the approximability of the ride-sharing problem. Other possible directions include studying the problem under different objectives such as minimizing the makespan or considering the release times and/or deadlines of the requests.