Hub relay network design for daily driver routes

Hub-based relay networks for long haul trucking offer an opportunity to improve the work–life balance of drivers while simultaneously supporting faster delivery through near-continuous flow of containers from source to destination. In this paper, we develop a model for deciding hub location and sizing along with the routing of loads. Costs of hub construction and operation, transportation and penalties for multi-day driver trips are included. Both deterministic and two-stage stochastic programming models have been formulated in this paper. The goal is to determine the optimal hub and route decisions so that overall cost is minimised. A case study on the highway network for the Western United States demonstrates the computational tractability of the approach along with the importance of considering demand uncertainty.     

A two-dimensional bin-packing problem with conflict penalties

In this paper, we address the two-dimensional bin-packing (2BP) problem with variable conflict penalties, which incur if conflicting items are loaded into the same bin. Such a problem is observed in applications such as supermarket chains and automobile components transportation. The problem not only focuses on minimisation of number of bins used, but also deals with the conflict penalties at the same time. We propose a heuristic method based on the IMA algorithm and adapt it to solve this problem. A local search procedure is also designed to further improve the solutions. For instances derived from benchmark test data, the computational results indicate that the adapted IMA heuristic algorithm with local search effectively balances the number of bins used and the conflict penalties. The algorithm outperforms several adapted approaches that are well known for the 2BP problems.     

Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems

It has been well established that to find an optimal or near-optimal solution to job shop scheduling problems (JSSPs), which are NP-hard, one needs to harness different features of many techniques, such as genetic algorithms (GAs) and tabu search (TS). In this paper, we report usage of such a framework which exploits the diversified global search and the intensified local search capabilities of GA and TS, respectively. The system takes its input directly from the process information in contrast to having a problem-specific input format, making it versatile in dealing with different JSSP. This framework has been successfully implemented to solve industrial JSSPs. In this paper, we evaluate its suitability by applying it on a set of well-known job shop benchmark problems. The results have been variable. The system did find optimal solutions for moderately hard benchmark problems (40 out of 43 problems tested). This performance is similar to, and in some cases better than, comparable systems, which also establishes the versatility of the system. However for the harder benchmark problems it had difficulty in finding a new improved solution. We analyse the possible reasons for such a performance.     

Heuristics for the generalised assignment problem: simulated annealing and tabu search approaches

The generalised assignment problem (GAP) is the problem of finding a minimum cost assignment of a set of jobs to a set of agents. Each job is assigned to exactly one agent. The total demands of all jobs assigned to any agent can not exceed the total resources available to that agent. A review of exact and heuristic methods is presented. A-generation mechanism is introduced. Different search strategies and parameter settings are investigated for the-generation descent, hybrid simulated annealing/tabu search and tabu search heuristic methods. The developed methods incorporate a number of features that have proven useful for obtaining optimal and near optimal solutions. The effectiveness of our approaches is established by comparing their performance in terms of solution quality and computional requirement to other specialized branch-and-bound tree search, simulated annealing and set partitioning heuristics on a set of standard problems from the literature.     

面向多处理器SoC设计的低功耗软硬件划分

提出了解决多处理器SoC的低功耗软硬件划分问题的方法--基于神经网络的禁忌搜索算法.其基本思想是:真实的生物神经元具有抑制重复激活的阻尼特性,这与禁忌搜索对重复搜索加以限制相类似,因此设计具有阻尼特性的神经网络实现禁忌搜索算法,受阻尼特性抑制的神经元对应禁忌活动.由于神经网络复杂的动态特性和禁忌搜索优秀的全局搜索能力,该算法能够有效地跳出局部最优解.对真实任务图的实验表明,与遗传算法相比,该算法不但具有搜索速度上的优势,而且所得到的绝大部分软硬件划分方案有更低的系统功耗.     

Evolutionary algorithms applied to reliable communication network design

Several evolutionary algorithms (EAs) applied to a wide class of communication network design problems modelled under the generalized Steiner problem (GSP) are evaluated. In order to provide a fault-tolerant design, a solution to this problem consists of a preset number of independent paths linking each pair of potentially communicating terminal nodes. This usually requires considering intermediate non-terminal nodes (Steiner nodes), which are used to ensure path redundancy, while trying to minimize the overall cost. The GSP is an NP-hard problem for which few algorithms have been proposed. This article presents a comparative study of pure and hybrid EAs applied to the GSP, codified over MALLBA, a general purpose library for combinatorial optimization. The algorithms were tested on several GSPs, and asset efficient numerical results are reported for both serial and distributed models of the evaluated algorithms.     

Optimization of truss topology using tabu search

