The energy-constrained quickest path problem

Abstract

This paper addresses a variant of the quickest path problem in which each arc has an additional parameter associated to it representing the energy consumed during the transmission along the arc while each node is endowed with a limited power to transmit messages. The aim of the energy-constrained quickest path problem is to obtain a quickest path whose nodes are able to support the transmission of a message of a known size. After introducing the problem and proving the main theoretical results, a polynomial algorithm is proposed to solve the problem based on computing shortest paths in a sequence of subnetworks of the original network. In the second part of the paper, the bi-objective variant of this problem is considered in which the objectives are the transmission time and the total energy used. An exact algorithm is proposed to find a complete set of efficient paths. The computational experiments carried out show the performance of both algorithms.

1 Introduction

The quickest path problem (QPP) is a path problem in a directed network which aims to minimize the time taken to transmit a given amount of data. The transmission time depends on two parameters, an additive function which represents the traversal time or the delay along the path and a bottleneck function which represents the path capacity.

Let $\mathcal {G = [N, A]}$ be a directed network without multiple arcs and self loops, where ${\mathcal N}$ denotes the set of nodes and ${\mathcal A}$ the set of directed arcs. Let n be the number of nodes and m the number of arcs. Let s and t be two distinguished nodes in the network called, respectively, origin and destination and $\sigma$ the data units to be sent from node s to node t. Each arc $(u,v)\in \mathcal A$ is endowed with a capacity $c(u,v)> 0$ and a delay time $l(u,v)> 0$. The capacity represents the amount of data that can be sent through arc (u, v) per time unit. The delay time is the time required for the data units to traverse the arc (u, v).

Let us assume that a message is transmitted as a continuous stream along the arc (u, v) at a constant flow rate $\rho \leqslant c(u,v)$. At this flow rate, a message of $\sigma$ data units is sent from node u to node v through arc (u, v) in $l(u,v) + \frac{\sigma }{\rho }$ time. This expression takes its minimum value when $\rho = c(u,v)$. Thus, the minimum required transmission time is $l(u,v) + \frac{\sigma }{c(u,v)}$.

A simple path or loopless path P from node s to node t is a sequence of nodes and arcs $P=(s= u_1, u_2, \ldots , u_k=t)$ such that $u_i\in {\mathcal N}$, $i= 1,\ldots , k$, $u_i\not = u_j$ if $i\not = j$, and $(u_i, u_{i+1})\in {\mathcal A}$, $i = 1, \ldots , k-1$. In the paper, we use the term path in place of simple or loopless path for short as well as the term $s-t$ path in place of a path from s to t. We assume that the set of $s-t$ paths in the network ${\mathcal G}$ is nonempty.

The delay experienced by a message sent via path P depends on the message forwarding mechanism used at the intermediate nodes [18]. If $\sigma$ data units are sent at a constant rate from s to t along the $s-t$ path P with no buffering at intermediate nodes (circuit switching mode), the minimum transmission time or end-to-end delay of path P is

$$\begin{aligned} T_\sigma (P)=l(P)+ \frac{\sigma }{c(P)} \end{aligned}$$

(1)

where $l(P) =\sum \nolimits _{i=1}^{k-1} l(u_i,u_{i+1})$ denotes the delay time of path P and $c(P)=\min _{i=1, \ldots , k-1}c(u_i,u_{i+1})$ denotes its capacity.

Hence, the QPP can be formulated as finding an $s-t$ path so that:

$$\begin{aligned} \begin{array}{ll} \min \limits _{P}&{}T_\sigma (P)\\ \mathrm {s.t.}&{}P \, \mathrm {is \,an}\, s-t \,\mathrm{path\,in\,the\,network} \, \mathcal G \end{array} \end{aligned}$$

(2)

A characteristic of the QPP is that, in general, the size of the message has a strong influence on the optimal path. When $\sigma$ is small with respect to the arc capacities, the transmission time is controlled by the arc delays and a shortest path with respect to the arc delay could be a good solution to the problem. However, when $\sigma$ is very large, the transmission time is controlled by the arc capacities and the problem could be approached by computing the shortest path with respect to the arc delay among all paths with the largest capacity. It is also worth mentioning that the QPP does not satisfy the property known as ‘the optimality principle’, i.e. an $s^\prime -t^\prime$ subpath of an optimal $s-t$ path is not necessarily an $s^\prime -t^\prime$ optimal path.

