Computational constraint models for decision support and holistic solution design

Summary. The paradigm of constraint reasoning, aims at creating computerized solution models to tackle combinatorial search problems. The methodology and principles of such models are based on relationships among data and variables, specified as constraints that must hold for a solution to solve a decision or optimization problem. The relationships can be dependencies of any kind: geographical, engineering, environmental, or economic. Constraint models have been developed to this date to provide proactive analysis of some climate change issues, such as investment planning in renewable energies over a given horizon. The challenge of computerized constraint solution models is their reliability and effectiveness to become real world implementations. This is feasible if : 1) the modeling approach taken is holistic and specifies the complexity of real world scenarios, and 2) the users feel involved and become actual actors in the decision process. Constraint models facilitate a holistic approach by focusing on the solution model, and allowing heterogeneous data, variables and constraint types to be modeled independently of their solving. In this article we give an overview of such approaches to foster the implementation of climate change solutions.

Introduction

Climate change is a fact. Whether human behavior is the major cause of it or not is no longer the core question. The issues today are manyfold: 1) monitoring the changes and contributing factors, 2) forecasting the evolution and assessing potential impacts, 3) modeling and implementing proactive solutions from a holistic perspective. This paper is concerned with the latest one. Thus it is not concerned with the causes or the problems of climate change, rather in solutions that can be put in place. The complexity lies in the interdisciplinary nature of the solution models, their scale, time span and of course the cost-effectiveness of their actual implementation. The main factors of climate change that we will consider in this short paper are:

• Heat, both in terms of abundant source of energy, and coping with increased temperatures. • Water, both in terms of scarcity and flooding.

Carmen Gervet

Regarding both factors, solutions can be global as well as local. As early as the 1920s, the Atlantropa project sought to bring together Europe and North Africa in one common electricity grid via a giant hydro power station in Gibraltar [START_REF] Lehmann | Infinite Power to Change the World: Hydroelectricity and Engineered Climate Change in the Atlantropa Project[END_REF]. The support for this project was limited to architects and planners from Germany and some northern European countries. It never saw the light due to several issues, some of them being the lack of involvment or cooperation of Mediterranean countries, and the poor study of the impacts it would have had on the local communities of the Mediterranean coast. More recently in the same spirit, the Desertec project was founded in 2009 [START_REF] Goudet | Desertec : le projet colossal du solaire saharien[END_REF]. It carried out several studies to develop a global renewable energy plan, by creating sustainable power plants in the Northern African desert, and transferring this energy through high-voltage current to Europe. The solar energy was the main source even though wind power plants were also considered. However, by 2014, 47 of the 50 initial shareholders had left the consortium [START_REF] Tagliapietra | Energy across the mediterranean: A call for realism[END_REF]. Clearly such visions come with a substantial financial commitment to become reality, but also a strong level of involvment from all parties, who can see their own gains and benefits in the short, medium, and longer term. They are global and complex projects which not only require a holistic perspective but also simulation tools to study the multiple issues at stake, to bring awareness and involvment of all the potential partners.

Today smaller scale solutions start to be implemented worldwide. Local initiatives are also developed to bring incentives to reduce home consumption of energy, and water. Desalination technologies are also being developed using solar power plants, often referred to as solar desalination [START_REF] El-Kordy | Economical evaluation of electricity generation considering externalities[END_REF] . For such proposals to be actually effective in the longer term, we also need to take many aspects and constraints into account as part of the solution design, and to raise acceptance and awareness of the different possible actors.

How computational decision models can contribute to guide the effective implementation of solutions under climate change

Let us illustrate the methodology with an example we investigated: the issue of techno-economics of renewable energy parks implantation [START_REF] Gervet | Optimal Allocation of Renewable Energy Parks: A two Stage Optimization Model[END_REF]. Applied research in in this field raises complex challenges of a technological, environmental, social, economic and political nature. Thus they involve many constraints among disciplines that do not necessarily interact. The case study took place in Egypt, a large country with a fast increasing population, an increased level of heat and an increased demand in electricity, including the use of air conditioning systems to reduce indoors heat in large cities. The national goal, back in 2010, was to determine "how to satisfy 20 percent of the forecasted energy demand in 2020 using renewable energies, at minimal cost". Even though this was a national project, it involved international technologies in Concentrated Solar Power (CSP), photovoltaic systems, wind turbines designs, as well as investments and planning. Under an Egyptian funding, the authors of [START_REF] Gervet | Optimal Allocation of Renewable Energy Parks: A two Stage Optimization Model[END_REF] built a prototype tool based on constraint technology, that served as much as a communication tool between the parties involved, as a simulation tool for the potential actors to evaluate the impact and effectiveness of their choices. The computational model specified the rules and conditions that must hold on the environmental, energetic, and economic levels, and the objective functions to optimize. Examples of possible constraint rules are: • A solar park must be at a given maximum distance of a connection point to the national grid,

• A solar park cannot be built on a depression area in the desert,

• The production rate of a wind turbine is bounded by certain values,

• The maximum investment per year is bounded by a certain cost.

The potential actors in such problems range from investors, engineers, economists, to local community representatives. This renders the actual implementation of a solution very complex in real life and often source of conflictsl. Hence the benefits of a holistic computational approach are numerous to guide the decision process, improve communication, and address different challenges in one integrated model. Furthermore, the technology combines the computational efficiency of powerful algorithms, with the modeling and expressive power of heterogeneous constraints. It brings together complementary fields and experts.

In the second section we will give an overview of constraint models and the methodological process. The third section will describe some existing solution designs under climate change. The fourth section will describe our vision for the next generation of holistic models coupled with interactive and persuavive interface to increase the involvement of the user, and his/her active role in the implementation process.

Constraint-based reasoning in a nutshell

The holy grail of constraint programming was "focus on the problem, the computer will take care of the solving". It is a powerful paradigm developed in the late 70ies in the field of Artificial Intelligence, to tackle complex planning and scheduling problems in areas such as transportation, production, networks, bioinformatics, configuration and logistics. The problems are of a combinatorial nature, which means that there is an exponential number of combinations of values to explore, when searching for a solution. The problem might end up being unsatisfiable: no solution that satisfies all the constraints exists. In this case one will need to account for possible data uncertainties, or soften certain rules or constraints that render the problem unfeasible. The essence of constraint programming is to model the problem independently of its solving, by focusing on the properties a viable solution should have, and letting the underlying algorithms prune out combinations of values that can never hold. Today the paradigm draws from areas wider than Artificial Intelligence and combines methods and models from graph theory, Operations Research, and multi-agent systems, to address real-world combinatorial search and decision problems. The field of constraint programming together with its application have been integrated in a comprehensive handbook [START_REF] Editors | Handbook of constraint programming[END_REF]. We define the notion of a constraint problem modelled as a constraint satisfaction problem as follows: Definition 1. A constraint satisfaction model is composed of a set of variables (unknown parameters), a set of domains where each variable can take its value from, and a set of constraints over the variables.

This definition has been extended to cases where the parameters defining the constraints can be uncertain, and with objective functions that turn the decision problem into an optimization problem. The methods to solve the decision problems are based on filtering and propagation techniques that prune the impossible values from the domains in a deterministic fashion. Let us illustrate this core technique, through a simple example. Basically if you are a sudoku player, you do constraint propagation and search when filling up the grid cells. The sudoku is a logic puzzle, which can be found in all newspapers today. We have a 9 by 9 grid, composed of 9 blocks of 3 by 3 cells. Each cell must take a value in {1, ..., 9} such that no two cells in one column, row or block can share a value. The model and techniques of constraint solving mimic at different levels of inferences (more or less global) the human reasoning. The basic approach is one of trial and error without accounting for the structure of the problem or the globality of the constraints. A constraint model of a sudoku problem corresponds to 1) the data being the cells that have a known value, the decision variables that are the open cells with domains {1, .., 9}, and the constraints that simply state that any two pairs of cells cannot take the same value within a row, column or block. Thus if a row has the values 1, 3 and 5 taken, these will be removed from the related cells domains by filtering out the values and the domains will be reduced to {2, 4, 6, 7, 8.9}. Any change in the domain of a variable, triggers the constraints involving this variable to be checked again, to determine whether it propagates a change or not in the variables domain. Once we reach a stage where no more domains can be filtered, in this deterministic manner, a search procedure is triggered to find possible values for the non instantiated variables. Global filtering techniques are available in the numerous systems that exist on the market today, leading to powerful filtering of domains before searching for solutions. For instance if two of the variables in a given row share the same two values, we can filter out these values from the remaining 7 variables denoting the other cells in this row, since none of them can take them or the problem would fail.

