Search

In this paper, we consider the problem of completely flying over an area just hit by an earthquake with a fleet of Unmanned Aerial Vehicles (UAVs) to opportunely direct rescue teams. The cooperation between UAVs ensures that the search for possible survivors can be faster and more effective than the solutions currently implemented by civil protection. To study this scenario, we introduce the Cover by Multitrips with Priorities (CMP) problem, which tries to keep into account all the main real-life issues connected to the flight and coordination of the UAVs. We conduct a theoretical study to estimate the best number of UAVs and additional batteries, to give indications to the organization that leads the rescue teams to be able to guarantee rapid and effective rescue. Finally, based on some theoretical considerations, we propose some heuristics that tackle the problem of flying over the whole area with a fleet of UAVs in the shortest possible time. Simulations show that they work efficiently in both the proposed scenarios and provide better performance than previous solutions once they are arranged to work in our scenarios. The main advantages of our approach w.r.t. the current drone-based solutions used by the civil defense are that UAVs do not need drivers so the time of all available rescue workers can be invested in doing something else. In our model, we take into account that some sites (e.g. buildings with a high fire risk or schools and hospitals) have a higher priority and must be inspected first, and the possibility that UAVs can make a decision based on what they detect. Finally, our approach allows UAVs to collaborate so that the same sites will be flown over exactly once in order to speed up the rescue mission.

To control the flow in a dynamical network where the nodes are associated with buffer variables and the arcs with controlled flows, we consider a network-decentralised strategy such that each arc controller makes its decision exclusively based on local information about the levels of the buffers that it connects. We seek a flow control law that asymptotically minimises a cost specified in terms of a weighted L 1 -norm. This approach has the advantage of providing a solution that is generally sparse, because it uses a limited number of controlled flows. In particular, in the presence of a resource demand applied on a single node, the asymptotic flow is concentrated along the shortest path.

In order to foster increasing shares of renewable generation at distribution level, it is necessary to introduce control strategies to avoid voltage and loading congestions. Control strategies are also needed to facilitate the provision of ancillary services to the transmission grid by distributed resources. Centralized control solutions are often the best choice for an optimal management of distribution networks, but they usually require monitoring vast network areas and many grid nodes, which is frequently unaffordable. For this reason, some portions of the network (i.e. LV nodes) can be operated in an unsupervised way, and the fundamental control functions are operated by generators local controllers. Of course, these controllers also impact on the supervised network portions, therefore centralized architectures should take their (side) effects into account in order to compensate them. This paper analyses the behavior of a real distribution grid with a hybrid control strategy (i.e. where automatic local controllers are implemented in some portions, while some generators and distribution transformers are controlled by the network operator) and compares it to situations in which either central control only or local controllers only are activated.

The Italian day-ahead electricity market is a zonal market with a national uniform purchase price, called PUN (in Italian “Prezzo Unico Nazionale”). The clearing of such a market is based on linear programming techniques, where primal variables represent quantities of traded energy and dual variables represent prices. Since the PUN cannot be expressed as a linear combination of primal or dual variables only, up to now the above clearing problem could be solved exclusively using heuristic techniques and/or approximations. The authors of this paper have developed an exact mixed integer linear programming model, capable to clear the Italian day-ahead electricity market. In this paper, this new model is compared with the existing, non-exact, market solvers in terms of numerical results and computational costs. In particular, numerical results are perfectly adherent with the ones published by the Italian Market Operator, while the computational costs are of the order of few seconds on a PC.

We study diffusion of cooperation in a two-population game in continuous time. At each instant, the game involves two random individuals, one from each population. The game has the structure of a Prisoner's dilemma where each player can choose either to cooperate (c) or to defect (d), and is reframed within the field of approachability in two-player repeated game with vector payoffs. We turn the game into a dynamical system, which is positive, and propose a saturated strategy that ensures local asymptotic stability of the equilibrium (c, c) for any possible choice of the payoff matrix. We show that there exists a rectangle, in the space of payoffs, which is positively invariant for the system. We also prove that there exists a region in the space of payoffs for which the equilibrium solution (d, d) is an attractor, while all of the trajectories originating outside that region, but still in the positive quadrant, are ultimately bounded in the rectangle and, under suitable assumptions, converge to the solution (c, c).

