1 Introduction

In the real world, many ongoing decision-making activities in various areas, such as foreign currency trading [1, 2], vehicle routing [3, 4], and inventory ordering [5, 6], must be carried out in due course with no secure knowledge of future situations. However, such knowledge (e.g., future exchange rates in the foreign currency trading, service requests in the vehicle routing, and customer demands in the inventory ordering) often has a critical impact on the decision results.

Faced with this lack of knowledge, players of these decision-making games often formulate them as stochastic models based on assumptions about the future distributions of relevant quantities. Unfortunately, they may give some real-time solutions that are far from the relevant optimal solutions in some scenarios. Additionally, for most nontrivial decision making activities, it is difficult to estimate probability distributions accurately. In this case, the approach of probabilistic analysis is no longer suitable for addressing this type of ongoing decision-making problems. Another common way to deal with uncertain information in the decision-making problems is to model it as fuzziness (e.g., [7–9]), which also requires to make some estimations of the future uncertain situations. Unlike these two approaches, competitive analysis proposed by Sleator and Tarjan [10] provides a new appropriate framework to handle these problems, in which estimations of the uncertain situations are not required.

In the competitive analysis theory [11, 12], an algorithm is said to be online if its decisions are made in due course with no secure knowledge of future events. In general, due to the absence of information about the future, an online algorithm cannot make the decision in an optimal fashion. The performance of an online algorithm is measured against that of the optimal offline algorithm, which knows all the information when making its decision and thus, the decision can be optimized. The supremum of the ratio between the performances of these two algorithms is called competitive ratio. If the ratio is a constant α, then we say the online algorithm is an α-competitive algorithm. It implies that the cost of the online algorithm will not exceed α times of the optimal offline cost for any inputs. It is clear that this performance measure provides very robust statements about the performance of an online solution, against all possible future scenarios.

The online k-taxi problem [13] is a generalization of the k-server problem introduced by Manasse et al. [14], which has been extensively studied (see, e.g., [15–18]) as one of the famous basic online problems discussed in competitive analysis theory. In the k-server problem, k servers reside and move in a metric space to supply service. When a request is made by a point, one of the servers must be moved to the point to satisfy this request immediately. An algorithm which decides a server to satisfy the request at each step is said to be online if its decisions are made without the information about future requests. The goal is to minimize the total cost or distance of satisfying all requests.

In the online k-taxi problem, different from that in the k-server problem, each request contains two points, one of which is the start point making the request and the other is the destination point. It implies that there is a passenger at the start point to be picked up and taken to the destination point. When a request is made we must move one taxi to serve it immediately without the information about future possible requests. Some important results concerning this problem and its variants have been presented by Xu et al. [13], Xin and Ma [19], and Ma et al. [20–22].

In the traditional online k-taxi problem, it is usually assumed that the taxis are dispatched completely without any other information about future possible requests. In this paper, we consider the problem with a new feature that partial information about prospective possible service requests is provided in advance when deciding which taxi should be dispatched to serve the current request, and investigate the value of foreknowledge in this problem. This feature arises from realistic application background and also can be seen in many other online decision-making problems. In practice, the foreknowledge (i.e., information about future possible requests) may be provided by forecasting or encouraging customers to release their requests in advance (e.g., discounted price available for reservation).

In general, we can use the extra information, available in advance, to make better decisions. As the performance of an online algorithm is measured by competitive ratio in the traditional online k-taxi problem, it is natural to quantify the value of foreknowledge in the k-taxi problem with this new feature in the form of improved competitive ratios (with respect to the ratios of the traditional problem). This idea can also be seen in the online traveling salesman problem and traveling repairman problem with advanced information proposed by Jaillet and Wagner [3].

The rest of this paper is organized as follows. The problem description and formulation are presented in Sect. 2. Improved algorithms for the problem with foreknowledge are proposed in Sect. 3. Then the competitive analysis of the algorithms is given in Sect. 4. The value of foreknowledge as improved competitive ratios is also discussed in this section. Subsequently, Sect. 5 presents some numerical examples to illustrate the proposed algorithms as well as their performances in practice. Finally, conclusions are given in Sect. 6.

2 Problem description and formulation

Let G(V, E) denote a connected and edge weighted graph, where V is the metric space consisting of n (n ≥ 2) points, and E is the set of all weighted edges. For any points x, y ∊ V, d(x, y) indicates the distance of the shortest path between the points x and y. The weights of edges are symmetric and satisfy triangle inequality, i.e., for any x, y, z ∊ V, d(x, y) = d(y, x) and d(x, z) + d(z, y) ≥ d(x, y). For any points x ≠ y ∊ V, let d max = max d(x, y), d min = min d(x, y), and

$$\lambda = \frac{{d_{\hbox{max} } }}{{d_{\hbox{min} } }} .$$
(1)

It is clear that λ ≥ 1.

There are k (k ≥ 1) taxis that reside and move on the graph G to supply service. A service request r = (a, b) (a, b are different points in the given graph G), implies there is a passenger at point a that must be taken to b by a taxi. A service request sequence R consists of a series of service requests in turn, namely R = (r 1, r 2, …, r m ), where r i  = (a i , b i ), 1 ≤ i ≤ m. It is assumed that a i  ≠ b i in the following discussion, because if a i  = b i , the request r i does not exist in fact and this case is of no significance to discuss.

2.1 Traditional online k-taxi problem

Let us consider the following two problems:

  1. 1)

    Given a service request sequence R = (r 1, r 2, …, r m ) in advance, how to dispatch the taxis to minimize the total distance of serving all the requests?

  2. 2)

    How can we deploy the taxis to reduce the relevant moving distance when the service requests are received one by one, and each request is to be served immediately after it is made without any information about future possible requests?