Constraint programming is very well suited for the kind of decision combinatorial problems where the number of potential combinations is large but few of them can lead to a solution (possibly none). Thus it can be of substantial help to seek solutions to new problems particularly of a holistic nature, with complex and heterogeneous constraints involved. It is possible that for such problems, taking all the constraints at hand into account does not describe any solution, and thus the model needs to be refined. If one or several functions are added to the problem, the issue is one of optimization under constraints and constraint programming can then be combined with global optimization techniques from Operations Research (such as Linear Programming or mathematical programming) [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF]. More information on constraint programming technology can be found in [START_REF] Editors | Handbook of constraint programming[END_REF].

The methodological process of designing and implementing solution models to real world problems is an iterative and incremental one, involving all potential decision makers, actors and domain experts in the specification of the problem. It consists of three main iterative procedures: 1) specification of the solution requirements, 2) solution design and implementation, 3) evaluation and testing. The methodology aims at ensuring an effective development process in the presence of heterogeneous sources of data, interdisciplinary sources of information, and a complex decision making process. It iterates over the definition phase, the construction phase and the visualization and interactive decision making phase. The construction phase is itself composed of two activities, the solution design and the programming activities. This incremental and iterative methodology is necessary to ensure validation of the model by all the potential actors. An example of such a methodological process was developed by a consortium of academic and industrial partners to build solutions to large scale combinatorial optimization problems, of which holistic constraint models for solutions under climate change is an element [START_REF] Gervet | Large Scale Combinatorial Optimization: A Methodology for Hybrid Models and Solutions[END_REF][START_REF] Gervet | Large Scale Combinatorial Optimization: A Methodological viewpoint[END_REF].

The methodology behind the models themselves, focusses on the design and implementation of practical solutions, satisfying geographical, economical or planning constraints at hand. In other words, by knowing the human factors that intensify climate change (e.g. factory farming, carbone dioxide emissions, energy sources), an expert can conceive means to reduce the impact of such factors. The idea behind constraint based models and their design is to seek practical and viable socio-economico solutions and identify realistic means to implement them. The key lies in the effectiveness of migrating from a current practice to new practices that would reduce the human impact factors on climate change, as well as viable means to cope with foreseen scenarios that will require drastic changes to our ways of living.

Designing a constraint model... Basically, a set of actors with complementary expertise, who seek the economic and societal viability of a new approach to water resource management, or migrating to renewable energy for a given country, needs to seek compromises between:

• Satisfying hard constraints such as ensuring that there will be enough resources to sustain the population, the demand can be fulfilled given the new means of production, the cost of implementing a new approach does not exceed a certain limit. These constraints heterogeneous and bring together technological, economical and societal aspects. They can often take the form of relational and linear or non linear formulas, over the variables we seek a value to (amount of production, potential relevant localizations, ...), and the data available in terms of existing resources, and limitations. • Reaching the objectives sought, such as by 2030 a given percentage of water resources comes from a desalination process, or a given percentage of electricity production, comes from renewable energy sources. Often the objective functions are multi-criteria ones, in the sense that a trade-off is sought to maximise for instance biodiversity, while ensuring a production level that is sustainable for the farmer. This multi-criteria approach ensures that all the relevant actors are involved in the design of the model, that it is viable, and represent a realistic transition from existing practices to more sustainable ones.

The iterative process of designing the model, evaluating the computerized solutions, and seeking experts and user feedback is a key component to the use of computational constraint technology to help guide the decision makers in the actual implementation of their solutions. It is also a valuable communication tool between the different actors who can see the effects of limitation of certain constraints on the solutions produced.

Example cases and thematic studies

To this date a large number of computational constraint models are proposed in applied research to address different aspects of climate change solution designs. We present a few to illustrate the approaches and their potentials. In the past 15 years, the novelty of these models is the motivation to design integrated systems that include many different aspects of real life issues in one system, including existing data, environnemental, economical, societal and technological constraints. In this short article one can not be comprehensive in the survey of existing models but wet give an overview and idea of existing approaches that investigate the means and viability of solution implementations to different issues related to climate change. These include water resources management, migration to renewable energy sources, and biodiversity conservation. It is important to note that constraint based models and decision support tools, focus on helping different parties and decision makers become actors in the implementation of solutions to a given challenge and not on detecting the problem that could result from climate change.

Water resource management

This field seeks means to handle water scarcity, costs and migration towards different systems. Some computational models have been proposed to help decision makers cooperate with a holistic perspective, including for instance the water resource components and the economic ones. A mathematical programming model, with the objective of maximizing economic profits from water uses in various sectors is proposed in [START_REF] Cai | Implementation of holistic water resources-economic optimization models for river basin management -Reflective experiences[END_REF]. Such a model aims at addressing both the environmental and economic issues. It is one typical example of large scale holistic modeling for integrated river basin management. It raises also the issues of the complexity of holistic models, the handling of uncertainty ubiquitous in such problems and the involvment of various decision makers. A thorough review of approaches to characterize the economic value of water usage, and to embed these in computational models can be found in [START_REF] Harou | Hydro-economic models: Concepts, design, applications, and future prospects[END_REF]. It presents various hydro-economic models addressing the issues of spatial and temporal dimensions of distributed water resource systems, infrastructure, management options and economic values in an integrated manner. These models specify hydrologic engineered systems while explicitly considering the economic nature of water demands and costs. Basically they provide a support for decision makers to analyze costs and profits, while considering the value of water services in planning and operation. As the authors say: " until now, hydroeconomic modeling has been practiced in academic and policy circles with limited implementation of study recommendations by water managers, operators, and practitioners. Hydroeconomic modelers can improve the impact of their work by collaborating with practitioners and extending existing (and trusted) operations models to include hydroeconomic components."

Renewable energy planning

Some computational models integrating economic, engineering and environmental aspects together are also being considered relative to the migration towards renewable energies to produce electricity. The need for clean energy is recognized worldwide not only to face global warming and CO2 emissions, but also to reduce grounds for international conflicts. National and international targets are being set [START_REF] Bull | Renewable energy today and tomorrow[END_REF][START_REF] Bull | The integration of renewables[END_REF]. There are many aspects to the development of renewable energy technologies which can be broadly categorized into engineering & technological advancement aspects, versus techno/economical and commercial ones. The engineering components deal with the construction of renewable plants that are reliable, effective and realistic including essentially hydro, solar (photo-voltaic and concentrated solar power), wind and bio-fuel. The techno-economical study of renewable energy on the other hand, investigates gradual implantation of Renewable Energy (RE) systems for a given country such that the installation and maintenance costs are minimized and the short/long term returns on investment are maximized. Studies in this field investigate country profiles in terms of energy demand, available resources, anticipated renewable engineering cost reductions [START_REF] Loiter | Technology policy ad renewable energy:public roles in the development of new energy technologies[END_REF]. However, more is needed as highlighted in [START_REF]The economics of renewable energy[END_REF], that "there is little economic analysis of renewable energy". The main objectives of studying the economics of RE is to attract investments (national and international) and set realistic targets and strategies that will remain so in the longer term.