This work explores two different techniques for the prediction of the Italian day-ahead electricity market prices, the zonal prices and the uniform purchase price (Prezzo Unico Nazionale or PUN). The study is conducted over a 2-year long period, with hourly data of the prices to be predicted and a large set of variables used as predictors (i.e. historical prices, forecast load, wind and solar power forecasts, expected plenty or shortage of hydroelectric production, net transfer capacity available at the interconnections and the gas prices). A Neural Network (NN) and a Support Vector Regression (SVR) are applied on the different predictors to obtain the final forecasts. Different predictors' combinations are analyzed in order to find the best forecast. We compare the NN and SVR to two less sophisticated post-processing methods, i.e. a linear regression (LR) and the persistency (P).

Given a physical substrate network and a collection of requests of virtual networks, the Virtual Network Embedding problem (VNE) calls for the embedding onto the physical substrate of a selection of virtual networks in such a way that the profit is maximized. The embedding corresponds to a virtual-to-physical mapping of nodes and links, subject to capacity constraints. Since, in practical scenarios, node and link demands are typically much smaller than the peak values specified in the virtual network requests, in this work we propose and investigate a robust optimization approach. This allows us to find solutions with a much larger profit which, at the same time, are guaranteed to be feasible with a high probability. To this end, we propose a robust Mixed-Integer Linear Programming (MILP) formulation for VNE, based on the well-known model of Γ-robustness. To solve larger scale instances, for which the exact approach is computationally too demanding, we also propose a MILP-based two-phase heuristic which relies on Γ-robustness.

In this paper we use a metaheuristic approach to solve the Portfolio Selection problem, in a constrained formulation which is NP-hard and difficult to be solved by standard optimization methods. We are comparing the algorithm's performances with an exact solver and we are showing that different mathematical formulations lead to different algorithm's behaviour. Results show that our approach can be efficiently used to solve the problem at hand, and that a sound basin of attraction analysis may help developers and practitioners to design the experimental analysis.

A distributed routing control algorithm for dynamic networks has recently been presented in the literature. The networks were modeled using time evolution of density at network edges and the routing control algorithm allowed edge density to converge to a Wardrop equilibrium, which was characterized by an equal traffic density on all used paths. We borrow the idea and rearrange the density model to recast the problem within the framework of mean-field games. The contribution of this paper is three-fold. First, we provide a mean-field game formulation of the problem at hand. Second, we illustrate an extended state space solution approach. Third, we study the stochastic case where the density evolution is driven by a Brownian motion.

This paper studies opinion dynamics and stubbornness using mean-field game theory. Assuming an initial exponential density function and affine control policies we analyze under what conditions the Fokker-Planck equation returns an exponential density function over the horizon. Consensus and clusters formation are also studied.

In this paper the authors study the problem of the assignment of road paths to vehicles. If the authors assume available the real-time road network information, then (self-concerned) vehicles select paths in a way related to user optimization which results in Wardrop equilibrium. The latter, even though fair for the vehicles of the same Origin-Destination (O-D) pair, in general can be arbitrarily more costly than the system optimum. System optimization, on the other hand, can produce unfair assignments both for the vehicles of the same as of different O-D pairs. To surmount the performance issue of the user in respect to the system-optimization while considering the fairness issues, the authors propose a MAS-based distributed optimization model for path assignment to vehicles from the same and different OD pairs at two levels. On the upper level, the proposed model optimizes the overall O-D pairs' Nash Welfare with the fairness related constraints while on the lower level, for every O-D pair separately, paths are assigned to individual vehicles through the auction algorithm. The authors test the solution approach through simulation, compare it with the conventional user- and system-optimization, and thus demonstrate that it results in fair and globally efficient path-vehicle assignments.

