# AGV Scheduling Optimization for Medical Waste Sorting System

Authors: Xueting He; Hao Quan; Wanlong Lin; Weiliang Deng; Zheyi Tan
Journal: Scientific Programming
 (2021)

---

## Abstract

The dramatic increase in medical waste has put a severe strain on sorting operations. Traditional manual order picking is extremely susceptible to infection spread among workers and picking errors, while automated medical waste sorting systems can handle large volumes of medical waste efficiently and reliably. This paper investigates the optimization problem in the automated medical waste sorting system by considering the operational flow of medical waste. For this purpose, a mixed-integer programming model is developed to optimize the assignment among medical waste, presorting stations, and AGVs. An effective variable neighborhood search based on dynamic programming algorithm is proposed, and extensive numerical experiments are conducted. It is found that the proposed algorithm can efficiently solve the optimization problem, and the sensitivity analysis gives recommendations for the speed setting of the conveyor.


---

## Body

## 1. Introduction

Medical waste carries a large number of pathogenic microorganisms and harmful chemicals, making it an important risk factor for the spread of disease. Medical waste, if not properly recycled and disposed of, poses a great threat to the environment and human health. In recent years, the rapid development of China's healthcare industry has inevitably caused the problem of a sharp increase in medical waste. The recent outbreak of the novel coronavirus has stimulated the demand for medical services and protective equipment, causing the amount of medical waste to increase exponentially. The medical waste generated during an epidemic is highly infectious and prone to secondary contamination if not timely and correctly disposed of. Additionally, the current disposal rate of medical waste cannot meet the growth rate of medical waste. Therefore, how to collect and dispose of medical waste safely and efficiently is particularly important to protect human health, maintain ecological safety, and promote sustainable social development.The disposal process of medical waste mainly includes classification and collection, transportation, and recycling. As the last segment of the medical waste disposal process, the recycling, which comprises sorting and reuse or incineration to landfill, occupies a significant role. The recycling of medical waste can reduce the infection rate as well as improving the utilization of resources. For example, recycling decreases the utilization of forests, mined metals, and oil, and it also reduces greenhouse gas emissions by decreasing the amount of waste disposed of in landfills [1]. For traditional reasons, quite a few medical waste disposal centers still use the manual sorting method. However, the dramatic increase in medical waste has put a severe strain on sorting operations, and traditional manual sorting is no longer capable of handling large volumes of medical waste efficiently and safely.With the rapid development of automation technology and information technology, the application of automatic sorting systems is becoming more and more widespread. Besides, automated sorting systems are currently used in a variety of industries, such as the postal industry, warehouses, cross docks, and airports, due to their fast processing speed, ability to efficiently handle large volumes of goods, and reliable processes. Considering that medical waste is infectious, toxic, and hazardous, the application of automated sorting systems can greatly reduce the infection rate of operators and improve the efficiency of medical waste disposal compared with traditional manual sorting.Due to the large amount of medical waste that needs to be sorted, medical waste recycling and processing centers (MWRPC) face the requirements for small orders, high volume, and strict work schedules, which are similar to e-commerce warehouses. Nowadays, automated sorting systems, such as automated picking workstations, robots, and AGV-assisted order picking systems, are widely used in e-commerce warehouses to process a huge number of parcels quickly and accurately [2]. Among the various automated sorting systems, vertical sorting systems can be used in MWRPC to reduce staff infection rates and improve the efficiency of medical waste sorting due to the high level of automation and the efficient and reliable handling of packages. Therefore, based on the operational flow of medical waste in an automated sorting system, this paper develops a mixed-integer linear programming model with the objective of minimizing the time to finish processing a batch of medical waste by optimizing the allocation of resources such as presorting table, sorting AGV, and resorting area in the sorting system. To improve the computational efficiency, a variable neighborhood search (VNS) algorithm based on dynamic programming (DP) is designed for the problem. The validity of the model and algorithm is verified by numerical experiments, and a sensitivity analysis is performed to derive management insights.The remainder of this paper is organized as follows. The related literature review is presented in Section2. Section 3 gives a detailed description of the proposed problem; then, a mathematical model is formulated in Section 4. A variable neighborhood search algorithm based on dynamic programming is designed to solve this problem in Section 5. Extensive numerical experiments are conducted in Section 6, and conclusions are drawn in Section 7.


## 2. Literature Review

This study is related to the AGV scheduling optimization problem for a specific kind of object, medical waste. Here some closely related studies are discussed as follows.A comprehensive summary of research on medical waste management in China was provided by He et al. [3], which found that the existing studies are mainly from a macroperspective and defined that medical waste recycling consists of two main aspects: collection and disposal. Mantzaras and Voudrias [4] developed a model to optimize the design of a whole process system for infectious medical waste. Fraifeld et al. [5] discovered that failure to properly segregate medical waste could lead to the misuse, environmental pollution, and increased costs to institutions. Taslimi et al. [6] designed a weekly inventory routing schedule to transport medical wastes to disposal centers, and a heuristic algorithm was devised to solve this problem. Ghannadpour et al. [7] focused on the real-life medical waste collection vehicle routing problem of small medical centers in Iran and aimed to reduce public health risks by minimizing the waste collection time. During the disposal process of medical waste, Liu et al. [8, 9] designed a medical waste classified disposal system based on the RFID technology, and the application of this system model can strictly supervise the classification and disposal of medical waste, effectively reduce the spread of germs, and protect the environment.The vertical sorting system mainly consists of cross-belt conveyor, AGVs, picking station, etc., and previous scholars have done various studies in all aspects. As for the conveyor-based system, Boysen et al. [10] provided a comprehensive review about various types of fully automated conveyor-based sorting system and divided decision problems into the following four areas: layout design, inbound problems, outbound problems, and short-term scheduling decisions. Fedtke and Boysen [11] stressed that the number of loading stations and its correlation with inbound and outbound destinations were shown to influence the throughput of a hub terminal. Briskorn et al. [12] investigated the short-term decision problem to minimize the makespan and derived some basic design rules. In warehouses, order consolidation processes are inevitable when zoning and batching process is performed. To enable fast assembly of picking orders to their packing stations, Boysen et al. [13, 14] optimized bins released from automated storage/retrieval system in their specific warehouse setting. Chen et al. [15] studied the integrated order batching, sequencing, and routing problem in warehouses. An algorithm integrating hybrid coded genetic algorithm and ant colony optimization was developed to solve the nonlinear mixed-integer model.Besides, robots and AGVs are the critical resources in RMFS and AGV-based picking systems, so the research on robot routing, driving behavior, and operational strategies has received much attention. Vis [16] discussed literature related to design and control issues of AGV systems at manufacturing, distribution, transshipment, and transportation systems. Xie et al. [17] concentrated on decisions about the assignment of shelves to stations and orders to stations in robotic mobile fulfillment systems, and they presented a new MIP model to integrate both decision problems. Gharehgozli and Zaerpour [18] studied the operational problem of scheduling a mobile robot fulfilling a set of customer orders from a pick station. They formulated the basic problem as an asymmetric traveler problem and extended the model by adding priority constraints to provide different priorities for customer orders depending on their urgency.Metaheuristics are crucial to accelerate convergence, and some local search heuristics are used to avoid trapping in local optimum, like Critical-Searching Neighborhood Search [19, 20] and Squeaky Wheel Optimization [21, 22]. Two variable neighborhood search algorithms are used to solve joint order batching and picker routing problem and clustered vehicle routing problem [23, 24]. Hintsch and Irnich [25] proposed that the standard approach for the shortest-path problem with resource constraints was based on dynamic programming labeling algorithms. Cimen and Soysal [26] used hybrid genetic algorithm with variable neighborhood search to solve vehicle routing problem.The review of the literature reveals that many works have been done to reduce the infection rate and improve medical waste disposal efficiency. While most studies on medical waste management have focused on the medical waste transportation aspect, studies on MWRPC are rare. Considering that medical waste and parcel have many similar characteristics, such as large quantity and strict timetable, it is highly feasible to apply the automatic sorting system to the MWRPC. The novelty of our work is fourfold. First, we study the sorting process in the medical waste recycling and processing center based on the automatic sorting system. Second, we investigate the operational problem of a vertical sorting system and transform the problem into a mixed-integer programming model. Third, we proposed VNS/DP algorithm for problem solving. Finally, some managerial insights are concluded according to numerical experiment.


