Raïssa G Mbiadou Saleu
email: raissa.saleu@isima.fr

Laurent Deroussi
email: laurent.deroussi@uca.fr

Dominique Feillet
email: feillet@emse.fr

Nathalie Grangeon
email: nathalie.grangeon@uca.fr

Alain Quilliot
email: alain.quilliot@isima.fr

An iterative two-step heuristic for the Parallel Drone Scheduling Traveling Salesman Problem

Keywords: drone delivery, vehicle routing problem, city logistics, dynamic programming, heuristic, PDSTSP

. In this problem, deliveries are split between a vehicle and one or several drones. The vehicle performs a classical delivery tour from the depot, while the drones are constrained to perform back and forth trips. The objective is to minimize the completion time. We propose to solve the problem with an original iterative two-step heuristic, composed of: a coding step that transforms a solution into a customer sequence, and a decoding step that decomposes the customer sequence into a tour for the vehicle and series of trips for the drone(s). Decoding is expressed as a bicriteria shortest path problem and is carried out by dynamic programming. Experiments conducted on benchmark instances from the literature confirm the efficiency of the approach and give some insights on this drone delivery system.

INTRODUCTION

Last mile logistics has become a popular area of interest for retailers. Companies are always searching for fast and cost-efficient ways to deliver goods to their customers. It is from this perspective that in 2013, the chief executive officer of the largest online retailer Amazon revealed a revolutionary project of the company called Prime Air [1], a drone designed to deliver packages in just 30 minutes (Fig. 1). In August 2014, Google followed by revealing its drone delivery project called wing, with experiments run in Australia. In September 2014, DHL Express launched its parcelcopter, a helicopter-style drone which could deliver medications and urgently needed goods to the remote North Sea island of Juist [2]. In 2015, the online retailer Alibaba tested the usage of drones to deliver online orders of tea to customers in China [START_REF] Kelion | Alibaba begins drone delivery trials in China[END_REF]. In April 2016, Autralia post started testing the usage of remotely piloted drones internally for parcel delivery, with the support of the Civil Aviation Safety Authority [START_REF]Australia Post tests drones for parcel delivery[END_REF]. In July 2016, convenience store chain 7-eleven made their first commercial delivery with drone, partnered with the drone start-up Flirtey [START_REF] Liptak | Eleven just made the first commercial delivery by drone[END_REF]. United Parcel Service (UPS) company is testing drones to deliver medicine to an island near Boston [START_REF] Ngowi | UPS testing drones for use in its package delivery system[END_REF]. Still in july 2016, the first humanitarian drone called Zipline arrived in Rwanda. Zipline is a drone of about 10 kilos that is capable of carrying 1.3 kilos of medicines or blood [START_REF]The Future of Healthcare is Out for Delivery[END_REF]. In August 2016, Domino's Pizza announced their intention to extend to France their experiments on pizza delivery by drone, as initiated in New Zealand [START_REF]L'avenir est dans le ciel : Domino's et Flirtey s'associent pour livrer des pizzas par drone, conformÃľment au code de l'aviation[END_REF]. Many other companies not mentioned above have launched similar projects.

Previously exclusively used in military applications, drones are becoming a part of the last mile delivery concept which can significantly accelerate delivery times and reduce human intervention. Indeed, drones are lightweight, they consume less energy than standard vehicles and they are not subject to congestion problems since they do not follow the road network. On the other hand, drones are limited in terms of endurance, capacity and payload. Despite several regulatory and safety standards barriers, the idea of using Unmanned Aerial Vehicle (UAV) for parcel delivery is gaining ground. Companies that want to use drones in their delivery process are confronted by air control administrations like the FAA 1 in the United States or the DGAC 2 in France. The scientific community is getting more and more interested in investigating the design of drone delivery systems.

In this paper, we are interested in the development of efficient solution methods for a specific drone delivery system. The remainder of the paper is organized as follows. In Section 2, we present the related literature. In Section 3, we formally describe the problem addressed in this paper and provide an integer linear programming formulation. We propose a heuristic to solve the problem in Section 4. In Section 5, we discuss the results obtained from our computational experiments. Finally, we conclude with some directions for future researches in Section 6.

RELATED WORK

The problem of parcel delivery with drone has received increasing attention these last years. Murray and Chu [START_REF] Chase | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF] introduced the Flying Sidekick Traveling Salesman Problem (FSTSP) and the Parallel Drone Scheduling Traveling Salesman Problem (PDSTSP). In both problems, the optimization criterion is the minimization of the completion time, i.e., the time elapsed between the beginning and the end of the delivery process.

In the FSTSP, deliveries are performed by a single vehicle and a single drone working in tandem. The vehicle carries the drone and when the vehicle is at a customer location, it can decide to launch the drone to visit another customer location. After this drone delivery, the vehicle will then have to retrieve the drone at another customer location. Formally, a drone trip is represented as a triplet < i, j, k > where i is the launching point, j is the service point and k is the rendez-vous point (i j, j k and i k). Figure 2 shows an illustration of the synchronization mechanism in the FSTSP. The authors proposed a Mixed-Integer Linear Programming (MILP) formulation and a heuristic that first constructs a TSP tour visiting all the customer locations and next, repeatedly run a relocation procedure to assign some customer requests to the drone. The second problem introduced by Murray and Chu [START_REF] Chase | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF], the PDSTSP, simplifies the FSTSP setting by relaxing the synchronization issue between the vehicle and the drone. Conversely, it considers a fleet of drones instead of a single drone. The vehicle visits a subset of customers with a TSP tour and the drones serve the remaining customers directly from the depot with back and forth trips. Again, the authors proposed a MILP formulation and a heuristic. The principle of the heuristic is to partition the set of customers into two subsets (a vehicle set and a drone set). Then, a TSP tour is computed for the customers assigned to the vehicle and a Parallel Machine Scheduling (PMS) problem is solved to assign customer requests (jobs) to drones (machines). At the end, an improvement step is performed to reassign customers either to the drone set or to the vehicle set in order to better balance vehicle and drones activities.

In his Master Thesis, Ponza [START_REF] Ponza | Optimization of Drone-assisted parcel delivery[END_REF] addresses the FSTSP and proposes a simulated annealing heuristic.

Wang et al. [START_REF] Wang | The vehicle routing problem with drones: several worst-case results[END_REF] studied an extension of the FSTSP called the Vehicle Routing Problem with Drones (VRPD) in which they considered a homogeneous fleet of trucks, each one of them carrying several identical drones. A drone launched from a truck must be picked up by the same truck at the same or at a different location. The objective is still to minimize the completion time. The authors proposed worst-case analyses and obtained theoretical bounds on the benefits achieved using drones.

In [START_REF] Agatz | Optimization approaches for the traveling salesman problem with drone[END_REF], Agatz et al. introduced another variant of the FSTSP that they called the Traveling Salesman Problem with Drone (TSP-D). Contrary to the FSTSP, the launching point of a drone and the rendezvous point with the vehicle are not necessarily different. Furthermore, the objective is to find the shortest tour to serve all customer locations either by the vehicle or the drone. The authors proposed an Integer Programming (IP) formulation and a route firstcluster second heuristic.

Ha et al. [START_REF] Quang | Heuristic methods for the Traveling Salesman Problem with Drone[END_REF] adopted the name TSP-D for the FSTSP. They proposed a cluster first -route second and a route first -cluster second heuristic. In [START_REF] Quang | On the Min-cost Traveling Salesman Problem with Drone[END_REF], the same authors investigated a different objective function: the minimization of the total transportation cost for both the vehicle and the drone. They coined this problem as min-cost TSP-D. They proposed a MILP model and two heuristics: one based on a Greedy Randomized Adaptive Search Procedure (GRASP) and another one called TSP-LS adapted from the work of Murray and Chu [START_REF] Chase | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF]. Dorling et al. [START_REF] Dorling | Vehicle routing problems for drone delivery[END_REF] introduced a very different problem that they called Drone Delivery Problem (DDP). They considered two variants of the DDP: the Minimum Cost Drone Delivery Problem (MC-DDP) that aims at minimizing the total delivery cost and the Minimum Time Drone Delivery Problem (MT-DDP) that aims at minimizing the total delivery time. In these problems, deliveries are only performed by drones, and the energy consumption is explicitly considered for the drones, taking into account their payload. The authors established the relationship with the Multi-Trip Vehicle Routing Problem (MTVRP). They proposed a MILP formulation and a Simulated Annealing (SA) heuristic.

Ulmer and Thomas [START_REF] Ulmer | Same-Day Delivery with a Heterogeneous Fleet of Drones and Vehicles[END_REF] studied a dynamic variant of the PDSTSP. They called their problem Same-Day Delivery Routing Problem with Heterogeneous Fleets (SDDPHF). The SDDPHF considers two fleets of vehicles and drones that deliver goods from the depot to customers who dynamically request services. When a new customer request arrives, a dispatcher has to decide whether or not to accept the customer for the same-day delivery and determine the according assignment and routing decisions. The SDDPHF takes into account a time window for each request, the loading time for both vehicles and drones, the time to drop off a package from a vehicle or a drone as well as the recharging or battery swap time for drones. The objective is to maximize the expected number of customers served the same day. To solve the problem, the authors proposed an adaptive dynamic programming approach called parametric policy function approximation (PFA).

Table 1 gives a summary of the main papers on drone delivery problems found in the literature.

In connection with the literature on drone delivery, we can also mention the Carrier-Vehicle TSP, addressed by Garonne et al. [START_REF] Garone | Traveling-Salesman Problem for a Class of Carrier-Vehicle Systems[END_REF] or Gambella et al. [START_REF] Gambella | Exact Solutions for the Carrier-Vehicle Traveling Salesman Problem[END_REF]. In this problem, two vehicles with different capabilities cooperate. The carrier is slow but has a virtually infinite operating range. Its role is to deploy and recover a second vehicle, typically an aircraft, which is faster but has a reduced operating range.

THE PARALLEL DRONE SCHEDULING TRAVELING SALESMAN PROBLEM

In this paper, we focus on the PDSTSP, presented in [START_REF] Chase | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF], that we found more relevant on a short term in view of actual delivery practices and that has yet drawn less attention in the literature. The PDSTSP is formally defined below.

Problem definition and notation

We consider a complete directed graph G = (N ∪ {0}, A) where N = {1, . . . , n} is a customer set and 0 is the depot. A vehicle and a fleet of M drones are available to deliver parcels to customers. The vehicle delivers customers with a single tour starting from the depot, visiting a subset of customers and returning back to the depot. Drones operate back and forth trips between the depot and the customers, delivering a single customer in each trip. Not all customers are eligible for drone delivery, because of practical constraints such as the limited payload or the flying range of drones. The subset of customers that can be served by a drone is denoted N d . These customers are consistently called drone-eligible in the rest of the paper. Figure 3 depicts a solution of the PDSTSP on an instance with 10 customers, among which 5 are drone-eligible. A travel time d i j is incurred when the vehicle goes through an arc (i, j) ∈ A. A travel time d i is incurred when a drone serves a customer i ∈ N d . Assuming that both the vehicle and the drones can start from the depot at time 0, the objective of the PDSTSP is to minimize the delivery completion time, i.e., the time at which the vehicle and all drones are back to the depot, with the service of all customers carried out.

MILP formulation