Comprehensive surveys are now available discussing the trends and current improvements in the cost, performance, and reliability of renewable energy systems [START_REF] Bull | Renewable energy today and tomorrow[END_REF]. Clearly electricity from renewable energy remains generally more expensive than from conventional fossil-fuel sources. However, the cost of electricity from RE sources has been falling steadily for the last two decades and various estimates have been derived in terms of "expected cost of electricity production from RE sources" [?]. Today wind energy is the least expensive option but requires more maintenance, and is space consuming compared to photo-voltaic solar panels which however, are currently more expensive. Note that the forecasts in price reduction are promising though, as shown in Figure 1.1 [START_REF] Bull | Renewable energy today and tomorrow[END_REF]. This indicates that taking into account forecast measurements is a strong element of effective decision making.

Fig. 1.1. RE costs forecast

Based on existing forecast studies, and each country renewable resources, which REs or portfolio of RE should a given nation invest in? How much should be invested now, or in 15 yeas time? These are questions at the heart of the "economics of RE" for which our decision support tool aims to seek an answer. We seek the best tradeoff cost/return on investment by taking into account physical installation constraints as well as energy requirements and costs.

The author in collaboration with the German University in Cairoand the NREA (New ad Renewable Authority in Egypt) studied this problem focussing on Egypt, where data and a govermental interested were provided [START_REF] Gervet | Optimal Allocation of Renewable Energy Parks: A two Stage Optimization Model[END_REF]. Our goal was to build a decision support tool that will provide private and governmental investors into renewable energy systems, valuable insights to make informed short and longer term decisions with respect to the creation and placements of solar and wind turbine parks in Egypt. Egypt is growing at fast pace and relies extensively on fossil fuel as shown in the latest earth-trends survey [START_REF]Earth Trends. Energy and resources[END_REF]. Egypt enjoys excellent wind and solar resources and there are tremendous potentials for investment towards local consumption and even export. Research and onsite-projects are being carried out with a growing trend.

A short-term government plan was to meet 20% of Egypt electricity demand by 2020 using RE sources. While wind farms installation is currently cheaper than solar panels of Concentrated Solar Power (CSP) plants, there are strong arguments in favor of solar energy. Thus it is essential to consider both. Basically solar energy can be installed on small surfaces (little cable and maintenance required), offers more stability especially in Egypt (sun is less dependent on season fluctuations for countries located on the sun belt), plus wasted heat has the advantage of being usable for water desalination [START_REF] El-Kordy | Economical evaluation of electricity generation considering externalities[END_REF]. Egypt can become a strong player in wind and solar energy. However, a specific strategy is still to be determined, together with investments.

The optimization problem we addressed is defined as follows. Given the country of Egypt with its data and constraints: 1) Egypt map of populated areas, 2) Wind and Solar atlas, 3) electricity grid map, 4) current and forecast energy cost per RE resource, 5) current and forecast energy demands per month, 6) a set of potential RE park locations; determine the set of energy parks to be invested in today, the set of energy parks to be invested in the future (e.g. 10-20 years time), such that 20% of the current and forecast energy demand are covered for each month of the year, and the anticipated financial cost is minimized. The cost is determined in terms of sum of total costs associated with each potential park: cost of connection to the grid, cost of installation, and cost of park maintenance. The core contribution was a portfolio selection model for renewable energy parks, such that planning for both short and medium term park installation is seen as one decision problem. One key component to the realistic nature of the model lies in the data made available which consisted of wind and solar atlas, electricity grid and cost figures. The wind atlas for Egypt in the form of a hard copy document, was obtained from the NREA, who took measurements over 14 years in partnership with the Danish Ministry of foreign affairs (1991)(1992)(1993)(1994)(1995)(1996)(1997)(1998)(1999)(2000)(2001)(2002)(2003)(2004)(2005). It provides a comprehensive overview of the wind resource over the entire land area (and sea) of Egypt. The maps produced indicate the mean power density, and wind speeds at a height of 50m over the actual land surface. It gives for a set of specific locations, the prediction of the average yearly energy production of a specific wind turbine or wind farm based on actual measurements of wind speed and direction [START_REF] Hansen | Wind Atlas For Egypt[END_REF]. The solar atlas fo Egypt, established in 1998 as part of a USAID project (United States Agency for International Development) and managed by the NREA, is a document including maps of solar energy density for each month. The data is the result of measuring the solar radiation daily in ten locations between 1980 and 1988. The maps were produced using a computerized model that distributes the daily value of global solar radiation into different energy bands [START_REF] Mosalam | Solar energy variability over horizontal and inclined passive systems in Egypt[END_REF].The different constraint models and algorithms used can be found in [START_REF] Gervet | Optimal Allocation of Renewable Energy Parks: A two Stage Optimization Model[END_REF], and we illustrate in Figure 1.2 the decision support tool, designed to help the decision makers simulate different scenarios to take informed planning and investment decisions.

Other approaches and research developments aim at using remote sensing data to monitor climate change [START_REF] Posselt | Remote sensing of solar surface radiation for climate monitoring the CM-SAF retrieval in international comparison[END_REF], and integrate such studies to build decision support systems for the planning of solar energy parks. For instance a study combines a Geographic Information System (GIS) tools or multicriteria decision making optimization models to determine the optimal placement of photovoltaic solar power plants in southeast Spain [START_REF] Garcia-Cascales | Geographical Information Systems (GIS) and Multi-Criteria Decision Making (MCDM) methods for the evaluation of solar farms locations: Case study in south-eastern Spain[END_REF]. Such approaches bring together the analysis of data with the decision making process. Just like in the sudoku example, the power of cosntraint reasoning make it possible to reduce the areas of study by discarding the locations that cannot be used to implement renewable energy plants, because the cost to reach the grid is too high, or the location is to close to living areas, or corresponds to a desert depression, etc.

Biodiversity management

Another thematic strongly linked to human impact on climate change is biodiversity. A key challenge is the field of ecosystem services, and enhancing biodiversity lies in the policy and decision making processes. An increased number of constraint-based models seeks to evaluate the feasability of solutions and guide decision makers in relation with the environment and the actors involved. Some surveys article and specific case studies have been developed. We refer in particular to studies in the European Union [START_REF] Maes | Mapping ecosystem services for policy support and decision making in the European Union[END_REF], and different constraint based optimization models. Studies investigated computational models to help design reserve networks for the persistence of biodiversity, with the same idea of developing tool that help dfferent actors communicate through the use of decision aid tools. In [START_REF] Cabeza | Design of reserve networks and the persistence of biodiversity[END_REF] a computational site-selection tool applied to conservation planning is proposed bringing together scientists, managers and investors. Another set of computational constraint models also in the form of decision support tools, relate to conservation planning tools to seek means to reduce species extinction and preserve biodiversity. These studies address similar challenges related to the necessary involment of different parties, and modelling of the constraints at hand in a holistic manner. We can refer in such cases to budgetary, ethical, and other sociopolitical constraints [START_REF] Sarkar | Biodiversity conservation planning tools: present status and challenges for the future[END_REF].

Perspectives

In the future, we foresee increased use of complex and holistic computational constraint models to implement climate change solutions, such as water-use efficiency, solar energy-use efficiency or bio-diversity management. They will involve many more actors and decision makers by integrating all components in one tool. Research efforts in this field of Artificial Intelligence and Operational Research address the technical and modeling challenges, to handle the spatio-temporal aspects of planning new solutions, as well as the handling of uncertainties in the data available and forecasted.

Also, to help foster such tools to be active support and communication tools among different actors, we need to render them easy to use, attractive and interactive. Indeed, if current behaviors, local as well as global are still passive, reasons can be that individuals do not feeling concerned, or information not being accessible (possibly to avoid non productive states of fear or panic), or feel powerless. Some studies related to this aspect investigate the "knowledgeignorance paradox" [START_REF] Ungar | Knowledge, ignorance and the popular culture: climate change versus the ozone hole[END_REF]. Recent research in the field of persuasive computing with serious games go in this direction. Their aim is to help the user feel engaged, involved and actor in the implementation of changes. In [START_REF] Krotoski | Serious fun with computer games: Sophisticated multimedia experiments offer platforms for learning about science through play[END_REF], a set of approaches are discussed where various games are presented with different global warming scenarios. " Players explore geoengineering, alternative energy sources and other options for protecting the planet over the next 200 years. " The game presents various realistic predictions for different climate change models and allow the player to engage with different climate-change challenges. The ultimate goal is to bring awareness to the issues and make players, actors of change. Such approaches are to be used for local aspects of energy saving and water consumption in private homes.

