Keywords

1 Introduction

The single vehicle scheduling problem (SVSP) consists of a set of customers situated at different vertices on a given network and a single vehicle initially located at a fixed depot. Each customer has a release time before which it cannot be served, and a service time which the vehicle has to spend in serving the customer. The vehicle, required to serve all the customers, takes a travel time when it travels from one customer to another. The completion time of a customer is defined as the time by which it has been served completely, while the completion time of the vehicle means the time by which it has served all the customers and returned to its initial location. A permutation of the customers, which implies the customer service order and can specify the routing of the vehicle, is considered as a schedule for the problem. The problem aims to find a schedule to minimize the makespan. We distinguish two versions. In the first one, which is called tour-version, the makespan is defined as the completion time of the vehicle. In the other one, which is known as path-version, the makespan means the completion time of the last served customer. For convenience, when the network is restricted to a line (resp. tree, cycle), we denote the single vehicle scheduling problem by L-SVSP (resp. T-SVSP, C-SVSP). When the service time of each customer is zero, SVSP is known as single vehicle routing problem (SVRP) in some paper. Thus we denote SVRP on a line, tree and cycle by L-SVRP, T-SVRP and C-SVRP, respectively.

There are plenty of results on VRP and VSP. [1] showed that both the tour-version and the path version of L-SVSP are ordinarily NP-hard. [2] presented polynomial time algorithms for both versions of L-SVRP. [3] provided a \(\frac{3}{2}\)-approximation algorithm for the tour-version of L-SVSP in the case that the vehicle initial locates at an extreme vertex, and [4] gave a \(\frac{5}{3}\)-approximation algorithm for the counterpart in which the initial location of the vehicle is arbitrary. [5, 6] presented a \(\frac{3}{2}\)-approximation algorithm for the tour-version of L-SVSP and a \(\frac{5}{3}\)-approximation algorithm for the path-version of L-SVSP with no constraint on the initial location of the vehicle, and [6] also provided examples to show that the performance ratios are tight. When it comes to multi-vehicle scheduling problem (MVSP), [7] provided a 2-approximation algorithm for the path-version of the general L-MVSP in which the initial location of each vehicle is arbitrary. [8] showed that both the tour-version and path-version of L-MVRP can be solved in polynomial time.

It has been shown in [9] that both the tour-version and the path-version of T-SVRP (and hence T-SVSP) are ordinarily NP-hard. For the tour-version of T-SVSP, they showed that the problem can be exactly solved in \(O(n\log n)\) time if adding a constraint that the vehicle has to process all tasks in a depth-first manner, and the \(O(n\log n)\) time algorithm can be considered as a 2-approximation algorithm for the T-SVSP without the depth-first constraint. [10] ultimately proved that both versions of T-SVSP are strongly NP-hard. For the tour-version, they provided a \(O(n^b)\) time DP algorithm where b is the number of leaves. [5] introduced an improved \(\frac{11}{6}\)-approximation algorithm for the tour-version of T-SVSP. In their algorithm, they partitioned the set of customers into two subsets. The vehicle first serves part of customers in one subset, and then serves all the remaining customers. They also presented a \(\frac{9}{5}\)-approximation algorithm with a similar method for the tour-version of C-SVSP. [11] provided a \(\frac{9}{5}\)-approximation algorithm and a \(\frac{27}{14}\)-approximation algorithm for the tour-version and the path-version of T-SVSP, respectively. For both tour-version and path-version of C-SVSP, they provided a \(\frac{12}{7}\)-approximation algorithm. [12] presented polynomial time approximation schemes for both versions of SVSP on a tree with a constant number of leaves. [13] presented a 3-approximation algorithm for MVSP on a tree and a \((5-\frac{2}{m})\)-approximation algorithm for that on a general network.

In this paper, we consider both the tour-version and the path-version of T-SVSP and the tour-version of C-SVSP. For each problem, we propose an approximation algorithm and prove its performance ratio. Our algorithms are improvements on those in [11].

