1,720,981 research outputs found
The New Generation of OR Enthusiasts: the AIROYoung Experiment
Full text linkThis special issue is dedicated to young researchers in operations research (OR) and to the newest topics of research in this field. To better understand the new generations of OR enthusiasts, what they are working on, and how they are going to feel part of this research community, the issue is dedicated to the 4th AIROYoung Workshop (Bolzano, 5–7 February 2020) and to the Italian AIROYoung chapter experience. AIROYoung is an example of a successful initiative that was born “from young researchers for young researchers”: volunteering PhDs and young OR specialists put their time and energies to create a young community, offer resources, and foster the collaboration between universities and industries. The issue will contain both scientific papers on the newest research topics, and extra contents and interviews to picture the community behind AIROYoung, and why it is important for young OR researchers around the world to feel part of a community
Two-phase strategies for the bi-objective minimum spanning tree problem
No full textThis paper presents a new two-phase algorithm for the bi-objective minimum spanning tree (BMST) problem. In the first phase, it computes the extreme supported efficient solutions resorting to both mathematical programming and algorithmic approaches, while the second phase is devoted to obtaining the remaining efficient solutions (non-extreme supported and non-supported). This latter phase is based on a new recursive procedure capable of generating all the spanning trees of a connected graph through edge interchanges based on increasing evaluation of non-zero reduced costs of associated weighted linear programs. Such a procedure exploits a common property of a wider class of problems to which the minimum spanning tree (MST) problem belongs, that is the spanning tree structure of its basic feasible solutions. Computational experiments are conducted on different families of graphs and with different types of cost. These results show that this new two-phase algorithm is correct, very easy to implement and it allows one to extract conclusions on the difficulty of finding the entire set of Pareto solutions of the BMST problem depending on the graph topology and the possible correlation of the edge costs
An extended model of coordination of an all-terrain vehicle and a multivisit drone
No full textIn this paper, a model that combines the movement of a multivisit drone with a limited endurance and a base vehicle that can move freely in the continuous space is considered. The mothership is used to charge the battery of the drone, whereas the drone performs the task of visiting multiple targets of distinct shapes: points and polygonal chains. For polygonal chains, it is required to traverse a given fraction of its lengths that represent surveillance/inspection activities. The goal of the problem is to minimize the overall weighted distance traveled by both vehicles. A mixed integer second-order cone program is developed and strengthened using valid inequalities and giving good bounds for the Big-M constants that appear in the model. A refined matheuristic that provides reasonable solutions in short computing time is also established. The quality of the solutions provided by both approaches is compared and analyzed on an extensive battery of instances with different number and shapes of targets, which shows the usefulness of our approach and its applicability in different situations
An integrated model for high-speed rolling-stock planning and maintenance scheduling
No full textHigh-speed trains have to undergo special maintenance services. The maintenance service is highly specialized and can only run on specific platforms. Most of the optimization models proposed in the literature do not consider this problem integrated with the rolling-stock planning, although the two problems affect each other, and their separation leads to suboptimal solutions of the overall problem. This article presents an integrated approach based on a mixed integer mathematical formulation and computational results on a testbed of instances, derived from a real-world case study. This approach is compared with a two-stage one, commonly used in practice and in the literature. The results show that the rolling-stock planning problem can produce input parameters for the scheduling problem for which no feasible schedules exist. When a scheduling solution exists, the final percentage gap of the two-stage solution is much higher than the one provided by the integrated model
Coordinating drones with mothership vehicles: The mothership and drone routing problem with graphs
No full textThis paper addresses the optimization of routing problems with drones. It analyzes the coordination of one mothership with one drone to obtain optimal routes that have to visit some target objects modeled as general graphs. The goal is to minimize the overall weighted distance traveled by both vehicles while satisfying the requirements in terms of percentages of visits to targets. We discuss different approaches depending on the assumption made on the route followed by the mothership: i) the mothership can move on a continuous framework (the Euclidean plane), ii) on a connected piecewise linear polygonal chain or iii) on a general graph. In all cases, we develop exact formulations resorting to mixed integer second order cone programs that are compared on a testbed of instances to assess their performance. The high complexity of the exact methods makes it difficult to find optimal solutions in short computing time. For that reason, besides the exact formulations we also provide a tailored matheuristic algorithm that allows one to obtain high quality solutions in reasonable time. Computational experiments show the usefulness of our methods in different scenarios
Optimal energy management of uav-based cellular networks powered by solar panels and batteries: Formulation and solutions
No full textWe focus on the problem of managing the energy consumption of a cellular network tailored to cover rural and low-income areas. The considered architecture exploits Unmanned Aerial Vehicles (UAVs) to ensure wireless coverage, as well as Solar Panels (SPs) and batteries installed in a set of ground sites, which provides the energy required to recharge the UAVs. We then target the maximization of the energy stored in the UAVs and in the ground sites, by ensuring the coverage of the territory through the scheduling of the UAV missions over space and time. After providing the problem formulation, we face its complexity by proposing a decomposition-based approach and by designing a brand-new genetic algorithm. The results, obtained over a set of representative case studies, reveal that there exists a trade-off between the UAVs battery level, the ground sites battery level, and the level of coverage. In addition, both the decomposed version and the genetic algorithm perform sufficiently close to the integrated model, with a strong improvement in the computation times
A multiple-drone arc routing and mothership coordination problem
Full text linkThis paper considers the optimisation problems that arise in coordinating a tandem between a mothership vehicle and a fleet of drones. Each drone can be launched from the mothership to perform a task. After completing their tasks, the drones return to the mothership to recharge their batteries and be ready for a new task. Tasks consist of (partially) visiting graphs of a given length to provide some services or to carry out a surveillance/inspection activity. The goal is to minimise the overall time of travelling carried out by the mothership (makespan) while satisfying some requirements in terms of fractions of visits to the target graphs. In all cases, we develop exact formulations resorting to mixed-integer second-order cone programmes that are compared on a testbed of instances to assess their performance. We also develop a matheuristic algorithm that provides reasonable solutions. Computational experiments show the usefulness of our methodology in different scenarios
A Mathematical Programming Approach to Sparse Canonical Correlation Analysis
Full text linkRecent developments in the interplay between Operational Research and Statistics allowed us to exploit
advances in Mixed-Integer Optimisation (MIO) solvers to improve the quality of statistical analysis. In
this work, we tackle Canonical Correlation Analysis (CCA), a dimensionality reduction method that jointly
summarises multiple data sources while retaining their dependency structure. We propose a new technique
for encoding sparsity in CCA by means of a mathematical programming formulation that allows one to obtain
an exact solution using readily available solvers (such as Gurobi) or design solution algorithmic procedures
based on it. Finally, we evaluate the performance of alternative solution strategies presented on multiple
datasets from the literature. The results of the extensive comparison study highlight that the proposed
approach is capable of finding the optimal correlation or finding good quality solutions, better than those
provided by other conventional methods
A fast and effective greedy heuristic for on-line train calendars generation
No full textThis paper describes a new approach for train calendars textual generation, that is a heuristic algorithm designed to automatically generate a text to final customers, concisely and clearly, from a service calendar represented by a boolean vector as input. This niche problem belongs to the transportation field, specifically, to railway services. The new heuristic algorithm, developed in the C programming language, guarantees a constant computation time, between 0 and 16 ms. Tested on several real railway timetables, this new approach was extensively compared with existing mathematical programming models presented in Amorosi et al. (2019), with a significant reduction of computation times that makes it applicable in practical contexts
Energy-efficient mission planning of UAVs for 5G coverage in rural zones
No full textWe target the problem of providing 5G network connectivity in rural zones by means of Base Stations (BSs) carried by Unmanned Aerial Vehicles (UAVs). Our goal is to schedule the UAVs missions to: i) limit the amount of energy consumed by each UAV, ii) ensure the coverage of selected zones over the territory, ii) decide where and when each UAV has to be recharged in a ground site, iii) deal with the amount of energy provided by Solar Panels (SPs) and batteries installed in each ground site. We then formulate the RURALPLAN optimization problem, a variant of the unsplittable multicommodity flow problem defined on a multiperiod graph. After detailing the objective function and the constraints, we solve RURALPLAN in a realistic scenario. Results show that RURALPLAN is able to outperform a solution ensuring coverage but not considering the energy management of the UAVs
- …
