Ant colony optimization model with characterization-based speed and multi-driver for the refilling system in hospital

Abstract

Different optimization algorithms are used in fast medicine dispensing system to improve the efficiency of refilling. To achieve rapid replenishing of the manipulator and improve efficiency in pharmacy automation system. An ant colony optimization algorithm, which is named ant colony optimization model with characterization-based speed and multi-driver, is proposed. Simulations of different picking points by order-picking mode, particle swarm optimization, particle swarm optimization with characterization-based speed and multi-driver, genetic algorithm, genetic algorithm with characterization-based speed and multi-driver, ant colony optimization, and ant colony optimization with characterization-based speed and multi-driver were carried out, and practical tests of different picking points by order-picking mode and ant colony optimization with characterization-based speed and multi-driver were done in a hospital. The data were collected and comparisons were made. Comparisons among order-picking mode, particle swarm optimization, genetic algorithm, particle swarm optimization with characterization-based speed and multi-driver, genetic algorithm with characterization-based speed and multi-driver, ant colony optimization, and ant colony optimization with characterization-based speed and multi-driver are made. Practical test results in hospital show that the ranges of optimization ratios of the average time values tested by ant colony optimization with characterization-based speed and multi-driver and the order-picking mode are 12.4%–40.3% when the picking points are between 5 and 20. Ant colony optimization with characterization-based speed and multi-driver is suitable for the refilling process in fast medicine dispensing system. It is capable of finding the refilling route which spends the shortest refilling time, and this meets the requirements in hospital.

Keywords

Engineering optimization industrial engineering computer-assisted engineering medical devices design optimization ant colony optimization

Introduction

Logistics systems for transportation and warehouse storage can solve problems regarding production and service sectors.^1,2 In most modern warehouses, the efficiency of order picking is related to multiple factors including layout designs, storage assignments, batching, zoning, and picking route. Among these factors, order-picking route, which should be adjusted dynamically according to the real-time information in warehouse management, is considered to have the highest flexibility.³ Meanwhile, order picking is one of the main activities performed due to its operational costs and time.^2,4 A high percentage of travel time is observed in an order-picking mode. Order picking accounts for not less than 55% of the total costs in warehouse operations.^5–7 Therefore, efficient policies for picking and refilling routing have been selected by warehouses, which have a large potential for reducing costs and time. Picking route strategy is an influential factor in warehouse operations.

With the development of intelligent logistics technology used in modern hospitals, management in pharmacies and medicine access mode has been converted from labor management mode to automated management mode. Since the 1990s, automatic control, computer network, medical Internet of Things, operations research, and machine manufacturing technology have been merged into the pharmacy automation system (PAS), and it is used in countries such as Germany, the United States, Japan, and Holland.⁸ Automation equipment in the PAS has achieved digitizing, networking, and automation of pharmacy management. The fast medicine dispensing system (FMDS) has been developed as one of the automated medicine dispensing systems in the PAS. The system has achieved the goal of providing automation in medicine refilling, storage, and dispensation using a computer control system to replace traditional human-based drug administration and distribution. Drug administration and distribution are important jobs. Therefore, an additional defense, such as FMDS-assisted medication administration and distribution, is needed to intercept drug administration errors and improve safety of the patients.^9,10 The pharmacist may use automatic operation, which provides fast medicine delivery, rapid and accurate medicine dispensation, intensive medicine storage, and effective management. Automatic operation processes improve the distribution rate and storage rate of medicine dispensing systems and utilize automation, integration, and intelligentization of medicine logistics. The FMDS research mainly focuses on automatic medicine replenishing of box-packed drug, medicine-intensive storage, and automatic medicine dispensation. In some countries, medicine refilling is conducted by human¹¹ and manipulators,¹² which have low efficiency. The order-picking mode (OPM) has been applied to the automatic refilling system by the manipulator whose working principle is similar to shooting^13,14 to optimize the traditional manual refilling and traditional manipulator process. The OPM was designed to find the nearest picking point in the X-direction and then find the nearest picking point in the Y-direction. The OPM was simply and universally used in the FMDS, but the route selection mode of the OPM cannot guarantee that the next point chosen is the nearest one, and the value of route is an exact value. It is an optimal route selection mode that the closest point is chosen for the next point. Therefore, the OPM for refilling has still not been fully optimized for practical use, and as a result, optimization is needed.

Some optimization algorithms, which are based on genetic algorithm (GA) and particle swarm optimization (PSO), and ant colony optimization (ACO) are used in the FMDS to improve refilling efficiency. In terms of searching the optimized route in the FMDS, both the GA¹² and the PSO achieved optimized results by effectively decreasing the route values or the quantity of the manipulator. Although the structure of the PSO is simple and the time that the computer spends on single iteration is short, it needs more iterations to achieve optimized solution due to few adjustable parameters. In contrast, the accuracy of the ACO is high, notwithstanding the structure of the ACO is complex and the time that the computer spends on single iteration is long.¹⁵ In general, when the amount of ants and the amount of picking points are close or the same (between 5 and 15), the ACO is better than the GA in searching optimized solution of traveling salesman problem (TSP).¹⁶ When the numbers of picking points are between 0 and 20, the ACO is more suitable than any other algorithm in searching optimized solution.

The ACO, which is a new heuristic and biomimetic algorithm proposed by Italian scholar M Dorigo et al.¹⁷ in 1991, is suitable for refilling. The ACO was widely applied in different fields such as the TSP,^18,19 vehicle routing problem (VRP),²⁰ quadratic assignment problem (QAP),^17,21 and network traffic management,^3,22 and good results have been obtained. The TSP was first described in the knight’s tour problem (KTP) in 1759²³ and was proposed as a mathematical program by Danzig et al. in 1959. TSP is a member of the set of non-deterministic polynomial complete problems (NP-complete problems).²⁴

Most of the previous studies on the automatic pharmacy system focus on simulation programs without considering the effect of the variation in speed between two storage positions. This article reports a picking routing mathematical model modified by the ant colony optimization with characterization-based speed and multi-driver (ACO-SD) considering the variation in speed which plays a significant role in the FMDS. The simulation results are applied in a hospital as a new operation system. An FMDS is established, including a new loading medicine manipulator, to test our simulation results. The FMDS is used in a hospital to collect data to compare the simulation results. The simulation method is modified by the addition of speed factor, and an optimized refilling process is proposed and applied in the FMDS, instead of the old mathematical model.

Problem described and model established

The refilling process consists of the manual refilling medicine process by a pharmacist, the refilling route process by the manipulator, and the automatic refilling medicine process from the manipulator to the medicine storage by the beating module of the manipulator. The refilling route process is related to sequence scheduling, which is a medicine logistics system for the FMDS.

Picking scheduling established

Figure 1 presents the management system of the FMDS. The management system can be divided into three modules which are module-management module, refilling module, and alarm module. The refilling module is divided into six sequential steps:

Medicine information entry and verification. Each medicine has its own two-dimensional (2D) code. Medicine boxes with 2D code are scanned by a 2D code scanner. The code information is read by a computer. The name and the information of the medicine are shown on the interface of refilling medicine for a pharmacist.

Shortages and location of the medicine. When the medicine is in the management system and the medicine is selected, the location of the medicine and the information of shortages will be entered in the picking point table. Meanwhile, information of the medicine, including 2D of the medicine, medicine name, and place of production, is shown on the interface of the refilling medicines.

Sequence scheduling table established. Sequence scheduling table is an important part in the refilling process. When the order of picking points is arranged by path selection algorithm, the sequence scheduling table is established.

