François Cluzel
email: francois.cluzel@ecp.fr

Bernard Yannou

Yann Leroy

Dominique Millet

Towards parametric environmental profiles of complex industrial systems in preliminary design stage

Keywords: Eco-design, Life Cycle Assessment (LCA), Complex industrial system, parametric simulation, AC/DC conversion substation

The eco-design of complex industrial systems becomes a major issue for the concerned companies. Life Cycle Assessment (LCA) in particular is more adapted to "classical" products such as consumer goods. Performing LCA of such systems requires some thoughts to ensure significant results, for example concerning data granularity and quality. This article proposes a Life Cycle Assessment of an Alstom Grid AC/DC conversion substation for the aluminium industry. This LCA integrates first answers to the previous limitations. Very interesting results permit to orient the ecodesign strategy of the company. Moreover they lead to imagine original ways to configure the system. Thus a first and simple parametric LCA model is proposed: four different electrical sources are used to analyze the sensitivity of the design factors to the environmental impacts of the substation. Based on design of experiments, a more advanced model of such a tool would permit to identify the best configuration in terms of environmental performance, costs and reliability.

INTRODUCTION

Due to the current highly competitive markets and the growing sustainable awareness, environmental considerations have become a more and more crucial topic in the industrial world. Even if this growing awareness is a consequence of the recent environmental regulations (for example the WEEE [1], RoHS [2] or EuP [3] European directives or the REACH [4] European regulation), many companies attempt to go further and to propose more eco-friendly products. This kind of eco-design proactive approach is often considered as an important competitive advantage [START_REF] Dewulf | A pro-active approach to ecodesign: framework and tools[END_REF]. Dealing first with mass consumer goods, eco-design now reaches B to B and large-scale systems, in particular energy systems.