## 3. Problem Description

The disposal process of medical waste mainly includes classification and collection, transportation, and recycling. Firstly, medical waste is generated and placed by medical personnel in designated recycling bags and recycling bins according to its category. Then, the medical waste temporarily stored in the hospital is transported to a medical waste disposal center. Finally, medical waste is sorted and disposed for reprocessing or incineration to landfill. Medical waste is usually divided into five categories: infectious waste, pathological waste, injury waste, pharmaceutical waste, and chemical waste. However, in the actual recycling activities, medical waste usually needs to be classified again according to its composition. For example, it can be divided into waste glass, waste metal, waste plastic, waste rubber, paper, pharmaceuticals, etc. [3]. Medical wastes are briefly classified and represented in Figure 1.Figure 1
Classification of medical wastes.The vertical sorting system consists of an induction station, a cross-belt conveyor, several presorting stations, some trailers, and a fleet of AGVs. The induction station is used to capture information on the type of medical waste which would be used in sorting. The cross-belt conveyor is used to transfer different categories of medical waste to the corresponding presorting tables. A presorting station has a slide for receiving medical waste from the cross-belt conveyor and a mechanical arm for placing parcels onto AGV. The AGV fleet is assigned to transport medical waste to the trailers and complete the sorting. Trailers are used to collect different types of medical waste.Therefore, the sorting process for medical waste is as follows. Firstly, medical waste enters the system through the induction station in turn, while the induction station identifies medical waste information. Secondly, medical waste proceeds along the conveyor and is led by the conveyor to chutes of presorting stations as soon as it reaches the designated presorting station. Thirdly, once the medical waste arrives at the presorting station, it is carried by the mechanical arm on the presorting station to an AGV that has already arrived at the presorting station in advance. Finally, the AGV loaded with medical waste travels to the location of the designation trailer and drops the package into the trailer. Then, the AGV moves to the next designated sorting station to transport the next medical waste.Figure2 illustrates the sorting process in vertical sorting system. From the above sorting procedures, we can summarize several decision problems that are crucial for the sorting process in vertical sorting system. First, different categories of medical waste need to be assigned to the suitable presorting stations to accomplish the initial sorting process of medical waste. Second, the transportation routes of AGVs require reasonable allocation and scheduling to complete the final sorting of medical waste. In addition, there is a tight limit on the processing time of medical waste, and large batches of medical waste need to be sorted urgently, so the completion time of the last medical waste is used as the optimization objective in this paper.Figure 2
A top view of automated medical waste sorting system.Before modeling the sorting problem, several assumptions need to be cleared.(a)
The destination information of the medical waste and the trailer designated for the medical waste are known in advance.(b)
There is no waiting time for the processing of medical waste. This means that when medical waste arrives at the presorting table, it needs to be immediately carried by the mechanical arm to the AGV that arrives at the presorting table in advance.(c)
A presorting table can process no more than one defined category of medical waste, and the medical waste belonging to the same category can only be processed by a certain presorting station.


## 4. Mathematical Model

In this section, a mixed-integer programming model for the sorting problem is presented. The objective of the model is to minimize the completion time of last medical waste.


### 4.1. Notations

The following notations are introduced to the model:Indices and sets are given as follows:P: set of medical wasteP1: a subset of medical waste, P1⊆P,2≤P1≤PI: set of presorting stationsJ: set of AGVsT: set of medical waste categoriesParameters are given as follows:e,e^: dummy points for the start point and end point of AGV routesh: the handling time for the mechanical arm at the presorting stationmp,p′: set to one when medical wastes p and p′ belong to the same category and medical waste p′ enters the induction station after medical waste p, and to zero otherwisefp: category of medical waste pci1: medical waste travel time of conveyor from induction station to presorting stationci,p2: AGV travel time from presorting station i to trailer for medical waste pgp: the time of medical waste p released to the induction stationDecision variables are as follows:μi,t: set to one if medical wastes belonging to category t are allocated to presorting station i, and to zero otherwiseνp,p′,j: set to one if medical waste p′ is transported by AGV j right after medical waste p, and to zero otherwiseρp,j: set to one if medical waste p is transported by AGV j, and to zero otherwiseφp,j: the arrival time of AGV j to the presorting station which handles medical waste pτp,j: the start time of medical waste p being transported by AGV jζj: the time of AGV j finishing all its transporting tasks


### 4.2. Mathematical Model

(1)Minimizemaxj∈Jζj,s.t.(2)∑i∈Iμi,t=1,∀t∈T,(3)∑t∈Tμi,t≤1,∀i∈I,(4)∑j∈Jρp,j=1,∀p∈P,(5)∑p∈P∪eνp,p′,j=∑p∈P∪e^νp′,p,j=ρp′,j,∀p′∈P,j∈J,(6)∑p∈P∪e^νe,p,j=∑p∈P∪eνp,e^,j=1,∀j∈J,(7)∑p∈P1∑p′∈P1νp,p′,j≤P1−1,P1⊆P,2≤P1≤P,∀j∈J,(8)φp′,j≤τp,j+h+∑i∈Ici,p2μi,fp+∑i∈Ici,p2μi,fp′+M1−νp,p′,j,∀p∈P,p′∈P,j∈J,(9)φp′,j≥τp,j+h+∑i∈Ici,p2μi,fp+∑i∈Ici,p2μi,fp′−M1−νp,p′,j,∀p∈P,p′∈P,j∈J,(10)τp′,j′≥τp,j+h−M3−mp,p′−ρp,j−ρp′,j,∀p,p′∈P,j,j′∈J,(11)τp,j≥gp+∑i∈Ici1μi,fp+Mρp,j−1,∀p∈P,j∈J,(12)τp,j≤gp+∑i∈Ici1μi,fp−Mρp,j−1,∀p∈P,j∈J,(13)φp,j≤τp,j,∀p∈P∪e,e^,j∈J,(14)τp,j≤Mρp,j,∀p∈P,j∈J,(15)ζj≥τp,j+h+∑i∈Ici,p2μi,fp+Mρp,j−1,∀p∈P,j∈J,(16)μi,t,νp,p′,j,ρp,j∈0,1,∀p,p′∈P∪e,e^,j∈J,t∈T,(17)φp,j,τp,j≥0,∀p,p′∈P∪e,e^,j∈J,where objective (1) minimizes the latest completion time for a particular batch of medical waste sorting. Constrains (2) ensure that medical waste with the same category is allocated to only one presorting station. Constraint (3) guarantees that each presorting station handles at most one category of medical waste. Constraint (4) stipulates that each medical waste is transported by only one AGV. Constraints (5) and (6) ensure the continuity of the AGV transportation routes. Constraint (7) prevents the transportation routes of AGVs from forming loops. Constraints (8) and (9) indicate that if medical waste p′ is transported by the AGV j right after medical waste p, the arrival time of the AGV to the presorting station serving medical waste p′ cannot be earlier than the travel time at which AGV j transports medical waste p and then travels to the presorting station serving medical waste p′. Constraints (10) guarantee that if parcel p′ is handled right after parcel p by the same presorting station, the start time of parcel p′ being transported by AGV j needs to be later than the time at which parcel p is transported by AGV plus the handling time of mechanical arm. Constraints (11) and (12) enforce the rule that medical waste p is transported by the AGV as soon as it arrives at the presorting station. Constraint (13) ensures that the start time of AGV transporting medical waste is later than the time medical waste arrives the presorting station. Constraints (14) link two decision variables τp,j and ρp,j. Constraint (15) states the finishing time of processing the last medical waste. Constraints (16) and (17) define the domains of decision variables.