The QPP was first proposed by Moore [11] to model flows of convoy-type traffic. Then it was proposed by Chen and Chin [5] in the context of modeling transmission problems in communication networks where nodes represent transmitters/receivers without data memories and arcs represent communication channels. Clímaco et al. [6] applied the model to the routing of data packets in Internet networks. Hamacher and Tijandra [8] proposed the QPP for a special evacuation problem where evacuees may use only a single path or tunnel from their initial position. Martins and Santos [10] and Pelegrín and Fernández [16] approached the QPP as a special minsum-maxmin bi-objective path problem. They proved that any optimal solution of the QPP is a nondominated solution of the bi-objective problem in which the delay time is minimized and the capacity of the path is maximized. Hence, a quickest path can be obtained by solving this bi-objective problem and selecting a nondominated path with the minimum transmission time.

Several polynomial time algorithms have been proposed in the literature, all with the same time complexity. They are based on solving a shortest path problem in an enlarged network [2, 5], solving a sequence of shortest path problems with respect to the delay time on networks where the minimum capacity increases [10, 11, 16, 19], using a label-setting algorithm [12] or taking into account that a quickest path is a supported efficient solution of the aforementioned bi-objective problem [20].

Several variants and extensions of the QPP have been addressed in the literature. The problem of finding the first K quickest paths in nondecreasing order of transmission time has been analyzed in [4, 6, 13, 15, 19]. The QPP constrained to contain a given subpath has been studied in [3, 19]. The problem of determining the transmission process when data are transmitted in batches of variable size but with required limits has been considered in [1]. The problem of computing the quickest path whose reliability is not lower than a given threshold has been analyzed in [2]. Pascoal et al. [14] provide a survey on the subject.

When formulating the QPP, no attention is paid to the characteristics of the transmitters/receivers represented by the nodes. It is implicitly assumed that they have unlimited energy available for transmitting messages. Usually, this can be the case in wired networks. However, for mixed networks which combine wired and radio link connections, some of the nodes can have limited power to transmit messages. This available power must be taken into account when computing the QPP since the energy consumed at node u during the transmission of the message along the arc (u, v) depends on the units of time during which node u is active, i.e. while it is sending data. Hence, it depends on the rate at which data are transmitted. In this paper, we introduce the energy-constrained quickest path problem (EQPP) which aims to obtain a quickest path whose nodes are able to support the transmission of $\sigma$ data units. We formulate the problem and develop a polynomial time algorithm to solve it based on computing shortest paths with respect to the delay time in a sequence of subnetworks of the original network. Although it is a constrained QPP, the time complexity of the algorithm is the same as that of any of the algorithms developed for solving the QPP. In the second part of the paper we address the minsum–minsum bi-objective variant of this problem (BEQPP) in which the total transmission time and the total consumed energy are minimized. We approach this NP-hard problem by determining a complete set of efficient paths and develop an exact algorithm based on solving bi-objective shortest path problems. The paper is structured as follows. Sections 2 and 3 formally set out the EQPP and prove the main theoretical results which support the algorithm developed for solving it. Section 4 goes on to develop a polynomial algorithm to solve the EQPP and shows its computational complexity. In Sect. 5 the bi-objective EQPP is formulated as well as its properties are proved and the algorithm is developed to find a complete set of efficient paths. Section 6 displays the results of the computational experiment carried out to assess the performance of the proposed algorithms. Finally, our conclusions are presented in Sect. 7.

2 The energy-constrained quickest path problem

Let $\mathcal {G = [N, A]}$ be the directed network introduced in Sect. 1. In order to formulate the EQPP, we assume that each arc $(u,v)\in \mathcal A$ is endowed with an energy rate $\omega (u,v)>0$ which measures the energy required at node u to transmit data units along the arc (u, v) per time unit. This energy typically depends on the characteristics of the arc (delay time and capacity).

Each node $u\in \mathcal N$ is endowed with a power $b_u$ which represents the limited energy available for transmission at node u. If $\sigma$ data units are transmitted as a continuous stream from node u to node v along the arc (u, v) at a constant flow rate $\rho$, then the node u is active, i.e. sending data, during $\frac{\sigma }{\rho }$ time units. Hence the required energy at node u is $\omega (u,v) \ \frac{\sigma }{\rho }$. Without loss of generality, we assume that

