tag:www.gerad.ca,2005:/en/papersCahiers du GERAD2020-05-21T13:56:03-04:0020tag:www.gerad.ca,2005:Paper/27792020-05-21T13:56:03-04:002020-05-21T13:56:03-04:00G-2019-100 : Prosumers and energy pricing policies: When, where and under which conditions will prosumers emerge? A case study for Ontario, CanadaElizaveta Kuznetsova, Miguel F. Anjos
<p>The energy landscape is marked by a rapid emergence of electricity prosumers at all levels of the grid. While energy policy seems to be more adaptive to the needs of large-scale prosumers, it may be less concerned to accommodate the needs of small-scale prosumers. While their behaviour may be disruptive for the entire grid when their number reaches a certain threshold, scepticism about the feasibility and profitability of the disconnection mode remains. This paper contributes to the exploration of these issues by analysing the impact of billing policy on the profitability of investment in prosumer schemes, such as Net Metering and Off-grid, for the case of Ontario (Canada). We conclude that fast improvement of commercial storage technologies makes it possible for prosumer to become fully electricity self-sufficient even in locations with low availability of renewable energy sources. While the profitability analysis shows that Off-grid is not profitable in 2019 and will likely remain not profitable in 10 years, it reveals some important findings. The profitability of investment in Net Metering scheme is comparable with the profitability with Off-grid scheme in 2019. For Ontario, this means that a prosumer would need to triple his investment to switch from Net Metering to the grid-disconnected mode, but the profitability of this decision will be divided by two. Critical locations where consumers are more prompt for disconnection are characterised by a high share of fixed costs in the total electricity bill. The pattern of disconnection profitability increase matches with the pattern of fixed costs share increase showing that billing policy has a direct impact on consumers decisions. The profitability of disconnection increases faster with the increase of fixed charges. By comparing the three locations of Atikokan, Hawkesbury and Espanola, it was found that a five-fold increase in variable cost (with same fixed cost) increases the Off-grid profitability by 10% while a three-fold increase in fixed cost (with same variable cost) will increase the Off-grid profitability by 26%. If the shares of variable and fixed costs are maintained the same in the future, the profitability of Off-grid mode may almost double between 2019 and 2030. Moreover, if the cost trends of recent years are maintained, i.e., decrease of variable costs and increase of fixed costs, then the profitability of Off-grid mode will push electricity consumers toward disconnection.</p>2019-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27782020-05-21T11:34:41-04:002020-05-21T14:32:18-04:00G-2020-26 : Long-term influence of priority order of short-term unit commitment in a complex hydroelectric systemEmmanuel Bigeon, Martin Gagnon, Stéphane Alarie, Souheil-Antoine Tahan, Michel Gamache
<p>In the area of hydraulic power generation, there is a great deal of
interest in two interdependent domains: operation and maintenance. This
interdependence is usually simplified, or even ignored, to tackle the
issue raised by the difference in planning horizons scales in each of
these domains, causing conservative planning for the maintenance and
missed opportunities in operation. This paper presents a new model for
the simulation of the operation of a complex system that is a hydraulic
power-generating grid, over an arbitrary long horizon, with a small
step, in a reasonable time through a sequential resolution of the hourly
operational plan of the system. The model is used to assess the
influence of operation decisions (in this case, the start-up order of
generating units) on the reliability of components through uptime,
start-ups number and mode of operation over a medium horizon. A
preliminary case study is presented using a standard operation strategy
and its counterpart to validate the approach.</p>2020-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27772020-05-21T11:28:36-04:002020-05-21T11:28:36-04:00G-2020-29 : Machine-learning-based column selection for column generationMouad Morabit, Guy Desaulniers, Andrea Lodi
<p>Column generation (CG) is widely used for solving large-scale optimization problems. This article presents a new approach based on a machine learning (ML) technique to accelerate CG. This approach, called <em>column selection</em>, applies a learned model to select a subset of the variables (columns) generated at each iteration of CG. The goal is to reduce the computing time spent reoptimizing the restricted master problem at each iteration by selecting the most promising columns. The effectiveness of the approach is demonstrated on two problems: the vehicle and crew scheduling problem, and the vehicle routing problem with time windows. The ML model was able to generalize to instances of different sizes, yielding a gain in computing time of up to 30%.</p>2020-05-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27762020-05-21T11:24:28-04:002020-05-21T11:24:44-04:00G-2020-28 : The Covering-Assignment Problem for swarm-powered ad-hoc clouds: A distributed 3D mapping use-case Leandro R. Costa, Daniel Aloise, Luca G. Gianoli, Andrea Lodi
<p>The popularity of drones is rapidly increasing across the different sectors of the economy. Aerial capabilities and relatively low costs make drones the perfect solution to improve the efficiency of those operations that are typically carried out by humans (e.g., building inspection, photo collection). The potential of drone applications can be pushed even further when they are operated in fleets and in a fully autonomous manner, acting de facto as a drone swarm. Besides automating field operations, a drone swarm can serve as an ad-hoc cloud infrastructure built on top of computing and storage resources available across the swarm members and other connected elements. Even in the absence of Internet connectivity, this cloud can serve the workloads generated by the swarm members themselves, as well as by the field agents operating within the area of interest. By considering the practical example of a swarm-powered 3D reconstruction application, we present a new optimization problem for the efficient generation and execution, on top of swarm-powered ad-hoc cloud infrastructure, of multi-node computing workloads subject to data geolocation and clustering constraints. The objective is the minimization of the overall computing times, including both networking delays caused by the inter-drone data transmission and computation delays. We prove that the problem is NP-hard and present two combinatorial formulations to model it.
Computational results on the solution of the formulations show that one of them can be used to solve, within the configured time-limit, more than 50% of the considered real-world instances involving up to two hundred images and six drones.</p>2020-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27742020-05-07T13:13:04-04:002020-05-07T13:13:04-04:00G-2020-16 : The pickup and delivery problem with time windows, multiple stacks, and handling operationsMarilène Cherkesly, Timo Gschwind
<p>In this paper, we introduce, model and solve the pickup and delivery problem with time windows, multiple stacks, and handling operations (PDPTWMS-H).
%
In the PDPTWMS-H, a fleet of vehicles based at a depot is used to complete a set of requests which consist of transporting items from a pickup location to a delivery location.
The vehicles have multiple compartments operated using last-in-first-out (LIFO) loading which requires the vehicle to be rear-loaded and items can only be unloaded if they are closest to the back door.
In the PDPTWMS-H, additional handling operations, referred to as rehandling, are allowed and an additional handling time might be incurred when rehandling items (by unloading and reloading items).
The problem consists of determining the number of vehicles and the vehicle routes needed to complete the set of requests at minimal cost while respecting the possible handling operations.
We model the PDPTWMS-H with a set-partitioning formulation and resort to branch-price-and-cut (BPC) for its solution.
To solve the pricing problem, we derive a labeling algorithm that is able to cope with the different rehandling possibilities.
The labeling algorithm keeps track about the information of on-board items such that symmetries with respect to both stacks and item positions are reduced.
Extensive tests are performed on benchmark instances to assess the performance of the proposed BPC methodology and to provide insights on the impact of the rehandling flexibility on solution cost and time.</p>2020-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27732020-05-07T13:05:26-04:002020-05-07T13:05:26-04:00G-2020-25 : DMulti-MADS: Mesh adaptive direct multisearch for blackbox multiobjective optimizationJean Bigeon, Sébastien Le Digabel, Ludovic Salomon
<p>The context of this research is multiobjective optimization where conflicting objectives are present. In this work, these objectives are only available as the outputs of a blackbox for which no derivative information is available. This work proposes a new extension of the mesh adaptive direct search (MADS) algorithm to constrained multiobjective derivative-free optimization. This method does not aggregate objectives and keeps a list of non dominated points which converges to a (local) Pareto set as long as the algorithm unfolds. As in the single-objective optimization MADS algorithm, this method is built around a search step and a poll step. Under classical direct search assumptions, it is proved that the so-called DMulti-MADS algorithm generates multiple subsequences of iterates which converge to a set of local Pareto stationary points. Finally, computational experiments suggest that this approach is competitive compared to the state-of-the-art algorithms for multiobjective blackbox optimization.</p>2020-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27722020-05-07T13:02:00-04:002020-05-07T13:07:00-04:00G-2020-27 : A Simulation model for short and long term humanitarian supply chain operations managementMarilène Cherkesly, Yasmina Maïzi
<p>Traditionally, the design of supply chains for humanitarian operations has been developed distinctly for the different disaster management phases, with little attention to relief to development continuum. For the immediate response phase, this design has an emphasis on speed, whereas for the reconstruction phase, it has an emphasis on cost-reduction. In this paper, we develop a sustainable humanitarian supply chain network for the relief to development continuum. Hence, this network ensures an effective and smooth transition from response to reconstruction operations. We develop three network structures which integrate the lean and agile principles at a different extent. To determine the best characteristics of such a sustainable supply chain, we use discrete event simulation (DES) modeling. We validate and compare each network structure through several scenarios fed by data sets available from the United Nations World Food Program (WFP) for operations conducted in the Republic of Congo (RoC).</p>2020-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27712020-04-22T11:10:40-04:002020-05-04T10:02:50-04:00G-2020-24 : On the interplay between self-driving cars and public transportation: A game-theoretic perspectiveNicolas Lanzetti, Maximilian Schiffer, Michael Ostrovsky, Marco Pavone
<p>Cities worldwide struggle with overloaded transportation systems and their externalities, such as traffic congestion and emissions. The emerging technology of autonomous transportation systems bears a high potential to alleviate these issues. At the same time, this technology might also introduce negative effects, in particular by disproportionately cannibalizing public transportation. A careful analysis of this trade-off requires modeling both modes of transportation within a unified framework. In this paper, we propose such a framework, which allows us to study the interplay among mobility service providers, public transport authorities, and customers, and in particular to analyze the effect of autonomous ride-hailing services on the demand for public transportation. This framework combines a graph-theoretic network model for the transportation system with a game-theoretic model whereby mobility service providers are profit-maximizers and customers select individually-optimal transportation options. We apply our modeling approach to data for the city of Berlin, Germany and present sensitivity analyses to study factors that mobility service providers or municipalities can act upon to strategically steer the overall system. We show that depending on market conditions and policy restrictions, autonomous ride-hailing systems may complement or cannibalize a public transportation system, and discuss the main factors behind such different outcomes as well as strategic design options available to policymakers.</p>2020-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27702020-04-22T11:06:17-04:002020-04-22T11:06:17-04:00G-2020-22 : On the impact of the power production function approximation on hydropower maintenance schedulingEloise Edom, Miguel F. Anjos, Claudia D'Ambrosio, Wim van Ackooij, Pascal Côté, Sara Séguin
<p>Maintenance planning for hydropower plants is a crucial problem. In this paper, we evaluate the impact of the Hydropower Production Function (HPF) formulation on the maintenance scheduling. Based on an existing model for Generator Maintenance Scheduling that uses a convex hull approximation for representing the HPF, we developed two additional approximations, one that is piecewise linear approximation and another that uses a polynomial function. Then, we compare these three approximations: first a convex hull approximation, then a piecewise linear approximation and third, a nonlinear approach using a polynomial function fitted on real data. We experiment with two test cases based on real-world hydroelectric systems. The results show that for a one-month planning horizon, depending on the approximation used, maintenance tasks can be shifted by up to 5 days, and the difference in energy production can reach 8,300 MWh.</p>2020-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27692020-04-17T12:12:58-04:002020-04-17T12:12:58-04:00G-2020-21 : Dynamic constraint aggregation for solving very large-scale airline crew pairing problemsGuy Desaulniers, François Lessard, Mohammed Saddoune, François Soumis
<p>The monthly crew pairing problem (CPP) consists of determining a least-cost set of feasible crew pairings (sequences of flights starting and ending at a crew base) such that each flight is covered once and side constraints are satisfied. This problem has been widely studied but most works have tackled daily or weekly CPP instances with up to 3500 flights. Only a few papers have addressed monthly instances with up to 14000 flights. In this paper, we propose an effective algorithm for solving very large-scale CPP instances. This algorithm combines, among others, column generation~(CG) with dynamic contraint aggregation (DCA) that can efficiently exploit the CG master problem degeneracy. When embedded in a rolling-horizon (RH) procedure, DCA allows to consider wider time windows in RH and yields better solutions. Our computational results show, first, the potential gains that can be obtained by using wider time windows and, second, the very good performance of the proposed algorithm when compared to a standard CG/RH algorithm for solving an industrial monthly CPP instance with 46588 flights.</p>2020-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27682020-04-17T12:07:55-04:002020-04-17T12:07:55-04:00G-2019-93 : A new matheuristic approach for optimizing mineral value chains under uncertainty Amina Lamghari, Roussos Dimitrakopoulos
<p>Mineral value chains or mining complexes involve mining, processing,
stockpiling, waste management, and transportation activities. An
integrated stochastic optimization of all related aspects and activities
has ben shown to increase the net present value of related mining
projects and operations, reduce risk in meeting production targets, and
lead to more robust and coordinated production schedules. However, it
entails solving a substantially large and more complex stochastic
optimization problem than separately optimizing individual components of
a mineral value chain. To tackle this complex optimization problem, a
new matheuristic that integrates components from exact algorithms
(relaxation and decomposition), machine learning techniques
(reinforcement learning and artificial neural networks), and heuristics
(local improvement and randomized search) is proposed. A general
mathematical formulation that serves as the basis for the proposed
methodology is also introduced.</p>2019-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27672020-04-07T11:14:54-04:002020-04-07T11:15:57-04:00G-2019-102 : Implications of EMF 34 scenarios on renewable deployment and carbon abatement in Canada: Insights from a regionalized energy modelOlivier Bahn, Kathleen Vaillancourt
<p>This paper proposes a detailed analysis of the evolution of Canadian energy systems under some selected EMF (Energy Modeling Forum) 34 scenarios. Our analysis is based on NATEM, an energy model that follows the TIMES approach of the International Energy Agency to represent in detail the energy sector of each of the 13 Canadian provinces and territories. NATEM shows that imposing different renewable penetration constraints for electricity generation has limited impacts outside the electricity sector. In particular, greenhouse gas (GHG) emissions continue to increase over time. Conversely, the imposition of a carbon tax has broader impacts on Canadian energy systems and on GHG emissions that are almost stabilized. However, the level of the carbon tax envisions by the EMF 34 study (increasing to a maximum level of $130 per tonne by 2050) is not high enough, in a Canadian context, to trigger a decrease of GHG emissions over time as mandated by Canadian climate policies.</p>2019-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27662020-04-07T11:11:19-04:002020-04-07T11:11:19-04:00G-2019-98 : Improving classification performance on sparse data: Augmenting a convolutional neural net with generalized angular orientations of edgesAmir Abbas Haji Abolhassani, Roussos Dimitrakopoulos, Frank P. Ferrie, Prasun Lala
<p>With sufficient layers, enough training data, enough time, and often a
custom tailored architecture, modern deep learning methods can be
extremely successful in classification tasks. However, with real-world
practical applications, a lack of training data can impede the success
of such techniques, which often over-fit the sparse data. A particular
task hindered by sparse data, may take advantage of an existing
pre-trained network of a separate but related task trained on sufficient
data, to achieve high accuracy with minimal additional training.
However, such transfer-learning does not generalize well to new tasks
that have little relation between their data and the pre-trained
network's data. To overcome this hurdle, we introduce a novel feature
(AngOri) kernel that leverages the generalized inherent richness of
curvature and gradient in image edges, and that can augment any type of
convolutional neural network with any arbitrary number of channels to
quickly achieve accurate classification with minimal training on sparse
data. The AngOri kernels can be pre-computed and thus directly
implemented in a convolutional layer of a network, which is not possible
with other gradient based features. Testing on the MNIST, CIFAR-10, and
a satellite image database, we consistently found AngOri to aid a
network to achieve more accurate classification on a small dataset when
compared to the same network without the AngOri layers. Such a
generalizable, lightweight kernel holds promise for using neural
networks to tackle real-world problems with limited resources, such as
embedded systems examining sparse data.</p>2019-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27652020-04-07T11:07:54-04:002020-04-17T12:09:12-04:00G-2019-97 : Stochastic short-term production scheduling and shovel allocation for mining complexes including stockpiling and operational alternativesChristian Both, Roussos Dimitrakopoulos
<p>A new mathematical model for stochastic short-term optimization of mining complexes is presented that simultaneously optimizes the short-term extraction sequence, shovel allocation including costs of their relocation, stockpiling, and operational alternatives in processing streams. The optimization formulation accounts for metal and material type uncertainty, stemming from the geological reserve, as well as uncertain shovel production, reflecting the natural risk of underperformance of mining equipment. The method has been applied to a real-world gold mining complex. The resulting production schedule requires a minimum amount of shovel movements and shows an increased metal production of +1.23%, leading to a higher expected profit of +0.77%.</p>2019-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27642020-03-26T10:50:32-04:002020-03-26T10:50:32-04:00G-2020-20 : The value of randomized strategies in distributionally robust risk averse network interdiction gamesUtsav Sadana, Erick Delage
<p>Conditional Value at Risk (CVaR) is widely used to account for the preferences of a risk-averse agent in the extreme loss scenarios. To study the effectiveness of randomization in interdiction games with an interdictor that is both risk and ambiguity averse, we introduce a <em>distributionally robust network interdiction game</em> where the interdictor randomizes over the feasible interdiction plans in order to minimize the worst-case CVaR of the flow with respect to both the unknown distribution of the capacity of the arcs and his mixed strategy over interdicted arcs. The flow player, on the contrary, maximizes the total flow in the network. By using the budgeted uncertainty set, we control the degree of conservatism in the model and reformulate the interdictor's non-linear problem as a bi-convex optimization problem. For solving this problem to any given optimality level, we devise a spatial branch and bound algorithm that uses the McCormick inequalities and reduced reformulation linearization technique (RRLT) to obtain convex relaxation of the problem. We also develop a column generation algorithm to identify the optimal support of the convex relaxation which is then used in the coordinate descent algorithm to determine the upper bounds. The efficiency and convergence of the spatial branch and bound algorithm is established in the numerical experiments. Further, our numerical experiments show that randomized strategies can have significantly better in-sample and out-of-sample performance than optimal deterministic ones.</p>2020-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27632020-03-26T10:45:49-04:002020-03-26T10:45:49-04:00G-2020-15 : Smart distributed energy storage controller (smartDESC)Filippo Malandra, Arman C. Kizilkale, Frédéric Sirois, Brunilde Sansò, Miguel F. Anjos, Michel Bernier, Michel Gendreau, Roland P. Malhamé
<p>While one can exploit the storage properties and thus the deferability or anticipation potential of many classes of power system loads (such as thermal loads) as an increasingly needed tool to mitigate renewable sources variability, the challenge to do so in an optimal and coherent manner is immense. This is in view of the sheer number and dynamic diversity of the loads that can be involved in any large-scale application of such an approach. The smartDESC concept is a control architecture that was developed for this purpose. It builds on the more pervasive communication means currently available (such as Advanced Metering Infrastructures), as well as the mathematical tools of (i) aggregate load modeling, (ii) renewable energy forecasting, (iii) optimization theory, deterministic or stochastic, and (iv) the recent developments in control of large-scale systems based on game theory and called mean-field (MF) control theory, which allow producing a scalable yet optimal approach to the decentralized control of large pools of loads. This paper presents the building blocks of the smartDESC architecture, together with an associated simulator and simulation results.</p>2020-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27622020-03-26T10:36:48-04:002020-03-26T10:36:48-04:00G-2020-11 : Computational study of a branching algorithm for the maximum \(k\)-cut problemVilmar Jefté Rodrigues De Sousa, Miguel F. Anjos, Sébastien Le Digabel
<p>This work considers the graph partitioning problem known as maximum <em>k</em>-cut. It focuses on investigating features of a branch-and-bound method to efficiently obtain global solutions. An exhaustive experimental study is carried out for two main components of a branch-and-bound algorithm: computing bounds and branching strategies. In particular, we propose the use of a variable neighborhood search heuristic to compute good feasible solutions, the <em>k</em>-chotomic strategy to split the problem, and a branching rule based on edge weight to select variables. Moreover, this work analyses the linear relaxation strengthened by semidefinite-based constraints, the cutting plane algorithm, and some node selection strategies. Computational results show that the method using the best procedures of the branch-and-bound outperforms the state-of-the-art and uncover the solution of several instances, especially for problems with <code>\(k \geq 5\)</code>.</p>2020-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27612020-03-19T11:45:54-04:002020-03-20T13:25:26-04:00G-2020-19 : Open-loop and feedback Nash equilibrium in scalar linear-state differential games with impulse controlUtsav Sadana, Puduru Viswanadha Reddy, Georges Zaccour
<p>We consider a two-player linear-state differential game, where one player
intervenes continuously in the game, while the other implements an impulse
control. When the number of impulses is exogenous, we obtain the classical
result in linear-state differential games that open-loop and feedback Nash
equilibria coincide. When the impulse instants are endogenous, this result
no longer holds.</p>2020-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27602020-03-19T11:42:25-04:002020-03-19T11:42:25-04:00G-2020-10 : Elements of networked protection systems for distribution networks and microgrids: A cyber-security perspective Younes Seyedi, Houshang Karimi, Santiago Grijalva, Brunilde Sansò
<p>Networked protection systems use information, communication and computation technologies to collect and process sensor data from spatially distributed sensors, and launch protective and control actions by sending commands to local devices. Such protection systems are also capable of supporting specialized tasks including asset control and backup protection in case of traditional relaying failures. This paper explains the structure and the fundamental elements of the networked protection systems in distribution systems and microgrids. The overall system is divided into three subsystems which are interconnected by communication systems. Different types of cyber-attacks on the subsystems and their impacts are discussed from the vantage point of protection. False and delayed tripping, non-detection, cascading failures, and unstable operation of distributed energy resources (DERs) are discussed as the critical issues that can be related to cyber-attacks.</p>2020-01-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/27592020-03-19T11:39:24-04:002020-03-19T11:39:24-04:00G-2020-09 : A new approach to reliability assessment of synchrophasor communications in smart grids Younes Seyedi, Houshang Karimi, Constant Wetté, Brunilde Sansò
<p>Wireless communications can facilitate transfer of synchrophasor data between spatially separated phasor measurement units (PMUs) and phasor data concentrators (PDCs). However, such communication systems may impose random access delay and failure on PMU channels that lead to missing synchrophasor data frames at the output of the PDC. This paper presents a new approach for online reliability assessment and improvement of synchrophasor data communications. The proposed approach involves elaborate estimation and probabilistic prediction algorithms that trigger a prioritized handover mechanism in order to minimize the number of synchrophasor data frames that are missing over successive time-stamps. Extensive simulations based on LTE wireless communications confirm significant improvement in terms of data loss under both absolute and relative waiting time logics. This non-intrusive approach can be adopted by network operators to ensure reliable transmission of synchrophasor data to monitoring, control, and protection applications in smart grids.</p>2020-01-01GERADinfo@gerad.ca