# Approximate Path Searching Method for Single-Satellite Observation and Transmission Task Planning Problem

Authors: Shuang Peng; Hao Chen; Jun Li; Ning Jing
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Satellite task planning not only plans the observation tasks to collect images of the earth surface, but also schedules the transmission tasks to download images to the ground station for users’ using, which plays an important role in improving the efficiency of the satellite observation system. However, most of the work to our knowledge, scheduling the observation and transmission tasks separately, ignores the correlation between them in resource (e.g., energy and memory) consumption and acquisition. In this paper, we study the single-satellite observation and transmission task planning problem under a more accurate resource usage model. Two preprocessing strategies including graph partition and nondominated subpaths selection are used to decompose the problem, and an improved label-setting algorithm with the lower bound cutting strategy is proposed to maximize the total benefit. Finally, we compare the proposed method with other three algorithms based on three data sets, and the experimental result shows that our method can find the near-optimal solution in much less time.


---

## Body

## 1. Introduction

Earth observation satellite (EOS) collects images of the earth surface and downloads them to the ground station for users’ using, which has been widely used in environmental monitoring, resource management, agricultural analysis, military reconnaissance, and another aspect of life [1–3]. At present, the contradiction between the overloaded requirements for remote sensing images and the limited EOS resources is increasingly acute. Satellite task planning is to optimize the observation and transmission activities to maximize the total benefit that receives much attention from the government and space agency [1, 4–6].As is shown in Figure1, the EOS orbits the earth. The observation payload takes images and stores them in the storage when a target is in the view of the EOS; this process is called “observation.” The transmission payload downloads images to the ground and frees the corresponding storage when the EOS is in the visible range of a ground station; this process is called “transmission.” Energy is consumed in the process of observation and transmission and acquired when the EOS is in the sun. There is a strong correlation between the observation tasks and the transmission tasks in resource (e.g., energy and memory) consumption and acquisition, which makes the problem intractable to solve.Figure 1
The operation of an EOS.In this paper, we study the single-satellite observation and transmission tasks planning problem (SOTTP) under a more accurate resource usage model. The main contribution includes the following: (1) we develop a directed acyclic graph model and propose two preprocessing strategies including graph partition and nondominated subpaths selection. These two preprocessing strategies decompose the graph model into a series of subgraphs that effectively reduce the complexity of the problem. (2) We construct an equivalent mathematical model and propose an improved label-setting algorithm with the lower bound cutting strategy to solve the SOTTP. This strategy removes the low-benefit paths in each subgraph that improves the search efficiency. (3) Numerical experiments on three data sets show that our method can find the near-optimal solution in much less time.This paper is organized as follows. Section2 places the related work of our research. Section 3 describes the problem which includes the time-dependent resource change relation and the resource constraints. In Section 4, two preprocessing strategies including graph partition and nondominated subpaths selection are used to decompose the problem, and an equivalent mathematical model is developed. In Section 5, an improved label-setting algorithm with the lower bound cutting strategy is adopted to solve the problem. Section 6 describes experimental result on three data sets. Section 7 provides concluding remarks and future works.


## 2. Relate Works

Satellite task planning is a typical combinatorial optimization problem and proved to be NP-Hard [1, 2, 6, 7], which has been widely concerned by scholars and made great achievements. According to the planning approach, the research can be mainly classified into three categories: separate planning, hierarchical planning, and coordinate planning.In separate planning, the observation tasks and the transmission tasks are scheduled separately. Either the satellite observation task planning problem (SOTP) or the satellite transmission task planning problem (STTP, it is also called the satellite ground station scheduling problem) is generally formulated by some mathematical models, such as graph model [8–10], integer programming model [1, 2, 7, 8, 11, 12], or constraint satisfaction programming model [6, 13, 14]. Then they are solved by metaheuristic algorithms (like genetic algorithm [3, 6, 13], tabu search [14, 15], and ant colony optimization [9]), mathematical programming methods (like Lagrangian relaxation [2, 12], branch and cut [7], and column generation [8]), and other domain knowledge based heuristic approaches [10, 16]. However, the memory constraint is ignored or the storage is assumed to be large enough in the SOTP [1–3, 8–11, 14–18]. The energy and memory constraints are neglected or simplified, and the minimum download time is used as the primary optimization objective in the STTP [6, 7, 12, 13, 19–21]. Though the separate planning approach simplifies the problem, it disregards the correlation between the observation tasks and the transmission tasks in resource (e.g., energy and memory) consumption and acquisition.In hierarchical planning [22, 23], the observation tasks are first planned by an algorithm; then the transmission tasks are scheduled by another algorithm based on the selected observation tasks in the previous stage. The quality of solution not only depends on the performance of the two algorithms, but also relates to the way to bond them. The planning result of the observation tasks can be easily destroyed while scheduling the transmission tasks.In coordinate planning [5, 24, 25], the observation tasks and the transmission tasks are scheduled together. Such studies are not much and still in the exploring stage. Li et al. [24] proposed a K-shortest path genetic algorithm to balance the response time and resource utilization. Wang et al. [25] studied the scheduling problem of four optical satellites and four SAR satellites and presented a priority-based heuristic method to maximize the rewards of the images taken and transmitted. Chen et al. [5] considered the specific constraints of electromagnetic detection satellites and adopted a genetic algorithm with solution repairing strategy to solve the problem. Because of the limitation of the TT&C (Telemetry, Tracking, and Command) network resource, the maximum working time is used to model the resource constraint (e.g., the working time of the EOS in each orbital period is the same) in the above research. In the real world, the resource (e.g., energy and memory) status is continuous and correlated [7, 26, 27]. The more resources consumed in the current orbital period, the fewer resources available in the next cycle. It is evident that the traditional resource usage model is imprecise that usually limits the capacity of the EOS. With the emergence of autonomous satellite [26] and the use of data relay satellite [28], it is possible to get the resource status in real time and use the onboard resource usage model to accurately represent the realistic constraints of the EOS rather than the traditional model.In this paper, we study the single-satellite observation and transmission task planning problem from the perspective of resource consumption and acquisition and coordinately plan the observation tasks and the transmission tasks. A more accurate resource usage model is considered, and an approximate path searching method is proposed to solve the problem.


## 3. Problem Description

In the problem, we consider the following hypotheses:(1)
The observation tasks and the transmission tasks are given before planning.(2)
The energy and the memory are renewable resources, but they are limited by the battery capacity and storage capacity, respectively.(3)
The EOS may view more than one ground station simultaneously, but it can only download the images to one ground station at a time.(4)
The EOS cannot transmit the images to the ground station during observing.(5)
Once an observation task or a transmission task is executed, it cannot be interrupted or removed.


### 3.1. Planning Horizon

H
=
[
T
a
,
T
e
] is the planning horizon, where Ta is the start time and Te is the end time. All observation and transmission tasks must be in the planning horizon.


### 3.2. Data Set

(1) Task Set
S
T. The observation task and the transmission task are collectively referred to as task. ∀i∈ST, it is expressed by a 3-tuple (tai,tei,bi):(i)
tai: the start time of task i, which is a constant(ii)
tei: the end time of task i, which is a constant(iii)
bi: the benefit of task i. For an observation task, bi∈[1,40], the higher the value, the more important the task. For a transmission task, it does not take any pictures except downloading them to the ground station such that the benefit is set as zero.(2) Light Window Set
L
W. The EOS can only recharge the battery in the light window. ∀k∈LW, it is expressed by a 2-tuple (lak,lek):(i)
lak: (a constant) the start time of light window k, which means the EOS goes into the sunshine from the shadow(ii)
lek: (a constant) the end time of light window k, which means the EOS goes into the shadow from the sunshine.


### 3.3. Temporal Relation between Tasks

The EOS cannot perform two tasks at a time in our problem. As a result, a setup timeTs(i,j) (Ts(i,j)≤Tsm, where Tsm is the maximum setup time) is required for any two tasks i and j, ∀i,j∈ST. Note that Ts(i,j) is a constant and predefined before planning. Then the temporal relation can be presented as follows: (1)tai<taj⟶taj-tei≥Tsi,j,∀i,j∈ST.


### 3.4. Time-Dependent Resource Change Relation

(1) The Change of Energy. The EOS collects energy by the solar panel and stores it in the battery to support the basic functionality and perform tasks. The change of energy is described as follows: (2)Δet1,t2=∫t1t2πe+t-πe-t-ϕe-tdt,t2>t1, where πe-(t) is the energy consumption rate of basic functionality, ϕe-(t) is the energy consumption rate of satellite payloads, and πe+(t) is the charging rate. If the EOS wants to charge in the high charging rate, it must adjust the attitude that points the solar panel to the sun when it is idle (e.g., no task to do) and a minimum charging time is needed. As a result, πe+(t) is defined by a piecewise function (see (3)), as is shown in Figure 2. (3)πe+t=01if∀k∈LWsuchthatt∉lak,lekπlt2if∃k∈LW,∃i∈STsuchthatt∈lak,lek,t∈tai,teiπlt3if∃k∈LW,∀i∈STsuchthatt∈lak,lek,t∉tai,tei,ΔTck,t<Cminπht4if∃k∈LW,∀i∈STsuchthatt∈lak,lek,t∉tai,tei,ΔTck,t≥Cmin, where πl(t) is the low charging rate, πh(t) is the high charging rate, Cmin (Cmin>Tsm) is the minimum charging time, and ΔTc(k,t) is the available charging time which is defined by(4)ΔTck,t=min⁡lek,tai∣i∈ST,tai>t-max⁡lak,tai∣i∈ST,tai<t.Figure 2
The charging rate in different situations.(2) The Change of Data. The change of data is described as (5)Δdt1,t2=∫t1t2ϕdtdt,t2>t1, where ϕd(t) is the change rate of data, ϕd(t)>0 when the EOS is performing an observation task at time t, and ϕd(t)<0 when the EOS is performing a transmission task at time t; otherwise ϕd(t)=0.


### 3.5. Energy and Memory Constraints