Obviously, problem (1) is offline, whereas (2) is an online problem. The difference between them lies in whether complete information of the service request sequence is known while serving the current request. The latter is also known as the traditional online k-taxi problem. Due to the absence of information about future requests, it is hard to make the decision in an optimal fashion for problem (2).

Following many earlier studies on the classical online service dispatching problems (e.g. [13, 14, 23, 24]), this paper also assumes that when a new service request occurs, all taxis are available. In other words, when a new service request occurs, previous service requests have been completed and all the taxis are idle and ready to serve the new one.

For any request sequence R = (r 1, r 2, …, r m ), let \(C_{\text{OPT}} \left( R \right)\) denote the optimal (minimum) cost (total moving distance) required to complete the whole sequence with the optimal offline algorithm which knows the whole request sequence before it starts. Then, we can get that

$$C_{\text{OPT}} \left( R \right) \ge \sum\limits_{i\,=\,1}^{m} {d(a_{i} ,b_{i} )} ,$$
(2)

since \(\sum\nolimits_{i\,=\,1}^{m} {d(a_{i} ,b_{i} )}\) is the total distance travelled by passengers. It is the minimum cost that should be paid for serving the sequence R. In other words, if the sequence R is completed by taxis without the case that moving with on passenger, the cost of serving R is \(\sum\nolimits_{i\,=\,1}^{m} {d(a_{i} ,b_{i} )}\). However, in order to serve the requests, the taxis may should be dispatched to the start points of these requests first via moving with no passenger, and then the cost of serving R would be more than \(\sum\nolimits_{i\,=\,1}^{m} {d(a_{i} ,b_{i} )}\).

Let \(C_{\text{ON}} \left( R \right)\) denote the cost (total moving distance) of completing the whole sequences with an online algorithm which has not any knowledge about the future requests when serving the current request. If there exist constants α (α ≥ 1) and β satisfying the following inequality for any possible request sequence R,

$$C_{\text{ON}} \left( R \right) \le \alpha \cdot C_{\text{OPT}} \left( R \right) + \beta ,$$
(3)

the on-line algorithm is called an α-competitive algorithm and α is the competitive ratio. Our goal is to design some online algorithms with competitive ratios as small as possible.

2.2 Online k-taxi problem with foreknowledge

Now, let us consider the problem with some foreknowledge about the future possible requests. In other words, the online player is empowered with the ability of limited looking ahead and knows partial information about future requests in advance. More specifically, we consider the following two scenarios.

  1. 1)

    The online player only knows the start point of next request in advance when making the decision for serving the current request. The start point a 1 of the first request is given before the game plays. In the following whole process, when the i-th request r i occurs, the end point of the i-th request and the start point of the (i + 1)-th request \(r_{i + 1}\) are known by the player. In other words, the information of the (i + 1)-th request is not completely released before the i-th request is served, and only the start point is known in advance. In the following discussion, the online k-taxi problem in this scenario is denoted as P1.

  2. 2)

    The online player knows the next request (both the start point and the destination point) in advance when making the decision to serve the current request. The first request r 1 = (a 1, b 1) is known before the game plays. In the following whole process, when the i-th request r i occurs, the (i + 1)-th request \(r_{i + 1}\) is known by the player in advance (before r i is served). In other words, the information of the (i + 2)-th request is completely released after the i-th request and all of its previous requests are served. In this case, it is assumed that the order of serving the adjacent two requests can be exchanged. In the following discussion, the online k-taxi problem in this scenario is denoted as P2.

The problems are to decide which taxi is to be dispatched to serve the request when a new service request occurs on the basis that no more information about future possible requests is known. With the aid of partial information known in advance, it is anticipated that a better decision than that in the traditional online k-taxi problem can be made.

In the following sections, we propose some improved algorithms for this problem with foreknowledge, and quantify the value of foreknowledge in the form of improved competitive ratios with respect to the ratios of the traditional online k-taxi problem.

3 Improved algorithms with foreknowledge

In many classical online service dispatching problems (e.g. [13, 14, 23]), in order to play against the adversary and reduce the costs of serving the requests in worst cases, covering strategy has been extensively applied. In this section, we propose improved covering strategies for the online k-taxi problem with foreknowledge.

To implement the covering strategies, the initial locations of the taxis are assumed such that each point in the graph is occupied by at least one taxi if k ≥ n, or else (i.e., k < n) these k taxis are respectively located at k different points and there is a taxi at a 1 before the first service request comes in (as described in the previous formulation, the player with foreknowledge knows that the first request will occur at point a 1 before the service starts). Otherwise, we can make it happen by finite number of movements, and the moving distance will not exceed a constant \((k - 1)d_{\hbox{max} }\). This constant makes no influence on the discussion of competitive ratio [11]. In other words, we precondition the taxi locations such that these taxis cover distinct points as many as possible and the point a 1 is occupied by at least one taxi.

3.1 Improved covering strategy for problem P1

For the problem P1, in which the online player only knows the start point of next request in advance when making the decision to serve the current request, an online algorithm, called Improved Covering Strategy (denoted as S1), is designed as follows:

Improved Covering Strategy (S1):