## 4.1. Notations

The following notations are introduced to the model:Indices and sets are given as follows:P: set of medical wasteP1: a subset of medical waste, P1⊆P,2≤P1≤PI: set of presorting stationsJ: set of AGVsT: set of medical waste categoriesParameters are given as follows:e,e^: dummy points for the start point and end point of AGV routesh: the handling time for the mechanical arm at the presorting stationmp,p′: set to one when medical wastes p and p′ belong to the same category and medical waste p′ enters the induction station after medical waste p, and to zero otherwisefp: category of medical waste pci1: medical waste travel time of conveyor from induction station to presorting stationci,p2: AGV travel time from presorting station i to trailer for medical waste pgp: the time of medical waste p released to the induction stationDecision variables are as follows:μi,t: set to one if medical wastes belonging to category t are allocated to presorting station i, and to zero otherwiseνp,p′,j: set to one if medical waste p′ is transported by AGV j right after medical waste p, and to zero otherwiseρp,j: set to one if medical waste p is transported by AGV j, and to zero otherwiseφp,j: the arrival time of AGV j to the presorting station which handles medical waste pτp,j: the start time of medical waste p being transported by AGV jζj: the time of AGV j finishing all its transporting tasks


## 4.2. Mathematical Model

(1)Minimizemaxj∈Jζj,s.t.(2)∑i∈Iμi,t=1,∀t∈T,(3)∑t∈Tμi,t≤1,∀i∈I,(4)∑j∈Jρp,j=1,∀p∈P,(5)∑p∈P∪eνp,p′,j=∑p∈P∪e^νp′,p,j=ρp′,j,∀p′∈P,j∈J,(6)∑p∈P∪e^νe,p,j=∑p∈P∪eνp,e^,j=1,∀j∈J,(7)∑p∈P1∑p′∈P1νp,p′,j≤P1−1,P1⊆P,2≤P1≤P,∀j∈J,(8)φp′,j≤τp,j+h+∑i∈Ici,p2μi,fp+∑i∈Ici,p2μi,fp′+M1−νp,p′,j,∀p∈P,p′∈P,j∈J,(9)φp′,j≥τp,j+h+∑i∈Ici,p2μi,fp+∑i∈Ici,p2μi,fp′−M1−νp,p′,j,∀p∈P,p′∈P,j∈J,(10)τp′,j′≥τp,j+h−M3−mp,p′−ρp,j−ρp′,j,∀p,p′∈P,j,j′∈J,(11)τp,j≥gp+∑i∈Ici1μi,fp+Mρp,j−1,∀p∈P,j∈J,(12)τp,j≤gp+∑i∈Ici1μi,fp−Mρp,j−1,∀p∈P,j∈J,(13)φp,j≤τp,j,∀p∈P∪e,e^,j∈J,(14)τp,j≤Mρp,j,∀p∈P,j∈J,(15)ζj≥τp,j+h+∑i∈Ici,p2μi,fp+Mρp,j−1,∀p∈P,j∈J,(16)μi,t,νp,p′,j,ρp,j∈0,1,∀p,p′∈P∪e,e^,j∈J,t∈T,(17)φp,j,τp,j≥0,∀p,p′∈P∪e,e^,j∈J,where objective (1) minimizes the latest completion time for a particular batch of medical waste sorting. Constrains (2) ensure that medical waste with the same category is allocated to only one presorting station. Constraint (3) guarantees that each presorting station handles at most one category of medical waste. Constraint (4) stipulates that each medical waste is transported by only one AGV. Constraints (5) and (6) ensure the continuity of the AGV transportation routes. Constraint (7) prevents the transportation routes of AGVs from forming loops. Constraints (8) and (9) indicate that if medical waste p′ is transported by the AGV j right after medical waste p, the arrival time of the AGV to the presorting station serving medical waste p′ cannot be earlier than the travel time at which AGV j transports medical waste p and then travels to the presorting station serving medical waste p′. Constraints (10) guarantee that if parcel p′ is handled right after parcel p by the same presorting station, the start time of parcel p′ being transported by AGV j needs to be later than the time at which parcel p is transported by AGV plus the handling time of mechanical arm. Constraints (11) and (12) enforce the rule that medical waste p is transported by the AGV as soon as it arrives at the presorting station. Constraint (13) ensures that the start time of AGV transporting medical waste is later than the time medical waste arrives the presorting station. Constraints (14) link two decision variables τp,j and ρp,j. Constraint (15) states the finishing time of processing the last medical waste. Constraints (16) and (17) define the domains of decision variables.


## 5. Solution Methodology

For some small-scale problem instances, the proposed model in Section4 can be solved directly by commercial solver, such as CPLEX. However, when facing large-scale problem instances, the model becomes too intractable for CPLEX to solve. This study designs a variable neighborhood algorithm (VNS) based on dynamic programming (DP) for solving this model. Section 5.1 addresses the VNS framework. Then, Section 5.2 elaborates on the DP algorithm.


### 5.1. Variable Neighborhood Search

From constraints (11) and (12) of the proposed model, the medical waste p is transported by the AGV as soon as it arrives at the presorting station. Besides, from constraint (15), it can be seen that the completion time of the sorting task for all medical wastes mainly depends on the allocation of presorting stations and the arrival time of medical waste to the assigned presorting station. Clearly, the allocation of presorting stations relies on the decision variable μi,t. We denote the arrival time of medical waste p to the presorting station by Up; then, Up=gp+ci1. Furthermore, the assigned presorting station i relies on the decision variable μi,t, where t=fp. Therefore, we find that once the decision variable μi,t is determined, the objective function is determined.However, the routes of the AGVs interact with the allocation of presorting stations, making this problem difficult to solve. In order to determine the betterμi,t, an effective VNS algorithm based on DP is designed in this paper. The VNS algorithm is mainly used to generate distribution schemes of presorting stations. Besides, DP algorithm is mainly used to generate the feasible routes of AGVs under a certain presorting station allocation plan generated by VNS algorithm.In addition, on the basis of the VNS framework, the critical issues to solve the proposed model include the following.


#### 5.1.1. Initial Solution Generation

According to Zhen [27, 28], it can be seen that prioritizing the destinations with a larger number of parcels to the presorting station close to the induction station can effectively improve the sorting efficiency. Therefore, this article first generates the initial solution according to this rule. If the solution is not feasible, a heuristic algorithm is used to find a feasible solution. An example result is shown in Figure 3. Medical wastes belonging to categories 1, 2, 3, 4, and 5 are allocated to presorting stations 2, 1, 5, 3, and 4, which means μ1,2,μ2,1,μ3,5,μ4,3,μ5,4=1.Figure 3
Initial solution generation.


#### 5.1.2. The Design of Neighborhood Structures

Considering the characteristics ofμi,t, the following two neighborhood structures are designed in this paper.(1) Neighborhood structure 1: interval reversal: the process of interval reversal is shown in Figure4. First, a subinterval of the medical waste categories sequence is randomly selected, and then we invert the corresponding relationship between the medical waste category and the presorting station in the interval.Figure 4
Neighborhood structure: interval reversal.(2) Neighborhood structure 2: exchange: we will randomly select two medical waste categories and exchange their corresponding presorting stations, as shown in Figure5.Figure 5
Neighborhood structure: exchange.


