Optimizing Hospital Operations: Scheduling Autonomous Mobile Robots for Cost Efficiency

By Dr. Sampath LonkaReviewed by Susha Cheriyedath, M.Sc.Oct 10 2023

In a recent publication in the journal PLOS ONE, researchers examined the scheduling of autonomous mobile robots (AMRs) in hospital settings with variable travel and service times. The objective is to minimize daily hospital costs, considering AMR fixed costs, time window violations, and transportation expenses.

Background

In recent years, the aging population has created a noticeable trend, placing additional demands on healthcare workers. AMRs offer a solution by assisting with tasks such as medication and document delivery, reducing staff workload and infection risks, and enhancing efficiency. Effective scheduling is pivotal in optimizing resource utilization, particularly in the face of uncertainties in AMR travel speeds and service times.

The scheduling of mobile robots has been a prominent research focus, mainly within deterministic environments. Notable studies include work on the vehicle routing problem with fixed running speed, task allocation, and deterministic AMR scheduling using different search algorithms. Robots functioning in stochastic settings. Scheduling AMRs in such environments is a variant of the traditional vehicle routing problem (VRP) due to their unique service characteristics. VRPs typically encompass different stochastic aspects, including uncertainty in requests, service times, and travel times.

In stochastic settings, VRPs are typically approached as multi-stage stochastic programming models to minimize expected total costs, with two main model types: chance-constrained programming (CCP) and stochastic programming with recourse. The CCP model enforces constraint conditions to meet a specific confidence level. Various researchers have delved into these models to address stochastic elements in VRPs. For VRPs, heuristic algorithms are commonly adopted to derive satisfactory solutions. These include genetic algorithms, variable neighborhood search algorithms, grey wolf optimizers, ant colony algorithms, gravitational search algorithms, and the tabu search algorithm (TS). While TS effectively solves VRPs in stochastic environments, it may be time-consuming, leading to improvements and hybrid approaches proposed by scholars.

TS algorithm

The current study focuses on AMR scheduling in stochastic hospital environments, considering different constraints, including single-route service per request, input-output arc balance, AMR loading capacities, and time window adherence. The objective function minimizes total costs, consisting of AMR fixed, penalty, and transportation costs. The arrival time approximation follows a normal distribution.

TS Algorithm: The AMR scheduling problem poses a computational challenge, making it difficult to achieve optimal solutions within reasonable computation time. Therefore, heuristic algorithms are typically employed to find suboptimal solutions. TS, a neighborhood search-based heuristic algorithm, is well-suited for solving combinatorial optimization problems, including variants of the VRP involving stochastic elements.

Improved TS (I-TS) improves the standard TS algorithm by incorporating a greedy insertion algorithm, an adaptive mechanism for selecting neighborhood operators, and more effective tabu tenure parameters for addressing the scheduling problem effectively.

Experiments and results

Improved Solomon Instances: To address the lack of suitable benchmark problems for AMR services, new instances based on the Solomon benchmark (C, R, and RC) are generated. These instances feature varying geographical location distributions (clustered, uniform, and semi-clustered), time window widths, and environments (morning peak, afternoon peak, and non-peak). Each instance has two subsets: type-1 and type-2, based on time windows. The Solomon benchmark is modified to reflect hospital-specific conditions, including service times, time window definitions, AMR travel speeds, and the distribution of medical requests across floors.

Parameter Tuning: Parameter tuning is crucial for the effectiveness of the I-TS algorithm. Experiments are conducted to optimize two key parameters: tabu tenure and the number of iterations. Results suggest the value of tabu tenure is 40, and the number of iterations is 500 for effective problem solving.

Validity Test of the I-TS Algorithm: The I-TS algorithm's performance is evaluated in comparison to CPLEX (simplex algorithm implementation in C), especially in solving 20-request instances in a deterministic setting. The results demonstrate that the I-TS algorithm provides near-optimal solutions within a relatively short time, outperforming CPLEX in some instances. This underscores the effectiveness of the I-TS algorithm in finding high-quality solutions efficiently.

AMR Routing Planning: An example of AMR route planning for the environment RC101 with 20 instances is presented. Key findings include the necessity of at least 16 AMRs to handle the tasks effectively, varying service probabilities for different routes, and a decrease in service probability as the number of requests on a route increases. These results highlight the stochastic programming model's effectiveness in planning AMR routes across diverse environments.

Management Insight: Service quality is assessed using the concept of service probability, which represents the likelihood of medical requests being serviced within specified time windows. Results show high service probabilities across various environments, indicating the effectiveness of the proposed stochastic programming model for AMR scheduling. Additionally, the number of AMRs participating in service is analyzed, with wider time windows requiring fewer AMRs due to reduced penalty costs. The stochastic programming model proves feasible for AMR scheduling in different hospital environments.

Conclusion

In summary, the research examines hospital AMR scheduling, addressing randomness in service and travel times. A stochastic programming model minimizes fixed, operation, and delay costs. An I-TS algorithm combining greedy insertion and tabu search is proposed, with a repair operator for infeasible solutions. Experiments confirm its effectiveness in generating reliable AMR service routes in stochastic settings. Future work may consider dynamic emergency requests and more complex time distributions, adding complexity to the problem.