03964.com

文档资料库 文档搜索专家

文档资料库 文档搜索专家

AAS 07-150

A GREEDY RANDOM ADAPTIVE SEARCH PROCEDURE FOR OPTIMAL SCHEDULING OF P2P SATELLITE REFUELING

Atri Dutta? and Panagiotis Tsiotras?

Abstract All studies of peer-to-peer (henceforth abbreviated as P2P) satellite refueling so far assume that all active satellites return back to their original orbital positions after undergoing fuel exchanges with the passive satellites. In this paper, we remove this restriction on the active satellites, namely, we allow the active satellites to interchange orbital slots during the return trips. We formulate the problem as a three-index assignment problem in a tripartite constellation graph. We use a greedy random adaptive search procedure (GRASP) to determine the optimal P2P refueling schedule between the active and the passive satellites. It is shown that the proposed methodology leads to considerable fuel reduction over the baseline P2P refueling strategy.

INTRODUCTION

The lifespan of satellite constellations can be extended by periodic refueling of the satellites in the constellation. The traditional approach for satellite refueling involves a single service vehicle refueling all fuel-de?cient satellites in the constellation in a sequential manner. Several studies have been performed on the problem of servicing multiple satellites in a constellation.1 Recently, an alternative scenario for distributing fuel amongst a large number of satellites has been proposed.2, 3 In this scenario, no single spacecraft is in charge of the whole refueling process. Instead, all satellites share the responsibility of refueling each other on an equal footing. We call this the peer-to-peer (P2P) refueling strategy.3 Studies have also been performed on mixed refueling strategies, in which the P2P refueling is an integral component.4, 5 It has been shown that a mixed refueling strategy is a competitive alternative to the single service vehicle refueling strategy, outperforming the latter for a large number of satellites in the constellation.4 Additional extensions, namely, the coasting time allocation strategy and the asynchronous P2P refueling strategy,5 have also been developed. These extensions result in considerable reduction of the fuel expenditure in mixed refueling scenarios. In all of the above-mentioned studies, P2P refueling was perceived as a means to equalize fuel in the constellation. In order to achieve fuel equalization in the constellation, an optimization problem was formulated, such that the deviation of each satellite’s fuel from the initial

Graduate student, D. Guggenheim School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0150. Email: gtg048j@mail.gatech.edu. ? Professor, D. Guggenheim School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0150. Tel: (404) 894-9526, Fax: (404) 894-2760, Email: tsiotras@gatech.edu.

?

1

average fuel in the constellation is penalized. Under such a formulation, the problem of ?nding optimal pairings of satellites reduces to a problem of ?nding the maximum weighted matching in the so-called constellation graph. This maximum matching problem can be solved using standard methods.6 A decentralized approach that uses auctions has also been reported in Ref 7. An alternative formulation for the P2P refueling problem is to impose a minimum fuel requirement for each satellite in the constellation in order to remain operational. Satellites having the required amount of fuel are fuel-su?cient, while those which do not have the required amount of fuel are fuel-de?cient. We therefore seek to determine the optimal pairings of satellites so that all satellites end up being fuel-su?cient at the end of the refueling process. This is to be achieved by using as little fuel as possible in the process. In all studies of P2P refueling so far, the active satellites have been constrained to return to their original positions. In this paper, we relax this constraint. Namely, we allow the active satellites to interchange their orbital positions in the constellation after the refueling of the passive satellites has been completed. When the active satellites are constrained to return to their original orbital positions, the problem of P2P refueling can be solved as a two-index assignment problem on a bipartite graph, between the fuel-su?cient and fuel-de?cient satellites. The assignment between the fuel-su?cient and fuel-de?cient satellites completely determines the P2P maneuvers. In the current formulation of the P2P refueling problem, this is not the case however. Since the active satellites are allowed to interchange orbital slots during their return trip, the assignment between fuel-su?cient satellites and fuel-de?cient satellites only determines the forward trip. We also need to assign each refueling transaction to an available orbital slot for the active satellite to return. We therefore need to consider three entities in order to completely de?ne a P2P maneuver. These entities are the fuel-su?cient satellite, the fuel-de?cient satellite, and the orbital slot the active satellite will return to. The P2P refueling problem can therefore be posed as a three-index assignment problem. It is known that the three-index assignment problem is NP-complete.8 The general multiindex assignment problem was ?rst stated by Pierskalla9 as an extension of the two-index assignment problem. The three dimensional assignment problem, which is a special case of the multi-index assignment problem, can be viewed as a matching problem on a complete tripartite graph. Several sub-optimal algorithms have been proposed for this problem. A branch-and-bound algorithm was proposed to solve the three-index assignment problem by Balas and Saltzman.10 Approximation algorithms for three-index assignment problems with triangle inequalities were addressed by Crama and Spieksma.11 For multi-index assignment problems in k -partite graphs with decomposable costs§ , Bandelt, Crama and Spieksma12 introduced two approximate algorithms, each of which solves a sequence of two-index assignment problems. Another class of algorithms that has been developed for solving the three-index assignment problem includes the Greedy Random Adaptive Search Procedure (GRASP).13–15 Feo and Resende13 discussed GRASP as a means for solving general combinatorial optimization problems. Robertson14 introduced four GRASP implementations for the multi-index assignment problem, which are combinations of two constructive methods (i.e., randomized reduced cost greedy, and randomized maximum maximum regret) and two local search methods (i.e.,

By decomposable costs, we mean that the cost of a clique in the k-partite graph is a function of the cost of the edges induced by the clique. Note that a clique is a subgraph in which all vertices are pairwise adjacent. For a k-partite graph, a clique comprises of exactly one node from each partition of the k-partite graph.

§

2

two-assignment exchange, and variable depth exchange). Aiex et al.15 proposed the use of GRASP with path relinking. This method was able to improve the quality of the heuristic solutions proposed in Refs. 10 and 12. Moreover, the GRASP method is shown to bene?t from parallelization. In this paper, we apply the GRASP method for solving the P2P refueling problem, under the assumption that the active satellites are allowed to interchange their orbital positions after they have refueled the passive satellites. However, since our problem deviates from the standard three-index assignment problem, we need to incorporate additional validation steps when we construct a basic feasible solution for an instance of our problem. These steps are explained in great detail later on in the section that discusses the three-index assignment problem.

