Optimization for medical logistics robot based on model of traveling salesman problems and vehicle routing problems

Abstract

Fast medicine dispensing system (FMDS) as a kind of medical logistic robot can dispense many drugs for one prescription at the same time. To guarantee the sustainability of drug dispensation, it is required that FMDS replenish drugs rapidly. The traditional order picking model (OPM) is difficult to meet the demand of prompt replenishment. To solve the problems of prolonged refilling route and inefficiency of drugs replenishment, a mixed refilling model based on multiple steps traveling salesman problem model (MTSPM) and vehicle routing problem model (VRPM) is proposed, and it is deployed in two circumstances of FMDS, including temporary replenishment mode (TRM) and concentrate replenishment mode (CRM). It not only meted the demand under different circumstances of drug replenishment but also shortened the refilling route significantly. First, the new pick sets were generated. Then, the orders of pick sets were optimized and the new paths were achieved. When the number of pickings is varied no more than 20, experiment results declared that the refilling route is the shortest by utilizing MTSPM when working under the TRM condition. Comparing MTSPM with OPM, the rate of refilling route length decreased up to 32.18%. Under the CRM condition, the refilling route is the shortest by utilizing VRPM. Comparing VRPM with OPM, the rate of refilling route length decreased up to 58.32%. Comparing VRPM with MTSPM, the rate of refilling route length has dropped more than 43.26%.

Keywords

Medical logistics robot multiple steps-TSP VRP ant colony optimization

Introduction

Path planning, which is one of the key technologies used in increasing time and cost saving, attracts more and more attention on logistics robot, autonomous vehicles, express logistics, and so on.^1

–4 Compared with express logistics, path planning of logistic robots and autonomous vehicles has more similar requirements. Express of path planning takes the object, such as time or path length, seriously.⁵ To path planning of robots or manipulators, most of the studies focus on efficient approaches to search the shortest length, such as Huang and Savkin used a shortest viable path planning algorithm in the unicycle robot,⁶ least time, such as Jin et al. considered a path planning by dual motors, the influence of velocity affects the path selected between any two pickings,^7,8 or least energy, such as Norouzi studied an analytical strategy to generate stable paths for manipulator arms of the reconfigurable mobile robot.⁹ Besides the localization problem of the robot affects the path selected, such as Gao et al. studied localization problem of the robot, and a new evaluation function for path planning has been proposed,¹⁰ memory saving, such as Song et al. proposed an improved cuckoo search algorithm based on compact and parallel techniques for three-dimensional path planning problems,¹¹ path smoothness, such as Nazarahari et al. proposed an innovative artificial potential field algorithm and an enhanced genetic algorithm to find a set of feasible initial paths and is guaranteed to find a feasible path improved.¹² But the best scheme from start to end, generally, without other factors is unconsidered in the path such as environment, artificial element, and so on.¹³ Path planning of logistics robot and autonomous vehicles is another programming. The process of planning is dynamic. According to the surrounding environment, additional information, and other means, path optimization has adjusted dynamically when the system running.^14,15

The change of surrounding environment, information, and operating mode are the major factors to affect the path chosen in logistics robot and autonomous vehicles.^16,17 Drug circulation in pharmacy is a key link of modern pharmaceutical logistics that lead to medical logistic robots developed for reducing dispensing errors, including comparability misses of drugs’ name and dispensing dysfunction, which occur at this stage may harm the patient directly.^18,19 A medical logistics robot, named as fast medicine dispensing system (FMDS), is designed to administer medicines and make up electronic prescriptions automatically to replace manual work as required before.^7,20

In many Asian countries, physicians play a dual role in checking prescription and dispensing medicine, and they have essentially no time to instruct patients in terms of drug usage.²¹ In western countries, the responsibilities of pharmacists are checking the prescriptions, dispensing medicine according to the prescription, providing consultation, and offering advice on drug usage to patients.²² One of the main objectives for the implementation of an automated dispensing system (ADS) or automated dispensing machines is to enable pharmacists to have more engagements with the patients.^23,24 In China, thousands of patients mean that a large quantity of distribution of medicine is needed. Compared with other countries, device features of ADS are high capacity and replenish manipulator in China.

The goal of providing automation in medicine refilling, storage, and dispensation has been achieved by replacing traditional human-based drug administration and distribution with a computer-controlled system. It is capable of dispensing many drugs for one prescription synchronized and efficiency improved. It is necessary to provide a rapid replenishment in FMDS. The replenishing process is dynamic and can be regarded as the warehouse picking problem. Dynamic order picking strategy has been used for the operations of retrieving goods from special storage locations based on customer orders. The travel time is wasted in vain since it is not cost effective.^25,26 Therefore, to improve the performance of order picking, it is critical to reduce the travel time.

In this article, a novel mixed refilling model, multiple steps traveling salesman problem model (MTSPM) and vehicle routing problem model (VRPM), is proposed. This model is combined with ant colony optimization (ACO) algorithm for searching the shortest refilling route. In the preutilization and early literature, order picking model (OPM) is used as drug replenishing algorithm.²⁷ According to the rules, the algorithm has to be simple and convenient, and it is the most frequently used method. The refilling route is generally searched with rather a long length of time because it follows the particular rules of arrangement by OPM. According to particular rules of arrangement, the next picking selected may not be the closest one. The refilling model is considered as a traveling salesman problem (TSP).⁸ The refilling process is simplified so that all medicine storage cells, which will be refilled, can be refilled in one traveling. It ignores one constraint and maximizes the capacity of the end effector. Besides, the refilling model is considered as a vehicle routing problem (VRP).²⁸ It opts out the traditional rules of arrangement and some constraints. This results that it is applicable only to concentrate replenishment mode (CRM), which is one of the replenishment requirements. The novel mixed refilling model not only meets all replenishment requirements but also provides the best policy of searching route to search the shortest refilling route.

This article is organized as follows. The second section introduces the concept and constitution of dispensing and managing system. The third section describes the conventional refilling model, called OPM, and the novel mixed refilling model, called MTSPM and VRPM. The fourth section presents the rules of different refilling models and the refilling route searching by different refilling models. The fifth section shows and analyzes two groups of experimental results with different refilling models and the trend of variation between two refilling models. Finally, the sixth section comes to a conclusion and gives some perspectives for future investigations.

