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 Importance of Representing Microterrain in Studies of Air Defence against Helicopters

Simulation of air-defence engagements between ground forces and aircraft or helicopters requires complex models to examine the many-on-many interactions. One of the critical factors determining the outcome of a low-altitude engagement is the terrain over which it is fought. The terrain determines the aircraft's flight path as well as the firing opportunities for the ground forces. Methods of terrain representation that work well for aircraft engagements may not be suitable for helicopters. The different flight characteristics of helicopters cause them to interact more closely with microterrain features and so modify their flight paths. Representation of microterrain features on the terrain database leads to significantly different exposure statistics compared with those obtained when such features are absent. A bias is also present in battle-simulation results, leading to the conclusion that microterrain must be included to obtain realistic battle-model outputs when studying air defence against helicopters.     

军事物流系统中定位-运输路线安排模型及算法

考虑到战时物资需求的紧迫性和保障资源的有限性,从决策者的角度出发,以军事物流系统总体供应时间最短为目标,构建了两级军事配送网络的定位-运输路线安排模型,并给出一种启发式算法.算法分为两个阶段,首先利用蚁群算法和线性规划的方法解决运输路线安排问题,然后运用贪婪搜索算法解决军事物流配送中心选址问题.最终,将两种算法结合起来进行逐步搜索,从而得到模型的解,并运用实例说明了算法的有效性和可行性.     

Operational aircraft maintenance routing problem with remaining time consideration

The aircraft maintenance routing problem is one of the most studied problems in the airline industry. Most of the studies focus on finding a unique rotation that will be repeated by each aircraft in the fleet with a certain lag. In practice, using a single rotation for the entire fleet is not applicable due to stochasticity and operational considerations in the airline industry. In this study, our aim is to develop a fast responsive methodology which provides maintenance feasible routes for each aircraft in the fleet over a weekly planning horizon with the objective of maximizing utilization of the total remaining flying time of fleet. For this purpose, we formulate an integer linear programming (ILP) model by modifying the connection network representation. The proposed model is solved by using branch-and-bound under different priority settings for variables to branch on. A heuristic method based on compressed annealing is applied to the same problem and a comparison of exact and heuristic methods are provided. The model and the heuristic method are extended to incorporate maintenance capacity constraints. Additionally, a rolling horizon based procedure is proposed to update the existing routes when some of the maintenance decisions are already fixed.     

Simultaneous evacuation and entrance planning in complex building based on dynamic network flows

This paper presents mathematical models and a heuristic algorithm that address a simultaneous evacuation and entrance planning. For the simultaneous evacuation and entrance planning, four types of mathematical models based on the discrete time dynamic network flow model are developed to provide the optimal routes for evacuees and responders within a critical timeframe. The optimal routes obtained by the mathematical models can minimize the densification of evacuees and responders into specific areas. However, the mathematical model has a weakness in terms of long computation time for the large-size problem. To overcome the limitation, we developed a heuristic algorithm. We also analyzed the characteristics of each model and the heuristic algorithm by conducting case studies. This study pioneers area related to evacuation planning by developing and analyzing four types of mathematical models and a heuristic algorithm which take into account simultaneous evacuation and entrance planning.     

Scheduling aircraft landings at London Heathrow using a population heuristic

With increasing levels of air traffic, making effective use of limited airport capacity is obviously important. This paper reports on an investigation undertaken by National Air Traffic Services in the UK into improving runway utilisation at London Heathrow. This investigation centred on developing an algorithm for improving the scheduling of aircraft waiting to land. The heuristic algorithm developed (a population heuristic) is discussed and results presented using actual operational data relating to aircraft landings at London Heathrow. This data indicates that our algorithm could have improved on air traffic control decisions in such cases by between 2–5?% in terms of reducing the timespan required to land all of the aircraft considered.     

A mathematical programming model for the bus deviation route problem

In small towns, or in those peripherical metropolitan areas in which the demand for public transportation is relatively low, the objectives of the bus route planner are different from those faced in highly congested networks. Some towns, also in Italy, are experimenting with urban public transportation systems where regular bus routes are designed which allow users located at specific points outside the main line to signal their presence to the bus driver, who then deviates from the main route to satisfy this demand. This way the bus line is a mixture between a regular line and a dial-a-ride system. The bus deviation route problem is concerned with the design problem which arises in planning the location of the demand points outside the line. A model is presented which takes into account both the advantage of passengers served by this deviation device and the disadvantage suffered by passengers on the bus, whose travel time increases during deviations, and by passengers downstream of the deviation whose waiting time also increases. Through some modeling assumption we are able to represent this problem as a mixed integer linear programming problem, whose relatively low dimension allows for exact solution through standard simplex-based branch and bound code. The proposed model has been applied to a real case and some results of this are presented and discussed.     

