A Multi-stage Heuristic Algorithm for Matching Problem in the Modified Miniload Automated Storage and Retrieval System of E-commerce

E-commerce, as an emerging marketing mode, has attracted more and more attention and gradually changed the way of our life. However, the existing layout of distribution centers can＇t fulfill the storage and picking demands of e-commerce sufficiently. In this paper, a modified miniload automated storage/retrieval system is designed to fit these new characteristics of e-commerce in logistics. Meanwhile, a matching problem, concerning with the improvement of picking efficiency in new system, is studied in this paper. The problem is how to reduce the travelling distance of totes between aisles and picking stations. A multi-stage heuristic algorithm is proposed based on statement and model of this problem. The main idea of this algorithm is, with some heuristic strategies based on similarity coefficients, minimizing the transportations of items which can not arrive in the destination picking stations just through direct conveyors. The experimental results based on the cases generated by computers show that the average reduced rate of indirect transport times can reach 14.36% with the application of multi-stage heuristic algorithm. For the cases from a real e-commerce distribution center, the order processing time can be reduced from 11.20 h to 10.06 h with the help of the modified system and the proposed algorithm. In summary, this research proposed a modified system and a multi-stage heuristic algorithm that can reduce the travelling distance of totes effectively and improve the whole performance of e-commerce distribution center.

A Weight-Coded Evolutionary Algorithm for the Multidimensional Knapsack Problem

A revised weight-coded evolutionary algorithm (RWCEA) is proposed for solving multidimensional knapsack problems. This RWCEA uses a new decoding method and incorporates a heuristic method in initialization. Computational results show that the RWCEA performs better than a weight-coded evolutionary algorithm pro-posed by Raidl (1999) and to some existing benchmarks, it can yield better results than the ones reported in the OR-library.

SEMI-DEFINITE RELAXATION ALGORITHM OF MULTIPLE KNAPSACK PROBLEM

The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .

Quantum-inspired ant algorithm for knapsack problems

The knapsack problem is a well-known combinatorial optimization problem which has been proved to be NP-hard. This paper proposes a new algorithm called quantum-inspired ant algorithm （QAA） to solve the knapsack problem. QAA takes the advantage of the principles in quantum computing, such as qubit, quantum gate, and quantum superposition of states, to get more probabilistic-based status with small colonies. By updating the pheromone in the ant algorithm and rotating the quantum gate, the algorithm can finally reach the optimal solution. The detailed steps to use QAA are presented, and by solving series of test cases of classical knapsack problems, the effectiveness and generality of the new algorithm are validated.

A Hybrid Parallel Multi-Objective Genetic Algorithm for 0/1 Knapsack Problem

In this paper a hybrid parallel multi-objective genetic algorithm is proposed for solving 0/1 knapsack problem. Multi-objective problems with non-convex and discrete Pareto front can take enormous computation time to converge to the true Pareto front. Hence, the classical multi-objective genetic algorithms (MOGAs) (i.e., non- Parallel MOGAs) may fail to solve such intractable problem in a reasonable amount of time. The proposed hybrid model will combine the best attribute of island and Jakobovic master slave models. We conduct an extensive experimental study in a multi-core system by varying the different size of processors and the result is compared with basic parallel model i.e., master-slave model which is used to parallelize NSGA-II. The experimental results confirm that the hybrid model is showing a clear edge over master-slave model in terms of processing time and approximation to the true Pareto front.

Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts

Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O（2^3n/8） time when O（2^3n/8） shared memory units and O（2^n/4） processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-fist algorithm is the first exclusive-read exclusive-write （EREW） parallel algorithm that can solve the knapsack instances in less than O（2^n/2） time when the available hardware resource is smaller than O（2^n/2） , and hence is an improved result over the past researches.

An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

A new parallel algorithm is proposed for the knapsack problem where the method of divide and conquer is adopted. Based on an EREW-SIMD machine with shared memory, the proposed algorithm utilizes O(2 n/4 ) 1-ε processors, 0≤ ε ≤1, and O(2 n/2 ) memory to find a solution for the n -element knapsack problem in time O(2 n/4 (2 n/4 ) ε) . The cost of the proposed parallel algorithm is O(2 n/2 ) , which is an optimal method for solving the knapsack problem without memory conflicts and an improved result over the past researches.

The 0/1 Multidimensional Knapsack Problem and Its Variants: A Survey of Practical Models and Heuristic Approaches

