Sage Journals: Discover world-class research

Abstract

Modern manufacturing systems require timely and efficient production tasks. Any mistakes can have serious consequences which effect the production process obviously. The supply of goods is the beginning of the production process, ensuring that production can proceed normally. Using mobile robots for transportation and supply of production lines can achieve automatic manufacturing. We studied the use of multiple mobile robots to supply multiple production lines. Robots need to return to warehouse when no goods exist. This problem is called a multi-mobile robots and multi-trips feeding scheduling problem. We constructed a mathematical model describing multi-mobile robots and multi-trips feeding scheduling problem, and the objective function is to minimize the transportation cost and waiting cost. To solve this problem, we proposed an improved hybrid genetic algorithm, where a strategy of mixing improved genetic algorithm and tabu search algorithm is adopted to find robots with reasonable routes. Combining genetic algorithm with tabu search algorithm can improve the route planning effect and find a lower cost solution. In the experimental part, it is verified that the proposed algorithm could effectively find reasonable ways for robots to provide services. We also put forward suggestions for the scenarios of using robots in actual production.

Keywords

Mobile robot multi-trips feeding hybrid genetic algorithm scheduling

Introduction

With upgrading of technology and increasing demand from customers, the manufacturing system is moving toward a more reliable and intelligent direction. In today’s manufacturing systems, there are high demands for automated loading and unloading of goods and automated processing production tasks. Using automated mobile robots has gradually become a trend. The use of robots not only allows fewer errors to occur but also satisfies the requirements of manufacturing. Mobile robots are self-moving, with embedded batteries and manipulation arms that can carry goods and perform many types of tasks. Mobile robots can load goods required by production lines from warehouse, transport it, and feed goods to production lines after reaching the designated location. When a robot has no goods, it needs to return to warehouse to reload goods. The amount of goods that each robot can carry is fixed, which means that the number of feeding tasks that a robot can provide is limited. Each production line has been in the process of production. Continuous production of supplementary goods is only carried out within the certain range of the existing goods on the production line. This process satisfies the characteristics of the (s, Q) inventory system. The multi-mobile robots and multi-trips feeding scheduling problem (MMRMTFSP) is a challenging and realistic planning problem to match mobile robots’ movement and the process of feeding goods with production process of production lines.

The MMRMTFSP asks multiple mobile robots to load goods needed in production lines at warehouse. After the loading process is completed, the warehouse will arrive at the production line at a given time, and goods will be fed for production lines. In the (s, Q) system, the production line has a limit on the need to add goods, and when the quantity of goods on production lines is below the limit, goods need to be added. Adding goods to production lines cannot be later than when there are no goods on production lines. The range of arrival limit and quantity of goods in each production process constitutes an available time window, while the time to reach the limit is release time, and the time when the quantity of goods is 0 is due time. The time selection of the robot transport is particularly important. The mobile robot can arrive earlier than the release time. If it arrives in advance, the robot needs to wait for a while. But the robot cannot arrive later than the due time, which will cause the production process work improperly. Every time the robot feeds the goods for the production line, it is boxed, and each time you add the goods, you can do it all at once. When goods carried by the robot can no longer continue to be feed into the production line, the robot needs to return to the warehouse to re-add goods. Each robot can add goods to multiple production lines according to its own tasks, which will result in multiple trips. In the MMRMTFSP, it is necessary to plan the number of robots used to perform the transport and feed processes in the production process over a period and the time from warehouse to provide the location where the next transport arrives after goods are delivered once.

Research on mobile robots’ route and feeding planning is an area that has gradually emerged in recent years. Early researchers tried to build classic models to describe this problem. The feeding scheduling problem with a single robot was first described as an asymmetric traveling salesman problem (ASTP) problem and proved to be NP-hard. Dang et al.¹ proposed a heuristic-based genetic algorithm to solve the problem of a single mobile robot part-feeding planning. Mosallaeipour et al.² analyzed the mobile order of mobile robots, used decision toolbox to provide decision support for enterprises, and proposed a sequential part production matrix to determine feasible robot move strategies. Kats and Levner³ considered the problem of a mobile robot with m machines providing services, and a robotic mobility scheme including two cyclic is designed. Dang et al.⁴ constructed a mathematical model of mixed integers for mobile robot route planning problems, minimizing travel time as an optimization goal. Giordani et al.⁵ proposed a two-level decentralized multi-agent system and obtained the mobile robot route scheme through the multi-agent method. Buccieri et al.⁶ studied the transformation of contextual description into knowledge, using knowledge to improve the work of mobile robots, and improving the efficiency of mobile robots to perform tasks. Cárdenas et al.⁷ used the fuzzy logic theory, and the trajectory of the mobile robot is optimized in the dynamic model of the mobile robot. Liu et al.⁸ studied the mobile robot planning problem that can provide multiple services and analyzed the difficulty of single-capacity cache robots for scheduling. Flushing et al.⁹ studied the task assignment of mobile robot team, data routing, and road transmission problems and considered the task and actual data transmission within the scope of planning and scheduling. Booth et al.¹⁰ solved the problem of single-robot task planning using mixed-integer programming method and constraint programming method. Research of this kind of problem has certain similarities with satellite mission planning and flight scheduling, and related research can be used as a reference.^11
–13