For the i-th (i ≥ 1) service request r i  = (a i , b i ):

  1. 1)

    If there are taxis at both a i and b i , consider the following two cases:

    1. i)

      If there are more than one taxis at a i , choose one taxi arbitrarily and use it to take the passenger from a i to b i . The cost of completing this request is \(C_{{{\text{S}}1}} (r_{i} ) = d(a_{i} ,b_{i} )\). The move is denoted as a i  → b i .

    2. ii)

      If there is only one taxi at a i , the taxi at a i takes the passenger from a i to b i . Then if \(a_{i + 1}\) is without a taxi and \(d(a_{i + 1} ,b_{i} ) \le d(a_{i} ,b_{i} )\), the taxi moved from a i to b i continues to move to \(a_{i + 1}\). The cost of completing this request is \(C_{{{\text{S}}1}} (r_{i} ) \le 2d(a_{i} ,b_{i} )\), and the moves are denoted as \(a_{i} \to b_{i} \to a_{i + 1}\). Otherwise, the taxi moved from a i to b i moves back to a i . The cost of completing this request is \(C_{{{\text{S}}1}} (r_{i} ) = 2d(a_{i} ,b_{i} )\), and the moves are denoted as a i  → b i  → a i .

  2. 2)

    If there is a taxi at a i but no taxi at b i , the taxi at a i takes the passenger from a i to b i . The cost of completing this request is \(C_{{{\text{S}}1}} (r_{i} ) = d(a_{i} ,b_{i} )\). The move is denoted as a i  → b i .

  3. 3)

    If there is a taxi at b i but no taxi at a i , the taxi at b i moves to a i first and then takes the passenger from a i to b i . The cost of completing this request is \(C_{{{\text{S}}1}} (r_{i} ) = 2d(a_{i} ,b_{i} )\). The moves are denoted as b i  → a i  → b i .

  4. 4)

    If neither a i nor b i has a taxi (i ≥ 2 holds), the following two cases concerning the relationship between a i and a i−1 need to be considered.

    1. i)

      If a i  = a i−1, the taxi at b i−1 (since the (i − 1)-th service request is r i−1 = d(a i−1, b i−1), there must be a taxi at b i−1) moves to a i first, and then takes the passenger from a i to b i . The cost of completing this request is \(C_{{{\text{S}}1}} (r_{i} ) = d(a_{i - 1} ,b_{i - 1} ) + d(a_{i} ,b_{i} )\). The moves are denoted as b i−1 → a i  → b i .

    2. ii)

      If a i  ≠ a i−1 and k ≥ 2, schedule the nearest taxi (suppose it locates at c i , where \(c_{i} \ne a_{i + 1}\)) to a i and then use it to take the passenger from a i to b i . If a i  ≠ a i−1 and \(k = 1\), schedule the only one taxi (assume that it locates at c i ) to a i and then use it to take the passenger from a i to b i . The cost of completing this request is \(C_{{{\text{S}}1}} (r_{i} ) = d(c_{i} ,a_{i} ) + d(a_{i} ,b_{i} )\). The moves are denoted as c i  → a i  → b i .

The main idea behind the covering strategy is to let these k taxis always cover as many distinct points as possible in the whole game to reduce the total distance of the moves for serving all possible requests. Similar approaches were also proposed to obtain some good results in [13, 20, 22]. In fact, this idea is extensively applied in online algorithms (such as position maintaining strategy and greedy algorithm) for the k-server problem and its variants [14].

With the foreknowledge about the next request, the algorithm S1 considers how to serve the next request while processing the current one [case (1-ii)] and avoids dispatching the taxi that may be used to serve the next request to complete the current request [case (4-ii)]. Benefited by the foreknowledge, we will show that the competitive ratio of the covering strategy can be improved in the following sections.

3.2 Improved covering strategy for problem P2

For the problem P2, in which the online player knows the next request (both the start point and the destination point) in advance, a similar Improved Covering Strategy (denoted as S2) can be designed as follows. For the sake of simplicity, only the moves in each case of this strategy that have similar meaning as those in Strategy S1 are illustrated.

Improved Covering Strategy (S2):

For the i-th (i ≥ 1) service request r i  = (a i , b i ):

  1. 1)

    If there are taxis at both a i and b i , consider the following two cases:

    1. i)

      If there are more than one taxis at a i , the move is a i  → b i .

    2. ii)

      If there is only one taxi at a i , and if \(a_{i + 1}\) is without a taxi and \(d(a_{i + 1} ,b_{i} ) \le d(a_{i} ,b_{i} )\), the moves are \(a_{i} \to b_{i} \to a_{i + 1}\), or else, the moves are a i  → b i  → a i .

  2. 2)

    If there is a taxi at a i but no taxi at b i , the move is a i  → b i .

  3. 3)

    If there is a taxi at b i but no taxi at a i , the moves are b i  → a i  → b i .

  4. 4)

    If neither a i nor b i has a taxi (i ≥ 2 holds), consider the following four cases:

    1. i)

      If a i  = b i+1 and a i+1 has a taxi, move the taxi at a i+1 to b i+1 to serve the request \(r_{i + 1}\) first, and then move it from b i+1 (it is also a i ) to b i to serve the request r i . The moves are denoted as a i+1 → b i+1(a i ) → b i . Consequently, both requests r i and \(r_{i + 1}\) are served, and the strategy turns to serve \(r_{i + 2}\) next.

    2. ii)

      If a i  = b i+1 and a i+1 does not have a taxi, schedule the nearest (away from a i+1) taxi (suppose it locates at c i ) to a i+1 first, and then move it from a i+1 to b i+1 and from b i+1 (a i ) to b i to serve the requests \(r_{{i{ + }1}}\) and r i successively. The moves are denoted as c i  → a i+1 → b i+1(a i ) → b i . After that, both requests r i and \(r_{{i{ + }1}}\) are served, and the strategy turns to serve \(r_{i + 2}\).

    3. iii)

      If a i  = a i−1, the moves for serving r i are b i−1 → a i  → b i , and then go on to serve the next request \(r_{i + 1}\).

    4. iv)

      If a i  ≠ a i−1, a i  ≠ b i+1, and k ≥ 3, schedule the nearest taxi at point c i , where \(c_{i} \ne a_{i + 1}\) and \(c_{i} \ne b_{i + 1}\), to a i to serve r i . If a i  ≠ a i−1, a i  ≠ b i+1, and 1 ≤ k ≤ 2, schedule the nearest taxi at anywhere to serve r i . The moves for serving this request are denoted as c i  → a i  → b i . Then the strategy turns to serve \(r_{i + 1}\).

