Solving Hierarchical Constraints over Finite Domains with Local Search

Many real world problems have requirements and constraints which conflict with each other. One approach for dealing with such over-constrained problems is with constraint hierarchies. In the constraint hierarchy framework, constraints are classified into ranks, and appropriate solutions are selected using a comparator which takes into account the constraints and their ranks. In this paper, we present a local search solution to solving hierarchical constraint problems over finite domains (HCPs). This is an extension of local search for over-constrained integer programs WSAT(OIP) to constraint hierarchies and general finite domain constraints. The motivation for this work arose from solving large airport gate allocation problems. We show how gate allocation problems can be formulated as HCPs using typical gate allocation constraints. Using the gate allocation benchmarks, we investigate how constraint heirarchy selection strategies and the problem formulation using two models: a 0–1 linear constraint hierarchy model and a nonlinear finite domain constraint hierarchy model.     

Evolutionary Optimization of File Assignment for a Large-Scale Video-on-Demand System

We present a genetic algorithm for tackling a file assignment problem for a large-scale video-on-demand system. The file assignment problem is to find the optimal replication and allocation of movie files to disks so that the request blocking probability is minimized subject to capacity constraints. We adopt a divide-and-conquer strategy, where the entire solution space of file assignments is divided into subspaces. Each subspace is an exclusive set of solutions sharing a common file replication instance. This allows us to utilize a greedy file allocation method for finding a good-quality heuristic solution within each subspace. We further design two performance indices to measure the quality of the heuristic solution on 1.) its assignment of multicopy movies and 2.) its assignment of single-copy movies. We demonstrate that these techniques, together with ad hoc population handling methods, enable genetic algorithms to operate in a significantly reduced search space and achieve good-quality file assignments in a computationally efficient way.     

复合类别航站楼分配问题的改进和声搜索算法

随着航空运输业的蓬勃发展,如何在硬件条件受限的情况下尽量提高机场的运行效率来满足日益增长的航班起降需求,日益受到关注.为了对机场航站楼登机门分配问题进一步优化,提出一种考虑登机门复合类别的航站楼分配问题,并建立数学模型,描述在航线类别、班机型号以及最短停靠间隔对于登机门选取的约束下,带有临时停机坪辅助的登机门分配优化问题.在模型经过精确算法验证的基础上,为适应登机门问题特性并求解中大规模问题,首次引进和声搜索算法,增加复杂约束条件,对编码解码、初始解产生以及寻优过程进行改进,提出一种更高效的改进和声搜索算法对模型进行求解.通过使用Lingo软件和Matlab软件对中小规模算例分别进行精确求解和智能算法求解,对比表明所提出智能算法的有效性、全局搜索能力以及求解效率.再通过对大规模问题的求解,表明所提出算法在现有条件下能够减小转机旅客的总转机路程,取得了较好的效果.     

Data mining based storage assignment heuristics for travel distance reduction

Among the warehousing activities in distribution centres, order picking is the most time‐consuming and labour‐intensive. As a result, order picking may become a bottleneck preventing distribution centres from maximizing the effectiveness of their warehousing activities. Although storage location assignment (or product allocation) is a tactical decision, it is especially influential on the effectiveness of order picking. In previous studies, most storage assignment approaches considered the order frequency of individual products rather than that of product groups, which often are purchased together. This paper proposes a new association measure, weighted support count (WSC), based on association rule mining, to represent both the intensity and nature of the relationships between products in a distribution centre. This paper presents two storage assignment heuristics, the modified class‐based heuristic (MCBH) and the association seed based heuristic (ASBH), designed to facilitate efficient order picking by applying WSC. The real‐world data set of a grocery distribution centre is used to verify the effectiveness of the proposed approaches. From the computational results, MCBH cuts at most 4% from the travel distance for order picking per month, as compared with the traditional class‐based approach. Meanwhile, ASBH achieves at most a 13% reduction in travel distance.     

A two-phase heuristic evolutionary algorithm for personalizing course timetables: a case study in a Spanish university

This paper presents, as a case study, the application of a two-phase heuristic evolutionary algorithm to obtain personalized timetables in a Spanish university. The algorithm consists of a two-phase heuristic, which, starting from an initial ordering of the students, allocates students into groups, taking into account the student's preferences as a primal factor for the assignment. An evolutionary algorithm is then used in order to select the ordering of students which provides the best assignment.The algorithm has been tested in a real problem, the timetable of the Telecommunication Engineering School at Universidade de Vigo (Spain), and has shown good performance in terms of the number of constraints fulfilled and groups assigned to students.     