Dispensing and managing system

FMDS contains dispensing and management system (DMS), drug distribution unit (DDU), drug storage unit (DSU), and drug replenishment unit (DRU). DMS is connected with Hospital Information System via local area networks to manage and distribute drugs in FMDS, as shown in Figure 1. After the paid prescription is received by DMS, medicine storage cells and quantities of drugs are distributed. When drugs are dispensed to a patient according to the prescription, management and control of drug distribution are completed in FMDS. Meanwhile, management and control of drug replenishment are required in FMDS. Thus, optimized medicine storage cells and refilling route are chosen by DMS. After loading the medicine by DRU, drug replenishment of specified medicine storage cell is also completed.

Figure 1.

Drug distribution based on fast medicine dispensing system.

There are two main components of DSU: medicine storage cells and braced frame. The quantity of medicine storage cells that are used in drug storage is more than 1000 in DSU (Figure 1). Normal drugs between 200 and 500 kinds are present in large comprehensive hospitals. To ensure appropriate storage of drugs, each medicine storage cell can store one kind of medicine only, but a kind of medicine can be distributed between 1 and 20 medicine storage cells. To ensure adequate distribution of drugs, high efficiency of drug replenishment is required in FMDS. The effective method to improve efficiency is to choose the optimal refilling route.

DRU has two main components, which are an end effector for drugs replenished and a 2-DOF Cartesian coordinate robot (Figure 1(c) and (d)). The end effector can move along two directions: X coordinate and Y coordinate. The coordinate values on X and Y coordinates corresponding to the medicine storage cells are stored in pharmacy server. The maximum number of medicine boxes depends on the medicine because the capacity of the end effector is limited and the height of the medicine boxes may be different from others. In our experiment, the maximum number of the two test medicines samples is 25 and 13, respectively, as presented in Table 1.

Table 1.

The picking set generated.

Step	Program
1	If $⌀$ $\in$ $p i c k i n g s c h e d u l i n g$
2	k =1, k is the number of picking set
3	Picking set $s e t {()}_{k}$ is generated
4	$p i c k i n g_{k}$ is selected, if $d_{i j}$ is shorter than others in $a l l o w e d_{k}$
5	picking is put in $s e t {()}_{k}$ , the picking deleted in $p i c k i n g s c h e d u l i n g$
6	If $a m o u n t_{P i c k i n g s}$ $>$ $a m o u n t_{s e t {()}_{k}}$ , the Picking rule number two is used
7	If the $a m o u n t_{s e t {()}_{k}}$ + the $a m o u n t_{s e t {()}_{k + 1}}$ $\leq$ the $s h o r t a g e_{s e t {()}_{k}}$ , picking is added
8	If $s h o r t a g e_{i n c r e a s e d}$ $\leq$ $s h o r t a g e_{e n d e f f e c t o r}$ , the picking is put in the $s e t {()}_{k}$ , $p i c k i n g$ $\in$ $p i c k i n g s c h e d u l e$
9	If $s h o r t a g e_{i n c r e a s e d}$ $>$ $s h o r t a g e_{e n d e f f e c t o r}$ , The picking set is completed. Loops above procedure, to 5
10	If $\emptyset$ $\in$ $p i c k i n g s c h e d u l i n g$ , Picking set $s e t {()}_{k + 1}$ is generated. Loops the procedure, to 3, until the $p i c k i n g$ $\emptyset$ $\in$ $p i c k i n g s c h e d u l i n g$
11	Picking sets are completed
12	$e n d$

Compared with traditional manual dispensation and storage, dispensing and storing errors are reduced by FMDS significantly because of the usage of data management, automatic replenishment, and automatic dispensation. Synchronized dispensation of many drugs can be completed by DMS in DDU, and it is capable of finishing one prescription within less than 10 s and this meets the need of hospitals. DRU configured with an end effector results in low efficiency in terms of drug replenishment. Therefore, improving efficiency of drug replenishment is important for researching in FMDS. Furthermore, there are other methods to improve efficiency of drug replenishment, including improving the speed, increasing the capacity, increasing the quantity of end effector, and optimizing refilling route. Compared with other methods, the optimizing refilling route requires no extra costs and is also applicable for the same type of other logistics automatic equipment.

Problems and refilling models description

Under the condition of certain constraints of the refilling model, the locations and numbers of medicine storage cells, cargo of end effector as well as the appropriate route are determined by the specific rules. The capacity of the end effector is crucially important. It restricts the maximum number of the medicine storage cells, which are refilled in one operation. However, the end effector has to refill up all of the storage cells. Picking stand for medicine storage cells is selected to be refilled. Every picking has its own time and is called picking time. As medicine storage cell is called picking, and therefore, medicine storage time is called picking time. Medicine storage time is counted till the very moment when the final medicine box is refilled into the medicine storage cell.

If the shortage of all pickings exceeds the capacity of the end effector, the end effector has to operate more than once, and pickings refilled correspond to pickings of picking set. According to the rules of refilling models, if all pickings cannot be refilled by the end effector in just only one operation, any one of the pickings will be arranged at an operation in refilling process of the medicine. An operation of the end effector is recorded as a refilling path, and refilling route of a category of medicine consists of some refilling paths. Therefore, the influence factor of the refilling route is not only pickings but also the arrangement of pickings in every refilling path. Both of them are determined by the specific rules of the refilling model.

Refilling modes are divided into two modes, including temporary replenishment mode (TRM) and CRM. Different refilling models are selected for different refilling modes. In the operation of FMDS, the medicine is reminded to refill when storage of the medicine is lower than the threshold. The threshold is set by pharmacists or administrators according to the actual conditions. Under the circumstances, TRM is suitable for single medicine replenishment. After a period of dispensing medicines in FMDS, there will be a shortage of most of the medicines. In this condition, CRM is more suitable for the large quantities and replenishment of various medicines.