The difference between strategies S2 and S1 lies in the case (4). Since more foreknowledge is known in advance, strategy S2 considers more sophisticated cases to reduce the relevant moving distance for serving the requests.

4 Value of foreknowledge as improved competitive ratios

In this section, we first prove the competitive ratios of the proposed two covering strategies, and then compare them with those in the traditional online k-taxi problem. The value of foreknowledge is quantified as the improved competitive ratios.

4.1 Competitive ratio of strategy S1

For the competitive ratio of strategy S1, which is proposed for addressing the problem P1, we have the following theorems.

Theorem 1

For the problem P1 with k taxis, if k ≥ n − 1, the strategy S1 is an online algorithm with competitive ratio 2, where n (n ≥ 2) indicates the number of points of graph G.

Proof

As mentioned previously, we preconditioned the taxi locations such that these taxis cover distinct points as many as possible, and the point a 1 has at least one taxi, before the first service request comes. It is easy to verify that case (4) in the strategy S1 would never happen in the whole game if k ≥ n − 1, because there are enough taxis to cover at least n − 1 distinct points in the graph. Particularly, if k ≥ n, all the points are always occupied by at least one taxi after a request is served by the strategy S1; whereas if \(k = n - 1\), there is only one point unoccupied by a taxi. Consequently, the strategy does not make full use of the foreknowledge about the next request, and the problem degenerates to the traditional k-taxi problem.For the cases (1), (2) and (3), we have

$$C_{{{\text{S}}1}} (r_{i} ) \le 2d(a_{i} ,b_{i} ) .$$
(4)

Therefore,

$$\begin{aligned} C_{{\text{S1}}} \left( R \right) &\,=\,\sum\limits_{i\,=\,1}^{m} {C_{{\text{S1}}} (r_{i} )} + \beta \\ & \le \sum\limits_{i\,=\,1}^{m} {2d(a_{i} ,b_{i} )} + \beta \\ & \le 2C_{{\text{OPT}}} \left( R \right) + \beta , \\ \end{aligned}$$
(5)

where β is a constant denoting the cost of preconditioning. This proves Theorem 1.□

In order to prove the competitive ratio for a special case with k = n − 2, we present some lemmas first.

Lemma 1

For the problem P1 with k (k ≥ 2) taxis, if k = n − 2, at least one of the following inequalities concerning the cost of strategy S1 to serve the requests r i and \(r_{i + 1}\) holds,

$$C_{{{\text{S}}1}} (r_{i} ) + C_{{{\text{S}}1}} (r_{i + 1} ) \le 2d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} } ,$$
(6)

or

$$C_{{{\text{S}}1}} (r_{i} ) + C_{{{\text{S}}1}} (r_{i + 1} ) \le d(a_{i} ,b_{i} ) + 2d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} } .$$
(7)

Proof

For any request r i  = (a i , b i ), according to the strategy S1, we have

$$C_{{{\text{S}}1}} (r_{i} ) \le d(a_{i} ,b_{i} ) + d_{\hbox{max} } ,$$
(8)

since for any points x ≠ y ∊ V, \(d(x,y) \le d_{\hbox{max} }\) holds.

At the beginning of the game, there must exist a taxi at the point a 1 as described in the preconditioning. According to the cases (1) and (2) of the strategy S1, we can get that

$$C_{{{\text{S}}1}} (r_{1} ) \le 2d(a_{1} ,b_{1} ) .$$
(9)

Combining the inequalities (8) and (9), the following inequality holds,

$$C_{{{\text{S}}1}} (r_{1} ) + C_{{{\text{S}}1}} (r_{2} ) \le 2d(a_{1} ,b_{1} ) + d(a_{2} ,b_{2} ) + d_{\hbox{max} } .$$
(10)

Therefore, for the case i = 1, Lemma 1 holds.

