Open AccessArticle

Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems

Kelin Luo

and

Frits C. R. Spieksma

Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands

Author to whom correspondence should be addressed.

Algorithms 2022, 15(2), 30; https://doi.org/10.3390/a15020030

Submission received: 7 December 2021 / Revised: 8 January 2022 / Accepted: 14 January 2022 / Published: 18 January 2022

(This article belongs to the Collection Feature Paper in Algorithms and Complexity Theory)

Download

Browse Figures

Figure 1
A worst-case instance for the transportation algorithm. "> Figure 2
A worst-case instance for the <math display="inline"><semantics> <msub> <mi>CA</mi> <mrow> <mi>s</mi> <mi>u</mi> <mi>m</mi> </mrow> </msub> </semantics></math> of <math display="inline"><semantics> <msub> <mi>CS</mi> <mrow> <mi>s</mi> <mi>u</mi> <mi>m</mi> </mrow> </msub> </semantics></math>. "> Figure 3
A worst-case instance for the <math display="inline"><semantics> <msub> <mi>CA</mi> <mrow> <mi>s</mi> <mi>u</mi> <mi>m</mi> </mrow> </msub> </semantics></math> of <math display="inline"><semantics> <msub> <mi>CS</mi> <mrow> <mi>s</mi> <mi>u</mi> <mi>m</mi> <mo>,</mo> <mi>s</mi> <mo>=</mo> <mi>t</mi> </mrow> </msub> </semantics></math>. "> Figure 4
A worst-case instance of the <math display="inline"><semantics> <mrow> <mi>MA</mi> <mo>(</mo> <mn>2</mn> <mo>,</mo> <mi>μ</mi> <mo>)</mo> </mrow> </semantics></math> for <math display="inline"><semantics> <mrow> <mi>C</mi> <msub> <mi>S</mi> <mrow> <mi>l</mi> <mi>a</mi> <mi>t</mi> <mo>,</mo> <mi>s</mi> <mo>=</mo> <mi>t</mi> </mrow> </msub> </mrow> </semantics></math>. "> Figure 5
A worst-case instance for the <math display="inline"><semantics> <msub> <mi>CA</mi> <mrow> <mi>l</mi> <mi>a</mi> <mi>t</mi> </mrow> </msub> </semantics></math> of <math display="inline"><semantics> <msub> <mi>CS</mi> <mrow> <mi>l</mi> <mi>a</mi> <mi>t</mi> <mo>,</mo> <mi>s</mi> <mo>=</mo> <mi>t</mi> </mrow> </msub> </semantics></math>. ">

Review Reports Versions Notes

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

{CS}_{s u m}

) and to serve the maximum number of requests with the minimum total latency (called

{CS}_{l a t}

). In addition, we studied the special case where the pick-up and drop-off locations of a request coincide. Both problems

{CS}_{s u m}

and

{CS}_{l a t}

are APX-hard when

c \geq 2

. We propose an algorithm, called the transportation algorithm (TA), which is a

(2 c - 1)

-approximation (resp. c-approximation) algorithm for

{CS}_{s u m}

(resp.

{CS}_{l a t}

); 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

{CS}_{s u m}

(resp.

{CS}_{l a t}

), and these ratios are better than the ratios of the individual algorithms, the TA and MA.

Keywords:

ride-sharing; approximation algorithms; transportation problem

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 {| R |, c \cdot | D |}

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 ${CS}_{s u m}$ and the special case of ${CS}_{s u m}$ where the pick-up and drop-off locations are identical for each request ${CS}_{s u m, 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 ${CS}_{l a t}$ and the special case of ${CS}_{l a t}$ where the pick-up and drop-off locations are identical for each request ${CS}_{l a t, 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 \leq 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

{CS}_{s u m}

or minimizing the total latency in

{CS}_{l a t}

The problems

{CS}_{s u m, s = t}

and

{CS}_{l a t, s = t}

are natural special cases of

{CS}_{s u m}

and

{CS}_{l a t}

, 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 (

{CS}_{s u m}

) or minimizing the total waiting time (

{CS}_{l a t}

). As far as we are aware, this particular ride-sharing problem has not been extensively studied, especially for the latency criterion, i.e.,

{CS}_{l a t}

. Notice that when

c = 1

, the ride-sharing problems

{CS}_{s u m}

and

{CS}_{l a t}

become minimum weight assignment problems, and an optimal solution can be found in

O (| D |^{3})

(see, e.g., [21]). Bei and Zhang [9] considered

{CS}_{s u m}

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 \geq 2

In fact, both

{CS}_{s u m}

and

{CS}_{l a t}

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

2 n

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

{CS}_{s u m}

and

{CS}_{l a t}

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.,

cost (i, j, k) = d_{i j} + d_{j k} + d_{k i}

, 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

{CS}_{s u m}

, as well as in

{CS}_{l a t}

differs from the above expression for

c o s t (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, 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 (see also [22]). Notice that for

{CS}_{s u m, s = t}

{CS}_{l a t}

, and

{CS}_{l a t, 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

{CS}_{s u m}

and

{CS}_{l a t}

. 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

{CS}_{s u m}

and

{CS}_{l a t}

. 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}, \dots, 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, \dots, n}

, each car k consisting of its location

d_{k} \in V

and m requests

R = {r_{1}, r_{2}, \dots, 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{matrix} M = {(k, R_{k}) : k \in D, R_{k} \subseteq R, | R_{k} | \leq c, R_{1}, R_{2}, . ., R_{n} are pairwise disjoint}, \end{matrix}

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}

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

SHP (s_{r}, R_{k})

. We view

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

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:

cost (k, R_{k}) = min_{r \in R_{k}} {w (d_{k}, s_{r}) + SHP (s_{r}, R_{k})} .

(1)

We denote the travel time of an allocation M by:

cost (M) = \sum_{(k, R_{k}) \in M} cost (k, R_{k}) .

(2)

{CS}_{s u m}

and

{CS}_{s u m, s = t}

, the goal is to find an allocation M that minimizes

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. 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}

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

wait (k, R_{k})

as consisting of two parts: one term

c \cdot w (d_{k}, s_{r})

expressing the waiting time between

d_{k}

and the first pick-up location

s_{r}

; another term

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:

wait (k, R_{k}) = min_{r \in R_{k}} {c \cdot w (d_{k}, s_{r}) + SHWP (s_{r}, R_{k})} .

(3)

We denote the latency of an allocation M by:

wait (M) = \sum_{(k, R_{k}) \in M} wait (k, R_{k}) .

(4)

Thus, in

{CS}_{l a t}

and

{CS}_{l a t, s = t}

, the goal is to find an allocation M that minimizes

wait (M)

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

{CS}_{l a t}

. In this setting, the drop-off location clearly becomes irrelevant to the objective, and our approximation results for

{CS}_{l a t, 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

{CS}_{s u m}

{CS}_{s u m, s = t}

{CS}_{l a t}

, and

{CS}_{l a t, 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

{γ_{1} (k), \dots, γ_{c} (k)}

, resulting in car sets

Γ = {γ_{1} (1), \dots, γ_{c} (1), \dots, γ_{1} (n), \dots, γ_{c} (n)}

with

| Γ | = 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} (γ_{i} (k), r)

(or

v_{2} (γ_{i} (k), r)

) between a request

r \in R

and a car

γ_{i} (k) \in Γ

v_{1} (γ_{i} (k), r) = \{\begin{matrix} w (d_{k}, s_{r}, t_{r}) + w (t_{r}, d_{k}) & i f i < c \\ w (d_{k}, s_{r}, t_{r}) & i f i = c \end{matrix} .

(5)

v_{2} (γ_{i} (k), r) = \{\begin{matrix} (c - i + 1) w (d_{k}, s_{r}, t_{r}) + (c - i) w (t_{r}, d_{k}) & i f i < c \\ w (d_{k}, s_{r}, t_{r}) & i f i = c \end{matrix} .

(6)

Next, we introduce how to assign

c \cdot n

requests to the

c \cdot n

cars. As is showed in Algorithm 1.

Algorithm 1 Transportation algorithm (

TA (v)

1:: Construct a graph: Let $G_{1} \equiv (Γ \cup R, v_{1})$ (resp. $G_{2} \equiv (Γ \cup R, v_{2})$ ) be the complete bipartite graph with left vertex-set $Γ$ , right vertex-set R, and edge weights $v_{1} (γ_{i} (k), r)$ (resp. $v_{2} (γ_{i} (k), r)$ ) for $γ_{i} (k) \in Γ$ and $r \in R$ .
2:: Find a min-weight assignment: Find a minimum weight assignment $M_{1}$ (resp, $M_{2}$ ) in $G_{1} \equiv (Γ \cup R, v_{1})$ (resp, $G_{2} \equiv (Γ \cup R, v_{2})$ ) with weight $v_{1} (M_{1})$ (resp. $v_{2} (M_{2})$ ).
3:: Output: $TA (v_{1}) \equiv {(k, {r_{1}, \dots, r_{c}}) : (γ_{1} (k), r_{1}), \dots, (γ_{c} (k), r_{c}) \in M_{1}}$ .
$TA (v_{2}) \equiv {(k, {r_{1}, \dots, r_{c}}) : (γ_{1} (k), r_{1}), \dots, (γ_{c} (k), r_{c}) \in M_{2}}$ .

A solution is then found by letting car

k \in D

serve the requests assigned to virtual cars

{γ_{1} (k), \dots, γ_{c} (k)}

. Let

R_{k} = {r_{1}, r_{2}, \dots, r_{c}}

(

k \in D

) denote the requests assigned to a car k, where request

r_{i} \in R_{k}

is assigned to

γ_{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}_{s u m}

and

M_{2}

to construct a solution for

{CS}_{l a t}

Observe that

v_{1} (M_{1}) = \sum_{(γ_{i} (k), r) \in M_{1}} v_{1} (γ_{i} (k), r)

. This amounts to a solution where each car

k \in D

travels according to the following path:

\begin{matrix} d_{k} \to s_{r_{1}} \to t_{r_{1}} \to d_{k} \to s_{r_{2}} \to t_{r_{2}} \to \dots \to d_{k} \to s_{r_{c}} \to t_{r_{c}} . \end{matrix}

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{matrix} d_{k} \to s_{r_{1}} \to t_{r_{1}} \to s_{r_{2}} \to t_{r_{2}} \to \dots \to t_{r_{c - 1}} \to s_{r_{c}} \to t_{r_{c}} . \end{matrix}

In fact, we use

TA (v_{1})

to denote this resulting solution found by the TA for

{CS}_{s u m}

, with

cost (TA (v_{1}))

denoting its cost.

We conclude:

cost (TA (v_{1})) \leq v_{1} (M_{1}) .

(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:

\begin{matrix} d_{k} \to s_{r_{1}} \to t_{r_{1}} \to d_{k} \to s_{r_{2}} \to t_{r_{2}} \to \dots \to d_{k} \to s_{r_{c}} \to t_{r_{c}} . \end{matrix}

As argued above, shortcutting gives us then a feasible solution for an instance of

{CS}_{l a t}

we denote by

TA (v_{2})

with cost

wait (TA (v_{2}))

. We have:

wait (TA (v_{2})) \leq v_{2} (M_{2}) .

(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} (M_{1})

(also,

v_{2} (M_{2})

), we can subtract the corresponding travel time from the total travel time. We now give two lemmas concerning

v_{1} (M_{1})

(which we need to prove Theorem 1) and two more lemmas concerning

v_{2} (M_{2})

(which we need to prove Theorem 2).

Lemma 1.

For any

c \geq 2

, we have:

\begin{matrix} v_{1} (M_{1}) = \sum_{(k, R_{k}) \in TA (v_{1})} (\sum_{r \in R_{k}} w (d_{k}, s_{r}, t_{r}, d_{k}) - max_{r \in R_{k}} w (d_{k}, t_{r})) . \end{matrix}

Proof.

We claim that

v_{1} (M_{1})

is minimized if and only if, for each car

k \in D

and

(γ_{c} (k), 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} (\cdot, \cdot)

, 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{matrix} v_{1} (M_{1}) = \sum_{(k, R_{k}) \in TA (v_{1})} (\sum_{r \in R_{k}} w (d_{k}, s_{r}, t_{r}, d_{k}) - max_{r \in R_{k}} w (d_{k}, t_{r})) . \end{matrix}

It remains to prove the claim. Consider any

R_{k} = {r_{1}, r_{2}, \dots, r_{c}}

for car

k \in D

. We prove that

v_{1} (M_{1})

is minimized if and only if

w (d_{k}, t_{r_{c}}) \geq 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}}) \leq 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}}) \leq w (d_{k}, t_{r_{c}})

holds.

Sufficient condition: Since

w (d_{k}, t_{r_{c}}) \geq 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}}) \geq 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} (M_{1})

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 (Γ \cup R, v_{1})

, we have the following lemma:

Lemma 2.

For

c \geq 2

and for each allocation M, we have:

\begin{matrix} v_{1} (M_{1}) \leq \sum_{(k, R_{k}) \in M} (\sum_{r \in R_{k}} w (d_{k}, s_{r}, t_{r}, d_{k}) - max_{r \in R_{k}} w (d_{k}, t_{r})) . \end{matrix}

We now provide two lemmas concerning

v_{2} (M_{2})

. In the statement of these lemmas, we index the requests such that, for each

k \in D

R_{k} = {r_{1}, r_{2}, \dots, r_{c}}

Lemma 3.

For any

c \geq 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}}) \leq w (d_{k}, s_{r_{y}}, t_{r_{y}}) + w (d_{k}, t_{r_{y}})

Proof.

We claim that

v_{2} (M_{2})

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}, \dots, r_{c}}

with

x < y

w (d_{k}, s_{r_{x}}, t_{r_{x}}) + w (d_{k}, t_{r_{x}}) \leq 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}, \dots, r_{c}}

with

x < y

for car

k \in D

. We prove that

v_{2} (M_{2})

is minimized if and only if

w (d_{k}, s_{r_{x}}, t_{r_{x}}) + w (d_{k}, t_{r_{x}}) \leq w (d_{k}, s_{r_{y}}, t_{r_{y}}) + w (d_{k}, t_{r_{y}})

Necessary condition: Since

v_{2} (M_{2})

is minimized, based on definition of cost

v_{2} (\cdot, \cdot)

, we have:

\begin{matrix} (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}) \\ \leq (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{matrix}

⟺ (y - x) (w (d_{k}, s_{r_{x}}, t_{r_{x}}) + w (d_{k}, t_{r_{x}})) \leq (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}}) \leq 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}}) \leq w (d_{k}, s_{r_{y}}, t_{r_{y}}) + w (d_{k}, t_{r_{y}})

implies that

v_{2} (M_{2})

is minimized. □

Since

M_{2}

is a minimum weight assignment in

G_{2} \equiv (Γ \cup R, v_{2})

, we have the following lemma:

Lemma 4.

For

c \geq 2

and for each allocation M, we have:

\begin{matrix} v_{2} (M_{2}) \leq \sum_{(k, R_{k}) \in M} \sum_{i = 1}^{c} ((c - i + 1) \cdot w (d_{k}, s_{r_{i}}, t_{r_{i}}) + (c - i) \cdot w (d_{k}, t_{r_{i}})) . \end{matrix}

3.2. Approximation Analysis of the TA

Let us denote an optimal allocation in

{CS}_{s u m}

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

TA (v_{1})

for

{CS}_{s u m}

and

{CS}_{s u m, s = t}

Theorem 1.

The

TA (v_{1})

is a

(2 c - 1)

-approximation algorithm for

{CS}_{s u m}

. Moreover, there exists an instance I of

{CS}_{s u m, s = t}

for which

cost (TA (v_{1}) (I)) = (2 c - 1) \cdot cost (M^{*} (I))

Proof.

\begin{matrix} cost (TA (v_{1})) \leq v_{1} (M_{1}) \end{matrix}

(9)

\begin{matrix} \leq \sum_{(k, R_{k}^{*}) \in M^{*}} (\sum_{r \in R_{k}^{*}} w (d_{k}, s_{r}, t_{r}, d_{k}) - max_{r \in R_{k}^{*}} w (d_{k}, t_{r})) \end{matrix}

(10)

\begin{matrix} = \sum_{(k, R_{k}^{*}) \in M^{*}} (\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})) \end{matrix}

(11)

\begin{matrix} \leq \sum_{(k, R_{k}^{*}) \in M^{*}} (2 c - 1) cost (k, R_{k}^{*}) \end{matrix}

(12)

\begin{matrix} = (2 c - 1) cost (M^{*}) \end{matrix}

(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 cost (k, R_{k}^{*}) .

To see that the bound

2 c - 1

is tight even for

{CS}_{s u m, s = t}

, consider the instance I depicted in Figure 1. This instance has c cars

D = {k_{1}, k_{2}, \dots, k_{c}}

with car locations

{d_{1}, d_{2}, \dots, d_{c}}

and

c^{2}

requests

R = {1, 2, \dots, c^{2}}

with locations

{s_{1}, s_{2}, \dots, 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, \dots, c}), (k_{2}, {c + 1, c + 2, \dots, 2 c}), \dots, (k_{c}, {c (c - 1) + 1, c (c - 1) + 2, \dots, c^{2}})}

with cost(

M^{*} (I)) = c

Let us now analyze the performance of

TA (v_{1})

on instance I. Notice that

TA (v_{1})

may assign requests

{i, c + i, \dots, (c - 1) c + i}

to car

k_{i}

. In that case, the total cost of

TA (v_{1})

c (2 (c - 1) + 1)) = c (2 c - 1)

, showing tightness. □

We proceed by establishing the worst-case ratios of the

TA (v_{2})

for

{CS}_{l a t}

and

{CS}_{l a t, s = t}

. Again, we assume that an optimal solution to

{CS}_{l a t}

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}, \dots, r_{c}}

Theorem 2.

The

TA (v_{2})

is a c-approximation algorithm for

{CS}_{l a t}

. Moreover, there exists an instance I of

{CS}_{l a t, s = t}

for which

wait (TA (v_{2}) (I)) = c \cdot wait (M^{*} (I))

Proof.

\begin{matrix} wait (TA (v_{1})) \leq v_{2} (M_{2}) \end{matrix}

(14)

\begin{matrix} \leq \sum_{(k, R_{k}) \in M^{*}} \sum_{i = 1}^{c} ((c - i + 1) \cdot w (d_{k}, s_{r_{i}}, t_{r_{i}}) + (c - i) \cdot w (d_{k}, t_{r_{i}})) \end{matrix}

(15)

\begin{matrix} = \sum_{(k, R_{k}^{*}) \in M^{*}} \sum_{i = 1}^{c} (c \cdot w (d_{k}, s_{r_{i}}, t_{r_{i}}) - (i - 1) \cdot w (d_{k}, s_{r_{i}}, t_{r_{i}}) + (c - i) \cdot w (d_{k}, t_{r_{i}})) \end{matrix}

(16)

\begin{matrix} \leq \sum_{(k, R_{k}^{*}) \in M^{*}} \sum_{i = 1}^{c} c \cdot w (d_{k}, s_{r_{i}}, t_{r_{i}}) \end{matrix}

(17)

\begin{matrix} \leq \sum_{(k, R_{k}^{*}) \in M^{*}} c \cdot wait (k, R_{k}^{*}) \end{matrix}

(18)

\begin{matrix} = c \cdot wait (M^{*}) \end{matrix}

(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{matrix} \sum_{i = 1}^{c} (- (i - 1) \cdot w (d_{k}, s_{r_{i}}, t_{r_{i}}) + (c - i) \cdot w (d_{k}, t_{r_{i}})) \leq 0 . \end{matrix}

The final Inequality (18) follows from the fact that

\sum_{i = 1}^{c} w (d_{k}, s_{r}, t_{r}) \leq wait (k, R_{k}^{*})

Notice that:

\begin{matrix} \sum_{i = 1}^{c} (- (i - 1) \cdot w (d_{k}, s_{r_{i}}, t_{r_{i}}) + (c - i) \cdot w (d_{k}, t_{r_{i}})) \\ \leq \sum_{i < \frac{c + 1}{2}} (c - 2 i + 1) \cdot w (d_{k}, t_{r_{i}}) - \sum_{i \geq \frac{c + 1}{2}} (2 i - c - 1) \cdot w (d_{k}, s_{r_{i}}, t_{r_{i}}) \\ = \sum_{i < \frac{c + 1}{2}} ((c - 2 i + 1) \cdot w (d_{k}, t_{r_{i}}) - (2 (c + 1 - i) - c - 1) \cdot w (d_{k}, s_{r_{c + 1 - i}}, t_{r_{c + 1 - i}})) \\ \leq 0 \end{matrix}

where the first inequality follows from the triangle inequality; the second inequality follows from

w (d_{k}, t_{r_{x}}) \leq 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}}) \leq 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

{CS}_{l a t, s = t}

, consider the instance depicted in Figure 1. Observe that an optimal solution is

M^{*} (I) = {(k_{1}, {1, 2, \dots, c}), (k_{2}, {c + 1, c + 2, \dots, 2 c}), \dots, (k_{c}, {c (c - 1) + 1, c (c - 1) + 2, \dots, c^{2}})}

with

wait (M^{*} (I)) = c^{2}

. Let us now analyze the performance of

TA (v_{2})

on instance I.

TA (v_{2})

may assign requests

{i, c + i, \dots, (c - 1) c + i}

to car

k_{i}

. In that case, the total waiting time of

TA (v_{2})

c \cdot (1 + 3 + \dots + (2 (i - 1) + 1) + \dots + 2 (c - 1) + 1)) = c (c \cdot (1 + 2 c - 1) / 2) = c^{3}

, showing tightness. □

3.3. Discussion