Network flow-based approaches for integrated aircraft fleeting and routing

Given a schedule of flights to be flown, the aircraft fleeting and routing problem (AFRP) consists of determining a minimum-cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenance requirements and other activity constraints. We investigate network flow-based heuristic approaches for this problem. Computational experiments conducted on real-data given by TunisAir show that the proposed heuristic consistently yields very near-optimal solutions while requiring modest CPU effort.     

Improving short-term conflict alert via tabu search

In this paper we describe some work carried out by National Air Traffic Services in the UK into developing optimisation tools to help improve the effectiveness of one of their air traffic control safety systems—short-term conflict alert. In short-term conflict alert a computer system continually monitors radar data and alerts air traffic controllers if it detects a situation where two aircraft are in danger of approaching too close to one other. Within the computer program that makes up the short-term conflict alert system is a large number of parameters. Choosing appropriate values for these parameters is a task that is currently done via extensive human intervention. In this paper we describe how a modern heuristic technique, tabu search, can be used to make parameter choices.     

The min-max multi-depot vehicle routing problem: heuristics and computational results

In the multi-depot vehicle routing problem (MDVRP), there are several depots where vehicles can start and end their routes. The objective is to minimize the total distance travelled by all vehicles across all depots. The min-max multi-depot vehicle routing problem (Min-Max MDVRP) is a variant of the standard MDVRP. The primary objective is to minimize the length of the longest route. We develop a heuristic (denoted by MD) for the Min-Max MDVRP that has three stages: (1) simplify the multi-depot problem into a single depot problem and solve the simplified problem; (2) improve the maximal route; (3) improve all routes by exchanging customers between routes. MD is compared with two alternative heuristics that we also develop and an existing method from the literature on a set of 20 test instances. MD produces 15 best solutions and is the top performer. Additional computational experiments on instances with uniform and non-uniform distributions of customers and varying customer-to-vehicle ratios and with real-world data further demonstrate MD’s effectiveness in producing high-quality results.     

Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery

The vehicle routing problem (VRP) with simultaneous pickup and delivery (VRPSPD) is an extension of the classical capacitated VRP (CVRP). In this paper, we present the saving heuristic and the parallel saving heuristic for VRPSPD. Checking the feasibility of a route in VRPSPD is difficult because of the fluctuating load on the route. In the saving heuristic, a new route is created by merging the two existing routes. We use a cumulative net-pickup approach for checking the feasibility when two existing routes are merged. The numerical results show that the performance of the proposed heuristics is qualitatively better than the existing insertion-based heuristics.     

Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem

Because most commercial passenger airlines operate on a hub-and-spoke network, small disturbances can cause major disruptions in their planned schedules and have a significant impact on their operational costs and performance. When a disturbance occurs, the airline often applies a recovery policy in order to quickly resume normal operations. We present in this paper a large neighborhood search heuristic to solve an integrated aircraft and passenger recovery problem. The problem consists of creating new aircraft routes and passenger itineraries to produce a feasible schedule during the recovery period. The method is based on an existing heuristic, developed in the context of the 2009 ROADEF Challenge, which alternates between three phases: construction, repair and improvement. We introduce a number of refinements in each phase so as to perform a more thorough search of the solution space. The resulting heuristic performs very well on the instances introduced for the challenge, obtaining the best known solution for 17 out of 22 instances within five minutes of computing time and 21 out of 22 instances within 10 minutes of computing time.     

An Heuristic Method for Solving Time-Sensitive Routeing Problems

Many vehicle scheduling situations require careful monitoring and control of the time a vehicle is on the road. Setting time limits as rigid constraints on a vehicle scheduling problem is usually not appropriate since minor violations of such constraints do not really imply that a solution is infeasible. An heuristic method for solving vehicle scheduling problems in which time is an important factor has been developed. The heuristic creates routes based on a "time density function" which identifies clusters of stops and chooses stops from these clusters to form a route. Important considerations balancing overtime costs, overnight route costs and travel costs to and from far clusters of stops are part of the heuristic. The method has been tested on 10 days of data from a large food distributor in the midwestern United States and found to affect significantly both variable and fixed costs in these commercial problems. The smallest of these problems had 110 stops, while the largest had 223. A modest amount of computer time (under 15 seconds in every case) was required to generate the assignment of stops to trucks and produce routes for the vehicles.     

Representing the command and control process in simulation models of conflict

Command and Control is the process by which military personnel in war command their forces to take account of military aims and objectives. Across NATO, there is a growing realisation that the proper representation of Command and Control (C2) in models of conflict is very important. Since it essentially concerns itself with the representation of human decision-making, this is recognised as one of the most difficult areas for defence analysis. One approach to this problem is through the use of large rule-based expert systems. The work reported here lays out an alternative approach founded on the use of Bayesian inference and transitions between different mission ‘states’, leading to what we call the the mission based approach to Command and Control. These ideas are already being incorporated into the next generation of simulation models currently under development which range across the land/air, maritime and peacekeeping areas of application.     