A design procedure for integrating topological considerations in the framework of structural optimization is presented. The proposed approach is capable of considering multiple load conditions, stress, displacement and local/global buckling constraints, and multiple objective functions in the problem formulation. Further, since the proposed method permits members to be added to or deleted from an existing topology and the topology is not defined by member areas, the difficulty of not being able to reach singular optima is also avoided. These objectives are accomplished using a discrete optimization procedure which uses 0–1 topological variables to optimize alternate designs. Since the topological variables are discrete in nature and the member cross-sections are assumed to be continuous, the topological optimization problem has mixed discrete-continuous variables. This non-linear programming problem is solved using a memory-based combinatorial optimization technique known as tabu search. Numerical results obtained using tabu search for single and multiobjective topological optimization of truss structures are presented. To model the multiple objective functions in the problem formulation, a cooperative game theoretic approach is used. The results indicate that the optimum topologies obtained using tabu search compare favourably, and in some instances, outperform the results obtained using the ground–structure approach. However, this improvement occurs at the expense of a significant increase in computational burden owing to the fact that the proposed approach necessitates that the geometry of each trial topology be optimized.     

Particle-swarm harmony search for water network design

The optimal design of water distribution networks is a non-linear, multi-modal, and constrained problem classified as an NP-hard combinatorial problem. Because of the drawbacks of calculus-based algorithms, the problem has been tackled by assorted stochastic algorithms, such as the genetic algorithm, simulated annealing, tabu search, shuffled frog-leaping algorithm, ant colony optimization algorithm, harmony search, cross entropy, and scatter search. This study proposes a modified harmony search algorithm incorporating particle swarm concept. This algorithm was applied to the design of four bench-mark networks (two-loop, Hanoi, Balerma, and New York City networks), with good results.     

Applying tabu search and simulated annealing to the optimal design of sewer networks

Optimizations of sewer network designs create complicated and highly nonlinear problems wherein conventional optimization techniques often get easily bogged down in local optima and cannot successfully address such problems. In the past decades, heuristic algorithms possessing robust and efficient global search capabilities have helped to solve continuous and discrete optimization problems and have demonstrated considerable promise. This study applied tabu search (TS) and simulated annealing (SA) to the optimization of sewer network designs. For a case study, this article used the sewer network design of a central Taiwan township, which contains significantly varied elevations, and the optimal designs from TS and SA were compared with the original official design. The results show that, in contrast with the original design's failure to satisfy the minimum flow-velocity requirements, both TS and SA achieved least-cost solutions that also fulfilled all the constraints of the design criteria. According to the average performance of 200 trials, SA outperformed TS in both robustness and efficiency for solving sewer network optimization problems.     

A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem

Solving optimization problems with multiple objectives under uncertainty is generally a very difficult task. Evolutionary algorithms, particularly genetic algorithms, have shown to be effective in solving this type of complex problems. In this paper, we develop a simulation-based multi-objective genetic algorithm (SMOGA) procedure to solve the build-operate-transfer (BOT) network design problem with multiple objectives under demand uncertainty. The SMOGA procedure integrates stochastic simulation, a traffic assignment algorithm, a distance-based method, and a genetic algorithm (GA) to solve a multi-objective BOT network design problem formulated as a stochastic bi-level mathematical program. To demonstrate the feasibility of SMOGA procedure, we solve two mean-variance models for determining the optimal toll and capacity in a BOT roadway project subject to demand uncertainty. Using the inter-city expressway in the Pearl River Delta Region of South China as a case study, numerical results show that the SMOGA procedure is robust in generating ‘good’ non-dominated solutions with respect to a number of parameters used in the GA, and performs better than the weighted-sum method in terms of the quality of non-dominated solutions.     

Strategic network planning for an international automotive manufacturer

This article addresses the strategic network planning for international automotive manufacturers, in particular of premium cars. The focus is on the product to plant allocation and capacity expansion decisions for a given network design with fixed plant locations. A mixed integer program minimizing the net present value (NPV) of all capital expenditures and operational cost while incorporating flexibility of a network by a specific allocation structure (“chain”) is formulated. Computational illustrations on the influence of flexible allocation structures on the NPV are demonstrated considering changes in demand, exchange rates and total available capacity.     

New Tabu search heuristics for the dynamic facility layout problem

A manufacturing facility is a dynamic system that constantly evolves due to changes such as changes in product demands, product designs, or replacement of production equipment. As a result, the dynamic facility layout problem (DFLP) considers these changes and is defined as the problem of assigning departments to locations during a multi-period planning horizon such that the sum of the material handling and re-arrangement costs is minimised. In this paper, three tabu search (TS) heuristics are presented for this problem. The first heuristic is a simple TS heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic TS heuristic. To test the performances of the heuristics, two sets of test problems from the literature are used in the analysis. The results show that the second heuristic out-performs the other proposed heuristics and the heuristics available in the literature.     

A tabu‐search‐based algorithm for continuous multiminima problems