PROBLEM FORMULATION

We consider a constellation with n satellites distributed over n orbital slots in a circular orbit. Let S = {si : i = 0, 1, 2, . . . , n} denote the set of satellites, where s0 represents a ?ctitious satellite, and let Φ = {φi ∈ [0, 2π ) : i = 1, 2, . . . , n, φi = φj } be the set of orbital slots. We introduce a mapping σt : Φ → S that, at time t, assigns to each orbital slot a satellite from S . Speci?cally, σt (φj ) = si implies that the satellite si occupies the orbital slot φj at time t. If the slot φj is empty at time t, we write σt (φj ) = s0 . We designate the constellation by the triplet C = {S , Φ, σt≥0 }. Let the fuel content of satellite si at time t be denoted by fi,t and let the minimum fuel content for satellite si in order to remain operational be denoted by f i . Finally, let the initial fuel content of satellite si be denoted by fi? , that is, fi? = fi,0 . Satellites having amount of fuel more than or equal to the amount required to remain operational are termed fuel-su?cient, while the ones having fuel less than the required amount are termed fuel-de?cient satellites. In a P2P refueling strategy, the fuel-su?cient and the fuel-de?cient satellites undergo fuel transactions amongst themselves, such that, at the end of refueling, each satellite has at least the required amount of fuel in order to remain operational. It will be convenient to keep track of the indices of the satellites participating in the refueling process under di?erent roles. To this end, let I = {1, 2, . . . , n}, and let Is,t = {i : fi,t ≥ f i } denote the index set of all fuel-su?cient satellites at time t, and let Id,t = {i : fi,t < f i } denote the index set of all fuel-de?cient satellites at time t. In a P2P refueling transaction between a fuel-su?cient and a fuel-de?cient satellite, one of them (henceforth referred to as the active satellite) performs an orbital transfer to rendezvous with the other satellite (henceforth referred to as the passive satellite). After a fuel exchange takes place between the active and the passive satellite, the active satellite returns to one of the available orbital slots. We will denote the index set of active satellites by Ia ? I and the index set of the passive satellites by Ip ? I . Our current problem formulation assumes that after refueling a passive satellite, each active satellite is allowed to return to any orbital slot that has been left vacant by another active satellite. For convenience, let Js,t = {j : σt (φj ) = si , i ∈ Is,t } denote the index set of orbital slots occupied by fuel-su?cient satellites at time t, let Jd,t = {j : σt (φj ) = si , i ∈ Id,t } denote the index set of orbital slots occupied by fuel-de?cient satellites at time t, and let Ja = {j : σ0 (φj ) = si , i ∈ Ia } denote the index set of orbital slots occupied by the active satellites before any orbital maneuver commences. We therefore de?ne a complete tripartite

3

constellation graph G consisting of three partitions. The ?rst partition consists of nodes that correspond to the elements of the index set Js,0 . The second partition consists of nodes that correspond to the elements of the index set Jd,0 , and the third partition consists of nodes that correspond to the elements of the index set Ja . Therefore, nodes of G are given by Js,0 ∪ Jd,0 ∪ Ja and the edges of G are all edges induced by triplets in Js,0 × Jd,0 × Ja , that is, G = {Js,0 ∪ Jd,0 ∪ Ja , Js,0 × Jd,0 × Ja }. Let us consider a triplet (i, j, k) ∈ Js,0 × Jd,0 × Ja . We say that the triplet (i, j, k) is feasible if the satellites σ0 (φi ) and σ0 (φj ) can engage in a feasible P2P refueling maneuver, that is, the active satellite (which can be either σ0 (φi ) or σ0 (φj )) rendezvous with the passive satellite, exchanges fuel, and then returns to the orbital slot initially occupied by the active satellite σ0 (φk ), such that both σ0 (φi ) and σ0 (φj ) end up being fuel-su?cient at the end of the process. Let T ? Js,0 × Jd,0 × Ja denote the set of all feasible triplets in the constellation graph G .

Maneuver Costs and Feasible Triplets

Let us consider a triplet (i, j, k) ∈ Js,0 × Jd,0 × Ja in the constellation graph G . Also, let the satellite s? occupy the orbital slot φi at time t = 0 and the satellite sν occupy the orbital slot φj at time t = 0. Hence, s? = σ0 (φi ) and sν = σ0 (φj ). Without loss of generality, assume s? to be a fuel-su?cient satellite and sν to be a fuel-de?cient satellite, that is, ? ∈ Is,0 and ν ∈ Id,0 . Either of the two satellites may be active during a refueling transaction between the two satellites. Hence, two di?erent P2P refueling transactions are possible for the triplet (i, j, k). In the ?rst case, the fuel-su?cient satellite is active, that is, the satellite s? performs the orbital maneuver to rendezvous with the passive satellite sν . Therefore, ? ∈ Ia ∩ Is,0 and ν ∈ Ip ∩ Id,0 . After a fuel exchange takes place between the two satellites, s? performs another orbital maneuver and moves to the orbital slot φk initially occupied by the active satellite σ0 (φk ). Note that k ∈ Ja and k = j . The fuel consumed by the active satellite s? to transfer from the orbital slot φi to the orbital slot φj is given by:

? p? ij = ms? + f?

1?e

?

?Vij c0?

,

(1)

where ms? is the mass of the permanent structure of satellite s? , and ?Vij is the optimal velocity change required for a two-impulse transfer from the orbital slot φi to the orbital slot φj . The parameter c0? is de?ned by c0? = g0 Isp? , where g0 is the acceleration due to gravity at the Earth’s surface and Isp? is the speci?c thrust of satellite s? . The fuel content of satellite ? ? p? . Since the fuel s? after its forward trip (but before fuel exchange takes place) is f? ij consumption during the maneuver is minimized if the active satellite returns with exactly the required minimum amount of fuel to remain operational, the amount of fuel consumed during the return trip, during which satellite s? travels from φj to φk , is given by p? jk = ms? + f ? e