The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints

The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to satisfy operational constraints. The aim of this paper is to develop an operationally flexible method, based upon the one-day routes business model, to compute tail assignments that satisfy short-range—within the next three days—aircraft maintenance requirements. While maintenance plans commonly span multiple days, the methods used to compute tail assignments for the given plans can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by using solutions from the one-day routes aircraft maintenance routing approach as input. The daily tail assignment problem is solved with an objective to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A computational study will be performed to assess the performance of exact and heuristic solution algorithms that modify the input lines-of-flight to reduce maintenance misalignments. The daily tail assignment problem and the developed algorithms are demonstrated to compute solutions that effectively satisfy maintenance requirements when evaluated using input data collected from three different airlines.     

Bi-criteria dynamic location-routing problem for patrol coverage

In this paper, we address the problem of dynamic patrol routing for state troopers for effective coverage of highways. Specifically, a number of state troopers start their routes at temporary stations (TS), patrol critical locations with high crash frequencies, and end their shifts at other (or the same) TS so the starting points for the next period are also optimized. We determine the number of state troopers, their assigned routes, and the locations of the TS where they start and end their routes. The TS are selected from a given set of potential locations. The problem, therefore, is a multi-period dynamic location-routing problem in the context of public service. Our objective is to maximize the critical location coverage benefit while minimizing the costs of TS selections, vehicle utilizations, and routing/travel. The multi-objective nature of the problem is handled using an ?-constraint approach. We formulate the problem as a mixed integer linear programming model and solve it using both off-the-shelf optimization software and a custom-built, efficient heuristic algorithm. The heuristic, utilizing the hierarchical structure of the problem, is built on the decomposition of location and routing problems. By allowing routing to start from multiple locations, our model improves the coverage by as much as 12% compared with the single-depot coverage model.     

A synthesis of assignment and heuristic solutions for vehicle routing with time windows

This paper proposes a three-stage method for the vehicle-routing problem with time window constraints (VRPTW). Using the Hungarian method the optimal customer matching for an assignment approximation of the VRPTW, which is a travel time-based relaxation that partially respects the time windows, is obtained. The assignment matching is transformed into feasible routes of the VRPTW via a simple decoupling heuristic. The best of these routes, in terms of travelling and vehicle waiting times, form part of the final solution, which is completed by the routes provided by heuristic methods applied to the remainder of the customers. The proposed approach is tested on a set of standard literature problems, and improves the results of the heuristic methods with respect to total travel time. Furthermore, it provides useful insights into the effect of employing optimal travel time solutions resulting from the assignment relaxation to derive partial route sets of the VRPTW.     

A Game Theoretical Multiple Resource Interaction Approach to Resource Allocation in an Air Campaign

In this paper we propose a multiple resource interaction model in a game-theoretical framework to solve resource allocation problems in theater level military campaigns. An air raid campaign using SEAD aircraft and bombers against an enemy target defended by air defense units is considered as the basic platform. Conditions for the existence of saddle point in pure strategies is proved and explicit feedback strategies are obtained for a simplified model with linear attrition function limited by resource availability. An illustrative example demonstrates the key features.     

A decision support model for establishing an air taxi service: a case study

Recent availability of relatively cheap small jet aircraft creates opportunities for a new air transport business: Air taxi, an on-demand service in which travellers call in one or a few days in advance to book transportation. In this paper, we present a methodology and simulation study supporting important strategic decisions, like for instance determining the required number of aircraft, for a company planning to establish an air taxi service in Norway. The methodology is based on a module simulating incoming bookings, built around a heuristic for solving the underlying dial-a-flight problem. The heuristic includes a separate method for solving the important subproblem of determining the best distribution of waiting time along a single aircraft schedule. The methodology has proved to provide reliable decision support to the company.     

A heuristic approach for an integrated fleet-assignment,aircraft-routing and crew-pairing problem

This paper deals with the fleet-assignment, aircraft-routing and crew-pairing problems of an airline flying between Canary Islands. There are two major airports (bases). The company is subdivided in three operators. There are no flight during the night. A crew route leaves from and returns to the same base. An aircraft route starts from one base and arrive to the other base due to maintenance requirements. Therefore some crews must change aircrafts, which is an undesired operation. This paper presents a mathematical formulation based on a binary variable for each potential crew and aircraft route, and describes a column-generation algorithm for obtaining heuristic solutions. Computational results on real-world instances are given and compared to manual solutions by the airline.