Quantity input. The prompt of total shortages for the medicine is shown on the interface of refilling medicine. The quantity of refilling medicine should not be more than total shortages, and the input value of total shortages is entered by a pharmacist.

Movement of the manipulator. The refilling process starts from the initial position and then replenishes all picking points according to the sequence scheduling table. This research focuses on the sequence arrangement.

Medicine information modified. When the refilling process is finished, the medicine information is modified to keep the correct amount of medicine storage in the management system of the FMDS.

Figure 1.

Management system of FMDS.

Definition of refilling process

Medicine refilling by the FMDS is carried out by the loading medicine manipulator according to the amount of medicine required by different storage containers. Mathematical abstract models of storage spaces with 2D distributions are made. The medicine storages required to replenish medicine are defined as picking points in this model.

Definition of the initial picking point

The manipulator remains stationary at the initial packing point defined as (0, 0) before running the program. The medicine loading manipulator starts from the initial picking point. After completing the picking point sequence, the manipulator returns back to the initial picking point.

Definition of the general picking point

One side of the storage spaces is a working interface, which contains m rows and n columns, in the rectangular region as described in Figure 2(a) and (b). The crossing points of the X and Y coordinates are located far to the left of one storage space represented as (x_i, y_j), where x_i is column i in the X-direction and y_j is row j in the Y-direction.

Figure 2.

Refilling processes of (a) the OPM and (b) the ACO-SD.

Figure 3.

Convergence results of different picking points by different algorithms: (a1) using the PSO with 5 picking points, (a2) using the PSO with 10 picking points, (a3) using the PSO with 20 picking points, (b1) using the GA with 5 picking points, (b2) using the GA with 10 picking points, (b3) using the GA with 20 picking points, (c1) using the ACO with 5 picking points, (c2) using the ACO with 10 picking points, (c3) using the ACO with 20 picking points, (d1) using the PSO-SD with 5 picking points, (d2) using the PSO-SD with 10 picking points, (d3) using the PSO-SD with 20 picking points, (e1) using the GA-SD with 5 picking points, (e2) using the GA-SD with 10 picking points, (e3) using the GA-SD with 20 picking points, (f1) using the ACO-SD with 5 picking points, (f2) using the ACO-SD with 10 picking points, and (f3) using the ACO-SD with 20 picking points.

Definition of the speed of drivers

In terms of the traditional method, both the X- and Y-directions display movement of the loading medicine manipulator, which is considered as a uniform motion process in the study, regardless of the velocity of the process between one medicine storage and another. In the new model, the horizontal velocity of the loading medicine manipulator is v_x and the vertical velocity is v_y.

Definition of the picking time

The picking time in the refilling process is related to the type and shortages of the medicine. The operation time of medicine administration and the time of medicine dropping from the manipulator to storage space are not included in the picking time in the theoretical calculation.

Definition of the refilling route

The refilling process for each picking point is regarded as a non-repeating route by order from A to E. After finishing all the picking points, the manipulator returns back to the initial picking point (Figure 2).

According to the model definition, the three-dimensional (3D) picking process of the warehouse was converted to a 2D TSP.

The ACO model with characterization-based speed and multi-driver

ACO, which is a heuristic algorithm successfully applied to several NP-hard combinatorial optimization problems, and first to TSP, consists of using a population of ants to collectively solve an optimization problem to discover the minimum cost paths through a certain graph, while respecting specific constraints.²⁵

Mathematical model of the ACO

The TSP may be defined on a graph G = {V, E}, where V = {V₀} ∪ N is the vertex set and E is the arc set. The initial position of the manipulator is defined as V₀ and is called the initial picking point. V₀ is mentioned in the second paragraph of section “Definition of refilling process.” The set of storages, which is needed to add drugs, is defined as N = {V₁, V₂,…, V_n}. N is the quantity of the storage. E = {(V_i, V_j)| V_i, V_j ∈ V} is the arc set. The path is defined as $d_{V_{i}, V_{j}}$ between two vertices i and j in G and satisfies the unequal relationship of a triangle, such as $d_{V_{i}, V_{k}} + d_{V_{j}, V_{k}} \geq d_{V_{i}, V_{j}}, V_{i}, V_{j}, V_{k} \in V$ . The distance from picking i to picking j is defined as $d_{ij} (i, j = 1, 2, \dots, n)$ , and the number of all picking is n. $b_{i} (t)$ indicates the number of ants at t point in time in picking i, and the total number of ants is $m = \sum_{i = 1}^{n} b_{i} (t)$ . The amount of pheromone is defined as $τ_{ij} (t)$ at t point in time on the edge between picking point i and picking point j. The amount of pheromone is equal to $Δ τ_{ij} (t) = 0 at t = 0$ . Over time, the pheromone path is changed because of new pheromone being applied and old pheromone evaporating.^26,27 $ρ$ is set as the evaporation coefficient of the pheromone and shows the speed of evaporation. When all ants completed one tour, the pheromone on each path is given as

τ_{ij} (t + 1) = (1 - ρ) τ_{ij} (t) + Δ τ_{ij} (t)

(1)

in which $Δ τ_{ij} (t) = \sum_{k = 1}^{m} Δ τ_{ij}^{k} (t)$ .

The concentration of pheromone on a path is defined as $Δ τ_{ij} (t)$ . $Δ τ_{ij}^{k} (t)$ is expressed as the pheromone which is released on the path from picking point i to picking point j by ant k. The pheromone value is dependent on the ant’s performance. A shorter path means more pheromone is applied by the unit. Ant-cycle is used in this article^28,29

