EURO 2025 Leeds
Abstract Submission

838. Multi-Appointment Scheduling with Patient Transportation

Invited abstract in session TA-20: Applications of combinatorial optimisation in industry and services 1, stream Combinatorial Optimization.

Tuesday, 8:30-10:00
Room: Esther Simpson 2.11

Authors (first author is the speaker)

1. Yang Wang
School of Management, Northwestern Polytechnical University
2. JUNPENG WANG
School of Management, Northwestern Polytechnical University
3. yaohui guo
School of Management, Northwestern Polytechnical University
4. Abraham Punnen
Simon Fraser University

Abstract

This paper addresses a novel multi-appointment scheduling problem with patient transportation (MASPT), where each patient requires a series of diagnostic tests and transportation operations across hospital departments under limited resource availability. The problem involves assigning each diagnostic test to a specific machine and each transportation operation to a designated resource, while determining their start times to minimize total patient waiting time. To tackle this problem, we formulate Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP) models and develop a two-individual based path-relinking (TIPR) algorithm. The TIPR algorithm incorporates three key innovations: (1) a novel encoding-decoding scheme that efficiently transforms a permutation list into a feasible schedule, (2) a backward swap-based local search strategy that leverages decoded information to enhance search efficiency, and (3) a forward swap-based path-relinking mechanism to promote solution diversity. Using real-world hospital data, we generate test instances with diverse structures and sizes to evaluate the proposed approaches. Experimental results demonstrate that the TIPR algorithm outperforms both MILP and CP models, as well as existing hospital scheduling practices. Furthermore, our findings reveal that while increasing transportation resources improves scheduling performance, the marginal benefit diminishes once a certain resource threshold is reached.

Keywords

Status: accepted

Back to the list of papers