However, we do believe that they can also be embedded in large scale constraint and decision models, which nowadays present a complex and integrated view of solutions design (economics, engineering, environmental), and be tailored to decision makers from different fields and expertise. As a conclusion, computational constraint models can help to simulate different scenarios and let the user see the impact of their actions or decisions. In general they aim at answering questions such as "how, when and where to migrate to new solutions (e.g. renewable energy parks, hydro-economic models, river basin plans), such that a set of environmental, social, technical and economic constraints are satisfied simultaneously". They are also a powerful communication tool among actors from different fields; The methodological process to build such models involves all the relevant parties to specify the requirements and existing constraints. The final tool can benefit from interactive interfaces to the computerized solutions. Enhancing such interfaces with techniques from persuasive computing and gamification, can involve the end-user further, increasing his awareness and make him actor in the implementation of the solutions.

Fig. 1 . 2 .

 12 Fig. 1.2. Prototype tool output


Nadeem Al-Kurdi

Benjamin Pillot

Carmen Gervet

Laurent Linguet

Towards robust scenarios of spatio-temporal renewable energy planning: A GIS-RO approach

Keywords: Renewable energy planning, Geographic Information systems, Robust optimization

Solar-based energy is an intermittent power resource whose potential pattern varies in space and time. Planning the penetration of such resource into a regional power network is a strategic problem that requires both to locate and bound candidate parcels subject to multiple geographical restrictions and to determine the subset of these and their size so that the solar energy production is maximized and the associated costs minimized. The problem is also permeated with uncertainty present in the estimated forecast energy demand, resource potential and technical costs. This paper presents a novel combination of Geographic Information Systems (GIS) and Robust Optimization (RO) to develop strategic planning scenarios of a collection of parcels that accounts for their spatio-temporal characteristics, and specifically their hourly radiation patterns that are location dependent, to best fit the network temporal demand and minimize technical costs. The problem is formulated as a GIS spatial placement problem and a RO fractional knapsack problem to plan the effective power penetration and geographical suitability of new PV facilities. The combination GIS-RO generates an excellent decision support system that allows for the computation of optimized parcel scenarios (locations, sizes and power). The qualitative and quantitative effectiveness of the approach is demonstrated on real data on the French Guiana region. Results show that the proposed approach provides reliable fine grained planning that also accounts for the risk adversity of the decision maker towards forecast demand and solar potentials.

Introduction and related work

Energy transition from a high-carbon regime born of fossil fuels to low-carbon solutions is a major challenge of current societies [START_REF] Bolwig | Review of modelling energy transitions pathways with application to energy system flexibility[END_REF]. Most of the energy planning strategies therefore aim at enhancing the share of renewable energy (RE) sources within power networks [START_REF] Hache | Renewable energy source integration into power networks, research trends and policy implications: A bibliometric and research actors survey analysis[END_REF]. When those energies are dispatchable, the integration remains pretty straightforward [START_REF] Dotzauer | How to measure flexibility -Performance indicators for demand driven power generation from biogas plants[END_REF][START_REF] Purkus | Contributions of flexible power generation from biomass to a secure and cost-effective electricity supply -a review of potentials, incentives and obstacles in Germany[END_REF]. However, when it comes to volatile, or intermittent RE sources, this is no longer true. Their unstable and variability nature implies that the resulting aggregated power injected into the grid may threaten network's stability by not matching the power demand [START_REF] Hache | Renewable energy source integration into power networks, research trends and policy implications: A bibliometric and research actors survey analysis[END_REF].

Thus, the full problem of integrating intermittent RE sources in power networks involves irregular spatio-temporal energy potential patterns, related to the location and dimensions of power facilities. It is a multi-criteria uncertain optimization and planning problem that combines the spatial placement of candidate parcels for installing power facilities subject to geographical constraints and temporal resource constraints, and the selection (location, size and capacity) of optimal plants such that the power into the network is increased at minimal costs and short-term unpredictability is limited to an acceptable level.

Taking into account spatio-temporal energy potential data, together with heterogeneous land, network, and technico-economic constraints for effective renewable energy planning remains a challenging multi-dimensional problem permeated with uncertain data [START_REF] Ramirez Camargo | Spatiotemporal modelling for integrated spatial and energy planning[END_REF]. The computational approaches are broadly divided into two research streams: 1) geographical information system (GIS) modeling with multi-criteria decision-making (MCDM) [START_REF] Ali | GIS based site suitability assessment for wind and solar farms in Songkhla, Thailand[END_REF][START_REF] Castro-Santos | Planning of the installation of offshore renewable energies: A GIS approach of the Portuguese roadmap[END_REF][START_REF] Ozdemir | Multi-criteria decision-making in the location selection for a solar PV power plant using AHP[END_REF][START_REF] Garni | Solar PV power plant site selection using a GIS-AHP based approach with application in Saudi Arabia[END_REF], and 2) bottom-up engineering approaches [START_REF] Hache | Renewable energy source integration into power networks, research trends and policy implications: A bibliometric and research actors survey analysis[END_REF][START_REF] Pfenninger | Energy systems modeling for twenty-first century energy challenges[END_REF][START_REF] Barbosa | Hydro, wind and solar power as a base for a 100% Renewable Energy supply for South and Central America[END_REF][START_REF] Ramirez Camargo | Spatiotemporal modelling for integrated spatial and energy planning[END_REF]. GIS models with MCDM focus on providing suitability maps based on static resource assessment and expert-based decision criteria. The maps depict areas with their respective weighted criteria values to be used in the MCDM model, such as economic, environmental or technical ones. These approaches do not aim at optimizing the actual parcel selection that would require taking into consideration the short-term temporal variation of both the resource and power demand, or their evolution in the long-term. On the other hand, bottom-up engineering approaches allow for time simulation and optimization of given energy system configurations. Their main objective is to guide energy policy road map often at a national scale and longer time horizon. This systemic approach gives a significant insight into the potential contribution of RE sources [START_REF] Breyer | North-East Asian Super Grid: Renewable energy mix and economics[END_REF][START_REF] Breyer | Solar photovoltaics demand for the global energy transition in the power sector[END_REF], but does not aim at identifying physical parcel locations. Similarly [START_REF] Gervet | Optimal allocation of renewable energy parks: a twostage optimization model[END_REF] addresses the resource management problem as a knapsack problem, that shows the suitability of linear programming to select among experts' given parcels, the ones with highest resource potential. It does not consider the hourly temporal patterns of the different sites and their projected uncertainty, the possibility to consider a fraction of a given parcel, nor the impact of geographical restrictions and distances, and the complexity of the associated technical costs.

In summary, to date we are not aware of computational approaches that tackle the spatio-temporal optimization problem consisting of identifying the best parcels that increase solar energy penetration into the network at minimal cost, while satisfying a region's specific constraints (terrain, resource, infrastructures, etc) and related costs. This paper addresses this problem by proposing a two-steps specification in terms of a spatial placement and a resource planning problem, and we propose an integrated computational approach. The approach contributes a novel framework based on GIS spatio-temporal data and constraint processing, connected to a Robust Optimization (RO) knapsack model to plan renewable energy scenarios. The combination GIS-RO generates an excellent decision support system that allows for the planning of parcel scenarios (locations and areas) that will best increase the RE power into the network at minimal cost, according to the decision maker risk adversity. A GIS can handle very large volumes of data, including remote sensing images for solar radiation indicators, land use maps, and various networks maps (electrical, roads, water). The application of global and multi-layers geographical constraints and various control parameters allow for an effective deterministic pruning of the region, to determine suitable candidate parcels, and their relevant properties without impairing the optimization problem.

