基于遗传算法的双区型仓库拣货路径优化研究

拣货作业成本是物流成本的重要组成部分。根据物流配送中心传统双区型仓库拣货路径问题的特点,建立了数学模型,并设计了相应的遗传算法来求解该问题。在算例中,通过与传统穿越策略、S形启发式算法和动态规划方法的比较,结果表明以遗传算法优化拣货路径问题,可以明显减少拣货路径的距离及拣货作业时间,具有良好的实用性。     

图的最大二等分问题的一种离散填充函数算法

图的最大二等分问题是一个经典的NP困难问题,有着广泛的应用背景。提出了一类求解最大二等分问题的离散填充函数算法。该算法采用快速的、基于迭代改进的算法作为局部搜索算法。构造了最大二等分问题的填充函数和辅助问题,并研究了该辅助问题的相关性质。利用局部搜索算法极大化辅助问题来寻找更好的解。用顶点数为800到10 000的大规模标准测试例子测试提出的算法。实验结果表明,该算法是有效的。     

Motion coordination algorithm for distributed agents in the cellular warehouse problem

A distributed approach is shown to coordinate the motions of transport tables for the cellular warehouse problem. In this approach, the tables are considered to be autonomous agents, and a built-in behavior function given by artificial neural networks (ANNs) and the evolved problem-oriented connection weights navigate the agents to their specified goals. To determine the agent to be moved, a measure of the priority to move is introduced. We show that distributed agents with the learned behavior function and the negotiation value perform a similar strategy to a “serializable” solution forN-puzzle problems, which provides a good heuristic strategy for large-scale problems. This work was presented, in part, at the Sixth International Symposium on Artificial Life and Robotics, Tokyo, Japan, January 15–17, 2001     

Discrete minimax problem: Algorithms and numerical comparisons

A discrete minimax problem is considered, and some applications are mentioned. A survey of algorithms for the solution of this problem is given. Particularly 2-stage-algorithms (developed by us, among others) using the Newton method to solve the optimality conditions are considered. Some of the mentioned algorithms are compared numerically by means of several examples.     

求解TSP 问题的离散狼群算法

通过定义反转算子, 对人工狼位置和智能行为重新进行整数编码设计, 并结合概率近邻初始化方法, 提出一种求解旅行商问题的离散狼群算法. 该算法保留了狼群算法基于职责分工的协作式搜索特性, 并较好地平衡了算法的广度开拓和深度开采能力. 采用C-TSP 问题和TSPLIB 数据库中的多组TSP 问题作为实验用算例, 并将所提出算法与其他5 种智能优化算法进行对比, 仿真结果表明, 所提出算法在求解准确率、稳定性和所需迭代次数等方面具有相对优势.

     

A parallel local search approach to solving the uncapacitated warehouse location problem

The uncapacitated warehouse location problem (UWLP) has been studied by many researchers. It has been solved using various approaches, including branch and bound linear programming, tabu search, simulated annealing, and genetic algorithms. This study presents a new local search (LS) approach to the UWLP that is quite simple and robust and is efficient in some cases. The algorithm was tested against standard OR Library benchmarks and M^* instances, which have already been used to test other approaches. The results show that the only disadvantage of the algorithm is the exponential growth of its computation time with the problem size. However, the multi-search design suggested here enables the algorithm to run under multi-processor or multi-core systems, which are currently provided as part of standard PC configurations.     

A particle swarm optimization algorithm for the multiple-level warehouse layout design problem