In this section, we express the PDSTSP with a MILP formulation. We introduce the following binary decision variables :

• z i = 1 if customer i is visited by the vehicle, 0 if it is visited by the drone (i ∈ N ); • x i j = 1 if arc (i, j) belongs to the vehicle tour, 0 otherwise ((i, j) ∈ A);

• y im = 1 if customer i is assigned to drone m, 0 otherwise (i ∈ N d , 1 ≤ m ≤ M).
In addition, we introduce a nonnegative variable T that represents the completion time.

The model is:

minimize T (1) subject to T ≥ (i, j)∈A d i j x i j (2) T ≥ i ∈N d d i y im (1 ≤ m ≤ M) (3)
z i = 1 (i ∈ N \ N d ) (4)
(i, j)∈A

x i j = z i (i ∈ N ) (5)
1≤m ≤M

y im = 1 -z i (i ∈ N d ) (6)
(0, j)∈A

x 0j ≤ 1 (7)
(i, j)∈A

x i j = (k,i)∈A x ki (i ∈ N ) (8) i ∈S j S x i j ≥ i ∈S z i + 1 -|S | (S ⊆ N , S ∅) (9)
z i ∈ {0, 1} (i ∈ N ) (10) x i j ∈ {0, 1} ((i, j) ∈ A) (11) y im ∈ {0, 1} (i ∈ N d , 1 ≤ m ≤ M) (12) T ≥ 0 ( 13
)
The objective (1) is to minimize the completion time T . Constraints (2) and (3) give lower bounds on T expressed using vehicle assignment and drone assignment variables. Constraints (4) ensure that all the customers that are not drone-eligible are served by the vehicle. Constraints ( 5) and ( 6) guarantee that every customer is served either by the vehicle or a drone, exactly once. Constraint [START_REF] Carlos | A bicriterion shortest path algorithm[END_REF] stipulates that the vehicle leaves the depot at most once. Constraints (8) ensure flow conservation for the vehicle tour. Subtour elimination constraints are provided by [START_REF] Gambella | Exact Solutions for the Carrier-Vehicle Traveling Salesman Problem[END_REF]. These constraints ensure that given a non empty subset of customers S ⊆ N , if all the customers in S are visited by the vehicle, there is at least one outgoing arc from S. Finally, constraints [START_REF] Garone | Traveling-Salesman Problem for a Class of Carrier-Vehicle Systems[END_REF] to [START_REF] Quang | On the Min-cost Traveling Salesman Problem with Drone[END_REF] define the decision variables.

ITERATIVE TWO-STEP HEURISTIC

The PDSTSP can be considered as a bilevel problem in which:

• at the first level, customers are partitioned between the vehicle and the fleet of drones; • the second level manages the routing optimization, which consists in solving two NP-Hard problems, namely: a TSP for the vehicle and a Parallel Machine Scheduling (PMS) problem for drones.

Our iterative two-step heuristic alternates between these two levels. Given a solution of the PDSTSP, a coding step transforms this solution into a customer sequence. Then, a decoding step decomposes this sequence into a tour for the vehicle and series of trips for the drones. These tours / trips are optimized and the process is repeated. The general solution framework does not depend on the number of drones, but the decoding procedure does. When M = 1, i.e., a single drone is available, the decoding scheme is exact. When M > 1, it is heuristically extended.

In Section 4.1, we describe the general scheme of the heuristic. The decoding procedure is detailed in Section 4.2 when M = 1. We explain how it is adapted to M > 1 in Section 4.3. In these sections, we adopt the following notation. A solution S is represented as a vector of M + 1 customer sequences (τ vehicl e , τ 1 , . . . , τ M ), where τ vehicl e indicates the visit order of the customers for the vehicle and τ 1 to τ M this order for the M drones. We denote c 1 (S) the completion time for the vehicle in solution S and c 2 (S) the completion time for the fleet of drones. Finally, c(S) = max(c 1 (S), c 2 (S)) is the solution cost.

General scheme of the iterative two-step heuristic

The general scheme of our heuristic is summarized in Algorithm 1 and is explained hereafter.

Algorithm 1 General scheme of the iterative two-step heuristic 1: τ ← solveT SP() 2: bestSol ← (τ , ∅, . . . , ∅) 3: while bestSol is improved do

end if 11: end while

In lines 1 and 2, we build a giant TSP tour τ visiting the depot and all the customers. For that matter, we apply a nearest-neighbor construction procedure. The TSP tour provides a starting solution (τ , ∅, . . . , ∅) for our algorithm, where all the customers are visited by the vehicle in the order of sequence τ and no customer is assigned to the drones.

The main part of the algorithm is given by lines 4 to 9 that are repeated as long as they enable finding better solutions. A solution S is considered to be better than another solution S ′ if one of the two following conditions hold:

• c(S) < c(S ′ ) • or c(S) = c(S ′ ) and min(c 1 (S), c 2 (S)) < min(c 1 (S ′ ), c 2 (S ′ ))
Decoding procedure split on Line 4 decomposes τ in two complementary subsequences: one assigned to the vehicle (τ vehicl e ) and one assigned to the fleet of drones (τ dr ones ). This procedure, which is central in the algorithm, is detailed below. Vehicle route τ vehicl e is then reoptimized, with Helsgaun's implementation of Lin-Kernighan heuristic [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF] (Line 5) and a PMS solution is obtained from τ dr ones (see Section 4.3). The new solution (τ opt vehicl e , τ opt 1 , . . . , τ opt M ) is compared with bestSol and the latter is updated if needed. Finally, in this case, all the customers from τ opt 1 , . . . , τ opt M are reinserted in τ opt vehicl e , in this order and with a best insertion policy (Line 9). Otherwise the algorithm stops. Note that when M = 1, the PMS problem is trivial, hence one can replace Line 6 with τ opt 1 ← τ dr ones .

Decoding procedure when M = 1

We first consider the case M = 1. Procedure split(τ ) computes the best partition of the customer set between the vehicle and the unique drone with the constraint that the customers in the vehicle tour follows the same order as in sequence τ . This problem is modeled as a bicriteria shortest path problem [START_REF] Carlos | A bicriterion shortest path algorithm[END_REF] in an acyclic directed graph and is solved by dynamic programming.

Definition of the acyclic graph. We introduce G τ = (V τ , A τ ) an acyclic graph defined as follows. V τ = {0, 1, 2, . . . , n, n+ 1} represents the set of customers completed by two copies of the depot: the original depot 0 and its copy n + 1. In the bicreteria shortest path problem, 0 will be the origin and n + 1 the destination. Given i and j in V τ , with i j, arc (i, j) exists in A τ if and only if the two following conditions are both satisfied:

• i = 0, or j = n + 1, or i is before j in τ (in the three cases we note i < τ j) • all the customers between i and j in τ are drone-eligible:

i < τ k < τ j ⇒ k ∈ N d
With every arc (i, j) ∈ A τ , we associate a cost vector (c 1 i j , c 2 i j ). The first cost component c 1 i j represents the cost incurred for the vehicle if it travels directly from i to j: c 1 i j = d i j . The second cost component c 2 i j represents the corresponding cost induced for the drone. If the vehicle travels directly from i to j, all customers k in-between (which by definition of A τ are all drone-eligible) are assigned to the drone:

c 2 i j = {k ∈V τ : i < τ k < τ j } d k .
Figure 4 shows an illustrative example for an instance with 5 customers. Customers 2 and 4 are not drone-eligible. The vehicle travel cost matrix is reported in Table 2(a) in which we add the copy of the depot (node 6). Table 2(b) presents the drone-trip costs for drone-eligible customers. We assume τ = (1, 2, 3, 4, 5).

Table 2 Illustrative instance

The set of paths from 0 to n + 1 in G τ exactly matches the set of acceptable routes for the vehicle that can be extracted from sequence τ . Furthermore, given a path P, the cost vector (c 1 (P), c 2 (P)) = ( (i, j)∈P c 1 i j , (i, j)∈P c 2 i j ) corresponds to the costs of the vehicle and the drone, if the route of the vehicle follows P and the remaining customers are assigned to the drone. Taking again the example depicted with Figure 4, path P = (0, 2, 4, 5, 6) should be interpreted as a solution S with a vehicle tour (0, 2, 4, 5, 0) and customers 1 and 3 assigned to the drone; c 1 (P) = 29, c 2 (P) = 28, c(S) = max(29, 28) = 29.

For that reason, the aim of the split procedure is to find the path P from 0 to n + 1 in G τ that minimizes max(c 1 (P), c 2 (P)). We now describe the dynamic programming procedure developed to compute this path.

Dynamic programming scheme. To understand the procedure applied to find that shortest path, let us first consider the following definitions:

• partial path: a path going from 0 (origin depot) to any node i of graph G τ ; • label: the cost vector (c 1 , c 2 ) of a partial path calculated by adding the costs of the crossed arcs.

The shortest path is found by applying the procedure described in Algorithm 2. The principle is to progressively associate a list of labels L(i) with each node i of G τ . At the initialization, L(i) is set to ∅ for every node i (Line 1). The procedure then starts by assigning label (0, 0) to L(0) (Line 2).

The procedure goes through the graph from the origin depot node 0 to the destination depot node n + 1 by following the order defined in sequence τ . Function increment on Line 5 is introduced for this purpose. For a given vertex i, list L(i) is constructed by adding a new label for every label in the list of labels of a predecessor node (Lines 6-13). The new label is simply defined by adding the arc cost (Line 8). In order to limit the number of labels generated in the lists as the procedure advance in the graph, some bounding mechanisms (Line 9) and a dominance rule (Line 10) are introduced. These two components are detailed below.

At the end, the shortest path is retrieved through a backtrack mechanism considering the best label found in L(n + 1). This shortest path constitutes the vehicle tour τ vehicl e and the nodes out of the path are assigned to the drone.

Dominance rule. The dominance rule is very

simple. A label L a = (c 1 a , c 2 a ) dominates a label L b = (c 1 b , c 2 b ) if (c 1 a < c 1 b and c 2 a ≤ c 2 b ) or (c 1 a ≤ c 1 b and c 2 a < c 2 b )
. Before adding a new label to a list of label, dominance tests are tried with all the labels in the list, both to check whether the new label should be discarded or if an existing label should be removed.

The dominance rule guarantees that the number of labels attached to a node is limited by the number of values that can take label components c 1 or c 2 . As this number can still be very large, bounding mechanisms are helpful to limit the combinatorial explosion.

Upper bound generation. The bounding mechanisms rely on the computation of several upper bounds. A first upper bound U B 1 is given by the value of the best solution found so far. A second upper bound U B 2 is obtained by applying Algorithm 2 with the following modifications:

• the bounding mechanisms of Line 9 are not considered;

• the dominance rule is changed to: L a dominates L b if c(L a ) ≤ c(L b ); with this new rule, a single label is kept at each node of the graph.

Algorithm 2 Procedure split(τ )

1: L(i) ← ∅ for 0 ≤ i ≤ n + 1 2: L(0) ← {(0, 0)} 3: i ← 0 4: while i < τ n + 1 do 5: increment i 6:
for all j such that arc (j, i) ∈ A τ do 7:

for all label L ∈ L(j) do 8:

L ′ ← (c 1 (L) + c 1 ji , c 2 (L) + c 2 ji ) 9:
if L ′ is not pruned with the bounding mechanisms then 10: The third upper bound U B 3 results from the following greedy heuristic. The nodes are considered in the order defined by < τ . Nodes are added to the vehicle tour τ vehicl e except when the two following conditions hold: node i is drone-eligible and adding i to the drone does not increase the completion time of the current partial solution. In this case, node i is assigned to the drone. U B is set as the best (minimal) upper bound among these three bounds: Lower bound generation. We introduce two lower bounds, LB t ot (i) and LB veh (i), at each customer node of the graph. Lower bound LB t ot (i) indicates the minimal total cost c 1 (P) + c 2 (P) of any path P between i and n + 1 in G τ . Lower bound LB veh (i) indicates the minimal vehicle cost c 1 (P) of any path P between i and n + 1 in G τ . Both bounds are computed simultaneously with a backward exploration of the acyclic (topologically-ordered) graph G τ . Bounding mechanisms. We define the three following bounding rules: LB veh (i): LB t ot (i):

L(i) ← addW ithDominance(L(i), L ′ )
U B = min(U B 1 , U B 2 , U B 3 ).
• R1: prune label L if c 2 (L) ≥ U B • R2: prune label L if c 1 (L) + LB veh (i) ≥ U B
Figure 6 Lower bounds for the graph of Figure 4.

• R3: prune label L if c 1 (L) + c 2 (L) + LB t ot (i) ≥ 2 × U B
Rule R1 identifies labels whose completion time is already at least U B, because of the customers already assigned to the drone. Rule R2 identifies labels whose vehicle tour cannot finish before U B, because of the subtour already assigned to the vehicle and the minimal remaining path to n + 1. Rule R3 considers both the vehicle and drone completion times. It is based on the fact that whatever the path P extending the subpath associated with L to n + 1, the completion time of the resulting solution is max(c 1 (L) + c 1 (P), c 2 (L) + c 2 (P)) ≥ c 1 (L)+c 1 (P )+c 2 (L)+c 2 (P )

2 ≥ c 1 (L)+c 2 (L)+LB t ot (i) 2 .
Hence, none of the labels for which R1, R2 or R3 holds, can result in a solution better than U B. They can be pruned.

Figure 7 illustrates the split subroutine on the graph presented in Figure 4. List L(i) is reported under every node i. In Figure 7(a), the bounding mechanisms are not applied. Labels can only be removed by dominance. Dominated labels are crossed out. In Figure 7(b), the bounding mechanisms are reinserted. The bounding rule(s) enabling to delete a label is reported on the right of the strikethrough label.

In both cases, the optimal path and the associated labels are represented in red. The optimal decomposition is to assign customer sequence (2, 4, 5) to the vehicle and customers (1, 3) to the drone. The cost of this solution is 29.

Decoding procedure when M > 1

When M > 1, the preceding decomposition scheme could naturally be adapted by defining labels of size M + 1, where the first field represents the vehicle cost and the following M fields represent the cost for each drone. This would however induce a more complex labeling algorithm and, above all, many more labels, with probably intractable computing times except for fairly small instances. We preferred to handle this situation with a different approach.

We reproduce exactly Algorithm 2 with the sole modification that arc costs c 2 i j are divided by M. This change simulates the fact that the total drone delivery time can be shared equally between the M drones. In other words, it also means that the PMS problem is relaxed, allowing both preemption of tasks and parallel execution of these tasks.

Sequence τ dr ones returned by procedure split is then transformed into a feasible PMS solution (τ opt 1 , . . . , τ opt M ) with a greedy heuristic. We propose to apply the well known Longest Processing Time (LPT) heuristic [START_REF] Weiss | Scheduling: Theory, Algorithms[END_REF]. In LPT, the tasks (drone deliveries) are first sorted in the decreasing order of their processing time ( d i ). Then, they are successively assigned to the drone with the minimal current completion time.

EXPERIMENTS AND RESULTS

We conducted two sets of experiments. In the first set, we evaluate the efficiency of our heuristic on Murray and Chu [START_REF] Chase | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF]'s benchmark instances and present some further analyzes. As far as we know, these instances are the only

Figure 7 Illustration of the split procedure on the graph of Figure 4, without or with the bounding mechanisms.

ones existing for this problem. Unfortunately, they are of small size (10 to 20 customers) and it is difficult to draw definitive conclusions with them. For this reason, we introduced instances of larger size on which we conducted a second set of experiments. In this second set, we investigate in more details the behavior of our heuristic and analyze the benefits of using drones.

The environment used for the computational work is Intel core(TM) i5-6200U CPU @ 2.30Ghz 2.40Ghz; 8GB RAM; Windows 10; 64 bits. C++ language is used for the implementation part.

For the experiments, we considered two different ways of applying our two-step heuristic:

(1) Single-start two-stepH: the algorithm is executed exactly as it is described in Section 4.

(2) Multi-start two-stepH: the algorithm is repeated several times, with a randomized initialization and until a time limit is reached. Randomization is introduced in the nearest neighbor heuristic, by randomly selecting one of the K closest neighbors instead of the closest. The solution returned is the best solution among all the solutions found. In the experiments, we arbitrarily set K = 3. The computing time limit depends on the experiments and is indicated when needed.

First set of experiments: Murray and Chu's instances

Murray and Chu [START_REF] Chase | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF]'s instances were generated with either 10 or 20 customers. The vehicle and drone speeds were fixed at the same speed of 25 miles/h. However, distances were computed with a Manhattan distance for the vehicle and with an Euclidean distance for the drones. The depot location was selected as being either near the center of all customers, near the edge of the customer region, or at the origin. Customer locations were generated such that either 20%, 40%, 60% or 80% of all customers were located within the drone's range from the depot, with the drone having a flight endurance of 30 min. Finally 10-20% of customers were arbitrarily set as not drone-eligible because of excessive parcel weights. Each of the above parameter settings was repeated 10 times, resulting in 120 instances with 10 customers and 120 instances with 20 customers. All these instances were solved with a single truck and either 1, 2 or 3 available UAVs, resulting in 720 test instances. For these instances, completion times are indicated in minutes.

Before analyzing the performance of our heuristic, let us recall the principle of Murray and Chu [START_REF] Chase | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF]'s PDSTSP heuristic. Their idea is to first assume that the drones will serve all the drone-eligible customers and that all remaining customers will be delivered by the vehicle. Based on this partition, a TSP and a PMS are solved for the vehicle and the drones, respectively. An improvement step reassigns individual customers to either a drone or the vehicle if it allows decreasing the overall completion time. This improvement step is implemented as follows. If the completion time for the drones exceeds the duration of the vehicle tour, a customer is moved from a drone to the vehicle. The move affording the greatest net savings is chosen. If no move yields a savings in the overall completion time a swap is investigated. The swap operator explores all pairwise exchanges of customers between the drones and the vehicle. If the completion time for the vehicle determines the overall completion time, the swap operator is again employed. The process of reallocating customers between the drones and the vehicle is repeated as long as improvements are carried out. Three TSP solution methods were evaluated for computing the vehicle tour, namely: integer programming (with the guarantee that the optimal TSP solution is obtained), the savings heuristic [START_REF] Lysgaard | Clarke & Wright's Savings Algorithm[END_REF], and the nearest neighbor heuristic. Similarly, two PMS solution methods were evaluated for the drones: integer programming (exact solution) and the longest processing time (LPT) heuristic [START_REF] Weiss | Scheduling: Theory, Algorithms[END_REF]. In Murray and Chu's experiments, mixed integer linear programs were solved with Gurobi version 5.6.0.

Table 3 presents a summary on the performance of our heuristics compared to Murray and Chu's. The first four lines correspond to Murray and Chu's methods. Note that we ignored the less efficient among their methods in this table . The fifth line provides information on the computation of exact solutions by Murray and Chu with their IP formulation. The results obtained with our two-step heuristic are presented for both single-start two-stepH and multi-start two-stepH, with a time limit of 3 seconds for the latter. Columns #Sol give the number of times each method found the best solution among all methods. Columns Gap give the average and maximal gaps to these best solutions, for each method. Columns Runtime report computing times, in seconds. Regarding best solutions, Murray and Chu [START_REF] Chase | The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[END_REF] indicate that their IP formulation was able to find the optimal solution for all of the 10-customer instances but was not able to solve in the imparted time 87 of the 360 20-customer instances. Column #Sol however shows that for these 87 instances, IP still found the best solution among all tried methods in all cases except 8.

We observe that the single-start version of the two-step heuristic and the Savings/LPT are both extremely fast. In comparable amounts of time, single-start two-stepH is able to achieve far better optimality gaps than Savings/LPT. Regarding the multi-start version, we can notice that with a time limit of only 3 seconds, the two-step heuristic yields very small optimality gaps. The IP/IP and IP/LPT methods are also effective but very slow. In general, this comparison shows that our two-step descent algorithm is able to converge very quickly towards very good solutions, at least for small instances with 10 or 20 customers. Table 4 and Table 5 show in more details the behavior of Multi-start two-stepH with 1, 2 or 3 drones for instances with 10 and 20 customers, respectively. 16 15 We notice that the average completion time value decreases when the number of drones increases. This is a logical expected result but it greatly depends on the number of drone-eligible customers and it is not always very significant. At some points, indeed, all the drone-eligible customers might be assigned to drones; then, if the vehicle tours is longer than drone tours, adding new drones does not help. Results also show that the split procedure is called 2 times on average. Seeing that our decoding scheme is optimal when M = 1 (a single drone) while it is not when M > 1, we could have also expected larger gaps for instances with several drones. This is however not clearly observed with these results, probably showing the quality of the approximation introduced in the multiple-drones case.

Second set of experiments: new instances generated from TSPLIB

To evaluate our heuristic on larger instances, we generated another set of instances by using TSPLIB files att48.tsp, berlin52.tsp, eil101.tsp, gr120.tsp, pr152.tsp and gr229.tsp. The number in the file name corresponds to the number of customers which are represented by their coordinates x and y. To stay consistent with Murray and Chu's instances, we used the Manhattan distance for the vehicle trip and the Euclidean distance for the drone trip. From each file, we generated what we call a reference instance and several instances that can be derived from this reference instance by changing some parameters. These instances are characterized by:

• The position of the depot: A fictitious point was added to represent the depot. The depot location was selected as being either near the center of all customers (x 0

= max i ∈N (x i )-min i ∈N (x i ) 2 , y 0 = max i ∈N (y i )-min i ∈N (y i ) 2
) or at the left-bottom corner of the region (x 0 = min i ∈N (x i ), y 0 = min i ∈N (y i )). In reference instances, the depot is located at the center.

• The percentage of drone-eligible customers: Instances were generated with either 0%, 20%, 40%, 60%, 80% or 100% of drone-eligible customers. We proceeded as follows. Let K be the target percentage of drone eligible customers. We introduced L (L = 30%) the percentage of non-drone-eligible customers that are not drone-eligible because of parcel weights. We selected these customers according to their index n: customers not drone-eligible because of their parcel weight are customers such that n (mod ⌊ 1 (1-K )×L ⌋) = 0. Remaining customers were then set as drone-eligible in the increasing order of their distance to the depot, until reaching K% of drone-eligible customers. In reference instances, K = 80%.