In this work we deal with a resource constrained project scheduling problem. The considered activities represent tasks in a manufacturing assembly process, in which multiple copies of a certain product have to be created. For each copy of the product, the operations must be processed on dedicated machines and must satisfy a given set of precedence constraints. The objective is to minimise the overall make span. When the number of copies becomes large, we are interested in designing periodic (or cyclic) schedules, where we want to maximize throughput, i.e., number of copies produced in a time unit, while keeping product flow time low. We present a heuristic algorithm based on a branch and bound scheme for the case of a pipeline assembly process.

This paper provides a mean-field game theoretic model of the bandwagon effect in social networks. The latter phenomenon can be observed whenever individuals tend to align their own opinions to a mainstream opinion. The contribution is three-fold. First, we provide a mean-field games framework that describes the opinion propagation under local interaction. Second, we establish mean-field equilibrium strategies in the case where the mainstream opinion is stationary. Such strategies are shown to have a threshold structure. Third, we study conditions under which a given opinion distribution is stationary if agents implement optimal non-idle and threshold strategies.

In recent years, there has been a remarkable growth of the Internet energy consumption, which is expected to persist in the future at an even higher pace. At the same time the network access capacity of individual subscribers is rapidly reaching values high enough to move the traffic bottleneck from the access network to the core network in most scenarios. This will soon make the elastic nature of traffic an important aspect of network resource management and will require a redesign of the energy-aware traffic engineering techniques so far based on inelastic traffic demands. We propose a novel optimization approach to select a routing path for each elastic traffic demand and decide which routers and links to put to sleep so as to maximize a network utility measure depending on the traffic demand rates, while satisfying a constraint on the total energy consumption. Bandwidth is allocated to each elastic demand according to the Max-Min Fairness (MMF) paradigm, which approximates the resource allocation of the transport layer.

We propose a two-stage stochastic optimization model for maximizing the profit of a price-taker power producer who has to decide his own power generation capacity expansion plan in a long time horizon, taking into account the uncertainty of the following parameters: fuel costs; market electricity prices, as well as prices of green certificates and CO2 emission allowances; market share. The parameter uncertainty is represented by scenarios on their values along the planning horizon and the associated probability of occurrence. We first discuss the risk neutral stochastic model, that maximizes over all scenarios the net present value of the expected profit along the planning horizon. The risk neutral model does not take into account the variability of the objective function value over the scenarios and, then, the possibility of realizing in some scenarios a very low profit. Several approches have been introduced in the literature for measuring the profit risk. In this work we consider the Conditional Value at Risk, that requires a confidence level to be defined, and the First-order Stochastic Dominance constraints, for which a benchmark need to be assigned. By using a realistic case study, we report the main results of considering risk averse strategies under different hypotheses of the available budget, analysing the impact on the expected profit.

International audience; We study the measurement of the Internet according to two graph parameters: treewidth and hyperbolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocketfuel and Strasbourg University, at the AS or at the router level. On the one hand, the treewidth of the Internet appears to be quite large and being far from a tree with that respect, reflecting some high degree of connectivity. This proves the existence of a well linked core in the Internet. On the other hand, the hyperbolicity (as a graph parameter) appears to be very low, reflecting a tree-like structure with respect to distances. Additionally, we compute the treewidth and hyperbolicity obtained for classical Internet models and compare with the snapshots.

We present a decision support procedure for the configuration of distributed generation systems in residential districts, where various types of energy demands (electrical load, high and medium temperature thermal load, cooling load) have to be served. In the configuration process alternative solutions have to be compared, both from a technical and an economical point of view, taking into account the energy consumption profiles that vary along the day and along the year, due to the weather conditions. The decision support procedure consists of two steps. In the first step, by solving a mixed integer linear programming model, the annual optimal dispatch of the distributed generation system is determined with a hourly discretization, taking into account technical constraints, load profiles and fuel costs. The optimal dispatch is then used for the economic evaluation of the investment, taking into account prices of commodities, taxation and financial aspects (debt/equity). The decision support procedure allows to compare different alternative plant configurations; it can also be used as a simulation tool, for assessing the system sensitivity to variations of parameter values.