The rest of this paper is structured as follows. In Sect. 2, we introduce the formulation of T-SVSP and some notations. In Sect. 3, we present approximation algorithms for two versions of T-SVSP and analyse the performance ratio. In Sect. 4, we describe an approximation algorithm for the tour-version of C-VSP and prove the performance ratio. Finally we give some concluding remarks in Sect. 5.

2 Problem Formulation and Preliminaries

The SVSP discussed in this paper is mathematically defined as follows. Let \(G=(V\cup \{0\},E)\) be an undirected network where \(V=\{1,2,...,n\}\) is a vertex set and E is a set of edges. An edge \(e\in E\) is an unordered pair (j, k) of two vertices in V, where j, k are called the endpoints of e. The travel time of the vehicle is \(t_{j,k}\ge 0\), which is the time to traverse edge \(e=(j,k)\) from j to k, and \(t_{k,j}=t_{j,k}\). When \((j,k)\notin E\), \(t_{k,j}\) denotes the travel time for the vehicle travelling along the shortest path from j to k. There is a unique customer i at each vertex \(i\in V\). Unless ambiguity would result, we do not distinguish between vertex and customer. There is a vehicle initially located at the depot 0 to serve all the costumers. Each customer i is associated with a release time \(r_i\) and a service time \(p_i\). It means that the vehicle cannot start serving customer i before \(r_i\), and needs \(p_i\) time units to finish its service. The vehicle arriving at a vertex i before \(r_i\) either waits until \(r_i\) to serve the customer \(v_i\), or moves to other vertices without serving \(v_i\) if it is more advantageous (in this case, the vehicle has to come back to i later to serve customer i). A routing schedule of the vehicle is specified by a sequence \(\pi =(\pi (1),\pi (2),...,\pi (n))\) of customers to be served, i.e. the vehicle travels along a shortest path from 0 to \(\pi (1)\) in G, taking the travel time of the length of the path, waits until \(r_{\pi (1)}\) if the arrival time is before \(t=r_{\pi (1)}\) and serve the customer \(\pi (1)\). After serving \(\pi (1)\), it immediately moves to \(\pi (2)\), waits until \(r_{\pi (2)}\) if the arrival time is before \(t=r_{\pi (2)}\) and serve the customer \(\pi (2)\), and so on. In the following, for any feasible schedule \(\pi \), we always assume \(\pi (0)=\pi (n+1)=0\). Let \(C_{[i]}(\pi )\) denote the service completion time of customer \(\pi (i)\) in \(\pi \), and set \(C_{[0]}(\pi )=0\). Then, \(C_{[i]}(\pi )\) equals to \(\max \{r_{\pi (i)},C_{[i-1]}(\pi )+t_{\pi (i-1),\pi (i)}\}+p_{\pi (i)}\) for all \(i=1,2,...,n\). The makespan of \(\pi \) is donoted by \(C_{max}^{tour}(\pi )\) in the tour-version, and \(C_{max}^{path}(\pi )\) in the path-version. Then, \(C_{max}^{tour}(\pi )=C_{[n]}(\pi )+t_{0,\pi (n)}\), \(C_{max}^{path}(\pi )=C_{[n]}(\pi )\).

We now introduce some notations to be used throughout the article. Let

$$\begin{aligned} \begin{array}{rcl} t_{max}&{}=&{}max_{1\le i\le n}t_{0,i}\\ L&{}=&{}\sum \nolimits _{(i,j)\in E}t_{i,j}\\ r_{max}&{}=&{}max_{1\le i\le n}r_i\\ P&{}=&{}\sum \nolimits _{i=1}^np_i\\ \end{array} \end{aligned}$$
(1)

and for \(0\le t \le r_{max}\),