• The drone speed: The drone can go at the same speed as the vehicle or 2, 3, 4 or 5 times faster. In this case, vector d is simply divided by the speed factor. In the reference instances, the speed factor is 2. • The number of drones: The drone fleet can be composed of 1, 2, 3, 4 or 5 drones. In the reference instance, a single drone is used.

Note that the method for generating drone-eligible customers might appear a little bit twisted, but it has the advantage of being fully deterministic and easily reproducible.

The first goal with these new instances is to conduct some sensitivity analyzes. We compare solutions obtained while changing the depot position, the percentage of drone-eligible customers, the drone speed factor and the number of drones, respectively. For that purpose, we consider the 6 reference instances and construct new instances by changing a single parameter at a time. The method used for these experiments is Multi-start two-stepH with a time limit set to 5 minutes (a large amount of time is given so as to obtain optimality gaps as small as possible and make the results more reliable).

Results are presented in tables 6 to 9. In these tables, columns labeled with C.T. indicate the value of the completion time and columns labeled with #D.C. indicate the number of customers assigned to the drones. Table 6 investigates the impact of the depot location. We observe that completion times are higher when the depot is located at the left-bottom corner. Furthermore less customers are assigned to the drone. These observations are consistent with expectations. In complement to this table, we also investigate if the drones tend to serve customers near the depot, in other words if there are any "rules of thumb" that dictate which customers should be served by the drones. Figure 8 shows Table 7 investigates the impact of the percentage of drone-eligible customers. The table shows that, in general, completion times are improved when the percentage of drone-eligible customers increases. However, it does not necessarily imply that the number of customers assigned to the drone increases (except of course for the case with 0 drone-eligible customers). Actually, at first, when a few customers are drone-eligible, they tend to be assigned to the drone to relieves the vehicle. Then, when a good balance in vehicle and drone completion times is reached, two conflicting phenomena are met: adding drone-eligible customers allows a better partition of the customers between the vehicle and the drone, and thus should result in an higher number of drones visited per unit of time; but, it also allows decreasing completion times, and thus should result in a smaller total number of customers assigned to the drone. In Table 8 and Table 9, we vary the speed and number of drones, respectively. We can notice that when the speed of the drone increases, the completion time is improved and the drone is able to visit more customers. Similar results are obtained when increasing the number of drones. Actually, this is not a surprise seeing that in the algorithm, changing the speed or the number of drones almost has the same effect. For example, the only difference between solving an instance with 2 drones having a speed ratio 2 and an instance with 1 drone of speed ratio 4, concerns the solution of the PMS. However, one should mention that when the number of drones increases the average number of customers assigned to each drone decreases. Finally, in some cases, adding drones does not allow improving the solution, for the reasons already developed in Section 5.1 (see att48 and berlin52). With further experiments, we analyze the behavior of our two-step heuristic general scheme. For these experiments, we only consider the reference instance obtained from gr229.tsp and execute Single-start two-stepH. Results are presented in Tables 10 and11.

Table 10 presents the results obtained while varying the percentage of drone-eligible customers. It provides the value of the completion time, the average number of calls to the split procedure, the average number of labels generated in the split procedure (summed over all nodes and including labels eventually deleted by dominance or with the bounding mechanisms) and the percentage of labels deleted with the bounding mechanisms. Several interesting conclusions can be drawn from this table. First, one can observe an increase in the number of calls to the split procedure following that of the number of drone-eligible customers. It indicates that, thanks to the flexibility provided by the new drone-eligible customers, the method gets less easily trapped into a local optimum. However, the method still converges quickly (a few iterations) and towards good-quality solutions: the gaps with the solutions found in 5 minutes with Multi-start two-stepH (last line of Table 7) remain limited. Second, one can see a quick increase in the number of generated labels. It can clearly be explained by the shape of graph G τ . Having more drone-eligible customers favors longer arcs and result in more arcs in the graph, and thus more possibilities for extending labels. Fortunately, bounding mechanisms are capable of getting rid of most of these labels: more than 99% when all the customers are drone-eligible.

Table 11 investigates the quality of the approximation made in the split procedure when M > 1. It shows the average and maximum gaps between the drone completion time found by the split procedure (assuming a single drone with a speed multiplied by M) and the completion time obtained after having applied the LPT heuristic. We observe that the gaps grow when the number of drones increases, but remain very limited. Finally, with Table 12, we provide a benchmark set of best known solutions on our new instances, for future researches. In this table, we consider our 6 references instances with a drone fleet size going from 1 to 5 drones. It gives rise to a new instance set of 30 instances. The results provided in the table were obtained with a single execution of Multi-start two-stepH with a time limit of 5 minutes.

CONCLUSIONS

Drone deliveries look like the future: unmanned aerial vehicles rapidly delivering packages to our doors, eliminating both waiting times and the cost of human labor.

In this paper, we studied the combination of vehicle and drones for parcel delivery in a approach without synchronization between the vehicle and drones. We proposed an iterative two-steps heuristic that uses dynamic programming for efficiently partitioning the customers between the vehicle and the drone fleet. Results are very promising and permit a clear improvement over the existing literature.

Nevertheless, there are still a lot of possible improvements. First, we mainly focused in this study on the split procedure. Clearly the quality of the results could be slightly improved by solving better the PMS that are repeatedly solved in the solution scheme. In the current implementation, the algorithms used for solving these problems are very simple. They have the advantage to be very quick, but it is certainly possible to gain in effectiveness with a limited increase in computing times. Most importantly, the iterative algorithm could certainly beneficially be inserted within a metaheuristic scheme. Multi-start two-stepH can already be interpreted as a GRASP, but more promising metaheuristic schemes exist. Iterated Local search, or the hybridization with evolutionary algorithms, would for example be natural candidates.

Apart from these issues, another clear limit in the evaluation of our method is the lack of lower bounds (except for small instances for which the optimal solution is known). Developing an efficient solution method, as branch-and-cut or branch-and-price, or finding tight lower bounds is certainly an important direction to follow. Branch-and-cut solution procedures have been developed for other types of routing problems where a single truck selects and visits a subset of customers (e.g., the Selective TSP [START_REF] Gendreau | A branch-and-cut algorithm for the undirected selective traveling salesman problem[END_REF] or the Profitable Tour Problem [START_REF] Kehlet Jepsen | A branch-and-cut algorithm for the capacitated profitable tour problem[END_REF]). The valid inequalities and separation algorithms used in these procedures could certainly be generalized to our problem.

Finally, more complex variants of the problem would certainly deserve to be addressed. Especially, a strong limit in the problem definition is the presence of a single vehicle. Parcel delivery typically involves many vehicles. Extending the problem to this setting would certainly be valuable, though raising new difficulties in the partitioning subproblem.

Figure 1

 1 Figure 1 Amazon Prime Air (source: amazon.com)

Figure 2

 2 Figure 2 FSTSP: Illustration of the synchronization mechanism (source [19])

Figure 3 A

 3 Figure 3 A set of 10 customers served by 1 vehicle and 2 drones.

4 :

 4 (τ vehicl e , τ dr ones ) ← split(τ ) 5: τ opt vehicl e ← reoptimizeT SP(τ vehicl e )

  Drone cost vector d i

Figure 4

 4 Figure 4 Graph G τ for the instance of tables 2(a) and 2(b), with τ = (1, 2, 3, 4, 5).

Figure 5

 5 Figure 5 Upper bounds for the graph of Figure 4.

Figure 5

 5 Figure 5 represents the application of these algorithms to compute U B 2 and U B 3 on the example introduced with Figure 4. Assuming that no previous solution is known (U B 1 = +∞), we obtain U B 2 = 29, U B 3 = 42 and U B = 29.

Figure 6

 6 Figure 6 details these lower bounds on the example introduced with Figure 4.

Figure 8

 8 Figure 8 Results of the two-step heuristic for the 6 reference instances

  An iterative two-step heuristic for the Parallel Drone Scheduling Traveling Salesman Problem

													, ,
			8,16				8,12				6,20
	0	8,0	1	10,0	2	13,0	3	11,0	4	5,0	5	8,0	6

  end while 15: bestLabel ← label L in L(n + 1) with minimum completion time max(c 1 (L), c 2 (L)) 16: τ vehicl e ← path that led to label bestLabel 17: τ dr ones ← nodes that are not in the path

	11:	end if
	12:	end for
	13:	end for
	14: 0	8,0	1 8,16	10,0	2	13,0	3 8,12	11,0	4	5,0	5 6,20	8,0	6
	U B 2 :	(0,0)		(8,0)		(8,16)		(21,16)		(16,28)		(21,28)		(29,28)
	U B 3 :	(0,0)		(8,0)		(18,0)		(18,12)		(29,12)		(34,12)		(42,12)

  An iterative two-step heuristic for the Parallel Drone Scheduling Traveling Salesman Problem

													, ,
			8,16				8,12				6,20
	0	8,0	1	10,0	2	13,0	3	11,0	4	5,0	5	8,0	6
	22		24		14		17		6		8		0
	51		43		33		24		13		8		0

Table 3

 3 Comparison with Murray and Chu results

	Solution approach	10 Customers				20 Customers
		Gap (%)	Runtime (s)		Gap (%)	Runtime (s)
		Avg Max	Avg	Max	#Sol	Avg Max	Avg	Max	#Sol
	IP/IP	0.12 10.13	2.4856 29.97	299	0.31 23.47	495	21510	302
	IP/LPT	0.12 10.13	2.3093 28.85	300	0.41 23.47	498	21521	292
	Savings/IP	1.57 20.68	0.2373 8.26	209	3.57 18.83	3.721 80.68	87
	Savings/LPT	1.58 20.68	0.0003 0.01	209	3.98 18.83	0.008 0.07	80
	Exact (IP)		0.3194 2.02	360		77.775 180.00	352
	Single-start two-stepH	0.12 8.51	0.1660 0.32	278	0.51 23.47	0.210 0.56	225
	Multi-start two-stepH	0.02 4.45	3.2060 3.26	313	0.15 23.47	3.072 3.32	337

Table 4

 4 Multi-start two-stepH (time limit: 3 sec) performance on 10 customer instances

		1 drone 2 drones 3 drones
	AVG Gap (%) 0.00	0.05	0.00
	MAX Gap (%) 0.00	4.45	0.19
	AVG Obj.	114.07 105.09	91.90
	#SplitCall	2	2	2
	#Start (3 sec) 17	19	8

Table 5

 5 Multi-start two-stepH (time limit: 3 sec) performance on 20 customer instances

		1 drone 2 drones 3 drones
	AVG Gap (%) 0.20	0.06	0.18
	MAX Gap (%) 23.47	2.41	6.33
	AVG Obj.	141.90 139.93	139.82
	#SplitCall	2	2	2
	#Start (3 sec) 15

Table 6

 6 Impact of depot position (80% of drone-eligible customers, 1 drone, speed factor 2)

	Instance	Center		Corner
		C.T.	#D.C.	C.T.	#D.C.
	att48	29954	17	33798	9
	berlin52	6386.48	18	7830	8
	eil101	564	28	650	19
	gr120	1414	30	1730	18
	pr152	76008	20	76556	19
	gr229	1794.84	25	1913.74	9

