Rafael Elizondo

Victor Parada

Lorena Pradenas

Christian Artigues

An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport

Keywords:

Operation management of underground passenger transport systems is associated with combinatorial optimization problems (known as crew and train scheduling and rostering) which belong to the np-hard class of problems. Therefore, their resolution in real situations is generally addressed using heuristic methods. This paper considers the duty generation problem, which consists of identifying an optimal trips set that the conductors should complete in a labor day. With regard to the operational and labor conditions, the trains should be driven with the lowest number of conductors and a minimized total idle time between trips. The problem is modeled and solved using a constructive hybrid approach, which has the advantage of visualizing a solution construction similar to the approach typically used by operators who manually solve the problem. This approach takes advantage of the benefits offered by evolutionary methods, which hardly store a candidate solutions population in each stage, controlling in this way the combinatorial explosion of possible solutions. The results that we obtained for problems with similar characteristics to those that are performed manually in the Santiago Metro System were compared with two alternative approaches based on tabu search and a greedy method. The hybrid method produced similar results to those generated by the tabu search, and both found better results than the greedy method.

INTRODUCTION

The conductor's activities' planning for passenger vehicles presents a complex decision-making scenario. Operations managers face the tough task of finding a feasible solution from the large number of possible combinations that should be considered. This type of operations is also related to combinatorial optimization and np-hardness, and consequently the search for efficient methods providing continuous resolution continues to be a challenge. Once efficient algorithmic methods are found, computational tools can be built which will allow managers to make rapid decisions with flexibility and efficacy.

Additionally, they will be able to simulate new demand scenarios, new facilities, and changes in labor conditions.

Crew scheduling problems emerge in the management of cargo and passenger transport, such as airlines, buses, and trains. These kind of problems typically have been approached by reduction to three main steps [START_REF] Caprara | A global method for crew planning in railway applications[END_REF]: train movement programming, duty generation, and conductor service assignment (rostering). A complete operational programming is generated when these three steps are solved.

The first step consists of timetable generation, which specifies train movement between the start and finish locations for each trip. This definition should consider the demand for trips that exist between the different network origins and destinations, the facilities available, and an adequate balance between service quality and operating cost. The result will be the generation of a set of trips that should be performed during the day.

Each trip is defined by the train number, start time and location, and the finish time and location.

Once the timetable is generated, the second step is to generate conductor duties, which are the feasible subsets of trips that can be performed by a single conductor. In the third step, each generated duty is associated to a conductor, considering homogenous rotation of the conductors to the duties in a longer programming period as well as additional activities such as: free days, vacations, weekends, training periods, etc. The final result is weekly or monthly programming.

Since the seventies, the crew scheduling problem has been widely studied for the case of airlines. However, in the case of surface passenger transport, the majority of the studies have been concentrated in the last few years [START_REF] Ernst | An annotated bibliography of personnel scheduling and rostering[END_REF]. Commonly, the study of these problems considers the three previously described steps separately. Meanwhile, attempts have been made to address the problem using a single model and consequently, simultaneously solving it using a single method. In this line of work, [START_REF] Freling | An overview of models and techniques for integrating vehicle and crew scheduling[END_REF] and [START_REF] Freling | Models and algorithms for integration of vehicle and crew scheduling[END_REF] analyzed the benefits of the integrated versus the independent perspective for each problem.

Although their proposal is applicable to real problems, leading towards a decision-making support system [START_REF] Freling | A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm[END_REF], the partial benefit that is obtained appears dependent on the flexibility to change the vehicles on duty. The authors have used the embedded column generation method in a branch-and-bound method to generate exact solutions [START_REF] Friberg | An exact branch and cut algorithm for the vehicle and crew scheduling problem[END_REF]. However, the combinatorial degree of these problems requires the use of approximation in order to solve real large-size problems [START_REF] Haase | Simultaneous vehicle and crew scheduling in urban mass transit systems[END_REF]. The partial improvements of the integrated perspective versus independent perspective has also been verified by other authors: [START_REF] Gaffi | An integrated approach to ex-urban crew and vehicle scheduling[END_REF] studied the problem that emerged in public transport using a heuristic method based on lagrangean relaxation. Several computational tools for the crew scheduling problem in large train systems have been developed. The Italian [START_REF] Caprara | Algorithms for railway crew management[END_REF]1999) and Australian [START_REF] Ernst | An integrated optimization model for train crew management[END_REF] railway systems have been addressed using binary programming. In the first case, the model also considered vehicle assignment using branch-and-cut as a solution method. In the second one, large size problems have been addressed incorporating rostering for each depot existing in the network. Heuristic column generation-based procedures have been proposed to solve the crew pairing problem in the large German railway system [START_REF] Bengtsson | Railway crew pairing optimization[END_REF] The Portuguese and Dutch train systems have been studied with an interactive perspective based on artificial intelligence techniques [START_REF] Morgado | Scheduling and Managing Crew in the Portuguese Railways[END_REF][START_REF] Morgado | CREWS_NS -Scheduling train crews in the Netherlands[END_REF]. The user can propose a solution or modify a generated solution following a set of heuristic rules. To model the transport systems of Singapore and Hong Kong, an integration between graphic problem resolution and heuristic methods was used [START_REF] Chew | An optimization based approach to the train operator scheduling problem at Singapore MRT[END_REF].

The problem has also been studied for mass transit and buses. For the case of buses, Lourenco et al. l (2001) and [START_REF] Dias | Genetic algorithms for the bus driver scheduling problem: a case study[END_REF] developed decision support systems based in genetic and tabu search algorithms.

The real situation presented by subterranean metro train transport has unique characteristics that make it different from urban surface transport systems and from longdistance cargo-and-passenger train systems. For example, in the subterranean transport of passengers, the exchanges of conductors is established in a way that they can only be carried out in some predefined stations and adequately implemented to receive the conductors that should wait there to carry out their next work or their meal break. In general, in the surface transport of passengers, the change of operators can be accomplished at any point on the route, thus in the transport of passengers by bus lines, it is possible to assign a unit operator-duty-bus which includes in addition to the trips, the reception and delivery of the vehicle at the parking depot, as also for the suspensions of service for the resupply of fuel. This type of assignment is not possible with subterranean passenger trains. From an algorithmic point of view, the underground passenger transport problem has been little explored. In a particular case, [START_REF] Cavique | Subgraph ejection chains and tabu search for the crew scheduling problem[END_REF] propose the use of a heuristic search to minimize the number of necessary duties for a determined planning period in the Lisbon underground. They describe a constructive algorithm that, with less computer time, obtains slightly worse solutions than those generated manually for real-size problems; however, the two most elaborated methods based on tabu search find better results in terms of solution quality but require a higher computer time.

In the situation above, as in many other problems in combinatorial optimization, constructive methods have been used principally to generate initial solutions, and in a second stage the search is performed with another method. The advantage of these methods lies in the speed of solution generation, which is possible because they perform an important pruning in the space of possible combinations as they construct the solution.