\begin{matrix} Δ τ_{ij}^{k} (t, t + 1) = {\begin{matrix} Q / L_{k} & the path from picking i to picking j by the ant k \\ 0 & other \end{matrix} \end{matrix}

(2)

P_{ij}^{k} = {\begin{matrix} \frac{τ_{ij}^{α} η_{ij}^{β}}{\sum_{j \in allowe d_{k}} τ_{ij}^{α} η_{ij}^{β}} & if j \in allowe d_{k} \\ 0 & other \end{matrix}

(3)

$allowe d_{k} = (V_{1}, V_{2}, \dots, V_{n}) - tab U_{k}$ represents the collection of locations that could be chosen by ant k. $tab U_{k} (k = 1, 2, \dots, m)$ is the taboo list of ant k. The visited location is recorded in the taboo list, and the memory of ant k is considered.³⁰

The inverse distance between picking point i and picking point j is defined as $η_{ij} (t)$ , $η_{ij} (t) = 1 / d_{ij}$ . $α$ is the residual degree of information on the edge between picking point i and picking point j. $β$ is the heuristic degree of information. Both of them could be changed by the user.

ACO-SD

It is found that in the process of TSP solved by the ACO, there is only one default driver while the ant is moving from picking point i to picking point j. And the direction of the default driver is from picking point i to picking point j which is the same as the ant. In previous practice studies, the optimization effect is significant with the influence factors, the different directions of driving force, and the speed, but neither of them are not considered in the ACO model.³¹

$v_{x}$ denotes the speed in the direction of X, and $v_{y}$ denotes the speed in the direction of Y. $L_{ij}^{x}$ is the distance from picking point i to picking point j in the direction of X, and $L_{ij}^{y}$ is the distance from picking point i to picking point j in the direction of Y. Therefore, the time from picking point i to picking point j has two values, $t_{ij}^{x}$ and $t_{ij}^{y}$ . $T_{ij}$ stands for the travel time between picking point i and picking point j

T_{ij} = {\begin{matrix} t_{ij}^{x} = L_{ij}^{x} / v_{x} if t_{ij}^{x} \geq t_{ij}^{y} \\ t_{ij}^{y} = L_{ij}^{y} / v_{y} if t_{ij}^{x} ≺ t_{ij}^{y} \end{matrix}

(4)

L_{k} = {\begin{matrix} L_{ij}^{x} if t_{ij}^{x} \geq t_{ij}^{y} \\ L_{ij}^{y} if t_{ij}^{x} ≺ t_{ij}^{y} \end{matrix}

(5)

η_{ij} (t) = \frac{1}{T_{ij}}

(6)

Combining equations (2) and (3), the new transfer probability between picking point i and picking point j can be calculated. $L_{k}$ is altered to affect the concentration of pheromone. And $η_{ij} (t)$ is altered which is based on the time of movement from picking point i to picking point j.

Algorithm pseudo-code

The OPM and the ACO-SD approach pseudo-codes are shown in Tables 1 and 2.

Table 1.

Order-picking mode algorithm.

Algorithm 1 (order-picking mode algorithm, OPM)
Input: Medicine name or Medicine ID Output: refilling route for medicine storages // Creating three tables (i.e. initial data table, process data table, refilling data table)// // All storage numbers and shortages of the medicine for Medicine name or Medicine ID into initial data table// Begin While (initial data table ! = null) Fori = min{i\| i ∈ A} Forj = min{j\| j ∈ B} If (U_ij is correct) ΣY = ΣU + U_ij Let (i, j, U_ij) into the process data table Delete the information of ij in the initial data table End if Else Alarm End for End for End while Return ΣU on the interface of refilling medicines Let all process data table into the refilling data table Clear the process data table Return refilling data table While (refilling data table ! = null) The refilling process is operating Delete the information of ij in the refilling data table when the refilling completion Alter the shortage of picking point ij in the management system End while Stop

Algorithm 1 (order-picking mode algorithm, OPM)

Input: Medicine name or Medicine ID
Output: refilling route for medicine storages
// Creating three tables (i.e. initial data table, process data table, refilling data table)//
// All storage numbers and shortages of the medicine for Medicine name or Medicine ID into initial data table//
Begin
While (initial data table ! = null)
Fori = min{i| i ∈ A}
Forj = min{j| j ∈ B}
If (U_ij is correct)
ΣY = ΣU + U_ij
Let (i, j, U_ij) into the process data table
Delete the information of ij in the initial data table
End if
Else
Alarm
End for
End for
End while
Return ΣU on the interface of refilling medicines
Let all process data table into the refilling data table
Clear the process data table
Return refilling data table
While (refilling data table ! = null)
The refilling process is operating
Delete the information of ij in the refilling data table when the refilling completion
Alter the shortage of picking point ij in the management system
End while
Stop

Table 2.

Ant colony optimization mode algorithm.

Algorithm 2 (ant colony optimization model characterization-based speed and multiple drivers’ algorithm, ACO-SD)
Input: Medicine name or Medicine ID Output: refilling route for medicine storages // Creating two tables (i.e. initial data table, and complete data table)// // All storage numbers and shortages of the medicine for Medicine name or Medicine ID into initial data table// Begin Initialize α, β, τ₀, ρ, Q, n, Nc_max For every edge (i, j) τ_ij(0) = τ₀ End for While (nc <= Nc_max) Initialize length_refilling, tabU_k, and allowed_k For (k = 1; k < m; k++) While (allowed_k ! = null) Build tabU_k by applying n − 1 times the following step tabU_k = tabU_k + (i, j), and allowed_k = allowed_k− (i, j) Choose the next node j probability, calculate P_ij^k according to formulas (2), (3), and (6) Calculate the optimal tour of ant k End while Update the historical optimal length_refilling For every edge (i, j) Update the pheromone according to formulas (2) and (5) End for End for End while Output the results in the complete data table Return the complete data table Stop

Algorithm 2 (ant colony optimization model characterization-based speed and multiple drivers’ algorithm, ACO-SD)

Input: Medicine name or Medicine ID
Output: refilling route for medicine storages
// Creating two tables (i.e. initial data table, and complete data table)//
// All storage numbers and shortages of the medicine for Medicine name or Medicine ID into initial data table//
Begin
Initialize α, β, τ₀, ρ, Q, n, Nc_max
For every edge (i, j)
τ_ij(0) = τ₀
End for
While (nc <= Nc_max)
Initialize length_refilling, tabU_k, and allowed_k
For (k = 1; k < m; k++)
While (allowed_k ! = null)
Build tabU_k by applying n − 1 times the following step
tabU_k = tabU_k + (i, j), and allowed_k = allowed_k− (i, j)
Choose the next node j probability, calculate P_ij^k according to formulas (2), (3), and (6)
Calculate the optimal tour of ant k
End while
Update the historical optimal length_refilling
For every edge (i, j)
Update the pheromone according to formulas (2) and (5)
End for
End for
End while
Output the results in the complete data table
Return the complete data table
Stop

The OPM algorithm is simple and practical for the refilling process, and its disadvantage is that the sequence of picking point optimization is unconsidered. The OPM can be described in the following steps:

Step 1. In terms of receiving messages of refilling medicine, there are two types of textboxes, 2D textbox and name textbox. 2D textbox entered with medicine ID is scanned by a 2D code scanner. Name textbox is entered with medicine name by a pharmacist. After the 2D textbox or name textbox receives messages, the medicine required in the message will be selected. When name textbox receives messages, due to the same medicines made by different pharmaceutical companies, it requires the pharmacist to double click the correct medicine which needs refilling. When 2D textbox receives messages, only the correct medicine is selected.

Step 2. As soon as the initial data table obtains information regarding refilling, OPM algorithm starts to run. The selection method is in accordance with the rules: the nearest number i on the X-axis in the initial data table is selected first and the nearest number j on the Y-axis is placed in the forefront. If the number of pickings is the same as on X-axis, the first picking selected will be arranged first. The vertex set on the X-axis of the picking point $V_{ij}$ is A and the vertex set on the Y-axis of the picking point $V_{ij}$ is B.

Step 3. The shortage of the last medicine storage, $U_{ij}$ , is entered in the process data table and it is deleted from the initial data table. The total shortage of medicine storages is defined as $\sum U$ . The alarm goes off when there is a mistake in the data. In terms of circulation, after the program deals with all the information in the initial table, the process data table completes collecting information, and then the program jumps out of circulation.

Step 4. The refilling data table is copied from the process data table, and the process data table is cleared. The amount of medicine in the refilling is shown in the interface of refilling medicines; the pharmacist needs to check and enter the value and determine the refilling process, which is mentioned in section “Picking scheduling established.”

Step 5. The manipulator runs in accordance with the sequence of medicine storages in the refilling data table. After completion of refilling process of the medicine storage, the information of the medicine storage will be deleted in the refilling data table and the information will be updated in the management system. After completion of refilling process, the refilling data table returns to null.

The ACO-SD algorithm is a novel algorithm for refilling process, whose object is to optimize the refilling time. To describe the ACO-SD procedures, nc is the index of iteration number, and Nc_max is the maximum iteration number as the stop rule. k = {1, 2,…, m} is the index of the ant, tabU_k is the set of picking points that ant k has passed, and correspondingly, allowed_k = V_c − tabU_k represents the set of picking points available for the next step, and V_c is the set of picking points that medicine storages are selected to replenish in the refilling process. The ACO-SD can be described in the following steps:

Step 1. This process is the same as Step 1 in the OPM.

Step 2. All parameters are initialized. The pheromone information for every edge is evaluated as τ₀.

Step 3. The main loop starts. If nc is more than Nc_max, the program goes to Step 8.

Step 4. m is the amount of ants, and the m ants are set randomly on n picking points.

Step 5. Build tabU_k by applying n − 1 times the following step. Medicine storage of (i, j) is put into tabU_k and is deleted in allowed_k. Choose the next node j probability and calculate P_ij^k according to formulas (2), (3), and (6).

Step 6. Update the historical optimal solution length_refilling.

Step 7. Calculate the pheromone information according to equations (2) and (5) and update τ_ij(t); iteration nc adds one and then the program goes to Step 3.

Step 8. Output the results from the complete data table and return the complete data table for refilling.

Step 9. The manipulator runs in accordance with the sequence of medicine storages in the complete data table. After completion of refilling process of the medicine storage, the information of the medicine storage will be deleted in the complete data table and the information will be altered in the management system. After completion of refilling process, the complete data table will be back to null.

Test and analysis

Simulation results and analysis

The programs of the ACO-SD and the OPM are coded in MATLAB 7. All the experiments were implemented on a PC with a Pentium 4 2.4 GHz CPU, 2 GB RAM, and Windows XP Home Basic Operating system. As shown in Table 3, the parameters of the ACO-SD are set.^32,33 Not more than 20 picking points are used in this article, which is consistent with the actual situation at the scene.

Table 3.

Parameters of the ACO-SD.

Parameter	Assignment	Parameter	Assignment
m	30	NC_max	150
n	5/10/20	$α$	1
Q	100	$β$	5
v_x	1 m/s	v_y	0.5 m/s

Table 3 shows the simulated parameters of the ACO-SD. The velocities in the X-direction, $v_{x}$ , and velocities i the Y-direction, $v_{y}$ , are used as movement in the X-axis and Y-axis, which are driven by the servo motor. $v_{x}$ and $v_{y}$ may be set differently and it depends on the proportion of length and height in storage spaces or the actual need in the FMDS. The proportion is changed in different FMDSs.

Based on the database of IRON-1200 and Rowa Vmax, the storage space of the FMDS is designed to balance dispensing with storing of medicines, and consequently, the storage space is limited. Generally, less than 20 storage storages are assigned for one type of medicine. Thus, the range of instances, which is the amount of medicine boxes, is set between 1 and 20. The samples are taken, including 5, 10, and 20, and each sample has been tested five times to ensure repeatable of simulation results in simulation.

From Tables 4 and 5, three aspects in the following can be seen:

Table 4.

Test results of simulation based on the shortest route searched.

Picking points	Number	Route value simulated				Time value simulated (s)
Picking points	Number	OPM	PSO³⁴	GA³⁵	ACO³¹	OPM	PSO	GA	ACO
5	1	44.361	31.3029	31.3029	31.3029	4.4	3.2	3.2	3.2
	2	44.361	31.3029	31.3029	31.3029	4.4	3.2	3.2	3.2
	3	44.361	31.3029	31.3029	31.3029	4.4	3.2	3.2	3.2
	4	44.361	31.3029	31.3029	31.3029	4.4	3.2	3.2	3.2
	5	44.361	31.3029	31.3029	31.3029	4.4	3.2	3.2	3.2
Average		44.361	31.3029	31.3029	31.3029	4.4	3.2	3.2	3.2
10	1	67.9801	34.0525	34.0525	34.0525	7.4	3.7	3.7	3.7
	2	67.9801	34.0525	34.0525	34.0525	7.4	3.7	3.7	3.7
	3	67.9801	34.0525	34.0525	34.0525	7.4	3.7	3.7	3.7
	4	67.9801	34.0525	34.0525	34.0525	7.4	3.7	3.7	3.7
	5	67.9801	34.0525	34.0525	34.0525	7.4	3.7	3.7	3.7
Average		67.9801	34.0525	34.0525	34.0525	7.4	3.7	3.7	3.7
20	1	120.2534	48.1182	47.1788	48.4627	13.6	6.2	5.8	6.4
	2	120.2534	47.1788	50.6221	47.8298	13.6	6.0	6.8	6.0
	3	120.2534	49.8581	48.8636	48.7172	13.6	6.3	6.2	5.8
	4	120.2534	48.1182	47.3997	47.7335	13.6	6.2	5.8	6.1
	5	120.2534	47.1788	48.6756	48.9381	13.6	6.0	6.4	5.8
Average		120.2534	48.0904	48.5481	48.3363	13.6	6.14	6.14	6.0

OPM: order-picking mode; PSO: particle swarm optimization; GA: genetic algorithm; ACO: ant colony optimization.

Table 5.

Test results of simulation based on the shortest time searched.

Picking points	Number	Route value simulated			Time value simulated (s)
Picking points	Number	PSO-SD	GA-SD	ACO-SD	PSO-SD	GA-SD	ACO-SD
5	1	31.3029	31.3029	31.3029	3.2	3.2	3.2
	2	31.3029	31.3029	31.3029	3.2	3.2	3.2
	3	31.3029	31.3029	31.3029	3.2	3.2	3.2
	4	31.3029	31.3029	31.3029	3.2	3.2	3.2
	5	31.3029	31.3029	31.3029	3.2	3.2	3.2
Average		31.3029	31.3029	31.3029	3.2	3.2	3.2
10	1	34.0525	34.0525	34.0525	3.7	3.7	3.7
	2	34.0525	34.0525	34.0525	3.7	3.7	3.7
	3	34.0525	34.0525	34.0525	3.7	3.7	3.7
	4	34.0525	34.0525	34.0525	3.7	3.7	3.7
	5	34.0525	34.0525	34.0525	3.7	3.7	3.7
Average		34.0525	34.0525	34.0525	3.7	3.7	3.7
20	1	48.9381	57.7532	48.9381	5.8	7.1	5.8
	2	48.9381	48.6668	50.3709	5.8	6.0	5.8
	3	50.2854	54.4726	48.7172	5.8	6.7	5.8
	4	48.9381	67.0300	48.9381	5.8	7.4	5.8
	5	48.9381	48.9381	48.9381	5.8	5.8	5.8
Average		49.2075	55.3721	49.1805	5.8	6.6	5.8

PSO-SD: particle swarm optimization with characterization-based speed and multi-driver; GA-SD: genetic algorithm with characterization-based speed and multi-driver; ACO-SD: ant colony optimization with characterization-based speed and multi-driver.

The OPM is based on section “Algorithm pseudo-code,” and the PSO, GA, and ACO are based on References 31, 34, and 35, respectively. The objective function of the GA and ACO is the shortest route. The ACO-SD is based on section “Algorithm pseudo-code.” The particle swarm optimization with characterization-based speed and multi-driver (PSO-SD) and genetic algorithm with characterization-based speed and multi-driver (GA-SD) are based on the PSO and GA, respectively. The objective function of the PSO-SD and GA-SD is the shortest time; meanwhile, both the PSO-SD and GA-SD take account of multiple drivers and the speed of drivers.

In terms of selecting route, the route values simulated by the PSO, GA, ACO, PSO-SD, GA-SD, and ACO-SD are shorter than that of the OPM significantly. It shows that applying heuristic algorithms in practice improves refilling efficiency and reduces refilling time. When the picking points are not more than 10, the route values simulated by the PSO, GA, and ACO are the same as that of the PSO-SD, GA-SD, and ACO-SD. When the picking points are 20, the route values simulated by the ACO-SD and PSO-SD may be the same. Not only the route values simulated by other algorithms are different from each other but also the route values simulated five times by the same algorithm may be not the same. All the average route values from the five simulated tests are compared. The average of the route values simulated by the PSO is the shortest, and the average of the route values simulated by the GA-SD is the longest. In terms of the route values, it shows that the ratios of route values of the PSO-SD, GA-SD, and ACO-SD are higher than that of the PSO, GA, and ACO, respectively. It demonstrates that the PSO-SD, GA-SD, and ACO-SD are not good at finding the shortest route. The reason for this is that the objective function of the PSO-SD, GA-SD, and ACO-SD is the shortest time, whereas the objective function of the PSO, GA, and ACO is the shortest route.

In terms of the length of time spent by different algorithms, the time values simulated by the PSO, GA, ACO, PSO-SD, GA-SD, and ACO-SD are shorter than that of the OPM significantly. Comparison among the results of the refilling time shows consistency in comparison among the results of the refilling route. When the picking points are not more than 10, all the refilling time values from these heuristic algorithms are the same. The time values simulated by the ACO-SD and PSO-SD are the same. The time values simulated are different between other algorithms, and it is because different algorithms select different refilling routes. In many simulation tests, although the ACO-SD and PSO-SD selected different routes and all route values are not the same, the time values simulated by the ACO-SD and PSO-SD are the same. It also shows that the time values simulated by the PSO-SD and ACO-SD are shorter than that of the PSO, GA, ACO, and GA-SD, and the time values simulated by the GA-SD are the shortest; nevertheless, the time value simulated by the GA-SD is far less than that of the OPM. Therefore, it shows that the ACO-SD and PSO-SD are not only reliable but also capable of selecting a better refilling route, and the time of the route traveled is the shortest.

In this article, there are two types of optimization ratios calculated between ACO-SD and another algorithm, including the optimization ratios of the average route value and the optimization ratios of the average time value. Both these types of optimization ratios are calculated in the same method, and the example of the optimization ratios of the average route value simulated between the OPM and the ACO-SD is shown in equation (7). “(1)” represents the value from the average route value. x represents the amount of picking points. The formula for calculation is as follows

OPM - ACO - SD (1) = \frac{OPM (picking (x)) - ACO - SD (picking (x))}{OPM (picking (x))}

(7)

In terms of equipment in the FMDS, the optimization ratio of refilling time is an important index for evaluation. In practice, the feedback shows that the pharmacists concern the refilling time the most. Their expectation is the shorter refilling time, the better. The reason for this is that although reducing refilling time on a single type of medicine may not seem very meaningful, when a large quantity of medicine needs to be refilled, it will save a significant amount of time spending on refilling. Thus, spending less time on refilling using a new algorithm than an old algorithm is more acceptable to the pharmacists in the FMDS. Calculating optimization ratio is a good method to compare refilling time between a new algorithm and an old algorithm. When a new product is presented to the pharmacists, the optimization ratio is regarded as an important index of evaluation.

In Table 6, the results are shown as follows: Comparisons of optimization ratios among algorithms are made. With increasing picking points, compared with the OPM, no matter the optimization ratios of the average route value or the average time value of the PSO, GA, ACO, PSO-SD, GA-SD, and ACO-SD are all increased. When the picking points are not more than 10, the test results of the PSO, GA, ACO, PSO-SD, GA-SD, and ACO-SD show that the optimization ratios of both the average route values and the average time values between any two of these six algorithms are null. Yet, when the picking points exceed 20, compared with the PSO, GA, and ACO, the optimization ratios of the average route values by the ACO-SD are lower; compared with the GA-SD, the optimization ratios of the average route values by the ACO-SD are higher. However, compared with the PSO, GA, ACO, and GA-SD, the optimization ratios of average time value by the ACO-SD are higher. Compared with the PSO-SD, both the optimization ratios of the average route values and the optimization ratios of the average route values are zero. In terms of selecting refilling routes, it demonstrates that the ACO-SD and PSO-SD have the same advantage which is that the time of the route traveled is the shortest.

Table 6.

Optimization ratio between ACO-SD and other algorithms.

Type	Algorithm	Pickings (5)	Pickings (10)	Pickings (20)
The average route value (1)	OPM	29.4%	49.9%	59.1%
	PSO	0	0	−2.2%
	GA	0	0	−1.3%
	ACO	0	0	−1.7%
	PSO-SD	0	0	0%
	GA-SD	0	0	11.1%
The average time value (2)	OPM	27.2%	50%	57.3%
	PSO	0	0	5.5%
	GA	0	0	5.5%
	ACO	0	0	3.3%
	PSO-SD	0	0	0%
	GA-SD	0	0	12.1%

OPM: order-picking mode; PSO: particle swarm optimization; GA: genetic algorithm; ACO: ant colony optimization; PSO-SD: particle swarm optimization with characterization-based speed and multi-driver; GA-SD: genetic algorithm with characterization-based speed and multi-driver.

Figure 3 shows the convergence results by different algorithms with different picking points. Table 7 shows the length of time used by different algorithms based on Figure 3.

Table 7.

Computational cost of convergence results by different algorithms.

Picking points	PSO	GA	ACO	PSO-SD	GA-SD	ACO-SD
5	1.089	3.179	0.409	1.104	3.516	0.413
10	1.585	3.463	1.678	1.566	3.741	1.662
20	7.293	7.808	6.005	7.932	8.240	5.994

PSO: particle swarm optimization; GA: genetic algorithm; ACO: ant colony optimization; PSO-SD: particle swarm optimization with characterization-based speed and multi-driver; GA-SD: genetic algorithm with characterization-based speed and multi-driver; ACO-SD: ant colony optimization with characterization-based speed and multi-driver.

Based on Figure 3 and Table 7, it shows that the times of iterations and the running time of the PSO and PSO-SD, the GA and GA-SD, as well as the ACO and ACO-SD are almost the same, respectively. The reason for this is that the PSO-SD, GA-SD, and ACO-SD are based on the PSO, GA, and ACO, respectively, except different objective functions.

From Figure 3(a1), (b1), (c1), (d1), (e1), and (f1), it appears that when the picking points are not more than five, all algorithms are fast on convergence. They all completed searching the best value in five iterations. In terms of running time, it shows that the ACO and ACO-SD used the shortest length of time, whereas the GA and GA-SD used the longest.

From Figure 3(a2), (b2), (c2), (d2), (e2), and (f2), it demonstrates that when picking points are between 5 and 10, the ACO and ACO-SD are the fastest on convergence, whereas the GA and GA-SD are significantly slow. It can be seen that the running time spent by the PSO, ACO, PSO-SD, and ACO-SD are very close.

From Figure 3(a3), (b3), (c3), (d3), (e3), and (f3), it shows that when picking points are between 10 and 20, the ACO and ACO-SD are the fastest on convergence, the PSO and PSO-SD are falling behind, whereas the GA and GA-SD are the slowest on convergence. The refilling time used by the ACO and ACO-SD is similar, the PSO and PSO-SD used longer, and the GA and GA-SD used the longest.

From the results above, it shows that the ACO and ACO-SD are the best in searching optimized solution, especially when there are few picking points. When there are few picking points, the convergence speed of the ACO and ACO-SD is fast and the running time is short. However, no matter the convergence speed or running time of the GA and GA-SD are the worst. When the picking points are 10, the running time of the PSO, ACO, PSO-SD, and ACO-SD is very similar. Yet, the convergence speed of the PSO and PSO-SD is not as good as that of the ACO and ACO-SD.

From the results above, it shows that the PSO and ACO are good at selecting the shortest routes, whereas the PSO-SD and ACO-SD are good at achieving the shortest time. However, compared with the PSO and PSO-SD, the ACO and ACO-SD are more advantageous as the times of iterations of the ACO and ACO-SD are less and the running time of the ACO and ACO-SD is shorter. Therefore, the ACO-SD is more suitable for searching optimized solution than the PSO-SD and GA-SD in the FMDS.

Operation results and analysis

Experimental platform

According to the prescription information provided by the hospital management system, the experimental platform, the FMDS, is designed to dispense medicine boxes. As shown in Figure 4(c), the FMDSs, which have been designed, manufactured, and debugged in 2013–2014, have three main compositions, including the automatic refilling subsystem, medicine storage subsystem, and automatic dispensing subsystem. Formal operation began in the second half of 2014. These main compositions are capable of automatic refilling, medicine-intensive storage, and automatic dispensing. The storage container to be refilled is called “picking point” to distinguish it from the others.

Figure 4.

The mechanical structure of FMDS: (a) the manipulator, (b) the view of medicine storages, and (c) side of FMDS.

The FMDS can simplify the medicine dispensing process and reduce the error rate of medicine dispensing, and therefore, it decreases the waiting time for patients. In the FMDS, the capacity of the medicine-intensive storage is limited due to the space of the device. The matrix linkage mode is used in the automatic dispensing process to effectively control the dispensing time of a field requirement. The automatic refilling subsystem is important in refilling route, which contains two primary parts, the transmission part of the manipulator and the loading medicine manipulator.¹⁴ The transmission part of a manipulator drives the manipulator to a specified location, and the medicine is pushed into storage space by the manipulator. To ensure that the manipulator operates with accuracy and stability, a Cartesian coordinate robot module is used to drive the loading medicine manipulator. The Cartesian coordinate robot is composed of two horizontal and two vertical linear motion units.²⁶ The horizontal direction is set as the X-axis, and the vertical direction is set as the Y-axis. The linkage of X- and Y-directions of the manipulator is achieved by a synchronous machine driver system, as shown in Figure 4(b).

The loading medicine manipulator comprises an integrated framework, a lifting mechanism, a platform transmission, a beating device, and a group of sensors for counting and protection, as presented in Figure 4(c). Medicine boxes were stored in the lifting mechanism in prepared status. The lifting mechanism was lifted by the platform transmission according to the accumulative medicine box height and moved to the medicine refilling port. The medicine boxes were pushed into the specific storage spaces by the beating device. The angle between the manipulator and the Cartesian coordinate unit was used to pinpoint the position of the medicine box (Figure 4).

The multiple axis controller from the United States was applied for motion control and Fuji motion. C# programming was used in the host computer (HC). The industrial personal computer (IPC) was used from Advantech. The sensor and programmable logic controller (PLC) from Omron were used.

Application results and analysis

The widths of ordinary medicine boxes are in the range of 35–110 mm and the heights are in the range of 10–60 mm, which is the source of test sample from many hospitals in different provinces in China. To reduce the influence of the size of different medicine boxes, the size of test sample is selected in the range that is mentioned above as they are commonly used in China. The test samples are shown in Table 8.

Table 8.

Medicine information of practice test sample.

Medicine name	Width (mm)	Height (mm)
Drospirenone and ethinyl estradiol tablets	44	15.5
Compound amino acid capsules (8–11)	64	24.8
Postpartum stasis granule	87	40.6

Figures 5 –7 show the records of refilling process and time in practice test by the OPM and the ACO-SD, whose information is identified by * in Table 9. The records of practical tests include the order of medicine storages (medicine storage number), medicine name, refilling time from one picking point to another one (refill time), and test number (order sequence), which are listed in Figures 5 –7. The amount of each group includes 5, 10, and 20 picking points.

Figure 5.

The refilling time of the FMDS: (a) using the OPM with five picking points and (b) using the ACO-SD with five picking points.

Figure 6.

The refilling time of the FMDS: (a) using the OPM with 10 picking points and (b) using the ACO-SD with 10 picking points.

Figure 7.

The refilling time of the FMDS: (a) using the OPM with 20 picking points and (b) using the ACO-SD with 20 picking points.

Table 9.

Results in practical tests.

Picking points	Test number	The best time value tested (s)		The optimization ratio
Picking points	Test number	OPM	ACO-SD	BOTT	OTT	WOTT
5	1*	13.977	11.212
	2	13.460	11.223
	3	14.107	11.637
	4	13.847	11.780
	5	13.663	11.180
Average		13.811	11.406	20.7%	17.4%	12.4%
10	1*	25.033	17.070
	2	25.790	16.937
	3	24.597	17.840
	4	25.103	17.223
	5	24.893	17.460
Average		25.083	17.306	34.3%	31.0%	27.4%
20	1*	44.387	27.217
	2	45.663	27.347
	3	45.597	27.810
	4	43.427	27.790
	5	44.377	27.557
Average		44.690	27.544	40.3%	38.3%	37.3%

OPM: order-picking mode; ACO-SD: ant colony optimization with characterization-based speed and multi-driver.

Significance of bold values are the max value and min value.

In the practical tests, a group of picking points for each medicine were tested five times to remove inaccuracy, which is shown in Table 8. The results of practical tests are recorded in the test projects of the FMDS. The required amount of one picking point is set 1 to simplify the operation model in both simulation program and the FMDS operation system and reduce time error due to beating module of the manipulator and platform transmission. In the simulation, the time of the medicine transferred from the manipulator to medicine storage, acceleration, and deceleration process is unconsidered. In practical tests, one medicine box is pushed into a storage space from the manipulator. The time normally used is 1.2–1.4 s. In this article, the optimal route time rate is studied, the period of time from the manipulator to the storage is subtracted, and 1.3 s is adopted

\begin{matrix} The optimization ratio of time value tested by the ACO - SD and the OPM (OTT) \\ = \frac{The average of best time value tested by the OPM - The average of best time value tested by the ACO - SD}{The average of best time value tested by the OPM} \times 100 % \end{matrix}

(8)

\begin{matrix} The best optimization ratio of time value tested by the ACO - SD and the OPM (BOTT) \\ = \frac{The maximum best time value tested by the OPM - The minimum best time value tested by the ACO - SD}{The maximum best time value tested by the OPM} \times 100 % \end{matrix}

(9)

\begin{matrix} The worst optimization ratio of time value tested by the ACO - SD and the OPM (WOTT) \\ = \frac{The minimum best time value tested by the OPM - The maximum best time value tested by the ACO - SD}{The minimum best time value tested by the OPM} \times 100 % \end{matrix}

(10)

The results of practical tests are shown in Table 9, which include the best time value tested in practical tests by the OPM and ACO-SD and the optimization ratios. The optimization ratios are calculated based on the best time value tested in practical tests by the OPM and ACO-SD, and the calculation process is shown in equations (8)–(10):

The period of time from the manipulator to the picking point is subtracted in both the refilling time by the OPM and ACO-SD, 6.5 s for 5 picking points, 13 s for 10 picking points, and 26 s for 20 picking points, respectively. The best time value tested is the processed refilling time in Table 9.

The changes and the trend of the best time value tested in practical tests by the OPM and ACO-SD are discussed for five picking points. The refilling time of five picking points by the OPM in the first practical test is 20.477 s, and it is 17.712 s by the ACO-SD, which are shown in Figure 4(a) and (b), and the average of the refilling time in five tests is 20.311 and 17.792 s. The period of time from the manipulator to the storage is subtracted, the best time value tested of five picking points by the OPM in the first practical test is approximately 13.977 s, and the average of the best time value tested is 13.811 s. The best time value tested of five picking points by the ACO-SD in the first practical test is 11.212 s and the average of the best time value tested is 11.406 s, which are shown in Table 9 and Figure 5(a) and (b). The refilling time and the best time value tested from the rest of samples are calculated in the same way as the first practical test. Compared with the best value time tested by the OPM, the ACO-SD spent less time. When five picking points are selected, there is a range of fluctuation of optimization ratio in five tests. The range of optimization ratio of the best time value tested by the ACO-SD and the OPM is calculated between 12.4% and 20.7%, and the average optimization ratio is more than 17.4%.

The changes and the trend of the best time value tested in practical tests by the OPM or by the ACO-SD for 10 picking points are discussed. The refilling time of 10 picking points by the OPM in the first practical test is 38.033 s and it is 30.070 s by the ACO-SD, which are shown in Figure 6(a) and (b), and the average of the refilling times in five tests is 38.083 and 30.306 s. The period of time from the manipulator to the storage is subtracted, the best time value tested of 10 picking points by the OPM in the first practical test is approximately 25.033 s, and the average of the best time value tested is 25.083 s. The best time value tested of 10 picking points by the ACO-SD in the first practical test is 17.070 s and the average of the best time value tested is 17.306 s, which are shown in Table 9 and Figure 6(a) and (b). Compared with the best value time tested by the OPM, the ACO-SD spent less time. When 10 picking points are selected, there is a range of fluctuation of optimization ratio in five tests. The range of optimization ratio of the best time value tested by the ACO-SD and OPM is calculated between 27.4% and 34.3%, and the average optimization ratio is more than 31.0%.

The changes and the trend of the best time value tested in practical tests by the OPM or by ACO-SD for 20 picking points are discussed. The refilling time of 20 picking points by the OPM in the first practical test is 70.387 s and by the ACO-SD is 53.217 s, which are shown in Figure 7(a) and (b), and the average of the refilling times in five tests is 70.690 and 53.544 s. The period of time from the manipulator to the storage is subtracted, the best time value tested of 20 picking points by the OPM in the first practical test is approximately 44.387 s, and the average of the best time values tested is 44.690 s. The refilling time of 20 picking points by the ACO-SD in the first practical test is 27.217 s, and the average of the best time values tested is 27.544 s, which are shown in Table 9 and Figure 7(a) and (b). Compared with the best value time tested by the OPM, the ACO-SD spent less time. When 20 picking points are selected, there is a range of fluctuation of optimization ratio in five tests. The range of optimization ratio of the best time value tested by the ACO-SD and OPM is calculated between 37.3% and 40.3%, and the average optimization ratio is more than 38.3%.

The trends of optimization ratios are discussed as follows. The optimization ratios of route value simulated between the ACO-SD and OPM increase with picking points increasing from 5 to 20 picking points, likewise the optimization ratios of time value simulated and the optimization ratios of time value tested in practical tests. However, the extent of increase decreases. With the increasing amount of picking points, the possibility of a better picking point and a better refilling path selected by the ACO-SD increases, but optimization effect decreases in limited space. Meanwhile, the route values and the time values simulated by the ACO-SD or OPM increase. The optimization ratios decrease as the ratio of the value of the denominator to the value of the numerator decreases. In practical tests, as the amount of picking points increases, some refilling paths become shorter due to the increase in the amount of refilling paths. Thus, the effect of the acceleration and deceleration of drivers becomes more important. In terms of the optimization ratios of time value tested by the ACO-SD and the OPM, the extent of increase decreases.

The values of optimization ratios are discussed. When the amount of picking points exceeds the thresholds, the optimization ratio of time value simulated by the ACO-SD and ACO is higher than the optimization ratio of route value simulated by the ACO-SD and ACO for the same picking points. The best route value simulated by the ACO is smaller than that of ACO-SD, but the best time value simulated by the ACO is longer than that of ACO-SD. The reason is that the best route value and the best time value simulated by the ACO did not consider the speed, multi-driver, acceleration, and deceleration of drivers in refilling process. The best route value and the best time value simulated by the ACO-SD consider the speed and multi-driver. If the shortest time is set as the objective function, a better picking point is selected by the ACO-SD than ACO. Meanwhile, the best time value tested by the ACO-SD in practical test is longer than that of simulation, because the speed, multi-driver, acceleration, and deceleration of the drivers are considered in refilling process. Thus, it demonstrates that the less the influence factors, the better the optimization effect, and the more the influence factors, the closer the practical operation. Consequently, the results by the ACO-SD are closer to the actual refilling process than that of the ACO.

The results regarding time spent in simulation and practical test by the ACO-SD and OPM are discussed. The practical operation process contains acceleration, uniform velocity, and deceleration of the drivers, whereas there is only velocity uniform in the simulation. It indicates that the non-uniform velocity of practical operation significantly influences the optimization results. The reason is that the time spent in practical test is longer than that in the simulation with the same picking points both by the ACO-SD and OPM.

Comparison between the results by the OPM and the results by the ACO-SD in practical tests is made. The ACO-SD finds the path of the next picking point using the minimum time spent between picking points. Therefore, the refilling time between the current picking point and the next picking point is not long. The influence of the acceleration and the deceleration during operation is more than the uniform speed. With the increasing amount of picking points in limited space, the shorter refilling path is chosen; thus, it leads to shorter path among pickings. The effect of acceleration and deceleration is obvious in the short path. Although the refilling time increases, the extent of increase decreases. It run first along the horizontal direction, and then the longitudinal, as shown in Figure 2(a), which is the OPM. The distance between picking points varies; some refilling paths are longer than the other. However, the longer refilling path is more advantageous for uniformity than the shorter refilling path. With the increasing amount of picking points, the longer refilling path is divided into many short ones. In addition, the order of pickings is optimized when the path is chosen by the OPM. The effect of optimization is more than the effect of the acceleration and the deceleration. Hence, optimization ratio of time by the ACO-SD and OPM in practical tests increases. With the increasing intensity of picking points, optimization ratio of time by the ACO-SD and OPM in practical tests is more than 17.4%, 31.0%, and 38.3% in 5, 10, and 20 picking points, respectively. Thus, the ACO-SD is suitable for the refilling process.

Time requirement of refilling algorithm in the FMDS is compared with IRON-1200. One manipulator of IRON-1200 accomplished approximately 1250 medicine boxes in an hour. When the ACO-SD is used in the FMDS, the refilling time of 5, 10, and 20 picking points is about 20, 30, and 50 s, respectively. The total refilling time is about 100 s and the total boxes are 35. Thus, approximately 1260 boxes of medicine are accomplished in an hour. Whereas when the OPM is used in the FMDS, only approximately 985 boxes of medicine are accomplished in an hour. The ACO-SD is used to refill medicine in the FMDS which is able to meet the requirements of dispensing in modern pharmacy.

Conclusion

The refilling route of the FMDS is studied in this research. A mathematical model of the FMDS, the ACO-SD, on the refilling route is established according to the mechanical apparatus. The orders of picking points are chosen by the ACO-SD, PSO-SD, GA-SD, ACO, PSO, GA, and OPM on 5, 10, and 20 picking points in simulation, and a comparison is made among them. The ACO-SD, PSO-SD, GA-SD, ACO, PSO, and the GA are better than the OPM on the refilling route and the refilling time in simulation. When the amount of picking points is not more than the thresholds, the refilling time by the ACO-SD, PSO-SD, GA-SD, ACO, PSO, and GA in simulation is the same. Over the threshold, the ACO-SD is better than the GA-SD, ACO, PSO, and GA on the refilling time in simulation, and the ACO-SD is more stable than the GA-SD, ACO, PSO, and GA on the time spent searching the refilling route. Although the refilling time of the PSO-SD and ACO-SD is the same when picking points are the same, the times of iteration and running time of the ACO-SD are better than that of the PSO-SD. In practical tests, refilling time by the ACO-SD is significantly shorter than that of the OPM. With the increasing amount of picking points, optimization ratio of time value tested by the ACO-SD and OPM increases, and the extent of increase decreases, because the effect of acceleration and deceleration becomes strong in limited space. The ACO-SD is suitable for refilling process and it provides a new study vision for the TSP.

Footnotes

Appendix 1

Academic Editor: Pak Wong

Author Note

Author Hui Jin is also affiliated to College of Mechanical Engineering, Chongqing University of Technology, No 69, Hong Guang Road, Chong qing 400054, China.

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: This research was supported by the National Science Foundation of China, contract no. 51305008.

References

Claudia

GGS

Laura

Juan

JGB

et al . Ant colony system with characterization-based heuristics for a bottled-products distribution logistics system. J Comput Appl Math 2014; 259: 965–977.

Rubrico

JUR

Higashi

Tamura

et al . Online rescheduling of multiple picking agents for warehouse management. Robot Cim: Int Manuf 2011; 27: 62–71.

Chen

Wang

et al . An ant colony optimization routing algorithm for two order pickers with congestion consideration. Comput Ind Eng 2013; 66: 77–85.

Theys

Bräysy

Dullaert

et al . Using a TSP heuristic for routing order pickers in warehouses. Eur J Oper Res 2010; 200: 755–763.

Bartholdi

Hackman

ST.

Warehouse distribution science, release 0.1.2, 2002, http://www.warehouse-science.com

Drury

Towards more efficient order picking (IMM Monograph no. 1). Cranfield: The Institute of Management, 1988.

Coyle

Bardi

Langley

CJ.

The management of business logistics. Saint Paul, MN: West, 1996.

Wang

Yun

et al . The present situation and development of automatic pharmacy. Robot Tech Appl 2007; 5: 27–32.

Samaranayake

Cheung

STD

Cheng

et al . Implementing a bar-code assisted medication administration system: effects on the dispensing process and user perceptions. Int J Med Inform 2014; 83: 450–458.

10.

Ong

YSP

Chen

Wong

et al . Evaluating the impact of drug dispensing systems on the safety and efficacy in a Singapore outpatient pharmacy (PHP38). Value Health 2014; 17: A791–A792.

11.

Balka

Kahnamoui

Nutland

Who is in charge of patient safety? Work practice, work processes and utopian views of automatic drug dispensing systems. Int J Med Inform 2007; 76: s48–s57.

12.

Che

Kang

et al . A simulation-based Genetic Algorithm approach for refilling process with Clip Type Passive Manipulator. In: Proceedings of the 15th international conference on intelligent systems design and applications, Marrakech, Morocco, 14–16 December 2015, pp.368–373. New York: IEEE.

13.

Yun

Fan

Gong

et al . The manipulator as the type of magazine clip, 25 September 2009, China. ZL2009 100931568, 2009.

14.

Jin

Yun

Wang

et al . Application and research of the Clip Type Manipulator. Mech Mach Sci 2016; 36: 841–851.

15.

Shi

Cai

Zou

et al . Comparison between ant colony algorithm and particle swarm optimization and their application in VRP. In: Proceedings of the 24th Chinese control conference, Guangzhou, China, 15–18 July 2005, pp.732–735. South China University of Technology Press.

16.

Dong

Design and analysis of TSP problem based on genetic algorithm and ant colony algorithm. J Wuhan Univ Technol 2010; 32: 89–92.

17.

Dorigo

Maniezzo

Colorni

Ant system: optimization by a colony of cooperating agents. IEEE T Syst Man Cy B 1996; 26: 29–41.

18.

Dorigo

Gambardella

LM.

Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE T Evolut Comput 1997; 1: 53–66.

19.

Ugur

Aydin

An interactive simulation and analysis software for solving TSP using ant colony optimization algorithms. Adv Eng Softw 2009; 40: 341–349.

20.

Pintea

Chira

Dumitrescu

et al . Sensitive ants in solving the generalized vehicle routing problem. Int J Comput Commun 2011; 6: 734–741.

21.

Puris

Bello

Herrera

Analysis of the efficacy of a two-stage methodology for ant colony optimization: case of study with TSP and QAP. Expert Syst Appl 2010; 37: 5443–5453.

22.

Kim

Lee

Park

et al . Ant colony based self-adaptive energy saving routing for energy efficient internet. Comput Netw 2012; 56: 2343–2354.

23.

http://baike.baidu.com/link?url=EA_r-TVLZ2JBj-rnckeFUK9-4nyQeGuadu7PBVW_C9KQ4x0-ouBCh_rCXJWmyqZCsv_QBk64RMTRwc03-5RIn9fF8ixCnkq8fU6KDt_4V7bAvClyPeRgxt8cOpA6ZbZF95rC1ek1esW9GsrjqjEgWq

24.

Helsgaun

An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur J Oper Res 2000; 126: 106–130.

25.

Aybars

Doğan

An interactive simulation and analysis software for solving TSP using ant colony optimization algorithms. Adv Eng Softw 2009; 40: 341–349.

26.

Zhao

et al . Ant colony optimization algorithm with mutation mechanism and its applications. Expert Syst Appl 2010; 37: 4805–4810.

27.

Yue

Zhou

Yue

et al . Multi-route railroad blocking problem by improved model and ant colony algorithm in real world. Comput Ind Eng 2011; 60: 34–42.

28.

Saenphon

Phimoltares

Lursinsap

Combining new Fast Opposite Gradient Search with Ant Colony Optimization for solving travelling salesman problem. Eng Appl Artif Intel 2014; 35: 324–334.

29.

Elloumi

Haikal

Abraham

et al . A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP. Appl Soft Comput 2014; 25: 234–241.

30.

Zhang

Feng

ZR.

Multi-satellite control resource scheduling based on ant colony optimization. Expert Syst Appl 2014; 41: 2816–2823.

31.

Jin

Yun

Gao

XS.

Application and research of the refilling path with Clip Type Manipulator. In: Proceedings of the 2015 IEEE conference on robotics and biomimetics, Zhuhai, China, 6–9 December 2015, pp.775–780. IEEE.

32.

Zheng

ZB.

The study of setting of parameters α, β, ρ in ant colony optimization the example as TSP. Geomat Inf Sci Wuhan Univ 2004; 29: 597–601.

33.

Figlali

Özkale

Engin

et al . Investigation of Ant System parameter interactions by using design of experiments for job-shop scheduling problems. Comput Ind Eng 2009; 56: 538–559.

34.

http://download.csdn.net/detail/evankaka/4889050

35.

http://blog.csdn.net/robert_chen1988/article/details/53003300