?Vjk c0?

1?e

?

?Vjk c0?

,

(2)

where ?Vjk is the optimal velocity change required for the transfer from the orbital slot φj to the orbital slot φk . Before the return trip (but after the fuel exchange takes place), the fuel on board satellite s? is f ? + p? jk . The fuel transferred to satellite sν during the fuel ? ? ? exchange is (f? ? pij ) ? (f ? + pjk ), assuming that the satellite sν has enough fuel capacity 4

to accommodate this amount of fuel. The fuel on board satellite sν after it is refueled is ? + (f ? ? p? ) ? (f + p? ). In order for satellite s to become fuel-su?cient after the fuel fν ν ? ij jk ? transaction, we must therefore have,

? ? ? fν + f? ? f ? + f ν ≥ p? ij + pjk .

(3)

If the above condition does not hold, then the P2P refueling transaction between s? and sν is not feasible. Also, if satellite s? does not have enough fuel to carry out the orbital transfer ? during the forward trip, that is, if p? ij ≥ f? , then the P2P refueling transaction is also not feasible. Let c1 (i, j, k) denote the cost of a P2P maneuver for the case when the fuel-su?cient satellite is active. Then c1 (i, j, k) is given by the sum of (1) and (2). We therefore have, c1 (i, j, k) =

? ? ? ? ? ? ? p? ij + pjk , if pij < f? and pij + pjk ≤ f? + fν ? f ? + f ν ,

∞,

(4)

otherwise.

In the second case, the fuel-de?cient satellite is active, that is, satellite sν performs the orbital maneuver to rendezvous with the passive satellite s? . Therefore, ? ∈ Ip ∩ Is,0 and ν ∈ Ia ∩ Id,0 . After a fuel exchange takes place between the two satellites, sν performs another orbital maneuver and travels to the orbital slot φk initially occupied by the active satellite σ0 (φk ). Note that k ∈ Ja and k = i. The fuel consumed for the active satellite sν to transfer from the orbital slot φi to the orbital slot φj is given by

? pν ji = msν + fν

1?e

?

?Vji c0ν

,

(5)

where msν is the mass of the permanent structure of satellite sν , and ?Vji is the optimal velocity required for the transfer from the orbital slot φj to the orbital slot φi . The fuel ? ? pν . content of satellite sν after its forward trip (but before fuel exchange takes place), is fν ji The amount of fuel consumed during the return trip, during which the satellite sν travels from the orbital slot φi to the orbital slot φk , is given by pν ik = msν + f ν e

?Vik c0ν

1?e

?

?Vik c0ν

,

(6)

where ?Vik is the optimal velocity change required for the transfer from the orbital slot φi to the orbital slot φk . Before the return trip (but after the fuel exchange takes place), the fuel on board satellite sν is f ν + pν ik . The fuel transferred to satellite sν during the fuel ν ? ν exchange is (f ν + pik ) ? (fν ? pji ). The fuel on board satellite s? after the fuel transaction ? ? (f + pν ) + (f ? ? pν ). In order for the satellite s to be fuel-su?cient after the fuel is f? ? ν ji ik ν transaction, we must have

? ? ν f? ? f ν + f ? ≥ pν + fν ji + pik .

(7)

If the above condition does not hold, then a P2P refueling transaction between s? and sν is not feasible. Also, if the satellite sν does not have enough fuel to carry out the orbital transfer ? during the forward trip, that is, if pν ji ≥ fν , then the P2P refueling transaction is also not feasible. Let c2 (i, j, k) denote the cost of a P2P maneuver for the case when the fuel-de?cient satellite is active. Then, c2 (i, j, k) is given by the sum of (5) and (6). We therefore have, c2 (i, j, k) =

ν ν ? ν ν ? ? pν ji + pik , if pji < fν and pji + pik ≤ f? + fν ? f ν + f ?

∞,

(8)

otherwise. 5

Of the two possible P2P maneuvers associated with the triplet (i, j, k), the cheaper one is of interest to us. To this end, let the total fuel expenditure incurred in the P2P maneuver associated with the triplet (i, j, k) be given by c (i, j, k) = c1 (i, j, k) , if c1 (i, j, k) ≤ c2 (i, j, k) c2 (i, j, k) , otherwise. (9)

We therefore associate with each triplet (i, j, k) ∈ Js,0 × Jd,0 × Ja a single P2P maneuver. The set of all feasible triplets is then de?ned as T = {(i, j, k) ∈ Js,0 × Jd,0 × Ja : c (i, j, k) < ∞}. Let now Act : T → I be a function that returns the index of the orbital slot of the active satellite, that is, i, if c1 (i, j, k) ≤ c2 (i, j, k) Act (i, j, k) = (10) j, otherwise. Similarly, let Pas : T → I be a function that returns the index of the orbital slot of the passive satellite, that is, j, if c1 (i, j, k) ≤ c2 (i, j, k) Pas (i, j, k) = (11) i, otherwise. Moreover, the edges induced by the triplets that are not feasible can be removed from the graph G in order to yield a reduced constellation graph Gr . Therefore, Gr = {Js,0 ∪ Jd,0 ∪ Ja , T }. Henceforth, we restrict our discussion to the reduced constellation graph Gr . Using equations (1), (2), (5) and (6), we can ascertain the cost of a triplet (i, j, k) ∈ T using (9). Notice that the calculation of the optimal costs ?Vij , ?Vji , ?Vjk and ?Vki in Equations (1), (2), (5) and (6) requires, in general, the solution of the two-impulse multirevolution Lambert problem.16

The Three-Index Assignment Problem

Since our goal is to refuel all fuel-de?cient satellites, each of them should be part of a feasible fuel transaction. We therefore seek a set of exactly |Id,0 | feasible triplets M? ? T in the reduced constellation graph Gr such that none of the triplets in M? share a common vertex or a common edge, and such that the sum of the costs of all these triplets is minimum. To this end, let M ? T be a set that consists of |Id,0 | triplets. To each triplet (i, j, k) ∈ T we associate the binary variable xijk as follows xijk = 1, if (i, j, k) ∈ M, 0, otherwise. (12)