$$\begin{aligned} \omega (u,v) \frac{\sigma }{c(u,v)} \leqslant b_u, \forall (u,v)\in \mathcal A \end{aligned}$$

(3)

If the arc (u, v) does not hold this condition it cannot support the transmission of the $\sigma$ data units and so can be removed.

Taking into account the message forwarding mechanism, $\sigma$ data units are sent along the $s-t$ path P at a constant rate c(P). Therefore, the total energy required to transmit $\sigma$ data units using the path P is:

$$\begin{aligned} E_\sigma (P)= \sum _{i=1}^{k-1} \omega (u_i,u_{i+1}) \ \frac{\sigma }{c(P)} \end{aligned}$$

(4)

Let us denote $W(P)=\sum \nolimits _{i=1}^{k-1} \omega (u_i, u_{i+1})$.

The residual energy $b_u(\sigma , P)$ at node u after transmitting $\sigma$ data units through the path P is

$$\begin{aligned} b_u(\sigma , P) = \left\{ \begin{array}{l@{\quad }l} b_u - \omega (u_i,u_{i+1}) \frac{\sigma }{c(P)}\quad &{}\mathrm {if}\, u= u_i, i=1,\ldots ,k-1\\ b_u\quad &{}\mathrm {otherwise} \end{array} \right. \end{aligned}$$

In order for P to be an $s-t$ feasible path, $b_u(\sigma , P)\geqslant 0$, $\forall u\in P$. That is to say, the feasibility of a path P is measured through the availability of its nodes to transmit the whole data units at a rate c(P). Hence, the energy-constrained quickest path problem (EQPP) can be formulated as finding an $s-t$ path so that:

$$\begin{aligned} \begin{array}{ll} \min \limits _{P}&{}T_\sigma (P)\\ \mathrm {s.t.}&{}b_u(\sigma , P) \geqslant 0, u\in \mathcal N\\ &{}P \, \mathrm {is \, an}\, s-t \, \mathrm{path\,in\,the\,network}\, \mathcal G \end{array} \end{aligned}$$

(5)

The special characteristics of the side constraint on the residual energy allow us to develop an algorithm which is based on successively solving shortest path problems in subnetworks of the original network $\mathcal G$ which guarantee the feasibility of the path with respect to the energy availability at the nodes.

3 Main theoretical results

In what follows, we assume without loss of generality that there are r different capacities $c_1< c_2< \cdots < c_r$ in the network $\mathcal G$. Let us assign to each arc $(u,v)\in \mathcal A$ the label

$$\begin{aligned} c^{\min }(u,v)=\min \limits _{i=1,\ldots ,r}\left\{ c_i : b_u- \omega (u,v)\ \frac{\sigma }{c_{i}}\geqslant 0\right\} \end{aligned}$$

This label provides the minimum capacity at which the node u is able to support the transmission of the $\sigma$ data units along the arc (u, v). Therefore, it gives an idea of the feasible paths in which this arc can be included. Note that (u, v) can be an arc of an $s-t$ feasible path P only if $c(P)\geqslant c^{\min }(u,v)$.

We define $\mathcal G_j = [\mathcal N, \mathcal A_j]$, $j=1, \ldots , r$, to be a subnetwork of $\mathcal G$ where $(u,v)\in \mathcal A_j$ if and only if $(u,v)\in \mathcal A$, $c(u,v)\geqslant c_j$ and $c^{\min }(u,v) \leqslant c_j$.

It is worth mentioning that, in general, the network $\mathcal G_{j+1}$ is not a subnetwork of $\mathcal G_j$ and so the number of arcs in the successive networks does not necessarily decrease. For illustration, Fig. 1 displays a network $\mathcal G$ with the capacities 1, 2, 3 and 4, and the associated networks $\mathcal G_j$.

Fig. 1

Networks $\mathcal G$ and $\mathcal G_j$, $j=1, \ldots , 4$

Lemma 1

Let $P=(s= u_1, u_2, \ldots , u_k=t)$ be an $s-t$ path in the network $\mathcal G_j$. Then, P is an $s-t$ feasible path for the EQPP.

Proof

If P is an $s-t$ path in the network $\mathcal G_j$, then $c(P)\geqslant c_j \geqslant c^{\min }(u_i,u_{i+1})$, $i=1,\ldots ,k-1$. Hence

$$\begin{aligned} b_{u_i}(\sigma , P) = b_{u_i} - \omega (u_i,u_{i+1}) \frac{\sigma }{c(P)} \geqslant b_{u_i} - \omega (u_i,u_{i+1}) \frac{\sigma }{c^{\min }(u_i,u_{i+1})} \geqslant 0 \end{aligned}$$

For the remaining nodes u of the network, $b_u$ is not modified when the $\sigma$ data units are transmitted. Therefore, $b_u(\sigma , P) \geqslant 0$ $\forall u\in \mathcal N$ and the result follows. $\square$

Lemma 2

Let $P=(s= u_1, u_2, \ldots , u_k=t)$ be an $s-t$ feasible path for the EQPP with capacity $c(P)=c_j$. Then, P is an $s-t$ path in the network $\mathcal G_j$.

Proof

Since P is feasible

$$\begin{aligned} b_{u_i}(\sigma , P) = b_{u_i} - \omega (u_i,u_{i+1}) \frac{\sigma }{c(P)} \geqslant 0, i=1, \ldots , k-1 \end{aligned}$$

Hence, $c^{\min }(u_i,u_{i+1}) \leqslant c(P) = c_j \leqslant c(u_i,u_{i+1})$, $i=1, \ldots , k-1$. Taking into account the definition of the network $\mathcal G_j$, we conclude that the arc $(u_i,u_{i+1})$, $i=1, \ldots , k-1$, is in $\mathcal A_j$, and so P is an $s-t$ path in $\mathcal G_j$. $\square$

It is worth pointing out that an $s-t$ feasible path P for the EQPP with capacity $c(P) > c_j$ is not necessarily an $s-t$ path in the network $\mathcal G_j$. For instance, in the example displayed in Fig. 1, the capacity of the path $1-3-4-6$ is equal to 3. However, this path is neither in network $\mathcal G_1$ nor in network $\mathcal G_2$. In other words, the network $\mathcal G_j$ contains the paths $P=(s= u_1, u_2, \ldots , u_k=t)$ of $\mathcal G$ which are feasible for the EQPP with capacity greater than or equal to $c_j$, for which

$$\begin{aligned} b_{u_i}(\sigma , P) = b_{u_i} - \omega (u_i,u_{i+1}) \frac{\sigma }{c_j} \geqslant 0, i=1, \ldots , k-1 \end{aligned}$$

i.e., whose nodes are able to support the transmission with capacity $c_j$. In particular, the network $\mathcal G_j$ contains all the $s-t$ feasible paths for the EQPP with capacity $c_j$. Hence, if there is no $s-t$ path in the network $\mathcal G_j$, then there will not be an optimal solution of the EQPP with capacity $c_j$.

Let us consider the following SPP with respect to the delay time in $\mathcal G_j$:

(6)

Lemma 3

Let P be an optimal solution of the $\mathrm {SPP}_j$ and $c(P)=c_h>c_j$. Then, there is no optimal solution of the EQPP with capacity $c_j$.

Proof

Let Q be an $s-t$ feasible path for the EQPP with capacity $c_j$. Then Q is a path in $\mathcal G_j$ and

$$\begin{aligned} T_\sigma (P)=l(P)+ \frac{\sigma }{c_h} < l(Q)+ \frac{\sigma }{c_j} = T_\sigma (Q) \end{aligned}$$

Thus, Q cannot be an optimal solution of the EQPP. $\square$

Next we prove that any optimal solution to the EQPP can be obtained as a shortest path with respect to the delay time.

Theorem 1

Let $P^*$ be an optimal solution of the EQPP and $c(P^*) = c_h$. Then, $P^*$ is an optimal solution of the $\mathrm {SPP}_h$ and any optimal solution of the $\mathrm {SPP}_h$ is an optimal solution of the EQPP.

Proof

Since $P^*$ is an $s-t$ feasible path for the EQPP with capacity $c_h$, then $P^*$ is an $s-t$ path in $\mathcal G_h$. Let Q be an $s-t$ path in the network $\mathcal G_h$. Thus, $c(Q)\geqslant c_h$. If $l(Q) < l(P^*)$, then

$$\begin{aligned} T_\sigma (Q)= l(Q)+ \frac{\sigma }{c(Q)} < l(P^*)+ \frac{\sigma }{c_h} = T_\sigma (P^*) \end{aligned}$$

which contradicts the optimality of $P^*$. Furthermore, by applying Lemma 3, the capacity of any $s-t$ shortest path $\widetilde{P}$ in $\mathcal G_h$ is $c(\widetilde{P}) = c_h$. Hence, $\widetilde{P}$ is an $s-t$ feasible path for the EQPP such that $T(\widetilde{P}) = T(P^*)$ and so is an optimal solution of the EQPP. $\square$

4 EQPA: an algorithm for solving the EQPP

As a consequence of Theorem 1, the optimal solutions of the EQPP can be obtained by computing shortest paths with respect to the delay time in the networks $\mathcal G_j$ and determining those which have minimum transmission time.

It is worth at this point emphasizing the important differences existing between the networks $\mathcal F_j$, $j=1,\ldots ,r$ constructed by the algorithms proposed in [10, 11, 16, 19] to solve the QPP and the networks $\mathcal G_j$, $j=1,\ldots ,r$.

The network $\mathcal F_j = [\mathcal N, \tilde{\mathcal A_j}]$ is defined to be a subnetwork of $\mathcal G$ where $(u,v)\in \tilde{\mathcal A_j}$ if and only if $(u,v)\in \mathcal A$ and $c(u,v)\geqslant c_j$. Hence $\mathcal F_1 \supset \mathcal F_2 \supset \cdots \supset \mathcal F_r$. This property allows the algorithms in [10, 11, 16, 19] to skip analyzing some of the networks $\mathcal F_j$ when solving the QPP. In fact, if the shortest path in the network $\mathcal F_j$ has capacity $c_j'> c_j$, the networks from $\mathcal F_{j+1}$ to $\mathcal F_{j'}$ can be omitted since they cannot provide a better candidate for the optimal solution of the QPP. However, as the networks $\mathcal G_j$ do not satisfy that property, when solving the EQPP it is necessary to solve the shortest path problem in each of the networks $\mathcal G_j$. No network can be skipped since arcs which are not in the network $\mathcal G_j$ can be in the network $\mathcal G_{j+1}$ and vice versa.