Large scale systems are characterized by a high level of complexity during their whole life cycle. It means that those systems are complex in themselves, but also that the way to model them is complex too, for example in environmental assessment. Actually, if a methodology like Life Cycle Assessment (LCA) is clearly defined and well mastered for "classical" consumer goods, the way to model complex industrial systems is much fuzzier. Examples of such limits in LCA are data availability and quality, choice of the boundaries according to the engaged resources or the local impacts and their evolution in time [START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 1: goal and scope and inventory analysis[END_REF][START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 2: impact assessment and interpretation[END_REF].

Examples of such systems are in particular energy systems, chemical facilities or industrial plants. This paper considers large electrical stations from Alstom Grid, called AC/DC conversion substations. This type of system is used in particular in primary aluminium smelters to convert the energy from the electrical network (high voltage) to energy usable for the electrolysis of aluminium (high current). It works continuously during 30 or 40 years. The life cycle of electrolysis substations is closely linked to the life cycle of the aluminium smelter, and, by extension, to the political and economic choices. This is a good example of a complex industrial system. This paper proposes to study the limits associated to the eco-design of complex industrial systems, in particular in LCA. A global LCA of an Alstom Grid AC/DC conversion substation has been performed by considering these limits to identify its sensitivity to the major layout and design factors. This ensures a good orientation of the eco-design activities as well as a good environmental knowledge to optimize the system configuration at the preliminary design stage. Thus a crucial question appears: which ways are possible to configure and value such complex systems in an environmental perspective? Considering the main characteristics of the studied system and its implementation context, a preliminary model based on parametric simulations is proposed. It opens the possibility to develop environmental configurators from the LCA results.

Section 2 explores the limits of LCA for complex industrial system and presents the study, while Section 3 describes the Alstom Grid substations and highlights their complexity. A LCA of a substation is described in Section 4. Section 5 is devoted to the integration of parametric environmental profile simulations to define the best environmental configuration of the studied system in a given context. Finally, Section 6 offers conclusions and perspectives for future works that will be led in the next months. Life Cycle Assessment, defined in standards ISO 14040 [START_REF]Environmental management -Life cycle assessment -Principles and framework[END_REF] and 14044 [9] is a powerful environmental evaluation tool. Internationally recognized, it is widely used in large companies to drive the eco-design of their products.

Life Cycle Assessment and complex industrial systems

Limits related to LCA

However LCA stays a relatively young methodology and is therefore subject to some limitations that can degrade the quality and the credibility of the results. Reap at al. [START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 1: goal and scope and inventory analysis[END_REF][START_REF] Reap | A survey of unresolved problems in life cycle assessment -Part 2: impact assessment and interpretation[END_REF] give a list of LCA problems by phase (see Table 1). The boundary selection, the spatial variation, the local environmental uniqueness and the dynamics of the environment are particularly important in this study. But data availability and quality are the major limitations of Life Cycle Assessment. This is particularly highlighted by Weidema and Wesnaes [START_REF] Weidema | Data quality management for life cycle inventories--an example of using data quality indicators[END_REF] or Leroy [START_REF] Leroy | Development of a methodology to reliable environmental decision from Life Cycle Assessment based on analysis and management of inventory data uncertainty[END_REF].

Another issue dealing with LCA is the fact that the assessment must be based on existing products [START_REF] Millet | Does the potential of the use of LCA match the design team needs?[END_REF]. Indeed, precise data are needed to feed the Life Cycle Inventory (LCI) phase, which does not match with products at a conceptual design stage.

Dealing with complex industrial systems

This paper focuses on complex industrial systems, whose specificities have not really been taken into account into LCA. These are industrial systems whose complexity induces major issues in terms of modeling, prediction or configuration. A complex industrial system in the sense of eco-design is:

 A large-scale system in terms of subsystems and components number, mass and resources use.  A system whose life cycle is hardly predictable at the design level, in particular its life time, upgrades, maintenance and end-of-life at long-term.  A system whose subsystems may have different life cycles and different obsolescence times.  A system which is in close interaction with its environment (super system, geographic site…).  A system supervised by human decisions and management.

Examples of such systems are in particular energy systems, like the Alstom Grid conversion substations described in Section 3. In front of such systems, the previously mentioned LCA limitations are amplified by the internal system complexity. In addition complementary issues appear, such as the quantification of the needed resources and, more globally, the organization of the project (deliverables, milestones, team…). We have already proposed the basis of an eco-design project management methodology for complex industrial systems [START_REF] Cluzel | Managing the complexity of environmental assessments of complex industrial systems with a Lean 6 Sigma approach[END_REF].

Life Cycle Assessments of large-scale energy systems have already been performed (see for example [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF][START_REF] Macharey | Life Cycle Assessment of Ultra High Voltage system layout and operation compared to 420 kV AC power systems[END_REF]). However they are considered as "classical" products. Local parameters in particular, implying nature of electricity, seems for us crucial to approximate the real environmental impacts of these systems. The next sections propose to optimize the application of LCA for complex industrial systems.

Presentation of the study

This study was conducted at Alstom Grid in the Power Electronics Massy unit (France). The main characteristic of the PEM systems (mainly AC/DC conversion substation for aluminium smelters) is their uniqueness, in the sense that there is no standard product, but a global product family. The design of a substation is based on previous substations and could be very close to that previous ones, but the integration of the customer needs make the systems always different. These substations are described in more details in the next section.

The second main characteristic of this study is the fact that if one substation subsystem is designed at the PEM unit, the others come from other Alstom Grid units, or even suppliers and subcontractors, making the data collection particularly hard to perform. Six months were necessary to conduct a global LCA of a substation, with about one month to structure the project and define the scope and objectives, four months to collect the data, one month to collect and analyze the LCIA results and one last month to precisely document and capitalize the study.

The study was structured around predefined deliverables and milestones, such as a project charter, data inventory templates, a data quality procedure and a precise LCA report. Data quality was managed through a simplified approach based on pedigree matrices [START_REF] Weidema | Data quality management for life cycle inventories--an example of using data quality indicators[END_REF][START_REF] Leroy | Development of a methodology to reliable environmental decision from Life Cycle Assessment based on analysis and management of inventory data uncertainty[END_REF][START_REF] Ecoinvent | [END_REF]. This approach allows an easy identification of the inventory weaknesses and it is then possible to improve its quality by directly working on these data. Data granularity, that means the extent to which the system is broken down into small parts, was chosen to permit the identification of the main environmental impacts on the whole substation life cycle, without spending too much time to collect the data. Limitations and weaknesses of the study were rigorously documented to facilitate the analysis and ensure the quality of future works.

Next section describes the Alstom Grid AC/DC conversion substations and their implementation context by highlighting their complexity. The LCA is then presented in Section 4.

AC/DC conversion substation: a complex industrial system

To understand the context of Alstom Grid AC/DC conversion substations for the aluminium industry, it is necessary to give some details about primary aluminium production.

Aluminium electrolysis

Primary aluminium production is based on the Hall-Héroult process discovered in 1886, using aluminium electrolysis. This process follows different steps identified on Figure 1. We focus in this section on the aluminium electrolysis stage.

Bauxite mining

Alumina extraction

Aluminium electrolysis

Aluminium casting

Bauxite

Alumina

Liquid aluminium Aluminium ingots

Figure 1. Primary aluminium production

An aluminium smelter includes the aluminium electrolysis and casting steps of the primary aluminium production. It is particularly energy-intensive: actually the amount of energy consumed by a state-ofthe-art primary aluminium plant is comparable to the amount of energy delivered by a nuclear plant unit, or consumed by a large city like Marseille (850,000 people), namely more than 1 GW. Given the electrical needs of such a plant, the furniture of energy is often realized by a captive power plant or a specific contract with energy producers. High cost and intermittent energies are not adapted to the electrolysis process, which must imperatively run continuously (24 hours a day) at an effective cost. That is why the current smelters mainly work with fossil energies (coal, natural gas, e.g. in India, China or Persian Gulf countries), hydro energy (e.g. in Canada, Iceland, Norway, Russia…) or nuclear power (e.g. French electrical mix).

The smelter is moreover often located near consequent transportation ways to import alumina and export aluminium (harborseven captive harbors -, roads, rail tracks).

A generic smelter (see Figure 2) consists in:  Potrooms that contains hundreds of electrolysis pots (commonly between 200 and 400 in a one-kilometer long building),  A casthouse,  An electrode plant that produces anodes for the electrolysis process,  An AC to DC conversion substations that supplies energy to the potlines from the grid,  Some other elements such as storage and auxiliaries buildings, silos or transportation facilities.

Despite great improvements in the last decades, the environmental impacts associated with aluminium electrolysis stay really huge [START_REF] Schmidt | Life cycle assessment of aluminium production in new Alcoa smelter in Greenland[END_REF][START_REF] Leroy | Provision of LCI data in the European aluminium industry Methods and examples[END_REF]. It is mainly due to CO2 emissions from the electrolysis pots and to energy consumption. Environmental considerations are then a major issue for aluminium producers, and the energy-related subsystems clearly need to be improved. The conversion substation is a key element of an aluminium smelter, as it permits to convert energy from the high voltage networks to energy usable from aluminium electrolysis. We focus in the next paragraph on this substation.

Electrolysis substation

PEM (Power Electronics Massy) is a unit of Alstom Grid, global player in electrical transmission all around the world. This unit designs, assembles and sells in particular AC/DC conversion substations for aluminium smelters worldwide. These are electrical stations to convert energy from the high voltage network to energy usable for the electrolysis of aluminium.

An aluminium electrolysis substation is made of thousands tons of power electronics components and transformers, for a cost of several dozens of million Euros. It is classically composed of several groups (including at least one redundancy), themselves composed of a regulating transformer, a rectifier transformer and a rectifier, as well as other smaller equipments. Figure 3 shows an example of a substation with 4 groups. The groups are connected on one side to the high voltage network through a high voltage substation (air or gas insulated, AC current), and on the other side to a busbar that is directly connected to the electrolysis potline (composed of hundreds of electrolysis pots, DC current). Filters are also added to the assembly to protect the network against harmonics. All the groups are supervised by control elements that are connected to the electrolysis pots to regulate the process.

The life time of this type of substations is really long, up to 30 or 40 years. No end-of life scenario is clearly defined as it is in charge of the customer (and it varies from one country to another). Moreover great uncertainties appear during the use phase: maintenance operations, dysfunctions, updates or revamping operations are not regular and they stay dependent on the economic situation and the aluminium producer investment policies.

In short, an AC/DC conversion substation for the aluminium electrolysis appears as a complex industrial system with close links to the primary aluminium production processes. In the context of ecodesign deployment at Alstom Grid PEM, a first LCA has been conducted on an instantiation of an electrolysis substation in India. This study is detailed in the next section. The analysis of the sensitivity of the layout and design factors will permit to identify environmental improvement ways through creativity sessions. It will also ensure good choices to configure the system at the preliminary design stage.

LCA of an electrolysis substation

This section is divided in three paragraphs corresponding to the three first phase of a LCA approach [START_REF]Environmental management -Life cycle assessment -Principles and framework[END_REF]: objectives and scope, Life Cycle Inventory (LCI) and Life Cycle Impact Assessment (LCIA).

Objectives and scope of the study

The main objective of this LCA study is the identification of the main environmental impacts of a substation life cycle in order to identify projects to improve its environmental performance. So its purpose is to orient the future eco-design activities that will be conducted at Alstom Grid PEM.

The study is focused on an Alstom Grid AC/DC conversion substation that has been designed and is currently under construction for the Hindalco Mahan aluminium smelter. The whole life cycle of the substation will be considered. This substation is composed of five groups.

The Hindalco Mahan aluminium smelter (under construction too) is located in central India (Bargawan, state of Madhya Pradesh). It is characterized by a captive coal power plant (900 MW) and is designed to produce 360,000 tons of primary aluminium per year with modern electrolysis pots.

Considering the constraints and characteristics of such a project, the following functional unit has been considered: "To ensure for 30 years without interruption the conversion of 220 kV AC high voltage energy to energy usable for aluminium electrolysis (360 kA DC , 1650 V DC ) according to the Hindalco specifications". This functional unit is adapted to our needs, namely to feed internal eco-design works on substations. The substation life time is 30 years, which means that the reference flow is 1.

The substation has been broken down into 8 subsystems: regulating transformers, rectifier transformers, rectifiers, busbars, filters, control, civil engineering, and other equipments. Each of these subsystems is himself divided into subassemblies and components.

The system is modeled thanks to SimaPro 7.2 software. Beside the specific data from Alstom grid, the LCI data come from Ecoinvent V2.1 database [START_REF] Ecoinvent | [END_REF]. The LCIA results are calculated with the ReCiPe 2008 midpoint (H) V1.03 methodology [START_REF] Goedkoop | ReCiPe 2008 -A life cycle impact assessment method which comprises harmonised category indicators at the midpoint and the endpoint level -First edition -Report I: Characterisation[END_REF]. Data inventory and data quality are managed thanks to the LCI procedure mentioned in Section 2.2.

Life Cycle Inventory

Data inventory

A major characteristic of Alstom Grid electrolysis substations is that the rectifiers only are designed at the PEM units. The other equipments are designed either by other Alstom Grid units or by suppliers or subcontractors. Thus PEM is mainly a systems integrator. This means that lots of data are not directly available or even not available at all (people do not respond for confidentiality reasons).

Consequently different data sources have been used:

 Internal Alstom Grid data  Data from suppliers, subcontractors or other units  Generic data (from LCA databases or literature) Specific data have been collected in a large Excel sheet. They mainly concern the following elements: masses, distribution, energy consumptions and end-of-life. Materials extraction and production, energy production and distribution as well as other data are generic.

Limitations

Mainly because of data availability, some limitations have appeared concerning the Life Cycle Inventory. The main limitation is that manufacturing processes and surface finishing have not been taken into account. Actually the data were not available for all component and materials. In order not to introduce an imbalance between the concerned equipments and the other ones, manufacturing processes and surface finishing have been dismissed. This choice is compatible with our objectives, because we aim at identifying the major environmental impacts on a large system; we prioritize a simplified and global modeling with regard to an extremely detailed and time-consuming one. The time spent to localize the data might not be profitable compared to the quality improvement of the modeling. This limitation has to be kept in mind to avoid too specific analysis of the results.

Concerning the distribution phase, only the transportation from the subsystems manufacturing site to the installation site has been considered. These transports use trucks and freight ships.

Another limitation that needs to be mentioned is the "frozen" use phase. Actually the maintenance operations, dysfunctions, upgrades or revampings are not regular and easily foreseeable. Further works are currently planned to develop a more precise life cycle modeling.

Finally, great uncertainties exist for the end-of-life phase: a simplified and possible scenario has only been modeled to illustrate what it could bring to the overall life cycle (reuse of metals and wood, recycling of transformer oil, average waste scenarios for the other components). Two reasons explain this limitation:

 The end-of-life is currently supported by the aluminium producers, not the substations suppliers. It varies a lot from a country to another because of the regulations, environmental considerations or industrial habits.  The end-of-life of a substation operates more than 30 years after its installation. In the developing countries in particular a 30 years vision for the recycling sector for example seems not real.

Keeping in mind these limitations, the next paragraph analyzes the main results of the LCI.

Results

Table 2 and Table 3 present the mass and energy balance sheets for the Hindalco Mahan substation.

Figures have been voluntarily adapted (+/-10 %) for confidentiality reasons.

In terms of mass, the civil engineering is by far the most impacting subsystem with almost 68% of the total substation mass. By removing the civil engineering from the substation, the total mass becomes about 2900 tons, for which more than two thirds are realized by the transformers. The busbars and, to a lower extent, the rectifiers are also not negligible. Concerning energy (losses during operation), the rectifier transformers, regulating transformer and rectifiers are respectively the three most impacting subsystems. The electrical losses of control, civil engineering and other equipments are considered as negligible.

It appears from these quick statements that electrical losses and masses are not correlated. It illustrates well the size and the complexity of the substation. Next paragraph will now present the potential environmental impacts associated to this inventory.

Life Cycle Impact Assessment

Life Cycle overview

Figure 4 gives an overview of the potential environmental impacts of the substation whole life cycle with a breakdown by life cycle phases. It appears that the use phase is responsible for more than 95 % of the total impacts, except for three impact categories: ozone depletion, ionizing radiation, metal depletion. For these categories, the contribution of the materials phase is higher. This is mainly due to metal production (steel, copper, aluminium), as well as PTFE production for ozone depletion. PTFE is included in the diodes of the rectifiers.

The domination of the use phase is clearly due to the production of electricity from coal, which is particularly polluting. Figure 4 also shows that the distribution phase is almost negligible (that is why it will not be detailed in this paper). The end-of-life phase permits to avoid less than 10 % (see small green bars below the horizontal axis) of the total impacts (let remember that only a basic end-of-life scenario has been modeled). It is also not further discussed in this paper.

Figure 4. Breakdown by life cycle phases of the substation life cycle impacts

By considering the contribution of each subsystem to the substation life cycle, it appears that the regulating and rectifier transformers are responsible for about 70 % of the total impacts, except for the three categories that were already highlighted in Figure 4. For ozone depletion, the contribution of the rectifiers is higher because of PTFE production. For ionizing radiation, the contribution of the busbars is higher, which is due to primary aluminium production (the generic data concerning the energy used for aluminium production include a part of nuclear electricity). The higher contribution of the transformers for metal depletion is caused by the high amount of copper used in their active parts.

For the other impact categories, the rectifiers account for about 19 % of the impacts, while the busbars represent between 7 and 10 % and the filters between 4 and 5 %. The other subsystems (control, civil engineering and other equipments) are negligible.

The materials phase

Figure 5 presents the breakdown by subsystems of the impacts associated with the materials phase. The busbars (550 tons of primary aluminium) are with the regulating and rectifiers transformers the most impacting subsystems. However three impact categories present singular results: ozone depletion, agricultural land occupation, and metal depletion.

Figure 5. Breakdown by subsystems of the materials phase impacts

As previously the PTFE in the rectifier diodes explains the singularity on ozone depletion. For agricultural land occupation the civil engineering is responsible for more than 60 % of the total impacts. This is mainly due to the high amount of concrete. Finally, the transformers represent 90 % of the impacts on metal depletion. This value is due to the high quantity of copper used in the active parts. Actually due to the currently known resources, the characterization factor for this impact category is much bigger for copper than for aluminium [START_REF] Goedkoop | ReCiPe 2008 -A life cycle impact assessment method which comprises harmonised category indicators at the midpoint and the endpoint level -First edition -Report I: Characterisation[END_REF], which explains the low score of the busbars.

The summation of the impacts generated by the transformers, rectifiers, busbars and civil engineering reaches more than 95 % of the total impacts of the materials phase. The other subsystems (filters, control and other equipments) are negligible.

The use phase

As the electricity used by these subsystems comes from the same source (a coal power plant), the contribution of the subsystems is the same for every impact category and corresponds to their contribution to the electrical losses (see Table 3). Thus the electrical losses of the rectifiers and transformers represent about 89 % of the total losses. The most impacting subsystem is the rectifier transformers, with 40 % of the impacts.

Synthesis

Those results show that with an electrical supply by a coal power plant, the use phase largely dominates the environmental impacts. The contribution of the materials phase stays low, except on Some materials which are particularly impacting for the environment have also been highlighted, like PTFE in the rectifier diodes, or, of course, the different metals (steel, copper, aluminium) or the concrete. In this case, classical eco-design strategies are the identification of substitute materials and the decreasing of the components masses and numbers. More in-depth analysis could permit to identify other materials or components that can be taken into account for further eco-design projects.

From these LCA results, one question that quickly appears is how to value them towards the client. The next section proposes an original approach to value the results based on parametric simulations.

Thus it appears that minimizing the electrical losses during the use phase is the best way to improve the environmental performance of the substation. For instance a classical strategy in eco-design to reach this objective is to increase the section of the conductors or to minimize their length.

To go further with parametric simulations

In order to identify the best configuration of a substation from its implementation context, a first and simple model of parametric LCA simulations is presented in this section. This short study will give the first elements that will be deepened in further works.

Towards parametric environmental models to configure complex industrial systems

The Life Cycle Assessment of the Hindalco Mahan substation has given us the opportunity to identify environmental improvements ways (innovation leads) that will be followed in R&D projects. The realization of these projects will give a "catalog" of eco-designed technological solutions. But the fact is that some of these solutions are maybe not compatible. Moreover nothing gives the guarantee that the optimal configuration is the assembly of all the eco-designed solutions (the global optimum is not necessarily the sum of the local optima).

Furthermore the choices made by the aluminium producers before the design of the substation are often dominant to assess its environmental impacts. The most striking example is the choice of the energy source.

Finally, the environmental considerations are clearly not the most influencing parameters in the industrial world. Economic costs, reliability, technical feasibility or quality are other criteria that are often predominant.

That is why we propose to develop in a first step parametric environmental profile simulations. From factors featuring the implementation context and/or some design parameter or design choice factors, such a tool would permit to define the optimal substation configuration among multiple response variables (including environmental performance). The technical knowledge of the designer is required to assess the consequences of the changing of a factor level on the system. This principle is explained on Figure 6.

Two complementary approaches could be developed:

 The first one will ensure the best "global" configuration from the client specifications at the call for tender stage. Input variables can be: energy source, voltage/intensity to supply, number of groups… As these are constraints fixed by the customer or issued from the environment, they are called exogenous parameters. In this global configuration, the exogenous parameters permit to define the best optimum for the main endogenous parameters (i.e. that are mastered by the actors of the system).  The second one will ensure the best "detailed" configuration from the global configuration previously defined. Input variables can be: number of diodes per rectifier arm, transformer oil, busbars section… From the main endogenous parameters fixed during the global configuration, the detailed configuration permits to fix the other endogenous design parameters.

Parametric simulations

Preliminary study: one factor with four levels

In this paragraph one input factor (electricity source) with four levels (electricity from coal, electricity from natural gas, hydroelectricity, and nuclear electricity) will be considered. Electricity from coal corresponds to the Hindalco Mahan substation that was previously assessed.

The environmental performance of the substation will be considered as response. In fact, this is a multi-objective response, because of the 18 impact categories composing the LCIA results with the ReCiPe 2008 method. For this simple application, the 7 most important categories with the LCIA normalized results have been chosen. Figure 7 shows the comparison of the environmental impacts for the four levels. 100 % represents the highest value among the four levels. If the hydro scenario is clearly the best alternative, it is more difficult to separate the three other scenarios. For example the nuclear scenario is the worst one on ionizing radiation and (only just) metal depletion. The coal scenario reaches the highest values for the other categories. The natural gas scenario is never the worst, but is for example higher than the nuclear scenario on climate change and lower on metal depletion.

The question that appears is then: is it possible to rank the four alternatives? Except for the hydro scenario which is the best one, it is not possible without a weighting of the categories. Such a weighting can be made by the customers considering their own environmental considerations. For example, climate change is clearly one of the main environmental issues for aluminium producers [START_REF] Innova | Toward a Sustainable Aluminium Industry: Stakeholder Consultations -Final Report[END_REF].

The comparison between the breakdown by life cycle phases for the hydro scenario and the coal scenario gives the most interesting results. It appears that the contribution of the use phase has largely decreased from the hydro scenario. This means that the materials phase is now responsible for most than 50 % of the total life cycle impacts on most of the impact categories. Moreover the gas and nuclear scenarios show intermediary results between the hydro and coal scenarios.

This is an extremely important result, which shows that the eco-design activities or the configuration choice stemming from the analysis of these environmental profiles may be different from one substation to another. Actually in the Hindalco Mahan case (electricity from coal), the decreasing of the electrical losses is the best way to improve the overall environmental performance of the substation. Impact transfers from the use phase to the materials phase can be acceptable if the environmental benefits are significant. On the contrary, in a Canadian case (hydroelectricity), minimizing weights and substituting materials can bring significant benefits. If the optimal configuration clearly depends on classical design parameters (endogenous parameters), this very simple design of experiments shows that the optimal configuration of a substation also depends on local parameters that are chosen by the clients (exogenous parameters). Thus they have to be taken into account in an environmental perspective. A more advanced model based on design of experiments and mixing endogenous and exogenous parameters could be a powerful tool to value eco-design towards customers. Such a model will be developed in the next months.

conclusions and perspectives

We have shown in this paper that conducting a Life Cycle Assessment of a complex industrial system is in itself complex. Limitations and simplifications are mandatory to reach satisfactory results with acceptable time and resources. Such a LCA permits to draw global conclusions and to envisage more advanced eco-design activities. More refined analysis on the subsystems must however be considered with precaution in view of the data granularity. But this global approach could be a powerful basis to indepth studies on a particular life cycle phase or subsystem for example.

In this way the LCA of an Alstom Grid AC/DC conversion substation for the primary aluminium industry presented in this paper gives a strong basis to further works. The substations main environmental issues have been clearly identified as well as the limitations of our approach. The principal limit is probably the "frozen" use phase, since maintenance, dysfunctions, updates and real life times have not been taken into account. We are currently working on a sharp parameterization of the LCA modeling to draw different usage scenarios and reach more precise analysis. In the Alstom Grid context, those LCA results and creativity sessions have already permitted to identify about fifteen promising improvement projects.

Furthermore the LCA results analysis has allowed us to imagine parametric environmental simulations to identify the best substation configuration from a given implementation context. A very simple approach with a single factor has shown that the electricity source for example is a crucial factor to orient eco-design actions and optimize the substation configuration. We are convinced that this kind of tool is essential to ensure a good demarcation from the competitors and to drive continuous improvement on eco-design in the company. A preliminary model will be developed in the next months to prove these assertions.

The principle of this more advanced model with several factors is the following: by mixing endogenous and exogenous parameters as input variables, it will be possible thanks to design of experiments to build a response surface to define the optimal configurations. By fixing the exogenous parameters from the customer requirements, it will be possible to choose the best endogenous parameters.

In a first step a model restricted to an Alstom Grid rectifier will be developed with one exogenous parameter (electricity source, as previously) and two endogenous parameters: the number of diodes per rectifier arm (which a dimensioning parameter for the rectifier) and the rectifier frame material. The variation of these two parameters influences both the electrical losses and the mass of the system. As response the economic cost (life cycle cost to include the electrical losses costs) and the reliability will be added to the environmental performance. This model will be a demonstrator to prove the possibilities of a more sophisticated configurator for commercial use.

Figure 2 .

 2 Figure 2. Aluminium Dunkerque, France (©2010 Google). The substation is surrounded by a rectangle.

Figure 3 .

 3 Figure 3. Example of an Alstom Grid aluminium electrolysis substation (Aluar smelter, Argentina)

F r e s h w a t e r e c o t o x

  r o p h i c a t i o n T e r r e s t r ia l e c o t o x i c i t y

  : ozone depletion, ionizing radiation, and metal depletion. The distribution is negligible.

Figure 6 .

 6 Figure 6. Principle of the proposed modelThe next paragraph proposes to illustrate what a parametric LCA simulation can be with a very simple example based on a single factor and a single response.

Figure 7 .

 7 Figure 7. Comparison of the four electricity sources scenarios for the whole substation life cycle

Table 1 . LCA problems by phase (from [6]) Phase Problem

 1

	Goal and scope definition	 Functional unit definition
		 Boundary selection
		 Social and economic impacts
		 Alternative scenario considerations
	Life cycle inventory analysis	 Allocation
		 Negligible contribution ('cutoff')
		criteria
		 Local technical uniqueness
	Life cycle impact assessment	 Impact category and methodology
		selection
		 Spatial variation
		 Local environmental uniqueness
		 Dynamics of the environment
		 Time horizons
	Life cycle interpretation	 Weighting and valuation
		 Uncertainty in the decision process
	All	 Data availability and quality

Table 2 . Mass balance sheet of the substation

 2

	Subsystems	Total mass (t) Contribution (%)
	Substation	8845	100 %
	1. Regulating transformers	1 000	11.3 %
	2. Rectifier transformers	1 100	12.4 %
	3. Rectifiers	120	1.4 %
	4. Busbars	550	6.2 %
	5. Filters	25	0.3 %
	6. Control	20	0.2 %
	7. Civil engineering	6 000	67.8 %
	8. Other equipments	30	0.4 %

Table 3 . Energy balance sheet of the substation Subsystems Total losses (kW) Contribution (%)

 3

	Substation	8 000	100 %
	1. Regulating transformers	2 400	30.0 %
	2. Rectifier transformers	3 200	40.0 %
	3. Rectifiers	1 500	18.8 %
	4. Busbars	550	6.9 %
	5. Filters	350	4.3 %
	6. Control	0	0%
	7. Civil engineering	0	0%
	8. Other equipments	0	0%

Acknowledgments

We gratefully thank Joël Devautour and François Puchar from Alstom Grid for their full support to this work. We also thank Daniel Afonso from CUBIK Partners for his contribution to the methodological aspects, as well as Anthony Rolland for his supplies to the LCA results.


Jean-Claude Bermond
email: jean-claude.bermond@inria.fr

David Coudert
email: david.coudert@inria.fr

Gianlorenzo D'
email: gianlorenzo.dangelo@inria.fr

Fatima Zahra Moataz
email: fatima-zahra.moataz@inria.fr

SRLG-Diverse Routing with the Star Property

The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues where some links of a network fail simultaneously. In this context, the diverse routing problem is to find a set of pairwise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proved NP -complete in general and some polynomial instances have been characterized.

 for computing a pair of SRLG-disjoint paths in networks with SRLGs satisfying the star property, and then prove that this problem is in fact NP -complete. Then, we devise polynomial time algorithms for practically relevant subcases, in particular when the number of SRLGs is constant, the maximum degree of the vertices is at most 4, and when the network is a directed acyclic graph.

Finally we consider the problem of finding the maximum number of SRLG-disjoint paths in networks with SRLGs satisfying the star property. We prove that such problem is NP -hard and hard to approximate. Then, we provide exact and approximation algorithms for relevant subcases.

I. INTRODUCTION

To ensure reliable communications, many protection schemes have been proposed. One of the most used, called dedicated path protection, consists in computing for each demand both a working and a protection path. A general requirement is that these paths have to be diversely routed, so that at least one of them can survive a single failure in the network. This method works well in a single link failure scenario, as it consists in finding two edge-disjoint paths between a pair of nodes. This is a well-known problem in graph theory for which there exist efficient polynomial time algorithms. However, the problem of finding two diversely routed paths between a pair of nodes becomes much more difficult in case of multiple correlated link failures that can be captured by the notion of SRLG (Shared Risk Link Group). In fact, an SRLG is a set of network links that fail simultaneously when a given event (risk) occurs. The scope of this concept is very broad. It can correspond, for instance, to a set of fiber links of an optical backbone network that are physically buried at the same location and therefore could be cut simultaneously (i.e. backhoe or JCB fade). It can also represent links that are located in the same seismic area, or radio links in access and backhaul networks subject to localized environmental conditions affecting signal transmission, or traffic jam propagation in road networks. Note that a link can be affected by more than one risk. In practice, the failures are often localized and common SRLGs are SRLGs verifying the star property [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] (coincident SRLGs in [START_REF] Doucette | Shared-risk logical span groups in spanrestorable optical networks: Analysis and capacity planning model[END_REF]). Under this property, all links of a given SRLG share an endpoint. Such failure scenarios can correspond to risks arising in router nodes like card failures or to the cut of a conduit containing links issued from a node (see Figure 1). Fig. 1. Example of localized risks: link l 4 shares risk r 2 , corresponding to Port 2 failure, with l 5 and l 6 , and shares risk r 4 , corresponding to a conduit cut, with links l 2 and l 3 .

Related work

In the context of SRLG, basic network connectivity problems have been proven much more difficult to address than their counterparts for single failures. For instance, the problem of finding a "SRLG-shortest" st-path that is a path from node s to node t having the minimum number of risks has been proven NP -hard and hard to approximate in general (see [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF]). However, the problem can be solved in polynomial time in two generic practical cases corresponding to localized failures: when all risks verify the star property [START_REF] Coudert | Shared risk resource groups and colored graph: Polynomial and FPT optimisation problems[END_REF] and when risks are of span 1 (i.e. when a link is affected by at most one risk and links sharing a given risk form a connected component [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF]).

The diverse routing problem in presence of SRLGs consists in finding two SRLG-disjoint paths between a pair of vertices (i.e. paths having no risk in common). It has been proven NPcomplete in general [START_REF] Hu | Diverse routing in mesh optical networks[END_REF]- [START_REF] Modiano | Survivable lightpath routing: a new approach to the design of WDM-based networks[END_REF] and many heuristics have been proposed. The problem is polynomial in some specific cases of localized failures: when SRLGs have span 1 [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF], and in a specific case of SRLGs having the star property [START_REF] Datta | Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures[END_REF] in which a link can be affected by at most two risks and two risks affecting the same link form stars at different nodes (this result also follows from results of [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF]).

Our results

We study the diverse routing problem when SRLGs have the star property and there are no restrictions on the number of risks per link. This case has been studied in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] in which the authors claim that the diverse routing problem with the star property can be solved in polynomial time. Unfortunately their algorithm is not correct; indeed we exhibit, in Section II of our paper, counterexamples for which their algorithm concludes to the non existence of two SRLG-disjoint paths although two such paths exist. We give the notation used in the paper in Section III. In Section IV, we prove that the problem is in fact NP-complete (again, contradicting the supposed polynomiality of the algorithm of [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF], unless P = NP ). On the positive side, we show, in Section V, that the diverse routing problem can be solved in polynomial time in particular subcases which are relevant in practice. Namely, we solve the problem when the number of SRLGs is bounded by a constant, when the maximum degree is at most 4 or when the input network is a directed acyclic graph. Finally, we consider the problem of finding the maximum number of SRLG-disjoint paths. This problem has been shown to be NP -hard in [START_REF] Li | Fiber span failure protection in mesh optical networks[END_REF]. We prove that it is also NP -hard under the star property, that it is hard to approximate and we give polynomial time algorithms for the above relevant subcases.

II. COUNTEREXAMPLES TO THE ALGORITHM OF LUO & WANG

Luo and Wang have published in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] an algorithm to find a pair of SRLG-disjoint paths with minimum total cost from a source s to a destination t in graphs with SRLGs satisfying the star property. The algorithm is an adaptation of the Bhandari's algorithm [START_REF] Bhandari | Survivable Networks: Algorithms for Diverse Routing[END_REF] with the use of a modified version of the Bellman-Ford algorithm to find the second path. At first, the algorithm finds the shortest path P a between s and t, then it reverses the edges of P a and assigns to them the negative values of their costs. Virtual nodes and edges are added afterwards to deal with some specific cases. The second path P b is then found with the use of the modified Bellman-Ford where SRLG-specific routing information is kept, particularly in the nodes of P a . In case P a and P b share common segments, the procedure of deletion and exchange of the Bhandari's algorithm is used.

The algorithm is incorrect for two reasons:

The first weakness is that the first and last edges of P a should be contained necessarily in the pair of paths returned by the algorithm: if no edge incident to s (resp. t) is SRLGdisjoint from the first (resp. last) edge of P a , the algorithm will ignore the existence of 2 SRLG-disjoint paths even if they exist.

The counterexample in Figure 2 illustrates the first weakness: risk r is shared between edges {s, v 0 } and {s, v 1 } and risk r 0 6 = r is shared between edges {s, v 0 } and {s, v 2 }. The shortest path is P a = {s, v 0 , t}. Let us apply the algorithm. As it is explained in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] page 451 lines 9-10, the initialization part guarantees that the first edge of P b is risk-disjoint from P a . Therefore in Figure 2, the algorithm does not find any edge to start and hence terminates concluding that there are no two SRLG-disjoint paths. However two SRLG-disjoint paths clearly exist, namely they are P 1 = {s, v 1 , w 1 , t} and P 2 = {s, v 2 , w 2 , t}. A similar counterexample exists, with the risks at destination vertex, putting risk r 1 shared between edges {v 0 , t} and {w 1 , t} and risk r 0 1 shared between edges {v 0 , t} and {w 2 , t}. This weakness can be overcome by running the algorithm for all possible pairs (u, v) such that u is incident to s and v is incident to t. The second weakness is that the algorithm only checks SRLG-disjointness around nodes of P a and never checks other nodes. It assumes implicitly that the only nodes that can be shared by the two SRLG-disjoint paths are nodes belonging to P a and ignores the existence of any other possibilities. Any attempt to modify the algorithm to face this weakness results in exponential time algorithms. Figure 3, illustrating the second weakness, shows a counterexample to the algorithm in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] that furthermore can give to the reader a flavor of the difficulty of the problem. In this figure, we have 2 specific risks r 1 and r 2 6 = r 1 forming a star in v. As vertex v is a cut-vertex any path should contain v. In this case, and to ensure the SRLG-disjointedness, one path should use the subpath u, v, b and the other one should use the subpath u 0 , v, b 0 . We have two SRLG-disjoint paths P 1 = {s, a, z, w, u, v, b, t} and P 2 = {s, a 0 , w, u 0 , v, b 0 , t}. The algorithm of [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] uses the shortest path P a = {s, a, v, b, t} and then performs a backwards phase which never finds w again. Then the algorithm stops missing the fact that there exist two SRLG-disjoint paths.