We can therefore formulate the problem of ?nding the set of feasible triplets M ? T that yield the minimum cost as follows c (i, j, k) xijk , (13) min

M?T (i,j,k)∈M

such that xijk ≤ 1, for all i ∈ Js,0 ,

j ∈Jd,0 k∈Ja

(14)

6

xijk = 1, for all j ∈ Jd,0 ,

i∈Js,0 k∈Ja

(15) (16) (17)

xijk ≤ 1, for all k ∈ Ja ,

i∈Js,0 j ∈Jd,0

r = Pas(i, j, k) for all (i, j, k) , (p, q, r) ∈ M.

Constraint (14) signi?es that not all fuel-su?cient satellites have to be part of P2P refueling transactions, because we may have |Is,0 | > |Id,0 |. Constraint (15) implies that each fuelde?cient satellite must be part of exactly one P2P fuel transaction. Constraint (16) signi?es that each of the slots left vacant by the active satellites needs to be assigned to a P2P refueling transaction. Note that the set of active satellites is not known a priori. We only know that Ja ? I . For solving our problem, we use Ja = I for the third partition of the constellation. Therefore, not all nodes of the third partition correspond to orbital slots of active satellites. Hence, the inequality sign in the constraint (16). Constraint (17) implies that the return orbital slot for the active satellite in a P2P maneuver cannot be the orbital slot of a passive satellite of a di?erent P2P maneuver. To illustrate this, let us consider two triplets (i, j, k) ∈ M and (p, q, r) ∈ M such that i = p, j = q , k = r. Without loss of generality, assume Act(i, j, k) = i and Act(p, q, r) = p. If r = j , then the fuel-su?cient satellite σ0 (φp ) initially occupying orbital slot φp returns to the orbital slot φj . However, the orbital slot φj is not vacant because the satellite σ0 (φj ) is passive and never leaves its slot. Constraint (17) avoids such infeasible cases. A set of triplets M ? T satisfying (12), (14)-(17) will be referred to as a basic feasible solution for our problem. It should be mentioned at this point that a few di?erences emerge between our problem and the standard three-index assignment problem (AP3) discussed in Refs. 9–12, 14, 15. First, the AP3 is a matching problem in a complete tripartite graph, whose partitions have the same number of nodes. In the case of the constellation graph G or the reduced constellation graph Gr , the three partitions do not have the same number of nodes. Secondly, in our problem, we have additional constraints given in (17), which need to be accounted for whenever a basic feasible solution is considered. Nonetheless, in our problem we can readily construct one basic feasible solution without solving a three-index assignment problem. This solution is obtained by solving the P2P refueling problem, while constraining the active satellites to return to their orbital slots after refueling. This problem can be solved as a two-index assignment problem.3, 5, 7

GREEDY RANDOM ADAPTIVE SEARCH PROCEDURE

In this section, we use a Greedy Random Adaptive Search Procedure to solve the three-index assignment problem, while taking into account the additional constraints in (17). The GRASP has been used to solve the standard AP3, and primarily consists of two phases: a construction phase that builds a basic feasible solution, and a local search phase that locates a solution in the neighborhood of the basic feasible solution with a lower cost. Reference 14 discusses two variants of implementing the construction phase (randomized greedy, maximum regret) as well as two variants of implementing the local search phase (two-exchange neighborhood search, variable depth exchange). We will use the randomized greedy method in the construction phase in order to generate a basic feasible solution, and we will perform a local search using a two-exchange neighborhood. 7

Construction of a Basic Feasible Solution