Tabu search algorithms are becoming very popular in operational research community. A lot of works and studies were carried out from the first presentation of Glover. The development of tabu search techniques concerns in almost all cases combinatorial problems, and we found very few papers about continuous problems. In this work, we briefly classify and describe the main continuous approaches to tabu search, then we will present a novel algorithm which explores a grid of points with a distance dynamically defined, it collapses to a local minimum then it continues the search from that point accepting some non‐improving points to allow the exploration of new regions of the domain. The proposed algorithm is deterministic with a little random component triggered only when loop conditions are detected and it contains a simple vocabulary building mechanism and a diversification procedure. Finally we show some comparisons with other optimization algorithms and a possible application of this method to an engineering problem. Copyright © 2001 John Wiley & Sons, Ltd.     

A combined global and local search method to deal with constrained optimization for continuous tabu search

Heuristic methods, such as tabu search, are efficient for global optimizations. Most studies, however, have focused on constraint‐free optimizations. Penalty functions are commonly used to deal with constraints for global optimization algorithms in dealing with constraints. This is sometimes inefficient, especially for equality constraints, as it is difficult to keep the global search within the feasible region by purely adding a penalty to the objective function. A combined global and local search method is proposed in this paper to deal with constrained optimizations. It is demonstrated by combining continuous tabu search (CTS) and sequential quadratic programming (SQP) methods. First, a nested inner‐ and outer‐loop method is presented to lead the search within the feasible region. SQP, a typical local search method, is used to quickly solve a non‐linear programming purely for constraints in the inner loop and provides feasible neighbors for the outer loop. CTS, in the outer loop, is used to seek for the global optimal. Finally, another local search using SQP is conducted with the results of CTS as initials to refine the global search results. Efficiency is demonstrated by a number of benchmark problems. Copyright © 2008 John Wiley & Sons, Ltd.     

Optimisation design of attribute control charts for multi-station manufacturing system subjected to quality shifts

The qualities of products are a major concern in any production system; thus implementing efficient inspection policies is of great importance to reduce quality-related costs. This article addresses the problem of finding optimal inspection policies for the multi-station manufacturing system (MMS) subjected to quality shifts to minimise total quality-related cost. Each station of the MMS may stay at either in-control condition or out-of-control condition, which may lead to different nonconforming product rates. Markov chain method is used to calculate the steady-state probability distribution (SSPD). Based on the SSPD, the cost structure of this MMS is analysed. The economical optimisation model of attribute control charts (ACCs) is then established, in which the decision variables are the control chart parameters: sampling interval, sample size and control limit. The ACCs optimisation model is resolved by the proposed integrated algorithm combining heuristic rule and tabu search. This approach is verified through an application case taken from a mobile phone shell production company. The results of comparative analysis show that the proposed model is much more economical than both the current outgoing inspection strategy and the regular np control chart. The sensitivity analysis of four input parameters is also conducted.     

Tabu search for the job-shop scheduling problem with multi-purpose machines

In this paper we study the following generalization of the job-shop scheduling problem. Each operation can be performed by one machine out of a set of machines given for this operation. The processing time does not depend on the machine which has been chosen for processing the operation. This problem arises in the area of flexible manufacturing. As a generalization of the jobshop problem it belongs to the hardest problems in combinatorial optimization. We show that an application of tabu search techniques to this problem yields excellent results for benchmark problems.Supported by Deutsche Forschungsgemeinschaft, Project JoP-TAG     

A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem

The problem that we consider in this article is a flexible job shop scheduling problem issued from the printing and boarding industry. Two criteria have to be minimised, the makespan and the maximum lateness. Two tabu search algorithms are proposed for finding a set of non-dominated solutions: the first is based on the minimisation of one criterion subject to a bound on the second criterion (ε-constraint approach) and the second is based on the minimisation of a linear combination of criteria. These algorithms are tested on benchmark instances from the literature and the results are discussed. The total tardiness is considered as a third criterion for the second tabu search and results are presented and discussed.     

基于连续函数优化的禁忌搜索算法

提出了一种连续禁忌搜索算法,用于求解连续函数优化问题.邻域规则及禁忌规则是禁忌搜索算法的核心,针对连续函数解空间的连续性,提出了一种邻域分割法来进行邻域搜索,并对禁忌规则进行了设计.通过经典函数测试可以看出,禁忌搜索算法在连续函数优化问题中显示出很强的"爬山"能力,优化结果与实际最优值非常接近,是一种有效的全局优化算法.     

集装箱车辆调度问题的变邻域禁忌搜索算法

研究一类带工作时间约束的集装箱专用车辆调度问题的混合禁忌搜索算法.此问题可分解为车辆路线设定和车辆分配两个组合优化问题,但是两个问题的分开求解最优解的组合却并不一定是总问题的最优解.首先对问题给出数学描述,之后通过引入一个变邻域搜索策略,提出一个解决该问题的混合禁忌搜索算法.该算法使用两行向量进行编码,采用随机扩大禁忌步长,并设计三种邻域变换定义,采用变邻域策略来扩大搜索空间.最后通过对6个不同规模算例求解验证该算法在解决此类问题的有效性.