#### 5.1.3. The Framework of Variable Neighborhood Descent

Variable neighborhood descent is the framework of the neighborhood search, which is used to search different neighborhood structures. The algorithm will completely explore one neighborhood structure and then move to the next neighborhood when no solution better than the optimal solution can be found (Algorithm1).Algorithm 1:Variable neighborhood descent (VND).
Input:s,s′,l←1//s′ is the optimal solution and s is the current solution, and l is used to record the neighborhood structure(1)
s⟵s′(2)
While(true)(3)
Switch(l)(4)
case 1:(5)
FindBestNeighborhood_one(s)(6)
If (fs′<fs)then//fs is the fitness of solution s, calculated by DP.(7)
s⟵s′;(8)
l=0;(9)
End if(10)
Break;(11)
case 2:(12)
FindBestNeighborhood_two(s)(13)
If (fs′<fs)then(14)
s⟵s′;(15)
l=0;(16)
End if(17)
break;(18)
default;(19)
return;(20)
l++;(21)
End while


#### 5.1.4. Shaking Procedure

To avoid falling into local optimization, we design a shaking procedure. The medical waste categories sequence is randomly divided into two parts, and the corresponding presorting station is shuffled by part, as shown in Figure6.Figure 6
Shaking procedure.In summary, based on the description about initial solution, neighborhood structure, and shaking procedure, the table provides the pseudocode of VNS (Algorithm2).Algorithm 2:Variable neighborhood search (VNS).
Input:G,g,s,s′,g=0,G=10 //g represents the current iteration number, G represents the maximum iteration number, s′ is the optimal solution, and s is current solution(1)
s0 //generate the initial solution;(2)
s′⟵s0;(3)
While (iteration < G)(4)
s⟵s′;(5)
Shaking(s);(6)
Variable neighborhood descent(s);(7)
If (fs<fs′)Then(8)
s′⟵s;(9)
g=0;(10)
End if(11)
g++;(12)
End whileOutput: best found solution.


### 5.2. Dynamic Algorithm

The dynamic programming method is a mathematical method for solving the optimization of decision-making processes. Besides, DP algorithm is mainly used to generate the feasible routes of AGVs (Algorithm3).The core idea is to divide a complex system problem into several stages and transform the multistage process into a series of single-stage problems. These single-stage problems are solved one by one by selecting appropriate decision variables and constructing indicator functions and optimal value functions. When using the idea of dynamic programming to solve the actual problem, it is necessary to abstract the corresponding terms of dynamic programming according to the actual situation of the problem, so as to facilitate the analysis and calculation.


#### 5.2.1. Stage

In this problem, the route of the AGV transporting medical waste is divided into different stages, denoted byk. The kth stage represents the kth medical waste transported by the AGV.


#### 5.2.2. State

The state represents the condition at the beginning of each phase. The state variablessk is used to describe the state at stage k, which means that the kth medical waste transported by AGV is sk.


#### 5.2.3. Decision

When the state of a stage is determined, the decision to make a choice to move to the next stage is called a decision. Commonlyuksk indicates the decision set in state sk at stage k. uksk denotes the set of medical waste that can be transported by the vehicle at stage k+1.


#### 5.2.4. State Transition Equation

If the state and decision of a stage are given, the state of the next stage can be determined, and the state transition equation can be set as(18)sk+1=uksk=ukminTk.


#### 5.2.5. Indicator Function

The indicator function is used to measure each state’s degree of excellence in order to achieve better decision-making. In the proposed problem,tk−1,k represents the sum of the time it takes the AGV to transport the medical waste k−1 to a designated trailer and the time it takes to travel to the medical waste k from the trailer. In this paper, the indicator function is set to (19)fk=0,k=0,minfk−1+h+tk−1,k,k>0.Algorithm 3:Dynamic programming (DP).
Input:P,J//P: set of medical waste. J: set of AGVS.Interpretations:Lp: set to 1 if medical waste p has been transported, and to zero otherwise. j.route.count indicates the number of medical wastes transported by AGV j. j⋅fk denotes the time for AGV j to transport the kth medical waste(1)
Forj∈J(2)
Select a medical wastep with an Lp=0;(3)
j.route.Addp;//add medical waste p to the route of AGV j(4)
j⋅f0=Up;(5)
Lp=1;(6)
End For(7)
Forj∈J(8)
Forp∈P(9)
k=j.route.count;(10)
j⋅fk=j⋅fk−1+h+tk−1,k;(11)
If (Lp=0&&j⋅fk<Up)(12)
j.route.Addp;(13)
Lp=1;(14)
End for(15)
End for(16)
Forp∈P(17)
If (Lp=1)(18)
Returnobj=MaxValue;(19)
End forOutput:obj=maxj∈Jj.fj.route.count−1


## 5.1. Variable Neighborhood Search

From constraints (11) and (12) of the proposed model, the medical waste p is transported by the AGV as soon as it arrives at the presorting station. Besides, from constraint (15), it can be seen that the completion time of the sorting task for all medical wastes mainly depends on the allocation of presorting stations and the arrival time of medical waste to the assigned presorting station. Clearly, the allocation of presorting stations relies on the decision variable μi,t. We denote the arrival time of medical waste p to the presorting station by Up; then, Up=gp+ci1. Furthermore, the assigned presorting station i relies on the decision variable μi,t, where t=fp. Therefore, we find that once the decision variable μi,t is determined, the objective function is determined.However, the routes of the AGVs interact with the allocation of presorting stations, making this problem difficult to solve. In order to determine the betterμi,t, an effective VNS algorithm based on DP is designed in this paper. The VNS algorithm is mainly used to generate distribution schemes of presorting stations. Besides, DP algorithm is mainly used to generate the feasible routes of AGVs under a certain presorting station allocation plan generated by VNS algorithm.In addition, on the basis of the VNS framework, the critical issues to solve the proposed model include the following.


### 5.1.1. Initial Solution Generation

According to Zhen [27, 28], it can be seen that prioritizing the destinations with a larger number of parcels to the presorting station close to the induction station can effectively improve the sorting efficiency. Therefore, this article first generates the initial solution according to this rule. If the solution is not feasible, a heuristic algorithm is used to find a feasible solution. An example result is shown in Figure 3. Medical wastes belonging to categories 1, 2, 3, 4, and 5 are allocated to presorting stations 2, 1, 5, 3, and 4, which means μ1,2,μ2,1,μ3,5,μ4,3,μ5,4=1.Figure 3
Initial solution generation.


### 5.1.2. The Design of Neighborhood Structures

Considering the characteristics ofμi,t, the following two neighborhood structures are designed in this paper.(1) Neighborhood structure 1: interval reversal: the process of interval reversal is shown in Figure4. First, a subinterval of the medical waste categories sequence is randomly selected, and then we invert the corresponding relationship between the medical waste category and the presorting station in the interval.Figure 4
Neighborhood structure: interval reversal.(2) Neighborhood structure 2: exchange: we will randomly select two medical waste categories and exchange their corresponding presorting stations, as shown in Figure5.Figure 5
Neighborhood structure: exchange.


### 5.1.3. The Framework of Variable Neighborhood Descent