The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting NP-hard combinatorial optimization problem that can model a number of challenging applications in logistics, finance, telecommunications and other fields. In the 0/1 MKP, a set of items is given, each with a size and value, which has to be placed into a knapsack that has a certain number of dimensions having each a limited capacity. The goal is to find a subset of items leading to the maximum total profit while respecting the capacity constraints. Even though the 0/1 MKP is well studied in the literature, we can just find a little number of recent review papers on this problem. Furthermore, the existing reviews focus particularly on some specific issues. This paper aims to give a general and comprehensive survey of the considered problem so that it can be useful for both researchers and practitioners. Indeed, we first describe the 0/1 MKP and its relevant variants. Then, we present the detailed models of some important real-world applications of this problem. Moreover, an important collection of recently published heuristics and metaheuristics is categorized and briefly reviewed. These approaches are then quantitatively compared through some indicative statistics. Finally, some synthetic remarks and research directions are highlighted in the conclusion.

An Improved Binary Wolf Pack Algorithm Based on Adaptive Step Length and Improved Update Strategy for 0-1 Knapsack Problems

Binary wolf pack algorithm (BWPA) is a kind of intelligence algorithm which can solve combination optimization problems in discrete spaces.Based on BWPA, an improved binary wolf pack algorithm (AIBWPA) can be proposed by adopting adaptive step length and improved update strategy of wolf pack. AIBWPA is applied to 10 classic 0-1 knapsack problems and compared with BWPA, DPSO, which proves that AIBWPA has higher optimization accuracy and better computational robustness. AIBWPA makes the parameters simple, protects the population diversity and enhances the global convergence.

Heuristic algorithm for RCPSP with the objective of minimizing activities' cost

Resource-constrained project scheduling problem（RCPSP） is an important problem in research on project management. But there has been little attention paid to the objective of minimizing activities＇ cost with the resource constraints that is a critical sub-problem in partner selection of construction supply chain management because the capacities of the renewable resources supplied by the partners will effect on the project scheduling. Its mathematic model is presented firstly, and analysis on the characteristic of the problem shows that the objective function is non-regular and the problem is NP-complete following which the basic idea for solution is clarified. Based on a definition of preposing activity cost matrix, a heuristic algorithm is brought forward. Analyses on the complexity of the heuristics and the result of numerical studies show that the heuristic algorithm is feasible and relatively effective.

Uncertain bilevel knapsack problem and its solution

This paper aims at providing an uncertain bilevel knapsack problem (UBKP) model, which is a type of BKPs involving uncertain variables. And then an uncertain solution for the UBKP is proposed by defining PE Nash equilibrium and PE Stackelberg Nash equilibrium. In order to improve the computational efficiency of the uncertain solution, several operators (binary coding distance, inversion operator, explosion operator and binary back learning operator) are applied to the basic fireworks algorithm to design the binary backward fireworks algorithm (BBFWA), which has a good performance in solving the BKP. As an illustration, a case study of the UBKP model and the P-E uncertain solution is applied to an armaments transportation problem.

A Novel Method for Solving Unbounded Knapsack Problem

Knapsack problem is one kind of NP-Complete problem. Unbounded knapsack problems are more complex and harder than general knapsack problem. In this paper,we apply QGAs (Quantum Genetic Algorithms) to solve unbounded knapsack problem and then follow other procedures. First,present the problem into the mode of QGAs and figure out the corresponding genes types and their fitness functions. Then,find the perfect combination of limitation and largest benefit. Finally,the best solution will be found. Primary experiment indicates that our method has well results.

1-Neighbour knapsack problem and prospective greedy algorithm of intentional islanding in active distribution network

A connected and undirected graph model of active distribution networks with considering the function of interconnecting switches is constructed in this paper.Based on this model,the island partition problem of active distribution networks can be described as a 1-neighbour knapsack problem.An effective heuristic algorithm named prospective greedy algorithm is then proposed to solve this problem.Case studies on PG&E 69-bus network show the validity of the proposed model and algorithm.

Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm

To address indeterminism in the bilevel knapsack problem,an uncertain bilevel knapsack problem(UBKP)model is proposed.Then,an uncertain solution for UBKP is proposed by defining thePE Nash equilibrium andPE Stackelberg-Nash equilibrium.To improve the computational efficiency of the uncertain solution,an evolutionary algorithm,the improved binary wolf pack algorithm,is constructed with one rule(wolf leader regulation),two operators(invert operator and move operator),and three intelligent behaviors(scouting behavior,intelligent hunting behavior,and upgrading).The UBKP model and thePE uncertain solution are applied to an armament transportation problem as a case study.

A two-stage metaheuristic algorithm for the dynamic vehicle routing problem in Industry 4.0 approach

