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.     

Optimization of air vehicles operations using mixed-integer linear programming

A scenario where multiple air vehicles are required to prosecute geographically dispersed targets is considered. Furthermore, multiple tasks are to be successively performed on each target, that is, the targets must be classified, attacked, and verified as destroyed. The optimal, for example, minimum time, performance of these tasks requires cooperation among the vehicles such that critical timing constraints are satisfied, that is, a target must be classified before it can be attacked, and an air vehicle is sent to a target area to verify its destruction only after the target has been attacked. In this paper, the optimal task assignment/scheduling problem is posed as a mixed-integer linear program (MILP). The solution of the MILP assigns all tasks to the vehicles and performs the scheduling in an optimal manner, including staged departure times. Coupled tasks involving timing and task order constraints are automatically addressed. When the air vehicles have sufficient endurance, the existence of a solution is guaranteed.     

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.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

Evaluation of the genetic algorithm parameters on the optimization performance: a case study on pump-and-treat remediation design

In this study, the impacts of different crossover and encoding schemes on the performance of a genetic algorithm (GA) in finding optimal pump-and-treat (P&T) remediation designs are investigated. For this purpose, binary and Gray encodings of the decision variables are tested. Uniform and two-point crossover schemes are evaluated for two different crossover probabilities. Analysis is performed for two P&T system optimization scenarios. Results show that uniform crossover operator with Gray encoding outperforms the other alternatives for the complex problem with higher number of decision variables. On the other hand, when a simpler problem, which had a lower number of decision variables, is solved, the efficiency of GA is independent of the encoding and crossover schemes.     

On the robust assignment problem under a fixed number of cost scenarios

We investigate the complexity of the min-max assignment problem under a fixed number of scenarios. We prove that this problem is polynomial-time equivalent to the exact perfect matching problem in bipartite graphs, an infamous combinatorial optimization problem of unknown computational complexity.     

Generalized cover facet inequalities for the generalized assignment problem

The generalized assignment problem is that of finding an optimal assignment of agents to tasks, where each agent may be assigned multiple tasks and each task is performed exactly once. This is an NP-complete problem. Algorithms that employ information about the polyhedral structure of the associated polytope are typically more effective for large instances than those that ignore the structure. A class of generalized cover facet-defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from generalized cover inequalities.     

An Interactive Algorithm for Multi-objective Route Planning

We address the route selection problem for Unmanned Air Vehicles (UAV) under multiple objectives. We consider a general case for this problem, where the UAV has to visit several targets and return to the base. We model this problem as a combination of two combinatorial problems. First, the path to be followed between each pair of targets should be determined. We model this as a multi-objective shortest path problem. Additionally, we need to determine the order of the targets to be visited. We model this as a multi-objective traveling salesperson problem (MOTSP). The overall problem is a combination of these two problems, which we define as a generalized MOTSP. We develop an exact interactive approach to identify the best paths and the best tour of a decision maker under a linear utility function.     

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.     

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.     

The availability of unmanned air vehicles: a post-case study

An Unmanned Air Vehicle (UAV) is an unmanned, remotely controlled, small air vehicle. It has an important role in anti-surface warfare. This implies over-the-horizon detection, classification, targeting and battle damage assessment. To perform these tasks several UAVs are needed to assist or interchange with each other. An important problem is to determine how many UAVs are needed in this respect. The answer depends on the characteristics of the UAV and its mission. The UAV availability problem is very complex and the usual method to solve such a problem is simulation. A disadvantage of simulation is that it can be very time-consuming. Hence it is not very suitable for sensitivity analysis. Moreover, since simulation gives mere approximations and is not very generic, theoretical insights are hardly gained. In this paper we show how such a complex problem can still be tackled analytically by using a basic model from reliability theory, viz., a 1-out-of-n system with cold standby, ample repair facility and general life time and repair distributions.     

A genetic algorithm for robotic assembly line balancing

Flexibility and automation in assembly lines can be achieved by the use of robots. The robotic assembly line balancing (RALB) problem is defined for robotic assembly line, where different robots may be assigned to the assembly tasks, and each robot needs different assembly times to perform a given task, because of its capabilities and specialization. The solution to the RALB problem includes an attempt for optimal assignment of robots to line stations and a balanced distribution of work between different stations. It aims at maximizing the production rate of the line. A genetic algorithm (GA) is used to find a solution to this problem. Two different procedures for adapting the GA to the RALB problem, by assigning robots with different capabilities to workstations are introduced: a recursive assignment procedure and a consecutive assignment procedure. The results of the GA are improved by a local optimization (hill climbing) work-piece exchange procedure. Tests conducted on a set of randomly generated problems, show that the Consecutive Assignment procedure achieves, in general, better solution quality (measured by average cycle time). Further tests are conducted to determine the best combination of parameters for the GA procedure. Comparison of the GA algorithm results with a truncated Branch and Bound algorithm for the RALB problem, demonstrates that the GA gives consistently better results.     