In this paper we propose a decentralized solution to the problem of network stabilization, under flow constraints ensuring steady—state flow optimality. We propose a stabilizing strategy for network flow control with capacity constraints which drives the buffer levels arbitrarily close to a desired reference. This is a decentralized strategy optimizing the flow via the minimization of a quadratic cost of the control. A second problem characterized by non-fully connected networks is also considered, for which an exact network equilibrium is not possible. Here, the strategy, in the absence of constraints leads to a least square decentralized problem, but, unfortunately, in the presence of constraints, it does not solve the constrained least square, but the minimum-distance from the unconstrained least square solution. An extension is considered to networks with intrinsic linear dynamics and we prove that our strategy is flow-optimal, with respect to a certain cost, even in this case.

A stochastic multi-stage portfolio model for a hydropower producer operating in a competitive electricity market is proposed. The portfolio includes its own production and a set of forward contracts for future delivery or purchase of electricity to hedge against risks. The goal of using such a model is to maximise the profit of the producer and reduce the economic risks connected to the fact that energy spot and forward prices are highly volatile. Our findings show that the use of forward contracts for hedging purposes results in a risk reduction and in a more efficient use of the hydroplant, taking advantage of the possibility of pumping water and ending up with a higher final value of the reservoi

This paper deals with the problem of assigning a Home Care (HC) patient to an operator, among a set of possible ones, under the constraint of continuity of care. To balance the workload among the operators, HC providers usually adopt an approach based on the difference between the operator capacity and his/her mean workload. In this paper, we propose a policy to assign a new admitted patient to the operator with the lowest cost increment, by taking into account or not the variability of patient demand. The comparison of the policy with the current practice of assigning the patient to the operator with the highest free capacity shows that savings can be reached by implementing the proposed policy.

We study the problem of injured people evacuation in the case of a medium/maxi health-care emergency such as, e.g., an airplane crash, a maxi-intoxication, or a major car accident, in which many patients are to be simultaneously evacuated, by being assigned to a hospital and to an ambulance, taking into account a color code, denoting their severity, their distances to the hospitals, and the hospital resources and competences. The work is part of the research project DECEMbRIA, funded by the Lombardy Region in Italy and carried out in collaboration with the local emergency service (118). In this paper, we propose a compact integer-linear programming formulation for the problem and show that, by relaxing the integrality constraints of some variables, the formulation still yields integer solutions. We report computational results obtained using both a commercial and a freely available solver.

We propose a novel approach that, given a linear saturated feedback control policy, asks for the objective function that makes robust optimal such a policy. The approach is specialized to a linear network flow system with unknown but bounded demand and politopic bounds on controlled flows. All results are derived via the Hamilton-Jacobi-Isaacs and viscosity theory.

We consider a continuous time linear multi inventory system with unknown demands bounded within ellipsoids and controls bounded within ellipsoids or polytopes. We address the problem of "-stabilizing the inventory since this implies some reduction of the inventory costs. The main results are certain conditions under which "-stabilizability is possible through a saturated linear state feedback control. All the results are based on a Linear Matrix Inequalities (LMIs) approach and on some recent techniques for the modeling and analysis of polytopic systems with saturations., Comment: submitted to Operational Research Letters

Hybrid optimal control problems are, in general, difficult to solve. A current research goal is to isolate those problems that lead to tractable solutions [5]. In this paper, we identify a special class of hybrid optimal control problems which are easy to solve. We do this by using a paradigm borrowed from the Operations Research field. As main result, we present a solution algorithm that converges to the exact solution in polynomial time. Our approach consists in approximating the hybrid optimal control problem via an integer-linear programming reformulation. The integer-linear programming problem is a Set-covering one with a totally unimodular constraint matrix and therefore solving the Set-covering problem is equivalent to solving its linear relaxation. It turns out that any solution of the linear relaxation is a feasible solution for the hybrid optimal control problem. Then, given the feasible solution, obtained solving the linear relaxation, we find the optimal solution via local search.