💻 computer science

Walk-In Multi-Stage Patient Flow Scheduling: An ASP Model with DES-Based Evaluation

This paper presents a reactive, multi-stage patient flow scheduling model for walk-in hospitals using Answer Set Programming (ASP) to optimize examination pathways and minimize travel and waiting times, demonstrating through Discrete-Event Simulation (DES) that it significantly outperforms greedy baselines in reducing patient stay durations, particularly under heavy load conditions.

Original authors: Ngoc-Mai Pham, Trang-Linh Nguyen, Thi-Hai-Yen Vuong, Ha-Thanh Nguyen, Van-Giang Trinh

Published 2026-07-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ngoc-Mai Pham, Trang-Linh Nguyen, Thi-Hai-Yen Vuong, Ha-Thanh Nguyen, Van-Giang Trinh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking into a massive, bustling theme park where the rides are medical tests and the park is a hospital. In a perfect world, you'd buy a ticket, get a map, and glide from one ride to the next without ever waiting in line. But in the real world, especially in busy hospitals, things are chaotic. Patients arrive without appointments, they need to do several different "rides" (like blood tests, X-rays, and scans) in a specific order, and the lines are long. The big question for scientists is: How do you organize this chaos? Should you just let people grab the first open spot they see (a "greedy" approach), or should you use a super-smart computer to plan the perfect route for everyone, considering how long lines are and how far people have to walk? This is the heart of "scheduling," a field that tries to make complex systems run smoothly. It's like being the ultimate traffic controller for a city where the cars are people, the roads are hallways, and the intersections are examination rooms. If you get it wrong, people wait too long; if you get it right, the whole system flows like water.

In this paper, the authors tackle a specific kind of chaos: the "walk-in" patient. These are people who show up at the hospital without a pre-booked time and need a series of tests done during a single visit. The researchers built a new way to schedule these patients using a clever type of logic puzzle solver called Answer Set Programming (ASP). Think of ASP as a super-organized librarian who can instantly look at every possible way to arrange a patient's day, check the rules (like "you must do the blood test before the scan"), and pick the absolute best path. But here's the twist: the hospital isn't a static puzzle; it's a living, breathing place where lines change and people arrive randomly. So, the authors didn't just solve the puzzle; they built a "time machine" called Discrete-Event Simulation (DES). This time machine lets them replay the day thousands of times with random delays to see if their smart schedule actually holds up when things get messy.

The team compared their smart ASP planner against two simpler methods used in real life. The first was a "greedy" approach, where a patient is sent to the first available room, ignoring what might happen next. The second was a slightly smarter version that tried to guess future lines but still made decisions one step at a time. The results, tested on huge made-up datasets representing hospitals with 100 to 650 patients, suggest that the ASP approach is a game-changer, especially when the hospital is packed. In simulations with heavy crowds, the ASP method reduced the total time patients spent in the hospital and significantly increased the number of people who didn't have to wait at all. For example, in a busy scenario with 400 patients, the ASP method helped 6.5% of patients avoid waiting entirely, compared to only 5% for the greedy method. Even more impressively, the smart planner kept the average "stay time" lower than the other methods, proving that thinking ahead about the whole journey is better than just reacting to the current moment.

However, the authors are careful to note that this isn't a magic wand that fixes everything instantly. The improvements were most noticeable when the hospital was under heavy pressure; when there were plenty of open rooms and few patients, all methods worked about the same. Also, while the ASP method was great at cutting down waiting time, it didn't drastically reduce the time spent walking between rooms, because the hospital layout is fixed and there aren't many shortcuts to find. The study also points out that their data was simulated based on typical hospital patterns, not real-world logs, because real data is often hidden for privacy reasons. They also assumed that once a patient is in a room, they are served in the exact order they arrived, ignoring emergencies or sick patients who might need to jump the line.

Ultimately, the paper suggests that by combining a powerful logic solver with a realistic simulation, we can create a "reactive" system that adapts to new patients the moment they walk through the door. It's like having a GPS that doesn't just tell you the fastest route to your destination, but recalculates the entire trip every time a new car enters the highway, ensuring you don't get stuck in a jam. While the authors admit there's still work to do—like testing this on real hospital data and handling emergencies—their work shows that with the right tools, we can make the hospital experience less stressful and more efficient for everyone.

Technical Summary: Walk-In Multi-Stage Patient Flow Scheduling

Problem Formulation
The paper addresses a reactive scheduling problem in walk-in hospital environments, specifically within multi-department settings common in developing countries like Vietnam. Unlike appointment-based systems, patients arrive without pre-booked slots and require a sequence of multiple examinations across different departments during a single visit. The core challenge is to dynamically compute a feasible examination pathway for each arriving patient that determines both the sequence of examinations and the assignment of examination rooms.

This problem is constrained by:

Medical Precedence: Certain examinations must occur before others.
Room Capacity: Limited slots in examination rooms.
Travel Time: Time required to move between departments.
Dynamic State: The scheduler must account for the current queue lengths and the activities of previously scheduled patients.

The objective is to minimize a two-part cost function: waiting time (queue-induced delays weighted by examination duration) and travel time between consecutive locations. The optimization is lexicographic, prioritizing the reduction of waiting time over travel time.

Methodology
The authors propose a hybrid framework combining declarative optimization with stochastic simulation:

Answer Set Programming (ASP) Model:
- The problem is modeled declaratively using clingo.
- Hard Constraints: The model enforces that every required examination is assigned exactly once, rooms match examination types, and medical precedence is respected.
- Optimization: Weak constraints are used to minimize waiting time (primary) and travel time (secondary).
- Reactive Mechanism: The solver is triggered upon each new patient arrival. It takes the current hospital state (including estimated queues and historical schedules) as input, computes an optimal pathway, and updates the system state (specifically the hist parameter) for the next arrival.
- Queue Estimation: To handle the dynamic nature of queues without full simulation at the solving step, the ASP model approximates the queue length at a future time $t$ using a throughput-based formula: $Queue(t) \approx \max(0, \text{InitialQueue} + \text{ScheduledArrivals}(t) - \text{Capacity} \times t / \text{AvgDuration})$ .
Discrete-Event Simulation (DES) Evaluation:
- Because the ASP model relies on deterministic assumptions and estimated queues, the authors employ a DES layer to evaluate the robustness of the generated schedules under stochastic service times and arrivals.
- The DES simulates the actual flow of patients, handling events like "Arrival" and "Start," and re-queues events if slots are unavailable, providing a realistic assessment of performance metrics like total stay time and zero-wait rates.
Baselines:
- DES (Greedy): A reactive strategy that assigns patients to the earliest available slot based on the current state, without anticipating future congestion.
- DES-F (Future Estimation): An extension of the greedy baseline that incorporates a future queue estimation similar to the ASP model to predict availability, serving as a fairer comparison for the optimization component.

Key Contributions

Novel Formulation: A reactive scheduling formulation for multi-stage walk-in pathways that jointly optimizes exam ordering and room assignment, addressing a gap in existing literature which often treats these separately or focuses on appointment-based systems.
ASP Encoding with Lexicographic Optimization: An efficient ASP model that prioritizes minimizing waiting time over travel cost, capable of solving the problem in under 0.1 seconds even for large grounding sizes.
DES-Based Evaluation Framework: A methodology that integrates declarative optimization with simulation to assess performance under stochastic conditions, bridging the gap between theoretical optimality and operational reality.
Empirical Validation: Large-scale synthetic experiments demonstrating the approach's effectiveness across varying capacity regimes and patient loads.

Experimental Results
The authors evaluated the approach on synthetic datasets derived from Vietnamese hospital parameters, testing scenarios with 100 to 650 patients and varying utilization rates (20% to 72%).

Performance vs. Baselines: The ASP approach consistently outperformed both DES and DES-F baselines in terms of median patient stay time and the proportion of zero-wait patients.
Impact of Load: The improvements were most pronounced under heavy loads (high utilization). For instance, in the 400-patient low-capacity scenario, ASP reduced the median stay time significantly compared to baselines and increased the zero-wait rate to 6.5% (vs. 5.0% for DES and 6.0% for DES-F).
Scalability: The solver remained computationally efficient (average runtime < 0.1s) even as the number of patients increased. In high-capacity scenarios, while the performance gap narrowed (as resources became less constrained), ASP still maintained superior or comparable metrics, particularly in reducing the number of "unfinished" patients (those who could not complete exams within the 10-hour window).
Stability: While the ASP approach showed slightly wider interquartile ranges (IQR) in stay times compared to the fixed-order DES-F (due to its flexibility in routing), it provided a more predictable experience than the standard greedy DES and consistently optimized total stay time.

Significance and Claims
The paper claims that its primary significance lies in providing a flexible decision-support framework for walk-in healthcare environments where real-time decision support is often absent. By unifying sequencing, resource allocation, and spatial routing within a reactive framework, the approach addresses the complexity of multi-stage patient flows that traditional appointment-based models overlook.

The authors modestly note that while the ASP model optimizes under deterministic assumptions, the integration with DES allows for a realistic assessment of operational performance. They acknowledge limitations, including the use of synthetic data (due to privacy restrictions on real micro-level hospital logs), the assumption of First-Come-First-Served service within rooms (ignoring patient acuity or emergencies), and the lack of re-optimization after each completed examination. However, the results suggest that declarative optimization via ASP is a viable and effective method for improving hospital resource management and patient flow in dynamic, walk-in settings.

Technical Summary: Walk-In Multi-Stage Patient Flow Scheduling

More like this