To address the target inaccessibility issue of the Artificial Potential Field (APF) method and the slow convergence of deep reinforcement learning algorithms, we propose a method combining the artificial potential field and an improved twin delayed deep deterministic policy gradient algorithm (PG-ITD3) for UAV path planning in post-disaster scenarios. This approach considers Unmanned Aerial Vehicles (UAV) kinematic constraints and dynamically adjusts the repulsive gain coefficient through deep reinforcement learning to enhance planning efficiency. The introduction of a virtual obstacle strategy, combining the aftershock probability model with prioritized experience replay (PER), and a novel reward function facilitates real-time reward acquisition and accelerates convergence. Simulation results demonstrate that our proposed algorithm outperforms traditional APF method and other advanced deep reinforcement learning methods in success rate, path length, path reward, and global smoothness. This research offers an effective solution for post-disaster UAV rescue path planning, contributing significantly to enhancing rescue efficiency and safety.

The$\alpha $-separator problem ($\alpha $-SP) consists of finding the minimum set of vertices whose removal separates the network into multiple different connected components with fewer than a limited number of vertices in each component, which belongs to the family of critical node detection problems. The$\alpha $-SP problem is an important NP-hard problem with various real-world applications. In this paper, we propose a frequent itemset-driven search (FIS) algorithm to solve$\alpha $-SP, which integrates the concept of frequent itemset into the well-known memetic search framework. Starting from a high-quality population built by population construction and population repair, FIS then iteratively employs a frequent itemset recombination operator (to generate promising offspring solution), a tabu-based simulated annealing (to find local optima), a population repair procedure, and a population management strategy (to guarantee healthy/diverse population). Extensive evaluations on 50 benchmark instances show that FIS significantly outperforms the state-of-the-art algorithms. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds. Finally, we experimentally analyze the importance of each key algorithmic component, and perform a case study on an air transportation network for understanding its network structure and identifying its influential airports.

This paper is devoted to the management of advance admission requests for obstetric care. Pregnant women in China select one hospital and request admission for both antenatal and postnatal care after nine weeks of pregnancy. Schedulers must make the admission decision instantly based on the availability of the most critical resource, that is, hospital beds for postnatal care. The random delay between admission requests and postnatal care has created a distinct advance admission control problem. To address this issue, we propose a basic model that assumes a unit bed requirement for one day. Each admission generates a unit of revenue and each unit of overcapacity use incurs an overcapacity cost. With the objective of maximizing the expected net revenue, we establish an optimal policy for unlimited requests, that is, an expected arrival time quota (EATQ) policy that accepts a fixed quota of advance admission requests with the same expected date of confinement. We then propose an extended model for general capacity requirements. Using the Poisson approximation, we establish the optimality of the EATQ policy, which is shown to be solvable by a simple linear programming model. We compare the numerical results from the different policies and conduct a sensitivity analysis. The EATQ policy is demonstrated to be the best option in all test instances and notably outperforms the current admission rules used in hospitals, which usually accept admission requests according to some empirical monthly quota of the expected delivery month. The Poisson approximation is shown to be effective for determining the optimal EATQ policy for both stationary and nonstationary arrivals. Summary of Contribution: First, this paper investigates the advance admission control problem for obstetric care. Pregnant women in China choose one hospital and request admission for both antenatal and postnatal care after nine weeks of pregnancy but the most critical resource is hospitalization beds needed for postnatal care. The random delay between admission request and postnatal care makes the problem unique and challenging to solve. It belongs to the scope of computing and operations research. Second, this paper formulates a dynamic programming model, analyzes the structural properties of the optimal control policy, and finally proposes a mathematical programming model to determine the optimal quota. Numerical experiments show the validity of the proposed approach. It covers the research contents of theories on dynamic stochastic control, mathematic programming model, and experiments. Moreover, this paper is motivated by the practical problem (advance admission control) in obstetric units of Shanghai. Using these optimality properties, solution approaches, and numerical results, this paper provides guidance on how to manage advance obstetric admission requests.