Clearly, the

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}, \dots, p_{n}$ . The travel time of serving requests in $R_{k}$ is denoted by $cost (k, R_{k}) / p_{k}$ , and the total travel time of an allocation M is denoted by $\sum_{(k, R_{k}) \in M} cost (k, R_{k}) / p_{k}$ . Analogously, the total latency of an allocation M is denoted by $\sum_{(k, R_{k}) \in M} wait (k, R_{k}) / p_{k}$ . Without going into the details, we point out that the $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 $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}, \dots, p_{n}$ . The travel time of serving requests in $R_{k}$ is denoted by $cost (k, R_{k}) / p_{k}$ , and the total travel time of an allocation M is denoted by $\sum_{(k, R_{k}) \in M} cost (k, R_{k}) / p_{k}$ . Analogously, the total latency of an allocation M is denoted by $\sum_{(k, R_{k}) \in M} wait (k, R_{k}) / p_{k}$ . Without going into the details, we point out that the $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 $TA$ as shown in Table 1 remain unchanged;
Car redundancy: $c \cdot 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 $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 \cdot n - m$ , where the travel time between a request in $R_{d}$ and a car in D is zero, i.e., $v_{1} (γ_{i} (k), r) = 0$ and $v_{2} (γ_{i} (k), r) = 0$ for all $i \in [c], 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 \cdot n = | R |$ will give us a solution to the original instance;
Car deficiency: $c \cdot n < m$ . In this situation, our problem is to find an allocation that serves the maximum number of requests ( $c \cdot 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 $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 \cdot 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 \cdot n$ requests with the minimum total weight. In fact, the proofs in Section 3.1 imply that the $TA (v_{1})$ is a $(2 c - 1)$ -approximation algorithm for CS $_{s u m}$ and the $TA (v_{2})$ is a c-approximation algorithm for ${CS}_{l a t}$ .

4. The Case $c = 2$ : Algorithms and Their Analysis

In this section, we consider the ride-sharing problems

{CS}_{s u m}

{CS}_{s u m, s = t}

{CS}_{l a t}

, and

{CS}_{l a t, s = t}

with capacity

c = 2

and each car serving exactly two requests, i.e.,

m = 2 n

(see [22]). In Section 4.1, we propose and analyze the match-and-assign algorithm (

MA

). Next, in Section 4.2, we analyze the combined algorithm (

CA

), i.e., the better of the two algorithms, the

MA

and

TA

For convenience, we explicitly write the quantity

SHP (s_{i}, {i, j})

{CS}_{s u m}

by a parameter

u_{i j}

as follows:

\begin{matrix} u_{i j} \\ \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})} \\ f o r e a c h i, j \in R \times R, i \neq j . \end{matrix}

(20)

Notice that the

u_{i j}

’s are not necessarily symmetric. Obviously,

u_{i j} \geq w (s_{i}, s_{j})

and

u_{j i} \geq w (s_{i}, s_{j})

. For

{CS}_{s u m, s = t}

, we have

u_{i j} = u_{j i} \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:

cost (k, {i, j}) = min {w (d_{k}, s_{i}) + u_{i j}, w (d_{k}, s_{j}) + u_{j i}} .

(21)

For convenience, we also explicitly write the quantity

SHWP (s_{i}, {i, j})

{CS}_{s u m}

by a parameter

μ_{i j}

as follows:

\begin{matrix} μ_{i j} \\ \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}), \\ w (s_{i}, t_{i}) + w (s_{i}, t_{i}, s_{j}, t_{j})} f o r e a c h i, j \in R \times R, i \neq j . \end{matrix}

(22)

Notice that the

μ_{i j}

’s are not necessarily symmetric. For

{CS}_{l a t, s = t}

, we have

μ_{i j} = μ_{j i} \equiv w (s_{i}, s_{j})

The latency needed to serve requests in

R_{k} = {i, j}

(

k \in D

) is then given by:

wait (k, {i, j}) = min {2 w (d_{k}, s_{i}) + μ_{i j}, 2 w (d_{k}, s_{j}) + μ_{j i}} .

(23)

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

We came up with a match-and-assign algorithm, the

MA (α, 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} ({i, j})

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} ({i, j}) \equiv \frac{v_{i j} + v_{j i}}{2}, v \in {u, μ} .

(24)

v_{4} (k, {i, j}) \equiv min {α w (d_{k}, s_{i}) + \frac{v_{i j} - v_{j i}}{2}, α w (d_{k}, s_{j}) - \frac{v_{i j} - v_{j i}}{2}}, α \in {1, 2}, v \in {u, μ} .

(25)

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

The resulting quantity is

v_{3} (M_{3}) + v_{4} (M_{4})

; we now prove two lemmas concerning this quantity, which will be of use in the approximation analysis.

Algorithm 2 Match-and-assign algorithm (

MA (α, 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} ({i, j})$ ;
Find a min-weight matching: Find a minimum weight perfect matching $M_{3}$ in $G_{3} \equiv (R, v_{3})$ with weight $v_{3} (M_{3})$ .

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} (M_{4})$ .

3:

Output:

MA = M_{4}

Lemma 5.

For each

α \in {1, 2}

and

v \in {u, μ}

, we have:

\begin{matrix} v_{3} (M_{3}) + v_{4} (M_{4}) = \sum_{(k, {i, j}) \in M_{4}} min {α w (d_{k}, s_{i}) + v_{i j}, α w (d_{k}, s_{j}) + v_{j i}} . \end{matrix}

Proof.

Without loss of generality, for any

{i, j} \in M_{3}

, suppose

v_{i j} - v_{j i} \geq 0

(the other case is symmetric).

\begin{matrix} v_{3} (M_{3}) + v_{4} (M_{4}) = \sum_{{i, j} \in M_{3}} \frac{v_{i j} + v_{j i}}{2} + \\ = \sum_{(k, {i, j}) \in M_{4}} min {α w (d_{k}, s_{i}) + \frac{v_{i j} - v_{j i}}{2}, α w (d_{k}, s_{j}) - \frac{v_{i j} - v_{j i}}{2}} \\ = \sum_{(k, {i, j}) \in M_{4}} min {α w (d_{k}, s_{i}) + v_{i j}, α w (d_{k}, s_{j}) + v_{j i}} . \end{matrix}

The first equality follows from the definition of

v_{3}

and

v_{4}

(see Equations (24) and (25)). □

Lemma 6.

For

α \in {1, 2}

v \in {u, μ}

, and for each allocation M, we have:

\begin{matrix} v_{3} (M_{3}) + v_{4} (M_{2}) \leq \sum_{(k, {i, j}) \in M} \frac{α w (d_{k}, s_{i}) + α w (d_{k}, s_{j}) + v_{i j} + v_{j i}}{2} . \end{matrix}

Proof.

For an allocation M, let

M_{R} = {R_{k} : (k, R_{k}) \in M}

. Observe that:

v_{3} (M_{3}) \leq \sum_{{i, j} \in M_{R}} \frac{v_{i j} + v_{j i}}{2},

(26)

since

M_{3}

is a minimum weight perfect matching in

G_{3} \equiv (R, v_{3})

We claim that:

v_{4} (M_{4}) \leq \sum_{(k, {i, j}) \in M} \frac{α w (d_{k}, s_{i}) + α 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

MA

. Based on M and

M_{3}

, we construct the graph

G^{'} = (R \cup D, M_{1} \cup {({i, k}, {j, k}) : (k, {i, j}) \in M})

. Note that every vertex in graph

G^{'}

has degree two. Thus, we can partition

G^{'}

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}, \dots, k_{h}, i_{1})

, where

{i_{s}, j_{s}} \in M_{3}

(k_{s}, {j_{s}, i_{s + 1}}) \in M

for

1 \leq 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_{ℓ}^{c}

and

M_{r}^{c}

$M_{ℓ}^{c} = {({i_{1}, j_{1}}, k_{1}), ({i_{2}, j_{2}}, k_{2}), \dots, ({i_{h}, j_{h}}, k_{h})}$ ,
$M_{r}^{c} = {(k_{1}, {i_{2}, j_{2}}), (k_{2}, {i_{3}, j_{3}}), \dots, (k_{h}, {i_{1}, j_{1}})}$ .

Obviously, both

M_{ℓ} \equiv ⋃_{c \in C} M_{ℓ}^{c}

and

M_{r} \equiv ⋃_{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}) \leq α w (d_{a}, s_{i}) + \frac{v_{i j} - v_{j i}}{2} + α w (d_{b}, s_{j}) - \frac{v_{i j} - v_{j i}}{2} = α (w (d_{a}, s_{i}) + w (d_{b}, s_{j})) .

Similarly, it follows that:

v_{4} (a, {i, j}) + v_{4} (b, {i, j}) \leq α (w (d_{a}, s_{j}) + w (d_{b}, s_{i}))

. Thus, for each

c \in C

\sum_{(k, {i, j}) \in M_{ℓ}^{c}} v_{4} (k, {i, j}) + \sum_{(k, {i, j}) \in M_{r}^{c}} v_{4} (k, {i, j}) \leq \sum_{\begin{matrix} {i, k}, {j, k} \in c \\ (k, {i, j}) \in M \end{matrix}} α (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_{ℓ}

and

M_{r}

are a feasible assignment in

G_{4} = (D \cup M_{3}, v_{4})

. Thus:

\begin{matrix} v_{4} (M_{4}) \leq \sum_{c \in C} min {v_{4} (M_{ℓ}^{c}), v_{4} (M_{r}^{c})} \\ \leq \frac{1}{2} \sum_{c \in C} (\sum_{(k, {i, j}) \in M_{ℓ}^{c}} v_{4} (k, {i, j}) + \sum_{(k, {i, j}) \in M_{r}^{c}} v_{4} (k, {i, j})) \\ \leq \sum_{(k, {i, j}) \in M} \frac{α w (d_{k}, s_{i}) + α w (d_{k}, s_{j})}{2} . \end{matrix}

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

Lemma 7.

For any two requests i and j, we have:

max {u_{i j}, u_{j i}} - min {u_{i j}, u_{j i}} \leq w (s_{i}, s_{j});

and:

u_{i j} \leq 2 u_{j i} .

Without loss of generality, suppose

u_{i j} \geq u_{j i}

u_{i j} \leq w (s_{i}, s_{j}) + u_{j i}

. Since

w (s_{i}, s_{j}) \leq min {u_{i j}, u_{j i}}

, we have

u_{i j} \leq 2 u_{j i}

for any two requests i and j.

Theorem 3.

The

MA (1, u)

is a two-approximation algorithm for

{CS}_{s u m}

. Moreover, there exists an instance I for which

cost (MA (I)) = 2 cost (M^{*} (I))

Proof.

We assume w.l.o.g. that, for each

(k, {i, j}) \in M^{*}

cost (k, {i, j}) = w (d_{k}, s_{i}) + u_{i j}

. We have:

\begin{matrix} cost (MA (1, u)) = \sum_{(k, {i, j}) \in MA} min {w (d_{k}, s_{i}) + u_{i j}, w (d_{k}, s_{j}) + u_{j i}} \end{matrix}

(29)

\begin{matrix} = v_{3} (M_{3}) + v_{4} (M_{4}) \end{matrix}

(30)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} \frac{w (d_{k}, s_{i}) + w (d_{k}, s_{j}) + u_{i j} + u_{j i}}{2} \end{matrix}

(31)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} \frac{2 w (d_{k}, s_{i}) + w (s_{i}, s_{j}) + 3 u_{i j}}{2} \end{matrix}

(32)

\begin{matrix} \leq \frac{1}{2} \sum_{(k, {i, j}) \in M^{*}} (2 w (d_{k}, s_{i}) + 4 u_{i j}) \end{matrix}

(33)

\begin{matrix} \leq \frac{1}{2} \sum_{(k, {i, j}) \in M^{*}} 4 cost (k, {i, j}) \end{matrix}

(34)

\begin{matrix} = 2 cost (M^{*}) . \end{matrix}

(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_{j i} \leq 2 u_{i j}

for each request pair

{i, j} \in R^{2}

based on Lemma 7. Inequality (33) follows from

w (s_{i}, s_{j}) \leq u_{i j}

. Notice that

cost (MA (I)) \leq 2 cost (M^{*} (I))

is actually tight by the instance depicted in Figure 2. □

Theorem 4.

The

MA (1, u)

is a

3 / 2

-approximation algorithm for

{CS}_{s u m, s = t}

. Moreover, there exists an instance I for which

cost (MA (I)) = 3 / 2 cost (M^{*} (I))

Proof.

\begin{matrix} cost (MA (1, u)) = \sum_{(k, {i, j}) \in MA} min {w (d_{k}, s_{i}) + u_{i j}, w (d_{k}, s_{j}) + u_{j i}} \end{matrix}

(36)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} w (s_{i}, s_{j}) + \frac{w (d_{k}, s_{i}) + w (d_{k}, s_{j})}{2} \end{matrix}

(37)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} 3 / 2 cost (k, {i, j}) \end{matrix}

(38)

\begin{matrix} \leq 3 / 2 cost (M^{*}) \end{matrix}

(39)

Equation (36) follows from (20). Inequality (37) follows from Lemma 5 and 6, and

u_{i j} = u_{j i} = w (s_{i}, s_{j})

To see that the equality may hold in

cost (MA (I)) \leq 3 / 2 cost (M^{*} (I))

, 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

cost (M^{*} (I)) = 2

. Note that

{MR}^{*} = {{1, 3}, {2, 4}}

. Let us now analyze the performance of

MA (1, u)

on this instance. Based on the u values as defined in (20),

MA (1, u)

can find, in the first step, matching

M_{3} = {{1, 2}, {3, 4}}

because

v_{3} (M_{3}) = v_{3} ({MR}^{*}) = 2

. Then, no matter how the second step assigns the request pairs to cars, the total waiting time of

MA (1, u)

will be three. □

Theorem 5.

The

MA (2, μ)

is a two-approximation algorithm for

{CS}_{l a t}

. Moreover, there exists an instance I of

{CS}_{l a t, s = t}

for which

wait (MA (I)) = 2 wait (M^{*} (I))

Proof.

\begin{matrix} wait (MA (2, μ)) = \sum_{(k, {i, j}) \in MA} min {2 w (d_{k}, s_{i}) + μ_{i j}, 2 w (s_{k}, s_{j}) + μ_{j i}} \end{matrix}

(40)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} \frac{2 w (d_{k}, s_{i}) + μ_{i j} + 2 w (d_{k}, s_{j}) + μ_{j i}}{2} \end{matrix}

(41)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} \frac{4 min {w (d_{k}, s_{i}), w (d_{k}, s_{j})} + μ_{i j} + 2 w (s_{i}, s_{j}) + μ_{j i}}{2} \end{matrix}

(42)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} min {4 w (d_{k}, s_{i}) + 2 μ_{i j}, 4 w (d_{k}, s_{j}) + 2 μ_{j i}} \end{matrix}

(43)

\begin{matrix} = \sum_{(k, {i, j}) \in M^{*}} 2 wait (k, {i, j}) \end{matrix}

(44)

\begin{matrix} = 2 wait (M^{*}) \end{matrix}

(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}) \leq min {μ_{i j}, μ_{j i}}

To see that the equality may hold in

wait (MA (I)) \leq 2 wait (M^{*} (I))

, 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

wait (M^{*} (I)) = 4

. Note that

M_{R}^{*} = {{1, 3}, {2, 4}}

. Let us now analyze the performance of the

MA (2, μ)

on instance I.

Based on the

μ

values as defined in (22), the

MA (2, μ)

can find, in the first step, matching

M_{3} = {{1, 2}, {3, 4}}

because

