Modelling the mobile target covering problem using flying drones

This paper addresses the mobile targets covering problem by using unmanned aerial vehicles (UAVs). It is assumed that each UAV has a limited initial energy and the energy consumption is related to the UAV’s altitude. Indeed, the higher the altitude, the larger the monitored area and the higher the energy consumption. When an UAV runs out of battery, it is replaced by a new one. The aim is to locate UAVs in order to cover the piece of plane in which the target moves by using a minimum number of UAVs. Each target has to be monitored for each instant time. The problem under consideration is mathematically represented by defining mixed integer non-linear optimization models. Heuristic procedures are defined and they are based on restricted mixed integer programming (MIP) formulation of the problem. A computational study is carried out to assess the behaviour of the proposed models and MIP-based heuristics. A comparison in terms of efficiency and effectiveness among models and heuristics is carried out.     

A truck and drones model for last-mile delivery: A mathematical model and heuristic approach

We present a mathematical formulation and a heuristic solution approach for the optimal planning of delivery routes in a multi-modal system combining truck and Unmanned Aerial Vehicle (UAV) operations. In this system, truck and UAV operations are synchronized, i.e., one or more UAVs travel on a truck, which serves as a mobile depot. Deliveries can be made by both UAVs and the truck. While the truck follows a multi-stop route, each UAV delivers a single shipment per dispatch. The presented optimization model minimizes the waiting time of customers in the system. The model determines the optimal allocation of customers to truck and UAVs, the optimal route sequence of the truck, and the optimal launch and reconvene locations of the UAVs along the truck route. We formulate the problem as a Mixed-Integer Linear Programming (MILP) model and conduct a bound analysis to gauge the maximum potential of the proposed system to reduce customer waiting time compared to a traditional truck-only delivery system. To be able to solve real-world problem size instances, we propose an efficient Truck and Drone Routing Algorithm (TDRA). The solution quality and computational performance of the mathematical model and the TDRA are compared together and with the truck-only model based on a variety of problem instances. Further, we apply the TDRA to a real-world case study for e-commerce delivery in São Paulo, Brazil. Our numerical results suggest significant reductions in customer waiting time to be gained from the proposed multi-modal delivery model.     

Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms

A problem of assigning multiple agents to simultaneously perform cooperative tasks on consecutive targets is posed as a new combinatorial optimization problem. The investigated scenario consists of multiple ground moving targets prosecuted by a team of unmanned aerial vehicles (UAVs). The team of agents is heterogeneous, with each UAV carrying designated sensors and all but one carry weapons as well. To successfully prosecute each target it needs to be simultaneously tracked by two UAVs and attacked by a third UAV carrying a weapon. Only for small-sized scenarios involving not more than a few vehicles and targets the problem can be solved in sufficient time using classical combinatorial optimization methods. For larger-sized scenarios the problem cannot be solved in sufficient time using these methods due to timing constraints on the simultaneous tasks and the coupling between task assignment and path planning for each UAV. A genetic algorithm (GA) is proposed for efficiently searching the space of feasible solutions. A matrix representation of the chromosomes simplifies the encoding process and the application of the genetic operators. To further simplify the encoding, the chromosome is composed of sets of multiple genes, each corresponding to the entire set of simultaneous assignments on each target. Simulation results show the viability of the proposed assignment algorithm for different sized scenarios. The sensitivity of the performance to variations in the GA tuning parameters is also investigated.     

Benchmarking of maintenance performance: a case study in two manufacturers of furniture

When profit margins of a plant are decreasing, the need forreliable and efficient maintenance policy becomes more important.Measuring maintenance performance is important for companiesto recognize whether their planned goals are achieved or not.Also, such measurements can be utilized for benchmarking, whichis one of the tools for never-ending improvement. But, theseobjectives cannot be achieved without well-documented data ofthe relevant variables. Better data coverage and quality isnecessary for following maintenance performance developmentand it would, in many cases, clarify the ambiguity concerningthe main problem in the context, namely that neither the productionnor maintenance department can show what effect maintenancehas on profitability. A more effective maintenance policy indirectly implies improvementsin product quality and manufacturing process effectiveness.Elongation of the production time, i.e. reducing the downtimedue to failures, planned replacements and repair, in additionto the improvement in the total maintenance activities, arealso some of the results that can be expected when an efficientmaintenance policy is used. Measuring and monitoring maintenanceperformance measures is required partly for detecting, and eventuallytreating as soon as possible, undesirable changes and partlyto make benchmarking with the best in the branch, which savesappreciable economic losses for companies. In this paper, a model for how to identify the measurable variables,which are needed to develop measures for monitoring maintenanceperformance behaviour systematically, is developed. Five maintenanceperformance measures are proposed and applied. An additionalmodel for systematically analysing the trend of maintenanceperformance measures, for an overall assessment of the company'ssituation, is presented. Two case studies in manufacturers offurniture are conducted to verify these models.     