The core contributions of this paper are: 1) the specification of a complex spatial placement and planning problem, 2) a computational approach that efficiently exploits GIS geographical constraints, and makes powerful use of large scale spatio-temporal environmental data, and 3) an integration of the spatial analysis with a robust optimization module through a comprehensive set of resource and contextual features. Through the use of Robust Optimization, data uncertainty present in the forecast figures for the planned horizon is tackled with a measure of robustness, allowing best and worst case scenarios to be studied according to various risk adversity positions of the decision maker.

The GIS-RO framework presented in this paper, is applied to a real world challenge of PV solar power plants planning in the region of French Guiana. It illustrates the qualitative and quantitative efficiency of the approach as a decision support system providing solution scenarios. The paper is organized as follows: Section 2 describes the problem and overall approach; section 3 presents the GIS module; section 4 the robust optimization model; section 5 is the experimental section based on a real-world case study for robust spatial decision making from time series resources; and section 6 concludes the paper.

Problem description, application and approach

The problem is motivated by a renewable energy scenario planning problem from the 2015 Energy Transition Act. France's energy policy has the target for overseas regions, in particular French Guiana, of 50 % of renewable energy in final consumption in 2020 and full energy self-sufficiency by 2030 [START_REF]CTG: Programmation pluriannuelle de l'énergie (PPE) 2016-2018 et 2019-2023 de la Guyane[END_REF]. The challenge is to identify suitable candidate parcels for RE parks and determine the ones, and their optimal size, that would maximize power network contribution at minimal costs. A candidate parcel must satisfy a number of geographical constraints, including topographic land use restrictions, type of ground surface, be at a maximum distance threshold from the electrical grid, and have a maximum surface with limited land slope. These constraints bound the areas for candidate parcels.

The scenarios for the best parcels selection deal with the resource potential and costs associated with each candidate parcel. The intermittent resource follows a temporal pattern specific to the geographic location. The costs are mainly technical costs (installation, maintenance, grid connection) that depend on the size of the parcel and its distance to the grid. These data have a degree of un-certainty in terms of their future value. The full problem can actually be defined as a spatial placement problem to identify candidate parcels, and a fractional uncertain knapsack problem with forecast time-series resource, to compute scenarios of optimal parcel selection and sizes. This paper aims at defining and showing the strengths of a combined GIS and RO computational approach to tackle complex spatial decision making problems with time-series resources, with application here to solar energy placement and planning.

Integrated computational work-flow

The work-flow depicted in Fig. 1 best describes the computational process and integration of the two modules. We first describe the main inputs, then each module. Geographical data layers and control parameters input the developed GIS GREECE module, which implements methods to determine the candidate parcels, and contributes a despatialization of the relevant features for each parcel (resource pattern, maximal size and costs), needed to enrich the RO model.

Fig. 1: GIS-RO integrated workflow

Data, constraints and control parameters In GIS terminology, the concept of layer corresponds to geographic datasets. When the dataset is an image, the term Raster is commonly used. The geometric objects are in vector mode and can be specified as polygons, lines or points. As depicted in Fig. 1, input data layers correspond to: 1) the study region or base layer, 2) the restricted area layers, 3) specific objects for which distance to resulting polygons must be computed (e.g. road, grid), 4) terrain features (land use and topography) and 5) the resource of interest (here solar radiation maps).

The restricted area layers stand for polygons where facilities cannot or should not be established. Typically, they include urban areas, ecological zones, water-courses, military sectors, cultural heritage, etc. They may also represent zones too far from specific objects (e.g. electrical grid). Geographic elements for which distance must be computed can be of any kind but are generally related to connection and accessibility costs such as road and grid networks. Topography and land use allow terrain to be characterized within each polygon. Finally, resource dataset is a set of raster or vector processed images, potentially with time series. Data layers and maps are retrieved from national and international geographic databases or remote sensing image processing.

The range control parameters are set by the user, and allow for different land management scenarios to be generated. Buffers surrounding geographic objects depend both on their type and on the kind of power station. Distance thresholds to given layers (e.g. road network, electrical grid) stand for the limit beyond which establishing a facility is not economically viable. Finally, land surface area specify a region's land management in terms of minimum and maximum allowed surface thresholds. Smaller or larger parcels might respectively be excluded from the study, or partitioned into suitable smaller parcels.

GIS module: GREECE

We specify the Geographical REnewable Energy Candidate Extraction problem below, then describe our spatial partitioning and placement solution methods. The set P of candidate parcels The de-spatialized resource time series and geographical features for each parcel Such that the following geographical restrictions hold:

A candidate parcel is geographically disjoint from all layers of restricted areas The surface of a candidate parcel is within given bounds A candidate parcel is within a bounded distance from the threshold layers

For space reasons, we give the main procedure in Algorithm 1, the spatial partitioning algorithm, and describe our spatial slicing and extraction methods, developed with Python GIS packages. The general procedure is decomposed in two main steps: 1) spatial placement and partitioning (Alg.1: line 2-10) , 2) conversion of the resulting polygons defined by their geographical coordinates into de-spatialized items with relevant features (Alg.1: line 11-20). The set of relevant built-in Python GIS functions for topological, raster, set and graph operations is defined (packages used: geopandas, shapely, rtree, gdal [START_REF]GDAL/OGR contributors: GDAL/OGR Geospatial Data Abstraction software Library[END_REF], numpy [START_REF] Van Der Walt | The numpy array: A structure for efficient numerical computation[END_REF], and networkx). The second step (Alg.1:lines 4-10), consists in filtering in a deterministic manner the polygons belonging to this set, based on their surface and distance to the grid. First we identify the parcels whose surface is beyond the allowed threshold. We developed a 2D space partitioning approach based on a k-way graph partitioning method, that partitions these parcels into smaller ones of suitable sizes (Algorithm 1: line7). Then, we prune further the resulting set of potential parcels according to the minimal surface threshold and distance to the grid, illustrated in Fig 2 (b). This last step is best handled using GIS geographical metric operators (Alg.1: lines 8-10). The extracted and computed parcels can all contribute to a solution, without inconsistent pruning of viable parcels from the standpoint of the threshold and land restriction constraints. Fig. 2 illustrates the spatial layers masking process as well as the pruning of parcels below a surface threshold, and beyond a distance threshold to network layers (grid, roads, ...). Spatial partitioning method To partition a polygon into smaller plots of equal size, we propose a k-way graph partitioning approach, depicted in Alg. 2. First, we specify the initial polygon as a honeycomb mesh, that is a set of connected hexagonal plots of given size (line 6). We then map the mesh to a graph, and apply a k-way graph partitioning (lines 7, 20-29). Each hexagon denotes a vertex connected to its concomitant neighbors by unweighted and undirected edges. The k value is first initialized using a desaggregation factor, that sets the size of each hexagon (lines 3-5). The bigger the factor value, the smaller each hexagon and thus the more refined is the mesh. Each vertex is weighted with the corresponding hexagon surface. The weight of the sought clusters (final plots) is initialized (lines 8-13), to feed the k-way graph partitioning (line 15). The procedure derives k clusters of vertices, to reach the surface threshold of each plot. The algorithm minimizes the number of edge cuts and forces contiguous partitions [START_REF] Karypis | METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices[END_REF], so that Algorithm 2: Surface partitioning the final aggregates present round-like geometries. The algorithm was developed using Python library networkx and the METIS package [START_REF] Karypis | A fast and highly quality multilevel scheme for partitioning irregular graphs[END_REF]. Finally the k-clusters are translated into k polygons (lines 17-18).

Example 1. The figure illustrate a 16-way graph partitioning of a km 2 polygon into plots of 50 km 2 , using an hexagonal honeycomb mesh. k is initialized to 781 50 . The algorithm derives 15 plots between 49 km 2 and km 2 plus one (marked with an asterisk) which fills the leftover space (≈ 32 km ). The output is a finite set of polygons of acceptable surface (below the maximum threshold).