Variable neighborhood descent is the framework of the neighborhood search, which is used to search different neighborhood structures. The algorithm will completely explore one neighborhood structure and then move to the next neighborhood when no solution better than the optimal solution can be found (Algorithm1).Algorithm 1:Variable neighborhood descent (VND).
Input:s,s′,l←1//s′ is the optimal solution and s is the current solution, and l is used to record the neighborhood structure(1)
s⟵s′(2)
While(true)(3)
Switch(l)(4)
case 1:(5)
FindBestNeighborhood_one(s)(6)
If (fs′<fs)then//fs is the fitness of solution s, calculated by DP.(7)
s⟵s′;(8)
l=0;(9)
End if(10)
Break;(11)
case 2:(12)
FindBestNeighborhood_two(s)(13)
If (fs′<fs)then(14)
s⟵s′;(15)
l=0;(16)
End if(17)
break;(18)
default;(19)
return;(20)
l++;(21)
End while


### 5.1.4. Shaking Procedure

To avoid falling into local optimization, we design a shaking procedure. The medical waste categories sequence is randomly divided into two parts, and the corresponding presorting station is shuffled by part, as shown in Figure6.Figure 6
Shaking procedure.In summary, based on the description about initial solution, neighborhood structure, and shaking procedure, the table provides the pseudocode of VNS (Algorithm2).Algorithm 2:Variable neighborhood search (VNS).
Input:G,g,s,s′,g=0,G=10 //g represents the current iteration number, G represents the maximum iteration number, s′ is the optimal solution, and s is current solution(1)
s0 //generate the initial solution;(2)
s′⟵s0;(3)
While (iteration < G)(4)
s⟵s′;(5)
Shaking(s);(6)
Variable neighborhood descent(s);(7)
If (fs<fs′)Then(8)
s′⟵s;(9)
g=0;(10)
End if(11)
g++;(12)
End whileOutput: best found solution.


## 5.1.1. Initial Solution Generation

According to Zhen [27, 28], it can be seen that prioritizing the destinations with a larger number of parcels to the presorting station close to the induction station can effectively improve the sorting efficiency. Therefore, this article first generates the initial solution according to this rule. If the solution is not feasible, a heuristic algorithm is used to find a feasible solution. An example result is shown in Figure 3. Medical wastes belonging to categories 1, 2, 3, 4, and 5 are allocated to presorting stations 2, 1, 5, 3, and 4, which means μ1,2,μ2,1,μ3,5,μ4,3,μ5,4=1.Figure 3
Initial solution generation.


## 5.1.2. The Design of Neighborhood Structures

Considering the characteristics ofμi,t, the following two neighborhood structures are designed in this paper.(1) Neighborhood structure 1: interval reversal: the process of interval reversal is shown in Figure4. First, a subinterval of the medical waste categories sequence is randomly selected, and then we invert the corresponding relationship between the medical waste category and the presorting station in the interval.Figure 4
Neighborhood structure: interval reversal.(2) Neighborhood structure 2: exchange: we will randomly select two medical waste categories and exchange their corresponding presorting stations, as shown in Figure5.Figure 5
Neighborhood structure: exchange.


## 5.1.3. The Framework of Variable Neighborhood Descent

Variable neighborhood descent is the framework of the neighborhood search, which is used to search different neighborhood structures. The algorithm will completely explore one neighborhood structure and then move to the next neighborhood when no solution better than the optimal solution can be found (Algorithm1).Algorithm 1:Variable neighborhood descent (VND).
Input:s,s′,l←1//s′ is the optimal solution and s is the current solution, and l is used to record the neighborhood structure(1)
s⟵s′(2)
While(true)(3)
Switch(l)(4)
case 1:(5)
FindBestNeighborhood_one(s)(6)
If (fs′<fs)then//fs is the fitness of solution s, calculated by DP.(7)
s⟵s′;(8)
l=0;(9)
End if(10)
Break;(11)
case 2:(12)
FindBestNeighborhood_two(s)(13)
If (fs′<fs)then(14)
s⟵s′;(15)
l=0;(16)
End if(17)
break;(18)
default;(19)
return;(20)
l++;(21)
End while


## 5.1.4. Shaking Procedure

To avoid falling into local optimization, we design a shaking procedure. The medical waste categories sequence is randomly divided into two parts, and the corresponding presorting station is shuffled by part, as shown in Figure6.Figure 6
Shaking procedure.In summary, based on the description about initial solution, neighborhood structure, and shaking procedure, the table provides the pseudocode of VNS (Algorithm2).Algorithm 2:Variable neighborhood search (VNS).
Input:G,g,s,s′,g=0,G=10 //g represents the current iteration number, G represents the maximum iteration number, s′ is the optimal solution, and s is current solution(1)
s0 //generate the initial solution;(2)
s′⟵s0;(3)
While (iteration < G)(4)
s⟵s′;(5)
Shaking(s);(6)
Variable neighborhood descent(s);(7)
If (fs<fs′)Then(8)
s′⟵s;(9)
g=0;(10)
End if(11)
g++;(12)
End whileOutput: best found solution.


## 5.2. Dynamic Algorithm

The dynamic programming method is a mathematical method for solving the optimization of decision-making processes. Besides, DP algorithm is mainly used to generate the feasible routes of AGVs (Algorithm3).The core idea is to divide a complex system problem into several stages and transform the multistage process into a series of single-stage problems. These single-stage problems are solved one by one by selecting appropriate decision variables and constructing indicator functions and optimal value functions. When using the idea of dynamic programming to solve the actual problem, it is necessary to abstract the corresponding terms of dynamic programming according to the actual situation of the problem, so as to facilitate the analysis and calculation.


### 5.2.1. Stage

In this problem, the route of the AGV transporting medical waste is divided into different stages, denoted byk. The kth stage represents the kth medical waste transported by the AGV.


### 5.2.2. State

The state represents the condition at the beginning of each phase. The state variablessk is used to describe the state at stage k, which means that the kth medical waste transported by AGV is sk.


### 5.2.3. Decision

When the state of a stage is determined, the decision to make a choice to move to the next stage is called a decision. Commonlyuksk indicates the decision set in state sk at stage k. uksk denotes the set of medical waste that can be transported by the vehicle at stage k+1.


### 5.2.4. State Transition Equation

If the state and decision of a stage are given, the state of the next stage can be determined, and the state transition equation can be set as(18)sk+1=uksk=ukminTk.


### 5.2.5. Indicator Function

The indicator function is used to measure each state’s degree of excellence in order to achieve better decision-making. In the proposed problem,tk−1,k represents the sum of the time it takes the AGV to transport the medical waste k−1 to a designated trailer and the time it takes to travel to the medical waste k from the trailer. In this paper, the indicator function is set to (19)fk=0,k=0,minfk−1+h+tk−1,k,k>0.Algorithm 3:Dynamic programming (DP).
Input:P,J//P: set of medical waste. J: set of AGVS.Interpretations:Lp: set to 1 if medical waste p has been transported, and to zero otherwise. j.route.count indicates the number of medical wastes transported by AGV j. j⋅fk denotes the time for AGV j to transport the kth medical waste(1)
Forj∈J(2)
Select a medical wastep with an Lp=0;(3)
j.route.Addp;//add medical waste p to the route of AGV j(4)
j⋅f0=Up;(5)
Lp=1;(6)
End For(7)
Forj∈J(8)
Forp∈P(9)
k=j.route.count;(10)
j⋅fk=j⋅fk−1+h+tk−1,k;(11)
If (Lp=0&&j⋅fk<Up)(12)
j.route.Addp;(13)
Lp=1;(14)
End for(15)
End for(16)
Forp∈P(17)
If (Lp=1)(18)
Returnobj=MaxValue;(19)
End forOutput:obj=maxj∈Jj.fj.route.count−1


## 5.2.1. Stage

In this problem, the route of the AGV transporting medical waste is divided into different stages, denoted byk. The kth stage represents the kth medical waste transported by the AGV.


## 5.2.2. State