Warehouse operation and management is one of the essential parts of manufacturing and service operations. The warehouse layout problem is a key to warehouse operations. Generally, warehouse layout design models attempt to optimize different objectives such as the orientation of storage racks, the allocation of space among competing uses, the number of cranes, the overall configuration of the facility, etc. The warehousing strategies can be classified as distribution-type, production-type and contract-type warehouse strategies. In this study, a distribution-type warehouse considered that various type products are collected from different suppliers for storing in the warehouse for a determined period and for delivery to different customers. The aim of the study is to design a multiple-level warehouse shelf configuration which minimizes the annual carrying costs. The turnover rates of the products are classified and they are considered while putting/picking them to/from shelves regarding the distances between the shelves and docks. Since proposed mathematical model was shown to be NP-hard, a particle swarm optimization algorithm (PSO) as a novel heuristic was developed for determining the optimal layout.     

A parallel local search approach to solving the uncapacitated warehouse location problem

The uncapacitated warehouse location problem (UWLP) has been studied by many researchers. It has been solved using various approaches, including branch and bound linear programming, tabu search, simulated annealing, and genetic algorithms. This study presents a new local search (LS) approach to the UWLP that is quite simple and robust and is efficient in some cases. The algorithm was tested against standard OR Library benchmarks and M^* instances, which have already been used to test other approaches. The results show that the only disadvantage of the algorithm is the exponential growth of its computation time with the problem size. However, the multi-search design suggested here enables the algorithm to run under multi-processor or multi-core systems, which are currently provided as part of standard PC configurations.     

The multi-level warehouse layout problem with uncertain information: uncertainty theory method

This paper investigates the multi-level warehouse layout problem with indeterminate factors, in which the monthly demands and horizontal transportation distances are described by uncertain variables. We first consider the distribution function of the total cost for transportation. Second, two uncertain models, namely, the chance-constrained programming model and the chance-maximum programming model, are developed to lay out the multi-level warehouse under uncertainty. Some properties of the models are discussed to solve the models. The properties point out that the optimal solution to the chance-constrained programming model is equivalent to a corresponding deterministic model. Additionally, we also discuss the relation between the chance-constrained programming model and the chance-maximum programming model, which leads to an effective approach to search for the optimal solution to the chance-maximum programming model. Finally, a numerical experiment is illustrated to show the ideas of the proposed models.     

离散蝙蝠算法在三阶段装配流水线调度问题的应用

为了解决三阶段装配流水线调度问题,提出一种改进的离散型蝙蝠算法(DBA).针对所提问题的瓶颈期,提出下限理论,改进三阶段瓶颈期的下限公式,并引入调度模型生成初始种群,重新划分蝙蝠的捕食范围(HR),通过捕食行为、迁移行为的改进提高局部搜索能力,以有效提高离散蝙蝠算法的性能.改进K-means聚类算法,将具有最高相似性的...     

解决零空闲流水线调度问题的离散粒子群算法

研究了以最大完工时间为目标的零空闲流水线调度问题.提出一种复杂度为O(nm)的最大完工时间算法和一种快速插入邻域搜索算法;提出了解决该问题的离散粒子群调度算法,并结合简化邻域搜索算法给出了提高调度算法性能的措施.仿真实验表明了所得算法的有效性.     

Discrete symbiotic organisms search algorithm for travelling salesman problem

A Discrete Symbiotic Organisms Search (DSOS) algorithm for finding a near optimal solution for the Travelling Salesman Problem (TSP) is proposed. The SOS is a metaheuristic search optimization algorithm, inspired by the symbiotic interaction strategies often adopted by organisms in the ecosystem for survival and propagation. This new optimization algorithm has been proven to be very effective and robust in solving numerical optimization and engineering design problems. In this paper, the SOS is improved and extended by using three mutation-based local search operators to reconstruct its population, improve its exploration and exploitation capability, and accelerate the convergence speed. To prove that the proposed solution approach of the DSOS is a promising technique for solving combinatorial problems like the TSPs, a set of benchmarks of symmetric TSP instances selected from the TSPLIB library are used to evaluate its performance against other heuristic algorithms. Numerical results obtained show that the proposed optimization method can achieve results close to the theoretical best known solutions within a reasonable time frame.     

Discrete cuckoo search algorithm for the travelling salesman problem