* 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Contextual data and resource time series de-spatialization

Geospatial data is an invaluable source of contextual information, to characterize in general, multiple land features and resources, but also their proximity with all sorts of infrastructure networks. The challenge when dealing with optimization problems evolving around resources, costs and constraints, is to seek a computational approach to specify and solve a problem as closely as possible to its real setting. A contribution of the proposed GIS-RO framework is to achieve this by using the qualitative and large spatio-temporal and contextual information analyzed and extracted through GREECE, with a de-spatilization process.

The goal is to convert the polygons into items without their geo-referencing, and to associate to each the features relevant to the optimization module. Regarding energy planning, the features must capture many land properties, and resource time series, but also dimensions and distances that will allow a reliable conversion to technical costs for each candidate parcel. The localization and maximal surface of a candidate parcel can provide numerous relevant information from the intersected data layers: 1) the distance to specific infrastructures such as substations, electrical grid or road network contributes to assessing energy losses as well as accessibility costs, 2) the maximal surface is linked to construction and maintenance costs [START_REF] Teixeira | Forest biomass power plant installation scenarios[END_REF][START_REF] Ali | GIS based site suitability assessment for wind and solar farms in Songkhla, Thailand[END_REF][START_REF] Garni | Solar PV power plant site selection using a GIS-AHP based approach with application in Saudi Arabia[END_REF]. In addition, terrain slope is a critical criterion for establishing power facilities [START_REF] Garni | Solar PV power plants site selection: A review[END_REF][START_REF] Woo | Optimizing the location of biomass energy facilities by integrating Multi-Criteria Analysis (MCA) and Geographical Information Systems (GIS)[END_REF]; in the same way, final cost might also be affected by land type and land use, or even the shape of the parcel. In the case of solar and wind energies, geo-referenced resource maps are available from satellite images or field studies [START_REF] Fillol | Spatiotemporal indicators of solar energy potential in the Guiana Shield using GOES images[END_REF][START_REF] Albarelo | Optimizing the heliosat-II method for surface solar irradiation estimation with GOES images[END_REF][START_REF] Ali | GIS based site suitability assessment for wind and solar farms in Songkhla, Thailand[END_REF]. By overlaying the previously sliced polygons with these raster images, it is therefore possible to aggregate the resource within each parcel. Essentially, the de-spatialization consists in translating the geography of each candidate into either static or dynamic quantifiable features. These features can then be integrated into energy models, converted into construction and operation costs, or used as constraints or in the objective functions of the optimization model. In the case of solar PV, GREECE extracts the following parameters from each candidate parcel: area, shape, distance to the grid, land use share, elevation, slope, aspect and solar GHI time series (Alg. 1:lines 13-20). The whole implementation has made use of the python libraries referred earlier. SURFACE(p) provides information on the maximum power plant capacity that could eventually be set up within the parcel. SHAPE ranges from 0 to 1 and measures the roundness of a parcel, that is how spread out a solar PV plant might eventually be. DISTANCE to the grid is computed from the polygon centroid and is used to get both connection costs and transmission losses. Land use share can be correlated to construction costs, as well as elevation (from DEM h) using SLOPE and ASPECT. They may also be used as exclusion thresholds. Land use share is retrieved by computing the intersecting area between the given parcel and each attribute of a land use layer LU layer (line 15). Elevation, slope and aspect are retrieved from the 3 arc second SRTM-based digital elevation model (DEM) [START_REF] Jarvis | Hole-filled SRTM for the globe Version 4[END_REF] and by calculating average and standard deviation from raster cells overlapping with each candidate parcel (lines 17-18). Finally, solar GHI time series are obtained in the same way as with the DEM but for as many time steps as available solar radiation maps (line 20). As a result, each candidate parcel is now a compound item with geometric and terrain features, and time series of solar GHI values. In the case of solar PV, we have also converted GHI into power by adapting the pvlib library from the Sandia National Laboratory (SNL) [START_REF] Holmgren | Pvlib Python: a Python package for modeling solar energy systems[END_REF].

Optimization module -fractional knapsack approach

The Optimal planning and sizing of PV plants (OPSPV) is an optimization problem permeated with uncertainty, rooted in projection estimates from current data relative to the growth of energy demand and the resource values. As shown in Fig. 1, it takes the candidate parcels with their de-spatialized features to select the ones and their optimal size such that the PV power penetration in the network is maximized at minimal cost. We propose a robust optimization approach based on the seminal works of [START_REF] Ben-Tal | Robust solutions of uncertain linear programs[END_REF][START_REF] Chinneck | Linear programming with interval coefficients[END_REF], that specifies uncertainty using deterministic intervals. They denote the robust bounds within which the uncertain data is known to take its value. This modelling approach enables reliable best and worst case planning scenarios to guide the decision makers, and to assess the impact of his risk adversity impact on the output scenarios. The specification of the problem is given in Fig. 3.

Robust constraint optimization model

The OPSPV, energy strategy planning problem can be modelled as a fractional knapsack problem with additional constraints. In this analogy, the knapsack corresponds to the forecast energy demand to be provided by existing and new intermittent RE sources (in KW/hr), and the items are the candidate parcels with their potential supply (KW/hr) plus their associated technical costs (installation relative to the size thus production (e/KW ), and connection to the grid and substation (e). The objective is to maximize hourly penetration of additional RE power in the network while minimizing global costs.

We first specify the problem and then describe the model developed in terms of variables, constraints and cost functions.

Variables We consider two sets of variables that need to be linked to each other. Boolean variables relate to the selection or not of a candidate parcel, needed to determine whether the unit connection cost is applied or not (Ccon i ). The area variables, ranging over a real interval, are involved in the energy production The set of parcels where power stations will be built The surface to consider for each candidate parcel that is selected Cost functions:

Sum of all costs of PV plant installation C = Σi(Ccapi + Copi + Cconi + Cstai) Unit capital cost for installing a PV power plant (e) Ccapi Annual operational cost per new PV plant (e)

Copi Unit connection costs for each new PV plant, transmission lines (e) Cconi Capital cost for new substation (e) Cstai Total added PV energy production ΣtP Vt Such that the following constraints hold:

PV newly added production plus existing production are below the hourly demand PV existing and new production are less than 35% of the total energy demand per hour PV parcel size cannot exceed a maximal set size Fig. 3: OPSPV problem specification constraint and the installation, capital and operational costs, that depend on the size of a new PV plant.

∀ i ∈ N, B i ∈ {0, 1} 1 if parcel is selected, 0 otherwise ∀ i ∈ N, SA i ∈ [0.00..Smax i ] Area of a parcel

Knapsack constraints

The first set of constraints relates to the forecast energy demand, using existing resources augmented with new PV production. It seeks to determine the capacity of new PV plants to contribute to the anticipated demand. Two scenarios are considered: 1) best case scenario (highest PV energy forecast and lowest forecast demand) and 2) worst case scenario (lowest PV energy forecast and highest forecast demand). This allows to study the impact of the decision maker risk adversity in planning the creation of new PV plants.

Best case scenario:

∀ t ∈ H, Σ i SA i × P pv t,i + Eint t + Ep t ≤ Dem t Worst case scenario: ∀ t ∈ H, Σ i SA i × P pv t,i + Eint t + Ep t ≤ Dem t
Network penetration constraints The second set of constraints states that the amount of intermittent energy resource into the network should be less than 35 % of the total forecast energy demand per hour (upper bound) [START_REF]EDF: Systèmes énergétiques insulaires Guyane -bilan prévisionnel de l'équilibre offre / demande d'électricité[END_REF]. The time stamp is the hour. It is also set for the best and worst case scenarios:

Best case scenario:

∀ t ∈ H, Σ i SA i × P pv t,i + Eint t ≤ 0.35 × Dem t Worst case scenario: ∀ t ∈ H, Σ i SA i × P pv t,i + Eint t ≤ 0.35 × Dem t
Connecting parcel selection and size The third set of constraints establishes a link between the Boolean and PV plant area variables. This relationship is needed to connect the energy production and the various costs. If a plant size is not null then the parcel is selected, and conversely if a parcel is not selected its size is forced to be null.