The energy level cannot exceed the lower bound and upper bound of energy at any time because of the limitation of battery capacity. When the energy level reaches the upper bound, it will stop increasing. Lete(t) be the energy level at time t, Emin be the lower bound, and Emax be the upper bound; then the energy constraint is represented as follows: (6)et=min⁡Emax,et1+Δet1,t≥Emin,t>t1.The memory constraint is similar to the energy constraint. The difference is that the data level will stop decreasing when it reaches the lower bound of memory (e.g., all images are downloaded to the ground). Letd(t) be the data level at time t and Dmin (Dmin=0 in the problem) and Dmax be the lower bound and upper bound of memory; then the memory constraint is formulated as follows: (7)dt=max⁡Dmin,dt1+Δdt1,t≤Dmax,t>t1.Definition 1 (resource vector).
Letp be the plan in the period [t1,t2]; then the resource usage of plan p can be expressed by the resource vector R=(Δemax,Δemin,Δdmax,Δdmin,Δeend,Δdend) (Figure 3); for the computation, one can refer to Appendix A. (i)
Δemax≥0 and Δemin≤0: the maximum and minimum change of energy while performing plan p.(ii)
Δdmax≥0 and Δdmin≤0: the maximum and minimum change of data while performing plan p.(iii)
Δeend and Δdend: the change of energy and memory after plan p is performed.Figure 3
The resource vector in the period[t1,t2].Theorem 2.
Lete(t1) and d(t1) be the energy and data level at time t1. If p is a feasible plan in the period [t1,t2], it must satisfy the following constraints: (8a)max⁡Δet1,t′,t′∈t1,t-Δet1,t≤Emax-Emin,t∈t1,t2,(8b)Δdt1,t-min⁡Δdt1,t′,t′∈t1,t≤Dmax-Dmin,t∈t1,t2,(8c)et1+Δemin≥Emin,(8d)dt1+Δdmax≤Dmax.Proof.
See AppendixB.Theorem 3.
Lete(t1) and d(t1) be the energy and data level at time t1. If p is a feasible plan in the period [t1,t2], the energy and data level at time t2 can be computed as follows: (9a)et2=min⁡Emax-Δemax,et1+Δeend,(9b)dt2=max⁡Dmin-Δdmin,dt1+Δdend.Proof.
See AppendixC.


### 3.6. Optimization Objective

The objective of the SOTTP is to plan the observation and transmission tasks in the planning horizon which maximize the total benefit without violating all constraints.


## 3.1. Planning Horizon

H
=
[
T
a
,
T
e
] is the planning horizon, where Ta is the start time and Te is the end time. All observation and transmission tasks must be in the planning horizon.


## 3.2. Data Set

(1) Task Set
S
T. The observation task and the transmission task are collectively referred to as task. ∀i∈ST, it is expressed by a 3-tuple (tai,tei,bi):(i)
tai: the start time of task i, which is a constant(ii)
tei: the end time of task i, which is a constant(iii)
bi: the benefit of task i. For an observation task, bi∈[1,40], the higher the value, the more important the task. For a transmission task, it does not take any pictures except downloading them to the ground station such that the benefit is set as zero.(2) Light Window Set
L
W. The EOS can only recharge the battery in the light window. ∀k∈LW, it is expressed by a 2-tuple (lak,lek):(i)
lak: (a constant) the start time of light window k, which means the EOS goes into the sunshine from the shadow(ii)
lek: (a constant) the end time of light window k, which means the EOS goes into the shadow from the sunshine.


## 3.3. Temporal Relation between Tasks

The EOS cannot perform two tasks at a time in our problem. As a result, a setup timeTs(i,j) (Ts(i,j)≤Tsm, where Tsm is the maximum setup time) is required for any two tasks i and j, ∀i,j∈ST. Note that Ts(i,j) is a constant and predefined before planning. Then the temporal relation can be presented as follows: (1)tai<taj⟶taj-tei≥Tsi,j,∀i,j∈ST.


## 3.4. Time-Dependent Resource Change Relation

(1) The Change of Energy. The EOS collects energy by the solar panel and stores it in the battery to support the basic functionality and perform tasks. The change of energy is described as follows: (2)Δet1,t2=∫t1t2πe+t-πe-t-ϕe-tdt,t2>t1, where πe-(t) is the energy consumption rate of basic functionality, ϕe-(t) is the energy consumption rate of satellite payloads, and πe+(t) is the charging rate. If the EOS wants to charge in the high charging rate, it must adjust the attitude that points the solar panel to the sun when it is idle (e.g., no task to do) and a minimum charging time is needed. As a result, πe+(t) is defined by a piecewise function (see (3)), as is shown in Figure 2. (3)πe+t=01if∀k∈LWsuchthatt∉lak,lekπlt2if∃k∈LW,∃i∈STsuchthatt∈lak,lek,t∈tai,teiπlt3if∃k∈LW,∀i∈STsuchthatt∈lak,lek,t∉tai,tei,ΔTck,t<Cminπht4if∃k∈LW,∀i∈STsuchthatt∈lak,lek,t∉tai,tei,ΔTck,t≥Cmin, where πl(t) is the low charging rate, πh(t) is the high charging rate, Cmin (Cmin>Tsm) is the minimum charging time, and ΔTc(k,t) is the available charging time which is defined by(4)ΔTck,t=min⁡lek,tai∣i∈ST,tai>t-max⁡lak,tai∣i∈ST,tai<t.Figure 2
The charging rate in different situations.(2) The Change of Data. The change of data is described as (5)Δdt1,t2=∫t1t2ϕdtdt,t2>t1, where ϕd(t) is the change rate of data, ϕd(t)>0 when the EOS is performing an observation task at time t, and ϕd(t)<0 when the EOS is performing a transmission task at time t; otherwise ϕd(t)=0.


## 3.5. Energy and Memory Constraints

The energy level cannot exceed the lower bound and upper bound of energy at any time because of the limitation of battery capacity. When the energy level reaches the upper bound, it will stop increasing. Lete(t) be the energy level at time t, Emin be the lower bound, and Emax be the upper bound; then the energy constraint is represented as follows: (6)et=min⁡Emax,et1+Δet1,t≥Emin,t>t1.The memory constraint is similar to the energy constraint. The difference is that the data level will stop decreasing when it reaches the lower bound of memory (e.g., all images are downloaded to the ground). Letd(t) be the data level at time t and Dmin (Dmin=0 in the problem) and Dmax be the lower bound and upper bound of memory; then the memory constraint is formulated as follows: (7)dt=max⁡Dmin,dt1+Δdt1,t≤Dmax,t>t1.Definition 1 (resource vector).
Letp be the plan in the period [t1,t2]; then the resource usage of plan p can be expressed by the resource vector R=(Δemax,Δemin,Δdmax,Δdmin,Δeend,Δdend) (Figure 3); for the computation, one can refer to Appendix A. (i)
Δemax≥0 and Δemin≤0: the maximum and minimum change of energy while performing plan p.(ii)
Δdmax≥0 and Δdmin≤0: the maximum and minimum change of data while performing plan p.(iii)
Δeend and Δdend: the change of energy and memory after plan p is performed.Figure 3
The resource vector in the period[t1,t2].Theorem 2.
Lete(t1) and d(t1) be the energy and data level at time t1. If p is a feasible plan in the period [t1,t2], it must satisfy the following constraints: (8a)max⁡Δet1,t′,t′∈t1,t-Δet1,t≤Emax-Emin,t∈t1,t2,(8b)Δdt1,t-min⁡Δdt1,t′,t′∈t1,t≤Dmax-Dmin,t∈t1,t2,(8c)et1+Δemin≥Emin,(8d)dt1+Δdmax≤Dmax.Proof.
See AppendixB.Theorem 3.
Lete(t1) and d(t1) be the energy and data level at time t1. If p is a feasible plan in the period [t1,t2], the energy and data level at time t2 can be computed as follows: (9a)et2=min⁡Emax-Δemax,et1+Δeend,(9b)dt2=max⁡Dmin-Δdmin,dt1+Δdend.Proof.
See AppendixC.


## 3.6. Optimization Objective

The objective of the SOTTP is to plan the observation and transmission tasks in the planning horizon which maximize the total benefit without violating all constraints.


## 4. The Preprocessing Strategies and the Planning Model

In this section, we first develop a directed acyclic graph model for the problem. Then the graph is partitioned into several subgraphs by the graph partition strategy, and the nondominated subpaths in each subgraph are searched by the nondominated subpaths selection strategy. Finally, an equivalent planning model is established.


### 4.1. The Directed Acyclic Graph Model

Given the tasks and sorting them in chronological order, the directed acyclic graphG=(V,E) (Figure 4) is used to model the problem, where V is the set of nodes and E is the set of edges. Each node vi∈V is expressed as (tai,tei), where tai,tei are the start time and end time of task i, i∈ST. Each edge (i,j)∈E is denoted by (Rij,bij), where Rij=(Δemaxij,Δeminij,Δeendij,Δdmaxij,Δdminij,Δdendij) is the resource vector (edge (i,j) is a plan in the period [tei,tej], see Definition 1) and bij is equal to the benefit of task j, j∈ST. ∀vi, vj∈V, if they satisfy the constraints (1), (8a), and (8b), there is a directed edge point from vi to vj. There are also two virtual nodes vTa′=(Ta,Ta) (the source node) and vTe′=(Te,Te) (the sink node) in the graph. The goal is to find an elementary path from vTa′ to vTe′ that maximizes the total benefit without violating the energy and memory constraints.Figure 4
The directed acyclic graph model.Some notations used in the model are defined as follows:(i)
Eo, Do: the amounts of energy and data that the EOS stored at the beginning of the planning horizon(ii)
Emin, Emax: the minimum and maximum allowable amounts of energy to be stored in the battery (e.g., the lower bound and upper bound of energy)(iii)
Dmin, Dmax: the minimum and maximum allowable amounts of data to be stored in the storage (e.g., the lower bound and upper bound of memory)(iv)
xij∈{0,1}: the decision variable; xij=1 means edge (i,j) is selected; otherwise it is not, 1≤i<j≤n(v)
yj≥0: the decision variable, which represents the total amount of energy spilled throughout edges that point to node vj, 1≤j≤n(vi)
zj≥0: the decision variable, which represents the total amount of data spilled throughout edges that point to node vj, 1≤j≤n.Then the mathematical model can be formulated as follows:(10)Maximize∑i=1n∑j=1nbij∗xij(11)Subjectto∑j=1nx1j=1(12)∑i=1nxin=1(13)∑i=1j-1xij≤1,1<j<n(14)∑i=1j-1xij=∑k=i+1nxjk,1<j<n(15)E0+∑j=2k-1∑i=1j-1Δeendij∗xij-yj+∑i=1k-1Δemaxik∗xik-yk≤Emax,1<k≤n(16)E0+∑j=2k-1∑i=1j-1Δeendij∗xij-yj+∑i=1k-1Δeminik∗xik≥Emin,1<k≤n(17)E0+∑j=2k-1∑i=1j-1Δdendij∗xij+zj+∑i=1k-1Δdmaxik∗xik≤Dmax,1<k≤n(18)E0+∑j=2k-1∑i=1j-1Δdendij∗xij+zj+∑i=1k-1Δdminik∗xik+zk≥Dmin,1<k≤n.The objective function (10) is used to maximize the total benefit over the planning horizon. Constraints (11), (12), (13), and (14) are the outdegree and indegree constraints of each node. Constraints (15), (16), (17), and (18) ensure that the energy and data level at each node cannot exceed the lower bound and upper bound of energy and memory.