$$\begin{aligned} \begin{array}{rcl} V(t)&{}=&{}\{i\in V\mid r_i\ge t\}\\ P(t)&{}=&{}\sum \nolimits _{i\in V(t)}p_i\\ V'(t)&{}=&{}\{i\in V\mid r_i>t\}\\ P'(t)&{}=&{}\sum \nolimits _{i\in V'(t)}p_i \end{array} \end{aligned}$$
(2)

Note that P(t) and \(P'(t)\) are piecewise constant functions of t, and different only at \(r_j(j=1,2,...,n)\).

For \(0\le t\le r_{max}\), let v(t) and \(v'(t)\) denote the farthest vertices from vertex 0 in V(t) and \(V'(t)\), respectively. We also define

\(\theta \): the shortest travelling tour over \(V\cup \{0\}\)

\(\delta _0'(t)\): the shortest travelling path over \(V'(t)\cup \{0\}\) starting from the depot 0.

When \(G=(V\cup \{0\},E)\) is a tree, for any \(U\subset V\cup \{0\}\), we define the spanning subtree on U as the smallest subtree of G which contains all the vertices in U. Furthermore, for \(0\le t \le r_{max}\), we let T(t), \(T'(t)\), \(\widehat{T}(t)\) and \(\widehat{T}'(t)\) denote the spanning subtree on the vertex sets V(t), \(V'(t)\), \(V(t)\cup \{0\}\) and \(V'(t)\cup \{0\}\), respectively.

In the following, a symbol denoting a subgraph of G also be considered as its length, i.e. if \(G'\) is a subgraph of G, then \(G'=\sum _{(j,k)\in G'}t_{j,k}\).

3 SVSP on Tree Network

In this section we consider T-SVSP. Without loss of generality, we consider the depot 0 as the root of the tree. A \(\frac{16}{9}\)-approximation algorithm for the tour-version is presented in Sect. 3.1, and a \(\frac{48}{25}\)-approximation algorithm for the path-version is provided in Sect. 3.2.

3.1 Tour-Version of T-SVSP

Karuno et al. [3] provided a \(\frac{11}{6}\)-approximation algorithm for the tour-version of T-SVSP. They first gave several different candidate schedules and then chose the best one as the approximation solution. Yu and Liu [6] proved that the tour version of T-SVSP has an r-approximation algorithm if the tour version of T-SVRP has. Then they presented a \(\frac{9}{5}\)-approximation algorithm for the tour-version of T-SVRP. We will adopt a similar approach and show the approximation ratio can be reduced to \(\frac{16}{9}\).

figure a

In the proof of the following theorem, we first propose several upper bounds on the makespan of \(\pi _1\), \(\pi _2\) and \(\pi _3\), and then prove that Algorithm 1 is a \(\frac{16}{9}\)-approximation algorithm to the tour-version of T-SVSP. Let \(\pi ^*\) denote the optimal schedule for the tour-version of T-SVRP.

Theorem 1

Algorithm 1 is a \(\frac{16}{9}\)-approximation algorithm to the tour-version of T-SVRP.

Proof. The proof will be presented in three steps.

Step 1: We prove an upper bound on \(C_{max}^{tour}(\pi _1)\).

In \(\pi _1\), the vehicle either waits at some customers for their release or doesn’t wait at any vertex. If the vehicle waits at some customers, assume customer j is the last customer where the vehicle waits. Because the first served customer is v(0), the travel time of the vehicle before it arriving at j is at least \(t_{0,v(0)}+t_{v(0),j}\). The total travel time of the vehicle in \(\pi _1\) is 2L. Then, the travel time of the vehicle after it serves customer j is no more than \(2L-t_{0,v(0)}-t_{v(0),j}\). Thus,

$$\begin{aligned} \begin{array}{rcl} C_{max}^{tour}(\pi _1)&{}\le &{} r_j+2L-t_{0,v(0)}-t_{v(0),j}\\ &{}=&{} r_j+t_{0,j}+2L-t_{0,v(0)}-t_{v(0),j}-t_{0,j}\\ &{}\le &{} 2C_{max}^{tour}(\pi ^*)-2t_{max} \end{array} \end{aligned}$$
(3)

where the last equality follows \(r_j+t_{0,j}\le C_{max}^{tour}(\pi ^*)\), \(2L\le C_{max}^{tour}(\pi ^*)\) and \(t_{max}=t_{0,v(0)}\le t_{v(0),j}+t_{0,j}\).

If the vehicle doesn’t wait at any vertex, then

$$\begin{aligned} \begin{array}{rcl} C_{max}^{tour}(\pi _1)&{}=&{}2L\\ &{}=&{}C_{max}^{tour}(\pi ^*)\\ &{}\le &{} 2C_{max}^{tour}(\pi ^*)-2t_{max} \end{array} \end{aligned}$$
(4)

Combing the above two cases, we conclude that

$$\begin{aligned} C_{max}^{tour}(\pi _1)\le 2C_{max}^{tour}(\pi ^*)-2t_{max}. \end{aligned}$$
(5)

Step 2: We show an upper bound on \(min\{C_{max}^{tour}(\pi _2),C_{max}^{tour}(\pi _3)\}\).

We first consider the total waiting time of the vehicle in \(\pi _2\) and \(\pi _3\). In both \(\pi _2\) and \(\pi _3\), the time of the vehicle arriving at point x is \(t^*\). Since \(t^*\ge r_{max}\), the vehicle does not wait at any customer in the later process. Thus, the total waiting time of the vehicle in \(\pi _2\) is \(t^*-L-\frac{t_{max}}{2}\), and that in \(\pi _3\) is \(t^*-L+\frac{t_{max}}{2}\). The total waiting time of the vehicle in \(\pi _2\) and \(\pi _3\) is \(2t^*-2L\).

Now we turns to provide an upper bound of the total travel time of the vehicle in \(\pi _2\) and \(\pi _3\). Let \(T_1\) and \(T_2\) be subtrees visited in \(\pi _2\) and \(\pi _3\), respectively. It is easy to see that the travel times of the vehicle in \(\pi _2\) and \(\pi _3\) are no more than \(2L+2((T_1\backslash T_2)\cap \widehat{T}'(t^*-L+\frac{t_{max}}{2}))\) and \(2L+2((T_2\backslash T_1)\cap \widehat{T}'(t^*-L+\frac{t_{max}}{2}))\), respectively. Since \(2((T_1\backslash T_2)\cap \widehat{T}'(t^*-L+\frac{t_{max}}{2}))+2((T_2\backslash T_1)\cap \widehat{T}'(t^*-L+\frac{t_{max}}{2}))\le 2\widehat{T}'(t^*-L+\frac{t_{max}}{2})\), the total travel time of the vehicle in \(\pi _2\) and \(\pi _3\) is at most \(4L+2\widehat{T}'(t^*-L+\frac{t_{max}}{2})\), which is no more than \(4L+2\widehat{T}'(L+\frac{t_{max}}{2})\) for \(t^*-L\ge L\).

Combing the above two discussion,

$$\begin{aligned} \begin{array}{rcl} C_{max}^{tour}(\pi _2)+C_{max}^{tour}(\pi _3)&{}\le &{} 2t^*-2L+4L+2\widehat{T}'(L+\frac{t_{max}}{2})\\ &{}=&{}2t^*+2L+2\widehat{T}'(L+\frac{t_{max}}{2}) \end{array} \end{aligned}$$
(6)

A straightforward conclusion of the inequality above is showed as follows.

$$\begin{aligned} \begin{array}{rcl} &{} &{}\min \{C_{max}^{tour}(\pi _2),C_{max}^{tour}(\pi _3)\}\\ &{}\le &{} \frac{1}{2}(C_{max}^{tour}(\pi _2)+C_{max}^{tour}(\pi _3))\\ &{}\le &{} t^*+L+\widehat{T}'(L+\frac{t_{max}}{2})\\ &{}\le &{} t^*+L+(C_{max}^{tour}(\pi ^*)-L-\frac{t_{max}}{2}+t_{0,v(L+\frac{t_{max}}{2})})/2\\ &{}\le &{} \frac{7}{4}C_{max}^{tour}(\pi ^*)+\frac{t_{max}}{4} \end{array} \end{aligned}$$
(7)

where the second inequality follows \(C_{max}^{tour}(\pi ^*)\ge t+2\widehat{T}(t)-t_{0,v(t)}\) and \(\widehat{T}'(t)\le \widehat{T}(t)\), the last inequality follows \(t_{0,v(L+\frac{t_{max}}{2})}\le t_{max}\) and \(C_{max}^{tour}(\pi ^*)\ge t^*\ge 2L\).

Step 3: We prove the correctness of Theorem 1.

Combining the conclusion of the above two steps,

$$\begin{aligned} \begin{array}{rcl} &{} &{}\min \{C_{max}^{tour}(\pi _1),C_{max}^{tour}(\pi _2),C_{max}^{tour}(\pi _3)\}\\ &{}\le &{} \min \{2C_{max}^{tour}(\pi ^*)-2t_{max},\frac{7}{4}C_{max}^{tour}(\pi ^*)+\frac{t_{max}}{4}\}\\ &{}\le &{} \frac{16}{9}C_{max}^{tour}(\pi ^*) \end{array} \end{aligned}$$
(8)

This completes the proof of Theorem 1.    \(\square \)

[11] showed that, in linear time, each instance \(\mathcal {I}\) of the tour-version of T-SVSP can be transformed into an instance \(\mathcal {I'}\) of the tour-version of T-SVRP such that any r-approximation schedule \(\pi '\) of \(\mathcal {I'}\) also can be transformed into an r-approximation schedule of \(\mathcal {I}\). Therefore, we design the following \(\frac{16}{9}\)-approximation algorithm for the tour-version of T-SVSP.

figure b

Theorem 2

Algorithm 2 is a \(\frac{16}{9}\)-approximation algorithm to the tour-version of T-SVSP.

Proof. Theorem 2 is a direct inference of Theorem 1.    \(\square \)

3.2 Path-Version of T-SVSP

When it comes to the path-version of T-SVSP, notice that the gap between the makespan of a schedule for the tour-version of T-SVSP and that of the same schedule for the path-version of T-VSP is no more than \(t_{max}\). Therefore, the approximation algorithm for the tour-version of T-VSP can also be used to solve the path-version of T-SVSP.

figure c

In the proof of the following theorem, we first propose several upper bounds on the makespan of \(\pi _1\) and \(\pi _2\), and then prove that Algorithm 3 is a \(\frac{48}{25}\)-approximation algorithm to the path-version of T-SVSP. Let \(\pi '\) and \(\pi ^*\) denote the optimal schedule for the tour-version of T-SVSP and the path-version of T-SVSP, respectively.

Theorem 3

Algorithm 3 is a \(\frac{48}{25}\)-approximation algorithm to the path-version of T-SVSP.

Proof. The proof will be presented in three steps.

Step 1. We prove an upper bound on \(C_{max}^{path}(\pi _1)\).

Let j denote the last customer served by the vehicle in \(\pi ^*\). It is easy to see that \(C_{max}^{tour}(\pi ^*)-C_{max}^{path}(\pi ^*)\le t_{0,j}\), and \(t_{0,j}\le t_{max}\). Then, we obtain \(C_{max}^{tour}(\pi ^*)\le C_{max}^{path}(\pi ^*)+t_{max}\). Thus,

$$\begin{aligned} \begin{array}{rcl} C_{max}^{path}(\pi _1)&{}\le &{} C_{max}^{tour}(\pi _1)\le \frac{16}{9}C_{max}^{tour}(\pi ')\\ &{}\le &{} \frac{16}{9}C_{max}^{tour}(\pi ^*)\\ &{}\le &{} \frac{16}{9}C_{max}^{path}(\pi ^*)+\frac{16}{9}t_{max} \end{array} \end{aligned}$$
(9)

Step 2. We show an upper bound on \(C_{max}^{path}(\pi _2)\).

It is easy to see that the optimal makespan of the auxiliary L-SVRP is a lower bound of \(C_{max}^{path}(\pi ^*)\). Compared with the optimal makespan of L-SVRP, the makespan of \(\pi _2\) increases at most \(2(L-t_{max})+P\) time units for travelling the subtrees \(T^0,T^1,...,T^{m+1}\) and serving all the customers. Then, we obtain

$$\begin{aligned} \begin{array}{rcl} C_{max}^{path}(\pi _2)&{}\le &{} C_{max}^{path}(\pi ^*)+2(L-t_{max})+P\\ &{}\le &{} 2C_{max}^{path}(\pi ^*)-t_{max} \end{array} \end{aligned}$$
(10)

Step 3. We prove the correctness of Theorem 3.

$$\begin{aligned} \begin{array}{rcl} &{} &{}\min \{C_{max}^{path}(\pi _1),C_{max}^{path}(\pi _2)\}\\ &{}\le &{}\min \{\frac{16}{9}C_{max}^{path}(\pi ^*)+\frac{16}{9}t_{max},2C_{max}^{path}(\pi ^*)-t_{max}\}\\ &{}\le &{} \frac{48}{25}C_{max}^{path}(\pi ^*) \end{array} \end{aligned}$$
(11)

This completes the proof of Theorem 3.    \(\square \)

4 SVSP on Cycle Network

We now turn to the tour version of C-SVSP. Let \(G=(V\cup \{0\}\)) be a cycle, where the vertices in \(V\cup \{0\}\) are numbered increasingly in the counterclockwise order. In the following of this section, we consider vertex \(n+1\) as vertex 0.

Recall the definitions of \(L,\theta ,\delta _0'(t)\) in Sect. 2. We assume that there is no edge \((i,i+1)\) such that \(t_{i,i+1}\ge \frac{1}{2}L\). Otherwise there exists an optimal schedule which never goes through the edge \((i,i+1)\), thus the tour-version of C-SVSP can be considered as a tour-version of L-SVSP. Since [6] showed a \(\frac{3}{2}\)-approximation algorithm for the tour-version of L-SVSP, we focus on the situation satisfying \(t_{i,i+1}<\frac{1}{2}L\) for all \(i=0,1,...,n\), which implies \(\theta =L\). Suppose that \(V'(t)=\{i_1,i_2,...,i_k\}\) with \(i_1<i_2<...<i_k\), and \(i_0=i_{k+1}=0\). Then \(\delta _0'(t)\) is the shortest one among the following paths:

  1. (i)

    for \(0\le j\le k-1\), the paths first from \(i_0\) to \(i_j\) in the counterclockwise direction, and then from \(i_j\) to \(i_{j+1}\) in the clockwise direction;

  2. (ii)

    for \(2\le j\le k+1\), the paths first from \(i_0\) to \(i_j\) in the clockwise direction, and then from \(i_j\) to \(i_{j-1}\) in the counterclockwise direction.

Then, we provide a \(\frac{5}{3}\)-approximation algorithm for the tour-version of C-SVSP as follows.

figure d

In the proof of the following theorem, we first propose several upper bounds on the makespan of \(\pi _1\) and \(\pi _2\), and then prove that Algorithm 4 is a \(\frac{5}{3}\)-approximation algorithm to the tour-version of T-SVSP. Let \(\pi ^*\) denote the optimal schedule for the tour-version of C-SVSP.

Theorem 4

Algorithm 4 is an \(\frac{5}{3}\)-approximation algorithm to the tour-version of C-SVSP.

Proof. The proof will be presented in three steps.

Step 1. We show that \(C_{max}^{tour}(\pi _1)\le C_{max}^{tour}(\pi ^*)+P\).

The optimal makespan of the C-SVRP is a lower bound of \(C_{max}^{tour}(\pi ^*)\). As a solution to C-SVSP, \(\pi _1\) increases at most P time units in makespan than as an optimal solution to C-SVRP. Then, \(C_{max}^{tour}(\pi _1)\le C_{max}^{tour}(\pi ^*)+P\).

Step 2. We prove that \(C_{max}^{tour}(\pi _2)\le max\{\frac{7}{3}C_{max}^{tour}(\pi ^*)-P, \frac{5}{2}C_{max}^{tour}(\pi ^*)-\frac{3}{2}P, \frac{5}{3}C_{max}^{tour}(\pi ^*)\}.\)

The vehicle does not wait at any customer in \(V\backslash V'(t^*)\), because it starts out from vertex \(v_{\delta _0'(t^*)}\) at or later than time \(t^*\). If the vehicle does not wait at any customer in \(V'(t^*)\), we have

$$\begin{aligned} \begin{array}{rcl} C_{max}^{tour}(\pi _2)&{}\le &{} max\{t^*,t_{0,v_{\delta _0'(t^*)}}\}+\theta +\delta _0'(t^*)+P\\ &{}\le &{} max\{\frac{1}{3}C_{max}^{tour}(\pi ^*),\frac{1}{2}\theta \}+2\theta +P\\ &{}\le &{} max\{\frac{7}{3}C_{max}^{tour}(\pi ^*)-P,\frac{5}{2}C_{max}^{tour}(\pi ^*)-\frac{3}{2}P\} \end{array} \end{aligned}$$
(12)

where the second inequality follows from \(C_{max}^{tour}(\pi ^*)\ge t^*+\delta _0(t^*)+P(t^*) \ge 3t^*\), \(t_{0,v'(t^*)}\le \frac{1}{2}\theta \) and \(\delta _0'(t^*) \le \theta \), and the last inequality follows from \(C_{max}^{tour}(\pi ^*)\ge \theta +P\).

If the vehicle waits at some customer in \(V'(t^*)\), let k be the last customer where the vehicle waits. Then we have

$$\begin{aligned} \begin{array}{rcl} C_{max}^{tour}(\pi _2)&{}\le &{} r_k+P'(t^*)+\delta _0'(t^*)\\ &{}\le &{} \frac{5}{3}C_{max}^{tour}(\pi ^*) \end{array} \end{aligned}$$
(13)

where the last inequality follows from \(C_{max}^{tour}(\pi ^*)\ge r_i+t_{0,i},\) \(\,for\,\,any\,\,i\in V\) and \(C_{max}^{tour}(\pi ^*)\ge t^*+\delta _0(t^*)+P(t^*) \ge \frac{3}{2}(\delta _0'(t^*)+P'(t^*)).\)

Step 3. We prove the minimum one between the makespans of \(\pi _1\) and \(\pi _2\) is at most \(\frac{5}{3}C_{max}^{tour}(\pi ^*)\).

$$\begin{aligned} \begin{array}{rcl} &{} &{}\min \{C_{max}^{tour}(\pi _1),C_{max}^{tour}(\pi _2)\}\\ &{}\le &{} \min \{C_{max}^{tour}(\pi ^*)+P,max\{\frac{7}{3}C_{max}^{tour}(\pi ^*)-P, \frac{5}{2}C_{max}^{tour}(\pi ^*)-\frac{3}{2}P, \frac{5}{3}C_{max}^{tour}(\pi ^*)\}\}\\ &{}=&{}\frac{5}{3}C_{max}^{tour}(\pi ^*) \end{array} \end{aligned}$$
(14)

This completes the proof.    \(\square \)

5 Conclusions

In this paper, we consider the single-vehicle scheduling problems on a tree and a cycle, and all of these problems are known to be NP-hard. For the tour-version and the path-version of T-SVSP, we present a \(\frac{16}{9}\)-approximation algorithm and a \(\frac{48}{25}\)-approximation algorithm, respectively. We also consider the tour-version of single-vehicle scheduling problem on a cycle, and give a \(\frac{5}{3}\)-approximation algorithm. Our algorithms improve the previous best results in the literature. The main idea used in the improved algorithms is to utilize the structure characteristics of tree and cycle to antedate the department time of the vehicle.

There are some issues that are still unsolved. We would like to know whether the approximation bounds obtained in this paper are tight. As a natural extension of this paper, researchers may study SVSP on a general network. If the general network satisfies the triangle inequality, it is straightforward to design a \(\frac{5}{2}\)-approximation algorithm. A better approximation bound is desirable.