Industry 4.0 is a concept that assists companies in developing a modern supply chain(MSC)system when they are faced with a dynamic process.Because Industry 4.0 focuses on mobility and real-time integration,it is a good framework for a dynamic vehicle routing problem(DVRP).This research works on DVRP.The aim of this research is to minimize transportation cost without exceeding the capacity constraint of each vehicle while serving customer demands from a common depot.Meanwhile,new orders arrive at a specific time into the system while the vehicles are executing the delivery of existing orders.This paper presents a two-stage hybrid algorithm for solving the DVRP.In the first stage,construction algorithms are applied to develop the initial route.In the second stage,improvement algorithms are applied.Experimental results were designed for different sizes of problems.Analysis results show the effectiveness of the proposed algorithm.

Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches. Keywords knapsack problem - NP-complete - parallel algorithm - optimal algorithm - memory conflict Supported by the National Natural Science Foundation of China under Grant No.60273075, the National High Technology Development 863 Program of China under Grant No.863-306-ZD-11-01-06.Ken-Li Li received his B.S. and M.S. degrees in mathematics from National University of Defense Technology and Central South University in 1995 and 2000 respectively and he is now a Ph.D. candidate in computer software and theory at Huazhong University of Science and Technology. His main research interests include parallel computing and combinatorial optimization.Ren-Fa Li received his Ph.D. degree in computer software and theory at Huazhong University of Science and Technology, and he is concurrently a professor and Ph.D. supervisor in School of Computer and Communication, Human University. His main research interests include network computing.Qing-Hua Li received his M.S. degree in computer science from Huazhong University of Science and Technology in 1981, and he is concurrently a professor and Ph.D. supervisor in School of Computer Science and Technology, Huazhong University of Science and Technology. His current research interests include parallel processing, combinatorial optimization, and grid computing.

An Algorithm for the Inverse Problem of Matrix Processing: DNA Chains, Their Distance Matrices and Reconstructing

We continue to consider one of the cybernetic methods in biology related to the study of DNA chains. Exactly, we are considering the problem of reconstructing the distance matrix for DNA chains. Such a matrix is formed on the basis of any of the possible algorithms for determining the distances between DNA chains, as well as any specific object of study. At the same time, for example, the practical programming results show that on an average modern computer, it takes about a day to build such a 30 × 30 matrix for mnDNAs using the Needleman-Wunsch algorithm;therefore, for such a 300 × 300 matrix, about 3 months of continuous computer operation is expected. Thus, even for a relatively small number of species, calculating the distance matrix on conventional computers is hardly feasible and the supercomputers are usually not available. Therefore, we started publishing our variants of the algorithms for calculating the distance between two DNA chains, then we publish algorithms for restoring partially filled matrices, i.e., the inverse problem of matrix processing. Previously, we used the method of branches and boundaries, but in this paper we propose to use another new algorithm for restoring the distance matrix for DNA chains. Our recent work has shown that even greater improvement in the quality of the algorithm can often be achieved without improving the auxiliary heuristics of the branches and boundaries method. Thus, we are improving the algorithms that formulate the greedy function of this method only. .

An Improved Heuristic Recursive Strategy Based on Genetic Algorithm for the Strip Rectangular Packing Problem

与基因算法结合的改进启发式的递归的策略在这份报纸被介绍。第一，这个方法寻找一些矩形，它有一样的长度或宽度，到没有浪费空间，形成一些层，然后，计算留下包装顺序的高度使用启发式的递归的策略并且使用基因算法的进化能力减少高度。基准问题的几个班上的计算结果证明了介绍算法能与已知的进化启发规则竞争。它特别为大测试问题更好表现。

A membrane-inspired algorithm with a memory mechanism for knapsack problems

Membrane algorithms are a class of distributed and parallel algorithms inspired by the structure and behavior of living cells. Many attractive features of living cells have already been abstracted as operators to improve the performance of algorithms. In this work, inspired by the function of biological neuron cells storing information, we consider a memory mechanism by introducing memory modules into a membrane algorithm. The framework of the algorithm consists of two kinds of modules (computation modules and memory modules), both of which are arranged in a ring neighborhood topology. They can store and process information, and exchange information with each other. We test our method on a knapsack problem to demonstrate its feasibility and effectiveness. During the process of approaching the optimum solution, feasible solutions are evolved by rewriting rules in each module, and the information transfers according to directions defined by communication rules. Simulation results showed that the performance of membrane algorithms with memory cells is superior to that of algorithms without memory cells for solving a knapsack problem. Furthermore, the memory mechanism can prevent premature convergence and increase the possibility of finding a global solution.

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization （ACO） is a new heuristic algo- rithm which has been proven a successful technique and applied to a number of combinatorial optimization problems. The traveling salesman problem （TSP） is among the most important combinato- rial problems. An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature con- vergence problem of the basic ACO algorithm on TSP. The main idea is to partition artificial ants into two groups： scout ants and common ants. The common ants work according to the search manner of basic ant colony algorithm, but scout ants have some differences from common ants, they calculate each route＇s muta- tion probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability. Simulation on TSP shows that the improved algorithm has high efficiency and robustness.