### 4.2. Graph Partition

In this subsection, a virtual common node based edge-cut method is used to partition the graph. The definition of the virtual common node is as follows.Definition 4.
Partition point and virtual common node: given a timetA, let V(LA) be the set of nodes whose start time is less than tA and V(RA) be the set of nodes whose end time is greater than tA. If the following two conditions are satisfied (as is shown in Figure 5), then time tA is a partition point and node vA′=(tA,tA) is a virtual common node of graph G. (1)
∀k∈LW→tA∉[lak,lek], min⁡{taj∣vj∈V(RA)}-max⁡teivi∈VLA≥Tsm.(2)
∃k∈LW→tA-max⁡lak,tei∣vi∈VLA≥Cmin,min⁡{lek,taj∣vj∈V(RA)}-tA≥Cmin.Figure 5
The partition point in a plan.If nodevA′=(tA,tA) is a virtual common node of graph G, then the edges that connect the nodes on the left and right side of vA′ are updated (e.g., edges (i,A),(A,j) are added in the graph and edge (i,j) is removed, ∀vi∈V(LA), ∀vj∈V(RA)). After all virtual common nodes are found and the edges are updated, the graph is partitioned (as is shown in Figure 6). Note that there is also an edge that connects two neighbor virtual common nodes.Figure 6
The DAG model after graph partition.Lemma 5.
If nodevA′=(tA,tA) is a virtual common node of graph G, the connectivity and the resource vector between any two nodes are consistent before and after graph partition.Proof.
From requirement (1) and requirement (2),∀vi∈V(LA), ∀vj∈V(RA), taj-tei>min{Tsm,Cmin}=Tsm≥Ts(i,j), so there is an edge or path connecting node vi and node vj before and after graph partition. That is, the connectivity is consistent.
∀
v
i
∈
V
(
L
A
), ∀vj∈V(RA), let πe+′(t), πe+′′(t), and πe+′′′(t) be the charging rate on edges (i,j), (i,A), and (A,j), respectively. If requirement (1) or requirement (2) is met, from formula (3), we know that πe+′(tA)=πe+′′(tA)=πe+′′′(tA); ∀t∈[tei,tA], πe+′(t)=πe+′′(t); ∀t∈[tA,taj], πe+′(t)=πe+′′′(t). That is, the charging rates in the period [tei,taj] are the same before and after graph partition. From Definition 1, we can conclude that the resource vector is consistent.By using the graph partition strategy, the graph model can be described asG={G1,G2,…,Gs}, where Gi is the ith subgraph and s is the number of subgraphs. Let V′={v0′,…,vs′} be the set of virtual nodes where v0′=vTa′ and vs′=vTe′; V(Gi) is the set of nodes in Gi; then V(Gi)∩V(Gi+1)=vi′, ⋃1≤i≤sV(Gi)=V(G)∪V′.


### 4.3. Nondominated Subpaths Selection

After the graph is partitioned, the label-setting algorithm [18, 29, 30] is used to search the nondominated subpaths in each subgraph. The dominance relation used in this algorithm is relaxed, which is defined as follows.Definition 6 (dominance relation).
LetPi,j be the set of paths from node vi to node vj. ∀pm,pn∈Pi,j, if they satisfy one of the following three conditions, then path pm is dominant to path pn and expressed as pm≳pn, where bm is the total benefit of pm, Δeendm and Δdendm are the change of energy and memory of pm (see Definition 1), and α,β,γ are the relaxation factor of benefit, energy, and memory, respectively. In these conditions, bm,α,β,γ are nonnegative, and Δeendm,Δdendm can be positive or negative. (1)
bm∗1+α≥bn, Δeendm≥Δeendm, and Δdendm≤Δdendm.(2)
bm≥bn, Δeendm∗(1+β∗Δeendm/|Δeendm|)≥Δeendn, and Δdendm≤Δdendn.(3)
bm≥bn, Δeendm≥Δeendn, and Δdendm∗(1-γ∗Δdendm/|Δdendm|)≤Δdendn.Forpn∈Pi,j, if ∄pm∈Pi,j with m≠n that satisfies pm≳pn, then pn is a nondominated path; otherwise it is a dominated path.The process of nondominated subpaths selection in subgraphGi is to search the nondominated paths from node vi-1′ to node vi′; for details, one can refer to [30]. Note that the subpaths violating constraint (8a) or (8b) are also removed in the process.


### 4.4. The Equivalent Planning Model

Through preprocessing, the graph model is partitioned into several subgraphs, and the problem is transformed to search a feasible subpath from each subgraph without violating the resource constraint. An equivalent planning model is developed in this subsection. The notations used in the model are summarised as follows.Parameters
(i)
s: the number of subgraphs in graph G
(ii)
n
i: the number of subpaths in subgraph Gi, 1≤i≤s
(iii)
t
g
i: the end time of subgraph Gi, which is equal to the end time of node vi′
(iv)
P
i: the set of subpaths (from node vi-1′ to node vi′) in subgraph Gi
(v)
Q
i: the set of paths (from node vTa′ to node vi′) in subgraph Gi
(vi)
p
i
j: the jth subpath in Pi
(vii)
b
i
j
′: the total benefit of subpath pij
(viii)
R
i
j
′
=
(
Δ
e
m
a
x
i
j
′
,
Δ
e
m
i
n
i
j
′
,
Δ
d
m
a
x
i
j
′
,
Δ
d
m
i
n
i
j
′
,
Δ
e
e
n
d
i
j
′
,
Δ
d
e
n
d
i
j
′
): the resource factor of subpath pij (a plan in the period [tgi-1,tgi]); for details, refer to Definition 1
(ix)
E
o, Do, Emin, Emax, Dmin, Dmax: refer to Section 4.1.Variables
(i)
x
i
j
′
∈
{
0,1
}: the binary value that represents whether subpath pij is selected, 1≤i≤s, 1≤j≤ni
(ii)
e
(
t
g
i
): the energy level at the end of subgraph Gi, 1≤i≤s
(iii)
d
(
t
g
i
): the data level at the end of subgraph Gi, 1≤i≤s.Then the planning model is formulated as follows:(19)Maximize∑i=1s∑j=1nibij′∗xij′(20)Subjectto∑j=1nixij′=1,1≤i≤s(21)etg0=Eo(22)dtg0=Do(23)etgi=min⁡Emax-∑j=1niΔemaxij′∗xij′,etgi-1+∑j=1niΔeendij′∗xij′,1≤i≤s(24)dtgi=max⁡Dmin-∑j=1niΔdminij′∗xij′,dtgi-1+∑j=1niΔdendij′∗xij′,1≤i≤s(25)etgi-1+∑j=1niΔeminij′∗xij′≥Emin,1≤i≤s(26)dtgi-1+∑j=1niΔdmaxij′∗xij′≤Dmax,1≤i≤s.The objective function (19) is the same as (10). Equation (20) enforces that there is one and only one subpath that can be selected in each subgraph. Constraints (21) and (22) initialize the amount of energy and data that satellite stored at the beginning of the planning horizon. Constraint (23) defines the energy level at the end of each subgraph. Constraint (24) defines the data level at the end of each subgraph. Constraint (25) ensures that the energy level cannot be less than the lower bound of energy in each subgraph. Constraint (26) ensures that the data level cannot be greater than the upper bound of memory in each subgraph.


## 4.1. The Directed Acyclic Graph Model

Given the tasks and sorting them in chronological order, the directed acyclic graphG=(V,E) (Figure 4) is used to model the problem, where V is the set of nodes and E is the set of edges. Each node vi∈V is expressed as (tai,tei), where tai,tei are the start time and end time of task i, i∈ST. Each edge (i,j)∈E is denoted by (Rij,bij), where Rij=(Δemaxij,Δeminij,Δeendij,Δdmaxij,Δdminij,Δdendij) is the resource vector (edge (i,j) is a plan in the period [tei,tej], see Definition 1) and bij is equal to the benefit of task j, j∈ST. ∀vi, vj∈V, if they satisfy the constraints (1), (8a), and (8b), there is a directed edge point from vi to vj. There are also two virtual nodes vTa′=(Ta,Ta) (the source node) and vTe′=(Te,Te) (the sink node) in the graph. The goal is to find an elementary path from vTa′ to vTe′ that maximizes the total benefit without violating the energy and memory constraints.Figure 4
The directed acyclic graph model.Some notations used in the model are defined as follows:(i)
Eo, Do: the amounts of energy and data that the EOS stored at the beginning of the planning horizon(ii)
Emin, Emax: the minimum and maximum allowable amounts of energy to be stored in the battery (e.g., the lower bound and upper bound of energy)(iii)
Dmin, Dmax: the minimum and maximum allowable amounts of data to be stored in the storage (e.g., the lower bound and upper bound of memory)(iv)
xij∈{0,1}: the decision variable; xij=1 means edge (i,j) is selected; otherwise it is not, 1≤i<j≤n(v)
yj≥0: the decision variable, which represents the total amount of energy spilled throughout edges that point to node vj, 1≤j≤n(vi)
zj≥0: the decision variable, which represents the total amount of data spilled throughout edges that point to node vj, 1≤j≤n.Then the mathematical model can be formulated as follows:(10)Maximize∑i=1n∑j=1nbij∗xij(11)Subjectto∑j=1nx1j=1(12)∑i=1nxin=1(13)∑i=1j-1xij≤1,1<j<n(14)∑i=1j-1xij=∑k=i+1nxjk,1<j<n(15)E0+∑j=2k-1∑i=1j-1Δeendij∗xij-yj+∑i=1k-1Δemaxik∗xik-yk≤Emax,1<k≤n(16)E0+∑j=2k-1∑i=1j-1Δeendij∗xij-yj+∑i=1k-1Δeminik∗xik≥Emin,1<k≤n(17)E0+∑j=2k-1∑i=1j-1Δdendij∗xij+zj+∑i=1k-1Δdmaxik∗xik≤Dmax,1<k≤n(18)E0+∑j=2k-1∑i=1j-1Δdendij∗xij+zj+∑i=1k-1Δdminik∗xik+zk≥Dmin,1<k≤n.The objective function (10) is used to maximize the total benefit over the planning horizon. Constraints (11), (12), (13), and (14) are the outdegree and indegree constraints of each node. Constraints (15), (16), (17), and (18) ensure that the energy and data level at each node cannot exceed the lower bound and upper bound of energy and memory.