In this paper, we present an improved and discrete version of the Cuckoo Search (CS) algorithm to solve the famous traveling salesman problem (TSP), an NP-hard combinatorial optimisation problem. CS is a metaheuristic search algorithm which was recently developed by Xin-She Yang and Suash Deb in 2009, inspired by the breeding behaviour of cuckoos. This new algorithm has proved to be very effective in solving continuous optimisation problems. We now extend and improve CS by reconstructing its population and introducing a new category of cuckoos so that it can solve combinatorial problems as well as continuous problems. The performance of the proposed discrete cuckoo search (DCS) is tested against a set of benchmarks of symmetric TSP from the well-known TSPLIB library. The results of the tests show that DCS is superior to some other metaheuristics.     

求解考试时间安排问题的离散蛙跳算法

针对考试时间安排问题,提出了一种离散化蛙跳求解算法,并结合简化邻域搜索算法给出了两种改进策略。该算法借助蛙跳算法优化机理,采用基于时间序列的编码方式和新的个体产生方法扩展了传统蛙跳算法的求解模型。仿真实验表明了所提算法及策略的有效性。     

随机中断情境下的离散型设施选址问题研究

针对传统的供应链设施选址模型大多是基于静态背景下的确定性选址问题研究,而较少考虑中断风险因素的情况,基于随机中断情境,建立了混合整数规划模型表述的设施可靠性选址问题模型,采用拉格朗日松弛算法进行求解。通过构建的算例,求解了问题模型的最优解并验证了该算法的求解性能。     

求解最小比率旅行商问题的离散蝙蝠算法

研究了以总路程与总收益之比为目标函数的最小比率旅行商问题,提出了求解该问题的离散蝙蝠算法。介绍了蝙蝠算法的基本思想,重新定义了位置与位置的减法操作算子、实数与位置的乘法操作算子以及速度与位置的加法操作算子,引入了城市子序列逆序策略来对线路进行局部搜索。给出了算法的具体实现方案,并通过仿真和比较实验验证算法的优化性能,实验结果表明该算法可以有效求解最小比率旅行商问题。     

离散微粒群算法求解批量流水线调度问题

提出了解决批量流水线调度问题的离散微粒群优化算法。该算法采用了基于工序的编码方式,设计了新的粒子生成公式,从而使微粒群算法可以直接应用于调度问题。同时,针对微粒群算法容易陷入局部最优的缺陷,将其与模拟退火算法结合,得到了改进的微粒群优化算法。仿真实验表明了上述算法的有效性。     

Comparative analysis of multi-criteria decision making methodologies and implementation of a warehouse location selection problem

For the solution of decision making problems with multi criteria, the literature presents many methodologies under the title of decision theory. In this context, AHP, TOPSIS, ELECTRE and Grey Theory are well-known and the most acceptable methodologies. Firstly, in this study; these methodologies are compared in terms of main characteristic of decision theory and thus advantages and disadvantages of these methodologies are offered. Later, the application of these methodologies on the warehouse selection problem, which is one of the main topics of logistics management that has a wide range of applications with multi-criteria decision making methodologies, is presented as a case study which is characterized in retail sector, that maintains high uncertainity and product variety and then how to choose the best warehouse location among many alternatives has been shown.     

Discrete Particle Swarm Optimization for the minimum labelling Steiner tree problem

Particle Swarm Optimization is a population-based method inspired by the social behaviour of individuals inside swarms in nature. Solutions of the problem are modelled as members of the swarm which fly in the solution space. The improvement of the swarm is obtained from the continuous movement of the particles that constitute the swarm submitted to the effect of inertia and the attraction of the members who lead the swarm. This work focuses on a recent Discrete Particle Swarm Optimization for combinatorial optimization, called Jumping Particle Swarm Optimization. Its effectiveness is illustrated on the minimum labelling Steiner tree problem: given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes, whose edges have the smallest number of distinct labels.