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 Tabu Search Algorithm for application placement in computer clustering

This paper presents and analyzes a model for the problem of placing applications on computer clusters (APP). In this problem, organizations requesting a set of software applications have to be assigned to computer clusters such that the costs of opening clusters and installing the necessary applications are minimized. This problem is related to known OR problems such as the multiproduct facility location problem and the generalized bin packing problem. We show that APP is NP-hard, and then propose a simple Tabu Search heuristic to solve it. The performance of the Tabu Search heuristic is assessed via extensive computational experiments, which indicate the promise of the proposed Tabu Search.     

Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU

General-purpose computing on graphics processing unit (GPGPU) has been adopted to accelerate the running of applications which require long execution time in various problem domains. Tabu Search belonging to meta-heuristics optimization has been used to find a suboptimal solution for NP-hard problems within a more reasonable time interval. In this paper, we have investigated in how to improve the performance of Tabu Search algorithm on GPGPU and took the permutation flow shop scheduling problem (PFSP) as the example for our study. In previous approach proposed recently for solving PFSP by Tabu Search on GPU, all the job permutations are stored in global memory to successfully eliminate the occurrences of branch divergence. Nevertheless, the previous algorithm requires a large amount of global memory space, because of a lot of global memory access resulting in system performance degradation. We propose a new approach to address the problem. The main contribution of this paper is an efficient multiple-loop struct to generate most part of the permutation on the fly, which can decrease the size of permutation table and significantly reduce the amount of global memory access. Computational experiments on problems according with benchmark suite for PFSP reveal that the best performance improvement of our approach is about 100%, comparing with the previous work.     

Operation assignment and capacity allocation problem in automated manufacturing systems

We address an operation assignment and capacity allocation problem that arises in semiconductor industries and flexible manufacturing systems. We assume the automated machines have scarce time and tool magazine capacities and the tools are available in limited quantities. The aim is to select a subset of operations with maximum total weight. We show that the problem is NP-hard in the strong sense, develop two heuristics and a Tabu Search procedure. The results of our computational tests have revealed that our Tabu Search procedure produces near optimal solutions very quickly.     

基于TS的动态车辆调度问题的混合算法研究

对带时间窗的动态车辆调度问题进行分析,采用实时再优化方法进行研究,引入时间轴概念,建立动态车辆调度模型,并给出求解的混合禁忌搜索算法。该算法先用C-K节约算法求得初始解,然后用禁忌搜索进行优化,得到全局最优解。禁忌搜索算法中采用动态邻域移动方法构造候选解和动态禁忌长度选取策略设置紧急长度,提高算法的收敛速度。最后用实例证明该混合算法的可行性和有效性。     

A multi-start tabu search method for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times

In this paper we study a problem of sequencing jobs in a machine with programmed preventive maintenance and sequence-dependent set-up times. The problem combines two NP-hard problems, so we propose a heuristic method for solving it, which hybridizes multi-start strategies with Tabu Search. We compare our method with the only published metaheuristic algorithm for this problem on a set of 420 instances. The comparison favors the method developed in this work, showing that is able to find high quality solutions in very short computational times.     

A Tabu Search algorithm for dynamic routing in ATM cell-switching networks

This paper deals with the dynamic routing problem in ATM cell-switching networks. We present a mathematical programming model based on cell loss and a Tabu Search algorithm with short-term memory that is reinforced with a long-term memory procedure. The estimation of the quality of the solutions is fast due to the specific encoding of the feasible solutions. The Tabu Search algorithm reaches good quality solutions outperforming other approaches such as Genetic Algorithms and the Minimum Switching Path heuristic attending both to the cell loss and the CPU time consumption. The best results were found for the more complex networks with a high number of switches and links.     

Pharmacy duty scheduling problem

In this study, we define the pharmacy duty scheduling problem, which requires a subset of pharmacies to be on duty on national holidays, at weekends, and at nights, in order to be able to satisfy the emergency medicine needs. We model the pharmacy duty scheduling problem as a multiperiod p‐median problem with special side constraints, and analyze the computational complexity. We propose a Tabu Search heuristic and develop lower bound (LB) algorithms. We test the performance of mathematical models, Tabu Search heuristic, and the LBs on randomly generated instances. We analyze the current system in ?zmir, the third largest city in Turkey, with a population of 3.5 million, and apply solution methods. Our results show that the proposed Tabu Search algorithm suggests improvements on the current system.     