## 4.2. Graph Partition

In this subsection, a virtual common node based edge-cut method is used to partition the graph. The definition of the virtual common node is as follows.Definition 4.
Partition point and virtual common node: given a timetA, let V(LA) be the set of nodes whose start time is less than tA and V(RA) be the set of nodes whose end time is greater than tA. If the following two conditions are satisfied (as is shown in Figure 5), then time tA is a partition point and node vA′=(tA,tA) is a virtual common node of graph G. (1)
∀k∈LW→tA∉[lak,lek], min⁡{taj∣vj∈V(RA)}-max⁡teivi∈VLA≥Tsm.(2)
∃k∈LW→tA-max⁡lak,tei∣vi∈VLA≥Cmin,min⁡{lek,taj∣vj∈V(RA)}-tA≥Cmin.Figure 5
The partition point in a plan.If nodevA′=(tA,tA) is a virtual common node of graph G, then the edges that connect the nodes on the left and right side of vA′ are updated (e.g., edges (i,A),(A,j) are added in the graph and edge (i,j) is removed, ∀vi∈V(LA), ∀vj∈V(RA)). After all virtual common nodes are found and the edges are updated, the graph is partitioned (as is shown in Figure 6). Note that there is also an edge that connects two neighbor virtual common nodes.Figure 6
The DAG model after graph partition.Lemma 5.
If nodevA′=(tA,tA) is a virtual common node of graph G, the connectivity and the resource vector between any two nodes are consistent before and after graph partition.Proof.
From requirement (1) and requirement (2),∀vi∈V(LA), ∀vj∈V(RA), taj-tei>min{Tsm,Cmin}=Tsm≥Ts(i,j), so there is an edge or path connecting node vi and node vj before and after graph partition. That is, the connectivity is consistent.
∀
v
i
∈
V
(
L
A
), ∀vj∈V(RA), let πe+′(t), πe+′′(t), and πe+′′′(t) be the charging rate on edges (i,j), (i,A), and (A,j), respectively. If requirement (1) or requirement (2) is met, from formula (3), we know that πe+′(tA)=πe+′′(tA)=πe+′′′(tA); ∀t∈[tei,tA], πe+′(t)=πe+′′(t); ∀t∈[tA,taj], πe+′(t)=πe+′′′(t). That is, the charging rates in the period [tei,taj] are the same before and after graph partition. From Definition 1, we can conclude that the resource vector is consistent.By using the graph partition strategy, the graph model can be described asG={G1,G2,…,Gs}, where Gi is the ith subgraph and s is the number of subgraphs. Let V′={v0′,…,vs′} be the set of virtual nodes where v0′=vTa′ and vs′=vTe′; V(Gi) is the set of nodes in Gi; then V(Gi)∩V(Gi+1)=vi′, ⋃1≤i≤sV(Gi)=V(G)∪V′.


## 4.3. Nondominated Subpaths Selection

After the graph is partitioned, the label-setting algorithm [18, 29, 30] is used to search the nondominated subpaths in each subgraph. The dominance relation used in this algorithm is relaxed, which is defined as follows.Definition 6 (dominance relation).
LetPi,j be the set of paths from node vi to node vj. ∀pm,pn∈Pi,j, if they satisfy one of the following three conditions, then path pm is dominant to path pn and expressed as pm≳pn, where bm is the total benefit of pm, Δeendm and Δdendm are the change of energy and memory of pm (see Definition 1), and α,β,γ are the relaxation factor of benefit, energy, and memory, respectively. In these conditions, bm,α,β,γ are nonnegative, and Δeendm,Δdendm can be positive or negative. (1)
bm∗1+α≥bn, Δeendm≥Δeendm, and Δdendm≤Δdendm.(2)
bm≥bn, Δeendm∗(1+β∗Δeendm/|Δeendm|)≥Δeendn, and Δdendm≤Δdendn.(3)
bm≥bn, Δeendm≥Δeendn, and Δdendm∗(1-γ∗Δdendm/|Δdendm|)≤Δdendn.Forpn∈Pi,j, if ∄pm∈Pi,j with m≠n that satisfies pm≳pn, then pn is a nondominated path; otherwise it is a dominated path.The process of nondominated subpaths selection in subgraphGi is to search the nondominated paths from node vi-1′ to node vi′; for details, one can refer to [30]. Note that the subpaths violating constraint (8a) or (8b) are also removed in the process.


## 4.4. The Equivalent Planning Model

Through preprocessing, the graph model is partitioned into several subgraphs, and the problem is transformed to search a feasible subpath from each subgraph without violating the resource constraint. An equivalent planning model is developed in this subsection. The notations used in the model are summarised as follows.Parameters
(i)
s: the number of subgraphs in graph G
(ii)
n
i: the number of subpaths in subgraph Gi, 1≤i≤s
(iii)
t
g
i: the end time of subgraph Gi, which is equal to the end time of node vi′
(iv)
P
i: the set of subpaths (from node vi-1′ to node vi′) in subgraph Gi
(v)
Q
i: the set of paths (from node vTa′ to node vi′) in subgraph Gi
(vi)
p
i
j: the jth subpath in Pi
(vii)
b
i
j
′: the total benefit of subpath pij
(viii)
R
i
j
′
=
(
Δ
e
m
a
x
i
j
′
,
Δ
e
m
i
n
i
j
′
,
Δ
d
m
a
x
i
j
′
,
Δ
d
m
i
n
i
j
′
,
Δ
e
e
n
d
i
j
′
,
Δ
d
e
n
d
i
j
′
): the resource factor of subpath pij (a plan in the period [tgi-1,tgi]); for details, refer to Definition 1
(ix)
E
o, Do, Emin, Emax, Dmin, Dmax: refer to Section 4.1.Variables
(i)
x
i
j
′
∈
{
0,1
}: the binary value that represents whether subpath pij is selected, 1≤i≤s, 1≤j≤ni
(ii)
e
(
t
g
i
): the energy level at the end of subgraph Gi, 1≤i≤s
(iii)
d
(
t
g
i
): the data level at the end of subgraph Gi, 1≤i≤s.Then the planning model is formulated as follows:(19)Maximize∑i=1s∑j=1nibij′∗xij′(20)Subjectto∑j=1nixij′=1,1≤i≤s(21)etg0=Eo(22)dtg0=Do(23)etgi=min⁡Emax-∑j=1niΔemaxij′∗xij′,etgi-1+∑j=1niΔeendij′∗xij′,1≤i≤s(24)dtgi=max⁡Dmin-∑j=1niΔdminij′∗xij′,dtgi-1+∑j=1niΔdendij′∗xij′,1≤i≤s(25)etgi-1+∑j=1niΔeminij′∗xij′≥Emin,1≤i≤s(26)dtgi-1+∑j=1niΔdmaxij′∗xij′≤Dmax,1≤i≤s.The objective function (19) is the same as (10). Equation (20) enforces that there is one and only one subpath that can be selected in each subgraph. Constraints (21) and (22) initialize the amount of energy and data that satellite stored at the beginning of the planning horizon. Constraint (23) defines the energy level at the end of each subgraph. Constraint (24) defines the data level at the end of each subgraph. Constraint (25) ensures that the energy level cannot be less than the lower bound of energy in each subgraph. Constraint (26) ensures that the data level cannot be greater than the upper bound of memory in each subgraph.


## 5. The Improved Label-Setting Algorithm

In this section, we propose an improved label-setting algorithm with the lower bound cutting strategy (LSLBC) to search the near-optimal solution of the SOTTP. The label-setting algorithm (LS) is an exact path searching algorithm that can find all nondominated paths in each subgraph. However, only the nondominated path with the maximum benefit is selected in our problem, and low-benefit paths in each subgraph are mostly useless. The lower bound cutting strategy is used to remove the paths in each subgraph whose benefit is less than the lower bound, which avoids enumerating all nondominated paths and improves search efficiency.


### 5.1. The Lower Bound Cutting Strategy

The lower bound of each subgraph is the key of the lower bound cutting strategy, but they are hard to be computed. In fact, there is a connection between them and the lower bound of the problem, such that we can compute the approximate lower bound of a subgraph based on this relation.


#### 5.1.1. The Lower Bound of the Problem