The following proof considers the general case of the i-th (i ≥ 1) service request. For r i  = d(a i , b i ):

  1. I)

    If the strategy S1 serves the request by the moves described in the cases (1), (2) and (3), then \(C_{\text{S1}} (r_{i} ) \le 2d(a_{i} ,b_{i} )\) holds.

    Combining it with (8), we get

    $$C_{{{\text{S}}1}} (r_{i} ) + C_{{{\text{S}}1}} (r_{i + 1} ) \le 2d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} } .$$
    (11)

    Lemma 1 holds.

  2. II)

    If the strategy S1 serves the request by the moves described in the case (4-i), the cost of completing this request is \(C_{{{\text{S}}1}} (r_{i} )\,=\,d(a_{i - 1} ,b_{i - 1} ) + d(a_{i} ,b_{i} )\). By using (8), we get

    $$C_{{{\text{S}}1}} (r_{i - 1} ) + C_{{{\text{S}}1}} (r_{i} ) \le 2d(a_{i - 1} ,b_{i - 1} ) + d(a_{i} ,b_{i} ) + d_{\hbox{max} } .$$
    (12)

    Lemma 1 holds.

  3. III)

    If the strategy S1 serves the request by the moves described in the case (4-ii), it implies that neither a i nor b i has a taxi. The moves and status of the related points are illustrated in Fig. 1, in which the circle filled in black indicates that it is occupied by a taxi while the empty circle denotes the point without a taxi. Since there are n − 2 taxis in total, after serving the request r i  = d(a i , b i ), neither a i nor c i has a taxi, whereas b i and all the other points (not shown in Fig. 1) are with a taxi. The cost of completing request r i satisfies the formula that \(C_{{{\text{S}}1}} (r_{i} ) \le d(a_{i} ,b_{i} ) + d_{\hbox{max} }\). For the cost of serving next request r i+1 = d(a i+1, b i+1), we need to consider the following three cases.

    Fig. 1
    figure 1

    Illustration of the moves for serving r i by the strategy S1 in the case (4-ii)

    Full size image
  4. a)

    a i+1 ≠ a i and a i+1 ≠ b i .

    Under this condition there must be a taxi at a i+1, because after serving the last request r i , neither a i nor c i has a taxi, and all the other points are with a taxi, as shown in Fig. 1. Thus, to serve the request r i+1, only the cases (1) or (2) in the strategy S1 could occur and the cost satisfies the formula that \(C_{{{\text{S}}1}} (r_{i + 1} ) \le 2d(a_{i + 1} ,b_{i + 1} )\). Then we have

    $$C_{\text{S1}} (r_{i} ) + C_{{{\text{S}}1}} (r_{i + 1} ) \le d(a_{i} ,b_{i} ) + 2d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} } .$$
    (13)

    Lemma 1 holds.

  5. b)

    a i+1 = a i .

    1. (i)

      b i+1 = c i . As shown in Fig. 1, after serving the last request r i , neither a i nor c i has a taxi. So the strategy S1 moves the taxi at b i to a i+1 to serve the request r i+1. The cost is \(C_{{{\text{S}}1}} (r_{i + 1} )\,=\,d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )\). Then Lemma 1 holds.

    2. (ii)

      b i+1 ≠ c i . After serving r i , there must be a taxi at b i+1, since only these two points a i and c i are without a taxi. Then we have \(C_{{{\text{S}}1}} (r_{i + 1} )\,=\,2d(a_{i + 1} ,b_{i + 1} )\). Lemma 1 holds.

  6. c)

    a i+1 = b i .

    Under this condition, there must be a taxi at a i+1 as shown in Fig. 1. Similarly to the analysis in case (a), it is easy to verify that Lemma 1 holds.

The proof is completed. □

Lemma 2

For the problem P1 with k (k ≥ 2) taxis, if k  =  n − 2, the following inequality concerning the cost of strategy S1 to serve the requests r i and \(r_{i + 1}\) holds,

$$C_{\text{S1}} (r_{i} ) + C_{\text{S1}} (r_{i + 1} ) \le \frac{3 + \lambda }{2}\left[ {d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )} \right] .$$
(14)

Proof

For any requests r i  = (a i , b i ) and r i+1 = d(a i+1, b i+1), we can prove Lemma 2 in two cases following from Lemma 1.

  1. I)

    If \(C_{{{\text{S}}1}} (r_{i} ) + C_{{{\text{S}}1}} (r_{i + 1} ) \le 2d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} }\) holds, we have

    $$\begin{aligned} \frac{{C_{S1} (r_{i} ) + C_{S1} (r_{i + 1} )}}{{d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )}} & \le \frac{{2d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} } }}{{d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )}} \\ &\,=\,2 + \frac{{d_{\hbox{max} } - d(a_{i + 1} ,b_{i + 1} )}}{{d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )}}. \\ \end{aligned}$$
    (15)

    Since \(d_{\hbox{min} } \le d(a_{i} ,b_{i} ),d(a_{i + 1} ,b_{i + 1} ) \le d_{\hbox{max} }\), we get that

    $$\frac{{d_{\hbox{max} } - d(a_{i + 1} ,b_{i + 1} )}}{{d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )}} \le \frac{{d_{\hbox{max} } - d_{\hbox{min} } }}{{d_{\hbox{min} } + d_{\hbox{min} } }} = \frac{\lambda - 1}{2} .$$
    (16)

    By taking (16) into (15), (14) is verified.

  2. II)

    If \(C_{{{\text{S}}1}} (r_{i} ) + C_{{{\text{S}}1}} (r_{i + 1} ) \le d(a_{i} ,b_{i} ) + 2d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} }\) holds, similarly, we have

$$\begin{aligned} \frac{{C_{{{\text{S}}1}} (r_{i} ) + C_{{{\text{S}}1}} (r_{i + 1} )}}{{d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )}} & \le \frac{{d(a_{i} ,b_{i} ) + 2d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} } }}{{d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )}} \\ &\,=\,2 + \frac{{d_{\hbox{max} } - d(a_{i} ,b_{i} )}}{{d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )}} \\ & \le 2 + \frac{{d_{\hbox{max} } - d_{\hbox{min} } }}{{2d_{\hbox{min} } }} \\ &\,=\,\frac{3 + \lambda }{2}. \\ \end{aligned}$$
(17)

Lemma 2 is proved.□

Following from Lemma 2, we obtain the following theorem for the competitive ratio of strategy S1.

Theorem 2

For the problem P1 with k (k ≥ 2) taxis, if \(k{\,=\,}n - 2\) , the strategy S1 is an online algorithm with competitive ratio (3 + λ)/2, where n (n ≥ 2) indicates the number of points of graph G and \(\lambda \,=\, d_{ \hbox{max} } /d_{ \hbox{min} }\).

Proof

For any request sequence R = (r 1, r 2, …, r m ), if m is an even number, following from Lemma 2, we can easily get that