∀i ∈ N, SA i ≤ Smax i × B i , B i × Smin ≤ SA i
Objectives and cost functions The OPSPV problem has two main objective functions: 1) to maximize the total hourly RE energy production over the year through new PV energy production, 2) to minimize the total technical costs.

Since the functions are in different units, a single weighted function is not meaningful, instead we seek the pareto frontier, by optimizing PV production function while constraining the cost function with more restrictive values at each run.

Maximize PV production: depending on the scenario considered, P pv t,i will take its highest estimate (P pv t,i for best case) or lowest estimate (P pv t,i for the worst case). The cost function to maximize is:

Σ i Σ t SA i × P pv t,i
Minimize costs: Modelling non-linear functions Four cost functions are involved and relate to the installation and size of a PV plant as defined in Fig. 3. Typically, capital and operational costs are approximated as linear functions [START_REF] Bogdanov | North-East Asian Super Grid for 100% renewable energy supply: Optimal mix of energy technologies for electricity, gas and heat supply options[END_REF][START_REF] Heydari | Optimization of a biomass-based photovoltaic power plant for an off-grid application subject to loss of power supply probability concept[END_REF][START_REF] Ferrer-Martí | A MILP model to design hybrid wind-photovoltaic isolated rural electrification projects in developing countries[END_REF]. However, this approach is unrealistic as both the Cap i and Cop i costs are in fact non-linear, since they depend on the size of the plant (linked to the related number of PV panels) [START_REF]Distributed generation renewable energy estimate of costs[END_REF]. Basically the fewer the number of panels the highest the relative cost per panel. To get closer to reality, we thus consider an innovative approach using a piece-wise linear function such that a i is the coefficient of the slope, and y i the value of the coordinate where the new slope begins. It is illustrated below for Cap i , and Cop i follows a similar specification with different constants. Values have been set from [START_REF]Distributed generation renewable energy estimate of costs[END_REF]:

Cap i =      a 1 × P nom × SA i + y 1 if 0 M W ≤ SA i × P nom ≤ 1 M W a 2 × P nom × SA i + y 2 if 1 M W ≤ SA i × P nom ≤ 10 M W a 3 × P nom × SA i + y 3 if 10 M W ≤ SA i × P nom
On the other hand, the unit connection cost of a PV plant, and the capital cost of a new station for a plant, are both linear functions that depend respectively on the creation of the plant in a parcel with its Euclidian distance to the grid, and the unit cost of a substation proportional to the computed size of the plant. We have the following functions:

Ccon i = Clan × Dg i × B i , Csta i = Csta × P nom × SA i

Experimental study and evaluation

The proposed GIS-RO framework seeks to make powerful use of multi-scale contextual information for spatial decision making and optimization. It is evaluated on the timely challenge in the region of French Guiana, where the objective is to reach the energy policy plan of 100% renewable by the year 2030, first by increasing PV, then biomass. The challenge lies in the strategic planning of solar PV scenarios using contextual real data characterized by spatio-temporal patterns and permeated with uncertainty (resource projections). In this section we present our results and analysis. Input data layers, retrieved from various national and world databases [START_REF]ONF Guyane: Occupation du sol en 2015 sur la bande littorale de la Guyane et son évolution entre 2005 et 2015[END_REF][START_REF]ONF Guyane: Programme régional de mise en valeur forestière pour la production de bois d'oeuvre -période 2015-2019[END_REF][START_REF] Juffe-Bignoli | World database on protected areas -User manual 1.4[END_REF][START_REF]IGN: BD TOPO R Version 2.2 -Descriptif de contenu[END_REF], and associated buffer values are depicted in Table 1. In addition, maximum distance to both power grid and road network has been set to 20 km, twice the value commonly used [START_REF] Ali | GIS based site suitability assessment for wind and solar farms in Songkhla, Thailand[END_REF][START_REF] Sabo | Spatial matching of large-scale grid-connected photovoltaic power generation with utility demand in Peninsular Malaysia[END_REF]. Land surface area minimum and maximum thresholds for establishing solar PV plants are respectively set to 1.5 ha [START_REF] Wang | A GIS-Based Approach in Support of Spatial Planning for Renewable Energy: A Case Study of Fukushima, Japan[END_REF] and 50 ha [START_REF]EDF: Systèmes énergétiques insulaires Guyane -bilan prévisionnel de l'équilibre offre / demande d'électricité[END_REF]. Finally, regarding plot resource, monthly solar GHI time series derived from satellite-based raster images [START_REF] Albarelo | Optimizing the heliosat-II method for surface solar irradiation estimation with GOES images[END_REF][START_REF] Fillol | Spatiotemporal indicators of solar energy potential in the Guiana Shield using GOES images[END_REF] have been disaggregated at the hour using an updated version of a synthetic generation model [START_REF] Aguiar | TAG: A time-dependent, autoregressive, Gaussian model for generating synthetic hourly radiation[END_REF][START_REF] Aguiar | Simple procedure for generating sequences of daily radiation values using a library of Markov transition matrices[END_REF][START_REF] Remund | Meteonorm Handbook part II: Theory, Global Meteorological Database Version 7 Software and Data for Engineers, Planers and Education[END_REF]. The GREECE module was implemented in Python using GIS-Python libraries recalled in the paper. It provides de-spatialized data items to the OPSPV module, which was implemented using IBM ILOG OPL CPLEX Optimization studio, on a 2 processors (Intel(R) Xeon(R) CPU E5-2609 v4 @1.70GHz) of 32 Go RAM. The GREECE module led to the extraction of 133 candidate parcels with their relevant features. The execution CPU time for the GREECE module is about 460 s. (reading files: 30 s; mask: 380 s.; partitioning: 3 s.; feature + monthly resource extraction: 50 s.), handled as a one off spatial placement preprocessing. The optimization CPU time varies from 23 s to 47 s depending on the bound set on the constrained objective function (runtime differences come from handling piece-wise linear functions that depend on the park sizes).

Data sets Restricted area layers handled in MASK correspond to a total of 21088 geographical objects. Here, the base layer B layer corresponds to Guiana's land use LU layer , which gathers 2643 polygons. Road network and power grid used in distance threshold computation are made of 2247 lines. Monthly solar resource is represented by a raster set of 12 × 3999 × 3999 cells. Global energy demand and existing production data are known from the sources and extractions from records of 2016 [18]. For the 2030 horizon we projected hourly energy demand values according to EDF estimations of worst case 5% annual growth and best case of 2% annual growth.

Results and analysis

We analyzed three aspects of relevance to the decision maker and network manager (power plant energy investors in Guiana and EDF) that are made possible with the combination of geographical and temporal contextual information and optimization: 1) the impact of the spatio-temporal energy patterns on the geographic selection process (Fig. 4 and 6 (b)), 2) the study of the risk adversity comparing best and worst case scenarios (Fig. 5), 3) the identification of robust planning investment scenarios where the optimal plants show to be identical regardless of the degree of spatio-temporal uncertainty on the power resource (Fig. 6 (a)).

Fig. 4 depicts the resulting spatial variation of the solar GHI patterns (derived by GREECE) on the produced power from the optimal solar PV plants (location and size) whose placement is visible in Fig. 6 (b). P1 and P4 sites (P2 and P3) have similar patterns for they are located in the same solar potential cluster zone. Essentially, it shows how our GIS-RO approach manages real site spatial arrangement so that the global output power is robust through time from the optimal PV plants: impact of their RE intermittency on future network power management is limited. Fig. 4: Normalized output power from solar PV sites of Fig. 6. Fig. 5 gives information about (a) the volume of solar PV plants one may install within the region without threatening the power grid in the long-term, and (b) its corresponding final share in the energy mix. As long as both Pareto lines remain together in Fig. 5 (a), the solution is robust, i.e. power generation over time from selected plants fills up the same free energy volume regardless of the scenario: corresponding PV sites can be explored safely in the limits of their maximum capacity estimated by the RO. In contrast, once the best case reaches its plateau , and so Pareto lines split in half (around 40 Me), power generation no longer fills up the same volume. At this point, the more the energy generated in the worst case scenario, the more it exceeds the energy generation limit in the best case: the risk grows as much as the gap between both lines.