The construction phase iteratively builds a feasible solution M by selecting |Id,0 | triplets, one at a time, from a list L of eligible triplets from T . The list L initially consists of all triplets in the reduced constellation graph Gr , that is, L = T , because initially all triplets are eligible for selection during the construction of M. Let M denote the constructed solution after the th iteration, where ≤ |Id,0 |. Initially M0 = ?. Assume p ? 1 < |Id,0 | triplets have been added after p ? 1 iterations, so the current constructed solution is denoted by Mp?1 = {(i , j , k ) : = 1, 2, . . . , p ? 1}. The pth triplet needs to be added to Mp?1 . A parameter η , known as restricted candidate list parameter, is selected at random from the interval [0, 1] and is used to form a list Lr called the restricted candidate list that comprises of the best (in terms of lower cost) candidate triplets available for selection during the current iteration step. The restricted candidate list Lr ? L is de?ned as c ? c)}, Lr = {(i, j, k) ∈ L : c (i, j, k) ≤ c + η (? ? are given by where c and c ? = max c (i, j, k) . c = min c (i, j, k) and c

(i,j,k)∈L (i,j,k)∈L

(18)

(19)

The de?nition of the restricted candidate list given in (18) shows the greedy nature of the algorithm. Only triplets in L having cost less than c + η (? c ? c) are made eligible for selection. At the pth step the triplet (ip , jp , kp ) is chosen at random from Lr , provided it does not violate (17), that is, kp = Pas(i , j , k ) for all = 1, 2, . . . , p ? 1, (20) and k = Pas(ip , jp , kp ) for all = 1, 2, . . . , p ? 1. (21) Equation (20) implies that the return orbital slot corresponding to the triplet (ip , jp , kp ) cannot be the orbital slot of a passive satellite corresponding to any of the triplets in Mp?1 , and equation (21) implies that the orbital slot of the passive satellite corresponding to the triplet (ip , jp , kp ) cannot be the returning orbital slot corresponding to any of the triplets in Mp?1 . Once the pth triplet is selected, the set of candidate triplets L must be adjusted to take into account that (ip , jp , kp ) is now part of the solution. Therefore, any triplet (i, j, k) ∈ L with i = ip or j = jp or k = kp is removed from L because any such triplet cannot be selected in the future; otherwise at least one of the constraints (14), (15), or (16) will be violated. Subsequently, the list L is updated accordingly. Finally, Mp = Mp?1 ∪ (ip , jp , kp ). The adaptive nature of the GRASP method is due to the fact that once a triplet from Lr is selected for addition to Mp?1 , all triplets that are made ineligible for addition to Mp+1 are removed from L. The probabilistic nature of the algorithm arises from the use of the random parameter η and the random selection of a triplet from the restricted candidate list. In the most simple implementation of the algorithm the value of η is not changed during the construction phase.

8

Local Search

In the local search phase, the feasible solution from the construction phase is improved upon by searching its neighborhood for a better solution. If an improvement is detected, the solution is updated and a new neighborhood search is initialized. The de?nition of the neighborhood N (M) of M is crucial for the performance of the local search. Here we use the 2-exchange neighborhood suggested in Ref 15. Recall that the basic feasible solution generated by the construction phase consists of |Id,0 | triplets. For convenience, let us denote the triplet (i , j , k ) by t . Let also D = {1, 2, . . . , |Id,0 |} denote the index set of triplets in M. We can therefore write M = {t : ∈ D}. We will denote the di?erence between tp , tq ∈ M by δ (tp , tq ) = {r : tp,r = tq,r , r = 1, 2, 3}. The distance between the triplets tp and tq is then de?ned as d(tp , tq ) = |δ (tp , tq )|. (23) (22)

Using (23), we can de?ne the 2-exchange neighborhood of the triplet pair (tp , tq ) ∈ M × M as N2 (tp , tq ) = {(τ, σ ) ∈ M × M : d(tp , τ ) + d(tq , σ ) = 2}. (24)

The neighborhood of the solution M consists of the union of 2-exchange neighborhoods of all possible triplet pairs (tp , tq ) ∈ M, that is, N (M) =

(tp ,tq )∈M

N2 (tp , tq ).

(25)

During the local search phase the cost of each M ∈ N (M) (validated with respect to the constraints as in (17)) is compared with the cost of M. If the cost is lower, then the current search is halted, and a search around the neighborhood of M is initialized. The local search ends when no neighbor of the current solution has a lower cost. The successive application of the construction phase and the local search phase may generate several local minima. The procedure halts either after the maximum number of iterations is reached, or if a local minimum with a value less than or equal to some pre-speci?ed value is found.

Path Relinking

Path relinking is used to improve the quality of the solution generated by the construction and local search phases. Path relinking consists of exploring a trajectory that connects two local minima. Let us consider one of the two local minima as the initial solution and the other one as the guiding solution. A path is generated by selecting steps that introduce in the initial solution attributes of the guiding solution. Each step in the generation of the trajectory is said to be a move. Let M1 and M2 be two local minima generated by the previous phases of the GRASP procedure. Let M1 = {t : ∈ D} be the initial solution and M2 = {g : ∈ D} be the guiding solution. Without loss of generality, we may assume t ,2 = g ,2 for all ∈ D because orbital slots of all fuel-de?cient satellites need to be in any basic feasible solution. The symmetric di?erence between M1 and M2 is given by the following expressions ?1 = { ∈ D : t

,1

= g ,1 , t ∈ M1 , g ∈ M2 }, 9

(26)

?3 = { ∈ D : t

,3

= g ,3 , t ∈ M1 , g ∈ M2 }.

(27)

An intermediate solution on the path from M1 to M2 can be generated by making two kinds of moves. The sets ?1 and ?3 are used to guide such moves. Let M = {h : ∈ D} be an intermediate solution such that t ,2 = h ,2 for all ∈ D. Initially, M = M1 . Let r ∈ ?1 . Also, let hq,1 = gr,1 for some q ∈ D. Then, in one kind of move, triplets hr and hq are replaced by (hq,1 , hr,2 , hr,3 ) and (hr,1 , hq,2 , hq,3 ) respectively in M. The new solution generated is M = M ∪ {(hq,1 , hr,2 , hr,3 ), (hr,1 , hq,2 , hq,3 )}\{hr , hq }. (28)

Once such a move is made, r is removed from ?1 . Similarly, let r ∈ ?3 and hq,3 = gr,3 for some q ∈ D. In the other kind of move, triplets hr and hq are replaced by (hr,1 , hr,2 , hq,3 ) and (hq,1 , hq,2 , hr,3 ) respectively in M. The new solution generated is M = M ∪ {(hr,1 , hr,2 , hq,3 ), (hq,1 , hq,2 , hr,3 )}\{hr , hq }. (29)

Once such a move is made, r is removed from ?3 . Provided a move generates a basic feasible solution (validated with respect to constraints as in (17)), the cost of the solution M or M is compared to M1 and M2 . If the cost of either M or M is found to be lower than M, then a local search is performed in its neighborhood to yield a better solution.

NUMERICAL RESULTS

In this section, we apply the GRASP method with path relinking in order to determine the optimal assignments required for P2P refueling of sample constellations when the active satellites are not restricted to return to their original orbital slots. We also compare the results against the baseline P2P cases, namely when the active satellites are constrained to return to their original orbital slots. With the help of numerical examples, we show how the removal of such a restriction leads to considerable reduction in the fuel expenditure required for the refueling process to be completed. In all examples, we run the GRASP procedure 10, 000 times in order to determine the optimal assignments. Example 1. We consider a circular constellation of 10 satellites evenly distributed in a circular orbit. The maximum allowed time for refueling is T = 12 orbital periods. The constellation details are given in Table 1. Each satellite si has a minimum fuel requirement of f i = 12 units, permanent structure of msi = 70, and a characteristic constant of c0i = 2943 m/s. The indices of the fuel-su?cient satellites are Is,0 = {1, 2, 8, 9, 10} and those of the fuel-de?cient satelites are Id,0 = {3, 4, 5, 6, 7}. For the baseline P2P refueling strategy, the optimal pairings are s4 → s1 , s5 → s2 , s7 → s8 , s6 → s9 , s3 → s10 , and the total fuel consumption for all P2P maneuvers is 26.07 units. This represents 14.48% of the total initial fuel in the constellation. The indices of the active satellites in this case are Ia = {3, 4, 5, 6, 7}. Note that Ia = Id,0 , that is, the fuel-de?cient satellites are the active ones for the baseline P2P refueling strategy. A fuel-de?cient satellite has smaller mass compared to a fuel-su?cient satellite and thus uses a smaller amount of fuel during an orbital transfer. Hence, during a refueling maneuver between a fuel-su?cient and a fuel-de?cient satellite, the fuel-de?cient satellite is more likely to be the active satellite. 10

i 1 2 3 4 5 6 7 8 9 10

Satellites s1 s2 s3 s4 s5 s6 s7 s8 s9 s10

Table 1: Constellation C1 . Orbital Position (deg) Initial fuel content ? φ1 = 0 f1 = 30 ? φ2 = 36 f2 = 30 ? φ3 = 72 f3 =6 ? φ4 = 108 f4 =6 ? φ5 = 144 f5 = 6 ? φ6 = 180 f6 =6 ? φ7 = 216 f7 = 6 ? φ8 = 252 f8 = 30 ? φ9 = 288 f9 = 30 ? φ10 = 324 f10 = 30

For the case in which the active satellites are allowed to interchange their orbital slots, the optimal assignment for P2P refueling, determined from GRASP, is s8 → s7 → s6 , s6 → s9 → s8 , s3 → s10 → s1 , s1 → s4 → s5 , s5 → s2 → s3 . The fuel expenditure during the refueling process is 18.73 units, which is less than the fuel expenditure for the baseline P2P case. This represents 10.41% of the total initial fuel in the constellation, or an improvement of 28% over the standard P2P scenario. Figure 1 shows the constellation and the optimal assignments. The active satellites are marked by ’ ’.

S4 S3 S5 S2

S6

S1

S7

S10

S8

S9

Figure 1: Constellation for Example 1.

The forward trips are marked by solid arrows, while the return trips are marked by dotted arrows. In the optimal assignment produced by the GRASP method, it is observed that each active satellite, after undergoing a fuel transaction with the corresponding passive satellite, returns to an available orbital slot in the vicinity of the passive satellite with which it was involved in the transaction. For instance, satellite s1 undergoes a fuel transaction with the satellite s4 and then returns to the orbital slot initially occupied by active satellite s5 . Moving to an orbital slot in the vicinity involves an orbital transfer through a smaller transfer angle and thereby results in a likely lesser fuel expenditure during the return trip. Hence, the active satellites, having the freedom to return to any available orbital slot, opt to move to a nearby 11

S4 S3 S5 S2 S5

S4 S3

S2

S6

S1

S6

S1

S7

S10

S7

S10

S8

S9

S8

S9

(a) Cost = 24.87

(b) Cost = 24.77

S4 S3 S5 S2 S5 S2 S4 S3

S6

S1

S6

S1

S7

S10 S7 S8 S9 S8 S9 S10

(c) Cost = 22.61

(d) Cost = 20.48

Figure 2: Assignments obtained during local searches of the GRASP method.

one during the return trip. In the baseline P2P strategy, such freedom is not available, and some of the active satellites have to perform orbital transfers that incur higher cost. Another observation is the fact that some of the active satellites are also fuel-su?cient. Note that satellites s1 and s8 are fuel-su?cient and active. For this problem, by having some fuelsu?cient satellites as the active satellites, it is ensured that all active satellites are able to return to the nearest orbital slot, thereby saving fuel during the return trip. Figure 2 depicts a basic feasible solution generated by the GRASP method along with a local search performed about this solution. Figure 2(a) is the basic feasible solution and corresponds to the assignment s4 → s10 → s1 , s1 → s3 → s4 , s7 → s8 → s2 , s2 → s5 → s7 , s6 → s9 → s6 . The cost of this assignment is 24.87 units of fuel. By performing a search in the neighborhood of this solution, another assignment of lower cost, shown in Figure 2(b) is obtained. In this assignment, satellite s4 returns to the orbital slot initially occupied by s2 instead of the orbital slot initially occupied by s1 , while satellite s7 returns to the orbital slot initially occupied by s1 instead of returning to the orbital slot initially occupied by s2 . The cost of this assignment is 24.77 units of fuel. A local search performed in the neighborhood of this solution yields the assignment shown in Figure 2 (c). In this assignment, satellite s7 rendezvous with s9 instead of s8 , while satellite s6 rendezvous with s8 instead of s9 . The cost of this assignment is 22.61 units of fuel. A search in the neighborhood of this solution now yields yet another assignment shown in Figure 2(d). In this assignment, satellite s2 returns to the orbital slot initially occupied by s6 instead of the orbital slot initially occupied by s7 , while satellite s6 returns to the orbital slot initially occupied by s7 instead of returning to its original orbital slot. The cost of this solution is 20.48. Finally, a local search in the neighborhood of this

12

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Table 2: Constellation C2 . Satellites Orbital Position Initial fuel content ? s1 φ1 = 0 f1 = 30 ? s2 φ2 = 22.5 f2 = 30 ? s3 φ3 = 45 f3 = 30 ? s4 φ4 = 67.5 f4 = 30 ? s5 φ5 = 90 f5 = 30 ? s6 φ6 = 112.5 f6 = 30 ? s7 φ7 = 135 f7 = 10 ? s8 φ8 = 157.5 f8 = 10 ? s9 φ9 = 180 f9 = 10 ? s10 φ10 = 202.5 f10 = 10 ? s11 φ11 = 225 f11 = 10 ? s12 φ12 = 247.5 f12 = 10 ? s13 φ13 = 270 f13 = 10 ? s14 φ14 = 292.5 f14 = 10 ? s15 φ15 = 315 f15 = 30 ? s16 φ16 = 337.5 f16 = 30

solution yields no other cheaper solution, thereby implying that the assignment in Figure 2(d) is a local minimum. Example 2. In this example we consider a circular constellation of 16 satellites, evenly distributed in a circular orbit. The maximum allowable time for refueling is T = 30 orbital periods. The constellation details are given in Table 2. Each satellite si has a minimum fuel requirement of f i = 15 units, permanent structure of msi = 70 units and a characteristic constant of c0i = 2943 m/s. The indices of the fuel-su?cient satellites are Is,0 = {1, 2, 3, 4, 5, 6, 15, 16}, while those of the fuel-de?cient satellites are Id,0 = {7, 8, 9, 10, 11, 12, 13, 14}. If the active satellites are constrained to return to their original orbital slots after refueling, then the optimal pairings are s11 → s1 , s12 → s2 , s9 → s3 , s7 → s4 , s8 → s5 , s10 → s6 , s13 → s15 , s14 → s16 , and the total fuel consumption during the P2P maneuvers is 37.46 units. This represents 11.71% of the total initial fuel in the constellation. For all the pairings in this case, only the fuel-de?cient satellites are the active ones, that is, Ia = {7, 8, 9, 10, 11, 12, 13, 14} = Id,0 . This is similar to the previous example. If the active satellites are allowed to interchange orbital slots, then the optimal assignment for the P2P refueling problem, as determined by the GRASP method, are s1 → s12 → s13 , s3 → s7 → s6 , s5 → s8 → s9 , s6 → s10 → s11 , s9 → s4 → s5 , s11 → s15 → s14 , s13 → s16 → s1 , s14 → s2 → s3 . Here, Ia = {1, 3, 5, 6, 9, 11, 13, 14}. Relaxing the return orbital position constraint reduces the fuel expenditure to 24.82 units. This represents 7.76% of the total initial fuel in the constellation or an improvement of 33% over the standard P2P scenario. Figure 3 shows the constellation and the optimal assignments. The active satellites are marked by ’ ’. Similar to Example 1, it is observed that the active satellites, after undergoing fuel transactions with the corresponding passive satellites, return to an available orbital slot in their vicinity. For instance, satellite s1 undergoes a fuel transaction with satellite s12 and returns to the orbital slot occupied by active satellite s13 . Also, the active satellites include fuel-su?cient 13

S5 S6 S7 S4 S3

S8

S2

S9

S1

S10 S11 S12 S13 S14 S15

S16

Figure 3: Constellation for Example 2.

ones. Here s1 , s3 , s5 and s6 are fuel-su?cient and active. We have also tested the proposed methodology on several sample constellations. Table 3 gives the description of a few of these sample constellations (C1 and C2 are the constellations already described in Examples 1 and 2, respectively). The optimal assignments for these constellations show considerable reduction in fuel consumption against the baseline P2P strategy. For instance, for constellation C3 the baseline P2P refueling strategy yields the optimal assignment s4 → s1 , s5 → s2 , s7 → s10 , s6 → s3 , s11 → s8 , s9 → s12 with a fuel expenditure of 26.73 units, with the fuel-de?cient satellites being the active ones. Our proposed methodology yields the optimal assignment s9 → s12 → s11 , s11 → s8 → s7 , s4 → s1 → s2 , s2 → s5 → s6 , s6 → s3 → s4 , s7 → s10 → s9 , that reduces the fuel expenditure to 18.51 units. Similarly, for

Fuel expenditure in P2P refueling

Baseline P2P Strategy 140 120 Proposed P2P Strategy

Fuel expenditure

100 80 60 40 20 0 C1 C2 C3 C4 C5 C6 C7

Constellations

Figure 4: Comparison of results for several sample constellations.

14

the other constellations the fuel expenses reduce from 41.06 units to 26.26 units in case of C4 , from 28.38 to 18.51 in case of C5 , from 28.77 units to 19.21 units in case with C6 , and from 34.97 units to 22.57 units in the case of C7 . Figure 4 summarizes these observations.

CONCLUSIONS

In this paper, we have studied the peer-to-peer satellite refueling problem under the assumption that the active satellites are allowed to interchange orbital positions during their return trips. The problem is formulated as a three-index assignment problem on a tripartite constellation graph. The problem is shown to deviate from the standard three-index assignment problem (AP3) studied in the literature owing to additional constraints imposed by the nature of the problem. We have used a Greedy Random Adaptive Search Procedure (GRASP) in order to ?nd the optimal assignments. With the help of numerical examples, it is shown that our proposed P2P refueling strategy, which allows active satellites to interchange orbital positions during their return trips, results in considerable reduction in the fuel expenditure incurred during the refueling process. It is also shown that each active satellite opts to return to an available orbital slot in the vicinity of the passive satellite with which it is involved in a fuel transaction. Table 3: Sample Constellations. Description 12 satellites, Altitude = 2, 000 Km, T = 30 fi? : 30, 30, 30, 10, 10, 10, 10, 10, 10, 30, 30, 30 ? f i = 30, f i = 15, msi = 70 for all satellites 18 satellites, Altitude = 6, 000 Km, T = 25 fi? : 25, 25, 25, 25, 25, 25, 25, 25, 25, 6, 6, 6, 6, 6, 6, 6, 6, 6 ? f i = 25, f i = 12, msi = 75 for all satellites 12 satellites, Altitude = 12, 000 Km, T = 20 fi? : 25, 25, 25, 25, 25, 25, 8, 8, 8, 8, 8, 8 ? f i = 25, f i = 12, msi = 75 for all satellites 14 satellites, Altitude = 1, 400 Km, T = 35 fi? : 25, 25, 25, 25, 25, 25, 25, 8, 8, 8, 8, 8, 8, 8 ? f i = 25, f i = 12, msi = 75 for all satellites 16 satellites, Altitude = 30, 000 Km, T = 15 fi? : 10, 10, 10, 10, 10, 10, 10, 10, 28, 28, 28, 28, 28, 28, 28, 28 ? f i = 30, f i = 15, msi = 70 for all satellites

Label C3

C4

C5

C6

C7

REFERENCES

[1] Shen, H. and Tsiotras, P., “Optimal scheduling for servicing multiple satellites in a circular constellation,” AIAA/AAS Astrodynamics Specialists Conference , No. AIAA Paper 024907, Monterey, CA, Aug. 2002.

15

[2] Shen, H., Optimal Scheduling for Satellite Refuelling in Circular Orbits , Ph.D. thesis, Georgia Institute of Technology, 2003. [3] Shen, H. and Tsiotras, P., “Peer-to-peer refueling for circular satellite constellations,” AIAA Journal of Guidance, Control, and Dynamics , Vol. 28, 2005, pp. 1220–1230. [4] Tsiotras, P. and Nailly, A., “Comparison between peer-to-peer and single spacecraft refueling strategies for spacecraft in circular orbits,” Infotech@Aerospace Conference , No. AIAA Paper 05-7115, Crystal City, DC, Sept. 2005. [5] Dutta, A. and Tsiotras, P., “Asynchronous optimal mixed P2P satellite refueling strategies,” D. Shuster Astronautics Symposium , No. AAS Paper 05-474, Bu?alo, NY, June 2005. [6] Gibbons, A., Algorithmic Graph Theory , Cambridge University Press, Cambridge, UK, 1985. [7] Salazar, A. and Tsiotras, P., “An auction algorithm for optimal satellite refueling,” Georgia Tech Space Systems Engineering Conference , Atlanta, GA, Nov. 2005. [8] Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness , W.H. Freeman and Company, San Francisco, CA, 1979. [9] Pierskalla, W., “The multi-dimensional assignment problem,” Operations Research , Vol. 16, 1968, pp. 422–431. [10] Balas, E. and Saltzman, M., “An algorithm for the three-index assignment problem,” Operations Research , Vol. 39, 1991, pp. 150–161. [11] Crama, Y. and Spieksma, F., “Approximation algorithms for three dimensional assignment problems with triangle inequalities,” European Journal of Operations Research , Vol. 60, 1992, pp. 273–279. [12] Bandelt, H., Crama, Y., and Spieksma, F., “Approximation algorithms for multidimensional assignment problems with decomposable costs,” Discrete Applied Mathematics , Vol. 49, 1994, pp. 25–50. [13] Feo, T. and Resende, M., “Greedy randomized adaptive search procedures,” Journal of Global Optimization , Vol. 6, 1995, pp. 109–133. [14] Robertson, A. J., “A set of greedy randomized adaptive local search procedure (GRASP) implementations for the multidimensional assignment problem,” Computational Optimization and Applications , Vol. 19, 2001, pp. 145–164. [15] Aiex, R., Resende, M., Pardalos, P., and Toraldo, G., “GRASP with path relinking for three-index assignment,” INFORMS Journal on Computing , Vol. 2, 2005, pp. 224–227. [16] Prussing, J., “A class of optimal two-impulse rendezvous using multiple-revolution Lambert solutions,” Advances in Astronautical Sciences , Vol. 106, 2000, pp. 17–39.

16

相关文章:

- P2P Streaming Modeling_图文.ppt
*P2P*Streaming Modeling_计算机软件及应用_IT/计算机_...? The*Greedy*Strategy can achieve better ...Structured Streaming*Scheduling*and routing can ...

- Simulating Greedy Propagation of P2P Worms_论文.pdf
- Simulating
*Greedy*Propagation*of**P2P*Worms_信息与通信_工程科技_专业资料。JOURNAL*OF*ELECTRONISENCE CCIANDECHNOLOG VOL.,T8NO.,4DECEMBER 1 200 Smuai ...

- ...RANDOM ADAPTIVE SEARCH PROCEDURE FOR OPTIMAL SCHEDULING OF....unkown
- AAS 07-150
*A**GREEDY**RANDOM**ADAPTIVE**SEARCH**PROCEDURE**FOR**OPTIMAL**SCHEDULING**OF**P2P*SATELLITE REFUELING Atri Dutta and Panagiotis Tsiotras Abstract ...

- Koorde A simple degree-optimal distributed hash table.pdf
- Koorde
*A*simple degree-*optimal*distributed hash ...(the set can be found by*a**greedy*algorithm: ...However. in*a**P2P*system we want no node to ...

- GPSA: A Greedy Pull-based Scheduling Approach for P2P Live ....pdf
- GPSA:
*A**Greedy*Pull-based*Scheduling*Approach*for**P2P*Live Streaming under Heterogeneous Enviro_专业资料。辞 hmuan西{Camii iontsnCco GPSA:*A*rGeedyPul? ...

- K. A dynamic pricing mechanism for p2p referral systems.pdf
- K.
*A*dynamic pricing mechanism*for**p2p*referral ...*State*University Raleigh, NC 27695, USA Katia Sy...We suggest the -*greedy*method to choose an ...

- Koorde A simple degree-optimal distributed hash table.pdf
- (the set can be found by
*a**greedy*algorithm: ...However. in*a**P2P*system we want no node to ...However, such replication does increase the*state*...

- Self-Configuration Protocols for P2P Networks Abstract.pdf
- including
*random*, egoist, altruist and*greedy*...*P2P*systems, meaning flooding-based*search*becomes...*state*, calling the*procedure*node_join depicted ...

- ...RANDOM ADAPTIVE SEARCH PROCEDURE FOR OPTIMAL SCHEDULING OF....unkown
- AAS 07-150
*A**GREEDY**RANDOM**ADAPTIVE**SEARCH**PROCEDURE**FOR**OPTIMAL**SCHEDULING**OF**P2P*SATELLITE REFUELING Atri Dutta and Panagiotis Tsiotras Abstract ...

- ...RANDOM ADAPTIVE SEARCH PROCEDURE FOR OPTIMAL SCHEDULING OF....unkown
- AAS 07-150
*A**GREEDY**RANDOM**ADAPTIVE**SEARCH**PROCEDURE**FOR**OPTIMAL**SCHEDULING**OF**P2P*SATELLITE REFUELING Atri Dutta and Panagiotis Tsiotras Abstract ...

更多相关标签:

- A greedy randomized adaptive search procedure for the quadratic assignment problem
- Asynchronous optimal mixed P2P satellite refueling strategies
- Adaptive greedy approximations
- A Greedy Randomized Adaptive Search Procedure for Technicians and Interventions Scheduling
- Minerva Collaborative p2p search
- Distributed interest-based adaptive search for P2P networks
- A Greedy Randomized Adaptive Search Procedure Applied to the Clustering Problem as an Initi
- IEEE TRANSACTIONS ON MULTIMEDIA 1 PULSE an Adaptive, Incentive-based, Unstructured P2P Live
- Greedy Randomized Adaptive Search and Variable Neighbourhood Search for
- An optimal local search procedure for manpower scheduling in call centers