v_{3} (M_{3}) = v_{3} (M_{R}^{*}) = 8

. Then, no matter how the second step assigns the request pairs to cars, the total waiting time of the

MA (2, μ)

will be eight. □

4.2. The Combined Algorithm and Its Analysis

The

{CA}_{s u m}

runs the

MA (1, u)

and

TA (v_{1})

and then outputs the better of the two solutions. We now state the main result for

{CS}_{s u m}

Theorem 6.

The

{CA}_{s u m}

is a two-approximation algorithm for

{CS}_{s u m}

. Moreover, there exists an instance I for which

cost ({CA}_{s u m} (I)) = 2 cost (M^{*} (I))

Proof.

It is obvious that, as

cost ({CA}_{s u m}) = m i n {cost (MA (1, u)), cost (TA (v_{1}))}

, Theorems 1 and 3 imply that the

{CA}_{s u m}

is a two-approximation algorithm for

{CS}_{s u m}

. 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^{*} (I) = {(k_{1}, {1, 3}), (k_{2}, {2, 4})}

with cost(

M^{*} (I)) = 2

. Note that

M_{R}^{*} = {{1, 3}, {2, 4}}

. Let us now analyze the performance of the

MA (1, u)

and

TA (v_{1})

on instance I.

Based on the

u_{i j}

values as defined in (20), the

MA (1, u)

can find, in the first step, matching

M_{3} = {{1, 2}, {3, 4}}

with

v_{3} (M_{3}) = v_{3} (M_{R}^{*}) = 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

MA (1, u)

will be four.

The

TA (v_{1})

may assign Requests 1 and 2 to Car 1 and Requests 3 and 4 to Car 2 since:

\begin{matrix} v_{1} ({(k_{1}, 1), (k_{1}, 2), (k_{2}, 3), (k_{2}, 4)}) = v_{1} ({(k_{1}, 1), (k_{1}, 3), (k_{2}, 2), (k_{2}, 4)}) = 6 . \end{matrix}

Thus, the total cost of the

TA (v_{1})

is four.

To summarize, the instance in Figure 2 is a worst-case instance for the

{CA}_{s u m}

. □

Theorem 7.

The

{CA}_{s u m}

is a

7 / 5

-approximation algorithm for

{CS}_{s u m, s = t}

. Moreover, there exists an instance I for which

cost ({CA}_{s u m} (I)) = 7 / 5 cost (M^{*} (I))

Proof.

We assume w.l.o.g. that, for each

(k, {i, j}) \in M^{*}

cost (k, {i, j}) = w (d_{k}, s_{i}) + u_{i j}

. We have:

\begin{matrix} 5 cost ({CA}_{s u m}) \leq 4 cost (MA (1, u)) + cost (TA (v_{1})) \end{matrix}

(46)

\begin{matrix} \leq 4 (v_{3} (M_{3}) + v_{4} (M_{4})) + v_{1} (M_{1}) \end{matrix}

(47)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} (4 w (d_{k}, s_{i}) + 3 w (d_{k}, s_{j}) + 4 w (s_{i}, s_{j})) \end{matrix}

(48)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} (7 w (d_{k}, s_{i}) + 7 w (s_{i}, s_{j})) \end{matrix}

(49)

\begin{matrix} = \sum_{(k, {i, j}) \in M^{*}} 7 cost (k, {i, j}) \end{matrix}

(50)

\begin{matrix} = 7 cost (M^{*}) \end{matrix}

(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

cost (k, {i, j}) = w (d_{k}, s_{i}) + u_{i j}

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, \dots, 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

cost (M^{*} (I)) = 10

. Note that

M_{R}^{*} = {{1, 3}, {2, 4}, {5, 6}, {7, 8}}

. Let us now analyze the performance of

MA (1, u)

and

TA (v_{1})

on instance I.

Based on the

u_{i j}

values as defined in (20), the

MA (1, u)

can find, in the first step, matching

M_{3} = {{1, 2}, {3, 4}, {5, 6}, {7, 8}}

because

v_{3} (M_{3}) = v_{3} (M_{R}^{*}) = 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

MA (1, u)

will be 14.

TA (v_{1})

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{matrix} v_{1} ({(k_{3}, 5), (k_{3}, 7), (k_{4}, 6), (k_{4}, 8)}) = v_{1} ({(k_{3}, 5), (k_{3}, 6), (k_{4}, 7), (k_{4}, 8)}) = 6 . \end{matrix}

Thus, the total cost of the

TA (v_{1})

is 14.

To summarize, the instance in Figure 3 is a worst-case instance for the

{CA}_{s u m}

. □

The

{CA}_{l a t}

runs the

MA (2, μ)

and

TA (v_{2})

and then outputs the better of the two solutions. We now state the main result for

{CS}_{l a t}

. The following lemma is useful to analyze the performance of the CA for

{CS}_{l a t}

Lemma 8.

For each

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

\begin{matrix} min {2 w (d_{k}, s_{i}, t_{i}) + w (t_{i}, d_{k}, s_{j}, t_{j}), 2 w (d_{k}, s_{j}, t_{j}) + w (t_{j}, d_{k}, s_{i}, t_{i})} \\ + 2 w (d_{k}, s_{i}) + 2 w (d_{k}, s_{j}) + μ_{i j} + μ_{j i} \\ \leq min {8 w (d_{k}, s_{i}) + 5 μ_{i j}, 8 w (d_{k}, s_{j}) + 5 μ_{j i}} . \end{matrix}

Proof.

We first prove

2 w (d_{k}, s_{i}, t_{i}) + w (t_{i}, d_{k}, s_{j}, t_{j}) + 2 w (d_{k}, s_{i}) + 2 w (d_{k}, s_{j}) + μ_{i j} + μ_{j i} \leq 8 w (d_{k}, s_{i}) + 5 μ_{i j}

. We distinguish three cases based on

μ_{i j}

: (1)

μ_{i j} = w (s_{i}, t_{i}) + w (s_{i}, t_{i}, s_{j}, t_{j})

; (2)

μ_{i j} = w (s_{i}, s_{j}, t_{i}) + w (s_{i}, s_{j}, t_{i}, t_{j})

; (3)

μ_{i j} = w (s_{i}, s_{j}, t_{j}) + w (s_{i}, s_{j}, t_{j}, t_{i})

Consider Case (1):

μ_{i j} = w (s_{i}, t_{i}) + w (s_{i}, t_{i}, s_{j}, t_{j})

. We have:

2 w (d_{k}, s_{i}) + μ_{i j} = 2 w (d_{k}, s_{i}) + 2 w (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}) \leq w (d_{k}, s_{i}) + w (s_{i}, t_{i}),

w (d_{k}, s_{j}) \leq (d_{k}, s_{i}) + w (s_{i}, t_{i}) + w (t_{i}, s_{j}) .

Based on the definition of

μ

, we know:

μ_{i j} = 2 w (s_{i}, t_{i}) + w (t_{i}, s_{j}) + w (s_{j}, t_{j}),

μ_{j i} \leq 2 w (s_{j}, t_{j}) + w (t_{j}, s_{i}) + w (s_{i}, t_{i}) \leq 3 w (s_{j}, t_{j}) + 2 w (s_{i}, t_{i}) + w (t_{i}, s_{j}) .

Using the above inequalities, we have:

\begin{matrix} 2 w (d_{k}, s_{i}, t_{i}) + w (t_{i}, d_{k}, s_{j}, t_{j}) + 2 w (d_{k}, s_{i}) + 2 w (d_{k}, s_{j}) + μ_{i j} + μ_{j i} \\ \leq 8 w (d_{k}, s_{i}) + 10 w (s_{i}, t_{i}) + 5 w (t_{i}, s_{j}) + 5 w (s_{j}, t_{j}) \\ = 8 w (d_{k}, s_{i}) + 5 μ_{i j} . \end{matrix}

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