A heuristic optimization approach for multi-vehicle and one-cargo green transportation scheduling in shipbuilding

To actively respond to the call for green shipbuilding, block cooperative transportation has been particularly concerned in reducing carbon emission in the shipyard, and hence a “multi-vehicle and one-cargo” (MVOC) green transportation scheduling problem emerges. Aiming to solve this problem effectively and improve transportation efficiency and reduce energy consumption, a bi-objective mathematical model combined routing model with synchronization constraints is proposed to simultaneously minimize non-value-added transportation time cost and total CO₂ emission. A Pareto-based multi-objective Tabu Search (MOTS) algorithm is then designed to solve the model, in which local improvements are developed to generate promising neighboring individuals. Experimental results show that the proposed MOTS algorithm can effectively solve the problem even on a large scale and outperform the classic algorithm of nondominated sorting genetic algorithm-II (NSGA-Ⅱ). It is hoped that this work enables an operation mode with high efficiency and low energy consumption and provides useful insights for flatcar transportation scheduling operators in the shipyard.     

Probabilistic GRASP-Tabu Search algorithms for the UBQP problem

This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by introducing a population management strategy. Both algorithms are based on a dedicated randomized greedy construction heuristic and a tabu search procedure. We show extensive computational results on two sets of 31 large random UBQP instances and one set of 54 structured instances derived from the MaxCut problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able to improve the previous best known results for 19 MaxCut instances.     

An Evolutionary Parallel Tabu Search approach for distribution systems reinforcement planning

In this paper a new meta-heuristic optimisation technique is proposed. The method is based on the Parallel Tabu Search (PTS) algorithm and the application is the optimal electrical distribution systems reinforcement planning through the installation of photovoltaic plants, parallel cables, capacitor banks and transformers. The issue is a combinatorial optimisation problem; the objective function is a non-linear expression of a large number of variables. In these cases, meta-heuristics have proved to work well and one of the most efficient is the Tabu Search algorithm. For large-scale problems, parallelisation improves Tabu Search computational efficiency as well as its exploration ability. In this paper, an enhanced version of PTS, Evolutionary Parallel Tabu Search (EPTS), is proposed. It performs reproduction operators on sub-neighbourhoods directing the search towards more promising areas of the search space. The problem of distribution systems reinforcement planning has been studied in detail and the results of the application show that the EPTS outperforms the PTS and Particle Swarm Optimisation algorithms.The algorithm's performance is also tested on mathematical test functions and other properties of the proposed algorithm are examined.     

有软时窗多车场开放式车辆路径及其禁忌搜索

有软时窗约束多车场开放式车辆路径问题是在基本的车辆路径问题上增加了时间窗约束和多车场作业的一种变化形式,是一个典型的NP-难问题。建立了问题模型,运用改进的禁忌搜索算法测试了算例。快速获得的高质量解验证了模型的正确性和算法性能的优良性。     

The time-dependent prize-collecting arc routing problem

A new problem is introduced named the Time-Dependent Prize-Collecting Arc Routing Problem (TD-PARP). It is particularly relevant to situations where a transport manager has to choose between a number of full truck load pick-ups and deliveries on a road network where travel times change with the time of day. Two metaheuristic algorithms, one based on Variable Neighborhood Search and one based on Tabu Search, are proposed and tested for a set of benchmark problems, generated from real road networks and travel time information. Both algorithms are capable of finding good solutions, though the VNS approach generally shows better performance.     

A note on the time travel approach for handling time windows in vehicle routing problems

In this paper, we identify two cases in which the proposition for calculating time window penalties presented in Nagata, Y., Bräysy, O. and Dullaert, W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research 2010;37(4): 724–37 yields incorrect results. We derive the corrected proposition and use numerical studies to show that a significant proportion of the evaluations performed by a Tabu Search for VRPTW falls under the two incorrect cases. Moreover, we demonstrate that the incorrect time window handling has a significant negative impact on the solution quality of the Tabu Search.     

定位—路线问题的遗传禁忌混合优化算法

研究了带软时间窗的定位—路线问题的遗传禁忌混合优化算法,该算法同时兼顾了定位—路线问题中的定位—配给和车辆路线安排两个子问题。给出的遗传算法与禁忌搜索算法的混合策略、遗传编码和相应的遗传操作方式,有效地提高了算法的求解效率和求解质量。最后,通过实验证明了算法的可行性和有效性。     