Table 7

 7 Impact of the percentage of drone-eligible customers (depot at the center, 1 drone, speed factor 2)

	Instance	0%		20%		40%		60%		80%		100%
		C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.
	att48	42136	0	38662	7	31592	15	30788.80 16	29954	17	27784	16
	berlin52	9675	0	9350	4	8300	15	7410	25	6386.48 18	6180	14
	eil101	819	0	738	18	646	31	578	27	564	28	561.41 26
	gr120	2006	0	1736	18	1624	25	1494	29	1414	30	1414.80 23
	pr152	86596	0	82504	22	77372	23	76786	20	76008	20	74468	23
	gr229	2020.16 0	1862.76 19	1828.02 22	1807.50 23	1794.84 25	1498.05 11

Table 8

 8 Impact of the drone speed (depot at the center, 80% of drone-eligible customers, 1 drone)

	Instance	1		2		3		4		5
		C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.
	att48	33234 10	29954	17	29142	21	28686	24	28610	26
	berlin52	7450 13	6386.48 18	5656.56 23	5290.65 31	5190	35
	eil101	650	17	564	28	504	36	456	39	420.83 47
	gr120	1592 18	1414	30	1289.27 37	1189.71 43	1112	50
	pr152	80164 12	76008	20	72936	31	70412	41	67798	31
	gr229	1865 13	1794.84 25	1735.16 36	1679.33 48	1642.04 58

Table 9

 9 Impact of the number of drones (depot at the center, 80% of drone-eligible customers, speed factor 2)

	Instance	1		2		3		4		5
		C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.	C.T.	#D.C.
	att48	29954	17	28686	24	28610	26	28610	26	28610	27
	berlin52	6386.48 18	5299.81 31	5290	35	5190	35	5190	35
	eil101	564	28	456	40	395	52	346.68	59	319.74	69
	gr120	1414	30	1188.51 43	1044.65 54	946.04	65	880	73
	pr152	76008	20	70244	42	65062.10 41	60027.40 56	56336.10 60
	gr229	1794.84 25	1686.75 50	1603.90 66	1518.62 84	1483.68 98

Table 10

 10 Impact of the percentage of drone-eligible customers on the behavior of Single-start two-sepH (depot at the center, 1 drone, speed factor 2)

	Drone-eligible	C.T.	#SplitCall #LabelsGenerated. LabelsDeleted (%)
	0%	2020.16 0	0	0
	20%	1867.60 3	9450	28.26
	40%	1826.22 6	32969	53.10
	60%	1812.84 6	139849	76.85
	80%	1809.84 4	385309	88.43
	100%	1500.45 4	3662748	99.05

Table 11

 11 Average gap between the drone completion time found by the split procedure and the completion time found with the LPT heuristic

	Number of drones	1	2	3	4	5
	Avg Gap (%)	0	0.01	0.73	0.85	0.99
	Max Gap (%)	0	0.01	1.41	1.35	1.86

Table 12

 12 Benchmark based on reference instances with 1 to 5 drones applying Multi-start two-setpH with a time limit of 5 mins

		1	2	3	4	5
	att48	29954	28686	28610	28610	28610
	berlin52	6386.48	5299.81	5190	5190	5190
	eil101	564	456	395	346.68	319.74
	gr120	1414	1188.51	1044.65	946.04	880
	pr152	76008	70244	65062.10	60027.40	56336.10
	gr229	1794.84	1686.75	1603.90	1518.62	1483.68

ACKNOWLEDGMENTS

The authors would like to thank Chase Murray and Amanda Chu for providing their instances and their results.


Christine E Hellweg
email: christine.hellweg@dlr.de

Christa Baumstark-Khan

Claudia Schmitz

Patrick Lau

Matthias M Meier

Isabelle Testard

Thomas Berger

Günther Reitz

Dr. med. vet. Christine E Hellweg

Activation of the Nuclear Factor κB pathway by heavy ion beams of different linear energy transfer

Keywords: Nuclear Factor kB, linear energy transfer, heavy ion, space mission, relative biological effectiveness bcl-2, B-cell lymphoma 2, bcl-XL, B-cell lymphomaextra large, CDKN1A, Cyclin-dependent kinase inhibitor 1A, CHO, Chinese Hamster Ovary, CIMAP, Centre de

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The radiation environment that astronauts experience during spaceflight differs significantly to that found on Earth [START_REF] Straube | Operational radiation protection for astronauts and cosmonauts and correlated activities of ESA Medical Operations[END_REF]. Besides protons and a-particles, heavier nuclei are part of the radiation field encountered in space. Although heavy nuclei only make up about 2% of the fluence in space, they will account for much of the biological consequences due to their higher linear energy transfer (LET) [START_REF] Pecaut | The impact of mouse strain on iron ion radio-immune response of leukocyte populations[END_REF]. Primarily late tissue sequelae like genetic alterations, cancer and non-cancer effects are the potential risks resulting from radiation exposure in deep space [START_REF] Blakely | Biological effects of cosmic radiation: Deterministic and stochastic[END_REF]. Due to mass limitations for spacecrafts and production of secondary particles in shielding material, the radiation exposure cannot simply be avoided by radiation shielding of the spacecraft (National Council on Radiation Protection and Measurements [NCRP] 2006). The prolonged exposure to galactic cosmic rays requires extensive further study of the biological effects of these extraordinary radiation qualities and quantities in order to improve the estimation of health effects of radiation exposures on humans during and after exploration missions [START_REF] Cucinotta | Managing lunar and Mars mission radiation risks. Part 1: Cancer risks, uncertainties, and shielding effectiveness[END_REF], NCRP 2006[START_REF] Hellweg | Getting ready for the manned mission to Mars: The astronauts' risk from space radiation[END_REF].