In terms of OPM, picking time, location, shortage of the picking, and cargo of the end effector are considered. According to the orders of pickings in picking sets, the refilling routing is generated, as shown in Figure 2. Based on the arrangement rules, pickings are assigned into picking sets under the constraint of the capacity of the end effector. The advantage of OPM is appropriate in TRM and CRM. The disadvantage is that the refilling route is searched not the shortest one because the shortest refilling route is not considered as the objective function.

Figure 2.

Pickings and picking sets processed.

A novel mixed refilling model, MTPSM and VRPM, is proposed in this article. It is regarded as two refilling models independently. One is MTPSM, and the other is VRPM. In Figure 2, MTSPM is a further study on OPM. MTSPM is different from OPM: the order of pickings is optimized by improved ACO algorithm in every picking set. It is just an optimization of picking order in every picking set separately, so the optimization is limited. The advantage of MTSPM is appropriate in TRM and CRM.

The optimization process of VRPM is different from that of MTSPM, and it has nothing to do with OPM. The shortest refilling route searched and the least number of refilling used are considered as the objective functions in VRPM. All pickings are stored into a picking set, and then, pickings of the picking set are assigned into some picking sets by ACO algorithm under the constraint of the capacity of the end effector. Pickings of one picking set are the same pickings as one of refilling paths. The orbit of refilling path depends on the order of pickings. The advantage of VRPM is that the refilling route searched is the shortest one. Yet, its disadvantage is that VRPM is appropriate in CRM only. Therefore, the mixed refilling model is proposed, which is not only to meet different refilling modes but also to search the shortest refilling route.

Refilling models

In FMDS, the initial data of picking points should be processed because the shortage of picking point may exceed the capacity of the end effector. Consequently, pickings are distributed in some picking sets, and the order of pickings is generated by the rules of refilling model. According to the order of pickings, refilling route is completed by the end effector. Figure 3 shows that pickings are distributed in picking sets by different refilling models.

Figure 3.

Refilling routes generated by different refilling models.

Initial data of pickings processed

Customers of conventional TSP or VRP are visited once only. Pickings have been processed because some pickings may be visited more than once. Pickings processed are similar to customers. In Figure 3, the process of pickings processed, which is from data pool A to data pool E, consists of pickings selected stage (from data pool A to data pool C) and data of pickings separated stage (from data pool C to data pool D or data pool E).

In pickings selected stage, if the medicine was stored in data pool A, pickings are selected and stored into data pool B while the medicine is being scanned. According to the rules, pickings are arranged and stored into data pool C from data pool B. Based on the rules of refilled time of picking, the earlier one is prioritized.

In data of pickings separated stage, if shortage of picking exceeds the maximum capacity of end effector, the picking has been separated into two parts. Pickings of data pool C are processed by equation (1) in the following detailed description, and pickings of data pool C processed are assigned to data pool D or data pool E according to the different circumstances.