Flying-V型仓储布局货位分配优化方法研究

Flying-V是一种典型的非传统布局方式,根据其布局方式的特性,针对仓储货位分配优化问题,以货物出入库效率最高和货物存放的重心最低为优化目标,建立了货位分配多目标优化模型,并采用自适应策略的遗传算法(GA),以及粒子群算法(PSO)进行求解。根据货位分配的优化特点,在GA算法的选择、交叉和变异环节均采用自适应策略, 同时采用惯性权重线性递减的方法设计了PSO算法,有效地解决了两种算法收敛速度慢和易“早熟”的问题,提高了算法的寻优性能。为了更好地表现两种优化求解算法的有效性和优越性,结合具体的货位分配实例利用MATLAB软件编程实现。通过对比分析优化结果表明,PSO算法在收敛速度和优化效果方面相比于自适应GA算法更具有优势,更加合适于解决Flying-V型仓储布局货位分配优化问题。     

多无人机协同任务策略优化

从研究多无人机协同任务的系统资源分配、任务分配、航线规划、轨迹优化等问题入手,建立了多基地多无人机协同侦察模型.针对问题,首先利用"栅格化聚拢"的思想对目标点进行过滤优化,进而对目标群和无人机基地进行了任务分配,而后结合蚁群算法、贪心算法、最短路径算法等思想,通过Matlab平台,计算出能够让无人机停留在雷达探测区域总时间最少的最优策略.     

Round robin tournaments and three index assignments

Scheduling a sports league can be seen as a difficult combinatorial optimization problem. We study some variants of round robin tournaments and analyze the relationship with the planar three-index assignment problem. The complexity of scheduling a minimum cost round robin tournament is established by a reduction from the planar three-index assignment problem. Furthermore, we introduce integer programming models. We pick up a popular idea and decompose the overall problem in order to obtain two subproblems which can be solved sequentially. We show that the latter subproblem can be casted as a planar three-index assignment problem. This makes existing solution techniques for the planar three-index assignment problem amenable to sports league scheduling.     

Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems

Various conic relaxations of quadratic optimization problems in nonnegative variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combinatorial optimization problems can be expressed in several ways, each of which results in different conic relaxations. For the completely positive, doubly nonnegative and semidefinite relaxations of the combinatorial optimization problems, we discuss the equivalences and differences among the relaxations by investigating the feasible regions obtained from different representations of the combinatorial condition which we propose as a generalization of the binary and complementarity condition. We also study theoretically the issue of the primal and dual nondegeneracy, the existence of an interior solution and the size of the relaxations, as a result of different representations of the combinatorial condition. These characteristics of the conic relaxations affect the numerical efficiency and stability of the solver used to solve them. We illustrate the theoretical results with numerical experiments on QAP instances solved by SDPT3, SDPNAL+ and the bisection and projection method.     

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.     

一类广义指派问题的有效解法

提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.     

Multiple depot ring star problem: a polyhedral study and an exact algorithm

The multiple depot ring-star problem (MDRSP) is an important combinatorial optimization problem that arises in optical fiber network design and in applications that collect data using stationary sensing devices and autonomous vehicles. Given the locations of a set of customers and a set of depots, the goal is to (i) find a set of simple cycles such that each cycle (ring) passes through a subset of customers and exactly one depot, (ii) assign each non-visited customer to a visited customer or a depot, and (iii) minimize the sum of the routing costs, i.e., the cost of the cycles and the assignment costs. We present a mixed integer linear programming formulation for the MDRSP and propose valid inequalities to strengthen the linear programming relaxation. Furthermore, we present a polyhedral analysis and derive facet-inducing results for the MDRSP. All these results are then used to develop a branch-and-cut algorithm to obtain optimal solutions to the MDRSP. The performance of the branch-and-cut algorithm is evaluated through extensive computational experiments on several classes of test instances.     

考虑多救援点的突发事件应急救援人员派遣模型

针对具有多救援点的突发事件应急救援人员派遣问题,给出了一种应急救援人员派遣模型。首先,依据救援人员关于救援任务的能力指标评价值计算出不同出救点的救援人员对救援点中救援任务的胜任度;其次,依据救援人员到达救援点的应急救援时间计算出应急救援时间满意度;然后,将救援人员对救援点的胜任度与应急救援时间满意度进行集结,获得应急救援人员与各救援点的综合匹配度;进一步地,以综合匹配度最大为目标,构建应急救援人员派遣优化模型,并通过模型求解获得最优的应急救援人员派遣方案;最后,通过一个算例说明了所构建的应急救援人员派遣模型具有可用性。