The joint optimization problem of multiresource capacity planning and multitype patient scheduling under uncertain demands and random capacity consumption poses a significant computational challenge. The common practice in solving this problem is to first identify capacity levels and then determine patient scheduling decisions separately, which typically leads to suboptimal decisions that often result in ineffective outcomes of care. In order to overcome these inefficiencies, in this paper, we propose a novel two-stage stochastic optimization model that integrates these two decisions, which can lower costs by exploring the coupling relationship between patient scheduling and capacity configuration. The patient scheduling problem is modeled as a Markov decision process. We first analyze the properties for the multitype patient case under specific assumptions and then establish structural properties of the optimal scheduling policy for the one-type patient case. Based on these findings, we propose optimal solution algorithms to solve the joint optimization problem for this special case. Because it is intractable to solve the original two-stage problem for a general multitype system with large state space, we propose a heuristic policy and a two-stage stochastic mixed-integer programming model solved by the Benders decomposition algorithm, which is further improved by combining an approximate linear program and the look-ahead strategy. To illustrate the efficiency of our approaches and draw managerial insights, we apply our solutions to a data set from the day surgery center of a large public hospital in Shanghai, China. The results show that the joint optimization of capacity planning and patient scheduling could significantly improve the performance. Furthermore, our model can be applied to a rolling-horizon framework to optimize dynamic patient scheduling decisions. Through extensive numerical analyses, we demonstrate that our approaches yield good performances, as measured by the gap against an upper bound, and that these approaches outperform several benchmark policies. Summary of Contribution: First, this paper investigates the joint optimization problem of multiresource capacity planning and multitype patient scheduling under uncertain demands and random capacity consumption, which poses a significant computational challenge. It belongs to the scope of computing and operations research. Second, this paper formulates a mathematical model, establishes optimality properties, proposes solution algorithms, and performs extensive numerical experiments using real-world data. This work includes aspects of dynamic stochastic control, computing algorithms, and experiments. Moreover, this paper is motivated by a practical problem (joint management of capacity planning and patient scheduling in the day surgery center) in our cooperative hospital, which is also key to numerous other applications, for example, the make-to-order manufacturing systems and computing facility systems. By using the optimality properties, solution algorithms, and management insights derived in this paper, the practitioners can be equipped with a decision support tool for efficient and effective operation decisions.

Home care (HC) services represent an effective solution to face the health issues related to population aging. However, several scheduling problems arise in HC, and the providers must make several scheduling and routing decisions, e.g., the assignment of caregivers to clients, in order to balance operating costs and client satisfaction. Starting from the analysis of a real HC provider operating in New York City, NY, USA, this article addresses a scheduling problem with chargeable overtime and preference matching and formulates it as an integer programming model. The objective is to minimize a cost function that includes traveling costs, the overtime cost paid by the provider, the preference mismatch, and a penalty related to the continuity of care violation. To solve this problem, we design a matheuristic algorithm that integrates a specific variable neighborhood search with a set covering model. The results demonstrate the applicability and efficiency of our approach to solving real-size instances. Sensitivity analyses are also performed to discuss practical insights. Note to Practitioners-This article provides a decision support tool to HC managers, which appropriately assigns caregivers to clients and makes routing decisions over a long horizon. Chargeable overtimes and preference matching enclosed in this tool are rarely considered in the literature, despite matching is relevant in HC caregiver-to-client assignments and chargeable overtime has potential in tailoring the service level based on the specific client. We formulate the scheduling problem as a mathematical model. Then, we propose a matheuristic algorithm to efficiently solve the problem in real-size instances. The results show the applicability and efficiency of our method. Thus, HC managers can exploit it to efficiently make assignment and routing decisions and to analyze the impact on other operating costs when adjusting any of them.