Theoretical aspects of multicriteria flight gate scheduling: deterministic and fuzzy models

This paper addresses the airport flight gate scheduling problem with multiple objectives. The objectives are to maximize the total flight gate preferences, to minimize the number of towing activities, and to minimize the absolute deviation of the new gate assignment from a so-called reference schedule. The problem examined is a multicriteria multi-mode resource-constrained project scheduling problem with generalized precedence constraints or time windows. While in previous approaches the problem has been simplified to a single objective counterpart, we tackle it directly by a multicriteria metaheuristic, namely Pareto Simulated Annealing, in order to get a representative approximation of the Pareto front. Possible uncertainty of input data is treated by means of fuzzy numbers.     

CSPs with counters: a likelihood-based heuristic

Abstract. Counter constraints are a naturalrepresentation of constraints on the finite capacity of resources in resource-allocation type problems. They are a generic family of non-binary constraints that limit the number of variables that may be assigned particular values. Counter constraints can be represented by binary constraints, at a cost. We analyse the cost, show how a counter can be represented as a linear number of binary constraints, and demonstrate empirically that even with the optimal reduction,an explicit representation of counters is preferable to their representation as a set of binary constraints. For counter constraints, value ordering is essential. An heuristic for value ordering on constraint satisfaction problems (CSP), based on the estimated likelihoodof a solution, is presented. The proposed value ordering heuristic is useful for counter constraints, as well as for binary CSPs, where it can be used to approximate the number of solutions consistent with a particular value assignment to a variable. The proposed value ordering heuristic integrates counter constraints with binary constraint networks in a novel manner. Counter constraints are problematic for most heuristics, which are local in scope, yet we demonstrated empirically that the proposed value ordering heuristic is significantly superior to heuristics used in previous work.     

A knowledge-based airport gate assignment system integrated with mathematical programming

Airport gate assignment is the process of selecting and allocating aircraft to gates to create an assignment schedule, and it is one of the major functions of airport operations. With the increase of passenger traffic volumes and the number of flights, the complexity of this task and the factors to be considered have increased significantly, and efficient gate utilization has received considerable attention. This paper proposes a knowledge-based airport gate assignment system integrated with mathematical programming techniques to provide a solution that satisfies both static and dynamic situations within a reasonable computing time. A partial parallel assignment is introduced, which considers a group of aircraft and looks at all the available gates and then does the gate assignments by optimizing a multi-objective function. For the validation of the proposed approach, an example is used as a case study, and a prototype system with various functions has been developed in a microcomputer environment.     

Planning with Multistep Forward Search with Forced Goal‐Ordering Constraints

To solve a real‐world planning problem with interfering subgoals, it is essential to perform early detection of subgoal dependencies and achieve the subgoals in the correct order. This is also the case for planning problems with forced goal‐ordering (FGO) constraints. In automated planning, forward search with FGO constraints has been proposed many times over the years, but there are still major difficulties in realizing these FGOs in plan generation. Many existing methods such as goal agenda manager and ordered landmarks cannot detect the FGOs accurately, and thus, the undiscovered ordering relationship may cause the forward search to suffer from deadlocks. In this article, we put forward an approach via an effective search heuristic to constrain a planner to satisfy the FGOs. We make use of an atomic goal‐achievement graph in a look‐ahead search under the FGO constraints. This allows a forward search strategy to plan forward efficiently in multiple steps toward a goal state along a search path. Experimental results illustrate that, by avoiding deadlocks, we can solve more benchmark planning problems more efficiently than previous approaches. We also prove several formal properties for search that are related to FGO detection.     

Improved assignment with ant colony optimization for multi-target tracking