The picking, current shortage of the picking, shortage of the picking stored in data pool D, shortage of the picking stored in data pool E, and the maximum capacity of the end effector are defined as i, L_i, $L_{i}^{"}$ , and $L_{i}^{,}$ , respectively. According to different heights of medicine boxes, q is variable. Location values of the picking are defined as i_x and i_y in the X and Y axes, respectively

L_{i}^{,} = \{\begin{matrix} L_{i} & \frac{L_{i}}{q} ≺ 1 \\ L_{i} - ⌊\frac{L_{i}}{q}⌋ q & \frac{L_{i}}{q} \geq 1 \end{matrix}

If $L_{i} / q < 1$ , data of the picking, $(i_{x}, i_{y}, {L'}_{i})$ , are stored in data pool E.

If $L_{i} / q \geq 1$ , data of the picking, $(i_{x}, i_{y}, {L'}_{i})$ , are stored in data pool E and data of the picking, $(i_{x}, i_{y}, {L ″}_{i})$ , are stored in data pool D, ${L ″}_{i} = ⌊L_{i} / q⌋$

According to equations (2) and (3), the minimum number of replenishing is calculated in data pool D and data pool E, respectively

E_{L} = ⌈\frac{\sum_{i = 1}^{N_{1}} {L'}_{i}}{q}⌉

D_{L} = ⌈\frac{\sum_{i = 1}^{N_{2}} {L ″}_{i}}{q}⌉

where N₁ and N₂ are numbers of pickings in data pool E and in data pool D, respectively. For the medicine, the optimal number of replenishing is $L = E_{L} + D_{L}$ .

When data pool C is empty, the process of pickings processed has been completed. In terms of pickings of data pool D, the ratio of the shortage of each picking to the capacity of the end effector is an integer value. The value is defined as s, $s = |\frac{L_{i}}{q}| .$ The replenishing process of the picking is regarded as the same repetitive process.

Each picking has been visited once in data pool E. As the number of pickings increases, the total shortage of all pickings exceeds the capacity of the end effector. In this case, all pickings are distributed into some picking sets. For each picking set, there is a refilling path in refilling process and an operation of end effector. The refilling route of the medicine is composed of some replenishing paths. Thus, it can be seen that picking set is an important factor in refilling route.

Picking sets generated

For picking sets generated, the picking rule of refilling model is the most important factor. There are two picking rules in OPM and MTSPM. Picking rule number one, if refilled time of the picking is earlier than others, then the picking is selected first and put into the picking set. Picking rule number two, if some pickings are selected by picking rule number one, then the picking closest to the X direction is selected. If the picking is more than one in the previous step, the picking closest to the Y direction is selected. According to equations (4) and (5), picking rule number one and picking rule number two are obeyed in the refilling model

\begin{array}{l} f_{(a_{x})} = {\begin{matrix} \sum_{i = X}^{M} {L'}_{i} & if \sum_{i = X}^{M} {L'}_{i} \leq q \\ \sum_{i = X}^{M - 1} {L'}_{i} & if \sum_{i = X}^{M} {L'}_{i} > q \end{matrix} \\ (X, M, N \in picking scheduling |1 \leq X, X \leq M, M \leq N) \end{array}

where $f_{(a_{x})}$ denotes the total shortage of one picking set. X, M, and N are numbers of picking order in the picking scheduling, N is the last number of picking in the picking schedule, and X is less than M, M is less than N.

f_{(a_{x})} = \{\begin{matrix} \sum_{i = X}^{M - N_{p}} {L'}_{i} + min (i_{y}, i_{x}) {L'}_{h} & if f_{(a_{x})} \leq q \\ \sum_{i = X}^{M - N_{p}} {L'}_{i} & if f_{(a_{x})} > q \end{matrix}

where p denotes that the pickings have the same refilled time in one picking set. N_p denotes the amount of pickings in p. Location values of the picking i are defined as i_x and i_v in the X and Y axes, respectively. Both are positive

\begin{array}{l} f_{(a)} = f_{(a_{1})} + \dots + f_{(a_{r})} + \dots + f_{(a_{R})} = \begin{matrix} \sum_{i = 1}^{N} {L'}_{i} \end{matrix} \\ (1 \leq r \leq R) \end{array}

E_{(L)} \leq R

where $f_{(a)}$ denotes the total shortage of all picking sets. r denotes the number of picking set. R stands for replenishing number of end effector. ${L'}_{h}$ and ${L'}_{i}$ are the pickings that are stored in p. Both of them mean the same thing, and it is just different ways to express.

In terms of VRPM, all pickings are put in one picking set only. The picking set is generated as given in equation (8)

f_{(a)} = \begin{matrix} \sum_{i = 1}^{N} {L'}_{i} \end{matrix}

After picking sets are generated, it is important to arrange the picking order in picking set. It affects the orbit of refilling path. In terms of OPM, according to the picking order in picking set, pickings are refilled. In terms of MTSPM and VRPM, the picking orders in picking set are optimized and they are different. Pickings are refilled based on the optimized picking order.

Picking order optimized

Picking sets of MTSPM are independent. Pickings have no relationship between different picking sets. Therefore, optimization of picking order in MTSPM is to optimize picking order of each picking set individually. Pickings are reordered in each picking set individually, and the optimization objective is to search for the shortest refilling path. As far as VRPM is concerned, all pickings are stored in one picking set only. The optimization objective is to search for the shortest refilling route. Thus, it can be seen that MTSPM is a local optimization model of picking order, and VRPM is a global optimization model of picking order.

In optimal path algorithms, ACO is regarded as one of the most efficient heuristic algorithms. It has been successfully applied to several NP-hard combinatorial optimization problems, primarily used in TSP, and it is effective.²⁹ VRP is first considered as a generalized form of the famous TSP formulated by Dantzig and Ramser.³⁰ ACO is used in solving this problem frequently and more effectively.^27,31,32 Therefore, ACO is used to optimize the picking order in this article.

A directed graph is defined as $G = {U, E}$ , $V = {U_{0}, U_{1}, \dots, U_{i}, \dots, U_{n}}$ . $U_{0}, U_{1}, \dots, U_{i}, \dots, U_{n}$ denote the n pickings, and the shortage of U_i is ${L'}_{i}$ . $E = {(i, j) | i, j \in U}$ is the arc set. Euclidean distance from picking i to picking j is defined as $d_{i j}$ $(i, j = 1, 2, \dots, N & i \neq j)$ . U₀, called zero point, denotes the initial point, which is the initial step of the end effector. n is the amount of pickings in the picking set.³³

For MTSPM, the minimum number of the picking set is processed firstly. The number of picking set is r in $f_{(a)}$ . The picking sets are generated based on equations (4) and (5). For VRPM, it has only one picking set. The picking set is generated based on equation (8). $b_{i} (t)$ shows the number of ants at t point in picking i. The pheromone concentration is defined as $τ_{i j} (t)$ at t moment on the edge between picking i and picking j. It is equal to $Δ τ_{i j} (t) = 0$ at $t = 0$ . Over time, the pheromone concentration on the path is changed because of new pheromone being applied and old pheromone evaporating. $ρ$ is set as volatility coefficient of the pheromone and showed the speed of evaporation.^27,34 When all ants completed one tour, the pheromone on each path is given as³⁵

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

where $Δ τ_{i j} (t) = \sum_{i = 1}^{N} Δ τ_{i j}^{k} (t)$

The pheromone concentration on a path is defined as $Δ τ_{i j} (t)$ . $Δ τ_{i j} (t)$ is expressed as the pheromone that is released on the path from picking i to picking j by ant k. The pheromone value is determined by the ant’s performance. A shorter path meant more pheromone is applied by the unit. Ant cycle is used in this article.^31,32

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

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

where ${allowed}_{k} = (U_{1}, U_{2}, \dots, U_{n}) - t a b U_{k}$ represents the collection of locations that could be chosen by ant k. $t a b 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 illustrated.³⁷ The inverse distance between picking i and picking j is shown as $η_{i j}$ , $η_{i j} = 1 / d_{i j}$ . $d_{i j}$ is the distance of the path value from picking i to picking j, which is calculated by equation (12) and is shown in Figure 4. α is the residual degree of information on $(i, j)$ edge. $β$ is the heuristic degree of information. Both of them could be changed by the user³⁸

d_{i j} = \{\begin{matrix} S_{x} & if \frac{[S_{x} / V_{x}]}{[S_{y} / V_{y}]} \geq 1 \\ S_{y} & other \end{matrix}

Figure 4.

$d_{i j}$ from picking i to picking j.

Simulation analysis and discussion

To ensure the experiment is repeatable and the refilling model is effective and universal, multigroup data are simulated in different refilling models. After comparing the length values of refilling routes by different refilling models, it can verify whether the novel refilling model is effective. The length value is the value of the refilling route, which is selected and composed of refilling paths. A closed and annular route called refilling path is generated by the end effector to a picking set in the refilling process. One refilling path consists of more d_ij in Figure 4. In the experiment, two test samples are adopted, and four group test data sets are included in one test sample. In the 50 time tests, the refilling path with the most repetitions is selected as a sample for analysis.

Test samples

In China, 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. The medicines are put in the end effector manually, and the maximum amount of medicine boxes is restricted by the heights of medicine boxes. In this randomized trial, two medicines are chosen from two different ranges of heights of medicine, as presented in Table 2.

Table 2.

Medicine information of test samples.

Number	Medicine name	Pharmaceutical manufacturers	Height (mm)	Max
1	Ethinylestradiol and cyproterone tablets	Zhejiang Xianju Pharmaceutical Co., Ltd	13.10	25
2	Amoxycillin capsules	United Laboratories Ltd	23.60	13

In Table 3, location, shortage, and the number of picking order in picking schedule are listed, and they represent with “picking,” “SPP,” and “ORT.” The data are from pharmacy server of a hospital. In four groups of test data sets, the amount of pickings includes 5, 10, 15, and 20. Experiments are implemented on a PC with a Pentium 4 CPU@2.4 GHz, 2 GB RAM, and Windows XP Operating system, and MATLAB 7.8 is used for simulation to select the refilling route.

Table 3.

Shortage and order of test samples.

Number	Picking	102	105	108	110	204	205	207	304	308	310
	SPP	1	2	16	3	7	4	8	20	5	6
	ORT	7	4	2	3	5	5	2	1	3	4
1	Picking	405	410	504	510	605	612	705	707	805	812
	SPP	9	10	12	11	13	14	15	19	17	18
	ORT	10	3	3	5	4	7	5	2	7	3
Number	Picking	103	107	109	203	206	209	305	309	402	404
	SPP	1	2	11	3	8	4	5	6	7	14
	ORT	2	4	1	3	1	1	2	3	5	2
2	Picking	407	505	507	604	610	702	706	710	802	806
	SPP	9	10	12	20	13	16	17	15	18	19
	ORT	1	3	1	2	1	5	1	7	2	1

Refilling route and refilling path

The sequence of pickings refilled is based on the picking order. The refilling route consists of all refilling paths in refilling processes of the medicine. Thus, the refilling route is described as a global refilling route, and the refilling path is described as a local refilling route. In Figure 5(b3), there are two refilling paths. Each refilling path starts from the initial point, travels some pickings, and returns back the initial point. The refilling route consists of two refilling paths.

Figure 5.

Refilling routes by simulation of OPM: (a1) 5 pickings, (b1) 10 pickings, (c1) 15 pickings, (d1) 20 pickings; (a2) MTSPM 5 pickings, (b2) 10 pickings, (c2) 15 pickings, (d2) 20 pickings; (a3) VRPM 5 pickings, (b3) 10 pickings, (c3) 15 pickings, (d3) 20 pickings. OPM: order picking model; MTSPM: multiple steps traveling salesman problem model; VRPM: vehicle routing problem model.

The amount of refilling paths and pickings of a medicine in each corresponding refilling path is the same as OPM and MTSPM. Picking orders are different in both of them. As far as VRPM is concerned, the amount of refilling paths, pickings of a medicine in each corresponding refilling path, and picking orders may be different from OPM and MTSPM.

Location of picking is defined by X and Y coordinates. For instance, picking 102, 2 denotes two units of X coordinate, and 1 denotes one unit of Y coordinate. A unit of X coordinate or Y coordinate denotes that the length is 12 cm.

Based on the picking rule of OPM, the second test picking set in the first test sample is adopted to generate the refilling route, as shown in Figure 5(b1). Five pickings (102, 105, 110, 205, 308) are included in the first refilling path. The sequence of pickings refilled is based on pickings’ order within the ORT in Table 2. Based on the refilled time of the picking, pickings’ order within the ORT is generated. Five pickings (310, 204, 207, 405, 410) are included in the second refilling path. The shortage of the first and the second refilling paths is 22 and 24, respectively. It can be seen that there are different shortages in different refilling paths. In terms of refilling paths, the different amount is loaded in the end effector.

Based on the picking rule of MTSPM, the second test picking set in the first test sample is adopted to generate the refilling route, as shown in Figure 5(b2). Five pickings (102, 105, 110, 308, 205) are included in the first refilling path. Five pickings (204, 207, 310, 410, 405) are included in the second refilling path. Thus, it can be seen that, compared with OPM, pickings are the same in the corresponding refilling path. The difference is the pickings’ order.

Based on the picking rules of VRPM, the second test picking set of the first test sample is adopted to generate the refilling route, as shown in Figure 5(b3). Six pickings (405, 207, 308, 410, 310, 110) are included in the first refilling path. Four pickings (102, 204, 205, 105) are included in the second refilling path. The shortage of the first and the second refilling paths is 25 and 21, respectively. Thus, it can be seen that, compared to OPM, MTSPM, picking amount, pickings, and pickings’ order are different in refilling paths. Therefore, different lengths of refilling route are adopted by different refilling models accordingly.

Simulation diagrams and analysis

According to four group test data sets of two test samples, length values of refilling route generated from three different refilling models are listed in Table 4. The length value is based on the orbit of refilling route shown in Figures 5 and 6.

Table 4.

Test results of three models.

Test sample	Algorithm model	Pickings (5)	Pickings (10)	Pickings (15)	Pickings (20)
1	OPM	27.0414	65.1632	106.4311	144.2082
1	MTSPM	21.6119	44.6494	73.9542	107.5128
	VRP	21.6119	31.0997	44.3590	61.0016
Test sample	Algorithm model	Pickings (5)	Pickings (10)	Pickings (15)	Pickings (20)
2	OPM	27.2394	59.8126	101.7417	131.1844
	MTSPM	19.8286	41.4220	69.0011	91.7284
	VRP	19.8286	30.7739	44.4375	57.8021

OPM: order picking model; MTSPM: multiple steps traveling salesman problem model; VRPM: vehicle routing problem model.

Figure 6.

Refilling routes by simulation of OPM (e1) 5 pickings, (f1) 10 pickings, (g1) 15 pickings, (h1) 20 pickings; MTSPM (e2) 5 pickings, (f2) 10 pickings, (g2) 15 pickings, (h2) 20 pickings; VRPM (e3) 5 pickings, (f3) 10 pickings, (g3) 15 pickings, (h3) 20 pickings. OPM: order picking model; MTSPM: multiple steps traveling salesman problem model; VRPM: vehicle routing problem model.

Simulation diagrams and analysis of the first test sample

In Figure 5 and Table 4, the comparisons of the length values of refilling routes from different refilling models are shown below.

When the amount of picking set is one and amount of pickings is five, the length values of refilling routes by MTSPM and by VRPM are identical, and both of them are shorter than the length values of refilling route by OPM, as shown in Figure 5 (a1), (a2), (a3).

When the amount of picking sets is 3, 4 and the amount of pickings is 15, 20, respectively, experiment results are the same as the results when the amount of picking sets is 2. The reasons analyzed as follows: the objectives of MTSPM and VRPM are to search for the shortest travel route. The picking orders are optimized. Both of them result in shorter length values of refilling routes by MTSPM and VRPM than that of OPM. The length values of refilling routes by MTSPM and VRPM are the same. The reason is that there is only one picking set, and multiple steps have been merged into one step in MTSPM. The optimized steps are different and the optimized effect depends on ACO when only one picking set is optimized on picking order either by MTSPM or by VRPM. As pickings increased, the length value of refilling routes by VRPM is shorter than the length value of refilling routes by MTSPM. The reason is that picking order is optimized in MTSPM just for picking order of each picking set separately, but picking order is optimized in VRPM for all pickings.

When the amount of pickings is 5, the refilling route has only one refilling path by OPM, and the refilling path is a part of the refilling route when the amount of pickings increases to 10, 15, and 20. Pickings and travel path have not been changed in the refilling path. It showed that the refilling route including 10 pickings, 15 pickings which is a part of refilling route when the amount of pickings increases to 15 and 20, or 20, respectively, as shown in Figure 5(a1), (b1), (c1), and (d1). Therefore, several pickings of refilling route are a part of large pickings of refilling route when pickings are arranged as the same order in OPM. In MTSPM, there are some similarities to OPM, as shown in Figure 5(a2), (b2), (c2), and (d2). The reason for this is that one picking corresponds to one refilling path. In terms of MTSP and MTSPM, as the amount of pickings increased, some refilling paths are increased. However, picking order and pickings have no change in the existing refilling paths.

In terms of VRPM, several pickings of refilling route are not a part of large pickings of refilling route, as shown in Figure 5(a3), (b3), (c3), and (d3). The reason for this is that optimal picking order is considered for all pickings, and each picking is arranged in an appropriate picking set. Because of the change of amount of pickings, the refilling route is quite different.

In summary, when the amount of pickings is low or all pickings can be stored in a picking set, the length values of refilling route by MTSPM and by VRPM are the same. Both of them are shorter than the length value of refilling route selected by OPM. When all pickings are stored in more than one picking set, the length value of refilling route is the shortest by VRPM.

Under the same condition, the length value of refilling route by VRPM is shorter than the length value of refilling route by OPM or by MTSPM. The length value of refilling route by MTSPM is shorter than the length value of refilling route by OPM. The optimum refilling route is searched by VRPM, but VRPM is only applied in CRM. The mixed refilling model, MTSPM and VRPM, is not only applicable for all refilling modes but also for searching the shortest refilling route.

Simulation diagrams and analysis of the second test sample

In Figure 6 and Table 4, given the same amount of pickings as the first test sample, the results of refilling routes are different from the first test sample because of different pickings. Yet, the optimized effect is similar to the first test sample. Thus, it is proved that MTSPM is better than OPM for searching the refilling routes, and VRPM is better than OPM for searching the refilling routes. As pickings increased, VRPM is better than MTSPM for searching the refilling routes.

Optimized rate of different refilling models analyzed and discussion

In Figure 7, the optimized rate of OPM-MTSPM (1) is calculated by using the length value of refilling route simulated by OPM and that of MTSPM, where “(1)” represents the first test sample. The horizontal axis represents the number of pickings in equation (13). The other calculations are the same. The formula for calculation is as follows

OPM - {MTSPM}_{(1)} = \frac{{OPM}_{x} - {MTSPM}_{x}}{{OPM}_{x}}

Figure 7.

(a) Optimized rates and (b) difference of optimized rate with different models.

The comparison can be summarized as below:

(1) In Figure 7(a), OPM-MTSPM and OPM-VRPM, compared with the length value of refilling route by OPM, the length value of refilling route by MTSPM or VRPM is shorter when the amount of pickings is 5, 10, 15, and 20. That is because the picking order of OPM follows the arranged rule, which is mainly considered as refilled time of each picking. The picking order of MTSPM or VRPM follows the arranged rule, which determines searching the shortest refilling route. In Figure 7(a), as shown in MTSPM-VRPM, the length value of refilling route by VRPM is shorter than the length value of refilling route by MTSPM when the amount of pickings is 10, 15, and 20. The reason for this is that, under the limited condition of MTSPM, pickings are arranged in some picking sets based on refilled time of the picking. The limited condition does not exceed the maximum capacity of the end effector. The objective function searches the shortest refilling path and picking order is optimized in each picking set. Therefore, optimized picking order of MTSPM only can be seen as a local optimization.

Under the limited condition of VRPM, pickings are arranged in some picking sets based on the objective function. The objective function searches the shortest refilling route, and all pickings are considered in the process of optimization of picking order. Thus, the optimized picking order of VRPM can be seen as a global optimization. Only one picking set needs to be created when there are a few pickings. In the test sample, when the amount of pickings is 5, the picking order of MTSPM is optimized from all pickings. In this case, picking order optimized of MTSPM can be seen as a global optimization. Hence, the refilling route searched by MTSPM is similar to that of VRPM.

(2) In Figure 7(a), OPM-MTSPM-(1) and OPM-MTSPM-(2), optimized rates of length value are more than 20.07%, 30.74%, 30.51%, and 25.44% when the amount of pickings is 5, 10, 15, and 20, respectively. The optimized rate is more than 20%, but it increased at first and then decreased, and the changing ranges are different. In Figure 7(b), OPM-MTSPM-(1) and OPM-MTSPM-(2), to the change range of OPM-MTSPM, minimal change range is more than 20.07% when the amount of pickings increases to 5. The minimal change range is more than 3.54% when the amount of pickings increases to 10 from 5. Negative growth occurred, and the change range is less than −0.97% when the amount of pickings increases 15 from 10. The change range is less than −5.07% when the amount of pickings increases to 20 from 15.

Optimized picking order and pickings arranged in some picking sets affect the trends and the changing range of OPM-MTSPM. The picking order of OPM is optimized by MTSPM, not only it ensures that the length value of refilling route by MTSPM is shorter than that of OPM but also it is the main cause of that optimized rate of OPM-MTSPM is more than 20%. The shortest refilling route searched is not regarded as the objective function in OPM when pickings are arranged in some picking sets. And the picking order optimized is only for each individual picking set. It is the main reason for changing the range to an optimized rate of OPM-MTSPM. In this case, in terms of OPM, some crosses may occur in a refilling path. As far as MTSPM is concerned, some crosses may occur in refilling paths. The influence factor of pickings arranged in some picking sets plays an increasingly influential part when more crosses occur. The trend, which is increased at first and then decreased, is affected by optimized picking order and pickings arranged in some picking sets. From the effects point of view, optimized picking order is very important when the amount of picking is low. Arranged pickings in some picking sets are important when the amount of picking increases because more and more crosses show in refilling route.

(3) In Figure 7(a), OPM-VRPM-(1) and OPM-VRPM-(2), the optimized rates of the length value are more than 20.07%, 48.54%, 56.32%, and 55.93% when the amounts of pickings are 5, 10, 15, and 20, respectively. The rate increases at first and then decreases, and the change ranges are different. In Figure 7(b), OPM-VRPM-(1) and OPM-VRPM-(2), in terms of changing range of OPM-VRPM, the minimal changing range is more than 20.07% when the amount of pickings increases to 5. The minimal changing range is more than 21.34% when the amount of pickings increases to 10 from 5. The minimal changing range is more than 6.05% when the amount of pickings increases to 15 from 10. Negative growth occurs and the changing range is less than −0.63% when the amount of pickings increases to 20 from 15.

Optimized picking order and pickings arranged in some picking sets affect the trend and changing range of OPM-VRPM. In terms of VRPM, the objective functions search the shortest refilling route and select the least amount of refilling paths. Meanwhile, the capacity of the end effector is limited. There are a few crosses in refilling route by VRPM, but they are much less than that of OPM.

(4) In Figure 7(a), MTSPM-VRPM-(1) and MTSPM-VRPM-(2), when the amount of pickings is 5, there is no optimization to refilling route by VRPM. The optimized rates of length values are more than 25.70%, 35.59%, and 36.98% when the amounts of pickings are 10, 15, and 20, respectively. The rates increase, but variation scopes are different.

In Figure 7(b), MTSPM-VRPM-(1) and MTSPM-VRPM-(2), in terms of the changing range of MTSPM-VRPM, the minimal changing range is more than 25.70% when the amount of pickings increases to 10 from 5. The minimal changing range is more than 9.67% when the amount of pickings increases to 15 from 10. The minimal changing range is more than 1.39% when the amount of pickings increases to 20 from 15.

In all, when all pickings can be included in one picking set, the reason for no optimization to refilling route by VRPM is that local optimization becomes a global optimization. In this case, the optimized picking order of all pickings by MTSPM is similar to that of VRPM. Only the optimization steps are different.

The reason for the trend increasing is a local optimization in MTSPM, and it is a global optimization in VRPM. Therefore, with the same pickings, the picking order by VRPM is more optimal than that of MTSPM. Optimized picking order and pickings arranged in some picking sets affect the trend and changing range of MTSPM-VRPM. In terms of VRPM, it is a multiobjective optimization problem. The objective functions search the shortest refilling route and select the least amount of refilling paths. Under the same conditions, the shortages of pickings are different, and the capacity of the end effector is limited. Some crosses occur in refilling route. With pickings increased, crosses increase and optimization efficiency reduces. In summary, the length value of refilling route by VRPM is obviously shorter than that of OPM or MTSPM when the amounts of pickings are adopted between 5 and 20. But VRPM is used in CRM only. A mixed refilling model, MTSPM and VRPM, is adopted to refill medicine in FMDS in this article. Compared with OPM, the mixed refilling model is more capable of searching the shortest refilling route. It applies to all refilling mode. In the study, although the length values of the refilling route by VRPM and by MTSPM are shorter than that of VRPM under the same pickings, and this may be not the shortest refilling route searched by MTSPM or by VRPM. Optimized picking order relates to ACO. Thus, ACO needs further improvement. Meanwhile, in some cases, the length values of optimized refilling route by the mixed refilling model are not obvious. For example, when it has only one picking, the refilling route searched by OPM, or by MTSPM, or by VRPM is the same. As pickings increased, it grows optimization effect significantly.

Conclusions

A new refilling model, which is named as MTSPM and VRPM, is presented in this article. This model has played an important role in medicine refilling processes. The track of refilling route depends on the picking order. Picking order is based on refilled time in OPM. On the basis of OPM, picking order of pickings in each picking set is optimized, respectively, in MTSPM. In terms of VRPM, the refilled time is no longer considered a constraint condition. All pickings are considered in picking order. Although the length values of refilling route by VRPM are the shortest, VRPM applies in CRM only. To verify the mixed refilling model of optimization, optimized effect and the trend between refilling models are compared and analyzed. Two test samples and four test picking sets in each test sample are adopted in this article. The experimental results show that the length values of refilling route searched by VRPM or by MTSPM are shorter than that of OPM under the same pickings, and the optimized rates of the length values are more than 20% when the amount of pickings is between 5 and 20. As pickings increased, the influence factor of pickings arranged in some picking sets becomes very important, and it is the reason that causes rises followed by decline of the optimized rates. Meanwhile, optimized picking order by MTSPM is considered as a local optimization, and optimized picking order by VRPM is considered as a global optimization. Hence, the length value of refilling searched by VRPM is shorter than the length value of refilling searched by MTSPM. Therefore, the mixed refilling model, MTSPM and VRPM, can be adopted to use in all refilling modes, and the length value of refilling route is searched.

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 the receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the General Program of Chongqing Science and Technology Commission [cstc2019jcyj - msxmX0161] and Technology Innovation and application project of Chongqing Municipal [cstc2019jscx-msxmX0006].

ORCID iDs

Hui Jin

Fangchao Hu

References

Lee

Kwag

SII

. Optimal capacity and operation design of a robot logistics system for the hotel industry. Tour Manage 2020; 76: 103971.

Nielsen

Sung

Nielsen

. Convex decomposition for a coverage path planning for autonomous vehicles: interior extension of edges. Sensors 2019; 19(19): 1–11.

Zhao

Wang

Stoeter

, et al. Path optimization model for intra-city express delivery in combination with subway system and ground transportation. Sustainability 2019; 11(3): 1–25.

Vazifeh

Santi

Resta

, et al. Addressing the minimum fleet problem in on-demand urban mobility. Nature 2018; 557: 534–538.

Zhang

Wen

, et al. Research on outlier detection algorithm for express logistics. Comput Ind 2017; 92–93: 43–49.

Huang

Savkin

. Viable path planning for data collection robots in a sensing field with obstacles. Comput Commun 2017; 111: 84–96.

Jin

Yun

Wang

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

Jin

Yun

Gao

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

Norouzi

Miro

Dissanayake

. Planning stable and efficient paths for reconfigurable robots on uneven terrain. J Intell Robot Syst 2017; 87: 291–312.

10.

Gao

Liu

, et al. A new path evaluation method for path planning with localizability. IEEE Acc 2019; 7: 162583–162597.

11.

Song

Pan

Chu

. A parallel compact cuckoo search algorithm for three-dimensional path planning. App Soft Comp 2020; 94: 106443.

12.

Nazarahari

Khanmirza

. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm. Exp Syst Appl 2019; 115: 106–120.

13.

Yang

. Express logistics distribution model optimization for e-commerce environment. In: International conference on smart grid and electrical automation, Changsha, China, 27–28 May 2017, pp. 473–476.

14.

Gao

Xin

Cheng

, et al. Multi-mobile robot autonomous navigation system for intelligent logistics. In: Chinese automation congress, Xian, China, 30 November–02 December 2018, pp. 2603–2609.

15.

Jiang

Fan

Sheng

. Research on path guidance of logistics transport vehicle based on image recognition and image processing in port area. Eur J Image Vid Process 2018; 2018: 141.

16.

Mei

Zhou

. Research and design of a path planning algorithm in the intelligent logistics sorting system. In: IEEE 3rd advanced information technology, electronic and automation control conference (IAEAC), Chongqing, China, 12–14 October 2018, pp. 2008–2012. IEEE.

17.

Liu

Wang

Peng

. Cooperative path following ring-networked under-actuated autonomous surface vehicles: algorithms and experimental results. IEEE Trans Cybern 2020; 50(4): 1519–1529.

18.

George

. Exploring the common prescribing errors that occur in the emergency department. Emerg Nurse 2020; 28: 17–22.

19.

Lim

Yates

Liang

. Out of sight: a lesson in drug errors. Pract Neurol 2020; 20: 243–245.

20.

Liu

. Structure design and realization of rapid medicine dispensing system. In: International conference on mechanical engineering and control system (MECS), Wuhan, China, 23–25 January 2015, pp. 13–16. Singapore: World Scientific Publ Co PTE LTD.

21.

Lizuka

. Markets with physcian dispensing. Encyl Heal Eco 2014; 221–227.

22.

Sung

Hsieh

. Policy satisfaction for separation of dispensing from medical practices in Taiwan: success of the prescription-release information system. Telemat Inform 2014; 31: 334–343.

23.

Bobers

Skopic

Dinter

. Design of an automated reagent-dispensing system for reaction screening and validation with DNA-tagged substrates. ACS Comb Sci 2020; 22: 101–108.

24.

Roman

Poole

Walker

, et al. A ‘time and motion’ evaluation of automated dispensing machines in the emergency department. Australas Emerg Nurs J 2016; 19: 112–117.

25.

Dauod

Serhan

Wang

. Robust receding horizon control strategy for replenishment planning of pharmacy robotic dispensing systems. Robot Comput Integ Manuf 2019; 59: 177–188.

26.

Ozturkoglu

Hoser

. A new warehouse design problem and a proposed polynomial-time optimal order picking algorithm. J Fac Eng Archit Gazi Univ 2018; 33: 1569–1588.

27.

Jin

Wang

Cai

, et al. Ant colony optimization model with characterization-based speed and multi-driver for the refilling system in hospital. Adv Mech Eng 2017; 9: 1–10.

28.

Che

Kang

, et al. A simulation-based genetic algorithm approach for refilling process with clip type passive manipulator. In: 15th International conference on intelligent systems design and applications, Marrakech, Morocco, 14–16 December 2015, pp. 368–373.

29.

Fadl

Khalil

Hassan

, et al. Dynamic flying ant colony optimization (DFACO) for solving the traveling salesman problem. Sensors 2019; 19: 1–30.

30.

Dantzig

Ramser

. The Truck Dispatching Problem. Management Sci 1959; 6: 80–91.

31.

Chen

Gui

Ding

. Optimization of transportation routing problem for fresh food by improved ant colony algorithm based on tabu search. Sustainability 2019; 11(23): 1–22.

32.

Stodola

. Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem. Nat Comput 2020; 19: 463–475.

33.

Luo

Wang

Zheng

, et al. Research on path planning of mobile robot based on improved ant colony algorithm. Neural Comput App 2020; 32: s1555–s1566.

34.

Wang

Xia

Gao

, et al. Improved ant colony-genetic algorithm for information transmission path optimization in remanufacturing service system. Chin J Mech Eng 2018; 6: 107–118.

35.

Sagban

Ku-Mahamud

Abu

, et al. Reactive max-min ant system with recursive local search and its application to TSP and QAP. Intell Auto Soft Comput 2017; 23: 127–134.

36.

Habir

Panicker

Sridharan

. Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem. Transp Res Part D Trans Environ 2017; 57: 422–457.

37.

Zhang

, et al. Multi-objective optimisation in flexible assembly job shop scheduling using a distributed ant colony system. Euro J Oper Res 2020; 283: 441–460.

38.

Arnaout

Elkhoury

Karayaz

. Solving the multiple level warehouse layout problem using ant colony optimization. Oper Res 2020; 20: 473–490.