This article studies the optimal allocation of inpatient rooms for multiple types of patients in public hospitals and the patient scheduling problem with planned acceptance ratios (ARs). For public hospitals, it is important to allocate limited resources to multiple types of patients and manage patient access for maximizing hospital revenue and upholding service equity. The problem is formulated as two-stage models. Considering uncertainties in patients' arrival and length of stay, we first propose a nonlinear stochastic programming (NSP) model for inpatient room allocation with the objective of maximizing revenue under the constraints of maintaining equity. To solve this problem, we transform the complex NSP model into a deterministic mixed-integer linear programming model, which is solved by CPLEX, by reformulating the chance constraints as knapsack constraints based on a linearization technique and a simulation model. Given the allocated capacity and planned AR, we further propose a two-stage stochastic mixed-integer program combined with a goal program model to optimize patient scheduling. To solve the model, a Benders decomposition based on the sample average approximation approach is proposed. The real data-based experimental results demonstrate the applicability and effectiveness of our models and approaches. The impacts of some parameters on the objective and decisions are also explored. A simulation procedure is developed to compare the performances of different patient scheduling methods, from which the results show that our proposed approach outperforms a benchmark policy. Note to Practitioners-Inpatient rooms are critical resources for hospitals. Against the background of aging populations and environmental problems, the twofold predicament-involving escalating healthcare demands and insufficient room-based resources-has led to the necessity for hospitals to operate more effectively and efficiently. Capacity management and patient scheduling are thus the two most important operations for hospital management. Because of the self-financing feature of hospitals and the quasi-public nature of medical services, it is important for public hospitals to judiciously allocate limited room capacities to multiple types of patients for balancing revenue and equity and schedule the arrival demands dynamically according to the planned capacity and acceptance ratio. In this article, we propose mathematical models and solution approaches for these two-stage problems, and their applicability and effectiveness are demonstrated by experiments based on real data. The managerial insights suggest that hospitals should improve the service equity gradually according to their financial situation because of the increasing marginal cost and should apply the scientific approaches and techniques, rather than by their experiences, to aid their management for better performance. By using approaches proposed in this article, hospital managers can be equipped with a decision support tool for effective capacity allocation and patient scheduling decisions. The parameters of our models could be tuned based on the preferences of different hospitals. Furthermore, these approaches can be applied to other settings with similar problems, such as government budget allocation considering both utility and equity, and service system management with waiting time requirement.

The environment after disaster is complicated and it is difficult to rescue the survivors timely and effectively. Robots can complete the rescue work instead of rescuers with high-efficiency and without limits of the disaster area. Based on this, a novel task allocation method for multi-robot in an environment after disaster is presented. Firstly, according to the locations and time constraints of the tasks, a new grouping method of the tasks is proposed to reduce the computational complexity. Following that, a new initial solution generation method is used to speed up the evolution. Finally, an improved particle swarm algorithm with the adaptive inertia weight and velocity update is developed to solve the grouping-based task allocation. The experimental results indicate that the proposed method can increase the success rate of rescue and speed up the rescue effectively.

In this paper, a modified centralized algorithm based on particle swarm optimization (MCPSO) is presented to solve the task allocation problem in the search and rescue domain. The reason for this paper is to provide a benchmark against distributed algorithms in search and rescue application area. The hypothesis of this paper is that a centralized algorithm should perform better than distributed algorithms because it has all the available information at hand to solve the problem. Therefore, the centralized approach will provide a benchmark for evaluating how well the distributed algorithms are working and how much improvement can still be gained. Among the distributed algorithms, the consensus-based bundle algorithm (CBBA) is a relatively recent method based on the market auction mechanism, which is receiving considerable attention. Other distributed algorithms, such as PI and PI with softmax, have shown to perform better than CBBA. Therefore, in this paper, the three distributed algorithms mentioned earlier are compared against three centralized algorithms. They are particle swarm optimization, MCPSO, described in this paper, and genetic algorithms. Two experiments were conducted. The first involved comparing all the above-mentioned algorithms, both centralized and distributed, using the same set of application scenarios. It is found that MCPSO always outperforms the other five algorithms in time cost. Due to the high failure rate of CBBA and the other two centralized methods, the second experiment focused on carrying out more tests to compare MCPSO against PI and PI with softmax. All the results are shown and analyzed to determine the performance gaps between the distributed algorithms and the MCPSO. Note to Practitioners-This paper was motivated by the limitation of current distributed task allocation algorithms as they cannot achieve performances that are as good as the centralized ones. Therefore, a centralized algorithm is designed to evaluate the performance gap between the state-of-the-art distributed and centralized approaches. In the future research section, a new distributed particle swarm optimization (PSO) algorithm is proposed based on this paper as the research has shown that the proposed centralized PSO algorithm delivers the best results so it is potentially a strong candidate for adaptation.