A constructive algorithm for a combinatorial optimization problem can be viewed as a graph search process in problem-solving [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]. In such an area, a graph representing all possible problem states (nodes) is used to systematically explore the search space. Several methods have been developed to find a goal when starting from an initial node [START_REF] Pearl | Intelligent Search Strategies for Computer Problem Solving[END_REF], looking to reduce the number of visited nodes by pruning part of the search space. If the domain that contains all the possible solutions of a combinatorial optimization problem is represented by a "space state graph" [START_REF] Pearl | Intelligent Search Strategies for Computer Problem Solving[END_REF], then the "search space methods" may be used to navigate the domain of the solutions of the optimization problem. Additionally, metaheuristic methods have been widely used in the last few years to solve many combinatorial optimization problems.

In this paper, we combine the two frameworks mentioned above generating a hybrid algorithm that gradually builds and stores only part of the total possible combinations in order to solve the crew scheduling problem (CSP) that emerges during the second step of the passenger transport operational programming. In short, trips are gradually combined to build duties, and simultaneously duties are combined to produce a complete crew schedule.

In Section 1 the problem is presented and in Section 2, three different approaches to solve the problem are described, while in Section 3 the results attained for real-size problems associated with the Santiago Metro are presented. Finally, the main conclusions and comments of the study are presented.

DESCRIPTION OF THE PROBLEM

The CSP considers the following characteristics in this study:

• Relief facilities: Some of the stations in the network have the installations required by conductors who are waiting for their next trip, resting, or having a meal break. Typically, these are the last stations on each line; however, there can be intermediate stations with relief facilities.

• Maximum conduction time. Each duty must respect the limiting value for the total amount of time that each conductor can drive a train each day excluding breaks.

• Continuous conduction time. Each duty must consider a maximum value of continuous conduction time, i.e. the maximum amount of time a conductor can drive without stepping down from the train.

• Meal breaks. Each duty should contain a predefined time interval for meals.

When considering all the duties, the meal breaks should be homogenously distributed in the duties.

• Work shifts. In order to cover the service time of a work day, several work shifts are required. These shifts are covered by a set of full-time and part-time conductors. Full-time conductors should perform their duties until a certain time, after which the activities should be performed by part-time conductors. In this way, a set of duties should be generated for each group of workers, considering each shift's start time as problem data.

• Conductors as passengers. A conductor can begin a trip in a relief station different from where his/her last trip ended. Therefore, the conductor can travel as a passenger in a train in order to arrive to another station before his/her next trip begins.

• Routes. The transport network contains several different lines; however, trips of distinct lines cannot be assigned to a single duty.

• Conduction interruptions. An interruption is the minimum interval of time that should exist between two consecutive trips in a duty. At the end of each trip and in certain relief stations, a conductor can make certain maneuvers in order to conduct the train to the first station of his/her next trip. A set of distinct interruptions are allowed during one day. For example, the interruption for the interval of 7:00-8:00 a.m. can be two minutes, while the interruption for the time interval 13:00-14:00 can be one minute. If the time interval that occurs between two trips of a same duty surpasses a given interruption, then the extra time of the interruption is considered as part of the rest or idle time. If not, it is considered as continuous conduction time.

Then, the problem consists in finding a feasible solution that generates the lowest number of duties with least total idle time.

Let N = {τ 1 , τ 3 ,…,τ n } be a set of n trips that need to be completed during the programming period. For each trip k, the vector (s k , e k , o k, d k ), denotes the start time, the finish time, the trip origin and trip destination. Figure 1 visually describes the problem; in 1a), the trips are organized around the x axis, which indicates the time of each programming day. A feasible duty d k consists in a set of trips that can be made by a conductor satisfying all the problem constraints presented in the previous section. A solution x for the problem is identified by its set of duties N(x). A solution is feasible if it is composed by feasible duties (Figure 1b). A feasible duty contains trips, rest periods, a meal break, interruptions, and idle time. The total duty time is obtained by adding all the time periods of the duty.

Insert Figure 1 about here

MODEL AND SOLUTION WITH EVOLUTIONARY AND CONSTRUCTIVE METHOD

State space representations, originally defined to represent problem solving in artificial intelligence, are useful tools to interpret search processes in combinatorial spaces such as those that typically emerge in combinatorial optimization. To represent a state space, a graph characterizes all the possible transitions (arcs) between the different problem states (nodes). With adequate use of a search method, a path between the initial given state and a pre-defined goal state can be identified. Therefore, the problem solution is made up of the sequence of steps to reach the goal-state from the initial state, characterizing a path or a subgraph on the graph. To perform this process, several algorithms have been generated based in depth-first and breadth-first searches while using problem information to guide the process [START_REF] Pearl | Intelligent Search Strategies for Computer Problem Solving[END_REF].

The heuristic resolution of a combinatorial optimization problem can be tackled with two types of methods: constructive and solution space. In evolutive methods, a solution is built step by step from a set of initial elements. During this process, partial solutions are added each time, producing more complex structures. In the second case, the search takes place directly in a space containing all the possible solutions. From an initial solution, a random or deterministic exploration strategy allows a feasible space exploration.

The search process ends when the optimal or a good solution is found. Both constructive and solution space methods can be represented as a search graph similar to those that emerge in the problem-solving area. The main difficulty that both search methods in problem-solving and the combinatorial optimization methods have in solving np-hard problems is the large amount of computer time required to find a good solution. To avoid this difficulty, the natural, implicit pruning scheme embedded in an evolutionary method may be considered to reduce the number of generated structures that need to be stored during the evolutionary construction [START_REF] Chaudhry | Application of genetic algorithms in production and operations management: a review[END_REF]. Thus, gradually building several solutions and storing them in populations allow us to propose an evolutionary, constructive algorithm to solve combinatorial optimization problems. In [START_REF] Parada | A hybrid algorithm for the nonguillotine cutting problem[END_REF], we defined the corresponding operators and numerically tested several of these ideas by solving a cutting stock problem.

In each stage, our method updates a population of partial constructions A(t) to generate A(t+1) as occurs in the evolutionary methods (Figure 2 ). With equation (1) a set A'(t) is obtained, formed of the best individuals m which constitute A(t), denoted by c j , where j=1,2,…, m. The partial constructions obtained are submitted to three crossover operations. The first follows the constructive approach, allowing the elements of A'(t) to combine with the original elements, which in this case correspond to the original trips represented in Figure 2 as set E. In the second, the combinations between the actual constructions are allowed; while in the third, following the evolutionary approach, the individuals of A'(t) are combined with the best structures that are found during the search process, i.e., with the elite set B(t). Subsequently, the mutation is performed (modules M in Figure 2), generating a set of partial constructions (C). Following the roulette method, the best solutions from C are selected to finally form the population A(t+1). B(t) is updated by deterministically selecting individuals from C (Algorithm 1).

A'(t) = {c j ; f(c j ) = min f(c i ); ∀ i ∈ A(t); j = 1,2,…, m} (1)
The fitness of the partial constructions is evaluated using the evaluation function

(2), where g(node) is a measure of the cost to generate the construction node and h(node) is an estimate of the cost that needs to be paid in the search constructive process until the solution of minimum f is obtained. The manner in which g(node) and h(node)are calculated will be discussed in detail in this paper.