In the cellular response to radiation, several sensors detect the induced DNA damage and trigger signal transduction pathways resulting in cell death or survival with or without certain amounts of remaining DNA damage (National Aeronautics and Space Administration (USA) [NASA] 2004, [START_REF] Ohnishi | Studies about space radiation promote new fields in radiation biology[END_REF]. Signal transduction leads to the activation of various transcription factors, resulting in the expression of certain genes whose protein products are involved in several possible outcomes, such as cell cycle arrest, allocating additional time for repair of the damaged DNA, cellular senescence or different types of cell death, if the damage is too severe and cannot be repaired.

An important transcription factor that is known to be activated by ionizing radiation is Nuclear Factor kB (NF-kB) [START_REF] Brach | Ionizing radiation induces expression and binding activity of the nuclear factor kappa B[END_REF]. The NF-kB/Rel (Reticuloendotheliosis) family (NF-kB1 (p50/p105), NF-kB2 (p52/p100), RelA (p65), RelB, and c-Rel) can be activated in response to many agents and is involved in regulation of proliferation, immune system development and performance, inflammation and apoptosis [START_REF] Barnes | Nuclear factor-kappaB: A pivotal transcription factor in chronic inflammatory diseases[END_REF][START_REF] Sonenshein | Rel/NF-kappa B transcription factors and the control of apoptosis[END_REF][START_REF] Wu | Inhibition of NF-kappaB/Rel induces apoptosis of murine B cells[END_REF]. Upon activation, the inhibitor of NF-kB (IkBa) that sequesters NF-kB in the cytoplasm [START_REF] Zabel | Nuclear uptake control of NF-kappa B by MAD-3, an I kappa B protein present in the nucleus[END_REF], is degraded by several proteases [START_REF] Alkalay | Stimulation-dependent I kappa B alpha phosphorylation marks the NF-kappa B inhibitor for degradation via the ubiquitin-proteasome pathway[END_REF] and the released NF-kB translocates to the nucleus and binds to kB DNA motifs (NF-kB response elements, NRE) initiating gene transcription. NRE have been identified in the promoter or enhancer regions of a number of growth factors, cytokines and adhesion molecules involved in fibrosis and inflammation [START_REF] Ghosh | NF-kappa B and Rel proteins: Evolutionarily conserved mediators of immune responses[END_REF]. In addition, NF-kB regulates the expression of many genes whose products are involved in the control of cell proliferation and cell death [START_REF] Baichwal | Activate NF-kappa B or die?[END_REF].

Exposure of human cells to energetic heavy ions allows simulation of an important component of the space radiation field, the heavy ion component of galactic cosmic radiation. Currently, experiments are mostly restricted to high-dose rate experiments due to limited beam time availability. Experiments at heavy ion accelerators with various cell lines and primary cells revealed a strong dependency of the relative biological effectiveness (RBE) for the investigated biological endpoint on the LET of the energetic heavy ions and on ion species, energy and charge (for example, [START_REF] Bird | Survival of synchronized Chinese hamster cells exposed to radiation of different linear-energy transfer[END_REF][START_REF] Stoll | Killing and mutation of Chinese hamster V79 cells exposed to accelerated oxygen and neon ions[END_REF][START_REF] Wulf | Heavy-ion effects on mammalian cells: Inactivation measurements with different cell lines[END_REF][START_REF] Yatagai | Mutations induced by heavy charged particles[END_REF]). For many biological endpoints, e.g., cell inactivation (for example, [START_REF] Blakely | Inactivation of human kidney cells by high-energy monoenergetic heavy-ion beams[END_REF], interphase death [START_REF] Sasaki | Dependence of induction of interphase death of Chinese hamster ovary cells exposed to accelerated heavy ions on linear energy transfer[END_REF], differentiation of fibroblasts [START_REF] Fournier | Changes of fibrosis-related parameters after high-and low-LET irradiation of fibroblasts[END_REF], mutation induction (for example, [START_REF] Cox | Mutation and inactivation of mammalian cells by various ionising radiations[END_REF], in vitro cell transformation [START_REF] Yang | Neoplastic cell transformation by heavy charged particles[END_REF], chromosomal aberrations [START_REF] Skarsgard | Survival, chromosome abnormalities, and recovery in heavy-ion and x-irradiated mammalian cells[END_REF] and tumor induction in vivo [START_REF] Alpen | Tumorigenic potential of high-Z, high-LET charged-particle radiations[END_REF]), a maximal RBE was reached with an LET from 90-230 keV/mm. The RBE for mutation induction was higher compared to the inactivation RBE for all examined LET values [START_REF] Yatagai | Mutations induced by heavy charged particles[END_REF].

There are several hints that the RBE for activation of signaling pathways by heavy ions may also depend on LET and ion species. Screening of gene expression in the nematode Caenorhabditis elegans suggests an LET or track structure dependence of the gene expression changes [START_REF] Nelson | Radiation-induced gene expression in the nematode Caenorhabditis elegans[END_REF]. In human lens epithelial cells, transcription and translation of Cyclin-dependent kinase inhibitor 1A (CDKN1A, Protein 21 Cyclin-dependent kinase 2-interacting protein 1, wild-type p53-activated fragment 1 , p21 CIP1/WAF1 ) are both temporally regulated after exposure to 4 Gy of high-energy accelerated iron-ion beams (∼ 150 keV/mm) as well as of protons (∼ 1 keV/mm) and X-rays, whereby the magnitude and kinetics of the expression enhancement seem to depend on the LET of the radiation [START_REF] Chang | Effects of iron ions, protons and X rays on human lens cell differentiation[END_REF]. Such an LET dependency is also suggested for accumulation of the tumor protein p53 (TP53) [START_REF] Fournier | Accumulation of the cell cycle regulators TP53 and CDKN1A (p21) in human fibroblasts after exposure to low-and high-LET radiation[END_REF].

For screening of the cellular NF-kB response, we developed a recombinant reporter cell line, HEK-pNF-kB-d2EGFP/Neo L2 [START_REF] Hellweg | Generation of stably transfected mammalian cell lines as fluorescent screening assay for NF-kappaB activation-dependent gene expression[END_REF]. These human embryonic kidney (HEK) cells harbor a plasmid which controls the expression of the destabilized variant of enhanced green fluorescent protein (d2EGFP) [START_REF] Li | Generation of destabilized green fluorescent protein as a transcription reporter[END_REF] as a reporter molecule by a synthetic promoter containing four NRE tandem copies. HEK cells are a useful tool to study many different processes in human cells, as they can easily be transiently and stably transfected. Many studies, including own investigations, have shown that the NF-kB pathway is functional in HEK cells (for example, [START_REF] Matsuda | Large-scale identification and characterization of human genes that activate NF-kappaB and MAPK signaling pathways[END_REF][START_REF] Hellweg | Activation of nuclear factor kappa B by different agents: Influence of culture conditions in a cell-based assay[END_REF][START_REF] Muscat | Coffee and Maillard products activate NF-kappaB in macrophages via H 2 O 2 production[END_REF][START_REF] Simon | Activation of NF-kappaB-dependent gene expression by Salmonella flagellins FliC and FljB[END_REF][START_REF] Rajagopal | The covalent modification and regulation of TLR8 in HEK-293 cells stimulated with imidazoquinoline agonists[END_REF]. Additionally, HEK cells express neuronal markers similar to that of neuronal stem cells [START_REF] Shaw | Preferential transformation of human neuronal cells by human adenoviruses and the origin of HEK 293 cells[END_REF][START_REF] Arnhold | Neuronal characteristics of amniotic fluid derived cells after adenoviral transformation[END_REF] and are therefore of interest for studying basic mechanisms of space radiation-induced cellular effects. In the recombinant cell system, activation of the cellular NF-kB pathway leads to binding of liberated NF-kB not only to its target genes but also to the synthetic promoter. Thus, the cells respond with increased transcription of d2EGFP, followed by translation and maturation of the protein. By that, it is possible to quantify NF-kB-dependent transcriptional activation in response to stimuli simply by measuring the yields of green fluorescence of the reporter protein. In order to overcome problems described for cell-based stable NF-kB-GFP reporter systems (El-Guendy and Sinai 2008), we have shown for the selected clone that the kinetics of activation of NF-kB dependent d2EGFP gene expression by tumor necrosis factor a (TNF-a) follows the nuclear translocation of the NF-kB subunit p65 [START_REF] Hellweg | Generation of stably transfected mammalian cell lines as fluorescent screening assay for NF-kappaB activation-dependent gene expression[END_REF] and that the response to DNA double-strand break inducing agents is intact [START_REF] Hellweg | Activation of nuclear factor kappa B by different agents: Influence of culture conditions in a cell-based assay[END_REF]). The dose-response curve for cytokines and several chemicals [START_REF] Hellweg | Activation of nuclear factor kappa B by different agents: Influence of culture conditions in a cell-based assay[END_REF]) could thus be followed using the HEK-pNF-kB-d2EGFP/Neo cells.

In previous studies, we have shown with this cell system that exposure to accelerated heavy ions (95 MeV/nucleon [MeV/n] -Ar, LET 272 keV/mm) results in stronger activation of NF-kB in human cells than X-ray exposure [START_REF] Baumstark-Khan | Cellular monitoring of the nuclear factor kappaB pathway for assessment of space environmental radiation[END_REF]. The NF-kB activation by energetic carbon ions (35 and 75 MeV/n, LET 73 and 33 keV/mm, respectively) was comparable to the effect induced by X-rays [START_REF] Hellweg | Carbon ion induced activation of the NF-kappaB pathway[END_REF], suggesting a narrow peak in the LET dependence of NF-kB activation. As this transcription factor is involved in regulation of apoptosis and immune and inflammatory response, its activation may influence the outcome of a heavy ion-exposed cell and therefore might be relevant for late effects which might occur after prolonged low-dose exposure during an interplanetary mission.

In this work, the influence of the LET of several accelerated heavy ions on activation of NF-kB dependent d2EGFP gene expression and on cellular survival was investigated. Here, we show that radiation qualities, which are relevant for space missions, are capable of activating the NF-kB pathway and that the activation threshold is in a space flight relevant fluence range for ions in the LET range of 91-272 keV/mm. Heavy ion-induced Nuclear Factor kB activation 3

Materials and methods

Cell culture

The cell line HEK 293 was established by [START_REF] Graham | Characteristics of a human cell line transformed by DNA from human adenovirus type 5[END_REF] from human embryonic kidney cells immortalized by transfection with sheared fragments of adenovirus type 5 DNA. The cells contain only the stably integrated region (E1a and E1b genes) of the human adenovirus genome and do not produce viral particles. Cells were obtained from the American Type Culture Collection (ATCC CRL-1573; now: LGC Standards, Wesel, Germany). Cloning of the plasmid pNF-kB-d2EGFP/ Neo, stable transfection and selection of an appropriate cell clone (HEK-pNF-kB-d2EGFP/Neo L2) was already described [START_REF] Hellweg | Generation of stably transfected mammalian cell lines as fluorescent screening assay for NF-kappaB activation-dependent gene expression[END_REF]. HEK-pNF-kB-d2EGFP/Neo L2 and untransfected HEK cells have comparable radiosensitivity to X-rays and to accelerated carbon ions and show no difference in proliferation [START_REF] Hellweg | Carbon ion induced activation of the NF-kappaB pathway[END_REF]. Cells were maintained in a-medium (Biochrom KG, Berlin, Germany) containing 1.5 mg/ml G418 and 10% fetal bovine serum (FBS) at standard conditions (37°C, 95% air and 5% CO 2 atmosphere). Cells were passaged every week and seeded in a cell density of 3  10 4 cells/cm 2 in 80 cm 2 cell culture flasks (Nunc, Novodirect, Kehl, Germany). Medium was exchanged after four days.

Treatment modalities

For cytokine treatment or irradiation experiments, 3  10 4 cells/cm 2 were seeded into suitable culture vessels freshly coated with poly-D-lysine (10 mg/cm 2 , Sigma-Aldrich Chemie, Steinheim, Germany) for 15 min followed by washing with phosphate buffered saline (PBS). For exposure to TNF-a, X-rays, 13 C, 22 Ne, 36 Ar, and 58 Ni ions, cells were seeded into 25 cm 2 flasks (Iwaki, Dunn Labortechnik GmbH, Asbach, Germany). For exposure to 208 Pb ions, cells were seeded into Petri dishes with a polytetrafluorethylene bottom (thickness 25 mm, Lumox ® , Greiner bio-one, Frickenhausen, Germany), since these ions could not penetrate the polystyrene bottom of standard culture flasks. Cells were incubated for two days before treatment. Control dishes were sham-treated.

Cytokine treatment

Human recombinant TNF-a was obtained from Sigma-Aldrich Chemie. TNF-a (final concentration 10 ng/ml), was dissolved in PBS, and added in serum-containing medium. Cells were harvested after 18 h for flow cytometry as described below.

X-irradiation

Cells in early exponential growth phase were irradiated at room temperature with 150 kV X-rays generated by an X-ray unit (Müller Typ MG 150, Philipps, Hamburg, Germany) yielding a dose rate of 1 Gy/min.

Heavy ion exposure

Irradiation with accelerated heavy ions was performed at the Grand Accélérateur National d'Ions Lourds (GANIL, Caen, France). Characteristics of the applied beams including the LET in water are shown in Table I. Adherent cells were irradiated in sub-confluent stage and in upright position at room temperature. Therefore, flasks and Petri dishes were completely filled with a-medium and closed. Petri dishes were wrapped with parafilm. Dose rates were adjusted to ∼ 1 Gy/min. Dosimetry was performed by the Centre de recherches sur les Ions, les Matériaux et la Photonique (CIMAP) / Laboratoire d'Accueil en Radiobiologie avec les Ions Accélérés (LARIA) staff at GANIL, yielding the fluence in particles/cm 2 (P/cm 2 ). To convert fluence (F) to the absorbed dose, the following formula was applied [START_REF] Wulf | Heavy-ion effects on mammalian cells: Inactivation measurements with different cell lines[END_REF]:

Dose [Gy] 5 1.6 5 10 29  LET [keV/mm]  F [P/cm 2 ] (1)

Colony forming ability

For survival experiments with X-rays and heavy ions, cells were seeded and irradiated as described previously. Immediately after irradiation cells were trypsinized and re-plated in six Petri dishes per dose. The cell density in the dishes was adjusted to compensate for the plating efficiency of the cell line and for the anticipated lethal effect of the radiation in order to allow growth of about 50 colonies per dish.

The cells were incubated for 21 days without medium change. The resulting colonies were stained with crystal violet (1 mg/ml in 3% formaldehyde solution, Sigma-Aldrich Chemie). Only colonies containing more than 50 cells were scored as survivors. The experiments were performed with six dishes per dose and repeated if beam time was available.

All data from the irradiated samples were fit by leastsquares linear regression analysis to lnS 5 ln(PE D /PE D 5 0 ) versus dose, where the natural logarithm of S is the survival and PE are the plating efficiencies of treated (PE D ) or untreated cells (PE D 5 0 ).

Flow cytometry

For measurement of d2EGFP, cells were harvested 18 h after radiation or cytokine treatment by trypsinization and fixed with 3 ml cold 3.5% formaldehyde in PBS. For flow cytometric analysis, cells were centrifuged and resuspended in PBS. Forward and sideward scatter and green fluorescence (FL-1) of 20,000 cells from the samples were measured in a FACScan (Becton Dickinson, San Jose, CA, USA) with an argon laser (488 nm) as excitation source. The markers d2EGFP (2) and d2EGFP () were set by means of untreated and TNF-a treated cells (Figure 2A). For comparison of NF-kB-dependent d2EGFP expression after exposure to different radiation qualities, the percentage of d2EGFP () cells in the treated samples was normalized to the percentage of the d2EGFP () cells in the corresponding mock-treated controls. HEK-pNF-kB-d2EGFP/Neo clone L2 cells after X-irradiation and after carbon ion exposure [START_REF] Hellweg | Carbon ion induced activation of the NF-kappaB pathway[END_REF]).

High-LET radiation exposure of HEK cells results in purely exponential survival curves (Figure 1A). Based on fluence, the cell killing potential strongly increases with LET up to 272 keV/mm. The increase of the killing effect from 272-9674 keV/mm is less prominent. Based on absorbed dose, heavy ions with an LET of 34-91 keV/mm are most efficient in cell killing, while radiation qualities with an LET above or below this range are less efficient in cell killing (Figure 1B). Lead ions with an extremely high LET are least efficient in reducing cellular survival. Exposure to X-rays resulted in a slightly shouldered survival curve (Figure 1B).

Calculation of relative biological effectiveness

The relative biological effectiveness (RBE) was calculated according to the formula: (2)

Fluences were converted to energy dose according to Equation (1). The reference radiation was 150 kV X-rays.

Survival

The D 0 , the reciprocal of the slope in the linear range of the survival curves, was used for RBE calculation. The D 0 was converted to absorbed dose for heavy ion exposure. The RBE for survival was calculated as follows:

RBE D reference radiation [Gy] D energetic heavy ion [Gy 0 0 Survival  ] ]
(3)