Online stochastic UAV mission planning with time windows and time-sensitive targets

In this paper we simultaneously consider three extensions to the standard Orienteering Problem (OP) to model characteristics that are of practical relevance in planning reconnaissance missions of Unmanned Aerial Vehicles (UAVs). First, travel and recording times are uncertain. Secondly, the information about each target can only be obtained within a predefined time window. Due to the travel and recording time uncertainty, it is also uncertain whether a target can be reached before the end of its time window. Finally, we consider the appearance of new targets during the flight, so-called time-sensitive targets, which need to be visited immediately if possible. We tackle this online stochastic UAV mission planning problem with time windows and time-sensitive targets using a re-planning approach. To this end, we introduce the Maximum Coverage Stochastic Orienteering Problem with Time Windows (MCS-OPTW). It aims at constructing a tour with maximum expected profit of targets that were already known before the flight. Secondly, it directs the planned tour to predefined areas where time-sensitive targets are expected to appear. We have developed a fast heuristic that can be used to re-plan the tour, each time before leaving a target. In our computational experiments we illustrate the benefits of the MCS-OPTW planning approach with respect to balancing the two objectives: the expected profits of foreseen targets, and expected percentage of time-sensitive targets reached on time. We compare it to a deterministic planning approach and show how it deals with uncertainty in travel and recording times and the appearance of time-sensitive targets.     

Performance prediction of an unmanned airborne vehicle multi-agent system

Consider unmanned airborne vehicle (UAV) control agents in a dynamic multi-agent system. The agents must have a set of goals such as destination airport and intermediate positions. At the same time, the agents have to avoid gun shootings which move to their neighbors randomly. Agents try to build and execute plans that yield a high probability of successfully achieving the targets. The plans are developed based on the negotiations between different UAVs in the region with the overall goal in mind. The information about enemy defenses can be communicated between UAVs and they can negotiate about the paths to be taken based on their resources, such as fuel, load, available time to complete the task and the information about the threat. By constructing a Markov Decision Process (MDP) in this paper, we derive the optimal path. Combining the MDP and the sample path technique, we obtain the maximum probability that the UAVs successfully reach the target.     

Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches

In this paper, we consider a task allocation model that consists of assigning a set of m unmanned aerial vehicles (UAVs) to a set of n tasks in an optimal way. The optimality is quantified by target scores. The mission is to maximize the target score while satisfying capacity constraints of both the UAVs and the tasks. This problem is known to be NP-hard. Existing algorithms are not suitable for the large scale setting. Scalability and robustness are recognized as two main issues. We deal with these issues by two optimization approaches. The first approach is the Cross-Entropy (CE) method, a generic and practical tool of stochastic optimization for solving NP-hard problem. The second one is Branch and Bound algorithm, an efficient classical tool of global deterministic optimization. The numerical results show the efficiency of our approaches, in particular the CE method for very large scale setting.     

Optimization and mechanism design

Mechanism design is about optimizing the allocation of resources when the parameters needed to determine an optimal allocation are privately held by the agents who will consume the resources. An agent’s report of her information will influence the resulting allocation which in turn will affect her utility. In such a situation, how can one simultaneously elicit the information that is privately held and choose the optimal allocation? This paper illustrates how standard results in linear programming play a role in the analysis of mechanism design problems. It is not a comprehensive survey. Rather, it focuses on two variations of a particular problem: the allocation of a single object.     

A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints

Aerial robotics can be very useful to perform complex tasks in a distributed and cooperative fashion, such as localization of targets and search of point of interests (PoIs). In this work, we propose a distributed system of autonomous Unmanned Aerial Vehicles (UAVs), able to self-coordinate and cooperate in order to ensure both spatial and temporal coverage of specific time and spatial varying PoIs. In particular, we consider an UAVs system able to solve distributed dynamic scheduling problems, since each device is required to move towards a certain position in a certain time. We give a mathematical formulation of the problem as a multi-criteria optimization model, in which the total distances traveled by the UAVs (to be minimized), the customer satisfaction (to be maximized) and the number of used UAVs (to be minimized) are considered simultaneously. A dynamic variant of the basic optimization model, defined by considering the rolling horizon concept, is shown. We introduce a case study as an application scenario, where sport actions of a football match are filmed through a distributed UAVs system. The customer satisfaction and the traveled distance are used as performance parameters to evaluate the proposed approaches on the considered scenario.     

Optimal placement of UV-based communications relay nodes

We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.     

A two-step method for forecasting spare parts demand using information on component repairs

Forecasting spare parts demand is notoriously difficult, as demand is typically intermittent and lumpy. Specialized methods such as that by Croston are available, but these are not based on the repair operations that cause the intermittency and lumpiness of demand. In this paper, we do propose a method that, in addition to the demand for spare parts, considers the type of component repaired. This two-step forecasting method separately updates the average number of parts needed per repair and the number of repairs for each type of component. The method is tested in an empirical, comparative study for a service provider in the aviation industry. Our results show that the two-step method is one of the most accurate methods, and that it performs considerably better than Croston’s method. Moreover, contrary to other methods, the two-step method can use information on planned maintenance and repair operations to reduce forecasts errors by up to 20%. We derive further analytical and simulation results that help explain the empirical findings.     

Devising a quick-running heuristic for an unmanned aerial vehicle (UAV) routing system

UAVs provide reconnaissance support for the US military and often need operational routes immediately; current practice involves manual route calculation that can involve hundreds of targets and a complex set of operational restrictions. Our research focused on providing an operational UAV routing system. This system required development of a reasonably effective, quick running routing heuristic. We present the statistical methodology used to devise a quick-running routing heuristic that provides reasonable solutions. We consider three candidate local search heuristic approaches, conduct an empirical analysis to parameterize each heuristic, competitively test each candidate heuristic, and provide statistical analysis on the performance of each candidate heuristic to include comparison of the results of the best candidate heuristic against a compilation of the best-known solutions for standard test problems. Our heuristic is a component of the final UAV routing system and provides the UAV operators a tool to perform their route development tasks quickly and efficiently.     

Error analysis for regenerative queueing estimators with special reference to gradient estimators via likelihood ratio

The performance of telecommunications systems is typically estimated (either analytically or by simulation) via queueing theoretic models. The gradient of the expected performance with respect to the various parameters (such as arrival rate or service rate) is very important as it not only measures the sensitivity to change, but is also needed for the solution of optimization problems. While the estimator for the expected performance is the sample mean of the simulation experiment, there are several possibilities for the estimator of the gradient. They include the obvious finite difference approximation, but also other recently advocated techniques, such as estimators derived from likelihood ratio transformations or from infinitesimal perturbations. A major problem in deciding upon which estimator to use and in planning the length of the simulation has been the scarcity of analytical error calculations for estimators of queueing models. It is this question that we answer in this paper for the waiting time moments (of arbitrary order) of theM / G / 1 queue by using the queueing analysis technique developed by Shalmon. We present formulas for the error variance of the estimators of expectation and of its gradient as a function of the simulation length; at arbitrary traffic intensity the formulas are recursive, while the heavy traffic approximations are explicit and of very simple form. For the gradient of the mean waiting time with respect to the arrival (or service) rate, and at 1 percent relative precision, the heavy traffic formulas show that the likelihood ratio estimator for the gradient reduces the length of the simulation required by the finite difference estimator by about one order of magnitude; further increasing the relative precision by a factor increases the reduction advantage by the same factor. At any relative precision, it exceeds the length of the simulation required for the estimation of the mean with the same relative precision by about one order of magnitude. While strictly true for theM / G / 1 queue, the formulas can also be used as guidelines in the planning of queueing simulations and of stochastic optimizations of complex queueing systems, particularly those with Poisson arivals.     

Bayesian modeling of forestry data with R using optimization and simulation tools

Data generated in forestry biometrics are not normal in statistical sense as they rarely follow the normal regression model. Hence, there is a need to develop models and methods in forest biometric applications for non-normal models. Due to generality of Bayesian methods it can be implemented in the situations when Gaussian regression models do not fit the data. Data on diameter at breast height (dbh), which is a very important characteristic in forestry has been fitted to Weibull and gamma models in Bayesian paradigm and comparisons have also been made with its classical counterpart. It may be noted that MCMC simulation tools are used in this study. An attempt has been made to apply Bayesian simulation tools using \textbf{R} software.     

