China
Africa
Explore chapters and articles related to this topic
AGV Routing via Ant Colony Optimization Using C#
Published in Kaushik Kumar, J. Paulo Davim, Optimization Using Evolutionary Algorithms and Metaheuristics, 2019
Şahin Inanç, Arzu Eren Şenaras
Ant colony algorithms were first proposed by Dorigo and colleagues as a multi-agent approach to difficult combinatorial optimization problems such as the traveling salesman problem and the quadratic assignment problem. There is currently much ongoing activity in the scientific community to extend and apply ant-based algorithms to many different discrete optimization problems. Recent applications cover problems such as vehicle routing, job shop scheduling, quadratic assignment problems and so on (Kulatunga et al. 2006).
Flexible Factory Layouts: Issues in Design, Modeling, and Analysis
Published in Cornelius Leondes, The Design of Manufacturing Systems, 2019
Because the quadratic assignment problem has been shown elsewhere to be NP complete [28], the model proposed here is also NP complete. This means that obtaining an optimal solution for most problems in practice would require an excessive amount of computational effort. Therefore, a heuristic method is provided next. The method is an extension of existing layout heuristics, such as CRAFT [44], that use an iterative pairwise, or multi-step, exchange procedure in generating a final layout. Our approach differs from these heuristics in that we are not only solving for the layout but also for the flow volume allocation between departments. Consequently, at each iteration step and for each new layout considered, the flow volume allocation problem needs to be solved before the layout cost can be calculated. Fortunately, the problem can be formulated as a linear program and solved optimally in a reasonable amount of time. The steps of the heuristic are described next. Step 1. Set J = 1.Step 2. Generate an initial layout.Step 3. Solve optimally for flow volume allocation (a linear program).Step 4. Calculate z(J), the resulting objective function value of the original layout problem.Step 5. Set J = J + 1. If J > Jmax, go to Step 9 (e.g., Jmax is the maximum number of feasible pairwise interchanges).Step 6. Generate the next layout (e.g., by a pairwise interchange).Step 7. Solve optimally for flow volume allocation (a linear program).Step 8. Calculate z(J), the resulting value for the objective function. Go back to Step 5.Step 9. Implement the minimum cost layout. If the minimum cost layout is the same as the previous one, then go to Step 10. Otherwise, set J = 1 and go back to Step 5.Step 10. Stop.
Concurrent design of product and supply chain architectures for modularity and flexibility: process, methods, and application
Published in International Journal of Production Research, 2022
Thiam-Soon Gan, Moritz Steffan, Martin Grunow, Renzo Akkerman
Decision variables:Module formation model: Subject to:The objective function (2) maximises the interactions between the seed parts i and the non-seed parts j (first expression) as well as the interactions between all non-seed parts j and k in all clusters (second expression). Constraints (3) ensure that each part j is assigned to exactly one seed part i. Constraints (4) ensure minimum and maximum cluster sizes. The quadratic assignment problem (Equations (2–4)) can be solved by a non-linear solver such as a quadratic and general reduced gradient solver or a meta-heuristic such as a genetic algorithm depending on the size of model. For the case study (Figure 4), we set the target number of seed parts as four and the minimum cluster size as two. The seed parts are determined at F-level = 0.13. The four resulting modules consist of the seed parts (P2, P5, P11 and P13) and their assigned parts (Figures 3 and 4). Using a laptop with Intel® Core i7 processor and 16GB RAM, the mode of the clustering method is solved by the genetic algorithm in Frontline Solver Pro (60 sec).
The ‘Idiot’ crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
Published in Optimization Methods and Software, 2020
The quadratic assignment problem (QAP) is a combinatorial optimization problem, being a special case of the facility location problem. It concerns a set of facilities and a set of locations. For each pair of locations there is a distance, and for each pair of facilities there is a weight or flow specified, for instance the number of items transported between the two facilities. The problem is to assign all facilities to different locations so that the sum of the distances multiplied by the corresponding flows is minimized. QAPs are well known for being very difficult to solve, even for small instances. They are NP-hard and the travelling salesman problem can be seen as a special case. Often, rather than the quadratic problem itself, an equivalent linearization is solved. A comprehensive survey of QAP problems and their solution is given by Loiola et al. [11].
A hybrid algorithm combining lexisearch and genetic algorithms for the quadratic assignment problem
Published in Cogent Engineering, 2018
Given a set of facilities and locations along with the flows between facilities and the distances between locations, the objective of the “Quadratic Assignment Problem” is to assign each facility to a location in such a way as to minimize the total assignment cost. The problem has a several applications such as the location of interdependent plants or facilities, the layout of interacting departments in an office building, the location of medical facilities in a hospital, the backboard wiring problem in the design of computer and other electronic equipment, and so on. As the problem is very difficult to solve, several methods have been proposed to find optimal solution. However, finding optimal solution within less computational efforts is still challenging one. This paper proposes a hybrid algorithm by combining two types of methods that encourages to make use of advantages of both methods. The experimental results also acknowledge its effectiveness.