Activation of NF-kB dependent d2EGFP gene expression

Using Sigma Plot 2002 for Windows Version 8.02 (Systat Software GmbH, Erkrath, Germany), a regression was adapted to each dose effect curve of NF-kB dependent d2EGFP gene expression activation, based on the regression coefficient.

The doses initiating a doubling of the d2EGFP fluorescence in HEK-pNF-kB-d2EGFP/Neo L2 cells 18 h after irradiation were derived from the regression curves. These doses were used as indicator of the threshold for activation of NF-kB dependent d2EGFP gene expression. The RBE for NF-kB dependent d2EGFP gene expression was calculated by dividing according to formula (2) the absorbed dose [Gy] of the reference radiation that elicited a doubling of d2EGFP fluorescence 18 h after irradiation by the absorbed dose [Gy] of energetic heavy ions inducing the same biological effect.

Statistics

Each experiment was repeated up to five times depending on the availability of beam time with one to six replicates each. Beam time is very restricted and it was not possible to repeat the experiments in independent beam times for every ion analyzed in this work. In order to account for different numbers of replicates and repeats, the standard error was calculated. Means, standard errors and significance levels in the t test were calculated with Microsoft ® Office Excel 2003 (Microsoft Deutschland GmbH, München, Germany). The t-test can be used even with small sample sizes. Regression analyses were performed using SigmaPlot 2002.

Results

The effect of different energetic heavy ions on the NF-kB pathway was studied in human embryonic cells. Heavy ion fluences resulting in absorbed doses between 0.2 and 60 Gy, depending on the anticipated killing effect of the examined ion [START_REF] Stoll | Killing and mutation of Chinese hamster V79 cells exposed to accelerated oxygen and neon ions[END_REF], were selected for the experiments.

Survival of human embryonic cells after X-ray and after heavy ion exposure

There are no significant differences in the survival of untransfected HEK cells and stably transfected The D 0 indicating the fluence necessary to reduce survival of HEK cells to 37% first decreases, then increases with increasing LET. The D 0 ranges between 2.5  10 7 P/cm 2 (1.4 Gy) for 13 C ions (75 MeV/n), ∼ 2.2  10 6 P/cm 2 (3.1 Gy) for nickel ions and 1.2  10 6 P/cm 2 (18.2 Gy) for lead ions. These fluences result in average in 35.5, 3.1 and 1.5 hits per cell nucleus, respectively.

Induction of NF-kB dependent d2EGFP gene expression by exposure to different radiation qualities

Previous experiments with TNF-a and argon ions revealed that the maximal d2EGFP fluorescence (3-6 h are necessary for d2EGFP translation, transcription and maturation) occurs 12-24 h after treatment [START_REF] Hellweg | Generation of stably transfected mammalian cell lines as fluorescent screening assay for NF-kappaB activation-dependent gene expression[END_REF], 2005, Baumstark-Khan et al. 2005). Therefore, 18 h was chosen as intermediate time point. HEK-pNF-kB-d2EGFP/Neo cells responded to TNF-a (10 ng/ml) with a strong increase of d2EGFP fluorescence (∼ 60% positive cells at 18 h, Figure 2A).

As argon ions strongly activate the NF-kB pathway (see below), fluorescence histograms of d2EGFP expression are shown in detail for this ion. After exposure with 95 MeV/n argon ions (Figure 2B), an increase in d2EGFP fluorescence is observed already after exposure to the lowest fluence. Part of the cell population shows a very strong fluorescence increase, and this subpopulation increases dose-dependently. The rest of the population shows only a small increase in fluorescence which is slightly dose-dependent.

Radiation experiments using low-LET ionizing radiation (150 kV X-rays) and moderate LET (75 MeV/n 13 C ions) show a dose-dependent increase of NF-kB dependent d2EGFP fluorescence (Figure 3A).

The comparison of the activation of NF-kB dependent d2EGFP gene expression by radiation of different LET reveals the maximal potency for neon and argon ions (Figure 3B). In average, 2.4 argon ion hits per cell nucleus (0.7 Gy) result in doubling of NF-kB dependent d2EGFP gene expression. For nickel and lead ions, a significant increase of fluorescence occurs at doses above 3.6 Gy and 10.6 Gy, respectively (Figure 3C). Nickel ions activate NF-kB dependent d2EGFP expression to an extent comparable to X-rays, and lead ions have a lower activating potency than X-rays (Figure 3C). Much higher fluences are required for maximal induction of NF-kB dependent d2EGFP gene expression in HEK cells. Depending on the radiation quality, the maximal activation is provoked by energy doses above 10 Gy (carbon, neon, argon), above 15 Gy (nickel, X-rays) or above 60 Gy (lead). After argon ion exposure, the number of d2EGFP () cells decreases after reaching the maximum (Figure 3B), while after neon, nickel and lead ion exposure, the maximum is not reached in the examined dose range (Figure 3B,3C).

Relative biological effectiveness of different energetic heavy ions

The RBE for survival was calculated from the D 0 . For NF-kB activation, the dose in Gy exposure to which resulted in doubling of the d2EGFP fluorescence was chosen for RBE calculation, as not all curves reached a clear maximum, precluding the determination of the dose that initiated maximal res ponse. The maximal biological effect was observed between 91 und 272 keV/mm for the examined endpoints survival and activation of NF-kB dependent d2EGFP gene expression (Figure 4). The extent of the RBE strongly depends on the nature of effect. The highest relative biological effectiveness for induction of NF-kB dependent d2EGFP gene expression is 8.9 (Figure 4B), for reproductive cell death only around 2 (Figure 4A).

Discussion

In this study, we show that energetic argon ions (LET 272 keV/mm) and neon ions (LET 91 keV/mm) are most effective in activating NF-kB dependent d2EGFP gene expression in human embryonic kidney cells. Relative biological effectiveness for survival reduction also peaks in this LET range, but the RBE is much lower.

Clonogenic survival

The survival curves' exponential course without shoulder after heavy ion exposure conforms to previously published data for the survival of human mammary epithelial cells [START_REF] Durante | Effects of alpha-particles on survival and chromosomal aber rat ions in human mammary epithelial cells[END_REF], human kidney cells (T-1) [START_REF] Yang | Response of cultured mammalian cells to accelerated krypton particles[END_REF], melanoma and Chinese Hamster Ovary (CHO) cells [START_REF] Bird | Survival of synchronized Chinese hamster cells exposed to radiation of different linear-energy transfer[END_REF] and CHO V79 cells [START_REF] Stoll | Killing and mutation of Chinese hamster V79 cells exposed to accelerated oxygen and neon ions[END_REF]. The analysis of cell death of glioblastoma cell lines after exposure to high LET carbon beams by the colony forming ability test revealed an LET dependent decrease in survival fraction [START_REF] Tsuchida | Cell death induced by high-linear-energy transfer carbon beams in human glioblastoma cell lines[END_REF]. Such an LET dependence of reproductive cell death was also observed in human fibroblasts [START_REF] Hamada | LET-dependent survival of irradiated normal human fibroblasts and their descendents[END_REF]. Also in this work, the fluences necessary for cell inactivation were dependent on the LET of the examined heavy ion beams. The higher the LET, the lower were the fluences to achieve the same killing effect. Based on dose, the relationship is more complex, with a maximal killing Figure 3. Dose effect relationships for activation of NF-kB-dependent d2EGFP gene expression after exposure to X-rays or to various energetic heavy ions, as detected in stably transfected HEK cells by the reporter gene d2EGFP controlled by the promoter containing four NRE and the minimal promoter of TK (HEK-pNF-kB-d2EGFP/Neo L2). Cells were harvested and fixed for flow cytometric analysis 18 h after treatment. Doses (Gy) were calculated from fluences (P/cm 2 ) according to Equation (1). Means and standard deviations of one to five independent experiments (X-rays: 5; 36 Ar: 4; 13 C, 58 Ni: 2; 22 Ne, 208 Pb: 1) with 3-6 samples per dose are shown. Significance compared to the mock-irradiated control: * p  0.05, ** p  0.01, *** p  0.001 (for X-rays only shown in A). MeV/n 5 MeV/nucleon. effect in the range of 34-91 keV/mm, as the fluences are weighted with the respective LET for conversion to absorbed dose according to Equation (1).

Activation of the NF-kB pathway by different energetic heavy ions

Our first study examining the effects of heavy ions on the NF-kB pathway revealed that high LET argon ions (272 keV/mm) activate the sequence of all events in the NF-kB pathway from DNA binding via transcription to protein translation and maturation [START_REF] Baumstark-Khan | Cellular monitoring of the nuclear factor kappaB pathway for assessment of space environmental radiation[END_REF]. Here, the LET dependence of this cellular response to heavy ion exposure was examined. Argon ions (272 keV/mm) have the maximal potency to activate NF-kB dependent d2EGFP gene expression in HEK cells. Neon ions (91 keV/mm) have a strong potency for NF-kB activation, and the maximal response was not reached in the examined dose range.

In line with the results presented here, other groups report NF-kB translocation after exposure of normal human monocytes (MM6 cells) to 0.7 Gy of 56 Fe ions using a DNA binding assay [START_REF] Natarajan | Posttranslational modification of I-kappa B alpha activates NF-kappa B in human monocytes exposed to 56 Fe ions[END_REF]. This clearly indicates that high LET iron ion exposure induces rapid and persistent NF-kB Heavy ion-induced Nuclear Factor kB activation 7 irradiation [START_REF] Mitra | Expression of NF-kappaB and ERK following heavy ion irradiation[END_REF]). NF-kB p65 expression was enhanced by 12 C ion exposure 8 h after 0.1 Gy and already 3 h after 1 Gy [START_REF] Mitra | Alteration in the expression of signaling parameters following carbon ion irradiation[END_REF]. Together with the half-life of the reporter protein d2EGFP, this enhanced NF-kB availability might explain the sustained NF-kB dependent d2EGFP gene expression which was observed 18 h after heavy ion exposure. Up-regulation of NF-kB activating cytokines such as interleukins and tumor necrosis factor might also play a role in perpetuating the NF-kB activation. The DNA-dependent protein kinase (DNA-PK) and phosphatidyl inositol kinase 3 (PI3 kinase) inhibitor Wortmannin (10 mmol/l) enhanced the 12 C ion-induced expression of NF-kB [START_REF] Mitra | Alteration in the expression of signaling parameters following carbon ion irradiation[END_REF]. In oral squamous cell carcinoma cells, a microarray analysis after carbon and neon ion (LET ∼ 75 keV/mm; 1, 4, 7 Gy) irradiation revealed no significant gene expression changes in the NF-kB signaling pathway [START_REF] Fushimi | Susceptible genes and molecular pathways related to heavy ion irradiation in oral squamous cell carcinoma cells[END_REF]. Whether the lack of inducible NF-kB activation is specific for these cancer cells, e.g., because of a constitutively highly active NF-kB pathway [START_REF] Nakayama | High expression levels of nuclear factor kappaB, IkappaB kinase alpha and Akt kinase in squamous cell carcinoma of the oral cavity[END_REF][START_REF] Tamatani | Enhanced IkappaB kinase activity is responsible for the augmented activity of NF-kappaB in human head and neck carcinoma cells[END_REF][START_REF] Bindhu | High expression levels of nuclear factor kappa B and gelatinases in the tumorigenesis of oral squamous cell carcinoma[END_REF], or if methodological differences are responsible for the contrary results, it remains to be determined.