We design a two-phase hierarchical algorithm (called GS-BC) to find the lower bound of the problem. Before discussing the algorithm, the concept it used is given as follows.Definition 7 (energy efficiency).
(27)
η
p
i
j
=
Δ
e
e
n
d
i
j
′
-
max
⁡
Δ
e
e
n
d
i
k
′
∣
p
i
k
∈
P
i
b
i
j
′
+
ε
,where η(pij) is the energy efficiency of subpath pij and ε is the smallest constant in the computer used to avoid zero-division error.The energy efficiency represents the amount of energy consumed per unit of benefit and satisfiesη(pij)≤0.In the first phase of GS-BC, the observation tasks are planned by the energy efficiency based greedy search algorithm (GS, as is shown in Algorithm1). This algorithm selects a subpath from each subgraph one by one until reaching the end. When it searches a subgraph, the subpath with the maximum benefit is added to the solution. If the energy constraint is violated, then the subpath with the minimum energy efficiency in the solution is replaced by another subpath (it is not searched and has the maximum benefit) until the conflict is removed. In the second phase of GS-BC, the branch and cut algorithm (BC) [7] is used to schedule the transmission tasks based on the selected observation tasks in the first phase.Algorithm 1:Energy efficiency based greedy search algorithm.
Input: graph G={G1,…,Gs}.
Output: solution P∗={p1∗,…,ps∗}  /∗  pi∗ is the selected subpath in Gi. ∗/
(1)∀i∈[1,s], pi∗←null;
(2)for all  Gi∈G  do
(3)pj←maxbenefit(Pi);  /∗  pj is the subpath with the maximum benefit in Pi. ∗/
(4)pi∗←pj;
(5)Pi←Pi\pj;
(6)if  isconflict(P∗)   then  /∗ whether the energy constraint is violated. ∗/.
(7)while  isconflict(P∗)   do
(8)m←repairid(P∗);  /∗  m is the index of the subpath with the minimum energy efficiency in P∗. ∗/
(9)pk←maxbenefit(Pm);  /∗  pk is the subpath with the maximum benefit in Pm. ∗/
(10)pm∗←pk;
(11)Pm←Pm\pk;
(12)end while
(13)end if
(14)end for


#### 5.1.2. The Lower Bound of the Subgraph

LetP∗={p1∗,p2∗,…,ps∗} be the solution of GS-BC, pi∗ be the selected subpath in subgraph Gi, and bi∗ be the benefit of subpath pi∗; then we define the lower bound of a subgraph as (28)Lk=fl∑i=1kbi∗∑i=1sbi∗∗∑i=1kbi∗,1≤k≤s,where fl(x) is the discount function that represents the relation between the lower bound of a subgraph and the lower bound of the problem. fl(x) is obtained by the statistical method; for details, refer to Section 6.2.2.


### 5.2. The Improved Label-Setting Algorithm

After the lower bound of each subgraph is computed, the improved label-setting algorithm with the lower bound cutting strategy is used to find the near-optimal solution of the problem. This algorithm incrementally searches the nondominated paths from the first subgraph to the last subgraph one by one until reaching the end. When it searches a subgraph, the low-benefit paths are removed by the lower bound cutting strategy, and the dominated paths are discarded based on the dominance relation (see Definition6) that avoids exploring the whole paths in the solution space. For details, refer to Algorithm 2.Algorithm 2:Improved label-setting algorithm.
Input: graph G={G1,…,Gs}.
Output: the optimal path qs∗
(1)for  i=2,…,s  do
(2)for all  pi∈Pi  do  /∗  Pi is set of subpaths in subgraph Gi. ∗/
(3)for allqi-1∈Qi-1  do  /∗  Qi-1 is set of paths in subgraph Gi-1. ∗/
(4)if  notconflict(qi-1,pi)  then /∗  pi must satisfy the constraint when adding it to qi-1. ∗/
(5)qi←append(qi-1,pi); /∗  add pi to qi-1. ∗/
(6)Qi←Qi∪qi;
(7)end if
(8)end for
(9)Li←getlowerbound(); /∗  Li is the lower bound of subgraph Gi. ∗/
(10)for  j=1,…,num(Qi)   do  /∗  num(Qi) is the number of paths in Qi. ∗/
(11)if  bj<L(i)   then  /∗  the total benefit must greater than the lower bound. ∗/
(12)Qi←Qi\qj;
(13)end if
(14)end for
(15)forj=1,…,num(Qi)  do
(16)for  k=j+1,…,num(Qi)  do
(17)if  qj≲qk  then
(18)Qi←Qi\qj;
(19)      break;
(20)else if  qj≳qk  then
(21)Qi←Qi\qk;
(22)end if
(23)end for
(24)end for
(25)end for
(26)end for
(27)qs∗←maxbenefit(Qs); /∗  qs∗ is the path with the maximum benefit in Qs. ∗/


## 5.1. The Lower Bound Cutting Strategy

The lower bound of each subgraph is the key of the lower bound cutting strategy, but they are hard to be computed. In fact, there is a connection between them and the lower bound of the problem, such that we can compute the approximate lower bound of a subgraph based on this relation.


### 5.1.1. The Lower Bound of the Problem

We design a two-phase hierarchical algorithm (called GS-BC) to find the lower bound of the problem. Before discussing the algorithm, the concept it used is given as follows.Definition 7 (energy efficiency).
(27)
η
p
i
j
=
Δ
e
e
n
d
i
j
′
-
max
⁡
Δ
e
e
n
d
i
k
′
∣
p
i
k
∈
P
i
b
i
j
′
+
ε
,where η(pij) is the energy efficiency of subpath pij and ε is the smallest constant in the computer used to avoid zero-division error.The energy efficiency represents the amount of energy consumed per unit of benefit and satisfiesη(pij)≤0.In the first phase of GS-BC, the observation tasks are planned by the energy efficiency based greedy search algorithm (GS, as is shown in Algorithm1). This algorithm selects a subpath from each subgraph one by one until reaching the end. When it searches a subgraph, the subpath with the maximum benefit is added to the solution. If the energy constraint is violated, then the subpath with the minimum energy efficiency in the solution is replaced by another subpath (it is not searched and has the maximum benefit) until the conflict is removed. In the second phase of GS-BC, the branch and cut algorithm (BC) [7] is used to schedule the transmission tasks based on the selected observation tasks in the first phase.Algorithm 1:Energy efficiency based greedy search algorithm.
Input: graph G={G1,…,Gs}.
Output: solution P∗={p1∗,…,ps∗}  /∗  pi∗ is the selected subpath in Gi. ∗/
(1)∀i∈[1,s], pi∗←null;
(2)for all  Gi∈G  do
(3)pj←maxbenefit(Pi);  /∗  pj is the subpath with the maximum benefit in Pi. ∗/
(4)pi∗←pj;
(5)Pi←Pi\pj;
(6)if  isconflict(P∗)   then  /∗ whether the energy constraint is violated. ∗/.
(7)while  isconflict(P∗)   do
(8)m←repairid(P∗);  /∗  m is the index of the subpath with the minimum energy efficiency in P∗. ∗/
(9)pk←maxbenefit(Pm);  /∗  pk is the subpath with the maximum benefit in Pm. ∗/
(10)pm∗←pk;
(11)Pm←Pm\pk;
(12)end while
(13)end if
(14)end for


### 5.1.2. The Lower Bound of the Subgraph

LetP∗={p1∗,p2∗,…,ps∗} be the solution of GS-BC, pi∗ be the selected subpath in subgraph Gi, and bi∗ be the benefit of subpath pi∗; then we define the lower bound of a subgraph as (28)Lk=fl∑i=1kbi∗∑i=1sbi∗∗∑i=1kbi∗,1≤k≤s,where fl(x) is the discount function that represents the relation between the lower bound of a subgraph and the lower bound of the problem. fl(x) is obtained by the statistical method; for details, refer to Section 6.2.2.


## 5.1.1. The Lower Bound of the Problem

We design a two-phase hierarchical algorithm (called GS-BC) to find the lower bound of the problem. Before discussing the algorithm, the concept it used is given as follows.Definition 7 (energy efficiency).
(27)
η
p
i
j
=
Δ
e
e
n
d
i
j
′
-
max
⁡
Δ
e
e
n
d
i
k
′
∣
p
i
k
∈
P
i
b
i
j
′
+
ε
,where η(pij) is the energy efficiency of subpath pij and ε is the smallest constant in the computer used to avoid zero-division error.The energy efficiency represents the amount of energy consumed per unit of benefit and satisfiesη(pij)≤0.In the first phase of GS-BC, the observation tasks are planned by the energy efficiency based greedy search algorithm (GS, as is shown in Algorithm1). This algorithm selects a subpath from each subgraph one by one until reaching the end. When it searches a subgraph, the subpath with the maximum benefit is added to the solution. If the energy constraint is violated, then the subpath with the minimum energy efficiency in the solution is replaced by another subpath (it is not searched and has the maximum benefit) until the conflict is removed. In the second phase of GS-BC, the branch and cut algorithm (BC) [7] is used to schedule the transmission tasks based on the selected observation tasks in the first phase.Algorithm 1:Energy efficiency based greedy search algorithm.
Input: graph G={G1,…,Gs}.
Output: solution P∗={p1∗,…,ps∗}  /∗  pi∗ is the selected subpath in Gi. ∗/
(1)∀i∈[1,s], pi∗←null;
(2)for all  Gi∈G  do
(3)pj←maxbenefit(Pi);  /∗  pj is the subpath with the maximum benefit in Pi. ∗/
(4)pi∗←pj;
(5)Pi←Pi\pj;
(6)if  isconflict(P∗)   then  /∗ whether the energy constraint is violated. ∗/.
(7)while  isconflict(P∗)   do
(8)m←repairid(P∗);  /∗  m is the index of the subpath with the minimum energy efficiency in P∗. ∗/
(9)pk←maxbenefit(Pm);  /∗  pk is the subpath with the maximum benefit in Pm. ∗/
(10)pm∗←pk;
(11)Pm←Pm\pk;
(12)end while
(13)end if
(14)end for


## 5.1.2. The Lower Bound of the Subgraph

LetP∗={p1∗,p2∗,…,ps∗} be the solution of GS-BC, pi∗ be the selected subpath in subgraph Gi, and bi∗ be the benefit of subpath pi∗; then we define the lower bound of a subgraph as (28)Lk=fl∑i=1kbi∗∑i=1sbi∗∗∑i=1kbi∗,1≤k≤s,where fl(x) is the discount function that represents the relation between the lower bound of a subgraph and the lower bound of the problem. fl(x) is obtained by the statistical method; for details, refer to Section 6.2.2.


## 5.2. The Improved Label-Setting Algorithm