III. NOTATIONS

We model the network as an undirected graph G = (V, E), where the vertices in V represent the nodes and the edges in E represent the links. We associate a color to each SRLG. Let us denote by C the set of all the colors. Then a network with SRLGs is modeled by a multi-colored graph that is a triple mG = (V, E, C), where (V, E) is a graph and C is a set of colors assigned to E.

We denote by E(c) the set of edges having color c 2 C, by C(e) the set of colors associated with edge e 2 E, by CPE = max e2E |C(e)| the maximum number of colors per edge, and by EPC = max c2C |E(c)| the maximum number of edges having the same color. Given a vertex v, (v) denotes the set of neighbors of v and d(v) = | (v)| its degree. A color is incident to v if it is assigned to an edge incident to v. The colored degree of v, denoted by d c (v), is the number of colors incident to v. The maximum degree and the maximum colored degree of a graph are denoted by and c , respectively. We can now model the star property defined in the introduction as follows. A color c 2 C is called a star color if all edges of E(c) are incident to the same vertex. A multi-colored graph has the star property if it has only star colors.

Given a multi-colored graph mG and two vertices s and t, an st-path is an alternating sequence of vertices and edges, beginning with s and ending with t, in which each edge is incident to the vertex immediately preceding it and to the vertex immediately following it. A path is denoted by the sequence of vertices or by the sequence of vertices and edges. We say that two paths P 1 and P 2 are color-disjoint if