f(node) = g(node) + h(node) (2)
In Algorithm 1, the pruning produced by the evolutionary components of the algorithm does not guarantee beforehand an optimal solution. However, when the random components of the algorithm are removed, and without considering a limit for population and set size, the procedure becomes an intelligent problem-solving search algorithm like the best first search algorithm described in [START_REF] Pearl | Intelligent Search Strategies for Computer Problem Solving[END_REF]. On the other hand, once a population A(t) has been obtained with its individuals being solutions of the problem, that is to say solutions that contain all of the trips, the algorithm transforms into a genetic algorithm.

Algorithm

f(c i ) = g(c i ) + h(c i ) ∀ c i ∈ C; Update B(t); A(t+1) ← probabilistic selection of best individuals of C; Until a termination criterion is satisfied; End.
Algorithm 1 requires the definition of some parameters such as: the number of elements of A'(t) which is determined as a fraction (f s ) of the number of elements in A(t) and denoted as n a ; the size of B(t) denoted as n b ; and the mutation probability p m .

Insert Figure 2 about here Representation of the crew scheduling problem requires the definition of a construction and an operator in order to generate a new construction based on a pair of given constructions. A construction is defined by the set of duties, where a duty is defined by a combination of trips.

Let's consider a partial construction x = {d 1 ,…,d k } defined as a set of duties. Two constructions x a and x b are combined to generate two new constructions x' a and x' b (Figure 3 ). Initially x' a is obtained copying the duties of x a . Then, all feasible trip insertions from x b into x' a are performed. When no other feasible insertion is possible, new empty duties are sequentially generated in x' a in order to fit all the remaining trips of x b into x a . The process is complete when all the trips of x a and x b are contained in the duties of x' a . A similar stage sequence gives x' b . The feasible insertion of a trip into a duty takes into account all the problem constraints, with the exception that all of the trips are being considered.

In figure 3 , an example of the crossover operator considering 3 duties with 9 different trips in each one is represented. In this example, trips 10 and 15 are inserted in the third duty of x' a , while trip 12 is inserted in the second duty of x' a . Two other new duties for x' a are generated with the remaining trips. Similarly, the second child x' b is obtained.

Insert Figure 3 about here The mutation of a new trip is performed as well with a feasible insertion of a trip not yet contained in the construction, but following a mutation probability p m . A random number between 0 and 1 is generated for each construction, and if this number is smaller than p m , then a feasible insertion of a new trip proceeds.

The constructive and evolutionary procedure continues until all of trips are included in the set of duties. Note that different work shifts can be easily considered by first separating the set of trips according to each trip's start time and then independently executing the algorithm.

The evolutionary process is conducted by the fitness function f(x), as defined in (2).

Both terms should fundamentally minimize idle time and the number of duties, noting that while the lower the idle time between each pair of trips, the higher the available time to fit another trip in the duty. On the other hand, a lower number of duties does not necessarily mean lower idle time. The objective is to minimize the number of duties so that each duty is as complete as possible with respect to the conductor's work day. In short, the duties must have the greatest number of possible trips, and consequently the smallest amount of idle time between each pair of trips. Therefore, idle time between tasks should also be minimized. Optimizing only the number of duties favors the generation of duties with high intermediate idle times, creating conductor discomfort. However, the exclusive minimization of idle time can generate an extreme case: lots of duties but some with only a few trips.

Two types of idle time were identified: internal idle time (t in ) consists of time between trips and external idle time (t ex ) corresponds to the interval between the end time of the duty's last trip and that work day's end time. Thus, total idle time of a duty is given by t i = t in + t ex . Therefore the total idle time t(x), of a construction x, is given by:

∑ = i t x t ) ( (3
) The generation cost g(x) of a construction x is related to idle time t(x) and the number of duties N(x) belonging to it according to (4). Parameter α produces unit homogenization and weighting of both objectives. The algorithm's goal should be to contain all the trips grouped into the smallest number of duties and with the least amount of idle time possible. According to the construction operator's structure, the goal can be constructed from any construction x.

g(x) = t(x) + α N(x) (4)
Let t'(x) be an estimate of the idle time still to be considered to reach the goal node.

Let N'(x) be an estimate of the number of duties in the goal construction. Thus, h(x) is defined according to (5), which represents an approximation of the total cost of the goal construction reachable from x.

h(x) = t'(x) + α N'(x)
(5) Where:

T MD : maximum conduction time for a conductor, Thus, N'(x) is obtained considering the number of trips still to be assigned to any duty of the construction x as an estimate of the number of trips that can be contained in duty (4, 5).

T T x N n x N MD ) ( ) ( ' - = (6) n T T n j j / 1 ∑ = = (7)
In the same way, t'(x) is obtained from N'(x) and the minimum idle time that can be obtained in a duty, i.e. the difference between the length of a conductor's work day and the time effectively used in conduction (8).

)

)( ( ' ) ( ' T T T T x N x t MD       - = (8)
In an evolutionary algorithm, the complexity is determined multiplying the number of elemental operations required by the algorithm in each stage by the number of generations, which will depend on the solution precision required. However, the constructive nature of algorithm 1 provides prior information on the limit for the number of generations. Indeed, in the worst case, each new construction contains at least one trip more than were contained in the preceding constructions. In other words, the algorithm evolves constructing more complete solutions each time, until generating a population of complete constructions, which requires at most n generations, which requires at most n 2 elementary operations. Consequently a "good" heuristics solution requires around n 3 elementary operations.

SOLUTION USING OTHER TWO METHODS

Tabu Search Method (TSM).

The tabu search method (TSM) is a metaheuristic method that has been widely used in combinatorial optimization. The technique consists of a set of tools that facilitate the search for the optimal solution to the problem. In each stage, the neighborhood of the current solution is visited to search for a solution that lets the process continue advancing.

The history of the path followed is considered to be an important source of information to proceed in the most effective and economic direction.

A detailed description of this methodology is found in [START_REF] Glover | Manuel Tabu Search[END_REF]. To use this technique in a given problem, the following elements need to be identified: the structure that represents a problem solution, the rule that locates a neighbor solution in the actual solution, the way to measure the objective to be optimized, and an initial solution.

For the CSP, we represent a solution in the manner presented in section 2, with the modification that all the trips are contained in each solution x visited. Its evaluation is performed according to (4). To represent the neighborhood, an exchange operation needs to be defined. Let two duties be d i and d j such as in ( 9) and ( 10) with number of trips u and v, respectively.

d i = {τ i1 , τ i2 ,..., τ il , τ i,l+1 ,..., τ iu } (9) d j = {τ j1 , τ j2 ,..., τ jm , τ j,m+1 ,..., τ jv } (10)
An exchange operation is defined between two duties d i and d j as the feasible exchange between some of the trips. To this end, the trips τ il of duty d i and the trips τ jm of duty d j are identified, generating two new duties ( 11) and ( 12), d i ' and d j '. The exchange is identified by: m(d i , d j , τ il , τ jm ).

d i ' = {τ i1 , τ i2 ,..., τ il , τ j,m+1 ,..., τ jv } (11) d j ' = {τ j1 , τ j2 ,..., τ jm , τ i,l+1 ,..., τ iu } (12)
To obtain a solution x', neighbor of the current solution, we apply an exchange operation to a pair of duties of x. Thus, considering all the pairs of duties for a solution, a maximum of n 3 (n-1) neighbor solutions can be generated. We consider the best_neighbor(x) procedure that determines the best solution x' reviewing all the possible exchanges. The last q exchanges made m 1 , m 2 ,…,m q are stored in a tabu list in order to avoid the return of already visited solutions. Therefore, best_neighbor(x) considers feasible exchanges that do not imply the return to already visited solutions. A tabu move is considered applicable, except when it leads effectively to a solution that has yet to be visited. The tabu list is fifo (first in, first out), and consequently as the search process advances, the moves that entered first are the first ones eliminated. The tabu status of a move is always removed when the value of the new generated solution is better than the best values found up to that iteration in the search.

To generate an initial solution x 0 from an ordered list of n trips, n duties are constructed, where each one contains one of the n trips. Let t si and t ei be the start and finish time for each duty. Then t si = s i and t ei = e i , i = 1,…,n. We define a feasible concatenation operation as the incorporation into a duty of the only trip that contains another duty. In this way, if d i = {τ i1 , ...,τ iu } and d j = {τ j1 }, then d i Θ d j generates d i = {τ i1 , ...,τ iu , τ j1 }. In algorithm 2, x 0 is generated, concatenating as many duties as possible. A concatenation is considered feasible when it satisfies problem constraints.

Algorithm 2: Concatenation. Input: trip list, parameters, and constraints. Output: x 0 . Begin L ← {τ 1 , τ 2 , ...,τ n } in ascending order of s k ;

d i = {τ i } ∀ i = 1,…,n; x =(d i ) ∀ i ; t si = s i ; ∀ i = 1,…,n; t ei = e i ; ∀ i = 1,…,n; i = 1; l = i+1; Repeat Repeat Determine k; t sk = min{( t sj -t ei ), j = l, n} ∆ i = t sk -t ei ; If ∆ i ≥ h then d i = d i Θ d k ; Eliminate d k ; t ei = e k ; l = k +1; Else l = l +1; Until l = n; i = i +1; Until i = n;
x 0 ← reordered list of duties. End.

In the TS, the intensification strategy is used to review promising regions that had already been partially visited by periodically updating a list of solutions considered to be promising. These are solutions from which a continuous drop of the objective function can be obtained during a set number of iterations (5 in this case). The list of promising solutions acts with a FIFO order and have a pre-defined size. The function Intensify (L, x f ) found a new solution x f from which the normal search continued. The intensification is activated after T i iterations have occurred without the modifying best solution obtained until then.

Diversification is a strategy that permits a tabu search to visit a previously unconsidered region. With this objective, a new solution is configured based on the actual solution, increasing the number of duties. To do this, a set that contains the duties with the largest number of trips is selected. Each of these duties is separated in the middle point, generating two new duties. This increase is performed after T d iterations have occurred without finding a better solution. Algorithm 3 describes the resulting complete tabu search procedure.

Algorithm 3: Tabu Search Method.

Input: Trip list, parameters and constraints. Output: Duties. Begin Generate x 0 ; Define T i and T d ; t 1 = 0; t lch = 0;

x c = x best = x 0 ; For Iter = 0 to Maxiter do x' = best_neighbor(x c );

x c = x'; If f(x') < f(x best ) then x best = x' ; t lch = Iter; Else If Iter -t lch > T d then Diversify(x c , x f ); x c = x f ; Si f(x c ) < f(x best ) then x best = x c ; t lch = Iter; Else If Iter -t lch > T i then Intensify(L, x f ); x c = x f ; If f(x f ) < f(x best ) then x best = x f ; t lch = Iter; End.

Greedy Method (GM)

Consider a tree enumerating all the feasible combinations of trips to generate a duty.

The root node does not have included trips, and the next node level has duties that contain a pair of assigned trips. The intermediate nodes contain duties without all the trips having been assigned. The leaf nodes of this tree correspond to solutions of the problem in which each trip is assigned to some duty. Therefore, a constructive algorithm for the CSP can be obtained by identifying a way to find a path from the origin node to a leaf node. Algorithm 2 finds a path on this tree aiming to accumulate minimal idle time. The next node in a path is obtained incorporating a new trip to a duty in the earliest time possible.

The algorithm constructs sequentially a set of duties through feasible insertions of the trips. Initially, the trips are ordered in ascendant order according to the start time. In any stage of the algorithm, a duty is constructed by reviewing one by one the remaining trips and inserting them in a feasible manner until no new insertion is possible. Figure 4 presents an example of the construction strategy. In the upper part, the trips are presented ordered by start time, while the lower part presents the three duties obtained from those trips. The first duty is built with trips 1, 3, 5 and 8, leaving the trips 2, 4, 6, 7 and 9, which will be distributed to the other two duties in the next two stages.

Insert Figure 4 about here Meal break assignment in each duty is performed in a randomly weighted manner so that the assignment has the greater probability to occur where the amount of the duty's conduction time is greatest.

In algorithm 4, the function next_in_L obtains the first element of the ordered list L and insertion(τ l , d(m)) returns true when it is feasible to insert τ l in the duty d(m).

; m = 0; Repeat m = m + 1; l = 0;
and λ. Fixing two parameters, the third was tuned, beginning with t 1 and finishing with λ.

As a result of this process, T i = 250, T d = 350 and λ = 17 were obtained.

Figure 5 shows the evolution of the algorithm through the best construction of each generation A(t). The minimum of f(node) corresponds to the largest number of "good" duties generated, i.e. duties containing the maximum number of trips. After such point, f(node) due to the increase difficulty of produce good duties waiting to be assigned. When there are few trips remaining in each construction, it is not possible to generate duties as good as the first ones. The function h(node) has linear behavior since, in calculating the remaining number of duties to generate, only trips that have not yet been assigned to any duty are considered. This number diminishes linearly as the iterative process increases.

The staggered behavior of g(node) is due to the gradual generation of new duties that emerge when it is not possible to incorporate a new trip into the already existing duties.

Insert Figure 5 about here

The speed of the greedy algorithm to complete its job can be appreciated in Table 1;

the computacional time required does not exceed two seconds and in all cases is less than the time required for TSM as well as EM. In turn, EM is faster than TSM in the ten cases studied.

The bicriterial nature of the problem studied in this paper can be seen to break down the objective function in its two components: idle time and number of duties. In this line of reasoning, it is found that TSM outperforms EM in the instances Pr2, Pr3, Pr7 and Pr9.

The number of duties is directly related to the number of train conductors required daily, while the idle time is related to the degree of concentration of duties and consequently with the quality of work of the conductors. The manner of considering both elements depends on each company: in this study both criteria have been considered

equally and the results obtained in six of the cases studied, EM solves the problem with a fewer number of conductors to fulfull the daily programming.

Insert Table 1 about here 5. CONCLUSIONS In this paper, we proposed methods to address operation management problems which emerge in underground passenger transport. The first method proposed is based on the gradual solution construction by recurring to evolutionary methods. The generation of partial constructions is represented by an And / Or graph. The graph of the constructions is implicitly generated, following a scheme similar to that used by the evolutive algorithms, selecting in each stage a set that constitutes a population of constructions. Furthermore, the space state representation used as described in this paper is a useful tool to visualize any constructive algorithmic scheme. Under the framework described in this paper, such methods can be analyzed with the purpose of determining an admissible heuristic function that, at the same time, is an exactitude measurement. As a consequence, it is possible to identify theoretically the needed modifications in order to get an exact, instead of a heuristic, method.

The EM and TSM provide better results than the GM in terms of the number of duties. However, in terms of idle time, the TSM provides better results than the other two methods.

It is suggested to address this problem as a multiobjective optimization in future investigations.

  T j : Duration of trip j, T: Duration a conductor's work day.

  FIGURE 3An example of the constructive operator

  The complexity of this algorithm is determined by the 2 cycles. When both are executed n times, then the complexity is O(n 2 )

	Algorithm 4: Greedy Method
	Input: Trip list, parameters and constraints.
	Output: Duties.
	Begin
	L ← {τ 1 , τ 2 , ...,τ n } in ascendant order of s k

TABLE 1

 1 Comparison of Results.

				EA			TS			GRA
	Problem N° of	N° of	Idle time	Run	N° of	Idle time	Run	N° of	Idle time	Run
		trips	Duties	[h:m:s]	time	Duties	[h:m:s]	time	Duties	[h:m:s]	time
					[m:s]			[m:s]			[m:s]
	P 1	733	82.8 163:26:54 01:04	86	102:38:05 07:46	87.4	132:6:30 00:02
	P 2	437	37.0 71:04:43 00:10	31	49:29:05 01:35	33.6	60:23:37 00:01
	P 3	475	44.0 62:55:02 00:17	38	59:13:52 02:08	42.4	58:55:50 00:01
	P 4	281	150.0 158:11:45 00:07	174	46:54:11 02:28	153.0 26:49:06 00:01
	P 5	733	117.4 197:47:42 01:45	121	101:32:31 40:00	135.0 152:32:43 00:01
	P 6	779	92.4 221:04:06 01:22	156	19:52:58 19:09	98.4	79:47:59 00:02
	P 7	697	74.6 155:35:07 00:59	74	79:23:53 07:24	98.4 141:29:00 00:01
	P 8	900	108.8 216:15:54 02:38	193	38:29:31 30:07	114.6 73:50:59 00:02
	P 9	764	132.8 174:32:11 01:42	121	41:48:11 45:00	139.8 121:14:38 00:01
	P 10	797	95.0 215:19:14 01:24	179	58:27:31 40:00	107.0 66:33:53 00:02

Acknowledgments

The authors would like to thank two anonymous referees and an associate editor that helped greatly in improving the paper. The second author was supported by The Millennium Scientific Institute Chile: Complex Engineering Systems. The third author was supported by Project C-13955/18-Fundación Andes; Project 204.097.007-1.0 -UDEC and Project II-0457-FA-FCD-FI-FC-ALFA.

Repeat

RESULTS

The algorithms were executed in a computer with a 950 Mhz Athlon processor and 256 Mb RAM. Each instance was executed 5 times for both EA and GRA and the results correspond to the average values. The ten problems considered in this study correspond to a real situation that contains trips to be assigned in a work day. For example the problem Pr 1 has 733 trips, 3 relief stations and 58 trains; Pr 2 has 475 trips with two relief stations and 18 trains; Pr 3 has 437 trips, 2 relief stations and 22 trains. Two work shifts are considered, the first from 6:00 AM to 2:30 PM, the second from 2: 00 PM to 10:00 PM. Partial time conductors can be assigned at any moment during the day.

A parameter calibration experiment was performed for algorithm 1 using the problems Pr 2 and Pr 3 . An approximate range for each parameter was identified from preliminary executions of the algorithm. Subsequently, the best set of parameters was defined within those ranges. The decision was made based on the best performance of the ones measured in terms of f(node). Thus, the established parameters are n a = 10, n b =5, f s = 0.2 and p m = 0.02.

Similarly, a parameter-tuning experiment was performed for TSM. Using a set of preliminary executions to solve Pr 1 , a range of best performance was determined for T i , T d


Alice Corbet

Jan Záhořík

Edited Byjean-Nicolas Bach

Jon Abbink

Stéphane Ancel

Azza Ahmed

Abdel Aziz

Emanuele Fantini

Patrick Ferras

Hassan Mwakimako

Clélie Nallet

Aleksi Ylönen

MIGRATION WITHIN THE HORN OF AFRICA New trends

Introduction

The Horn of Africa is one of the most fragile and vulnerable regions in Africa, if not in the whole world. All countries involved have had experience with some form of civil war, internal political turbulences, cross-border violence, weak institutions, economic decline, and subsequent waves of migration. Therefore, it is not surprising that the region has become one of the hot spots for migration in the eyes of the European Union and other relevant actors and organizations. However, due to both internal changes and international and global pressures, we can observe new trends in migration within the Horn of Africa.

Mobility as a concept in the Western media is almost automatically associated with the migration of people from the Middle East and Africa to Europe, in what is usually labeled as the 'migration crisis'. However, mobility is a much broader and multi-dimensional phenomenon, one that is as old as the history of mankind. First of all, mobility inside Africa by far exceeds movement of people from Africa to Europe. Second, mobility needs to be also see in a broader historical perspective as a phenomenon that changes, transforms, and evolves depending on both internal and external contexts.

The effects of mobility can be framed as being twofold. First, mobility is caused by multiple factors: the environment, labor opportunities, political reasons, the search for education opportunities, family reconciliation, etc. Second, the mobility of people reshapes the whole society and even cross-border relations between states and administrative regions / units. Even if the latter is twofold because of the way in which states and institutions affect societies has an obvious impact on mobility as well, for instance, due to economic policies, oppression, etc. Indeed, some states try to limit migration, either by offering alternative solutions to populations, especially economic ones, or by preventing displacement, often in an authoritarian and policed manner.

The twofold direction of mobility (the in-flow and out-flow of goods, knowledge, people, and information) can also be studied from a variety of other perspectives, being closely linked to the issue of sustainable development with its ecological, social, and economic aspects, 1 remittances, 2 governance, 3 adaptive strategies, 4 restricted knowledge and maneuvers, 5 the impact of modernization and technology on the societies being discussed. The main interlinking issues that are closely connected with mobility and globalization are the processes of cross-border cooperation, urbanization, and the search for education and more specifically higher education. Generally, higher education institutions have a universal appeal, and globalization, primarily via technology, has made the transfer and mobility of knowledge and information easier. Urban spaces are important to figure out the trends as they can be seen either as islands of privilege or as concentrations of massive deprivation. 10 Big cities, for example, Khartoum, Addis Ababa, and Nairobi, certainly have better access to wealth and the advantages of globalization, such as the international labor market, technologies, and infrastructure. However, at the same time, the urban poor live in extremely miserable conditions in overcrowded shanty towns or precarious districts with high prices charged for basic commodities such as food and housing.

11

Nonetheless, these trends are changing due to the connections that are being established between local institutional responses and global opportunities. When it comes to cross-border connectivity, we can see historically changing borders (more than in any other region in Africa of a comparable size) and different patterns of cooperation or hostility. As we focus here on regional (Horn of Africa) border connections, Ethiopia serves as a good example, since it shares borders with all other states within the wider Horn of Africa region. Other countries of origin of refugees, whether as a result of civil wars or droughts evolving in intensity over time, are Somalia, Southern Sudan and Darfur, Eritrea, making the Horn of Africa an area of restricted mobility. Despite the official closure of borders by governmental institutions, such as between Eritrea and Ethiopia, local-level cross-border connectivity continues uninterrupted, as can be seen in the constant migration of people from Eritrea to Ethiopia and back.

12 The post-Cold War period also witnessed the enormous rise of new opportunities for workers from the region, who in large numbers began to seek out job opportunities in the rich Gulf States, Europe, Asia, and the United States. [START_REF] Fargues | Skilful Survivals. Irregular Migration to the Gulf[END_REF] Different types of migration can evolve according to the political situation and the presence of economic opportunities: seasonal (related to the Sudanese 'gold rush', for example, or Ethiopian farmers working in Eastern Sudan around Gedareff), the numerous types of economic and political migration that press Ethiopians and Eritreans to come and work in Sudan, or again the thousands of female Ethiopian workers who leave to take up employment in the Gulf States 14 calling to mind the incredible airlift set up by the Saudi authorities in 2013 to return some 200,000 undocumented Ethiopian workers to Ethiopia within a matter of weeks. [START_REF] De | Deported Before Experiencing the Good Sides of Migration: Ethiopians Returning from Saudi Arabia[END_REF] On the issue of return, we can observe another dimension of the 'reshaping' of the Horn of Africa because, most often, the emphasis has been placed on mobility as a one-way process that starts at one point and ends at another. But the idea of mobility, in a very broad sense, i.e. the circulation of people or knowledge, information, images, ideas, as well as capital and resources, has not been researched extensively. We focus on mobility as a two-sided process that leads to losses and at the same time to gains. In doing so, we remember that mobility trajectories are not always linear: the journey can stop at some point, in order to work and get money, or if plans change with a shelter, a wedding, etc. Thus, the migratory project an itinerary can change or be modified along the road and mobility is always an undetermined route. The movement of people is closely related to education and research exchange, i.e. student and academic mobility.

Historically, a number of people leaving a region (and in some cases returning home) occurred not only due to the internal socio-political issues in those particular countries, but also due to the changing nature of international affairs, trends in globalization, and shifting centers of power and education. While before 1991 large numbers of students from Ethiopia went to study in the USSR, Czechoslovakia, Hungary, Poland, and other countries of the socialist bloc and were coming back as agents of change, in the last two decades, an obvious shift has been visible due to the rise of India and China as the two major powers cooperating with all of the regional states. 17

The flow of students from the region to India and China, as well as their return, has contributed not only to a shifting socio-economic landscape but also to new perspectives on development, as well as the circulation of new forms of knowledge that is contributing to the reshaping of the region in general, although with varied levels of intensity in the studied countries. Moreover, the post-Cold War era has opened up new opportunities for foreign academics, including those from India, who have until recently been a dominant force in most of the countries in the Horn of Africa. Three main reasons behind migration and/or displacement of people in the region are the following:

(1) ongoing civil conflict in Somalia that since 1991 displaced or forced to leave the country millions of people either to neighboring countries, or to the Gulf States and Europe; (2) civil war in South Sudan since the end of 2013, that caused an enormous humanitarian crisis with more than a million people moving in bordering countries (either to Uganda, or Sudan, Ethiopia, or Kenya); (3) political crisis in Eritrea, which has forced hundreds of thousands of people to leave the country in search of better socio-economic conditions and to escape the authoritarian regime and compulsory military service, and are going either to neighboring Ethiopia and Sudan or to Southern Africa and Europe. [START_REF]and Nairobi: EU Trust Fund for Africa (Horn of Africa Window) Research and Evidence Facility[END_REF] Ultimately, the Gulf States as well as the European Union (particularly Germany and Sweden) became the main targets for migration. Therefore, the European Union decided to intervene especially in regard to smuggling The most significant reasons for migrations, internal, in the bordering countries or abroad, are conflict, climatic upheavals, and economic difficulties. When they are moving for work or study, migrants use private agencies that prepare their paper work and facilitate travel as is the case for many Ethiopians who go to work in Saudi Arabia. When they do not have enough resources and social capital, they are traveling alone or with small groups and are frequently vulnerable to the activities of networks of human traffickers. These dangers are faced by many Somalis in Sudan or Ethiopians in Djibouti. [START_REF]Smuggling and Trafficking from the East and Horn of Africa[END_REF] The choice of routes is based on personal aspirations, recommendations, rumors, but equally according to the advice offered by 'brokers', actors of human trafficking who more often than not seek to enrich themselves rather than providing the service for which they are paid.

Another reason for migration is looking for better access to services, essentially health services. [START_REF]A Region on the Move[END_REF] The Horn of Africa is specifically characterized by mixed migration flows: people can flee the same country where other people are coming to find refuge, and where others are transiting through. These movements include refugees, asylum seekers, displaced persons, nomadic groups, and migrants pursuing family reunification, education, or looking for employment. That is why trying to identify who is migrating or who is a refugee is complicated: one can be identified as a 'refugee' one day and start a migration process the other day. Some forced migrants are admitted to refugees' camps and considered refugees by NGOs or UN agencies, because they are fleeing somewhere to find security. The East and Horn of Africa has always been confronted to conflicts and forced mass displacement, and these movements, accelerated with the environmental problems, are likely to continue for quite some time. The conflicts in Democratic Republic of the Congo, Somalia, and South Sudan pushed people since 2012 to seek protection in Uganda (first hosting country in Africa with million refugees and asylum seekers in 2018), Ethiopia (second country with 900,000 refugees), and Kenya (third country with 400,000 refugees), and numerous refugees in Sudan and Somalia (but uncounted, because they are very mobile with few administrations to manage them).

Displacement routes within and outside the Horn of Africa

Even if migration trends evolve over time and context, main flows of people leaving the Horn of Africa can be observed. Three main routes are used for migration in and outside the Horn: the East route, the South one, and the North one. [START_REF]A Region on the Move[END_REF] Migrations often take place on a recurring basis: the profiles of people encountered during international migration, particularly toward the Eastern route, have often previously made trips to the regional level.

First are the departing movements toward Somaliland and Puntland (Djibouti is less used) to the Gulf Cooperation Council (GCC) countries on the eastern route: it concerns about 35% of the displacements noticed by IOM. Men and women, who typically migrate alone, are looking in the GCC for work. In general, women have less opportunity to receive education than do men, and to gain rewarding employment: it is not surprising that the trend of migration among women is higher than that of men. As a result, they are more vulnerable during the migration process, and more inclined to be victims of trafficking networks. It has been shown than the most common occupation for male migrants in the Gulf States is 'driver', employees as factory workers, mechanics, laborers, farmers, guards, and waiters. Women migrants are employed as housemaids or nannies. [START_REF] Kebede | Ethiopia: An Assessment of the International Labour Migration Situation: The Case of Female Labour Migrants[END_REF] Their (particularly women) goal is to return to their home country once they have earned enough money. Agencies and smugglers often organize this route. For the ones who get enough money, they can travel relatively secure and have a job waiting for them in the country of arrival. However, the journey is very hazardous: they have to go illegally through dangerous places and are subjected to human rights abuses and risk of death in deserts or in the Gulf of Aden crossing (Somalia's coastline is 3,300 km long and under control of illegal and piracy groups). Smugglers are often unscrupulous and are doing a multifaceted business (contraband of goods, drugs and weapons, piracy, human traffic, etc.).

While Yemen is dealing with conflicts and humanitarian crises, especially since 2014, it is still a place where desperate people try to find a jobwithout problem of bureaucracy due to the chaosor a starting point for a third destination. In 2017, IOM identified 99,000 entries of Ethiopians and Somalis into Yemen (50,000 arrivals in the first half of 2018). At the same time, Yemeni people who can afford it or who have family relations in the Horn are settling in capitals or main cities, where they can capitalize on historical ties with the region, for example, in trade. [START_REF] Bezabeh | Subjects of Empires, Citizens of States: Yemenis in Djibouti and Ethiopia[END_REF] This example illustrates how migration responds to different motivations and evolves according to networks and income: when people from the Horn of Africa try to reach Yemen, then Yemenis try to reach the Horn of Africa.

The two other routes, the South one and the North one, concern, respectively, 8% and 5% of the patterns of mobility according to IOM. South Africa is the goal for many young people who want to find work and safety, but this is also an attractive location for students.

Their number is difficult to ascertain but seems to stabilize around 15,000 Ethiopians and Somalis per year. As on other routes, migrants are sometimes arrested in third countries. They can stay in prison for a long time. This is also very much the case for those who remain years in precarious situation, situation of exploitation, or detention in Libya, when using the Northern Road. [START_REF] Bredeloup | The Libyan Migration Corridor[END_REF] This North route is the most famous one for the westerners but is not favored by migrants. If they have enough money and the resources to have a visa before departure (as a student or working visas), migrants go to Europe and North America as students or temporary workers and then often claim asylum status in order to stay. Many of them are unable to afford the heavy expenses or to make use of the legal process: they rely on smugglers and human trafficking networks to join the very risky route going across Sudan (Darfur), Libya, Mediterranean Sea, and Europe. [START_REF] Jaspars | Darfuri Migration from Sudan to Europe: From Displacement to Despair[END_REF] The paths of exile are sometimes multiple, and two types of migration can coexist. That which is toward the Arab countries is encouraged by the families, because it's considered safe and yielding money. But with the difficulties of access and returns from the GCC, the Northern route attracts more and more, usually without the consent of the family. Migrants often finance their trip by a system called 'leave now, pay later', which forces them to remain stuck in a country after departure, often in Libya, and keeps them in a position close to slavery until 'reimbursement' of the traffickers. In Somaliland, for example, the term tahrib is used to refer to this exile, and has a huge repercussion on families who are weakened when they try to raise money to help their relatives stranded in a third country. Yet, young people continue to leave, while they represent a large part of the population in a country that cannot offer them any opportunities or job prospects.

Displacement within the horn and inside the country of residence

According to IOM, 51% of migrations observed in the region were people migrating within the Horn of Africa itself. Migrants are mainly male adults (48%). Twenty-seven percent are female adults and children were 25% recorded by IOM in 2018 (half-female and -male). An average of 1 million migrant movements is estimated yearly in Djibouti, Ethiopia, and Somalia. Seasonal migration is very common throughout the Horn of Africa. They are shaped by people looking for some opportunities in another place, sometimes just attracted by adventure and a better life, sometimes pushed by a bad rainy season, other natural hazards, or vicissitudes of economic life.

Most of the time, these migrants are constantly linked with their family and are traveling back and forth in a dense network of people who are known to them. Some deep and long migratory movements push areas to evolve either because of climate change, the attraction of cities, or political or economic incentives (as when big company purchases arable land and forces farmers to leave, or when water resources are captured elsewhere).

For those who are leaving their country because of war or political pressure, the refugees camps are places where they sometimes settle for decades, waiting for continuing the road or a prospective return once their places of origin are more stable, or simply camps transforming into urban spaces progressively. For example, Eritrea and Ethiopia signed a landmark declaration of peace and friendship in July 2018, but this has not yet prevented the displacement of Eritreans fleeing their birthplace. In Gambella, at the Sudan-Ethiopian border, more than 320,000 refugees are living in bad life conditions, and this sometimes spans up to two generations. 38 In addition to these trends, there are people who are migrating inside their country of origin (IDPs/ internally displaced persons). Such is the case of the 970,000 Ethiopians who were forced to flee in 2018 within South Ethiopia. In Somalia, in June 2018, IDP numbers stood at 2.6 million. This number is incessantly increasing, showing that the country is in a long-term multi-factorial crisis, marking a 30% increase from the previous year. These trends can be quickly reversed should security prevail, but it can also be a first stage of a longer migration process: some IDPs that do not find stability in the country sometimes begin international mobility. Drought pushed 2.6 million IDPs in May 2018. They often perceived departure as potentially definitive: pushed for reasons related to the climate or to the war, they have difficulty to consider returning to live a comfortable life at home. The option of temporary return to one's homeland is mainly considered in the context of economic migration, often to help the family left behind. Ethiopia is hosting many refugees, in particular around its Western border (with Sudan), and it is confronting many environmental upheavals and internal political challenges. Since 2016, the country is facing drought. Political protests in Oromia and Amhara Regional States provoked a state of emergency (2017-2018) and Somali and Oromo groups are in conflict since 2017. By the end of 2020, the civil war in Northern Ethiopia region pushed dozens of thousands of people from Amhara and Tigray regions to cross the Sudanese border as refugees. In this demographically challenging country, rural people move to cities (they represent about 50% of the urban population). In addition, the response capacity of rural societies to cyclical crises is decreasing. [START_REF] Planel | Densité, pauvreté et politique: une approche du surpeuplement rural en Éthiopie[END_REF] The Ethiopian state and the people have to adapt, which is often reflected in waves of migrations when the vulnerability is too high.

Ethiopia is also a country where population displacements caused by drought and by the government, in order to adjust the country's demographic regulation toward more productive land, but also to control political opposition, have been well documented, especially in the 1970s and 1980s. They gave rise to major debates on the instrumentalization of the international community among vulnerable populations by their government, and on situations of technocratic displacements of population. Today, migration must still be considered from an angle linking individual and institutional constraints, as in some instances departures are caused by territorial decisions.

Since the end of the twentieth century, most of Uganda (except the North) has been stable, which justifies why it has become the first hosting country for refugees: the country host 1,470,000 refugees in 2018. 40 Uganda welcomed the refugees and allocated a piece of land for them to stay on and hence become free on dependence on government and NGO-owned land. However, the pressure is very high, with agricultural difficulties for some refugees, huge refugees' camps remaining, and a lot of contestation coming from the hosting community. Kenya is less impacted by huge mass displacement due to conflicts, and displaced people are able to come back in their origin area relatively quickly. Indeed, the government is able to support help and reconstruction for displaced persons. The growing stability of Kenya, even if relative, allows its citizens to have an environment more peaceful than its neighbor-ingstates and to recover quicker after a disaster.

Other states have the capacities, or the will, to control and manage mass displacement, and to control international aid and rules in order to apply their own autonomous processes. The Government of Ethiopia had led its own displacement response after the 2017 drought with support from international organizations, with a USD 117.7 million multi-sector response plan. 42 South Sudan is under conflict and food insecurity since the end of 2013. South Sudanese refugees and asylum seekers numbered is continually increasing: over 2.4 million in June 2018, which means a 27% increase from June 2017, added to 1.8 million IDPs. There are still a huge number of South Sudanese refugees in Sudan considered until recently 'brothers and sisters', or refugees when they arrived more recently, there are also a high number of South Sudanese in Ethiopia and mostly in Uganda.

Another case of displacements concerns the specific case of pastoralists and semi-nomadic people.

These patterns are increasing with the environmental degradation that makes such populations move for farther distances. These groups move according to environmental factors and they cross borders frequently. Since the 2010s and the growing tendency for states to control their sovereignty and reinforce their border, in particular for fighting terrorist groups, the case of semi-nomadic is not yet an international concern, but is a real challenge for the economy and the life of cross-border cultural groups in areas of South and East Ethiopia, North Kenya, Somalia, and Uganda.

43

Conclusion

In January 2018, the African Union adopted a Protocol on Free Movement of Persons in Africa and a policy framework for migration in January 2018. For sure, when everything will be put in place (visa liberalization, common biometric passport), the protocol will pave the way for new forms of migration in the next few years. Taking into account political turbulences in Ethiopia, an authoritarian regime in Eritrea, ongoing instability in Somalia, South Sudan, and Sudan, as well as environmental challenges in the region, migration within the Horn of Africa is not likely to decrease in the foreseeable future. Political transformation in Ethiopia may have an impact on migration especially for Ethiopians abroad and peaceful settlement may inspire, as it is already inspiring, many people in the diaspora to return to Ethiopia for multiple purposes, mostly for investment.

At the same time, opening of borders between Eritrea and Ethiopia in 2018 allowed thousands of Eritreans to flee the country and move to the Tigray region in Northern Ethiopia, a trend likely to continue as any political transformation in Eritrea has not been seen yet. However, since the opening of war in Tigray which started in November 2020 between the Prime Minister Abiy Ahmed and the Tigray People's Liberation Front (TPLF), there has been a flow of dozens of thousands of refugees across the border in Sudan. The exact numbers (as of December 2020) are still not known as the situation may get worse in the region. The same seems to be true about the border between Ethiopia and South Sudan which is an area of trans-border movement of people characterized also by high level of insecurity.

In light of such patterns, it might be safe to say that mixed migration flows discussed in this chapter will likely to continue due to complex trans-boundary links, security issues, and environmental causes.

Notes

6 7 Furthermore

 7 This chapter will illustrate how the main nexus of migration routes from the Horn of Africa manifest in three ways: (1) migration from the Horn of Africa to Europe via Libya and the Mediterranean; (2) migration to the Middle East; (3) and migration within the Horn of Africa. These modes of migration cannot be analyzed separately but rather as a complex network, in which one does not exclude others. People have many strategies and many different push factors that may change their decision to use one or the other route. , this chapter presents and analyzes migration trends and patters within and from the Horn of Africa and their evolving character since the end of the Cold War. The Cold War era posed a great challenge to all states within the Horn of Africa due to numerous conflicts, environmental challenges, famines, and the existence of authoritarian regimes in Somalia, Sudan, South Sudan, Eritrea, and Ethiopia. According to numerous indexes, 8 these Horn of Africa states are among the poorest countries in the world.

9

 9

  as students coming from around the world who come to study Islamic teachings at the International University of Africa in Khartoum, is surely another dimension that requires attention.19Complex networks of migration and their dynamicsDuring the Cold War (primarily since the 1950s to 1991), thousands of people left the Horn of Africa due to ongoing civil wars and environmental disasters. The Ethiopian community in the United States was growing and so was the Somali community in Great Britain. After the end of the Cold War, with the collapse of Somalia and hostilities between Eritrea and Ethiopia, waves of migrants continued to leave the region but in a more diversified way, finding new opportunities not only in Europe and North America, but also in the Middle East, primarily Saudi Arabia, Lebanon, the UAE, and Qatar.[START_REF] Schwab | Cold War on the Horn of Africa[END_REF] According to the United Nations Economic Commission for Africa (UNECA) Report on Migration from 2017, certain stereotypes persist in regard to African migration. In Europe, the 'migration crisis' is presented as stemming from Africa and is usually negatively depicted as an 'exodus' of millions of people.21In reality, most Africans move within the continent, most Africans move for work, study, and family, and most of the Africans living in Western countries are not part of the most economically underprivileged in their societies of origin. Moreover, unauthorized migration forms a minority and only a small part of it can be classified as 'trafficking'.

  22

  an enormous business for many local trading networks in last two decades. This is particularly true in relation to the route leading through northeastern Sudan to Libya and Egypt where people become easy victims of gangs of traffickers. 26 As smuggling remains the main challenge to the migration policies, the EU initiated training law enforcement on how to handle migrant smuggling and trafficking. The EU Trust Fund for Africa covers nine countries which are included in the Horn of Africa: Djibouti, Eritrea, Ethiopia, Kenya, Somalia, South Sudan, Sudan, Tanzania, and Uganda. These initiatives include the EU-Horn of Africa Migration Route Initiative under the Khartoum Process (2014), 27 which deals with both trafficking and smuggling of migrants in the region with a prospect to end smuggling and to address the root causes of the migration. The EU has been heavily involved in launching counter-smuggling initiatives in East Africa as the region has been increasingly affected by the phenomenon of mixed migration defined as a tendency of people to migrate, either regularly or irregularly, in search for a better life in other parts of the world which usually has a combination of factors. 28 Furthermore, the Somalia-Kenya Forced Migrant Rights Initiative (2014-2017) targets migrant smuggling and human trafficking, with the aim of creating safe environment for forced migrants and smuggled migrants. 29 Strategies and routes of migrations are difficult to measure and are changing depending on circumstances. Even if the numbers of refugees and internally displaced persons (IDPs) are slightly slowing down in the last few years, they are still, respectively, according to the estimates by IOM 4.6 million and 13.5 million people hosted in 2018 in the Greater Horn of Africa region (Democratic Republic of Congo, Ethiopia, Somalia, Yemen, South Sudan, Uganda, Central African Republic, Kenya, United Republic of Tanzania, Burundi, Rwanda, Djibouti, and Eritrea).

30

 30

  Djibouti, already weakened by political and economic instabilities, was the site of many different forms of displacement. It is first the place of Djiboutian or Ethiopian people attracted by cities.[START_REF] Chire | Djibouti contemporain[END_REF] It is also a destination for human trafficking, particularly with children and women ending up in slavery and prostitution. At least, since 2009, it is a transit place for migrants in direction of the Middle East counties.