After the lower bound of each subgraph is computed, the improved label-setting algorithm with the lower bound cutting strategy is used to find the near-optimal solution of the problem. This algorithm incrementally searches the nondominated paths from the first subgraph to the last subgraph one by one until reaching the end. When it searches a subgraph, the low-benefit paths are removed by the lower bound cutting strategy, and the dominated paths are discarded based on the dominance relation (see Definition6) that avoids exploring the whole paths in the solution space. For details, refer to Algorithm 2.Algorithm 2:Improved label-setting algorithm.
Input: graph G={G1,…,Gs}.
Output: the optimal path qs∗
(1)for  i=2,…,s  do
(2)for all  pi∈Pi  do  /∗  Pi is set of subpaths in subgraph Gi. ∗/
(3)for allqi-1∈Qi-1  do  /∗  Qi-1 is set of paths in subgraph Gi-1. ∗/
(4)if  notconflict(qi-1,pi)  then /∗  pi must satisfy the constraint when adding it to qi-1. ∗/
(5)qi←append(qi-1,pi); /∗  add pi to qi-1. ∗/
(6)Qi←Qi∪qi;
(7)end if
(8)end for
(9)Li←getlowerbound(); /∗  Li is the lower bound of subgraph Gi. ∗/
(10)for  j=1,…,num(Qi)   do  /∗  num(Qi) is the number of paths in Qi. ∗/
(11)if  bj<L(i)   then  /∗  the total benefit must greater than the lower bound. ∗/
(12)Qi←Qi\qj;
(13)end if
(14)end for
(15)forj=1,…,num(Qi)  do
(16)for  k=j+1,…,num(Qi)  do
(17)if  qj≲qk  then
(18)Qi←Qi\qj;
(19)      break;
(20)else if  qj≳qk  then
(21)Qi←Qi\qk;
(22)end if
(23)end for
(24)end for
(25)end for
(26)end for
(27)qs∗←maxbenefit(Qs); /∗  qs∗ is the path with the maximum benefit in Qs. ∗/


## 6. Computational Experiments

### 6.1. Test Data

In the experiment, there are one satellite and four ground stations [25] (Kashi, Miyun, Sanya, and Beiji). The EOS is selected from the STK (Satellite Tool Kit) satellite database. The planning horizon is set as a typical 1 day from 2017-04-01 00:00:00 to 2017-04-02 00:00:00.There is no acknowledged benchmark data set in the single-satellite observation and transmission tasks planning problem, so we randomly generate three data sets: regional city data set, global city data set, and global point data set. Cities in the regional city data set and global city data set are selected from the STK city database. In the regional city data set, all targets are randomly distributed in the area: 0°N~65°N and 0°E~150°E. In the global city data set and global point data set, all targets are randomly distributed in the area: −65°S~65°N and −180°W~180°E. The access times between the EOS and the ground station or the EOS and the target are calculated by STK. Each access time is corresponding to a task.There are nine problem sets in each data set. Each problem set contains ten problems (i.e., a total of 90 problems in each data set). The number of observation tasks in each problem set is from 100 to 500 with step of 50.All algorithms in the experiment are implemented and compiled with Microsoft C# complier and run on Windows 7 OS with an Intel E5-2650 2.30 GHz CPU and 8 GB memory.


### 6.2. Parameter Study

#### 6.2.1. The Effect of the Relaxation Factors