The state represents the condition at the beginning of each phase. The state variablessk is used to describe the state at stage k, which means that the kth medical waste transported by AGV is sk.


## 5.2.3. Decision

When the state of a stage is determined, the decision to make a choice to move to the next stage is called a decision. Commonlyuksk indicates the decision set in state sk at stage k. uksk denotes the set of medical waste that can be transported by the vehicle at stage k+1.


## 5.2.4. State Transition Equation

If the state and decision of a stage are given, the state of the next stage can be determined, and the state transition equation can be set as(18)sk+1=uksk=ukminTk.


## 5.2.5. Indicator Function

The indicator function is used to measure each state’s degree of excellence in order to achieve better decision-making. In the proposed problem,tk−1,k represents the sum of the time it takes the AGV to transport the medical waste k−1 to a designated trailer and the time it takes to travel to the medical waste k from the trailer. In this paper, the indicator function is set to (19)fk=0,k=0,minfk−1+h+tk−1,k,k>0.Algorithm 3:Dynamic programming (DP).
Input:P,J//P: set of medical waste. J: set of AGVS.Interpretations:Lp: set to 1 if medical waste p has been transported, and to zero otherwise. j.route.count indicates the number of medical wastes transported by AGV j. j⋅fk denotes the time for AGV j to transport the kth medical waste(1)
Forj∈J(2)
Select a medical wastep with an Lp=0;(3)
j.route.Addp;//add medical waste p to the route of AGV j(4)
j⋅f0=Up;(5)
Lp=1;(6)
End For(7)
Forj∈J(8)
Forp∈P(9)
k=j.route.count;(10)
j⋅fk=j⋅fk−1+h+tk−1,k;(11)
If (Lp=0&&j⋅fk<Up)(12)
j.route.Addp;(13)
Lp=1;(14)
End for(15)
End for(16)
Forp∈P(17)
If (Lp=1)(18)
Returnobj=MaxValue;(19)
End forOutput:obj=maxj∈Jj.fj.route.count−1


## 6. Numerical Experiment

To validate the effectiveness of the proposed model and efficiency of the proposed algorithm, we conduct extensive numerical experiments on different instances. All experiments are performed on a workstation equipped with Intel i5-10210U CPU @1.60 GHz and 16 GB RAM. The proposed model and algorithm are implemented in C# (VS2019) concert technology with the solver IBM ILOG CPLEX 12.6.1.


### 6.1. Generation of Test Instances

Numerical examples of small, medium and large scale are designed to validate the performance of proposed algorithms, and each scale contains several groups of examples which can avoid accidental results.Since medical waste is mainly classified into five categories in Chinese hospitals, the number of medical waste categories and the number of presorting stations are both set to 5; i.e.,E=I=5. The category of medical waste fp is generated randomly. The release time of medical waste is related to the operation of induction station, and we use the formula gp=p to generate the release time. The handling time h for the mechanical arm is set to 1 second. According to the layout of the MWRPC, we can use the Manhattan distance to calculate the distance between the trailer and the presorting station, and the distance between induction station and the presorting station. Then we use the speed of conveyor and AGV to calculate the values of ci1 and ci,p2, respectively.


### 6.2. Algorithm Performance

Extensive experiments are conducted to test the performance of the proposed VNS algorithm based on DP. The results are shown in Tables1 and 2, with the objective function obtained by different methods, the calculation time, and the gap listed. The maximum calculation time is set to 7200 seconds. In our experiment, a heuristic algorithm is proposed for comparison. Besides, in order to artificially improve the solution quality of the heuristic algorithm, this paper will use the heuristic algorithm to solve the same instance five times and record the optimal solution in Tables 1 and 2. The procedure of the heuristic is listed as follows:Step 1: the corresponding relationship between medical waste categories and presorting stations is given randomly; i.e., the decision variableμi,t is assumed to be known.Step 2: each AGV is dedicated to a specific category of medical waste. Due to the limitation of a category of medical waste to be processed by only one presorting station, an AGV can only service a designated presorting station.Step 3: the greedy algorithm is designed to generate the route of AGVs transporting medical waste. The pseudocode of greedy algorithm is shown in Algorithm4.Table 1
Algorithm performance for small-scale instances.
InstancesCPLEXVNSComparisonHeuristicComparisonScaleIDZCTCZVTVGAPV (%)JHZHTHJGAPH (%)ZGAPH (%)J=8P=10140.021.4540.00.0030.001037.00.00925.00−7.50239.06.6139.00.0030.001047.00.01525.0020.51341.07.4341.00.0030.001042.00.00525.002.44441.010.8941.00.0020.001041.00.01325.000.00540.010.9240.00.0030.001040.00.02325.000.00Avg.40.211.4640.20.0030.001041.40.01325.003.09J=12P=15146.031.6246.00.0020.001552.00.01125.0013.04247.039.9847.00.0040.001547.00.00625.000.00341.039.6441.00.0020.001341.00.0108.330.00444.031.4344.00.0020.001244.00.0130.000.00542.031.4342.00.0050.001340.00.0078.33−4.76Avg.44.034.8244.00.0030.0013.644.80.00913.331.66J=14P=20147.0132.3247.00.0030.001647.00.02614.290.00246.041.2646.00.0060.001546.00.0077.140.00351.0416.4351.00.0050.002051.00.01242.860.00450.0799.3750.00.0040.001648.00.00314.29−4.00552.099.7552.00.0060.001552.00.0087.140.00Avg.49.2297.82649.20.0050.0016.448.80.01117.14−0.80J=16P=30161.0>720061.00.0030.001859.00.00612.50−3.28257.0>720057.00.0030.003058.00.00787.501.75354.0>720054.00.0060.001654.00.0100.000.00458.0>720058.00.0060.002662.00.01062.506.90562.0>720062.00.0060.002162.00.00731.250.00Avg.58.4>720058.40.0050.0022.259.00.00838.751.07Notes. (1)ZC denotes the optimal solution obtained by CPLEX. For the instance scale J=16,P=30, ZC denotes the feasible solution obtained by CPLEX in 7200 seconds. ZV,ZH denote the feasible solution obtained by VNS algorithm and heuristic algorithm, respectively. (2) JH represents the number of AGVs required when the heuristic algorithm obtains a feasible solution. TC,TV,TH are the computation time of CPLEX, VNS algorithm, and heuristic algorithm in seconds, respectively. (3) GAPV=ZVNS−ZCPLEX/ZCPLEX, JGAPH=JH−J/J, ZGAPH=ZH−ZV/ZV.Table 2
Algorithm performance for large-scale instances.
InstancesVNSHeuristicComparisonScaleIDZVTVJHZHTHJGAPH (%)ZGAPH (%)J=20P=50174.00.0062174.00.0085.000.00286.00.0083686.00.00780.000.00381.00.0053781.00.00385.000.00478.00.0063678.00.00380.000.00573.00.0082173.00.0065.000.00Avg.78.40.0073078.40.00551.000.00J=20P=1001125.00.01424125.00.00520.000.002127.00.01523126.00.00315.00−0.793126.00.01024126.00.00720.000.004132.00.01227131.00.00735.00−0.765130.00.02427128.00.00435.00−1.54Avg.128.00.01525127.20.00525.00−0.62J=21P=2001228.00.02626228.00.00323.810.002224.00.02527224.00.00328.570.003232.00.02629232.00.00838.100.004227.00.02626227.00.01123.810.005226.00.03027226.00.00328.570.00Avg.227.40.02727227.40.00628.570.00J=22P=5001527.00.09829527.00.01131.820.002529.00.09629529.00.00331.820.003525.00.09429525.00.00431.820.004531.00.09231531.00.00340.910.005530.00.09732529.00.00345.45−0.19Avg.528.40.09530528.20.00536.36−0.04Algorithm 4:Heuristic algorithm.
Input:P,I // P: set of medical waste.I: set of presorting stations;Lp: set to 1 if medical waste p has been transported, and to zero otherwise.Up: time to enter the presorting table for medical waste p. i.agv.count: indicates the number of AGVs serving presorting station i, set the initial value to 1.j⋅tp: denotes the finish time of AGV j transporting medical waste p, set j=0 initially.(1)
Fori∈I(2)
Forj∈i.agv.count(3)
Select a medical waste with minimizeUp in p∈P|Lp=0;(4)
If (Lp=0&&j⋅tp<Up)(5)
Updatej⋅tp;(6)
Lp=1;(7)
End if(8)
If (Lp=0)(9)
j=i.agv.count; Update j⋅tp;(10)
i.agv.count++;(11)
End If(12)
End For(13)
End ForOutput:∑i∈Ii.agv.count and maxj∈Jj⋅tpFor experiments of small-scale and medium-scale instances, we compare the result obtained by VNS algorithm and the heuristic. From Table1, we can see that VNS algorithm can obtain near-optimal results. The average gap between the objective values of the VNS algorithm and CPLEX is close to 0. What is more, CPLEX can only solve some small-scale problems within reasonable time period. When the number of medical wastes grows to 16 and the number of AGVs grows to 14, CPLEX is incapable of calculating the result under 7200 seconds. The computation time of VNS algorithm is much shorter than CPLEX when the scale of instances increases, where the average computing time for VNS is 0.009 seconds. It can be seen that the gap between the feasible solution obtained by heuristic algorithm and the optimal solution is about 1.26% on average. However, the number of AGVs required by the heuristic algorithm is 23.56% more than that of CPLEX on average.For experiments of large-scale instances, we compare the result obtained by VNS algorithm and the heuristic in Table2. It is obvious that the average computing time of the heuristic algorithm and the VNS algorithm is steadily less than 1 second. The objective function gap between heuristic algorithm and VNS algorithm is −0.16% on average; i.e., ZGAPH=−0.16%. However, the objective function of the heuristic is 1% lower than the objective function of the VNS algorithm; i.e., ZGAPH=−0.16%. However, the number of AGVs required by the heuristic is greater than that of the VNS algorithm by 23%; i.e., JGAPH=35.23%. That is to say, VNS algorithm results in much greater performance in solving large-scale problem than heuristic.