$$\begin{aligned} C_{{{\text{S}}1}} (R) &\,=\,\sum\limits_{i\,=\,1}^{m} {\left[ {C_{{{\text{S}}1}} (r_{i} )} \right]} + \beta \\ &\,=\,\left[ {C_{{{\text{S}}1}} (r_{1} ) + C_{{{\text{S}}1}} (r_{2} )} \right] + \left[ {C_{{{\text{S}}1}} (r_{3} ) + C_{S1} (r_{4} )} \right] + \cdots \\ & \quad + \left[ {C_{{{\text{S}}1}} (r_{m - 1} ) + C_{{{\text{S}}1}} (r_{m} )} \right] + \beta \\ & \le \frac{3 + \lambda }{2}\left[ {d(a_{1} ,b_{1} ) + d(a_{2} ,b_{2} ) + \cdots d(a_{m} ,b_{m} )} \right] + \beta \\ &\,=\,\frac{3 + \lambda }{2}\sum\limits_{i\,=\,1}^{m} d (a_{i} ,b_{i} ) + \beta \\ & \le \frac{3 + \lambda }{2}C_{\text{OPT}} (R) + \beta , \\ \end{aligned}$$
(18)

where β is a constant denoting the cost of preconditioning.

For the sequence R = (r 1, r 2, …, r m ), if m is an odd number, we have the following similar result.

$$\begin{aligned} C_{{{\text{S}}1}} (R) & \,=\, \sum\limits_{{i\,=\,1}}^{m} {\left[ {C_{{{\text{S}}1}} (r_{i} )} \right]} + \beta \\ &\,=\,\left[ {C_{{{\text{S}}1}} (r_{1} ) + C_{{{\text{S}}1}} (r_{2} )} \right] + \cdots + \left[ {C_{{{\text{S}}1}} (r_{{m - 2}} ) + C_{{{\text{S}}1}} (r_{{m - 1}} )} \right] \\ & \quad + C_{{{\text{S}}1}} (r_{m} ) + \beta \\ & \quad \le \frac{{3 + \lambda }}{2}\left[ {d(a_{1} ,b_{1} ) + d(a_{2} ,b_{2} ) + \cdots d(a_{{m - 1}} ,b_{{m - 1}} )} \right] \\ & \quad + C_{{{\text{S}}1}} (r_{m} ) + \beta \\ & \,=\, \frac{{3 + \lambda }}{2}\sum\limits_{{i\,=\,1}}^{m} d (a_{i} ,b_{i} ) - \frac{{3 + \lambda }}{2}d(a_{m} ,b_{m} ) + C_{{{\text{S}}1}} (r_{m} ) + \beta \\ & \quad \le \frac{{3 + \lambda }}{2}C_{{{\text{OPT}}}} (R) + \beta ^{\prime } , \\ \end{aligned}$$
(19)

where β ′ is a constant such that

$$\begin{aligned} \beta^{\prime }&\,=\,- \frac{3 + \lambda }{2}d(a_{m} ,b_{m} ) + C_{{{\text{S}}1}} (r_{m} ) + \beta \\ & \le - \frac{3 + \lambda }{2}d_{\hbox{min} } + d_{\hbox{max} } + \beta . \\ \end{aligned}$$
(20)

Formula (19) just has a different constant term comparing to (18), which makes no influence to the discussion of competitive ratio while m → ∞. The proof is completed. □

Theorem 3

For the problem P1 with k taxis, if 1 ≤ k ≤ n − 3, the strategy S1 is an online algorithm with competitive ratio \(1{ + }\lambda\) , where n (n ≥ 2) indicates the number of points of graph G and \(\lambda \,= \,d_{ \hbox{max} } /d_{ \hbox{min} }\).

Proof

Since for any request r i  = (a i , b i ), \(C_{{{\text{S}}1}} (r_{i} ) \le d(a_{i} ,b_{i} ) + d_{ \hbox{max} }\) holds, we have

$$\begin{aligned} C_{{{\text{S}}1}} \left( R \right)&\,=\,\sum\limits_{i = 1}^{m} {C_{{{\text{S}}1}} (r_{i} )} + \beta \\& \le \sum\limits_{i = 1}^{m} {\left[ {d(a_{i} ,b_{i} ) + d_{\hbox{max} } } \right]} + \beta \\& \le \left( {1 + \lambda } \right)\sum\limits_{i\,=\,1}^{m} {d(a_{i} ,b_{i} )} + \beta \\& \le \left( {1 + \lambda } \right)C_{\text{OPT}} \left( R \right) + \beta . \\ \end{aligned}$$
(21)

Theorem 3 is proved.□

In summary, for the problem P1 with k (k ≥ 1) taxis on a graph with n (n ≥ 2) points, the competitive ratio of the improved covering strategy S1 is

