Integrated optimization of location assignment and sequencing in multi-shuttle automated storage and retrieval systems under modified 2n-command cycle pattern

This article explores the integrated optimization problem of location assignment and sequencing in multi-shuttle automated storage/retrieval systems under the modified 2n-command cycle pattern. The decision of storage and retrieval (S/R) location assignment and S/R request sequencing are jointly considered. An integer quadratic programming model is formulated to describe this integrated optimization problem. The optimal travel cycles for multi-shuttle S/R machines can be obtained to process S/R requests in the storage and retrieval request order lists by solving the model. The small-sized instances are optimally solved using CPLEX. For large-sized problems, two tabu search algorithms are proposed, in which the first come, first served and nearest neighbour are used to generate initial solutions. Various numerical experiments are conducted to examine the heuristics’ performance and the sensitivity of algorithm parameters. Furthermore, the experimental results are analysed from the viewpoint of practical application, and a parameter list for applying the proposed heuristics is recommended under different real-life scenarios.     

A capacitated vehicle routing problem with order available time in e-commerce industry

In this article, a variant of the well-known capacitated vehicle routing problem (CVRP) called the capacitated vehicle routing problem with order available time (CVRPOAT) is considered, which is observed in the operations of the current e-commerce industry. In this problem, the orders are not available for delivery at the beginning of the planning period. CVRPOAT takes all the assumptions of CVRP, except the order available time, which is determined by the precedent order picking and packing stage in the warehouse of the online grocer. The objective is to minimize the sum of vehicle completion times. An efficient tabu search algorithm is presented to tackle the problem. Moreover, a Lagrangian relaxation algorithm is developed to obtain the lower bounds of reasonably sized problems. Based on the test instances derived from benchmark data, the proposed tabu search algorithm is compared with a published related genetic algorithm, as well as the derived lower bounds. Also, the tabu search algorithm is compared with the current operation strategy of the online grocer. Computational results indicate that the gap between the lower bounds and the results of the tabu search algorithm is small and the tabu search algorithm is superior to the genetic algorithm. Moreover, the CVRPOAT formulation together with the tabu search algorithm performs much better than the current operation strategy of the online grocer.     

Assembly block location and sequencing for flat transporters in a planar storage yard of shipyards

Assembly block location and sequencing are two important and related problems for scheduling a flat transporter to perform block storage and transport within a planar storage yard in shipyards. They affect not only the transport efficiency of storage yards but also the productivity and coordination of related workshops. This paper addresses the block location and sequencing at the same time with the purpose of reducing unproductive moves. A heuristic approach is proposed based on a sequencing strategy, a location selecting procedure for the incoming blocks and a policy for relocating blocks. A tabu search algorithm is proposed to improve the solution. Numerical experiments are conducted to validate the effectiveness and efficiency of the proposed approach.     

Mathematical modelling of container transfers and storage locations at seaport terminals

This paper models the seaport system with the objective of determining the optimal storage strategy and container-handling schedule. It presents an iterative search algorithm that integrates a container-transfer model with a container-location model in a cyclic fashion to determine both optimal locations and corresponding handling schedule. A genetic algorithm (GA), a tabu search (TS) and a tabu search/genetic algorithm hybrid are used to solve the problem. The implementation of these models and algorithms are capable of handling the very large problems that arise in container terminal operations. Different resource levels are analysed and a comparison with current practise at an Australian port is done.     

An implementation of the iterated tabu search algorithm for the quadratic assignment problem

In this paper, we describe an implementation of the iterated tabu search (ITS) algorithm for the quadratic assignment problem (QAP), which is one of the well-known problems in combinatorial optimization. The medium- and large-scale QAPs are not, to this date, practically solvable to optimality, therefore heuristic algorithms are widely used. In the proposed ITS approach, intensification and diversification mechanisms are combined in a proper way. The goal of intensification is to search for good solutions in the neighbourhood of a given solution, while diversification is responsible for escaping from local optima and moving towards new regions of the search space. In particular, the following enhancements were implemented: new formula for fast evaluation of the objective function and efficient data structure; extended intensification mechanisms (including randomized tabu criterion, combination of tabu search and local search, dynamic tabu list maintaining); enhanced diversification strategy using periodic tabu tenure and special mutation procedure. The ITS algorithm is tested on the different instances taken from the QAP library QAPLIB. The results from the experiments demonstrate promising efficiency of the proposed algorithm, especially for the random QAP instances.     

SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration

This paper presents a single instruction multiple data tabu search (SIMD-TS) algorithm for the quadratic assignment problem (QAP) with graphics hardware acceleration. The QAP is a classical combinatorial optimisation problem that is difficult to solve optimally for even small problems with over 30 items. By using graphic hardware acceleration, the developed SIMD-TS algorithm executes 20 to 45 times faster than traditional CPU code. The computational improvement is made possible by the utilisation of the parallel computing capability of a graphics processing unit (GPU). The speed and effectiveness of this algorithm are demonstrated on QAP library problems. The main contribution of this paper is a fast and effective SIMD-TS algorithm capable of producing results for large QAPs on a desktop personal computer equivalent to the results achieved with a CPU cluster.     

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

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

Location Selection and Scheduling Optimization of Material Storage in Manufacturing Workshop

Based on improved immune algorithm, the location of material storage in manufacturing workshop is studied. Intelligent optimization algorithms include particle swarm optimization algorithm, genetic selection algorithm, simulated annealing algorithm, tabu search algorithm and so on. According to the non-linear constraints, the objective function is established to solve the minimum energy consumption of material distribution. The improved immune algorithm can solve the complex problem of manufacturing workshop, and the material storage location and scheduling scheme can be obtained by combining simulation software. Scheduling optimization involves material warehousing, sorting, loading and unloading, handling and so on. Using the one-to-one accurate distribution principle and MATLAB software to simulate and analyze, the location of material warehousing in manufacturing workshop is determined, and the material distribution and scheduling are studied.     

Studying the effect of different combinations of timetabling with sequencing algorithms to solve the no-wait job shop scheduling problem

This paper considers the no-wait job shop (NWJS) problem with makespan minimisation criteria. It is well known that this problem is strongly NP-hard. Most of the previous studies decompose the problem into a timetabling sub-problem and a sequencing sub-problem. Each study proposes a different sequencing and timetabling algorithm to solve the problem. In this research, this important question is aimed to be answered: is the timetabling or the sequencing algorithm more important to the effectiveness of the developed algorithm? In order to find the answer, three different sequencing algorithms are developed; a tabu search (TS), a hybrid of tabu search with variable neighbourhood search (TSVNS), and a hybrid of tabu search with particle swarm optimisation (TSPSO). Afterwards, the sequencing algorithms are combined with four different timetabling methods. All the approaches are applied to a large number of test problems available in the literature. Statistical analysis reveals that although some of the sequencing and timetabling algorithms are more complicated than the others, they are not necessarily superior to simpler algorithms. In fact, some of the simpler algorithms prove to be more effective than complicated and time-consuming methods.     

MOAPPS 1.0: Aggregate production planning using the multiple-objective tabu search

In recent years, there has been a trend in the research community to solve large-scale complex planning and design problems using the modern heuristics optimization techniques (i.e. tabu search, genetic algorithms, etc.). This is mainly due to unsuitability of the classical solution techniques in many circumstances. Depending upon the assumptions made and the modelling approach used, aggregate production planning (APP) problems can be quite complex and large scale. Therefore, there is a need to investigate the suitability of modern heuristics for their solution. In this paper, the multiple-objective APP problem is formulated as a pre-emptive goal-programming model and solved by a specially developed multiple-objective tabu search algorithm. The mathematical formulation is built upon Masud and Hwang's model (original model) due to its extensibility characteristics. The present model extents their model by including subcontracting and setup decisions. The multiple-objective tabu search algorithm is applied to both the original and extended model. Results obtained from the solution of the original model are then compared. It is observed that the multiple-objective tabu search algorithm can be used as an alternative solution mechanism for solving APP problems. During this study, an object-oriented program is also developed using C++. This software is named as MOAPPS 1.0 (Multiple Objective Aggregate Production Planning Software).     

Multi-objective integrated acyclic crew rostering and vehicle assignment problem in public bus transportation