### 6.3. Sensitivity Analysis

The speed of the conveyor has a significant impact on the finishing time of medical waste sorting. Therefore, we calculate the minimum number of AGVs required to complete the sorting of 100 medical wastes in a timely manner at different conveyor speeds. In addition, the finishing time for medical waste sorting at different conveyor speeds is also calculated. Different sets of instances under the same scale are calculated, and the average value is taken to avoid unexpected results.From Figure7, we can see that there is an approximate positive correlation between conveying speed and finishing time, and an approximate negative correlation between conveyor speed and number of AGVs. Figure 7 illustrates the change rate of AGVs number and finishing time as the conveyor speed increases.Figure 7
Sensitivity analysis about AGVs number and finishing time.However, in the process of increasing the conveyor speed, the change rate of AGVs number is different. It can be seen that a conveyor speed of 1 m/s is a critical point. It is noticeable that the decrease rate in the number of AGVs when the conveyor speed increases from 0.4 m/s to 0.9 m/s is generally higher than the decrease rate when the conveyor speed increases from 1.1 m/s to 1.4 m/s. Similarly, there are differences in the change rate of the completion time. When the conveyor speed increases from 0.4 m/s to 0.9 m/s, the change rate is steadily decreasing while the change rate fluctuates and decreases when the conveyor speed increases from 1.1 m/s to 1.4 m/s.In this proposed problem, the completion time of medical waste sorting is regarded as the only objective function. However, in reality, managers often need to trade off the fixed cost of AGVs and the completion time of medical waste sorting. Therefore, Figure8 gives some recommendations to managers on how to set the conveyor speed when the number of AGVs is limited.Figure 8
Sensitivity analysis about speed of the conveyors and number of AGVs.


## 6.1. Generation of Test Instances

Numerical examples of small, medium and large scale are designed to validate the performance of proposed algorithms, and each scale contains several groups of examples which can avoid accidental results.Since medical waste is mainly classified into five categories in Chinese hospitals, the number of medical waste categories and the number of presorting stations are both set to 5; i.e.,E=I=5. The category of medical waste fp is generated randomly. The release time of medical waste is related to the operation of induction station, and we use the formula gp=p to generate the release time. The handling time h for the mechanical arm is set to 1 second. According to the layout of the MWRPC, we can use the Manhattan distance to calculate the distance between the trailer and the presorting station, and the distance between induction station and the presorting station. Then we use the speed of conveyor and AGV to calculate the values of ci1 and ci,p2, respectively.


## 6.2. Algorithm Performance