$$\alpha_{{{\text{S}}1}}\,=\,\left\{ {\begin{array}{*{20}l} {2,} \hfill & \quad {{\text{if }}k \ge n - 1} \hfill \\ {\frac{3 + \lambda }{2},} \hfill & \quad {{\text{if }}k \ge 2{\text{ and }}k\,=\,n - 2} \hfill \\ {1 + \lambda ,} \hfill & \quad {{\text{if }}1 \le k \le n - 3.} \hfill \\ \end{array} } \right.$$
(22)

4.2 Competitive ratio of strategy S2

Similarly, concerning the competitive ratio of strategy S2 for the problem P2, we have the following theorems.

Theorem 4

For the problem P2 with k taxis, if k ≥ n − 1, the strategy S2 is an online algorithm with competitive ratio 2, where n (n ≥ 2) indicates the number of points of graph G.

Proof

Following from the proof of Theorem 1, Theorem 4 can be similarly proved.□

Theorem 5

For the problem P2 with k taxis, if 1 ≤ k ≤ n − 4, the strategy S2 is an online algorithm with competitive ratio \(1{ + }\lambda\) , where n (n ≥ 2) indicates the number of points of graph G and \(\lambda \,=\,d_{ \hbox{max} } /d_{ \hbox{min} }\).

Proof

Following from the proof of Theorem 3, Theorem 5 can also be similarly proved.□

Theorem 6

For the problem P2 with k (k ≥ 3) taxis, if \(k{\,=\,}n - 2\) or \(k{\,=\,}n - 3\) , the strategy S2 is an online algorithm with competitive ratio (3 + λ)/2, where n (n ≥ 2) indicates the number of points of graph G and \(\lambda\,=\,d_{ \hbox{max} } /d_{ \hbox{min} }\).

Proof

Similarly to the proof of Theorem 2, we just need to prove that Lemmas 1 and 2 are also true for the strategy S2 when \(k{\,=\,}n - 2\) or \(k{\,=\,}n - 3\), and then Theorem 6 can be easily verified.

Now, we prove that for the problem P2 with k taxis, if k = n − 2 or \(k{\,=\,}n - 3\), at least one of the following inequalities concerning the cost of strategy S2 to serve the requests r i and \(r_{{i{ + }1}}\) holds,

$$C_{{{\text{S}}2}} (r_{i} ) + C_{{{\text{S}}2}} (r_{i + 1} ) \le 2d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} } ,$$
(23)

or

$$C_{{{\text{S}}2}} (r_{i} ) + C_{{{\text{S}}2}} (r_{i + 1} ) \le d(a_{i} ,b_{i} ) + 2d(a_{i + 1} ,b_{i + 1} ) + d_{\hbox{max} } .$$
(24)

Since the difference between strategies S2 and S1 only lies in the case (4), we just need to verify that the above proposition [namely, at least one of (23) or (24) is true] also holds in this case for \(k{\,=\,}n - 2\) or \(k{\,=\,}n - 3\).

What is more, if k = n − 2, case (4-ii) in the strategy S2 would never happen, since there are only two points that are not covered by a taxi in the whole game. Therefore, in the case (4-ii), we only should consider the situation that \(k{\,=\,}n - 3\).

For the case (4-i), the cost of serving r i and \(r_{{i{ + }1}}\) is

$$C_{{{\text{S}}2}} (r_{i} ) + C_{{{\text{S}}2}} (r_{i + 1} )\,=\,d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} ) .$$
(25)

Both (23) and (24) hold.

For the case (4-ii) and \(k{\,=\,}n - 3\), the cost of serving r i and \(r_{{i{ + }1}}\) is

$$C_{{{\text{S}}2}} (r_{i} ) + C_{{{\text{S}}2}} (r_{i + 1} )\,=\,d(c_{i} ,a_{i + 1} ) + d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} ) .$$
(26)

(23) and (24) also hold.

Figure 2 shows the moves and status of the related points in the case (4-ii) of strategy S2. The circle filled in black indicates that it is occupied by a taxi, while the empty circle denotes a point without a taxi. Since there are n − 3 taxis in total, all the other points not shown in Fig. 2 are occupied by a taxi.

Fig. 2
figure 2

Illustration of the moves for serving r i and \(r_{{i{ + }1}}\) by the strategy S2 in the case (4-ii)

Full size image

For the cases (4-iii) and (4-iv), the above proposition that at least one of (23) or (24) is true can be verified similarly to the proof of Lemma 1.

Consequently, we can get a similar result with Lemma 2 as follows. For the problem P2, if k = n − 2 or \(k{\,=\,}n - 3\), the following inequality concerning the cost of strategy S2 to serve the requests r i and \(r_{{i{ + }1}}\) holds,

$$C_{{{\text{S}}2}} (r_{i} ) + C_{{{\text{S}}2}} (r_{i + 1} ) \le \frac{3 + \lambda }{2}\left[ {d(a_{i} ,b_{i} ) + d(a_{i + 1} ,b_{i + 1} )} \right] .$$
(27)

Following from (27), Theorem 6 holds.□

In summary, for the problem P2 with k (k ≥ 1) taxis on a graph with n (n ≥ 2) points, the competitive ratio of the improved covering strategy S2 is