基于量子遗传混合算法的泊位联合调度

为了提高集装箱港口服务效率,减少船舶服务的拖期费用,针对港口硬件（泊位、拖轮、岸桥）既定条件下的拖轮-泊位联合调度问题,新建了以最小化总体船舶在港时间和总拖期时间为目标的数学模型,设计了一种混合算法进行求解。首先,分析确定了将量子遗传算法（QGA）和禁忌搜索（TS）算法进行串行混合的策略;然后,依据该联合调度问题特点,在解决算法实施中的关键技术问题（染色体结构设计和测量、遗传操作、种群更新等）的同时,采用了动态量子旋转门更新机制;最后,用生产实例验证了算法的可行性及有效性。算法实验结果表明,与人工调度结果相比,混合算法的总体船舶在港时间和总拖期时间分别减少了24%和42.7%;与遗传算法结果相比,分别减少了10.9%和22.5%。所提模型及算法不仅能为港口船舶的入泊、离泊和装卸作业环节提供优化作业方案,而且能增强港口竞争力。     

A GIS-Based Optimization Framework for Competitive Multi-Facility Location-Routing Problem

In a dynamic market setting, firms need to quickly respond to shifting demographics and economic conditions. In this paper, we investigate the problem of determining the optimum set of locations for a firm, which operates a chain of facilities under competition. We consider the objective of maximizing profit, defined as gross profit margin minus logistics costs. We propose a location-routing model where revenue is realized according to probabilistic patronization of customers and routing costs are incurred due to vehicles serving the open facilities from a central depot. We propose a hybrid heuristic optimization methodology for solving this model. The optimal locations are searched for by a Genetic Algorithm while an integrated Tabu Search algorithm is employed for solving the underlying vehicle routing problem. The solution approach is tested on a real dataset of a supermarket chain. The results show that the location decisions made by the proposed methodology lead to increased market share and profit margin, while keeping logistics costs virtually unchanged. Finally, we present a GIS-based framework that can be used to store, analyze and visualize all data as well as model solutions in geographic format.     

SVNTS算法的动态武器目标分配问题研究

动态武器目标分配(Weapon Target Assignment,WTA)问题是军事运筹学研究的重要理论问题,也是作战指挥决策中迫切需要解决的现实问题。运用约束规划方法建立了动态WTA问题的约束满足问题(ConstraintSatisfactionProb-lem,CSP)模型。提出了随机变邻域禁忌搜索(StochasticVariableNeighborhoodTabuSearch,SVNTS)算法对模型进行求解。与静态WTA模型相比,动态WTA模型通过时间优化以及匹配优化解决了武器射击时机问题,提高了武器利用效率。SVNTS算法运算速度快,解的质量基本令人满意,可用于解决较大规模的动态WTA问题。最后通过仿真实验,验证了模型和算法的有效性。     

跳跃逃逸算法优化模糊控制

提出一种智能启发式搜索算法:跳跃逃逸算法,该算法使搜索直接从局部极小中跳出,而不是像模拟退火、禁忌搜索等方法从局部极小中慢慢地爬出,因此该方法能更快、更有效地解决局部极小问题.模糊控制器的优化是一个复杂的问题,目前的优化方法通常需要人的经验或只针对某些特殊的给定模型.结合跳跃逃逸算法和局部连续模糊算法构成了自优化模糊计算机控制系统,其优化过程自动完成,无需人的经验且不依赖任何模型.仿真实验表明该系统效果良好.     

基于可变禁忌长度的优化停机位分配

针对机场"最大化停机位利用率"以及"最小化旅客行走路程"问题,提出了一种动态、灵活分配停机位的禁忌搜索算法。首先介绍了基本禁忌搜索算法的相关设计,然后引出了改进后的动态禁忌搜索算法（DTS算法）,最后利用实际数据对改进后的禁忌搜索算法进行演算。通过几组数据的对比可看出,突出可变禁忌长度能够缩短全局寻优的循环次数。而与相关文献的演算结果进行对比显示：在资源不受限情况下,旅客行走总时间减少了15.75%;在资源受限情况下,旅客行走总时间减少了22.84%。实验结果表明,采用动态禁忌搜索算法能够得到更小的旅客行走路程的分配方案。