Analogously, we have

2 w (d_{k}, s_{j}, t_{j}) + w (t_{j}, d_{k}, s_{i}, t_{i}) + 2 w (d_{k}, s_{i}) + 2 w (s_{k}, s_{j}) + μ_{i j} + μ_{j i} \leq 8 w (d_{k}, s_{j}) + 5 μ_{i j}

. □

Theorem 8.

The

{CA}_{l a t}

is a 5/3-approximation algorithm for

{CS}_{l a t}

Proof.

\begin{matrix} 3 wait ({CA}_{l a t}) \leq 2 wait (MA (2, μ)) + wait (TA (v_{2})) \end{matrix}

(52)

\begin{matrix} \leq 2 (v_{3} (M_{3}) + v_{4} (M_{4})) + v_{2} (M_{2}) \end{matrix}

(53)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} min {8 w (d_{k}, s_{i}) + 5 μ_{i j}, 8 w (d_{k}, s_{j}) + 5 μ_{j i}} \end{matrix}

(54)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} 5 min {2 w (d_{k}, s_{i}) + μ_{i j}, 2 w (d_{k}, s_{j}) + μ_{j i}} \end{matrix}

(55)

\begin{matrix} = 5 wait (M^{*}) . \end{matrix}

(56)

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

Theorem 9.

The

{CA}_{l a t}

is a 3/2-approximation algorithm for

{CS}_{l a t, s = t}

. Moreover, there exists an instance I for which

wait ({CA}_{l a t} (I)) = 3 / 2 wait (M^{*} (I))

Proof.

We assume w.l.o.g. that, for each

(k, {i, j}) \in M^{*}

wait (k, {i, j}) = 2 w (d_{k}, s_{i}) + w (s_{i}, s_{j})

. We have:

\begin{matrix} 2 wait (CA (2, μ)) \leq wait (MA (2, μ)) + wait (TA (v_{2})) \end{matrix}

(57)

\begin{matrix} = \sum_{(k, {i, j}) \in MA} min {2 w (d_{k}, s_{i}) + μ_{i j}, 2 w (s_{k}, s_{j}) + μ_{j i}} \end{matrix}

(58)

\begin{matrix} + \sum_{(k, {i, j}) \in TA (v_{2})} min {2 w (d_{k}, s_{i}) + μ_{i j}, 2 w (s_{k}, s_{j}) + μ_{j i}} \end{matrix}

(59)

\begin{matrix} = v_{3} (M_{3}) + v_{4} (M_{4}) + v_{2} (M_{2}) \end{matrix}

(60)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} (w (s_{i}, s_{j}) + w (d_{k}, s_{i}) + w (d_{k}, s_{j}) + 3 w (d_{k}, s_{i}) + w (d_{k}, s_{j})) \end{matrix}

(61)

\begin{matrix} \leq \sum_{(k, {i, j}) \in M^{*}} (3 w (s_{i}, s_{j}) + 6 w (d_{k}, s_{i})) \end{matrix}

(62)

\begin{matrix} = \sum_{(k, {i, j}) \in M^{*}} 3 wait (k, {i, j}) \end{matrix}

(63)

\begin{matrix} = 3 wait (M^{*}) . \end{matrix}

(64)

Equation (59) follows from (23). Equation (60) follows from Lemma 5. Inequality (62) follows from the triangle inequality. Equation (63) follows from

wait (

k, {i, j}) = 2 w (d_{k}, s_{i}) + μ_{i j}

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, \dots, 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{matrix} {(k_{1}, {1, 3}), (k_{2}, {2, 4}), (k_{3}, {5, 6}), (k_{4}, {7, 8})} \end{matrix}

with

wait (M^{*} (I)) = 8

. Note that

M_{R}^{*} = {{1, 3}, {2, 4}, {5, 6}, {7, 8}}

. Let us now analyze the performance of the

MA (2, μ)

and

TA (v_{2})

on instance I.

Based on the

μ_{i j}

values as defined in (22), the

MA (2, μ)

can find, in the first step, matching

M_{3} = {{1, 2}, {3, 4}, {5, 6}, {7, 8}}

because

v_{3} (M_{3}) = v_{3} (M_{R}^{*}) = 4

. Then, no matter how the second step matches the pairs to cars, the total waiting time of the

MA (2, μ)

will be 12.

The

TA (v_{2})

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{matrix} v_{2} ({(k_{3}, 5), (k_{3}, 7), (k_{4}, 6), (k_{4}, 8)}) = v_{2} ({(k_{3}, 5), (k_{3}, 6), (k_{4}, 7), (k_{4}, 8)}) = 8 . \end{matrix}

Thus, the total waiting time of the

TA (v_{2})

is 12.

To summarize, the instance in Figure 5 is a worst-case instance for the combined algorithm

{CA}_{l a t}

. □

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

(2 c - 1)

-approximation (resp. c-approximation) algorithm for

{CS}_{s u m}

and

{CS}_{s u m, s = t}

(resp.

{CS}_{l a t}

and

{CS}_{l a t, s = t}

). Furthermore, for the special case where capacity

c = 2

and

m = c \cdot 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.

Author Contributions

Investigation, conceptualization, methodology, formal analysis, K.L. and F.C.R.S.; writing—original draft preparation, K.L.; writing—review and editing, F.C.R.S. All authors have read and agreed to the published version of the manuscript.

Funding

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement number 754462 and funding from the NWO Gravitation Project NETWORKS, Grant Number 024.002.003.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

References