In this study, we try to solve a real planning problem faced in public bus transportation. It is a multi-objective integrated crew rostering and vehicle assignment problem. We model this problem as a multi-objective set partitioning problem. Most of the time, crew rostering problem with a single-objective function is considered, and the output may not satisfy some transport companies. To minimize the cost and maximize the fairness of the workload among the drivers, we define many criteria. Although crew rostering problem and its integrated versions appear in the literature, it is the first time these two problems are integrated. We propose a new multi-objective tabu search algorithm to obtain near Pareto-optimal solutions. The algorithm works with a set of solutions using parallel search. We test our algorithm for the case with ten objectives and define a method to choose solutions from the approximated efficient frontier to present to the user. We discuss the performance of our meta-heuristic approach.

     

Tabu search algorithm for flexible flow path design of unidirectional automated-guided vehicle systems

The unidirectional flow path design problem is one of the most important but difficult problems for the efficient design of automated-guided vehicle systems. As the problem was first formulated by Gaskins and Tanchoco, many researchers have studied the problem. However, the existing solution methods fail to provide an efficient solution approach. In this paper, a mathematical model for the unidirectional flow path design problem is developed. To obtain a near-to-optimal solution in reasonable computation time, a tabu search algorithm is presented. A fast construction algorithm first obtains a feasible initial solution, and a long-term memory structure and a neighbor solution generation approach are adapted to the problem characteristics and embedded in the proposed tabu search algorithm. Computational experiments show that the developed tabu search algorithm outperforms the Ko and Egbelu’s algorithm, Int J Prod Res, 41:2325–2343, (2003).     

基于数据挖掘的动态货位指派系统

目的为提高需求快速变化、波动较大的在线零售企业的仓库货位优化效率。方法利用数据仓库和数据挖掘法,研究基于复合规则的动态货位指派策略。对该货位指派的数据集成分析、指标计算、规则生成和货位指派等4个模块进行分析,并设计库区标定算法和规则生成算法来生成货位指派规则集。结果基于复合规则动态货位指派不仅能够节约拣货距离,而且拣货效率受需求变化的影响非常小。结论数值实验表明,与传统的货位指派策略相比,基于复合规则动态货位的指派系统可以得到更好的结果,并且在平均订单规模较大和需求偏度大的情况下效果更加明显。     

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

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

考虑废物包装时间的车辆回收路径规划方法

针对考虑废物包装时间的车辆回收路径规划问题,建立问题数学模型,提出禁忌搜索算法与模因算法求解该问题,并与爬山算法、遗传算法进行对比.模因算法是爬山算法和遗传算法的结合.实验结果表明:在解的质量方面,禁忌搜索算法与模因算法所求出的解的质量要远远好于另外两种算法,但在运行时间上,禁忌搜索、爬山算法与遗传算法要远优于模因算法.     

Research on Vehicle Routing Problem with Soft Time Windows Based on Hybrid Tabu Search and Scatter Search Algorithm

With the expansion of the application scope of social computing problems, many path problems in real life have evolved from pure path optimization problems to social computing problems that take into account various social attributes, cultures, and the emotional needs of customers. The actual soft time window vehicle routing problem, speeding up the response of customer needs, improving distribution efficiency, and reducing operating costs is the focus of current social computing problems. Therefore, designing fast and effective algorithms to solve this problem has certain theoretical and practical significance. In this paper, considering the time delay problem of customer demand, the compensation problem is given, and the mathematical model of vehicle path problem with soft time window is given. This paper proposes a hybrid tabu search (TS) & scatter search (SS) algorithm for vehicle routing problem with soft time windows (VRPSTW), which mainly embeds the TS dynamic tabu mechanism into the SS algorithm framework. TS uses the scattering of SS to avoid the dependence on the quality of the initial solution, and SS uses the climbing ability of TS improves the ability of optimizing, so that the quality of search for the optimal solution can be significantly improved. The hybrid algorithm is still based on the basic framework of SS. In particular, TS is mainly used for solution improvement and combination to generate new solutions. In the solution process, both the quality and the dispersion of the solution are considered. A simulation experiments verify the influence of the number of vehicles and maximum value of tabu length on solution, parameters’ control over the degree of convergence, and the influence of the number of diverse solutions on algorithm performance. Based on the determined parameters, simulation experiment is carried out in this paper to further prove the algorithm feasibility and effectiveness. The results of this paper provide further ideas for solving vehicle routing problems with time windows and improving the efficiency of vehicle routing problems and have strong applicability.     