$$\alpha_{\text{PMS}}\,=\,\left\{ \begin{aligned} &2, \; \; \quad \qquad {\text{ if }}k\,=\,n{\text{ or }}n - 1 \hfill \\ &1 + \lambda , \qquad {\text{ if }}1 \le k \le n - 2. \hfill \\ \end{aligned} \right.$$
(28)

4.3 Improved competitive ratios

The performance of an online algorithm is measured by competitive ratio in the competitive analysis theory. In [13], a competitive algorithm, called position maintaining strategy (PMS), is proposed to handle the traditional online k-taxi problem by Xu et al. It is proved that the competitive ratio of PMS is

$$\alpha_{\text{PMS}}\,=\,\left\{ \begin{aligned} 2, \quad {\text{ if }}k\,=\,n{\text{ or }}n - 1 \hfill \\ 1 + \lambda , \qquad {\text{ if }}1 \le k \le n - 2. \hfill \\ \end{aligned} \right.$$
(29)

Comparing (29) with (22) and (28), it can be seen that with the foreknowledge, the competitive ratios of the strategies S1 and S2 are improved.

To quantify the value of foreknowledge in the form of improved competitive ratios with respect to the ratios of the traditional online k-taxi problem, we can show that the improvements for the case of \(\, k\,=\,n - 2\) in problem P1 (k ≥ 2) and the case of \(\, k\,=\,n - 2\) or n − 3 in problem P2 (k ≥ 3) are

$$1 + \lambda - \frac{3 + \lambda }{2}\,=\,\frac{\lambda - 1}{2} \ge 0 .$$
(30)

In other words, the competitive ratios are decreased from 1 + λ to (3 + λ)/2 for some special cases of the online k-taxi problem by introducing the new feature of foreknowledge into it. The improvements, i.e., the value of foreknowledge in the sense of competitive analysis, are (λ − 1)/2, where λ is the parameter determined by the metric space in which the problem is discussed.

Furthermore, it also can be seen that, in all cases, the improved covering strategies would never perform wore, in the sense of competitive analysis, than the classical PMS for the traditional online k-taxi problem.

5 Performances in practice

In the above section, the performances of the proposed improved covering strategies are analyzed in a theoretical way. In this section, we give some numerical examples to illustrate the proposed online algorithms as well as their performances in practice.

Now, consider the graph consisting of 12 points and 17 weighted edges as shown in Fig. 3, which can be seen as a realistic representation of a little town with 6 blocks. All the edge weights are randomly generated following a normal distribution with mean value of 100 and standard deviation of 10.

Fig. 3
figure 3

A graph for numerical examples

Full size image

For this graph, it is easy to get that d min = d(G, K) = 84.10 and d max = d(I, D) = 465.69, and thus λ = 5.54. Then the competitive ratios of the improved covering strategies and the PMS are compared in Table 1. It is also illustrated that the improved covering strategies S1 and S2 would never perform wore than the classical PMS based on theoretical analysis.

Table 1 Competitive ratios of the online algorithms
Full size table

Then, these online algorithms as well as their practical performances are illustrated on the graph shown in Fig. 3, on the basis of some randomly generated service requests. In order to compare the performance of different algorithms in an appropriate way, the precondition cost is not taken into account, and it is assumed that the online algorithms are launched with the same initial state. In other words, the taxi locations are preconditioned to be same.

In the following, we take a service request sequence R 1 = ((K, H), (E, G), (J, B), (K, J), (C, D), (A, F)) for instance, and assume that there are 10 taxis moving on the graph to supply service.

For the optimal offline algorithms, since it knows the sequence before making decision and the precondition cost is not taken into account, it is easy to see that these six requests can be served respectively by one particular taxi being dispatched to the start point of the request in advance. Therefore, the optimal offline cost is \(d\left( {{\text{K}},{\text{H}}} \right) + d\left( {{\text{E}},{\text{G}}} \right) + d\left( {{\text{J}},{\text{B}}} \right) + d\left( {{\text{K}},{\text{J}}} \right) + d\left( {{\text{C}},{\text{D}}} \right) + d\left( {{\text{A}},{\text{F}}} \right) = 1000.48\).

For the online algorithms, the initial locations of the taxis can be randomly selected such that these 10 taxis are respectively located at 10 different points and there is a taxi at the start point of the first request. For instance, supposing that the points B and J are not occupied by a taxi, the moves of the three online algorithms to complete these service requests are listed in Table 2. The costs of the PMS and strategies S1 and S2 are 1850.76, 1768.46, and 1658.85, respectively, and their ratios to the optimal offline cost are 1.85, 1.77 and 1.66, respectively.

Table 2 Moves and performances for serving the sequence R 1
Full size table

In this case, the reduction of the costs of S1 and S2, with regard to PMS which does not have any foreknowledge, are respectively 82.3 and 191.91. Meanwhile, as for the ratios of the online solutions to the optimal offline solution, the improvements of S1 and S2 are 0.08 and 0.19, respectively.

Similarly, more experiments can be made based on some randomly generated service requests. Table 3 illustrates the performances of these online algorithms for serving different request sequences on the graph shown in Fig. 3 with 10 taxis.

Table 3 Performances for serving different request sequences
Full size table

From Table 1, we know the competitive ratios of the online algorithms PMS, S1 and S2 for the online k-taxi problem with k = 10 are 6.54, 4.27 and 4.27, respectively. Comparing this conclusion with the results shown in Table 3, it can be seen that the practical performances of these online algorithms are much better than the theoretical competitive ratios. In other words, the ratios of the practical online solutions to the optimal offline solutions are much less than the competitive ratios derived by theoretical analysis.

It is easy to understand that these results are consistent with the conclusions previously given in the theoretical analysis, since the approach of competitive analysis is based on worst-case analysis, and consequently, the competitive ratio is actually a worst-case measure, which provides very robust statement about the performance of an online solution.

Moreover, it can also be seen that the proposed improved covering strategies perform better than the traditional PMS in some special cases, not only with regard to theoretical analysis, but also in practice.

6 Conclusions

In this paper, the online k-taxi problem was revisited by introducing a new feature into it, which empowers the online player to have foreknowledge. Two different scenarios concerning how partial information of future possible service requests is released in advanced were discussed, and improved covering strategies with lower competitive ratios, with respect to the traditional online k-taxi problem, were proposed to address them. The competitive ratios are improved due to the utilizing of foreknowledge. Therefore, the improvements are regarded as the value of foreknowledge in this online k-taxi problem within the framework of competitive analysis.

However, concerning the topic that how to effectively dispatch taxis in an online fashion as well as the impact of foreknowledge on the online solutions, although some preliminary results have been presented in this paper, there still are some important issues to be further studied, which will be considered in our future work. For example, firstly, how to design better algorithms for the problem in more general cases? Secondly, it is clear that the more foreknowledge gained, the better decisions may be made. Then how to measure the value of foreknowledge compared to the amount of information known in advance? For this purpose, the notion of entropy [25, 26] may be introduced into this problem. Furthermore, it would also be interesting to consider how to gain more foreknowledge to improve the decisions in the real applications (e.g. learning from big data of the customers’ behaviors [27]).