Inexact Newton methods for the nonlinear complementarity problem

An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact Newton methods for solving the nonlinear, complementarity problem. In such an inexact method, the subproblems are solved only up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton method are established and analyzed. We also discuss some extensions as well as an application. This research was based on work supported by the National Science Foundation under grant ECS-8407240.     

Decomposition through formalization in a product space

When an optimization problem is posed in a product space it is classical to decompose this problem. The goal of this paper is to show how such an approach can be used when the problem to be solved is not naturally posed in a product space. By associating systematically to this problem an equivalent one posed in ann-fold cartesian product space, we obtain by decomposition of the latter both a splitting of operators and a desintegration of constraints for the former. Applications to three rather classical mathematical programming problems are given.     

Last time buy decisions for products sold under warranty

Manufacturers supplying products under warranty need a strategy to deal with failures during the warranty period: repair the product or replace it by a new one, depending on e.g. age and/or usage of the failed product. An (implicit) assumption in virtually all models is that new products to replace the failed ones are immediately available at given replacement costs. Because of the short life cycles of many products, manufacturing may be discontinued before the end of the warranty period. At that point in time, the supplier has to decide how many products to put on the shelf to replace failed products under warranty that will be returned from the field (the last time buy decision). This is a trade-off between product availability for replacement and costs of product obsolescence. In this paper, we consider the joint optimization of repair-replacement decisions and the last time buy quantity for products sold under warranty. We develop approximations to estimate the total relevant costs and service levels for this problem, and show that we can easily find near-optimal last time buy quantities using a numerical search. Comparison to discrete event simulation results shows an excellent performance of our methods.     

Problems Involving Infrequent but Significant Contingencies

Problematic situations often arise in which it is required to provide a solution which will tend to avoid events, which, if they occur, would be very costly, or, if not directly costable, they would be highly undesirable. Although direct approaches to this sort of problem exist, they can be unmanageable. If, however, we take as a posit, that the frequency with which the undesirable events arise, in the optimum solution, is small, considerable simplifications can be made. Naturally we need to check the posit once the solution has been found. This paper considers three applications of this principle, viz. determination of how many chargers are needed for steel furnaces, where the undesirable event is “a furnace waits for service”; determination of the number of emergency beds to set aside in a hospital unit, where the undesirable event is “an emergency case arrives and no bed is immediately available”; determination of an inventory reorder rule where the undesirable event is “stock run-out”. The general principle is formalized.     

Configurable node density generation with application to hotspot modelling

Mobility models are very relevant mainly when studying the performance of wireless systems by means of computer simulations. The main problem arises when deciding the best mobility model for a particular application. In some cases, it is very important to emulate hotspots or, in general, zones with different user (or node) densities. Current models do not allow complete control over hotspots, or in other words, they do not allow any general node density to be defined in the simulation area. Usually, when hotspots are modelled, closed zones are created with different numbers of users in each area, thus ensuring a fixed node density in each area. However, this approach results in an unfair comparison among users since they cannot move across zones.This paper proposes a new mechanism to solve these drawbacks. Using this mechanism, any general node density can be emulated allowing nodes to move around the entire simulation area. Any mobility model can be applied together with this density control mechanism, provided that the mobility model ensures a uniform node distribution.     

On the Measurement of Information in the Field of Criminal Detection

A method for measuring the value of information in those fields where the meaning of messages is important is discussed. At present there exists no accepted measure of information in such problem areas, the classical unit of bits flowing per second being unacceptable. It is shown that where two sets of phenomena are associated in some way with a given set of probabilities, e.g. a population and the crimes which are committed within it, the problem reduces to how much “choice” exists. This enables the concept of entropy to be used to advantage.After developing a measure of the value of information in the general case, the paper applies the method to the investigation of a case of simple larceny. This case illustrates several interesting features. Perhaps the most important feature is that some pieces of information, although they are very important to the police, only change the level of uncertainty very slightly. In such cases the piece of information generally demands that the police perform an action which either may provide useful information or lead to further action. To overcome this problem a potential entropy change is defined which takes this factor into account.It is hoped that the work may lead to a fuller understanding of how information flows in the police network. Thus it may be possible to see if the right information is getting into the police system, getting lost inside it or whether it is being used most efficiently.