([ e2P1 C(e)) \ ([ e2P2 C(e)) = ;.
The diverse routing problem defined in the introduction consists then in finding k color-disjoint paths and can be formulated formally as follows:

Problem 1 (k-Diverse Colored st-Paths, k-DCP): Given a multi-colored graph mG and two vertices s and t, are there k color-disjoint st-paths from s to t?

IV. NP -COMPLETENESS

In this section we will prove that the k-DCP problem is NPcomplete, by using a reduction to the problem described below of finding a T -compatible path (or a path avoiding forbidden transitions), which was proved NP -complete in [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF].

Let G = (V, E) be an undirected graph. A transition in v 2 V is a pair of edges incident to v. To each vertex v we associate a set T (v) of admissible (or allowed) transitions in v. We call transition system the set

T = {T (v) | v 2 V }.
Let G = (V, E) be a graph and T a transition system. A path

P = {v 0 , e 1 , v 1 , . . . , e k , v k } in G, with v i 2 V , e i 2 E, is said to be T -compatible if, for every 1  i  k 1, the pair of edges {e i , e i+1 } is an admissible transition , i.e. {e i , e i+1 } 2 T (v i ).
The transition system is represented in [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF] by a graph also denoted as T (v) where the vertices represent the edges of G incident to v and two vertices in T (v) are joined if the edges they represent in G form an admissible transition in v. We now can define the T -Compatible path problem.

Problem 2 (T -Compatible path, T -CP): Given a graph G = (V, E), two vertices s and t in V , and a transition system T , does G contain a T -compatible path from s to t?

It has been proved in [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF] that problem T -CP is NPcomplete in the strong sense and it remains NP -complete for the family G 4 of simple graphs where vertices s and t have It is easy to see that the problem is in NP . Given an instance G, s, t, T with G in the family G 4 of the T -CP problem, we define an instance of 2-DCP as follows. We associate to G a multi-colored graph H = (V H , E H , C) where:

v h e f (a) v in G, T (v) = {{e, h}, {f, h}} v x 0 e x e x f x 0 f x h x 0 h (b) v in H Edge Colors {v, x e } C ef , C ef 0 {v, x 0 e } C e 0 f , C e 0 f 0 {v, x f } C ef , C e 0 f {v, x 0 f } C ef 0 , C e 0 f 0 {v, x h } no colors {v, x 0 h } no colors
v e g f h (a) v in G, T (v) = {{e, f }, {g, h}} v x 0 g x g x 0 f x f x 0 e x 0 h x e x h (b) v in H Edge Colors {v, x e } C eg , C eg 0 , C eh , C eh 0 {v, x 0 e } C e 0 g , C e 0 g 0 , C e 0 h , C e 0 h 0 {v, x f } C fg , C fg 0 , C fh , C fh 0 {v, x 0 f } C f 0 g , C f 0 g 0 , C f 0 h , C f 0 h 0 {v, x g } C eg , C e 0 g , C fg , C f 0 g {v, x 0 g } C eg 0 , C e 0 g 0 , C fg 0 , C f 0 g 0 {v, x h } C eh , C e 0 h , C fh , C f 0 h {v, x 0 h } C eh 0 , C e 0 h 0 , C fh 0 , C f 0 h 0
• For every edge e = {u, v} in G, we associate in H two paths of length 2: {u, x e , v} and {u, x 0 e , v}. H has then |V (G)| + 2|E(G)| vertices and 4|E(G)| edges.

• We assign the colors to edges incident to a vertex v in H as follows:

No colors are assigned to the edges incident to t.

For each pair of edges e and f incident to s in G, such that e 6 = f , we will use 4 colors C ef , C ef 0 , C e 0 f and C e 0 f 0 . We assign colors C ef and C ef 0 to the edge {s, x e }; colors C e 0 f and C e 0 f 0 to the edge {s, x 0 e }, colors C ef and C e 0 f to the edge {s, x f } and colors C ef 0 and C e 0 f 0 to the edge {s, x 0 f }. For each v 6 = s, t, and for each pair of edges e and f incident to v in G such that e 6 = f and {e, f } is not an admissible transition (i.e. {e, f } / 2 T (v)), we assign colors C ef and C ef 0 (resp. C e 0 f and C e 0 f 0 ) to the edge {v, x e } ({v, x 0 e }, resp.), and colors C ef and C e 0 f (resp. C ef 0 and C e 0 f 0 ) to the edge {v, x f } (resp. {v, x 0 f }). As each vertex has either degree 3 or 4, two cases can occur: (i) If d(v) = 3, let e, f and h be the 3 edges incident to v and let T (v) = {{e, h}, {f, h}}, then edge {v, x e } receives the 2 colors C ef and C ef 0 , edge {v, x h } receives no colors and so on (see Figure 4 for the complete list of colors assigned to all the edges). (ii) If d(v) = 4, let e, f, g and h be the 4 edges incident to v and T (v) = {{e, f }, {g, h}}. Then edge {v, x e } receives the 4 colors C eg , C eg 0 , C eh , C eh 0 . Similarly, edge {v, x f } receives the 4 colors C fg , C fg 0 , C eh and C fh 0 (see Figure 5 for the complete list of colors assigned to all the edges). The transformation is polynomial time computable and the star property holds. Moreover, note that each edge has at most 4 colors, each color is associated with two edges, the degree of each vertex is at most 8 and the color degree is at most 16. It follows that CPE = 4, EPC = 2, = 8, and g = 16.

To prove the theorem, we will use the following properties. Property 1: Given an edge e incident to s in G, the edge {s, x e } in H shares a color with all the other edges incident to s but {s, x 0 e }. Said otherwise, the only pair of edges incident to s having no color in common are of the form {{s, x e }, {s, x 0 e }} for some e. Property 2: If v 6 = s, t, d(v) = 3 and T (v) = {{e, h}, {f, h}}, then two edges incident to v share a color if and only if one is of the form {v, x e } or {v, x 0 e } and the other is of the form {v, x f } or {v, x 0 f }. Property 3: If v 6 = s, t, d(v) = 4 and T (v) = {{e, f }, {g, h}}, then two edges incident to v share a color if and only if one is of the form {v, x e }, {v, x 0 e }, {v, x f } or {v, x 0 f } and the other is of the form {v, x g }, {v, x 0 g }, {v, x h } or {v, x 0 h }. We first show that if there exists a T -compatible path in G, then there exist two color-disjoint paths in H. Let P = {s, e 1 , v 1 , . . . , e p , v p , e p+1 , t} be a T -compatible path from s to t in G. Then Q = {s, x e1 , v 1 , . . . , x ep , v p , x ep+1 , t} and Q 0 = {s, x 0 e1 , v 1 , . . . , x 0 ep , v p , x 0 ep+1 , t} are two colordisjoint paths in H. In fact, any edge {v, x e } has no color in common with {v, x 0 e } by Properties 1, 2, or 3. Conversely, we now show that if there exist two colordisjoint paths in H, then there exists a T -compatible path in G. Let Q = {s, x 1 , v 1 , . . . , x p , v p , x p+1 , t} and Q 0 = {s, y 1 , u 1 , . . . , y p 0 , u p 0 , y p 0 +1 , t} be two color-disjoint paths in H. We prove by induction on i 2 {1, . . . , p + 1}, that {x i , y i } = {x ei , x 0 ei }, v i = u i and p = p 0 . For i = 1, by Property 1, {s, x 1 } and {s, y 1 } have no color in common only if {x 1 , y 1 } = {x e , x 0 e } for an edge e incident to s and then v 1 = u 1 .

Let us suppose that it is true until i = l and prove it for i = l + 1. In v l = u l , let the two edges used by Q and Q 0 be {x e l , v l } and {x 0 e l , v l }. If d(v l ) = 3, we distinguish two cases: (i) e l belongs to only one edge of T (v l ) say {e l , h l } and the paths Q and Q 0 being color-disjoint can only use the edges {v l , x h l } and {v l , x 0 h l }. (ii) e l belongs to two edges in T (v l ), {e l , f l } and {e l , h l }. If one path uses the edge {v l , x h l } ({v l , x 0 h l }, resp.) the other path cannot use the edge {v l , x f l } or {v l , x 0 f l } by Property 2, it has then to use edge {v l , x 0 h l } ({v l , x h l }, resp.). If d(v l ) = 4, by Property 3, the only possibility as Q and Q 0 are color-disjoint is that they use the edges {v l , x e l+1 } and {v l , x 0 e l+1 } where {e l , e l+1 } 2 T (v l ) and so the statement is true for i = l + 1.

It follows that the path P = {s, e 1 , v 1 , . . . , e p , v p , e p+1 , t} satisfies {e i , e i+1 } 2 T (v i ) for every i 2 {1, p} and then it is T -compatible.

To show that the problem remains NP -complete even for fixed CPE 2, EPC 4 and c 4, it is enough to modify the above transformation by using a different color assignment (details in [START_REF] Bermond | Diverse Routing with the star property[END_REF]). To extend the proof to the case of k 3, it is enough to add k 2 paths of length 2 from s to t P i = {s, w i , t}, i = 3, 4, . . . k, with a new color assigned to each edge {s, w i }. These paths are pairwise color-disjoint and also color-disjoint from the two paths in the above transformation. Moreover, this assignment does not change CPE and EPC and increases and c by k 2.

V. POLYNOMIAL CASES

In this section we give polynomial time algorithms for k-DCP for some important special cases.

A. Bounded number of colors

In this section, we give an algorithm to find k color-disjoint paths in the special case where the number |C| of colors in the network is bounded by a constant, i.e. |C| = O(1). We observe that such an algorithm works for every graph topology and even if the star property does not hold.

We will reduce our problem to the k-Set Packing problem.

Problem 3 (k-Set Packing): Given a set X and a collection S of subsets of X, is there a collection of disjoint sets S 0 ✓ S such that |S 0 | = k?

A subset S ✓ C of colors will be called realizable, if the subgraph G S induced by the edges whose colors are all in S (i.e. edges e such that C(e) ✓ S) contains a path from s to t. Note that such a path uses only colors of S.

The idea of the algorithm is to enumerate all the realizable subsets of C and then find k disjoint realizable subsets by using an exact algorithm for the k-Set Packing. As the size of C is constant, the computational time required by such algorithm is polynomial.

The details of the algorithm along with its correctness and complexity are given in the next theorem.

Theorem 2:

If |C| = O(1)
, there exists an algorithm that solves k-DCP with O(|V | + |E|) computational time.

Proof: Let X = C and S be the family of realizable subsets of colors. Then there exist a collection of k disjoint sets S 0 ✓ S if and only if there exist k color disjoint paths from s to t. Indeed, to each subset S 0 of S 0 is associated a path using uniquely colors of S 0 (as S 0 is realizable) and two disjoint subsets correspond to two color disjoint paths.

Determining if a subset of colors is realizable takes O(|V |+ |E|) computational time. Furthermore, it is known that there exist polynomial algorithms to solve the k-Set Packing problem when the size of X is bounded. For example the exact algorithm in [START_REF] Björklund | Set partitioning via inclusion-exclusion[END_REF]

has complexity O(|S|2 |X| |X| O(1)
) and so, as

B. Bounded degree

In this section, we give algorithms for finding k colordisjoint paths when < 4 and for finding 2 color-disjoint paths when = 4. First, note that the maximum number of color-disjoint paths in a graph is upper bounded by .

If  2 the problem is trivial as the graph is either a path or a cycle. In the first case, it always exists only one path from s and t. In the second case, the only vertices where the two possible paths can share colors are s and t and hence it is enough to check if the two edges incident to s (and t) are color-disjoint.

If 3, observe that if two different paths share an internal vertex of degree 3, they necessarily share also an edge and hence all the colors of that edge and so they cannot be colordisjoint. Furthermore, if two paths are color-disjoint the colors of their first edges should be different and also the colors of their last edges should be different. When = 3, there are 3 color-disjoint paths if and only if G has 3 vertex-disjoint paths between s and t (i.e. G is 3-connected) and the 3 first edges of these paths have different colors and also the 3 last edges. That can be checked in O(|V | + |E|) time: constant time for checking the color disjointness of the 3 first (last) edges, and O(|V | + |E|) time for testing is G is 3-connected (see [START_REF] Hopcroft | Dividing a graph into triconnected components[END_REF]).

For k = 2 and = 3 or 4 we have the following theorem:

Algorithm 1: Solving 2-DCP when = 3, 4.

1 foreach admissible graph G(s i , s j , t i 0 , t j 0 ) do 2 if there exist 2 vertex-disjoint paths form s to t in G(s i , s j , t i 0 , t j 0 ) then 3

There exist two color-disjoint paths from s to t in G;

4 else 5 if all the cut-vertices in G(s i , s j , t i 0 , t j 0 ) have degree 4 then 6 if for each cut vertex v, e and f denote the edges of the connected component of G(s i , s j , t i 0 , t j 0 Proof: We say that a pair {s i , s j } of neighbors of s in G is admissible, if they have different colors, i.e. C((s, s i )) \ C((s, s j )) = ; and similarly we say that {t i 0 , t j 0 } is an admissible pair of neighbors of t if they have different colors. Then we consider the admissible graph G(s i , s j , t i 0 , t j 0

) obtained from G by deleting the edges {s, s `} with `6 = i, j and the edges {t `0 , t} with `0 6 = i 0 , j 0 .

The correctness of Algorithm 1 follows from the observations given above.

By definition, if there exist two vertex disjoint paths from s to t in G(s i , s j , t i 0 , t j 0

) the first edges and last edges of such paths have different colors and so we conclude that there are 2 color-disjoint paths (lines 2, 3).

Otherwise if there exists a cut vertex v of degree 3, we cannot have color disjoint paths containing this vertex. That is in particular the case when = 3. Let = 4; if in v one path uses edge e and e 0 (resp e and f 0 ), the other path uses necessarily f and f 0 (resp f and e 0 ) and the conditions on colors are necessary and sufficient for the color disjointness of the paths at v (the center of the colors used in v). We have at most 6 admissible pairs of neighbors of s (resp. t) and so at most 36 graphs to consider. For each graph we have to check if it is 2-connected (that can be done in O(|V | + |E|) time) and if it is not 2-connected to verify coloring conditions at each cut vertex that can be done in constant time for a given vertex and so with an O(|V |) complexity.

Note that Algorithm 1 cannot be extended neither to find 3 or 4 color-disjoint paths on a graphs with = 4 nor to the case of 5.

C. Directed acyclic graphs

The Directed Acyclic Graphs (DAGs) being the simplest non trivial case of directed graphs, we give, in this section, an algorithm for finding k color-disjoint paths in a DAG with the star property. Note that we are using a model with a directed graph obtained from the graph model by assigning an orientation to each arc. As each color is a star color we can associate to each color c its center v defined as the common vertex to all arcs with color c. If the color has only one occurrence we choose arbitrarily as associated center one of the end vertices of the arc containing this color. We will say that the color c is centered in v.

The algorithm given in the proof of the next theorem uses ideas of [START_REF] Chakaravarthy | New results on the computability and complexity of points-to analysis[END_REF], in particular that of layered digraph and a construction similar to that used to find a polynomial time algorithm for disjoint paths with forbidden pairs (Theorem 6 of [START_REF] Chakaravarthy | New results on the computability and complexity of points-to analysis[END_REF]).

Definition 1 (Layered digraph):

A directed graph G = (V, E) is layered if there is a layering function l : V ! [0, 1, . . . , (|V | 1)
] such that for every arc (u, v) 2 E, l(v) = l(u) + 1. We say that vertex u is in layer l(u) and arc (u, v) is in layer l(u). Layered directed graphs are acyclic.

Note that the computational time required by the algorithm is

O(|V ||E| 2k
) which is polynomial only when k is a fixed constant. However, in the next section we will show that in DAGs it is not possible to find an algorithm requiring a computational time polynomial in k. In detail, it is not possible to solve k-DCP in DAGs with the star property in less then

(|V | + |E|) O(k) time.
Theorem 4: There exists an algorithm that solves k-DCP in a DAG with the star property in time O(|V ||E| 2k

). Proof: Let D be a multicolored DAG and s and t be two given vertices. As we want to find dipaths from s to t, we can delete the vertices not on a dipath from s to t and so we suppose in what follows that D is this reduced DAG. Now s is the unique vertex with no predecessor and t the unique vertex with no successor. We first associate to a multicolored DAG D a multicolored layered DAG LD as follows. We denote by (v) the set of vertices preceding v, i.e; vertices u such that (u, v) 2 E. We topologically order the vertices of the DAG D, with the ordering function l : V ! N as follows:

l(v) = ( 0 when v = s, 1 + max u2 (v) l(u) otherwise.
In such an ordering t has the maximum level as there is a dipath from any vertex to t in the reduced digraph. In the graph D of Figure 6(a), we have l(u

1 ) = 1, l(u 2 ) = 2, l(u 3 ) = 3, l(u 4 ) = l(u 5 ) = l(u 6 ) = 4, l(t) = 5.
Now we replace every arc (u, v), such that l(v) > l(u) + 1, with a directed path P uv from u to v of length l(v) l(u). We assign to the first arc of the dipath P uv the colors of the arc (u, v) centered in u and to the last arc of the dipath P uv the colors of the arc (u, v) centered in v. Doing so we have obtained from D a layered digraph LD, such that there exist k color disjoint paths in D from s to t if and only if there exist k color-disjoint paths in LD from s to t. In Figure 6(b), we indicate the layered graph LD obtained from the digraph D of Figure 6(a). We have given a name to each arc with a lower index indicating the level of the arc; we also indicate in () the colors attributed to each arc. For example the arc (s, u 3 ) which had colors c 1 , c 4 has been replaced by a path with 3 arcs: e 0 at level 0 which gets the color c 1 (centered at s), e 1 and e 2 at level 2 which gets the color c 4 (centered at u 3 ).

Therefore, in what follows we consider a layered digraph D with two specific vertices s and t. To D we will associate a digraph H with two specific vertices s and t, such that there exist k color disjoint dipaths in D from s to t if and only if there exists in H a dipath from s to t. For the ease of reading we first give the transformation for k = 2.

H has as vertices s, t, and all the pairs of arcs {e i , f i } having the same level i, 0  i  l(t) 1, and no color in common. Now we join, by an arc in H, s to all the vertices (pairs) {e 0 , f 0 }. Similarly we join a vertex {e l(t) 1 , f l(t) 1 } in H by an arc to t. Finally, for 0  i  l(t) 2, we join in H a vertex {e i , f i } to a vertex {e i+1 , f i+1 } if in G we have the following properties:

• the terminal vertex of e i (resp. f i ) is the initial vertex of e i+1 (resp. f i+1 ) and • the set of colors of C(e i ) [ C(e i+1 ) centered at their common vertex u i is disjoint from the set of colors of

C(f i ) [ C(f i+1 ) centered at their common vertex v i .
Note that if u i 6 = v i the second property is always satisfied as the colors are star colors. Figure 6(c) indicates the graph H obtained from LD of Figure 6(b). For example, consider the pair of arcs {e 2 , f 2 }, which have different colors. Consider two paths ending in u 3 with e 2 and f 2 ; the path ending with e 2 cannot continue with e 3 which has a color in common with f 2 ; similarly the path ending in f 2 cannot continue with g 3 so we can have at u 3 either subpaths (e 2 , f 3 ) and (f 2 , e 3 ) or (e 2 , g 3 ) and (f 2 , e 3 ). In the graph H it means that the pair {e 2 , f 2 } is joined to the pairs {e 3 , f 3 } and {e 3 , g 3 }.

The transformation is done in polynomial time. Now the existence in D of two disjoint colored dipaths P = (s, e 0 , u 0 , e 1 , . . . , e l(t) 2 , u l(t) 1 , e l(t) 1 , t) and Q = (s, f 0 , v 0 , f 1 , . . . , f l(t) 2 , v l(t) 1 , f l(t) 1 , t) implies the existence in H of a dipath from s to t namely P Q = (s, {e 0 , f 0 }, {e 1 , f 1 }, . . . , {e l(t) 1 , f l(t) 1 }, t) and vice versa. Indeed s is joined in H to {e 0 , f 0 } if and only if e 0 and f 0 have no color in common; similarly {e l(t) 1 , f l(t) 1 } is joined to t if and only if e l(t) 1 and f l(t) 1 have no color in common. Furthermore {e i , f i } is joined in H to {e i+1 , f i+1 } if and only if P and Q are dipaths, i.e. the terminal vertex of e i (resp. f i ) is the initial vertex of e i+1 (resp. f i+1 ) and the the second condition on colors is satisfied. In the example of Figure 6(c), H has many dipaths from s to t. For example to the dipath P = (s, {e 0 , g 0 }, {e 1 , h 1 }, {e 2 , f 2 }, {e 3 , g 3 }, {e 4 , g 4 }, t) are associated in LD the two color-disjoint dipaths P 1 = (s, e 0 , e 1 , e 2 , g 3 , g 4 , t) and P 2 = (s, g 0 , h 1 , f 2 , f 3 , f 4 , t), and in D the two dipaths s, u 3 , u 4 , t and s, u 1 , u 2 , u 3 , u 6 , t. The transformation can be generalized to any k 2 but instead of using as vertices of H the pairs of arcs at the same level, we use the k-element subsets of arcs at the same level.

Deleting the vertices and arcs not on a path from s and t can be done in O(|V | + |E|) time. Finding the levels can be done in O(|V | + |E|) time. The transformation to a layered DAG can be done in O(|V ||E|) time. Note that each arc is replaced by a path containing at most one arc of each level and so the number of arcs at a given level is at most |E|. The graph H obtained in the transformation has therefore at most l(t)|E| k vertices and l(t)|E| 2k edges and so we get the complexity of the theorem as l(t)  |V | Remark 1: The previous algorithm can be adapted to find a minimum cost pair of color-disjoint paths by applying the following modifications. Let us consider a weight function on the arcs of a graph D. We attribute the original weight of the arc(u, v) to the first arc of the path replacing it in LD. Then in H we attribute to the edge joining s to {e 0 , f 0 } the sum of the weights of e 0 and f 0 , and to the edge joining {e i , f i } to {e i+1 , f i+1 } the sum of the weights of {e i+1 and f i+1 }. With these modifications, the shortest path in H corresponds to the optimal pair of color-disjoint paths in D.

Remark 2: We can also use the previous algorithm to find a pair of color-disjoint paths with the minimum total number of colors by applying the following modifications. In H, we assign to the edge joining {e

i , f i } to {e i+1 , f i+1 } a weight equal to |C((e i ) [ C(e i+1 )) [ C((f i ) [ C(f i+1 ))|.
The shortest path in the weighted graph H will correspond then to the pair of color-disjoint paths with the minimum number of colors.

VI. MAXIMUM NUMBER OF COLOR-DISJOINT PATHS

We aim at finding the maximum number of color-disjoint paths, formally:

Problem 4 (Max Diverse Colored st-Paths, MDCP): Given a multi-colored graph mG and two vertices s and t, find the maximum number of color-disjoint st-paths.

The corresponding decision problem is the following. Problem 5 (Diverse Colored st-Paths, DCP): Given a multi-colored graph mG, two vertices s and t, and an integer k, are there k color-disjoint st-paths? We show that DCP is NP -complete in the strong sense and that MDCP is hard to approximate within some bound, even with some restrictions on CPE and EPC. The proofs for this section are omitted and can be found in [START_REF] Bermond | Diverse Routing with the star property[END_REF].

Theorem 5: DCP is NP -complete in the strong sense, even in DAGs, if the star property holds and CPE and EPC are fixed with CPE 3 and EPC 3 or CPE 6 and EPC 2.

In the next theorem we give an approximation factor preserving reduction from Maximum Set Packing (MSP).

Definition 2 (Maximum Set Packing, MSP): Given a set X and a collection S of subsets of X, find the maximum cardinality set packing, i.e., a collection of disjoint sets S 0 ✓ S such that |S 0 | is maximized.

Theorem 6: MDCP is as hard to approximate as MSP, with |V | = |S|, even in DAGs and if the star property holds.

It has been proven (see [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF]- [START_REF] Kann | Maximum bounded 3-dimensional matching is max snpcomplete[END_REF]) that problem MSP is not approximable within O(|S|). Moreover, if the cardinality of all sets in S is upper bounded by a constant s 3 or the number of occurrences in S of any element is upper-bounded by a constant B 2, then the problem is AP X-complete.

Corollary 1: Unless P = NP , MDCP cannot be approximate within O(|V |) even if EPC is fixed, EPC 2. Moreover, it is AP X-hard if CPE is fixed, CPE 3. These inapproximability results hold even in DAGs with the star property.

The next results are expressed in terms of parameterized complexity [START_REF] Downey | Parameterized Complexity[END_REF]. Recall that a problem is fixed parameter tractable, and so is in FPT, if it can be solved in time

O(f (k) • |V | O(1)
) where the function f is polynomial and depends only on the input parameter k. A problem is W [1]hard if a problem of the class W [1] (e.g., deciding if the graph contains a clique of size k) can be reduced to it in FPT-time.

Theorem 7: MDCP is W [1]-hard where the parameter is the number of color-disjoint paths, even with the star property.

Corollary 2: MDCP is not in F P T , unless F P T = W [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF].

As |V | is an upper bound to any optimal solution of MDCP, Corollary 1 implies that, if CPE is unbounded, we cannot find an approximation factor better than |V |/c, where c is a constant. This corresponds to find c color-disjoint st-paths, where c is a given constant. In other words, the only way to cope with this problem (in a general graph with the star property) is to find a fixed number of color-disjoint paths. ) time. Note also that the transformation used in Theorems 5-7 makes use of simple graphs that can be easily turned into DAGs. This implies that no algorithm can solve k-DCP in DAGs in less then O(k) time and then the algorithm in Section V-C is basically the best possible w.r.t this lower bound.

(|V | + |E|)
The algorithm in Section V-A can be used to find an exact algorithm for MDCP when |C| = O(1). In fact, it is enough to search for the maximum k for which such algorithm returns k color-disjoint paths. As the maximum number of color-disjoint paths is upper bounded by , by using a binary search such an approach requires to apply at most log times the algorithm of Section V-A. The following corollary follows. We can use the algorithms for bounded degree presented in Section V-B for solving MDCP when  4. We get a polynomial algorithm for  3 and a 2-approximation algorithm for = 4 as the maximum number of color-disjoint paths is upper bounded by = 4 . The following corollaries follow.

VII. CONCLUSION

The results, presented in this paper, give an almost complete characterization of the problem of finding SRLG-disjoint paths in networks with SRLGs satisfying the star property. We summarize them all in Table I.

Fig. 2 .

 2 Fig. 2. Example 1.

2 Fig. 3 .

 23 Fig. 3. Example 2

Fig. 4 .

 4 Fig. 4. Color assignment for vertices with degree 3.

Fig. 5 .

 5 Fig. 5. Color assignment for vertices with degree 4.

  |X| = |C| = O(1) and |S|  2 |C| = O(1), it requires O(1) time. Therefore, finding k color disjoint paths requires O(|V | + |E|) overall time.

) v containing s and e 0 and f 0 Theorem 3 :

 03 the edges of the connected component containing t, we have C(e) \ C(f ) = ;, C(e 0 ) \ C(f 0 ) = ; and either [C(e) \ C(e 0 ) = ; and C(f ) \ C(f 0 ) = ;] or [C(e) \ C(f 0 ) = ; and C(f ) \ C(e 0 ) = ;] then 7 There exist two color-disjoint paths from s to t in G; 8 No 2 color-disjoint paths from s to t exist in G; Algorithm 1 solves 2-DCP in graphs with the star property and = 3 or 4 in time O(|V | + |E|).

Fig. 6 .

 6 Fig. 6. Transformations for the DAG.

However, Theorem 7

 7 implies that no FPT algorithms can be devised, unless F P T = W [1]; so it cannot exist an algorithm which finds k color-disjoint paths in O(2 k • poly(|V | + |E|)) time. Moreover, Theorem 1 shows that even finding a fixed number k 2 of color-disjoint paths is NP -complete. This implies that it is impossible to devise an algorithm which finds k color-disjoint paths in O((|V | + |E|) O(poly(k))

Corollary 3 :

 3 There exists an algorithm that solves MDCP if |C| = O(1) in time O((|V | + |E|) log ).

Corollary 4 :

 4 If  3, there exists an algorithm that solves MDCP in a graph, with the star property, in time O(|V | + |E|). Corollary 5: If = 4, there exists a 2-approximation algorithm for MDCP in a graph, with the star property, in time O(|V | + |E|).

  |V | + |E|) time Optimum in O(|V | + |E|) time = 4 any any Solvable in O(|V | + |E|) time for k = 2 2-approximation in O(|V | + |E|) time |C| = O(1), any any any Solvable in O(|V | + |E|) time Optimum in O((|V | + |E|) log ) time even without star

	Graph		EPC	CPE	k-DCP		MDCP
	Undirected	8	2 4	4 2	Strongly NP -hard for	6 + k	Not approximable within O(|V |)
	Directed Solvable in O(DAG  3 any any 3 3 2 6 unbounded Solvable in O(|V ||E| 2k 2 unbounded unbounded 3	) time	Strongly NP -hard Not approximable within O(|V |) AP X-hard
			unbounded unbounded			W [1]-hard
					TABLE I
				SUMMARY OF COMPLEXITY RESULTS.