Efficiently Solving the Redundancy Allocation Problem Using Tabu Search

A tabu search meta-heuristic has been developed and successfully demonstrated to provide solutions to the system reliability optimization problem of redundancy allocation. Tabu search is particularly well-suited to this problem and it offers distinct advantages compared to alternative optimization methods. While there are many forms of the problem, the redundancy allocation problem generally involves the selection of components and redundancy levels to maximize system reliability given various system-level constraints. This is a common and extensively studied problem involving system design, reliability engineering and operations research. It is becoming increasingly important to develop efficient solutions to this reliability optimization problem because many telecommunications (and other) systems are becoming more complex, yet with short development schedules and very stringent reliability requirements. Tabu search can be applied to a more diverse problem domain compared to mathematical programming methods, yet offers the potential of greater efficiency compared to population-based search methodologies, such as genetic algorithms. The tabu search is demonstrated on numerous variations of three different problems and compared to integer programming and genetic algorithm solutions. The results demonstrate the benefits of tabu search for solving this type of problem.     

Coupling ant colony optimization and the extended great deluge algorithm for the discrete facility layout problem

This article uses a hybrid optimization approach to solve the discrete facility layout problem (FLP), modelled as a quadratic assignment problem (QAP). The idea of this approach design is inspired by the ant colony meta-heuristic optimization method, combined with the extended great deluge (EGD) local search technique. Comparative computational experiments are carried out on benchmarks taken from the QAP-library and from real life problems. The performance of the proposed algorithm is compared to construction and improvement heuristics such as H63, HC63-66, CRAFT and Bubble Search, as well as other existing meta-heuristics developed in the literature based on simulated annealing (SA), tabu search and genetic algorithms (GAs). This algorithm is compared also to other ant colony implementations for QAP. The experimental results show that the proposed ant colony optimization/extended great deluge (ACO/EGD) performs significantly better than the existing construction and improvement algorithms. The experimental results indicate also that the ACO/EGD heuristic methodology offers advantages over other algorithms based on meta-heuristics in terms of solution quality.     

Integrated Production Planning and Scheduling on Automobile Assembly Lines

We address the closely related problems of production planning and scheduling on mixed model automobile assembly lines. We propose an integrated solution, in which a production plan that is feasible with respect to aggregate capacity constraints is developed and then a sequence that is feasible with respect to this plan is sought. We propose three tabu-search-based algorithms that explore the solution spaces for both problems to different degrees to find a combination of a production plan and schedule that are feasible and that approximately optimize the objective function (involving the overproduction and underproduction of finished automobiles, the set-up cost, the idle times of work-cells on the line, the makespan and the load deviations among work-cells). Simulation is used to evaluate alternative schedules. Stochastic extensions are proposed and the complexities of these algorithms are discussed. Example runs comparing the algorithms are presented for deterministic cases, stochastic cases, types of automobiles, buffer sizes and number of work-cells. The results show that an embedded tabu search algorithm is suitable for solving small scale problems, an alternate tabu search algorithm for the medium scale and a serial tabu search algorithm for the large scale.     

A tree-search method for solving a cutting stock assignment problem

Many production environments such as carpet or flat glass manufacturing have linked operations that perform completely different activities. In this paper, we consider a two-stage manufacturing process involving a cutting operation, followed by an assignment operation. Raw material is cut to meet product demand with minimum trim loss, and assignments are made to minimize resource requirements. This cutting stock assignment problem is formulated as a large-scale, mixed-integer nonlinear programming problem. We propose a solution methodology based on decomposition and tree search heuristic strategies. We report on extensive computational experiments on a wide range of problems, and apply statistical techniques to determine significant factors. For all small-size problems tested, our method found the exact optimal solution. For practical-size problems, our method was about two orders of magnitude faster and produced solutions that were one-third better than tabu search.