The appearance of two populations in the d2EGFP histogram after argon ion exposure might be explained by two different processes: The population with the strong fluorescence increase shows high d2EGFP expression in response to binding of liberated NF-kB to the synthetic promoter of the stably transfected reporter construct. The subpopulation showing only a very small shift towards higher fluorescence intensities might result from radiation-induced cell cycle arrest, during which d2EGFP continues to accumulate without 'dilution' by cell division. Such a shift was described for UVC-irradiated stably transfected Chinese Hamster Ovary Cells that constitutively expressed EGFP [START_REF] Baumstark-Khan | Green Fluorescent Protein (GFP) as a marker for cell viability after UV irradiation[END_REF]. The threshold for the d2EGFP () cells was set above this subpopulation, in order to exclude possibly unspecific d2EGFP fluorescence.

As activation of the NF-kB pathway is supposed to play a role in the negative regulation of apoptosis, survival of cells with residual DNA damage might thus be favored. Even if this happens only in a small fraction of irradiated cells, it might be important for the initiation or promotion of cancer. Such effects which may be related to better survival of exposed cells through transitory induction of genes involved in maintaining DNA fidelity and in modulating cell-cycle progression and cell-death, would contribute considerably to astronauts' radiation risk, especially at low doses [START_REF] Williams | Predicting cancer rates in astronauts from animal carcinogenesis studies and cellular markers[END_REF].

Enhanced expression of cytokines and extracellular matrix proteases which are regulated by NF-kB after heavy ion exposure might also contribute to the remodeling of extracellular matrix that is observed after particle irradiation (NCRP 2006). Activation of NF-kB by high radiation doses (1-10 Gy) could contribute to the inflammatory response observed, e.g., in the developing brain after radiation exposure [START_REF] Monje | Inflammatory blockade restores adult hippocampal neurogenesis[END_REF].

Relative biological effectiveness of different energetic heavy ions

In this work, the maximal biological effect for the two examined endpoints peaks between 91 and 272 keV/mm. As mentioned activation. This activation of NF-kB was shown to be mediated through phosphorylation of IkBa and the subsequent proteasome-dependent degradation pathway. The iron study only revealed binding of NF-kB to its consensus sequence of 5′-GGGGACTTTCC-3′, and not transcriptional activation. [START_REF] Mitra | Expression of NF-kappaB and ERK following heavy ion irradiation[END_REF][START_REF] Mitra | Alteration in the expression of signaling parameters following carbon ion irradiation[END_REF] determined that the expression of the transcription factor NF-kB itself is influenced by 16 O and 12 C ion exposure (LET not published) in CHO V79 cells. Exposure to 16 O ions first decreased p65 expression as detected by Western blot 0.5 and 2 h after irradiation, with a recovery slightly over the initial cellular p65 content 4 h after The maximal relative biological effectiveness strongly depends on the nature of the effect and the cell type. As found in this work, the RBE for activation of NF-kB dependent d2EGFP gene expression is around 9, for reproductive cell death only around 2. The RBE for reproductive cell death is very similar to the RBE for DNA double-strand break induction (∼ 1.8) by energetic heavy ions [START_REF] Löbrich | Non-random distribution of DNA double-strand breaks induced by particle irradiation[END_REF][START_REF] Whalen | Specific ATM-mediated phosphorylation dependent on radiation quality[END_REF]. The RBE for survival also depends on the survival level used for its calculation, and its maximum was described to range between 2 and 4 [START_REF] Blakely | Heavy-ion radiobiology: Cellular studies[END_REF][START_REF] Alpen | Tumorigenic potential of high-Z, high-LET charged-particle radiations[END_REF][START_REF] Tsuruoka | LET and ion species dependence for cell killing in normal human skin fibroblasts[END_REF][START_REF] Hamada | LET-dependent survival of irradiated normal human fibroblasts and their descendents[END_REF]. For LET values above 900 keV/mm, RBE values for reproductive cell death drop below 1, which is in line with observations by [START_REF] Tolkendorf | Effect of ionizing-radiation of different linear energy-transfer on the induction of cellular death and of chromosome-aberrations in cells of the Chinese-hamster[END_REF], [START_REF] Wulf | Heavy-ion effects on mammalian cells: Inactivation measurements with different cell lines[END_REF] and [START_REF] Fournier | Changes of fibrosis-related parameters after high-and low-LET irradiation of fibroblasts[END_REF]. This overkill effect is explained by an increase in the degree of clustering of the initial physical damage within the target area with an increasing LET. It is seen as cause for the appearance of non-hit cells and the decrease in the mean number of lethal damage per unit dose, resulting in the decrease of RBE for cell killing [START_REF] Mehnati | Exploration of "over kill effect" of high-LET Ar-and Fe-ions by evaluating the fraction of non-hit cell and interphase death[END_REF].

Assuming that NF-kB activation promotes survival, it can be hypothesized that the extreme capacity of energetic heavy ions in the LET range of 90-300 keV/mm to activate NF-kB's transcriptional effects might be responsible for the lower relative effectiveness in cell killing observed in this range. Above 300 keV/mm the overkill effect possibly results in a decrease of the relative biological effectiveness.

Under these aspects, one can ask how can activated NF-kB influence the survival of heavy ion-irradiated cells? Possible pro-survival genes that might be transcribed at a higher rate are the inhibitor of apoptosis protein genes (IAP), and other anti-apoptotic genes such as bcl-2 (B-cell lymphoma 2), bcl-XL (B-cell lymphoma-extra large) and survivin. Preliminary experiments by Gong et al. have shown that high-LET radiation has a higher potential to activate survivin expression compared to low-LET radiation [START_REF] Gong | Heavy ion beams induce survivin expression in human hepatoma SMMC-7721 cells more effectively than X-rays[END_REF][START_REF] Jin | Survivin expressions in human hepatoma HepG2 cells exposed to ionizing radiation of different LET[END_REF].

The small numbers of particle tracks per cell nucleus -in the narrow LET range where the RBE reaches its maximumwhich are necessary to activate NF-kB suggest that NF-kB activation might be relevant for judging the biological effects of heavy ion exposures during long-term space missions. Availability of more sensitive methods to screen NF-kB activation in large sample numbers might enlarge this LET range.

The LET dependence of NF-kB activation found in this work might suggest that a differential activation of cellular signaling pathways by different radiation qualities could contribute to the underlying causes of the LET dependency of biological endpoints such as cell inactivation and mutation or chromosomal aberration induction.

RBE

  Absorbed dose of reference radiation inducing biological effe  c ct [Gy] Absorbed dose of test radiation inducing biological effect [ [Gy]

Figure 1 .

 1 Figure1. Clonogenic survival after exposure of HEK-pNF-kB-d2EGFP/ Neo cells to X-rays or to heavy ions, as fluence-effect curves (A) and dose-effect curves (B). HEK-pNF-kB-d2EGFP/Neo cells were exposed to 150 kV X-rays or to accelerated carbon, neon, argon, nickel or lead ions (A, B). Survival was determined by the colony forming ability test (CFA). Irradiated cells were seeded in Petri dishes. Grown colonies were fixed and stained after 14-21 days incubation. Data of one to five experiments were combined (X-rays: 5; 36 Ar: 3; 13 C,58 Ni, 208 Pb: 2; 22 Ne: 1); bars show standard error of up to 30 Petri dishes (5-6 per dose per independent experiment). P/cm 2 5 particles/cm 2 , MeV/n 5 MeV/nucleon.

Figure 2 .

 2 Figure 2. Activation of NF-kB-dependent d2EGFP gene expression by tumor necrosis factor a (TNF-a) and by high LET radiation, as detected in stably transfected HEK cells from d2EGFP reporter gene expression controlled by a promoter containing four NRE and the minimal promoter of thymidine kinase (TK) (HEK-pNF-kB-d2EGFP/ Neo clone L2). Cells were harvested and fixed for flow cytometry 18 h after treatment. Histogram overlays of representative flow cytometric analyses are shown in A and B. As positive control for activation of NF-kB dependent d2EGFP gene expression, cells were treated with 10 ng/ml TNF-a (A). An overlay of d2EGFP fluorescence histograms of cells exposed to 36 Ar ions (95 MeV/n, LET 272 keV/mm) is shown in B.Fluences were converted to absorbed doses according to Equation (1). P/cm 2 5 particles/cm 2 .

Figure 4 .

 4 Figure 4. Relative Biological Effectiveness (RBE) of energetic ions of different LET in inducing reproductive cell death (A), as measured by colony forming ability, and in activating NF-kB dependent d2EGFP gene expression (B). 150 kV X-rays were used as reference radiation and RBE was calculated according to Equation (2). The D 0 as descriptor of the survival curves was converted to energy dose for heavy ion exposure (A). The fluences eliciting a doubling of the NF-kB-dependent fluorescence signal were converted to absorbed dose (B). Means and standard errors for one to five beam times per radiation quality with six replicates are shown (Number of beam times: X-rays: 5; 36 Ar: 4, 13 C, 58 Ni, 208 Pb: 2; 22 Ne: 1). * Significant difference to the X-ray induced cellular response with p  0.05, ** with p  0.01, or *** with p  0.001. MeV/n 5 MeV/nucleon.

Table I .

 I Characteristics of the heavy ion beams. Effective irradiation energy at the cell monolayer after the energy losses in two detectors, the exit window, ∼ 1 cm air and the bottom of the culture vessel (1200 mm polystyrene or 25 mm polytetrafluoroethylene foil).

		Energy (MeV/n) a	LET (keV/mm)	Penetration
	Ion species	beam	on target b	in H 2 O	depth (mm)
	Carbon ( 13 C)	75.0	71.4	34.2	15120
	Neon ( 22 Ne)	80.0	74.5	91.2	10000
	Argon ( 36 Ar)	95.0	83.8	271.5	6336
	Nickel ( 58 Ni)	75.0	54.1	905.9	2092
	Lead ( 208 Pb)	29.2	19.5	9674.0	368

a MeV/nucleon; b

Acknowledgements

We thank Dr Hermann Rothard and all the physicists of CIMAP (Caen, France) involved in dosimetry and the beam operator team at GANIL for providing us valuable advice and Heavy ion-induced Nuclear Factor kB activation 9

LARIA, Laboratoire d'Accueil en Radiobiologie avec les Ions Accélérés; LET, linear energy transfer; MeV/n, Mega electron Volt per nucleon; NASA, National Aeronautics and Space Administration (USA); NCRP, National Council on Radiation Protection and Measurements; NF-kB, Nuclear Factor kB; RBE,

many help given during numerous night shifts at the French Heavy Ion Accelerator GANIL. The travel costs to the GANIL were supported in part by the European Union (EURONS). Luis Spitta, Melanie Thelen, Dimitri Ott, Britta Langen, Rebecca Ruland, Kristina Koch, Yueyuan Hu, Arif Ali Chishti and Sebastian Feles are acknowledged for their valuable help during beam times at GANIL.

Declaration of interest

The authors report no conflicts of interest. The authors alone are responsible for the content and writing of the paper.

Notice of correction

This paper published online on 6 July 2011 contained an error. Figure 1 A was published twice instead of Figure 1B. This current version of the paper is the correct version. The publisher would like to apologize for the inconvenience caused.