Detecting and tracking ground targets is crucial in military intelligence in battlefield surveillance. Once targets have been detected, the system used can proceed to track them where tracking can be done using Ground Moving Target Indicator (GMTI) type indicators that can observe objects moving in the area of interest. However, when targets move close to each other in formation as a convoy, then the problem of assigning measurements to targets has to be addressed first, as it is an important step in target tracking. With the increasing computational power, it became possible to use more complex association logic in tracking algorithms. Although its optimal solution can be proved to be an NP hard problem, the multidimensional assignment enjoyed a renewed interest mostly due to Lagrangian relaxation approaches to its solution. Recently, it has been reported that randomized heuristic approaches surpassed the performance of Lagrangian relaxation algorithm especially in dense problems. In this paper, impelled from the success of randomized heuristic methods, we investigate a different stochastic approach, namely, the biologically inspired ant colony optimization to solve the NP hard multidimensional assignment problem for tracking multiple ground targets.     

Robust assignment of airport gates with operational safety constraints

This paper reviews existing approaches to the airport gate assignment problem (AGAP) and presents an optimization model for the problem considering operational safety constraints. The main objective is to minimize the dispersion of gate idle time periods (to get robust optimization) while ensuring appropriate matching between the size of each aircraft and its assigned gate type and avoiding the potential hazard caused by gate apron operational conflict. Genetic algorithm is adopted to solve the problem. An illustrative example is given to show the effectiveness and efficiency of the algorithm. The algorithm performance is further demonstrated using data of a terminal from Beijing Capital International Airport (PEK).     

Stochastic resource allocation using a predictor-based heuristic for optimization via simulation

Some combinatorial stochastic resource allocation problems lack algebraically defined objective functions and hence require optimization via simulation as a mechanism for obtaining good solutions. For this class of problems, we propose a new predictor-based heuristic that uses a distance criterion to perform the solution search. To demonstrate our solution approach, we apply this heuristic to the problem of selecting the proper design configuration of an unmanned aerial system (UAS) fleet so as to maximize mission effectiveness. We compare our approach to black box optimization via simulation approaches (two tabu search-based procedures and a greedy heuristic) and glean both methodological and practical insights.     

A novel hybrid tabu search approach to container loading

The container loading problem, which is significant for a number of industrial sectors, aims to obtain a high space utilisation in the container while satisfying practical constraints. This paper presents a novel hybrid tabu search approach to the container loading problem. A loading heuristic is devised to incorporate heuristic strategies with a handling method for remaining spaces to generate optimal loading arrangements of boxes with stability considered. The tabu search technique, which covers the encoding, evaluation criteria and configuration of neighbourhood and candidate solutions, is used to improve the performance of the loading heuristic. Experimental results with benchmark data show that the hybrid approach provides a better space utilisation than the published approaches under the condition of all loaded boxes with one hundred percent support from below. Moreover, it is shown that the hybrid tabu search can solve problems with the constraints of weight limit and weight distribution with real world data.     

A sensitivity analysis of solving joint replenishment problems using the RAND method under inaccurate holding cost estimates and demand forecasts

This paper presents a study of solving the joint replenishment problem (JRP) by using the RAND method, a heuristic approach that has been proven to find almost as good as optimal solutions, under uncertain customer demands and inaccurate unit holding cost estimation. The classical JRP deals with the issue of determining a replenishment policy that minimizes the total cost of replenishing multiple products from a single supplier. The total cost considered in the JRP consists of a major ordering cost independent of the number of items in the order, a minor ordering cost depending on the items in the order, and the holding cost. There have been many heuristic approaches proposed for solving the JRP. Most of the research work was done under the assumptions that the demand for each item type and the unit holding cost are known and constant. However, in the real world accurately forecasting customer demands and precisely estimating the unit holding cost are both difficult. Besides, the real values of the demands and the unit holding cost may change over the replenishment horizon. The present study addresses the issue of the uncertain demands and the unit holding cost to the JRP and investigates how misestimates of these demands and holding costs may influence the replenishment policy as determined by the famous JRP heuristic, the RAND method.     

Considering inter-task resource constraints in task allocation

This paper focuses on task allocation with single-task robots, multi-robot tasks and instantaneous assignment, which has been shown to be strongly NP-hard. Although this problem has been studied extensively, few efficient approximation algorithms have been provided due to its inherent complexity. In this paper, we first provide discussions and analyses for two natural greedy heuristics for solving this problem. Then, a new greedy heuristic is introduced, which considers inter-task resource constraints to approximate the influence between different assignments in task allocation. Instead of only looking at the utility of the assignment, our approach computes the expected loss of utility (due to the assigned robots and task) as an offset and uses the offset utility for making the greedy choice. A formal analysis is provided for the new heuristic, which reveals that the solution quality is bounded by two different factors. A new algorithm is then provided to approximate the new heuristic for performance improvement. Finally, for more complicated applications, we extend this problem to include general task dependencies and provide a result on the hardness of approximating this new formulation. Comparison results with the two natural heuristics in simulation are provided for both formulations, which show that the new approach achieves improved performance.     