Finally, Fig. 6 evaluates the robustness of the investment according to spatiotemporal uncertainty on the resource: i) estimated GHI, energy potential (in blue), ii) its mitigation by a random uniform noise per hour and per parcel, between 0 and 10 % (in green) and iii) between 0 and 20 % (in red) respectively. The safety zone lies below a cost of 70 Me (C70), meaning that the selected PV sites are the same for all resource time series projections. Those sites are sorted by ascending parcel size area from the smallest (P1) to the largest (P4). The investment costs grow naturally when the optimal PV plant size grows within its corresponding parcel area (fractional knapsack optimization).

Conclusion

In this paper we have proposed a two-step specification and novel computational approach of the spatio-temporal placement and energy planning problem. We addressed key challenges of sustainable science in terms of spatial decision making and usage of complex contextual data, constraints and time series of resources.

The presented GIS-RO framework allows for real world and large scale applications to be solved through an integrated approach at the interface of GIS science, graph and robust optimization models and methods. The case study showed in particular the importance of taking into account actual resource patterns and allowing for fractional parcel selection to optimize power plants location and size, and thus optimize the power penetration at minimal cost. Current work includes its generalization to include the cost-effectiveness of energy storage considered not profitable to this date in Guiana, and the generalization to biomass resources that raises a complex temporal renewability issue of the resource.

Fig. 2 :

 2 Fig. 2: Pruning restricted areas and threshold layers

  (per year) t ∈ H = {1, • • • , 8760} Unit: Candidate parcel i ∈ N = {1, • • • , n} Current hourly production from intermittent energy sources (KWh) Eintt Current hourly production from non-intermittent energy sources (KWh) Ept Estimated global hourly power demand (KWh) Demt = [Demt, Demt] Nominal power of a PV unit (to convert plant size into power) P nom Minimum and maximum area for each candidate parcel (m 2 ) Smin, Smaxi Estimated hourly production per PV unit (W h/m 2 ) P pvt,i = [P pvt,i, P pvt,i] Minimal distance from the grid to centroid of a candidate PV parcel (m) Dgi Transmission line unit cost (e/m) Clan Substation unit power cost (e/KW) Csta Find:

Fig. 5 :

 5 Fig. 5: Pareto charts for both scenarios with respect to (a) generated energy and (b) PV penetration.

Fig. 6 :

 6 Fig. 6: Robustness of the worst-case scenario solution with decreasing resource

  Slicing the base layer: extracting parcel polygons The slicing of the whole study area is divided into two main steps. The first consists in identifying and removing the restricted areas that intersect a base polygon (our study area) as well as zones beyond the distance threshold from given elements (electrical grid, road network, etc.). The procedure MASK(B layer , R layers , B uf f ers ) applies set-based topological operators, that mask out portions of restricted layers and buffered zones, intersecting the base layer (Alg.1:line 3). It corresponds to a 2-dimensional difference operation. The result of this first step is a finite set P of new polygons, representing available land for potential power facilities, illustrated in Fig2 (a).

	Topological geometric and raster images operators
	DISTANCE(p,P )	Minimum euclidean distance between centroid
			of polygon p and all elements in set P
	UNION(p1, .., pn)	geometric union of the polygons pi
	RTREEIDX(P )	Compute spatial index idx of all elements in P
	INTERSECTS(p,P,idx )	geometric intersection of p with elements in P
	SHAPE(p)		Shape factor of polygon p (e.g. roundness)
	SURFACE(p)	Surface of polygon p
	SLOPE(h)		Slope raster from the Digital Elevation Model h
	ASPECT(h)		Raster of slope orientation values from DEM h
	Set and graph functions
	HONEYCOMB(x,s 19 /* Mean energy resource values per raster time series	*/
	20	p.APPEND({µ1, µ2, • • • , µt} ∈ ZONALSTAT(Rmaps, p, µ))
	3.1 Spatial placement and partitioning of polygons

hex ) Creates a honeycomb grid corresponding to polygon x of x with hexagonal elements having surface s hex PARTGRAPH(G, n, Wpart) Partitions a graph G into n parts having weights Wpart Algorithm 1: GREECE main algorithm 1 begin 2 /* Compute candidate parcels specified spatially as polygons */ 3 P ← MASK(B layer , R layers , B uf f ers ) 4 for p ∈ P : 5 if SURFACE(p) >= smax: 6 P .DELETE(p) 7 P .INSERT(PARTITION(p, smax, f d ))/* see algorithm 2 */ 8 for p ∈ P : 9 if SURFACE(p) < smin ∨ DISTANCE(p, i ∈ D layer ) > dti, dti ∈ DistT : 10 P .DELETE(p) 11 /* Compute, store de-spatialized features for each polygon p (Section 3.2) */ 12 for p ∈ P : 13 p.APPEND(DISTANCE(p, N ∈ N ET layers )) 14 p.APPEND(SHAPE(p)), p.APPEND(SURFACE(p)) 15 p.APPEND(s k ∈ SURFACE(p ∩ INTERSECTS(p, LU layer , RTREEIDX(LU layer )))) 16 /* Aggregate raster cell values, terrain features, within p */ 17 p.APPEND(µn ∈ ZONALSTAT({h, SLOPE(h), ASPECT(h)}, p, µ)) 18 p.APPEND(σn ∈ ZONALSTAT({h, SLOPE(h), ASPECT(h)}, p, σ))

  HONEYCOMB(p, area:smax/f d ) /* create the mesh of hexagons */ Input : set of hexagons H, set of corresponding weights W hexa Output : a graph G

	1 def PARTITION(p, smax, f d ): /* Partition polygon p into a set of
		polygons P of equal surface	*/
		Input : polygon p, maximal area per partition smax, disaggregation
		factor f d
		Output : a set P of polygons
	2	/* Initialization	*/
	3	k ← SURFACE(p) smax	/* Number of targeted plots	*/
	21	/* Initialization	*/

4 if k <= 1 and SURFACE(p) -spart < spart/f d : 5 return {p} 6 H ← 7 G ← TOGRAPH(H, SURFACE(hexa ∈ H)) 8 for i ∈ {1, .., k}: 9 /* Set the weight for each sought plot */ 10 W plot .APPEND(smax) 11 if SURFACE(p) mod smax not = 0: 12 W plot .APPEND(SURFACE(p) -n • smax) 13 k ← k + 1 14 /* k-way graph partitioning of G into a set of k clusters C */ 15 C ← PARTGRAPH(G, k, W plot ) 16 /* Convert the clusters of vertices into a set polygons */ 17 for set ∈ C: 18 P .INSERT(UNION(pi | i ∈ set)) 19 return P 20 def TOGRAPH(H, W hexa ): /* Convert the weighted mesh into a graph */ 22 G ← GRAPH() 23 for (h, w) ∈ (H, W hexa ): 24 /* set of polygons concomitant to h, frontiers */ 25 F ← INTERSECTS(h, H, RTREEIDX(H)) 26 for f ∈ F : 27 G.INSERT(EDGE(h, f )) 28 G.INSERT(NODE(p, weight:w)) 29 return G

Table 1 :

 1 Land management scenario used in this study for restricted areas.

	Layer Protected Forest Urban Flood Water Shore	Power	Road Wetland Dune/	Rice/
		areas		areas savanna bodies	grid network		Sand Orchard
	Buffer	500	200	200	100	100 100	100	30	0	0	0
	(m)
	Refs	[45]	[6] [45,3]	[41] [40,41] [40] [39,3,41] [39,3,41]	[41]