To investigate the effect of the three relaxation factors in our method, we conduct several experiments based on the global city data set.Figures7 and 8 show the result of LS under single relaxation factor. The horizontal axis represents the number of observation tasks, the vertical axis represents the average benefit or average CPU time, and the legend “α=0.001” means the relaxation factor of benefit is 0.001 and the other two relaxation factors are set as zero.Figure 7
The average benefit of LS under single relaxation factor.
(a)
(b)
(c)Figure 8
The average CPU time of LS under single relaxation factor.
(a)
(b)
(c)In Figure7, the average benefit falls with the increase of each relaxation factor. In Figure 7(a), the average benefit is drastically reduced when α is greater than 0.002. It reveals that LS is sensitive to the relaxation factor of benefit. In Figures 7(b) and 7(c), the gap of benefit is pretty narrow when β or γ is less than 0.01.In Figure8, the average CPU time apparently decreases with the increase of each relaxation factor. It illustrates that these relaxation factors have a significant effect on the CPU time.Based on the above analysis, we primarily investigate three combinations of them:{“0.001-0.005-0.005”, “0.002-0.005-0.005”, “0.02-0.01-0.01”. The parameters in a combination represent the relaxation factor of benefit, energy, and memory, respectively. The result is shown in Figures 9 and 10.Figure 9
The average benefit of LS under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setFigure 10
The average CPU time of LS under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setIn Figure9, the average benefit of “0.001-0.005-0.005” is slightly more than “0.002-0.005-0.005” and the worst is “0.002-0.01-0.01,” and the maximum gap between them is less than 0.3%.In Figure10, the average CPU time of “0.001-0.005-0.005” is more than “0.002-0.005-0.005” and “0.02-0.01-0.01.” The larger the relaxation factors, the more paths removed and the less CPU time.


#### 6.2.2. The Effect of the Lower Bound Cutting Strategy

We first describe the computation of the discount functionfl(x) mentioned in Section 5.1.2. Based on the amount of training data (the same size as the test data), we compute fl(x) by regression analysis. The process is as follows:(1)
Select one problem from the training data set.(2)
LetP′={p1′,p2′,…,ps′} (pi′ is the selected subpath in subgraph Gi) be the solution of CPLEX solver (used as the optimal solution) and P∗={p1∗,p2∗,…,ps∗} be the solution of GS-BC (used as the estimate solution). The relational data (xk,yk), k∈[1,s], is recorded. (29)xk,yk=∑i=1kbi∗∑i=1sbi∗,∑i=1kbi′∑i=1sbi∗,where bi∗ and bi′ are the benefit of subpaths pi∗ and pi′, respectively. The relational data describes the relation between the estimate solution and optimal solution at a subgraph.(3)
Return to (1) until all problems are solved.(4)
Compute the regression curve of the lower boundary of the relational data.Figure11 shows the distribution of the relational data and the approximate regression curve of the lower boundary, where the blue point is the relational data, the mauve point is the lower boundary, and the red line is fl(x). In fact, a piecewise function is used as the approximate expression of fl(x) and confirmed to be effective.Figure 11
The distribution of the relational data (xk,yk).Next, we analyze the effect of the lower bound cutting strategy in LSLBC. The average CPU time is shown in Figure12. The average benefit is almost the same as Figure 9 that it is not shown here.Figure 12
The average CPU time of LSLBC under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setComparing Figures10 and 12, the CPU time is greatly reduced by using the lower bound cutting strategy. It is because the strategy removes a large number of low-benefit paths during searching.Through the above analysis, we finally selectα=0.002, β=0.005, and γ=0.005 (e.g., the combination “0.002-0.005-0.005”) as the parameters of LSLBC.


### 6.3. Comparison Study

Three algorithms including the improved genetic algorithm (IGA) with a stochastic greedy conflict repairing strategy [5], the hierarchical algorithm [7] (called GA-BC), and the CPLEX solver [31] are used as baselines for comparison in this subsection. The stochastic greedy conflict repairing strategy in the IGA is slightly modified to meet the needs of our problem. In the repairing strategy, the observation task with the lowest benefit is removed when the solution violates constraints (6) and (7) until all conflicts are resolved. In the hierarchical algorithm, the observation tasks are firstly planned by the genetic algorithm [3]; then the transmission tasks are scheduled by the branch and cut algorithm [7] based on the selected observation tasks in the previous stage.The parameters of genetic algorithm in IGA and GA-BC are set as follows: the population size is 50, the crossover probability is 0.8, the mutation probability is 0.008, and the iterative number is 10000. If the solution is not improved in 500 iterations, then the algorithm stops. In CPLEX solver, the gap is set as 0.01, the stop time is set as 5 hours, and other parameters are executed in the default settings. All experiments are repeated 50 times. The following information is recorded; note that these statistics are computed only considering the problems that are solved by all algorithms.(i)
ave.b: the average benefit of an algorithm in a problem set. For example, the average benefit of LSLBC in a problem set is calculated as 1/10∑k=110bk(LSLBC), where bk(LSLBC) is the (average) benefit of LSLBC on the kth problem in the problem set.(ii)
ave.t: the average CPU time of an algorithm in a problem set, measured in seconds. For example, the average CPU time of LSLBC in a problem set is calculated as 1/10∑k=110tk(LSLBC), where tk(LSLBC) is the (average) CPU time of LSLBC on the kth problem in the problem set.(iii)
ave.g: the average benefit gap between an algorithm and the CPLEX solver. For example, the average benefit error of LSLBC in a problem set is calculated as 1/10∑k=110(bkCPLEX-bkLSLBC/bkCPLEX).Computational results on three data sets are given in Tables1, 2, and 3.Table 1
The computational result on the regional city data set.
Observation tasks
Problems
CPLEX
LSLBC
IGA
GA-BC
ave.b
ave.t
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
100
10
1501
26.21
1490
0.067
0.70%
1484
3.777
1.09%
1493
3.654
0.56%
150
10
1902
80
1891
0.175
0.62%
1869
7.11
1.73%
1875
7.873
1.42%
200
10
2168
192
2156
0.598
0.55%
2126
10.51
1.91%
2136
11.34
1.46%
250
10
2350
416
2341
1.256
0.37%
2302
12.97
2.02%
2299
15.42
2.17%
300
10
2522
700
2510
2.454
0.46%
2473
16.02
1.95%
2475
17.22
1.87%
350
10
2685
1134
2666
2.987
0.72%
2627
18.66
2.17%
2629
21.10
2.09%
400
10
2810
2205
2794
4.106
0.59%
2744
20.86
2.34%
2748
26.26
2.21%
450
10
2900
3634
2881
4.755
0.67%
2839
23.75
2.11%
2845
28.74
1.91%
500
10
3010
4433
2990
5.603
0.68%
2941
26.04
2.30%
2944
32.46
2.22%Table 2
The computational result on the global city data set.
Observation tasks
Problems
CPLEX
LSLBC
IGA
GA-BC
ave.b
ave.t
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
100
10
1680
37.92
1669
0.110
0.64%
1661
4.699
1.08%
1668
5.203
0.69%
150
10
2090
132
2080
0.422
0.48%
2041
8.278
2.31%
2076
9.542
0.65%
200
10
2384
371
2377
1.519
0.30%
2314
12.56
2.92%
2361
14.66
0.96%
250
10
2644
722
2636
3.605
0.30%
2570
16.69
2.79%
2619
19.45
0.95%
300
10
2843
1390
2838
6.751
0.16%
2759
21.44
2.97%
2812
24.43
1.09%
350
10
3023
2082
3015
7.846
0.24%
2923
24.98
3.31%
2991
30.34
1.04%
400
10
3193
3956
3183
10.48
0.32%
3088
29.58
3.29%
3154
33.23
1.21%
450
10
3350
7146
3334
12.34
0.49%
3227
33.97
3.69%
3303
40.00
1.43%
500
10
3496
7207
3482
11.98
0.39%
3354
38.54
4.06%
3445
42.26
1.44%Table 3
The computational result on the global point data set.
Observation tasks
Problems
CPLEX
LSLBC
IGA
GA-BC
ave.b
ave.t
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
100
10
1785
28.98
1778
0.124
0.36%
1765
5.779
1.11%
1784
6.559
0.02%
150
10
2246
117
2243
1.039
0.16%
2206
11.87
1.80%
2240
14.95
0.26%
200
10
2532
341
2532
3.893
0
2471
17.26
2.42%
2522
23.96
0.40%
250
10
2768
671
2768
9.349
0.02%
2704
22.91
2.34%
2752
31.80
0.59%
300
10
2949
1441
2944
15.84
0.15%
2871
28.38
2.66%
2932
41.77
0.59%
350
10
3118
3217
3113
26.95
0.16%
3037
34.75
2.59%
3096
48.86
0.67%
400
10
3268
7086
3266
35.25
0.08%
3187
42.05
2.50%
3250
60.00
0.57%
450
10
3415
6873
3406
34.33
0.28%
3318
48.71
2.85%
3385
67.14
0.87%
500
10(5)1
3475
11471
3478
41.30
−0.08%2
3381
56.89
2.70%
3449
74.34
0.74%
There
1 are 5 problems unsolved by CPLEX; 2LSLBC is better than CPLEX in some problems.In Tables1, 2, and 3, the benefit of LSLBC is better than IGA and GA-BC, except in a few problems that the number of observation tasks is 100 in the regional city data set and the global point data set. The average CPU times of LSLBC are all less than IGA and GA-BC in the above three data sets. This is because the two preprocessing strategies and the lower bounding cutting strategy in LSLBC remove a large number of redundant paths (the nondominated paths and the low-benefit paths). Though the IGA have a strong global search capability, the local search capability is weak. Besides, the stochastic greedy repair strategy does not consider the correlation between the observation tasks and the transmission tasks in resource consumption and acquisition. The GA-BC breaks up the optimal solution of the observation tasks during scheduling the transmission tasks.Tables1, 2, and 3 show that the average benefit gap of LSLBC is from −0.08% to 0.72% in three data sets. As the number of observation tasks increases, the number of edges in the graph model grows dramatically. The CPLEX solver has to take longer in the preprocessing, which even makes five problems unsolved (in Table 3). In the experiment, the gap of CPLEX solver is 1% which means the solution is not optimal. The LBLSC is an appropriate algorithm that it may be better than CPLEX solver in some problems when the relaxation factors are small, for example, some problems in the global point data set when the number of observation tasks is 200, 250, and 500 (in Table 3). Though the CPLEX solver can find a better solution for most problems, the CPU time is too long that it is difficult to meet the real requirement. The result verifies the ability of LSLBC to solve the SOTTP.When comparing Tables1, 2, and 3, we can know that the benefit gap of LSLBC in the global point data set is the least, the next is in the global city data set, and the largest is in the regional city data set. This reveals that our LSLBC has better performance on decentralized targets.


## 6.1. Test Data

In the experiment, there are one satellite and four ground stations [25] (Kashi, Miyun, Sanya, and Beiji). The EOS is selected from the STK (Satellite Tool Kit) satellite database. The planning horizon is set as a typical 1 day from 2017-04-01 00:00:00 to 2017-04-02 00:00:00.There is no acknowledged benchmark data set in the single-satellite observation and transmission tasks planning problem, so we randomly generate three data sets: regional city data set, global city data set, and global point data set. Cities in the regional city data set and global city data set are selected from the STK city database. In the regional city data set, all targets are randomly distributed in the area: 0°N~65°N and 0°E~150°E. In the global city data set and global point data set, all targets are randomly distributed in the area: −65°S~65°N and −180°W~180°E. The access times between the EOS and the ground station or the EOS and the target are calculated by STK. Each access time is corresponding to a task.There are nine problem sets in each data set. Each problem set contains ten problems (i.e., a total of 90 problems in each data set). The number of observation tasks in each problem set is from 100 to 500 with step of 50.All algorithms in the experiment are implemented and compiled with Microsoft C# complier and run on Windows 7 OS with an Intel E5-2650 2.30 GHz CPU and 8 GB memory.


## 6.2. Parameter Study

### 6.2.1. The Effect of the Relaxation Factors

To investigate the effect of the three relaxation factors in our method, we conduct several experiments based on the global city data set.Figures7 and 8 show the result of LS under single relaxation factor. The horizontal axis represents the number of observation tasks, the vertical axis represents the average benefit or average CPU time, and the legend “α=0.001” means the relaxation factor of benefit is 0.001 and the other two relaxation factors are set as zero.Figure 7
The average benefit of LS under single relaxation factor.
(a)
(b)
(c)Figure 8
The average CPU time of LS under single relaxation factor.
(a)
(b)
(c)In Figure7, the average benefit falls with the increase of each relaxation factor. In Figure 7(a), the average benefit is drastically reduced when α is greater than 0.002. It reveals that LS is sensitive to the relaxation factor of benefit. In Figures 7(b) and 7(c), the gap of benefit is pretty narrow when β or γ is less than 0.01.In Figure8, the average CPU time apparently decreases with the increase of each relaxation factor. It illustrates that these relaxation factors have a significant effect on the CPU time.Based on the above analysis, we primarily investigate three combinations of them:{“0.001-0.005-0.005”, “0.002-0.005-0.005”, “0.02-0.01-0.01”. The parameters in a combination represent the relaxation factor of benefit, energy, and memory, respectively. The result is shown in Figures 9 and 10.Figure 9
The average benefit of LS under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setFigure 10
The average CPU time of LS under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setIn Figure9, the average benefit of “0.001-0.005-0.005” is slightly more than “0.002-0.005-0.005” and the worst is “0.002-0.01-0.01,” and the maximum gap between them is less than 0.3%.In Figure10, the average CPU time of “0.001-0.005-0.005” is more than “0.002-0.005-0.005” and “0.02-0.01-0.01.” The larger the relaxation factors, the more paths removed and the less CPU time.


### 6.2.2. The Effect of the Lower Bound Cutting Strategy

We first describe the computation of the discount functionfl(x) mentioned in Section 5.1.2. Based on the amount of training data (the same size as the test data), we compute fl(x) by regression analysis. The process is as follows:(1)
Select one problem from the training data set.(2)
LetP′={p1′,p2′,…,ps′} (pi′ is the selected subpath in subgraph Gi) be the solution of CPLEX solver (used as the optimal solution) and P∗={p1∗,p2∗,…,ps∗} be the solution of GS-BC (used as the estimate solution). The relational data (xk,yk), k∈[1,s], is recorded. (29)xk,yk=∑i=1kbi∗∑i=1sbi∗,∑i=1kbi′∑i=1sbi∗,where bi∗ and bi′ are the benefit of subpaths pi∗ and pi′, respectively. The relational data describes the relation between the estimate solution and optimal solution at a subgraph.(3)
Return to (1) until all problems are solved.(4)
Compute the regression curve of the lower boundary of the relational data.Figure11 shows the distribution of the relational data and the approximate regression curve of the lower boundary, where the blue point is the relational data, the mauve point is the lower boundary, and the red line is fl(x). In fact, a piecewise function is used as the approximate expression of fl(x) and confirmed to be effective.Figure 11
The distribution of the relational data (xk,yk).Next, we analyze the effect of the lower bound cutting strategy in LSLBC. The average CPU time is shown in Figure12. The average benefit is almost the same as Figure 9 that it is not shown here.Figure 12
The average CPU time of LSLBC under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setComparing Figures10 and 12, the CPU time is greatly reduced by using the lower bound cutting strategy. It is because the strategy removes a large number of low-benefit paths during searching.Through the above analysis, we finally selectα=0.002, β=0.005, and γ=0.005 (e.g., the combination “0.002-0.005-0.005”) as the parameters of LSLBC.


## 6.2.1. The Effect of the Relaxation Factors

To investigate the effect of the three relaxation factors in our method, we conduct several experiments based on the global city data set.Figures7 and 8 show the result of LS under single relaxation factor. The horizontal axis represents the number of observation tasks, the vertical axis represents the average benefit or average CPU time, and the legend “α=0.001” means the relaxation factor of benefit is 0.001 and the other two relaxation factors are set as zero.Figure 7
The average benefit of LS under single relaxation factor.
(a)
(b)
(c)Figure 8
The average CPU time of LS under single relaxation factor.
(a)
(b)
(c)In Figure7, the average benefit falls with the increase of each relaxation factor. In Figure 7(a), the average benefit is drastically reduced when α is greater than 0.002. It reveals that LS is sensitive to the relaxation factor of benefit. In Figures 7(b) and 7(c), the gap of benefit is pretty narrow when β or γ is less than 0.01.In Figure8, the average CPU time apparently decreases with the increase of each relaxation factor. It illustrates that these relaxation factors have a significant effect on the CPU time.Based on the above analysis, we primarily investigate three combinations of them:{“0.001-0.005-0.005”, “0.002-0.005-0.005”, “0.02-0.01-0.01”. The parameters in a combination represent the relaxation factor of benefit, energy, and memory, respectively. The result is shown in Figures 9 and 10.Figure 9
The average benefit of LS under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setFigure 10
The average CPU time of LS under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setIn Figure9, the average benefit of “0.001-0.005-0.005” is slightly more than “0.002-0.005-0.005” and the worst is “0.002-0.01-0.01,” and the maximum gap between them is less than 0.3%.In Figure10, the average CPU time of “0.001-0.005-0.005” is more than “0.002-0.005-0.005” and “0.02-0.01-0.01.” The larger the relaxation factors, the more paths removed and the less CPU time.


## 6.2.2. The Effect of the Lower Bound Cutting Strategy

We first describe the computation of the discount functionfl(x) mentioned in Section 5.1.2. Based on the amount of training data (the same size as the test data), we compute fl(x) by regression analysis. The process is as follows:(1)
Select one problem from the training data set.(2)
LetP′={p1′,p2′,…,ps′} (pi′ is the selected subpath in subgraph Gi) be the solution of CPLEX solver (used as the optimal solution) and P∗={p1∗,p2∗,…,ps∗} be the solution of GS-BC (used as the estimate solution). The relational data (xk,yk), k∈[1,s], is recorded. (29)xk,yk=∑i=1kbi∗∑i=1sbi∗,∑i=1kbi′∑i=1sbi∗,where bi∗ and bi′ are the benefit of subpaths pi∗ and pi′, respectively. The relational data describes the relation between the estimate solution and optimal solution at a subgraph.(3)
Return to (1) until all problems are solved.(4)
Compute the regression curve of the lower boundary of the relational data.Figure11 shows the distribution of the relational data and the approximate regression curve of the lower boundary, where the blue point is the relational data, the mauve point is the lower boundary, and the red line is fl(x). In fact, a piecewise function is used as the approximate expression of fl(x) and confirmed to be effective.Figure 11
The distribution of the relational data (xk,yk).Next, we analyze the effect of the lower bound cutting strategy in LSLBC. The average CPU time is shown in Figure12. The average benefit is almost the same as Figure 9 that it is not shown here.Figure 12
The average CPU time of LSLBC under the combinations of relaxation factors.
(a)
Regional city data set
(b)
Global city data set
(c)
Global point data setComparing Figures10 and 12, the CPU time is greatly reduced by using the lower bound cutting strategy. It is because the strategy removes a large number of low-benefit paths during searching.Through the above analysis, we finally selectα=0.002, β=0.005, and γ=0.005 (e.g., the combination “0.002-0.005-0.005”) as the parameters of LSLBC.


## 6.3. Comparison Study

Three algorithms including the improved genetic algorithm (IGA) with a stochastic greedy conflict repairing strategy [5], the hierarchical algorithm [7] (called GA-BC), and the CPLEX solver [31] are used as baselines for comparison in this subsection. The stochastic greedy conflict repairing strategy in the IGA is slightly modified to meet the needs of our problem. In the repairing strategy, the observation task with the lowest benefit is removed when the solution violates constraints (6) and (7) until all conflicts are resolved. In the hierarchical algorithm, the observation tasks are firstly planned by the genetic algorithm [3]; then the transmission tasks are scheduled by the branch and cut algorithm [7] based on the selected observation tasks in the previous stage.The parameters of genetic algorithm in IGA and GA-BC are set as follows: the population size is 50, the crossover probability is 0.8, the mutation probability is 0.008, and the iterative number is 10000. If the solution is not improved in 500 iterations, then the algorithm stops. In CPLEX solver, the gap is set as 0.01, the stop time is set as 5 hours, and other parameters are executed in the default settings. All experiments are repeated 50 times. The following information is recorded; note that these statistics are computed only considering the problems that are solved by all algorithms.(i)
ave.b: the average benefit of an algorithm in a problem set. For example, the average benefit of LSLBC in a problem set is calculated as 1/10∑k=110bk(LSLBC), where bk(LSLBC) is the (average) benefit of LSLBC on the kth problem in the problem set.(ii)
ave.t: the average CPU time of an algorithm in a problem set, measured in seconds. For example, the average CPU time of LSLBC in a problem set is calculated as 1/10∑k=110tk(LSLBC), where tk(LSLBC) is the (average) CPU time of LSLBC on the kth problem in the problem set.(iii)
ave.g: the average benefit gap between an algorithm and the CPLEX solver. For example, the average benefit error of LSLBC in a problem set is calculated as 1/10∑k=110(bkCPLEX-bkLSLBC/bkCPLEX).Computational results on three data sets are given in Tables1, 2, and 3.Table 1
The computational result on the regional city data set.
Observation tasks
Problems
CPLEX
LSLBC
IGA
GA-BC
ave.b
ave.t
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
100
10
1501
26.21
1490
0.067
0.70%
1484
3.777
1.09%
1493
3.654
0.56%
150
10
1902
80
1891
0.175
0.62%
1869
7.11
1.73%
1875
7.873
1.42%
200
10
2168
192
2156
0.598
0.55%
2126
10.51
1.91%
2136
11.34
1.46%
250
10
2350
416
2341
1.256
0.37%
2302
12.97
2.02%
2299
15.42
2.17%
300
10
2522
700
2510
2.454
0.46%
2473
16.02
1.95%
2475
17.22
1.87%
350
10
2685
1134
2666
2.987
0.72%
2627
18.66
2.17%
2629
21.10
2.09%
400
10
2810
2205
2794
4.106
0.59%
2744
20.86
2.34%
2748
26.26
2.21%
450
10
2900
3634
2881
4.755
0.67%
2839
23.75
2.11%
2845
28.74
1.91%
500
10
3010
4433
2990
5.603
0.68%
2941
26.04
2.30%
2944
32.46
2.22%Table 2
The computational result on the global city data set.
Observation tasks
Problems
CPLEX
LSLBC
IGA
GA-BC
ave.b
ave.t
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
100
10
1680
37.92
1669
0.110
0.64%
1661
4.699
1.08%
1668
5.203
0.69%
150
10
2090
132
2080
0.422
0.48%
2041
8.278
2.31%
2076
9.542
0.65%
200
10
2384
371
2377
1.519
0.30%
2314
12.56
2.92%
2361
14.66
0.96%
250
10
2644
722
2636
3.605
0.30%
2570
16.69
2.79%
2619
19.45
0.95%
300
10
2843
1390
2838
6.751
0.16%
2759
21.44
2.97%
2812
24.43
1.09%
350
10
3023
2082
3015
7.846
0.24%
2923
24.98
3.31%
2991
30.34
1.04%
400
10
3193
3956
3183
10.48
0.32%
3088
29.58
3.29%
3154
33.23
1.21%
450
10
3350
7146
3334
12.34
0.49%
3227
33.97
3.69%
3303
40.00
1.43%
500
10
3496
7207
3482
11.98
0.39%
3354
38.54
4.06%
3445
42.26
1.44%Table 3
The computational result on the global point data set.
Observation tasks
Problems
CPLEX
LSLBC
IGA
GA-BC
ave.b
ave.t
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
ave.b
ave.t
ave.g
100
10
1785
28.98
1778
0.124
0.36%
1765
5.779
1.11%
1784
6.559
0.02%
150
10
2246
117
2243
1.039
0.16%
2206
11.87
1.80%
2240
14.95
0.26%
200
10
2532
341
2532
3.893
0
2471
17.26
2.42%
2522
23.96
0.40%
250
10
2768
671
2768
9.349
0.02%
2704
22.91
2.34%
2752
31.80
0.59%
300
10
2949
1441
2944
15.84
0.15%
2871
28.38
2.66%
2932
41.77
0.59%
350
10
3118
3217
3113
26.95
0.16%
3037
34.75
2.59%
3096
48.86
0.67%
400
10
3268
7086
3266
35.25
0.08%
3187
42.05
2.50%
3250
60.00
0.57%
450
10
3415
6873
3406
34.33
0.28%
3318
48.71
2.85%
3385
67.14
0.87%
500
10(5)1
3475
11471
3478
41.30
−0.08%2
3381
56.89
2.70%
3449
74.34
0.74%
There
1 are 5 problems unsolved by CPLEX; 2LSLBC is better than CPLEX in some problems.In Tables1, 2, and 3, the benefit of LSLBC is better than IGA and GA-BC, except in a few problems that the number of observation tasks is 100 in the regional city data set and the global point data set. The average CPU times of LSLBC are all less than IGA and GA-BC in the above three data sets. This is because the two preprocessing strategies and the lower bounding cutting strategy in LSLBC remove a large number of redundant paths (the nondominated paths and the low-benefit paths). Though the IGA have a strong global search capability, the local search capability is weak. Besides, the stochastic greedy repair strategy does not consider the correlation between the observation tasks and the transmission tasks in resource consumption and acquisition. The GA-BC breaks up the optimal solution of the observation tasks during scheduling the transmission tasks.Tables1, 2, and 3 show that the average benefit gap of LSLBC is from −0.08% to 0.72% in three data sets. As the number of observation tasks increases, the number of edges in the graph model grows dramatically. The CPLEX solver has to take longer in the preprocessing, which even makes five problems unsolved (in Table 3). In the experiment, the gap of CPLEX solver is 1% which means the solution is not optimal. The LBLSC is an appropriate algorithm that it may be better than CPLEX solver in some problems when the relaxation factors are small, for example, some problems in the global point data set when the number of observation tasks is 200, 250, and 500 (in Table 3). Though the CPLEX solver can find a better solution for most problems, the CPU time is too long that it is difficult to meet the real requirement. The result verifies the ability of LSLBC to solve the SOTTP.When comparing Tables1, 2, and 3, we can know that the benefit gap of LSLBC in the global point data set is the least, the next is in the global city data set, and the largest is in the regional city data set. This reveals that our LSLBC has better performance on decentralized targets.


## 7. Conclusion

In this paper, we study the single-satellite observation and transmission tasks planning problem under a more accurate resource usage model. Two preprocessing strategies including graph partition and nondominated subpaths selection are used to decompose the problem, and an improved label-setting algorithm with the lower bound cutting strategy is used to solve the problem, which avoids exploring the whole nondominated path set and accelerates the solving procedure. The optimality and feasibility of the proposed method are validated on three data sets, totaling 270 problems. The results demonstrate that our method can find the near-optimal solution in much less time and indicate the ability of our method to solve the SOTTP under different task size.The future work of our study is mainly focused on two aspects: (1) extending our approach to the scheduling of an agile satellite, which not only selects the tasks to be performed, but also determines the start time of them; (2) extending our approach to the onboard task planning problem for an autonomous satellite. The onboard dynamic situations are considered, such as the arrival of new tasks and cloud disturbances.



---

*Source: 7304506-2017-12-27.xml*