Notice also that, at the iteration j, the algorithm saves the shortest path Q as a candidate to be the optimal solution of the EQPP only if its capacity equals $c_j$ (Step 1). Otherwise, it is of no interest at this point of the algorithm. Indeed, if $c(Q)=c_{j'}>c_j$, by applying Lemma 3 no path with capacity $c_j$ can be an optimal solution of the EQPP. Moreover, the path Q will be one of the $s-t$ paths in $\mathcal G_{j'}$ and only if Q is an $s-t$ shortest path in the network $\mathcal G_{j'}$ will it be a candidate to be the optimal solution of the EQPP.

Finally, notice that if there are $P^*$ and $Q^*$ optimal paths with capacities $c_j =c(P^*)\not = c(Q^*)=c_{j'}$, the algorithm is able to provide both paths because they are $s-t$ shortest paths in $\mathcal G_j$ and $\mathcal G_{j'}$, respectively.

Theorem 2

The time complexity of the Algorithm EQPA is $O(r(m + n \log ( n)))$ and uses $O(n + m)$ space.

Proof

It is enough to realize that the algorithm essentially amounts to solving r times a shortest path problem each running in $O(m + n \log (n))$ time [7]. $\square$

5 The bi-objective energy-constrained quickest path problem

In this section we propose to take into consideration not only the transmission time but also the total energy used and thus to minimize both over the set of feasible paths. The bi-objective energy-constrained quickest path problem (BEQPP) can be stated as:

$$\begin{aligned} \begin{array}{ll} \min \limits _{P}&{} \quad {(T_\sigma (P), \quad E_\sigma (P))}\\ \mathrm {s.t.}&{} \quad b_u(\sigma , P) \geqslant 0, u\in \mathcal N\\ &{}P \, \mathrm {is\,an}\, s-t \,\mathrm{path\,in\,the\,network}\, \mathcal G \end{array} \end{aligned}$$

(7)

According to the theory of multi-objective optimization, a feasible solution P is efficient if and only if there is no other feasible solution Q so that $T_\sigma (Q)\leqslant T_\sigma (P)$ and $E_\sigma (Q)\leqslant E_\sigma (P)$ with at least one strict inequality. If P is an efficient solution, it will be called an $s-t$ efficient path. The image $(T_\sigma (P), E_\sigma (P))$ of P is called a non-dominated point. Two feasible solutions P and Q are called equivalent if they have the same image. A complete set of efficient solutions is a set of efficient solutions $X_e$ such that every feasible solution not in $X_e$ is either dominated or equivalent to at least one feasible solution in $X_e$.

The BEQPP is NP-hard since the bi-objective shortest path problem (BSPP) is also NP-hard [17]. Note that the BSPP can be obtained as a particular case of the BEQPP when $r = 1$ and the $b_u$ is big enough not to constrain the transmission. The following theorem allows us to conclude that the efficient paths of the BEQPP can be obtained by solving bi-objective shortest path problems in $\mathcal G_j$.

Theorem 3

Let $\widetilde{P}$ be an $s-t$ efficient path for the BEQPP and $c(\widetilde{P}) = c_h$. Then, $\widetilde{P}$ is an $s-t$ efficient path with respect to:

$$\begin{aligned} \begin{array}{lll} \mathrm {BSPP}_h:&{} \, \min \limits _{P}&{} \,{(l(P), W(P))}\\ &{}\mathrm {s.t.}&{}P \, {is\,an\, s-t \, path \,\,in\,\,the\,\,network} \,\, \mathcal G_h \end{array} \end{aligned}$$

(8)

Proof

The path $\widetilde{P}$ is an $s-t$ path in the network $\mathcal G_h$, by construction of this network. Let us assume that there is an $s-t$ path Q in $\mathcal G_h$ which dominates $\widetilde{P}$ with respect to the bi-objective function (l, W). Then, $c(Q)\geqslant c_h$ and $l(Q) \leqslant l(\widetilde{P})$ and $W(Q) \leqslant W(\widetilde{P})$ with at least one strict inequality. Let us assume for the time being that $l(Q) < l(\widetilde{P})$. Then,

$$\begin{aligned} T_\sigma (Q) = l(Q)+ \frac{\sigma }{c(Q)} \leqslant l(Q)+ \frac{\sigma }{c(\widetilde{P})} < l(\widetilde{P})+ \frac{\sigma }{c(\widetilde{P})} = T_\sigma (\widetilde{P}) \end{aligned}$$

and

$$\begin{aligned} E_\sigma (Q) = W(Q) \frac{\sigma }{c(Q)} \leqslant W(Q) \frac{\sigma }{c(\widetilde{P})} \leqslant W(\widetilde{P})\frac{\sigma }{c(\widetilde{P})} = E_\sigma (\widetilde{P}) \end{aligned}$$

which contradicts that $\widetilde{P}$ is an $s-t$ efficient path for the BEQPP. The other case is analogous. $\square$

As a consequence of Theorem 3, the description of the algorithm BEQPA proposed to solve the BEQPP is as follows:

where the operation Merge is defined as follows:

$$\begin{aligned} \begin{array}{ll} \mathrm {Merge}(\mathcal {E}, \mathcal E_j) = \{P\in \mathcal {E} \cup \mathcal E_j :&{} \mathrm {There\, is\, no}\, Q\in \, \mathcal {E} \, \cup \mathcal E_j \, \mathrm {such\, that} \, Q \, \mathrm {dominates}\, P\\ &{}\mathrm {with\, respect\, to\, the\, bi-objective\, function}\, {(T_\sigma , E_\sigma )}\} \end{array} \end{aligned}$$

Note that in Step 1 of the algorithm there is only the need to compute a complete set of efficient paths. Indeed, let P and Q be equivalent efficient paths for the $\mathrm {BSPP}_j$ with capacities $c(P)=c_h$, $c(Q) = c_i$ such that $c_h > c_i \geqslant c_j$. Since they are equivalent, $l(P) = l(Q)$ and $W(P) = W(Q)$. Hence,

$$\begin{aligned} T_\sigma (P)= & {} l(P)+ \dfrac{\sigma }{c(P)}< l(Q)+ \dfrac{\sigma }{c(Q)} = T_\sigma (Q)\\ E_\sigma (P)= & {} W(P) \dfrac{\sigma }{c(P)} < W(Q)\dfrac{\sigma }{c(Q)} = E_\sigma (Q) \end{aligned}$$

Therefore, P dominates Q with respect to the bi-objective function $(T_\sigma ,E_\sigma )$ and so the path Q is not relevant. In the case that the algorithm records Q, the path P would be considered for sure when solving the $\mathrm {BSPP}_h$.

6 Computational experience

This section presents the results of the computational experiment carried out to evaluate the performance of the algorithms EQPA and BEQPA proposed in this paper. The numerical experiments have been performed on a PC Intel® Core™ I7-3820 CPU at 3.6 GHz $\times$ 8 having 32 GB of RAM under Ubuntu Linux 14.04 LTS. Although we had a multi-processor computer at hand, only one processor was used in our tests. The code has been written in C++, GCC 4.8.2. The algorithm EQPA involves a Dijkstra’s algorithm whose implementation is based on a min-priority queue implemented using a binary heap data structure. In the implementation of the algorithm BEQPA, we have used the Biobjective Label Correcting Algorithm as described in [17] to solve the $\mathrm {BSPP}_j$. As mentioned above, the EQPP can be solved in polynomial time whereas the BEQPP is NP-hard. Due to this very distinctive characteristic, we have used different sets of test problems to assess the performance of the algorithms. Notice also that both algorithms heavily rely on the performance of the algorithms to solve the SPP and the BSPP which they have embedded.

6.1 The EQPA performance evaluation

We have considered three different sets of test problems as in [20]. Set 1 uses the network generator NETGEN [9] to provide the skeleton of the network. Set 2 is based on the network generator GRIDGEN, which is able to provide larger networks. It has been obtained from ftp://dimacs.rutgers.edu/pub/netflow/generators/network/gridgen/gridgen.c. Finally, Set 3 is based on seven USA road networks which have been obtained from http://www.dis.uniroma1.it/challenge9/download.shtml.

Table 1 shows the parameters n, m and r of the networks in Sets 1 and 2. There are 60 problem groups defined by the number of nodes n, the number of arcs m and the number of distinct capacities r in Set 1 and 75 in Set 2. For each problem group, we have generated 10 instances. Delay time and capacity coefficients are generated from uniform distributions in the range [10, 10, 000]. To generate problems with a fixed number of capacities, first the required number of capacities is generated from the corresponding uniform distribution. Then, each arc is assigned one of the capacities generated with a uniform probability. The energy rate of the arc (u, v) is computed as $\omega (u,v) = 10^{-5} c(u,v) l^2(u,v)$. The power at the nodes has been fixed at $3\times 10^8$. For assessing the effect of the number of items which are sent, we have taken $\sigma _1 = 100$, $\sigma _2 = 10{,}000$ and $\sigma _3 = 1{,}000{,}000$.

Table 1 Parameters of test problems Set 1 and Set 2

Tables 2 and 3 display the results provided by the EQPA for Sets 1 and 2. The first to third columns show the value of the parameters r, n and m. The fourth to sixth columns display the mean of the $s-t$ shortest paths computed by the algorithm in the 10 runs which are candidate to be an optimal solution of the EQPP, depending on the size of $\sigma$. The seventh to ninth columns show the mean CPU time in seconds of the 10 runs for the different values of $\sigma$. In the algorithm, there are as many networks $\mathcal G_j$ as distinct capacities. Hence, in principle, we could expect to have as many candidate $s-t$ shortest paths as distinct capacities. However, with an increasing number of distinct capacities, the number of candidate $s-t$ shortest paths increases more slowly. For instance, when $r= 10$, the mean of the $s-t$ shortest paths computed by the algorithm varies between 4.3 and 8.5 for Set 1 and between 5.1 and 9.1 for Set 2. However, when $r= 1000$, the range is 11.1–36.9 for Set 1 and 14.3–38.3 for Set 2. Regarding the CPU times, these are almost negligible when the number of distinct capacities is $r= 10$. As expected, the CPU time increases as long as the number of capacities and the size of the network increases, but for the largest problems the average CPU time is less than 6 min and usually takes less than 1 min. In order to get an overall picture of the CPU time invested by the algorithm in these sets of instances, Fig. 2 displays the boxplot of the CPU time for each number of capacities and each value of $\sigma$, depending on the type of network generator. Every boxplot summarizes the information of 200 problems when using Set 1 and 250 problems when using Set 2. Note that in both groups the variability increases when the number of capacities increases. Networks of Set 2 are larger and so CPU times are longer.

Fig. 2

Boxplots of CPU time depending on the number of capacities and the value of $\sigma$

Table 2 EQPA test results: Set 1

Table 3 EQPA test results: Set 2

As for Set 3, Table 4 displays the characteristics of these USA road networks: name of the network, number of nodes and arcs, and the destination node t. In all cases, the node origin is $s=1$. The energy rate of the arcs and the power of the nodes is the same as in Sets 1 and 2. Based on these networks we have constructed two different groups of test problems. In the first group, the delay is taken as the parameter distance of the road network [20]. The capacity is computed from the parameter time of the road network. The range of the arc times is partitioned in 100 intervals of equal length. In order to have integer capacities, the intervals are rounded off by applying the ceiling function to the upper endpoint and properly adjusting the intervals. For instance, if $(a_1, a_2]$, $(a_2,a_3]$ are the first two intervals of the partition, the resulting intervals would be $(a_1, \lceil {a_2}\rceil ]$, $(\lceil {a_2}\rceil , \lceil {a_3}\rceil ]$. Then, if an arc time is in the interval (a, b], the arc capacity is b. Therefore, problems with 100 distinct capacities are obtained.

Table 4 Dimension and destination nodes of the network in Set 3

The second group of instances built with the USA road networks takes the arc delay and capacity from the empirical distributions proposed in [6], which are displayed in Tables 5 and 6. For this group, 10 instances have been generated for each problem.

Table 5 Arcs delay empirical distribution

Table 6 Arcs capacity empirical distribution

Table 7 provides the results. Now the first column displays the name of the network and the second column shows the destination node. The other columns display, for the first group, the number of candidate shortest paths and the CPU time depending on the size $\sigma$. For the second group, the columns which contain the number of candidate shortest paths and CPU time provide the average of the 10 instances. Note that the number of candidates as well as the CPU time are small. It is worth pointing out that the USA road networks considered are not very dense. In fact, the average degree of the nodes is 2.6.

Table 7 EQPA test results: Set 3

6.2 The BEQPA performance evaluation

As mentioned above, it is harder to solve these problems. We present the results of a set of smaller networks which have been generated using NETGEN. The parameters have been assigned as follows. Delay time and capacity coefficients are generated from uniform distributions in the range [1, 50] and [10, 50], respectively. The energy rate of the arc (u, v) is computed as $\omega (u,v) = 0.01 c(u,v) l^2(u,v)$. The power at the nodes has been fixed at $3\times 10^5$. There are 45 problem groups defined by the number of nodes $n = 1000, 5000$ and 10,000, the number of arcs $m = 10n, 20n$ and 50n and the number of distinct capacities $r=2, 5, 10, 20$ and 30. For each problem group, we have generated 10 instances. The size of the message has been taken to be $\sigma _1 = {10{,}000}$, $\sigma _2={20{,}000}$ and $\sigma _3={50{,}000}$.

Table 8 presents the results provided by the BEQPA. The first to third columns show the value of the parameters r, n and m. The fourth to sixth columns display the mean of the candidate $s-t$ efficient paths computed by the algorithm in the 10 runs by solving problem (8), depending on the size of $\sigma$. The seventh to ninth columns show the mean of the cardinality of the complete set of efficient paths of the BEQPP computed by the algorithm in the 10 runs. Finally, the tenth to twelfth columns display the mean CPU time in seconds of the 10 runs for the different values of $\sigma$. We can see that the number of efficient solutions is reasonably small, as suggested in practical applications for the BSPP [17]. Moreover, computing times are also short, less than twelve seconds on average for all the problems.

Table 8 BEQPA test results

7 Conclusions

In this paper we have introduced the energy-constrained quickest path problem, a variant of the QPP with a side constraint on the consumption of energy at the nodes. Taking into account its properties, this problem can be reformulated as the problem of finding shortest paths with respect to the delay time on a sequence of as many subnetworks of $\mathcal G$ as different capacities. These subnetworks satisfy, by construction, that there is energy available at the nodes for transmitting the data units. A polynomial algorithm has been developed with the same time complexity as the algorithms developed to solve the QPP. The bi-objective variant of the energy-constrained quickest path problem is also considered which aims to minimize transmission time and consumed energy. The problem is transformed into finding a complete set of efficient shortest paths in the same networks. The results of the computational study show the good performance of the algorithms.