The intensive care unit (ICU) delivers care to critically ill patients with high resource intensity. Stochastic patient arrival and uncertain length of stay in ICUs present tremendous challenge to establish the admission and discharge policy to maximize the number of surviving patients and improve operational efficiency. In practice, ICU schedulers reserve some beds for potential patients with most critical conditions. Moreover, they prematurely discharge current ICU patients who are in stable status to accommodate for new and more urgent arrivals. We develop an analytical framework to quantify the impact of the number of reserved beds and suggest when to prematurely discharge current patients. A Markov decision process model is established to strike a balance between the rejection of incoming patient and the premature discharge in the near future. Monotonicity, concavity, and structural properties of the optimal control policy are presented. Using the inpatient record at a tertiary-level hospital in China, we conduct a case study and propose an effective threshold policy. Extensive numerical experiments are performed to analyze the effect of each parameter on the total survival benefits and compare different policies.

Diagnostic facility is one of the most important critical resources in the hospital. Patient scheduling plays an important role in managing these facilities, especially when they are shared between regular and emergency patients. Due to the non-stationary emergency arrival and waiting time targets of emergency patients, it is challenging for hospital managers to make appointment scheduling decision and real time scheduling decisions, i.e., how many regular patients could reserve the service and how to coordinate the service of both types of patients. To deal with this problem, this paper proposes a stochastic integer programming model by considering the uncertainty of emergency patients and their waiting time requirement. The objective is to minimize the weighted idle time, overtime, and patients' waiting time. Monte Carlo optimization is used to solve this model. Numerical experiments are proposed to show the usefulness of the proposed model for investigation of the influence of different parameters.

This paper addresses the dynamic assignment of a given set of surgeries to multiple identical operating rooms (ORs). Surgeries have random durations and planned surgeon arrival times. Surgeries are assigned dynamically to ORs at surgery completion events. The goal is to minimize the total expected cost incurred by surgeon waiting, OR idling, and OR overtime. We first formulate the problem as a multistage stochastic programming model. An efficient algorithm is then proposed by combining a two-stage stochastic programming approximation and some look-ahead strategies. A perfect information-based lower bound of the optimal expected cost is given to evaluate the optimality gap of the dynamic assignment strategy. Numerical results show that the dynamic scheduling and optimization with the proposed approach significantly improve the performance of static scheduling and First Come First Serve (FCFS) strategy.

In order to solve the problem of path planning in an environment with many terrains, we propose a method based on interval multi-objective Particle Swarm Optimization (PSO). First, the environment is modeled by the line partition method, and then, according to the distribution of the polygonal lines which form the robot path and taking the velocity's disturbance into consideration, robot's passing time is formulated as an interval by combining Local Optimal Criterion (LOC), and the path's danger degree is estimated through the area ratio between the robot path and the danger source. In addition, the path length is also calculated as an optimization objective. As a result, the robot path planning problem is modeled as an optimization problem with three objectives. Finally, the interval multiobjective PSO is employed to solve the problem above. Simulation and experimental results verify the effectiveness of the proposed method.

This paper addresses the design of contract for reserving the capacity of a shared critical resource from the perspective of a given class of customers. The contract is composed of three parts: contracted time slots (CTSs) reserved by the service provider for the class of customers, advance cancellation of contracted time slots, and requests for regular time slots (RTSs). The problem of CTS cancellation and RTS assignment is formulated as an average cost Markov Decision Process in order to minimize the total cost including customer waiting times, unused CTS, and CTS cancellation. Structural properties of the optimal control policies are established via the discounted cost problem. A local optimization algorithm is proposed to improve a given initial contract. Numerical results show that advance CTS cancellation significantly reduces the ratio of unused CTS with slight increase of customer waiting time.

This article surveys the medium term capacity planning methods for semiconductor wafer fabrication. The objectives of this article are to (1) identify the current research and fundamental methods for capacity planning, that is, spreadsheet, simulation, queueing model, linear programming and stochastic programming methods, and (2) take an in-depth look at the future research interest whether is it possible or not to combine the methods accepting uncertainty and those evaluating performance.