The Assembly Line Balancing (ALB) problem involves dividing total assembly operations into tasks and assigning them to workstations so that each workstation has approximately equal times and precedence constraints are met. The most fundamental and well-studied model in ALB is called Simple ALB Problem Type 1 (SALBP-1), which aims to minimize the number of loaded stations given a fixed cycle time. SALBP-1 is proven to be NP-hard and thus its efficient solution is challenging. In this paper, we developed an Iterated Local Search (ILS) algorithm customized for obtaining high-quality and feasible solutions to SALBP-1 by minimizing the number of assembly stations. We tested our method on 270 benchmark problems from Talbot's, Scholl's, and Otto's datasets, as well as on a real antenna assembly case, and compared the results with nine algorithms from the literature. Analyses showed that the ILS outperformed other algorithms by reaching or improving the best-known upper-bound solutions in 269 of the 270 instances within lower computational runtimes. Key components that contribute to the success of the ILS include the way the initial solution is selected, innovative shallow and deep task assignment implementation, and the diversity of neighborhood generating operators (including the novel Float Shift operator), which help the algorithm to converge toward feasible solutions and achieve minimal values for the objective function. The proposed method enables designers and engineers to design more efficient assembly lines and reduce production lead times and overall costs.

In this paper, a new variation to the Hub Maximal Covering problem called the Capacitated Single-Allocation Hub Maximal Covering Problem (CSAHMCP) is addressed for the first time and a novel binary-integer mathematical model has been proposed. To analyze the features of the problem’s solution space and to determine the most effective heuristic approach to solve it, a comprehensive Fitness Landscape Analysis is performed which reveals that the problem is of ‘rugged plain’ type and can best be solved using an algorithm with good exploration and exploitation capabilities at the same time. Accordingly, we proposed a new algorithm named GARVND, which is a hybrid of the Genetic Algorithm acting as the main framework for diversification, and a variant of the Variable Neighborhood Descent algorithm called ‘Reduced VND’ acting as a means to improve individual solutions (intensification) by searching in the spaces generated by four types of neighborhood operators. We also introduced two original crossover and mutation operators that can be used for any hub location solution method. The parameters of GARVND are tuned toward less computational times and higher solution quality by using the Taguchi experiment design technique. We solved 114 CSAHMCP instances (several times each) from the Australian Post (AP) dataset using the proposed GARVND, as well as by the Genetic Algorithm, Variable Neighborhood Search, Simulated Annealing, Tabu Search algorithms, and a hybrid algorithm consisting of Grey Wolf Optimizer and Simulated Annealing, in addition to the Gurobi exact solver. Extensive computational results and statistical analyses showed that GARVND yields favorable solutions, outperforming all the compared algorithms by producing smaller gaps with global optimal objective values. In addition, to illustrate the practical value of the CSAHMCP and the GARVND method, we performed a cost-flow sensitivity analysis for the AP Central Sydney network and came up with the best expansion scenarios to be adopted by the management.

In practical robot motion planning, robots usually do not have full models of their surrounding, and hence no complete and correct plan exists for the robots to be executed fully. In most real-world problems a robot operates in just a partially-known environment, meaning that most of the environment is known to the robot at the time of planning, but there exists incomplete information about some ‘hidden’ variables which represent potential blockages (e.g. open/closed doors, or corridors congested with other robots or obstacles). For these hidden variables, the robot has a probability distribution estimation and a prioritized preference over their possible values. In this paper, to deal with the problem of choosing an optimal policy for planning in offline mode, a stochastic dynamic programming model is developed, which is converted to and solved by linear programming. Next, a heuristic method is proposed for conditional planning in the presence of numerous hidden variables which produces optimal plans.

In this paper, the multi robot motion planning problem is solved through a decoupled approach, where a new algorithm for prioritizing the robots moves is developed. Assuming that the workspace is mapped into a tree graph and the initial and final configurations of robots are known, the robots' shortest start-to-goal paths on the tree are calculated independently. Then, a new rule-based prioritization scheme is applied in two phases: (a) Path Prioritization, which determines which robot can directly move along its shortest path and which robot should deviate from it, and (b) Motion Prioritization, which decides the order of robots' sequential moves. Furthermore, an algorithm is presented for minimizing the number of moves by adding extra vertices to the tree.

Two new heuristic models are developed for motion planning of point robots in known environments. The first model is a combination of an improved particle swarm optimization (PSO) algorithm used as a global planner and the probabilistic roadmap (PRM) method acting as a local obstacle avoidance planner. For the PSO component, new improvements are proposed in initial particle generation, the weighting mechanism, and position- and velocity-updating processes. Moreover, two objective functions which aim to minimize the path length and oscillations, govern the robot’s movements towards its goal. The PSO and PRM components are further intertwined by incorporating the best PSO particles into the randomly generated PRM. The second model combines a genetic algorithm component with the PRM method. In this model, new specific selection, mutation, and crossover operators are designed to evolve the population of discrete particles located in continuous space. Thorough comparisons of the developed models with each other, and against the standard PRM method, show the advantages of the PSO method.

Multi robot motion planning problems can be solved very efficiently when the configuration space is mapped onto a graph. Before planning, however, it must be assured that the constructed graph is reachable (solvable) for the given number and configuration of robots. Solvable trees are types of trees that let any arrangement of a specified number of robots be reached from any initial arrangement through sequential moves of robots on vertices of the tree. In this paper the properties of solvable trees are investigated, and minimal solvable trees, which are the smallest solvable trees in terms of the number of vertices, are introduced as a new concept. Also, a new algorithm with linear time complexity is proposed for deciding whether a multi robot motion planning problem has a solution on a tree, without explicitly solving it.

A new motion planning algorithm is proposed for point and disc robots. In this approach, the problem is first formulated as a Binary Integer Programming with variables taken from Delaunay Triangulation of the 2D or n-D Free Configuration Space, and then transformed into LMIs and solved to obtain an optimal channel made of connected triangles. The channel is then used to build safe and short paths within from Start to Goal. It is also possible to weight certain passageways of the space so that the robot can avoid costly routes, which is especially useful for traffic control applications. Finally, a tracking control strategy along trajectory based on preplanned path is applied for a synchronous drive robot. The algorithm is simple, complete, and does not suffer from local minima. It is also extendable to 3 and higher C-spaces.

This paper deals with the online path planning of mobile robots. We first suggest a systematic method to incrementally construct the Medial Axis of the workspace. This is done by using sensor information for land-marking the nodes of medial axis, which will guide the robot to explore the unknown environment thoroughly. Next, this approach is implemented in an online motion planning algorithm. This method can be generalized to higher spaces, and uses only the line of sight information of sonar sensors. It is much simpler than HGVG method, and is complete. The simulations showed good results for different environments.