Extensive experiments are conducted to test the performance of the proposed VNS algorithm based on DP. The results are shown in Tables1 and 2, with the objective function obtained by different methods, the calculation time, and the gap listed. The maximum calculation time is set to 7200 seconds. In our experiment, a heuristic algorithm is proposed for comparison. Besides, in order to artificially improve the solution quality of the heuristic algorithm, this paper will use the heuristic algorithm to solve the same instance five times and record the optimal solution in Tables 1 and 2. The procedure of the heuristic is listed as follows:Step 1: the corresponding relationship between medical waste categories and presorting stations is given randomly; i.e., the decision variableμi,t is assumed to be known.Step 2: each AGV is dedicated to a specific category of medical waste. Due to the limitation of a category of medical waste to be processed by only one presorting station, an AGV can only service a designated presorting station.Step 3: the greedy algorithm is designed to generate the route of AGVs transporting medical waste. The pseudocode of greedy algorithm is shown in Algorithm4.Table 1
Algorithm performance for small-scale instances.
InstancesCPLEXVNSComparisonHeuristicComparisonScaleIDZCTCZVTVGAPV (%)JHZHTHJGAPH (%)ZGAPH (%)J=8P=10140.021.4540.00.0030.001037.00.00925.00−7.50239.06.6139.00.0030.001047.00.01525.0020.51341.07.4341.00.0030.001042.00.00525.002.44441.010.8941.00.0020.001041.00.01325.000.00540.010.9240.00.0030.001040.00.02325.000.00Avg.40.211.4640.20.0030.001041.40.01325.003.09J=12P=15146.031.6246.00.0020.001552.00.01125.0013.04247.039.9847.00.0040.001547.00.00625.000.00341.039.6441.00.0020.001341.00.0108.330.00444.031.4344.00.0020.001244.00.0130.000.00542.031.4342.00.0050.001340.00.0078.33−4.76Avg.44.034.8244.00.0030.0013.644.80.00913.331.66J=14P=20147.0132.3247.00.0030.001647.00.02614.290.00246.041.2646.00.0060.001546.00.0077.140.00351.0416.4351.00.0050.002051.00.01242.860.00450.0799.3750.00.0040.001648.00.00314.29−4.00552.099.7552.00.0060.001552.00.0087.140.00Avg.49.2297.82649.20.0050.0016.448.80.01117.14−0.80J=16P=30161.0>720061.00.0030.001859.00.00612.50−3.28257.0>720057.00.0030.003058.00.00787.501.75354.0>720054.00.0060.001654.00.0100.000.00458.0>720058.00.0060.002662.00.01062.506.90562.0>720062.00.0060.002162.00.00731.250.00Avg.58.4>720058.40.0050.0022.259.00.00838.751.07Notes. (1)ZC denotes the optimal solution obtained by CPLEX. For the instance scale J=16,P=30, ZC denotes the feasible solution obtained by CPLEX in 7200 seconds. ZV,ZH denote the feasible solution obtained by VNS algorithm and heuristic algorithm, respectively. (2) JH represents the number of AGVs required when the heuristic algorithm obtains a feasible solution. TC,TV,TH are the computation time of CPLEX, VNS algorithm, and heuristic algorithm in seconds, respectively. (3) GAPV=ZVNS−ZCPLEX/ZCPLEX, JGAPH=JH−J/J, ZGAPH=ZH−ZV/ZV.Table 2
Algorithm performance for large-scale instances.
InstancesVNSHeuristicComparisonScaleIDZVTVJHZHTHJGAPH (%)ZGAPH (%)J=20P=50174.00.0062174.00.0085.000.00286.00.0083686.00.00780.000.00381.00.0053781.00.00385.000.00478.00.0063678.00.00380.000.00573.00.0082173.00.0065.000.00Avg.78.40.0073078.40.00551.000.00J=20P=1001125.00.01424125.00.00520.000.002127.00.01523126.00.00315.00−0.793126.00.01024126.00.00720.000.004132.00.01227131.00.00735.00−0.765130.00.02427128.00.00435.00−1.54Avg.128.00.01525127.20.00525.00−0.62J=21P=2001228.00.02626228.00.00323.810.002224.00.02527224.00.00328.570.003232.00.02629232.00.00838.100.004227.00.02626227.00.01123.810.005226.00.03027226.00.00328.570.00Avg.227.40.02727227.40.00628.570.00J=22P=5001527.00.09829527.00.01131.820.002529.00.09629529.00.00331.820.003525.00.09429525.00.00431.820.004531.00.09231531.00.00340.910.005530.00.09732529.00.00345.45−0.19Avg.528.40.09530528.20.00536.36−0.04Algorithm 4:Heuristic algorithm.
Input:P,I // P: set of medical waste.I: set of presorting stations;Lp: set to 1 if medical waste p has been transported, and to zero otherwise.Up: time to enter the presorting table for medical waste p. i.agv.count: indicates the number of AGVs serving presorting station i, set the initial value to 1.j⋅tp: denotes the finish time of AGV j transporting medical waste p, set j=0 initially.(1)
Fori∈I(2)
Forj∈i.agv.count(3)
Select a medical waste with minimizeUp in p∈P|Lp=0;(4)
If (Lp=0&&j⋅tp<Up)(5)
Updatej⋅tp;(6)
Lp=1;(7)
End if(8)
If (Lp=0)(9)
j=i.agv.count; Update j⋅tp;(10)
i.agv.count++;(11)
End If(12)
End For(13)
End ForOutput:∑i∈Ii.agv.count and maxj∈Jj⋅tpFor experiments of small-scale and medium-scale instances, we compare the result obtained by VNS algorithm and the heuristic. From Table1, we can see that VNS algorithm can obtain near-optimal results. The average gap between the objective values of the VNS algorithm and CPLEX is close to 0. What is more, CPLEX can only solve some small-scale problems within reasonable time period. When the number of medical wastes grows to 16 and the number of AGVs grows to 14, CPLEX is incapable of calculating the result under 7200 seconds. The computation time of VNS algorithm is much shorter than CPLEX when the scale of instances increases, where the average computing time for VNS is 0.009 seconds. It can be seen that the gap between the feasible solution obtained by heuristic algorithm and the optimal solution is about 1.26% on average. However, the number of AGVs required by the heuristic algorithm is 23.56% more than that of CPLEX on average.For experiments of large-scale instances, we compare the result obtained by VNS algorithm and the heuristic in Table2. It is obvious that the average computing time of the heuristic algorithm and the VNS algorithm is steadily less than 1 second. The objective function gap between heuristic algorithm and VNS algorithm is −0.16% on average; i.e., ZGAPH=−0.16%. However, the objective function of the heuristic is 1% lower than the objective function of the VNS algorithm; i.e., ZGAPH=−0.16%. However, the number of AGVs required by the heuristic is greater than that of the VNS algorithm by 23%; i.e., JGAPH=35.23%. That is to say, VNS algorithm results in much greater performance in solving large-scale problem than heuristic.


## 6.3. Sensitivity Analysis

The speed of the conveyor has a significant impact on the finishing time of medical waste sorting. Therefore, we calculate the minimum number of AGVs required to complete the sorting of 100 medical wastes in a timely manner at different conveyor speeds. In addition, the finishing time for medical waste sorting at different conveyor speeds is also calculated. Different sets of instances under the same scale are calculated, and the average value is taken to avoid unexpected results.From Figure7, we can see that there is an approximate positive correlation between conveying speed and finishing time, and an approximate negative correlation between conveyor speed and number of AGVs. Figure 7 illustrates the change rate of AGVs number and finishing time as the conveyor speed increases.Figure 7
Sensitivity analysis about AGVs number and finishing time.However, in the process of increasing the conveyor speed, the change rate of AGVs number is different. It can be seen that a conveyor speed of 1 m/s is a critical point. It is noticeable that the decrease rate in the number of AGVs when the conveyor speed increases from 0.4 m/s to 0.9 m/s is generally higher than the decrease rate when the conveyor speed increases from 1.1 m/s to 1.4 m/s. Similarly, there are differences in the change rate of the completion time. When the conveyor speed increases from 0.4 m/s to 0.9 m/s, the change rate is steadily decreasing while the change rate fluctuates and decreases when the conveyor speed increases from 1.1 m/s to 1.4 m/s.In this proposed problem, the completion time of medical waste sorting is regarded as the only objective function. However, in reality, managers often need to trade off the fixed cost of AGVs and the completion time of medical waste sorting. Therefore, Figure8 gives some recommendations to managers on how to set the conveyor speed when the number of AGVs is limited.Figure 8
Sensitivity analysis about speed of the conveyors and number of AGVs.


## 7. Conclusion

Existing MWRPC have difficulty in processing large volumes of medical waste efficiently. Considering the similarity between medical waste and parcels, we propose that the vertical sorting system can be applied in medical waste processing and sorting center. A mixed-integer linear programming model is established which aims to optimize the assignments of presorting stations and AGVs to improve the efficiency of medical waste sorting. Besides, we designed a VNS algorithm based on DP for problem solving. Compared with related works, the main contributions of this work are summarized as follows:(1)
This paper expands the medical waste sorting way in the medical waste processing and sorting center. The application of the automated sorting system can greatly reduce manual operations, thereby reducing the infection rate of medical waste. In addition, a reasonable and effective classification of medical waste can improve the recycling rate of resources.(2)
VNS algorithm is applied in problem solving, which is competent in solving both small- and large-scale problems. VNS algorithm improves computational efficiency, so the research finding provides a decision support tool for medical waste processing and sorting center.(3)
Different conveyor speeds will result in different operating efficiencies. The faster the conveyor speed, the greater the AGVs number required, and the shorter the finishing time of the medical waste sorting. Managers can adjust the conveyor speed to complete the medical waste sorting according to the number of AGVs and the urgency of medical waste disposal.This research also has its limitations. In our research, we only consider a relatively simple medical waste classification method, but there may be a variety of different classification requirements in reality, such as classification according to different treatment methods and classification according to the material. In addition, the objective of the model (i.e., to minimize the finishing time of the last medical waste) only considers the processing time but does not take account of the fixed cost of AGV. The start-up cost and maintenance cost of AGV and the finishing time of medical waste need to be considered simultaneously to achieve a balance of cost and utility. All of these issues can be our research directions in the future.



---

*Source: 4313749-2021-06-15.xml*