In the existing research, there is limited research on the supply of raw materials for multi-robots to the production line, and the waiting cost of the robot to reach the production line ahead of the time window is not considered. This article will consider the above two aspects in the meanwhile and study the multi-trips feeding scheduling problem of mobile robots which is more suitable for actual production.

The main contribution of this article is to construct the mathematical model of MMRMTFSP with the objective of minimizing transportation cost and waiting cost and to analyze the difficulty of solving this problem. An improved genetic algorithm based on the characteristics of the problem is proposed. Our proposed algorithm can effectively solve the planning problem. The impacts of the number of tasks, the ability of the robot to carry goods, and the location of the warehouse on MMRMTFSP were analyzed.

The structure of this article is as follows. In the second part, a mathematical model will be constructed for MMRMTFSP, and the assumptions and constraints of the problem will be given. The solution method of MMRMTFSP will be given in the third part, including a mobile robot route build algorithm (RBA) and an improved hybrid genetic algorithm (IHGA). The fourth part will verify the algorithm proposed in this article. In the last part, the conclusions of this study and the further research directions will be given.

Model building

Description of MMRMTFSP

Before giving a mathematical model of the MMRMTFSP, an easy-to-understand description of the problem is given in the form of a language. There are several mobile robots that are responsible for supplying original goods to multiple production lines in the production hall. All robots start from a common starting point at the beginning of the production. This starting point is called warehouse. Each time a robot adds original goods to a production line, it can meet the amount required by the production line in the next stage of production. It takes a certain time for a robot to add goods to a production line. This time is called service time. Due to the differences among production lines in the production plant, the time required to supply original goods is also different. Periodic lack of goods and periodic replenishment of production lines create need for mobile robots to rationally plan to replenish original goods for production lines. Every mobile robot starts from warehouse and needs to arrive at a production line after a certain period of time. If it is within a time window, that is, the production line needs to replenish original goods to maintain normal production, goods will be replenished immediately. If it arrives earlier than time window, the mobile robot needs to wait until the time to start execution is allowed. Waiting will cause the robot to consume energy and generate waiting costs. If it is later than time window, production line cannot add goods, which is not allowed for the production process. Therefore, it is necessary to rationally plan routes of the mobile robot to provide original goods and minimize the cost of mobile robots in the process of providing goods while ensuring normal production of production lines. For mobile robots, cost includes two parts, one is transportation cost of transporting goods, and the other is waiting cost before time window when robots arrive at production lines. Total costs can be divided into two categories according to the starting time and the end time of transportation, from warehouse to a production line and from a production line to warehouse. Robot can supply goods for one production line, or it can continue to deliver goods after moving to another production line after supplying goods for one production line. When goods carried by a robot cannot be satisfied and continue to ensure normal production of production lines, the robot needs to return to warehouse to refill goods. Process of filling goods also takes time, which is called preparation time. Scheduling for mobile robots from warehouse to production line services, moving between multiple production lines, and returning to warehouse without goods are the problems that MMRMTFSP needs to solve.

Mixed-integer programming model

For mobile robots feeding scheduling problems, Dang et al.¹⁴ and Liu et al.⁸ respectively constructed mathematical models.^8,15 The mathematical model of MMRMTFSP we constructed draws on the mathematical models of the first two studies and improves on the proposed problems. This section will present a mixed-integer programming model to determine the availability of multiple robots to deliver goods to multiple production lines. Some basic abilities of the robot and the production workshop are given in advance. Robots no longer simply serve a production line, and if they carry enough goods, they can continue to serve other production lines. Based on the mixed-integer model, an IHGA will be used for MMRMTFSP to plan a reasonable route for mobile robots.

In this section, assumptions, variables, objective functions, and constraints are given separately.

Assumption

Each time a mobile robot provides services, it can meet the production needs of the next stage of the production line.