Breakout local search for the multi-objective gate allocation problem

The problem of assigning gates to arriving and departing flights is one of the most important problems in airport operations. We take into account the real multi-criteria nature of the problem by optimizing a total of nine gate allocation objectives that are oriented both on convenience for airport/airline services and passenger comfort. As far as we are aware, this is the largest number of objectives jointly optimized in the GAP literature. Given the complexity of the considered problem, we propose a heuristic approach based on the Breakout Local Search (BLS) framework. BLS is a recent variant of the Iterated Local Search (ILS) with a particular focus on the perturbation strategy. Based on some relevant information on search history, it tries to introduce an appropriate degree of diversification by determining adaptively the number and type of moves for the next perturbation phase. Moreover, we use a new memory-based greedy constructive heuristic to generate a starting point for BLS. Benchmark instances used for our experiments and comparisons are based on information provided by Manchester Airport.     

民用机场停机位优化配置计算机仿真

停机位配置指为到港或离港航班指定适宜的登机口,确保航班正点。航班停机位的高效、合理安排是机场地面作业中的一项核心任务。在系统分析国内繁忙机场停机位配置情况的基础上进行计算机仿真,模拟给出停机位优化配置。同时考虑旅客登转机时间(旅客满意度)、机型与停机位类型匹配(机场效益)等优化目标。系统运行稳定,效率高。     

Study on an improved adaptive PSO algorithm for solving multi-objective gate assignment

Gate is a key resource in the airport, which can realize rapid and safe docking, ensure the effective connection between flights and improve the capacity and service efficiency of airport. The minimum walking distances of passengers, the minimum idle time variance of each gate, the minimum number of flights at parking apron and the most reasonable utilization of large gates are selected as the optimization objectives, then an efficient multi-objective optimization model of gate assignment problem is proposed in this paper. Then an improved adaptive particle swarm optimization(DOADAPO) algorithm based on making full use of the advantages of Alpha-stable distribution and dynamic fractional calculus is deeply studied. The dynamic fractional calculus with memory characteristic is used to reflect the trajectory information of particle updating in order to improve the convergence speed. The Alpha-stable distribution theory is used to replace the uniform distribution in order to escape from the local minima in a certain probability and improve the global search ability. Next, the DOADAPO algorithm is used to solve the constructed multi-objective optimization model of gate assignment in order to fast and effectively assign the gates to different flights in different time. Finally, the actual flight data in one domestic airport is used to verify the effectiveness of the proposed method. The experiment results show that the DOADAPO algorithm can improve the convergence speed and enhance the local search ability and global search ability, and the multi-objective optimization model of gate assignment can improve the comprehensive service of gate assignment. It can effectively provide a valuable reference for assigning the gates in hub airport.     

Airport Gate Scheduling with Time Windows

In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Although we minimize walking distances (or travel time) in our objective function, the model is easily adapted for other material handling costs including baggage and cargo costs. Our objectives are achieved through gate assignments, where time slots alloted to aircraft at gates deviate from scheduled slots minimally. Further, the model can be applied to cross-docking optimization in areas other than airports, such as freight terminals where material arrival times (via trucks, ships) can fluctuate. The solution approach uses insert and interval exchange moves together with a time shift algorithm. We then use these neighborhood moves in Tabu Search and Memetic Algorithms. Computational results are provided and verify that our heuristics work well in small cases and much better in large cases when compared with CPLEX solver.     

A heuristic manipulation technique for the sequential ordering problem

The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are respected, and the objective is to find a feasible solution with minimum cost.The sequential ordering problem models many real-world applications, mainly in the fields of transportation and production planning.A problem manipulation technique to be used in conjunction with heuristic algorithms is discussed. The aim of the technique is to make the search space associated with each problem more attractive for the underlying heuristic algorithms.This novel methodology is tested in combination with the state-of-the-art method for the sequential ordering problem. Improved results are obtained, particularly for the largest problems considered.