Uber. 2021. Available online: https://www.uber.com/nl/en/ride/uberpool/ (accessed on 1 December 2021).
TransVision. 2021. Available online: https://www.transvision.nl/ (accessed on 1 December 2021).
Tafreshian, A.; Masoud, N.; Yin, Y. Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions. Serv. Sci. 2020, 12, 44–60. [Google Scholar] [CrossRef]
Agatz, N.; Erera, A.L.; Savelsbergh, M.W.; Wang, X. Dynamic ride-sharing: A simulation study in metro Atlanta. Procedia-Soc. Behav. Sci. 2011, 17, 532–550. [Google Scholar] [CrossRef] [Green Version]
Luo, K.; Erlebach, T.; Xu, Y. Car-Sharing between Two Locations: Online Scheduling with Two Servers. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK, 27–31 August 2018; Volume 117, pp. 50:1–50:14. [Google Scholar]
Luo, K.; Erlebach, T.; Xu, Y. Car-Sharing on a Star Network: On-Line Scheduling with k Servers. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin, Germany, 13–16 March 2019; Volume 126, pp. 51:1–51:14. [Google Scholar]
Liu, H.; Luo, K.; Xu, Y.; Zhang, H. Car-Sharing Problem: Online Scheduling with Flexible Advance Bookings. In Proceedings of the Combinatorial Optimization and Applications—13th International Conference (COCOA 2019), Xiamen, China, 13–15 December 2019; Volume 11949, pp. 340–351. [Google Scholar]
Baldacci, R.; Maniezzo, V.; Mingozzi, A. An exact method for the car pooling problem based on lagrangean column generation. Oper. Res. 2004, 52, 422–439. [Google Scholar] [CrossRef]
Bei, X.; Zhang, S. Algorithms for trip-vehicle assignment in ride-sharing. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, LA, USA, 2–7 February 2018. [Google Scholar]
Masoud, N.; Jayakrishnan, R. A decomposition algorithm to solve the multi-hop peer-to-peer ride-matching problem. Transp. Res. Part B Methodol. 2017, 99, 1–29. [Google Scholar] [CrossRef] [Green Version]
Masoud, N.; Jayakrishnan, R. A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ride-sharing system. Transp. Res. Part B Methodol. 2017, 106, 218–236. [Google Scholar] [CrossRef]
Alonso-Mora, J.; Samaranayake, S.; Wallar, A.; Frazzoli, E.; Rus, D. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. Natl. Acad. Sci. USA 2017, 114, 462–467. [Google Scholar] [CrossRef] [PubMed] [Green Version]
Pavone, M.; Smith, S.L.; Frazzoli, E.; Rus, D. Robotic load balancing for mobility-on-demand systems. Int. J. Robot. Res. 2012, 31, 839–854. [Google Scholar] [CrossRef]
Agatz, N.; Campbell, A.; Fleischmann, M.; Savelsbergh, M. Time slot management in attended home delivery. Transp. Sci. 2011, 45, 435–449. [Google Scholar] [CrossRef] [Green Version]
Stiglic, M.; Agatz, N.; Savelsbergh, M.; Gradisar, M. Making dynamic ride-sharing work: The impact of driver and rider flexibility. Transp. Res. Part E Logist. Transp. Rev. 2016, 91, 190–207. [Google Scholar] [CrossRef]
Wang, X.; Agatz, N.; Erera, A. Stable matching for dynamic ride-sharing systems. Transp. Sci. 2018, 52, 850–867. [Google Scholar] [CrossRef]
Ashlagi, I.; Burq, M.; Dutta, C.; Jaillet, P.; Saberi, A.; Sholley, C. Edge weighted online windowed matching. In Proceedings of the 2019 ACM Conference on Economics and Computation, Phoenix, AZ, USA, 24–28 June 2019; pp. 729–742. [Google Scholar]
Lowalekar, M.; Varakantham, P.; Jaillet, P. Competitive Ratios for Online Multi-capacity Ridesharing. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’20), Auckland, New Zealand, 9–13 May 2020; pp. 771–779. [Google Scholar]
Guo, X.; Luo, K. Algorithms for online car-sharing problem. In Proceedings of the CALDAM 2022: The 8th Annual International Conference on Algorithms and Discrete Applied Mathematics, Puducherry, India, 10–12 February 2022. [Google Scholar]
Mori, J.C.M.; Samaranayake, S. On the Request-Trip-Vehicle Assignment Problem. In Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), Virtual Conference, 19–21 July 2021; pp. 228–239. [Google Scholar]
Burkard, R.; Dell’Amico, M.; Martello, S. Assignment Problems: Revised Reprint; SIAM: Philadelphia, PA, USA, 2012. [Google Scholar]
Luo, K.; Spieksma, F.C.R. Approximation Algorithms for Car-Sharing Problems. In Proceedings of the Computing and Combinatorics—26th International Conference (COCOON 2020), Atlanta, GA, USA, 29–31 August 2020; Volume 12273, pp. 262–273. [Google Scholar]
Goossens, D.; Polyakovskiy, S.; Spieksma, F.C.; Woeginger, G.J. Between a rock and a hard place: The two-to-one assignment problem. Math. Methods Oper. Res. 2012, 76, 223–237. [Google Scholar] [CrossRef]
Bandelt, H.J.; Crama, Y.; Spieksma, F. Approximation algorithms for multidimensional assignment problems with decomposable costs. Discret. Appl. Math. 1994, 49, 25–49. [Google Scholar] [CrossRef] [Green Version]
Queyranne, M.; Spieksma, F. Approximation algorithms for multi-index transportation problems with decomposable costs. Discret. Appl. Math. 1997, 76, 239–254. [Google Scholar] [CrossRef] [Green Version]
Williamson, D.P.; Shmoys, D.B. The Design of Approximation Algorithms; Cambridge University Press: Cambridge, UK, 2011. [Google Scholar]

Figure 1. A worst-case instance for the transportation algorithm.

Figure 2. A worst-case instance for the

{CA}_{s u m}

{CS}_{s u m}

Figure 2. A worst-case instance for the

{CA}_{s u m}

{CS}_{s u m}

Figure 3. A worst-case instance for the

{CA}_{s u m}

{CS}_{s u m, s = t}

Figure 3. A worst-case instance for the

{CA}_{s u m}

{CS}_{s u m, s = t}

Figure 4. A worst-case instance of the

MA (2, μ)

for

C S_{l a t, s = t}

Figure 4. A worst-case instance of the

MA (2, μ)

for

C S_{l a t, s = t}

Figure 5. A worst-case instance for the

{CA}_{l a t}

{CS}_{l a t, s = t}

Figure 5. A worst-case instance for the

{CA}_{l a t}

{CS}_{l a t, s = t}

Table 1. Overview of our results for ride-sharing problems with

c \geq 2

Table 1. Overview of our results for ride-sharing problems with

c \geq 2

Problem	TA
${CS}_{s u m}$	$(2 c - 1)$ $^{*}$ (Theorem 1)
${CS}_{s u m, s = t}$	$(2 c - 1)$ $^{*}$ (Theorem 1)
${CS}_{l a t}$	c $^{*}$ (Theorem 2)
${CS}_{l a t, s = t}$	c $^{*}$ (Theorem 2)

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

c = 2

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

c = 2

Problem	MA	TA	CA
${CS}_{s u m}$	2 $^{*}$ (Theorem 3)	3 $^{*}$ (Theorem 1)	2 $^{*}$ (Theorem 6)
${CS}_{s u m, s = t}$	1.5 $^{*}$ (Theorem 4)	3 $^{*}$ (Theorem 1)	7/5 $^{*}$ (Theorem 7)
${CS}_{l a t}$	2 $^{*}$ (Theorem 5)	2 $^{*}$ (Theorem 2)	5/3 (Theorem 8)
${CS}_{l a t, s = t}$	2 $^{*}$ (Theorem 5)	2 $^{*}$ (Theorem 2)	3/2 $^{*}$ (Theorem 9)

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Luo, K.; Spieksma, F.C.R. Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems. Algorithms 2022, 15, 30. https://doi.org/10.3390/a15020030

AMA Style

Luo K, Spieksma FCR. Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems. Algorithms. 2022; 15(2):30. https://doi.org/10.3390/a15020030

Chicago/Turabian Style

Luo, Kelin, and Frits C. R. Spieksma. 2022. "Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems" Algorithms 15, no. 2: 30. https://doi.org/10.3390/a15020030

APA Style

Luo, K., & Spieksma, F. C. R. (2022). Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems. Algorithms, 15(2), 30. https://doi.org/10.3390/a15020030

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems

Abstract

1. Introduction

1.1. Motivation

1.2. Related Work

1.3. Our Results

2. Preliminaries

3. The Transportation Algorithm and Its Analysis

3.1. The Transportation Algorithm

3.2. Approximation Analysis of the TA

3.3. Discussion

4. The Case $c = 2$ : Algorithms and Their Analysis

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

4.2. The Combined Algorithm and Its Analysis

5. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems

Abstract

1. Introduction

1.1. Motivation

1.2. Related Work

1.3. Our Results

2. Preliminaries

3. The Transportation Algorithm and Its Analysis

3.1. The Transportation Algorithm

3.2. Approximation Analysis of the TA

3.3. Discussion

4. The Case c = 2 : Algorithms and Their Analysis

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

4.2. The Combined Algorithm and Its Analysis

5. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

4. The Case $c = 2$ : Algorithms and Their Analysis