Time at which the mobile robot loads and feeds the goods is known.

Each robot can serve one or more production lines.

Distance between warehouse and production lines and that between each production lines are known.

Before the start of planning, the number of all goods on the production line is the largest.

Notations

T is the set of tasks. Where, when the task number is 0, it indicates that the mobile robot is at the warehouse location; M is the set of mobile robots; R is the set of routes; $r_{i}$ is the release time of task i; $d_{i}$ is the due time of task i; $p_{i}$ is the periodic time of task i; $f_{i k}$ indicates robot k is in the feeding time of task i. When in the warehouse, the working time is $w_{0 k}$ ; $t_{i j}$ is the traveling time of robot from the position of task i to the position of task j; $c_{i}$ is the part-feeding rate to machine of line i; $u_{i}$ is the maximum level of parts in line i; $v_{i}$ is the minimum level of parts in line i; $Q_{m}$ is the maximum amount of goods carried by robot.

\begin{array}{l} Decision variables : \\ x_{k l}^{i j} = {\begin{array}{l} 1 & \begin{array}{l} if robot k travels from location \\ of task i to location of task j \\ in route l \end{array} \\ 0 & otherwise \end{array} \end{array}

$s_{k}^{i}$ is the start time of the robot k to perform the task i.

When it is determined that the robot k is assigned a start time of the i-th task, the waiting time before the start of the (i + 1)-th task can be calculated by calculation, as shown in formula (1)

w_{k}^{i (i + 1)} = max [r_{i + 1} - s_{k}^{i} - f_{i} - t_{i (i + 1)}, 0], i \leq n - 1

$w_{k}^{i + 1}$ is the waiting time of the robot k for performing task i.

Calculation of production line time window can follow the calculation method of Liu et al.⁸ because it also follows the (s, Q) inventory policy. The calculation formula of the time window is shown as follows

p_{i} = (u_{i} - v_{i}) \cdot c_{i}, \forall i \in T \ {0}

r_{i} = r_{i - 1} + p_{i}, \forall i \in T \ {0}, r_{0} = 0

d_{i} = e_{i} + (v_{i} - 0) \cdot c_{i}, \forall i \in T \ {0}

Objective function

Minimize the sum of transportation cost and waiting cost of all mobile robots in the planning space, as the objective function of the mixed-integer programming model, as shown in equations (5) and (6)

\begin{array}{l} Objective function: \\ min F (x) (5) \end{array}

F (x) = \sum_{i = 1}^{T} \sum_{j = 1}^{T} \sum_{k = 1}^{M} \sum_{l = 1}^{R} t_{i j} x_{k l}^{i j} + \sum_{i = 1}^{T} \sum_{j = 1}^{T} \sum_{k = 1}^{M} \sum_{l = 1}^{R} w_{k}^{i j} x_{k l}^{i j}

Constraints

Constraints describe the conditions that mobile robots need to be met to maintain normal production of the production lines.

\begin{array}{l} Constraints: \\ r_{i} \leq s_{k}^{i}, \forall i \in T \ {0} (7) \end{array}

s_{k}^{i} \leq d_{i}, \forall i \in T \ {0}

\sum_{j \in T \ {0}} x_{1}^{0 j} = 1

\sum_{j \in T \ {0}} \sum_{l = 1}^{R} x_{1 l}^{0 j} \leq 1

\sum_{j \in T} \sum_{k \in M} \sum_{l = 1}^{R} x_{k l}^{i j} = 1, \forall i \in T \ {0}

\sum_{i \in T} \sum_{j \in T \ {0}} \sum_{k \in M} x_{k l}^{i j} \leq Q_{m}

x_{k l}^{i j} \in {0, 1}, \forall l \in R, \forall i, j \in T

Constraints (7) and (8) represent the time requirements for starting the task, and the execution task must be performed within the scope of the execution. Constraints (9) and (10) define that all mobile robots are in the warehouse position during the initial phase. The constraint (11) guarantees that each feeding operation is only allowed to be executed once. The constraint (12) indicates that the mobile robot cannot exceed its own capacity limit during transportation. The constraint (13) is a description of the range of values of the variables.

The MMRMTFSP is a very complicated issue. This is because every feeding job has a strict execution time range. It is necessary to wait too early to arrive at the production line and will not be able to provide service later than when the time window arrives. The ability of each robot is also limited, and the intelligence carries limited goods, which means that the number of services that can be provided is also limited. If there is no cargo, the mobile robot can only return to the warehouse to load the goods. These reasons make the problem have many possibilities for execution. The ideal robotic action plan can only be found using efficient optimization algorithms.

Methods for MMRMTFSP

Algorithm overall process

MMRMTFSP proposed in this article uses an IHGA, which combines the improved genetic algorithm with the tabu search to optimize the task sequence for performing the feeding. The RBA is used to construct a legal service route for the IHGA, to meet the working needs of the production line, and to calculate the cost of the mobile robot within the overall scheduling time range. The overall flow of the algorithm is shown in Figure 1.

Figure 1.

Overall algorithm flowchart.

When this algorithm needs to generate an initial solution, RBA* is used to construct a route. After reaching the usage threshold of RBA*, RBA is used directly for full routes construction, and tabu search algorithm is used to try to improve the task execution scheme. Use large populations for global optimization and small population local optimization. A variable for recording the dynamic population operation is λ, and finally the mobile robot moving route is outputted when the termination condition is satisfied. RBA will be introduced in the “Route build algorithm” section. The “Improved genetic algorithm” section describes the improved genetic algorithm. Tabu search will be introduced in the “Tabu search” section.

Route build algorithm

Route structure refers to time for robots to select appropriate travel time, arrival time, time to provide service for the next node, and time to return to the warehouse. This is the same as the vehicle routing problems with time windows (VRPTW) construct path.¹⁵ Route structure mainly includes two types of sub-contents, one is the route structure containing warehouse and the other is route construction from one production line to another.

Route structure containing warehouse is defined as RB ₀, which is divided into travel from warehouse and return warehouse. When the production line number in the route structure is 0, it is represented as a warehouse. When starting from the warehouse, we should minimize waiting time after the mobile robot reaches the production line. Therefore, you should just arrive at the production line at the release time of the production line and start the feeding work directly. In this way, the mobile robot does not need to wait for a period of time before starting service for the first time. The return of mobile robots from the production line to the warehouse is divided into two situations. One is that the goods carried by the robots have been used in the production of the production line, and it is unable to continue to serve other production lines and needs to return to the warehouse to refill the goods. Another situation is that all production lines can guarantee normal production within the scheduling time range, no need to feed the goods again by the robot, and the robot needs to return to the warehouse.

Route from one production line to another is defined as RB ₁. The reason for this process is relatively simple. When the mobile robot can still continue to provide services after providing service to one production line, it moves from one production line to another. When determining the starting point and ending point of the movement, the cost is fixed because the mobile robot has a cost in either the transportation or the waiting process. For a certain movement, the transportation cost is fixed. The mobile robot waits for a strict limit on the production line time window of the mobile end point, and after determining the route, the waiting cost can also be determined by calculation. The pseudo-code table of the path construction algorithm is shown in Algorithm 1.

Algorithm 1.

Route build algorithm (RBA).

To cooperate with the IHGA optimization process, we propose a route construction method for RBA*. This is a special RBA method. Different from the general RBA method, RBA* specifies the number of times each mobile robot provides services to the production lines. When the mobile robot reaches the upper limit of the number of services, it will return directly to the warehouse or it can continue service. The benefit of using this RBA is to facilitate the comparison of the impact of the combination of two different production lines on cost. Using the RBA* approach can be a good choice for individuals with more advantages in the early stages of IGA optimization.

Improved genetic algorithm

Genetic algorithm is a search algorithm that utilizes the evolution principle of population in biology, but the population improvement of basic genetic algorithm is not targeted, and the adaptability to many problems is poor, and the search efficiency is not high.¹⁶ This article proposes an improved genetic algorithm that satisfies the need of MMRMTFSP solution by improving the basic genetic algorithm. In the following, the main contents in the improved genetic algorithm will be introduced separately.

Coding

Before coding the genetic algorithm, we first need to number feeding jobs. Tasks’ numbers are grouped according to different production lines, and the number of each task is sorted according to the order of the task time windows in each group. The coding we use maps each task directly to the allele of the individual. Each allele represents a feeding task. The advantage of this coding method is that the genetic length of each individual in the genetic algorithm is equal to the length of the task sequence, and no additional decoding processing is required.

Initial solution generation

Generation of the initial solution directly affects subsequent process of optimization improvement. Initial solution is obtained in a heuristic-based approach. This heuristic-based approach sorts according to the time of production lines’ feeding jobs. To increase the diversity of population, we only identified the first feeding job, the 25%, 50%, and 75% of feeding jobs, if these positions are not integers (depending on the number of feeding jobs), rounded up way to determine, the other feeding job order is generated in a random way. By generating an initial solution in this way, the search space can be reduced.

Dynamic population strategy

Dynamic population strategy as an improved strategy of basic genetic algorithm can effectively improve the population improvement. Dynamic population strategy refers to dynamically adjusting the population size in the genetic algorithm according to the optimal performance of the genetic algorithm. A large population size can search for feasible solutions in a wide range, but there may be repeated searches, and search efficiency is not high, or performance is not good. Especially when the task size is large, the search is easy to be inefficient. When the population size is small, the search efficiency is high. However, it is easy to optimize the process only in the local space, only to achieve better results in the local range. Dynamic population strategy is a hybrid strategy that considers both large-scale population global search and small-scale population local search. A schematic diagram of a mixed dynamic population is shown in Figure 2. The blue arrow indicates a two-stage transition of the search process.

Figure 2.

Dynamic population strategy.

Firstly, large-scale populations are used for global search and improvement. When the performance of the optimal individual in the large-scale population search for several generations of populations still does not improve, a small-scale population local search is started. Small-scale populations look for better individuals in a localized range. Similar to large-scale population optimization, when small-scale population search for several generations of optimal individuals still does not improve, it returns to the large-scale population optimization process, which is counted as a stage of optimization. After that, continue the same optimization process as the previous stage. After several stages of improvement, optimization will achieve a better performance, but if this stage of evolution continues, it is difficult to further improve. Therefore, when the stage threshold $λ_{max}$ is reached, only small-scale populations are used for optimization, instead of large-scale population optimization.

Adaptive crossover

In the improved genetic algorithm, we propose a new way of crossing, called adaptive crossover. Adaptive crossover allows the algorithm to choose the crossover mode autonomously through the performance of different crossover modes. There are three crossover modes in the adaptive crossover, one is the intersection of single gene fragments, the middle-length gene fragments are crossed, and the long gene fragments are crossed. Single gene crossover refers to the exchange of only two genes in all gene fragments, as shown in Figure 3. Crossing a gene fragment causes a portion of the individual gene to be replaced from one location to another, as shown in Figure 4. Arrows in the figure indicate changes in gene position. The length of the allelic fragment of the medium-length gene fragment crossover is between the first two crossover operations.

Figure 3.

Single gene crossover.

Figure 4.

Fragment of genes crossover.

The choice of crossover method is similar to the adaptive search method^17,18 The three crossover modes have scores of $θ_{1}$ , $θ_{2}$ , and $θ_{3}$ , respectively. When a crossover operation is selected, the score $π_{1}$ is increased if the cost of the individual is lowered, and the score $π_{2}$ is increased if the cost is not changed, and the score $π_{3}$ is increased if the cost is increased.

According to the new score, new weights $ω_{1}$ , $ω_{2}$ , $ω_{3}$ for each cross operation are obtained. Adaptive selection is determined based on the specific gravity of the crossover operation in all cross operations. The weight calculation formula is as shown in equation (14)

ω_{i} = θ_{i} / \sum_{i = 1}^{3} θ_{i}

Adaptive operation can make the improved genetic algorithm autonomously select the crossover operation that is more conducive to improve the performance of the population according to the performance of different crossover modes. This crossover method can achieve a better level of optimization faster.

Mutation

Mutation is also an important part of improving genetic algorithm. Probability of mutation is much lower than crossover. Mutation helps individuals in population to change the original gene structure and obtain a new genetic structure, so that individual’s performance reaches a new level. In task sequence, mutations are made by exchanging one allele in one individual with another allele. Selected alleles are determined by random numbers, that is, the probability that each task is selected to perform mutation operation to change position is the same.

Tabu search

Tabu search is a classic heuristic rule.¹⁹ Hybrid strategy of combining tabu search and genetic algorithm can effectively prevent genetic algorithm from falling into the situation of repeated search. This is similar to Solomon’s use of tabu search for VRPTW, and Solomon uses tabu search to construct an initial solution.²⁰ We use tabu search as a means of searching for further improvements in genetic algorithms. Our tabu search and genetic algorithm processes are coordinated. Genetic algorithm obtains a new generation of populations and performs multiple search improvements. The starting point for search improvement is set to be in the top position gene segment after adaptive crossover. A total of two optional locations have been designed, depending on whether you are searching forward $\overset{\leftarrow}{S}$ or searching backward $\vec{S}$ . Selecting search direction is determined by a random number between [0, 1], and if the random number is between [0, 0.5], search for the forward position is adopted. If the random number is in the range of (0.5, 1), search is performed to the latter position. When it is determined that search is performed to the front position, the task at the foremost position in the gene segment is selected as the search start point. In the position search, the search starts from the task in the last position of the gene segment. In order not to reduce the efficiency of the improved genetic algorithm, tabu search only takes no more than three steps from the starting point forward or backward, that is, three task ranges.

When a better individual is obtained by searching for lower robots’ transportation and waiting cost, the latest neighborhood structure is recorded in the tabu table. This means that the next time such a neighborhood structure occurs, the positional relationship between the tasks saved in the tabu table will be discarded. When there are multiple records in the tabu table in the search process, the neighborhood structure is deleted from the tabu table, and population individuals can adopt the neighborhood structure.

Using tabu search to improve the individual performance of the population, while providing services for mobile robots to reduce costs, it does not fall into local optimization and is difficult to jump out like local search, which can balance the optimization process well.²¹ IHGA is formed by a combination of tabu search and improved genetic algorithm.

Experimental analysis

We have fully designed in the experimental part, which includes different types of tasks, different robots carrying goods, and warehouses in different locations. To verify the applicability of algorithm for different experimental scenarios and to propose a reasonable design of production lines, mobile robots, and warehouses. The proposed algorithms are implemented by Matlab2017a on a desktop with Core I7-7700 3.6 GHz CPU, 8 GB memory, and Windows 7 operating system. We have chosen a local search (LS), two heuristic algorithms: nearest production line position priority (H1) and farthest line position priority (H2).

First, we compare algorithm planning effects under different task scales. Results are presented in Table 1. T1, T2, and T3 in the table represent 10 tasks, 20 tasks, and 30 tasks, respectively. Two search algorithms were run 30 times respectively, and the respective average and optimal values were taken as comparison criteria. In the three scenarios of T1–T3, mobile robots obtained by IHGA provide the lowest cost. Moreover, advantages of the algorithm become more apparent as the number of tasks increases. This reflects that our proposed algorithm is more suitable for scenarios with larger task sizes, because the IHGA can better find better solutions from search space when search space is larger. After that, we consider the impact of different warehouse locations on the performance of algorithms under 10 tasks. Results are presented in Table 2.

Table 1.

Results of different task scales.

Instance	IHGA		LS		H1	H2
Instance	Average	Best	Average	Best	H1	H2
T1	5834	5080	9269	7783	12,898	10,613
T2	17,901	14,569	27,029	20,988	28,368	24,156
T3	38,876	34,437	55,743	46,344	61,815	59,475

IHGA: improved hybrid genetic algorithm.

Table 2.

Results of different warehouse locations under 10 tasks.

Instance	IHGA		LS		H1	H2
Instance	Average	Best	Average	Best	H1	H2
L1	5834	5080	9269	7783	12,898	10,613
L2	5684	5070	7881	5100	8863	11,875
L3	5647	5190	8458	6352	10,945	10,403

IHGA: improved hybrid genetic algorithm.

In Table 2, L1 indicates that the warehouse is located at the left-numbered production line, L2 indicates that the warehouse is at the middle position, and L3 indicates that the warehouse is located at the right-numbered production line. It can be seen from the experimental results that when there are 10 tasks, the warehouse is located in the middle position, which can save the cost of the service provided by the robot. And when the warehouse is on the right side, the cost is the highest. We also compared the choice of warehouse locations in 20 tasks situations to make it more reasonable.

L4 indicates that the warehouse is on the left side, L5 indicates that the warehouse is in the middle, and L6 indicates that the warehouse is on the right side. As can be seen from Table 3, when the warehouse is located on the left side, the cost incurred is the lowest. Compared to results of different warehouse locations under 10 missions, the choice of warehouse location has a greater impact on results. At the same time, the choice of warehouse location is more obvious for the other three comparison algorithms. We also compared the planning performance of different warehouse locations with a task number of 30. Results are shown in Figure 5.

Table 3.

Results of different warehouse locations under 20 tasks.

Instance	IHGA		LS		H1	H2
Instance	Average	Best	Average	Best	H1	H2
L4	17,901	14,569	27,029	20,988	28,368	24,156
L5	19,468	15,499	30,144	25,325	35,606	29,553
L6	19,591	18,782	27,881	20,213	31,668	31,294

IHGA: improved hybrid genetic algorithm.

Figure 5.

Results of different warehouse locations under 30 tasks.

As can be seen from Figure 5, when the number of tasks is 30, the choice of warehouse location has a significant impact on the result. L7 indicates that the warehouse is on the left side, L8 indicates that the warehouse is in the middle, and L9 indicates that the warehouse is on the right side. Similar to the situation of 20 tasks, cost is the lowest when the warehouse location is closest to the left. Secondly, it is in the middle position, and the highest cost is that the warehouse is at the rightmost position. It can also be seen in the figure that performance of LS is better than that of the other two heuristic algorithms in the L7 scene, and performance in L8 and L9 is not ideal. This shows that after the task size is increased, the search space will make the neighborhood search easy to fall into local optimization situation, and it is difficult to get a lower cost scheme. After discussing the impact of warehouse location, we also compared the impact of mobile robots with different cargo carrying capabilities on the planning results. In this experiment, the number of tasks is 10, and warehouse was in the middle position. Results are presented in Table 4.

Table 4.

Planning results for different goods carrying capacity.

Instance	IHGA		LS		H1	H2
Instance	Average	Best	Average	Best	H1	H2
C1	5511	4930	7516	5540	10,355	12,868
C2	5834	5080	9269	7783	12,898	10,613
C3	5690	4840	5690	4840	13,602	11,984
C4	5492	4875	9100	6263	13,702	9575

IHGA: improved hybrid genetic algorithm.

In Table 4, C1–C4 respectively indicate that each robot can carry two to five units of goods. It can be seen from results that when robots’ ability to carry goods increases, cost of service provided by robots shows a trend of decreasing first and then rising. When a robot carries four units of goods, the cost is the lowest.

After that, we verified genetic algorithm parameters in IHGA. Genetic algorithm has the most important impact on optimization results, because route construction and tabu search are based on the task execution order generated by this algorithm. In genetic algorithm, crossover and mutation are important evolution processes of population, and this process directly affects the final optimization effect. We first compare optimization effects of different crossover probabilities. Results are shown in Figure 6.

Figure 6.

Different crossover probability results.

In Figure 6, we designed four experiments with crossover probabilities of 0.95, 0.9, 0.85, and 0.8. Among four crossover probabilities, the crossover probability of 0.9 yielded the best optimization results, followed by the crossover probability. It is 0.85, followed by an optimization result with a crossover probability of 0.95. The highest cost is the task execution plan with a crossover probability of 0.8. It can be said that in the case of 20 tasks, it is more desirable to set the crossover probability of 0.9. After that, we compare effects of different mutation probabilities on mission planning results. Experimental scene settings and crossover probability are designed identically. Results are shown in Figure 7.

Figure 7.

Different mutation probability results.

Mutation probabilities are set to 0.1, 0.05, and 0.02, respectively. As can be seen from the results of Figure 7, under 20 task scales, mutation probability value setting of 0.05 is the most appropriate. The second best performance is the result of a mutation probability of 0.1. Optimization result with a mutation probability of 0.02 is the worst.

We conducted several experiments on different task scales, different warehouse locations, different robots, different mutation probabilities, and crossover probabilities. Based on the above experimental results, our proposed algorithm can effectively solve MMRMTFSP. Moreover, IHGA algorithm is more advantageous in the case of a larger task scale. This reflects that dynamic population strategies and adaptive crossover are more suitable for large-scale applications. IHGA can be used well in actual production process to guide mobile robots in planning the feeding of goods for production lines.

Conclusion

This article studied a route planning problem of using mobile robots to feed goods in production lines in real production. Different from previous research, our MMRMTFSP involves multiple robots, each of which can provide multiple services for production lines within its capabilities. To solve this problem, we constructed a mixed-integer programming model. The difficulty of this type of problem mainly comes from the fact that each production line has strict time limits for providing goods to maintain production and the ability of a robot to carry goods.

To effectively solve MMRMTFSP, we propose an IHGA. This algorithm combines improved genetic algorithm with tabu search algorithm and uses tabu search algorithm to further improve the task execution scheme obtained by genetic algorithm. In the improved genetic algorithm, we used dynamic population strategy and adaptive crossover to improve the performance of genetic algorithm. Through simulation experiments, we can see that our proposed algorithm can effectively solve this planning problem of mobile robots providing goods for production lines and provided guidance for the design of warehouse location, the number of tasks, and the choice of robots. It has a good practical application prospect.

In future research, we will have more capable robots, such as robots that can assist with some planning problems in production process. Meanwhile, artificial intelligence adopted into the mission planning process is also a focus of our next research. In addition, a multi-robots collaborative framework and online scheduling of multi-robot real-time response are also a possibility of research. In this case, task execution plan of mobile robots can be adjusted in time according to actual production situation to ensure that production process is not affected by unexpected situations.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: National Natural Science Foundation of China (Grant/Award Number: 71690233 and 61473301).

ORCID iD

Yan-Jie Song

References

Dang

Nielsen

Steger-Jensen

et al. Scheduling a single mobile robot for part-feeding tasks of production lines. J Intell Manuf 2014; 25(6): 1271–1287.

Mosallaeipour

Nejad

Shavarani

et al. Mobile robot scheduling for cycle time optimization in flow-shop cells, a case study. Prod Eng 2018; 12(1): 83–94.

Kats

Levner

. Parametric algorithms for 2-cyclic robot scheduling with interval processing times. J Sched 2011; 14(3): 267–279.

Dang

Nielsen

Steger-Jensen

. Mathematical formulation for mobile robot scheduling problem in a manufacturing cell. In: IFIP international conference on advances in production management systems, vol. 384, Stavanger, Norway, September 2011 pp. 37–44. Berlin: Springer, 2012.

Giordani

Lujak

Martinelli

. A distributed multi-agent production planning and scheduling framework for mobile robots. Comput Ind Eng 2013; 64(1): 19–30.

Buccieri

Perritaz

Mullhaupt

et al. Velocity-scheduling control for a unicycle mobile robot: theory and experiments. IEEE Trans Robot 2009; 25(2): 451–458.

Cárdenas Selene

Castillo

Aguilar

et al. Tracking control for a unicycle mobile robot using a fuzzy logic controller. Stud Fuzz Soft Comput 2007; 208: 243–253.

Liu

Xiang

et al. Mobile robot scheduling with multiple trips and time windows. In: 13th international conference on advanced data mining and applications, ADMA 2017, Vol. 10604, Singapore, 5–6 November 2017. Cham: Springer.

Flushing

Luca

Gianni

ADC

. Simultaneous task allocation, data routing, and transmission scheduling in mobile multi-robot teams. In: 2017 IEEE/RSJ international conference on intelligent robots and systems, IROS 2017, Vancouver, BC, Canada, 24–28 September 2017.

10.

Booth

KEC

Tran

Nejat

et al. Mixed-integer and constraint programming techniques for mobile robot task planning. IEEE Robot Autom Lett 2017; 1(1): 500–507.

11.

Song

Zhou

Zhang

et al. A framework involving MEC: imaging satellites mission planning. Neural Comput Appl 2019; 1–12.

12.

Sherali

Bae

Haouari

. A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture. Ann Oper Res 2013; 210(1): 213–244.

13.

Jiang

Barnhart

. Dynamic airline scheduling. Transport Sci 2009; 43(3): 336–354.

14.

Dang

Nielsen

Stegerjensen

et al. Scheduling a single mobile robot for part-feeding tasks of production lines. J Intel Manuf 2014; 25(6): 1271–1287.

15.

Vitória

Morabito

Reimann

. Vehicle routing with multiple deliverymen: modeling and heuristic approaches for the VRPTW. Eur J Oper Res 2012; 218(3): 636–647.

16.

Goncalves

de Magalhaes-Mendes

Resende

MGC

. A hybrid genetic algorithm for the job shop scheduling problem. Comput Ind Eng 2003; 167(1): 77–95.

17.

Kolisch

Drexl

. Adaptive search for solving hard project scheduling problems. Nav Res Logist 1996; 43(1): 23–40.

18.

Huang

Yang

Zhou

et al. Novel adaptive search method for bearing fault frequency using stochastic resonance quantified by amplitude-domain index. IEEE Trans Instrum Meas 2019; (99): 1–13.

19.

Solomon

. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 1987; 35(2): 254–265.

20.

Crama

Kolen

AWJ

Pesch

. Local search in combinatorial optimization. In: Braspenning

Thuijsman

Weijters

AJMM

(eds) Artificial neural networks. Lecture notes in computer science, Vol. 931. 2003, pp. 157–174. Berlin, Heidelberg: Springer.

21.

Bent

Van Hentenryck

. A two-stage hybrid local search for the vehicle routing problem with time windows. Transport Sci 2004; 38(4): 515–530.

Multi-mobile robots and multi-trips feeding scheduling problem in smart manufacturing system: An improved hybrid genetic algorithm

Abstract

Keywords

Introduction

Model building

Description of MMRMTFSP

Mixed-integer programming model

Assumption

Notations

Objective function

Constraints

Methods for MMRMTFSP

Algorithm overall process

Route build algorithm

Improved genetic algorithm

Coding

Initial solution generation

Dynamic population strategy

Adaptive crossover

Mutation

Tabu search

Experimental analysis

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References