Minimizing delays of patient transports with incomplete information: A modeling approach based on the vehicle routing problem

Adelhütte, Dennis; Braun, Kristin; Liers, Frauke; Tschuppik, Sebastian Article — Published Version Minimizing delays of patient transports with incomplete information: A modeling approach based on the vehicle routing problem OR Spectrum Provided in Cooperation with: Springer Nature Suggested Citation: Adelhütte, Dennis; Braun, Kristin; Liers, Frauke; Tschuppik, Sebastian (2024) : Minimizing delays of patient transports with incomplete information: A modeling approach based on the vehicle routing problem, OR Spectrum, ISSN 1436-6304, Springer, Berlin, Heidelberg, Vol. 47, Iss. 2, pp. 565-604, https://doi.org/10.1007/s00291-024-00788-6 This Version is available at: https://hdl.handle.net/10419/323265 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) OR Spectrum (2025) 47:565–604 https://doi.org/10.1007/s00291-024-00788-6 ORIGINAL ARTICLE Minimizing delays ofpatient transports withincomplete information: Amodeling approach based onthevehicle routing problem DennisAdelhütte1· KristinBraun1,2 · FraukeLiers1· SebastianTschuppik1 Received: 8 September 2023 / Accepted: 22 August 2024 / Published online: 10 September 2024 © The Author(s) 2024 Abstract We investigate a challenging task in ambulatory care, the minimizing of delays of patient transports. In practice, a limited number of vehicles is available for non-rescue transports. Furthermore, the dispatcher rarely has access to complete information when establishing a transport plan for dispatching the vehicles. If additional transport is requested on demand then schedules need to be updated, which can lead to long delays. We model the scheduling of patient transports as a vehicle routing problem with general time windows and solve it as a mixed-integer linear problem that is modified whenever additional transport information becomes available. We propose a modeling approach that is designed to determine fair and stable plans. Furthermore, we show that the model can easily be modified when transports need to satisfy additional requirements, e.g., during pandemics, exemplarily the Covid-19 pandemic. To show the applicability and efficiency of our modeling approach, we conduct a numerical study using historical data from the region of Middle Franconia. The results reveal and show that, by applying mathematical optimization—or, to be more precise by solving mixed-integer linear problem formulations—one can significantly decrease delays and have considerable potential for optimized patient transports. Keywords OR in health services· Vehicle routing· Heuristics· Mixed-integer linear optimization· Patient transport * Kristin Braun [email protected] 1 Department ofData Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, Cauerstraße 11, 91058Erlangen, Germany 2 Fraunhofer Institute forIntegrated Circuits IIS, Nordostpark 84, 90411Nuremberg, Germany 566 D.Adelhütte et al. 1 Introduction In a healthcare system, patient transport needs to be well planned to ensure a functioning system. Because such a system consists of many components, e.g., health promotion, primary care, specialized services, and hospitals, transporting patients without delays is by no means trivial, especially when the respective transports are not emergencies and can be postponed. This could be the case when a patient needs to be transported home from a hospital or when patients receive certain treatments at a specific destination. While in principle those transports could be carried out by the vehicles that carry out rescue transports, a different fleet is typically used for other patient transports in Germany. In contrast to rescue transports, patient transports allow delays, though they are not desirable. Scheduling them is a challenge due to different reasons. While the number of vehicles in the transport fleet is limited, the drivers’ work shifts need to be respected. Moreover, a vehicle can transport only one patient at once. Finally, not all transport requests are known at the time when the plans are established: Many transports are requested during the day when a transport schedule is already in operation. The last point in particular can lead to long delays for patients waiting for their transport, as it is often impossible to handle all transports at once. A natural scheduling approach is a greedy approach: whenever a transport is requested, the vehicle that can reach the patient most quickly is dispatched. This approach is performed in Middle Franconia, according to the local dispatcher, the Integrierte Leitstelle Nürnberg (ILS). For the resulting transport plans, optimization potential is usually disregarded and sometimes transports even have to be rescheduled to the following day. As a motivation, we provide some statistics about the transport data in the following. 1.1 Statistics aboutthepatient transports We consider the number of transports from January 2020 to July 2021. In Fig.1a, we plot the number of patient transports. The number of weekly transports on weekends, especially on Sundays, is decreasing, while the total number of transports shows a similar order of magnitude. Over the turn of the year, due to Christmas and other holidays, fewer transports are requested. In 2020, there is another small decrease starting in April. There is no such decline before 2020, so this is likely due to the onset of the Covid-19 pandemic. Further, we plot the percentage of transports that involved an patient either infected, or, at least, suspected to be infected, with Covid-19. These are represented by the black portion of the bars in Fig. 1a. For better visibility, the percentage of Covid-19 transports is also given in Fig.1b. In the peak phase, up to 60% of all transports have been classified as infected cases. This is—as there are a lot of suspected cases—not the actual number of infections. However, the trend given in Fig.1b is quite similar to the number of actual Covid-19 cases in Middle Franconia, cf. Robert Koch Institute (2020). This trend is shown in the red part of the plot. 567 Minimizing delays ofpatient transports withincomplete… Furthermore, we consider the number of transports during the course of a day in Fig.2: Transports are distinguished depending on the time when they are requested and the number of requested transports per hour is plotted for the same time window as before. The majority of the transports are requested at 6 am or later. The peak is in the late morning, thereafter the number slowly decreases. After about 7 pm, the number of transports is again relatively low compared to the previous hours. (a) Absolutenumberof transports,distinguished on the basis whetherthe patient is knowntobe infected (black bars) or not (gra y bars). (b)Percentageofknown Covid-19transports and totalnumberofCovid-19 cases in the catchment area of the ILS. Fig. 1 Statistics on the numbers of transports and the percentage of known Covid-19 transports for the available data Fig. 2 Number of plannable and ad hoc transports, differentiated by the target time 568 D.Adelhütte et al. The number of plannable transports1 is shown in the gray bars, while the black bars represent the number of ad hoc transports.2 In the early morning hours, i.e., between 6 and 8 am a lot of transports are ad hoc ones. After that, until noon, most transports are plannable. Then, the percentage of ad hoc transports increases over the course of the day. After 3 pm, more than 80% of all transports are ad hoc transports. 1.2 Our contribution In this paper, we model the problem of finding fair schedules for patient transports. In our case, ‘fair’ means that the maximum delay over all patient transports is minimized as the first priority, before, secondly, the total delay over all transports is minimized. Besides the aim of distributing the minimal delay among the patients roughly uniformly we need to respect the drivers’ shifts whenever possible. We present two approaches to handle transports that are requested during the course of the day: On the one hand, if the dispatcher has knowledge of the requested transport in advance, but does not yet know the time it is supposed to happen (for example a patient needs to be taken home after a treatment), so-called dummy transports are introduced to block vehicle capacities. These transports can be expected due to, for example, requests that typically come in at specific times of the day or as follow-up transports. On the other hand, whenever an ad hoc transport becomes known to the dispatcher, we reoptimize the part of the schedule that has not yet begun and establish a new schedule that incorporates the ad hoc transport. The model is based on the vehicle routing problem with general time windows (VRPGTW) that was introduced in Ibaraki etal. (2005). We solve the optimization problems using state-of-the-art solvers for MIP that we enhance with heuristics in order to improve their running time. We demonstrate that one can modify our proposed model whenever necessary by introducing a general and adaptable way to add new inequalities, equations and penalty variables. As an application, we discuss the issues that need to be taken into account during the Covid-19 pandemic to minimize the risk of infection and how to model them. In our numerical study, we show that our optimized procedure for scheduling transports is effective and efficient in practice. Regarding infectious illnesses, we show that transporting patients that are (at least suspected to be) infected using separate vehicles is desirable. In several key points, our approach differs from previous work. Firstly, rather than treating fairness as a separate model parameter, we incorporate it directly into our objective function. Secondly, our methodology ensures robustness without the use of random variables. Thirdly, rather than focusing on optimizing required time or returned distance, we prioritize minimizing delays for patients even if this causes detours of vehicles. Our research is based on a dynamic and deterministic vehicle routing problem (VRP) and employs a wait-first strategy. Finally, because rescue and non-rescue transports in Germany use separate vehicle fleets, we also use a 1 Transports that are known when establishing a schedule. 2 Transports that become known during the day. 569 Minimizing delays ofpatient transports withincomplete… separate fleet dedicated solely to patient transports, distinct from the fleet designated for rescue vehicles. We discuss these points in more detail in our literature review in Sect.2. 1.3 Structure ofthepaper In Sect.2, we present related work concerning vehicle routing problems and other problems arising in the healthcare sector. Furthermore, we show our chosen way of modeling the VRPGTW. Thereupon, in Sect.3, the patient transport problem is described on an abstract level. We first define different transports and discuss the amount of information available at the time of planning. We also introduce techniques for modifying models on an abstract level. In Sect.4, we discuss how the patient transport problem can be modeled as a MIP. Subsequently, the model is modified to incorporate the required updates when a previously unknown transport is requested. We then describe how to incorporate Covid-19-related requirements, including disinfection time and the goal of separating known Covid-19 transports from other requests as far as possible. In Sect.5, we elaborate on algorithmic methods to improve the running time for our models’ solving process and evaluate the methods by using the available historical data. In particular, we compare our methods to an implementation simulating the current scheduling practice at the ILS. Finally, in Sect.6, we discuss our results and provide some ideas for future research. 2 Literature review Since the VRP generalizes the traveling salesperson problem (TSP), it is naturally NP-hard. Before we present our chosen approach to model the VRP in Sect.2.5, we present an overview of research about VRPs in the literature. Further, we present and discuss some literature concerning transport problems in healthcare that have been discussed in the context of mathematical optimization. Finally, we classify our problem depending on these findings. 2.1 Vehicle routing problems The VRP presented in Dantzig and Ramser (1959) is a generalization of the wellknown TSP: Given an (un-)directed graph, and given a fixed nonnegative integer m and a fixed node, the question is whether the given graph can be partitioned into at most m Hamiltonian cycles that share only the given fixed node. The interpretation given in Dantzig and Ramser (1959) is that the given number m is the number of available vehicles to carry out (petrol) deliveries such that each customer is served exactly once by exactly one vehicle and that each vehicle starts and ends its tour at a depot (which corresponds to the given fixed node). For a general overview of vehicle routing problems, we refer to Vigo and Toth (2014). In this work, an overview of different methods for modeling and solving variations of vehicle routing problems 570 D.Adelhütte et al. and its modifications are presented and evaluated, including branch-and-boundalgorithms, branch-and-cut-algorithms, set-covering-based algorithms and heuristic methods, among others. It is also possible to model VRPs as MIPs. This is also our solution approach since we use state-of-the-art software in our numerical study. In Sect.2.5 we justify this choice in more detail. The works of Cordeau etal. (2007a, b) present an overview of different problem classes of vehicle routing problems. Two generalizations are the vehicle routing problems with time windows and the vehicle routing problem with pick-up and delivery. The latter one usually contains time windows, so one mostly omits the pick-up and delivery part. In our work, we use the VRPGTW which was introduced in Ibaraki etal. (2005). Contrary to the vehicle routing problem with time windows, the bounds on target times can be soft, i.e., their violation is penalized, or hard, i.e., the corresponding constraints need to be satisfied. Vidal etal. (2020) discusses many current VRP extensions, such as service quality, equity, and working hours, among others. Another generalization discussed in Ibaraki etal. (2005) is the diala-ride problem. This problem aims to model transports of passengers. Thus, human factors like their satisfaction must also be included. For an overview we simply refer to Ho etal. (2018). VRPs are either static or dynamic and either deterministic or stochastic. In a static VRP, all transports are known beforehand, while in a dynamic one they can change over time. Further, new transports can be requested over time. The distinction between deterministic and stochastic VRP depends on whether some data is uncertain. 2.2 Dynamic VRPs Dynamic VRPs require more sophisticated solution techniques, while static VRPs are, in comparison, usually easy to solve by applying state-of-the art MIP approaches. Berbeglia etal. (2010), Pillac etal. (2013), Bektas etal. (2014) present overviews of dynamic VRPs. The first consists of a collection of problems while the latter focuses on the distinction between periodic and continuous solving methods. A periodic solving method re-optimizes the problem after a certain (fixed) time period or as soon as new data is available while a continuous solving method is performed throughout the whole day. Another overview from Psaraftis etal. (2016) further introduces a new classification scheme for dynamic VRPs that consists of eleven criteria, for example the type of the objective function (i.e., whether one minimizes costs, distances, travel times, etc.), the fleet size, the type of time constraints and the solution method. Another solution method for dynamic VRPs is given in Ferrucci etal. (2013). There, the authors introduce dummies to precautionarily schedule ad hoc transports to areas where new requests are likely to occur. Further, there are different possibilities, how currently waiting vehicles can behave to handle incoming transport requests better. The work of Mitrović-Minić and Laporte (2004) describes different waiting strategies, namely the drive-first strategy where a vehicle leaves its current location as soon as possible. In contrast to the drive-first strategy, for the wait-first 571 Minimizing delays ofpatient transports withincomplete… strategy, the vehicle waits as long as possible. Further, two mixtures of both are introduced. Due to the stochastic probability distribution for new customers’ location, heuristics focusing on the waiting location are considered. 2.3 Stochastic VRPs In addition to dynamic VRPs, uncertainties add another layer of complexity. Stochastic VRPs can consist of different types of uncertainties. The work of Soeffker etal. (2022) summarizes where those may occur: The main source of uncertainty is demand, which refers to the number of requests, as well as where, if, and when they will occur. Furthermore, the environment may be uncertain, such as fluctuating travel times due to traffic. Finally, one may have uncertain resources, which means that the availability of, for example, vehicles and drivers is not guaranteed. Further overviews over stochastic VRPs can, for example, be found in Berhan etal. (2014), Oyola etal. (2018). The work of Oyola etal. (2017) focuses on solution methods for these problems. Bertsimas and van Ryzin (1991) is one of the first works discussing dynamic and stochastic VRPs. There, the authors propose heuristics to solve these more difficult problems. Also, Flatberg etal. (2007) distinguishes stochastic, dynamic and dynamic/stochastic VRPs. They further mention that it is helpful to gather patient data to determine a probability distribution. Similarly, the more current survey Ritzinger etal. (2015) investigate these three types of VRPs. Stochastic VRPs are frequently solved with Markov Decision Processes (MDPs). A general MDP has four components: states, actions, transitions, and rewards. For VRPs, each state contains the vehicle(s)’ current location, arrival time at the current node, and the status of all customers. An action assigns times to customers, and transitions are used for changing from one state to the next after an action is chosen. The reward is determined by how the problem is defined and what specific goals are set, e.g. minimizing travel times, maximizing the number of visited customers or balancing the workload between drivers. Unlike general MDPs, route-based MDPs explicitly model route plans as sequences of possible future actions, thereby redefining the feasible action space. This enables real-time decisions that directly adjust and optimize future routes. This also implies that states in route-based MDPs now include routes. Ulmer etal. (2017) shows that MDP and route-based MDP formulations are equivalent when using a slightly restricted formulation of the Bellman equation. Kim etal. (2005) and Kim etal. (2016) apply MDPs to solve stochastic VRPs with uncertain travel times. The first uses heuristics and real-time data, while the latter deals with nonstationary stochastic travel times and attempts to determine a probability distribution. Furthermore, Kim etal. (2005) optimizes driver attendance times and vehicle coverage, which are fixed in our case. In both cases, the customers and their demands are known in advance. Further, Zhang etal. (2021), Wang etal. (2021) and Schilde etal. (2014) solve stochastic versions of a dial-a-ride problem with uncertain travel times. In Secomandi and Margot (2008), the authors assume that they have complete information about all customers, with the exception of stochastic demands. As a 572 D.Adelhütte et al. result, due to limited capacity, vehicles may be required to return to the depot during replanning. MDPs and heuristics are used to solve the problem for a single vehicle with known probability distributions. There is also some work to be done to address the uncertainty concerning whether multiple requests will occur at all. In Ulmer etal. (2020), possible customer locations are known beforehand. Additionally, the number of requests is available. Yu etal. (2019) discusses vacant taxi routing, which involves deciding where taxis that are not currently transporting passengers should drive or wait. In this case, customer requests may appear from any position. This is handled by clustering positions into zones, resulting in a discrete action space. Both works use MDPs to solve stochastic VRPs. Thomas (2007) also solves a dynamic and stochastic VRP with unknown requests. The author pays special attention on the question where vehicles should wait. Other solution methods feature combinations of MDPs with rolling horizon approaches Margolis etal. (2022) and genetic ant colony algorithms Hanshar and Ombuki-Berman (2007). Many applications can be modeled as order picking and delivery problems. In Zhang etal. (2017, 2019), the authors consider delivery for business-to-costumer and online-to-offline supermarkets, respectively. A more general work can be found in Chen and Xu (2006) where a VRP for minimizing the driven road distance is modeled and evaluated on benchmark instances. In contrast to their approach, we minimize delays and not a road distance. In Gendreau etal. (1999), the main question is to decide whether ad hoc transports should be accepted or rejected what is not possible in healthcare. During the whole time period, the problem is optimized continuously. Kok etal. (2012) introduce a new model, namely a VRP with timedependent travel times. Varying travel times, such as those caused by traffic jams, are taken into account in this specific model. The travel time is determined by the origin and destination, as well as the requested departure time. By incorporating this information, the authors intend to enhance the reliability of planned routes. In Bertsimas etal. (2019), the authors apply the solution of snapshots to handle another dynamic VRP, namely scheduling ad hoc transports for online taxi routing. In our work, we consider a dynamic and deterministic VRP. 2.4 Transport problems inhealthcare There is also a lot of work that model passenger transporting problems that occur in healthcare as vehicle routing problems. The work of Hulshof etal. (2012) is a taxonomy of healthcare decisions and thus, a good overview. In Beaudry etal. (2010) and Kergosien etal. (2011), the patient transport problem within a hospital is considered. In the former one, they assume that the hospital is one building, while in the latter one, the buildings of the hospital are spread over the whole city—in this specific example, in Tours (France). A static version of the VRP for the patient transport problem is discussed in Melachrinoudis etal. (2007), an example for a work about rescue transports is Gendreau etal. (2001). Important work in the field of patient transport in the European area is described in van den Berg and van Essen (2019), 579 Minimizing delays ofpatient transports withincomplete… transports of Tplan are carried out, transports of Tad hoc need to be incorporated and the schedule usually has to be updated. For transports T∈Tsemi , no target time is yet defined. When one treats them as ad hoc transports, the dispatcher ignores them until their target time becomes known. Alternatively, the estimated target time test T could guide scheduling, treating the transport as a plannable transport in Tplan . If the actual target time differs, the dispatcher adjusts accordingly. If earlier, it is treated ad hoc; if later, the vehicle waits. However, since estimated times may vary significantly, a maximum waiting time is introduced. If a vehicle exceeds this waiting time, it is reassigned, treating the transport as ad hoc and deleting the dummy transport. This is formalized as follows: Definition 7 (Dummy transport) A transport T is called a dummy transport, if i) T∈Tsemi , i.e., it is semiplannable, ii) its target time is estimated with test T ≥ 0 , and, iii) it has a waiting time wT≥0 after which T will be treated as an ad hoc transport. The set of dummy transports is denoted as Tdummy . To estimate the target time, historical data or medical expertise can be used. An example for a scenario where dummy transports are applicable in practice in our real-world example are return trips from dialysis. We come back to this in Sect.4.2.1. This concludes the discussion of the patient transport problem. In the following section, we model the specific optimization problems and describe how they can be solved, also when incorporating semiplannable and ad hoc transports. 4 Mathematical optimization The patient transport problem described in the previous section is now modeled as a VRPGTW. This type of modeling has proved to be the most appropriate for our application’s practical requirements and standards as discussed in Sect. 2.5. We begin by modeling the plannable patient transport problem in Sect.4.1. Then, we extend this formulation for semiplannable and ad hoc transports in Sect.4.2.1 before we elaborate on the modeling of requirements of the Covid-19 pandemic in Sect.4.2.2. 4.1 Modeling thepatient transport problem asaVRPGTW To model our problem, we use the VRPGTW formulation from Sect.2.5. Assume we have n plannable transports (Definition1) from Tplan that have to be scheduled 580 D.Adelhütte et al. with m vehicles. We begin by explaining how the plannable model is created. The parameters of the VRPGTW are defined as follows: • N∶= {1, …,n} is the set of plannable transports. Each node i corresponds to transport Ti . The depot is denoted as node 0 and has a copy n+1 . The vehicles start at 0 and end their trip at n+1 . This avoids modeling issues and does not have other implications. • K∶= {1, …,m} is the set of available vehicles. • AN∶= {( i , j )∈ N × N ∶ i≠j } is the set of arcs ‘between two transports’. An arc (i,j)∈AN is used if and only if a vehicle carries out Tj directly after transport Ti . • AK∶= {(0, j)∶j∈N}∪{(i,n+1)∶i∈N}∪{(0, n+1)} is the set of arcs from the depot to all j∈N , from each i∈N to its depot and the arc (0, n+1) that is used by a vehicle if it does not transport any patients. • The digraph is G∶= (V,A) with V∶= N∪{0, n+1} and A∶= AN∪AK . • For each i∈N , ti is the target time of transport Ti . • For k∈K , [ak,bk]⊆ℝ+ denotes the shift of the driver(s) of vehicle k. • For i,j∈N , 𝜏i,j≥0 denotes the time a vehicle needs to reach Oj after starting transport Ti , i.e., the sum of di and the travel time disti,j≥0 from Di to Oj . • For j∈N , 𝜏k 0,j > 0 denotes the travel time for vehicle k∈K to reach Oj from its depot and 𝜏k j,n+1 > 0 denotes the travel time for vehicle k∈K to reach its depot from Dj . We set 𝜏k 0,n+1 ∶= 0 for all k∈K . We need the superscript k here, since there can be multiple depots. The variables of our model are: • xi,j,k∈{0, 1} is the binary variable that indicates whether vehicle k travels from node i to j, i.e., whether vehicle k carries out transport Tj directly after it carries out transport Ti . • For all i∈N , yi∶= yi,k∈ℝ+ denotes the time when vehicle k arrives at node i, i.e., when transport Ti starts. We only need one variable for each transport Ti as at most one vehicle serves it. • y0,k∈ℝ+ denotes the time when a vehicle starts its trip and yn+1,k∈ℝ denotes the time when it ends its trip. Here we need a variable for each vehicle. As a choice of an objective function that evaluates the quality of the schedule adequately, we use piecewise linear measures of quality that we will linearize whenever necessary. To simplify notation, we thus introduce the following concept for penalty weights: Definition 8 (Penalty weights) Let Λ be a set of variables. A penalty weight is a parameter 𝛾∈ℝ that is used to penalize all variables 𝜆∈Λ . The penalty set Γ contains the tuples (𝛾,Λ) . Using this representation, an objective function has the form 581 Minimizing delays ofpatient transports withincomplete… Since our goal is to create a fair schedule, we attempt to minimize the maximum delay throughout the day. To this end, we introduce a penalty parameter 𝛾max >0 . Further, we minimize the individual delays (possibly weighted by 𝛾i ), yielding the (piecewise linear) measure of quality as we defined it in Definition4. Objective function(3) can be easily linearized, as one can see in the Objective function (4a) and Constraints(4h), (4i) of the following MIP where our (linearized) instance is formulated: We can represent the current penalties for the delays using the penalty weights of Definition8 by so we do not state the delays explicitly in the following. ∑ (𝛾,Λ)∈Γ ∑ 𝜆∈Λ 𝛾⋅𝜆 . (3) 𝛾 max ⋅max{0, y1−t1,…,yn−tn}+ ∑ i∈N 𝛾imax{0, yi−ti } (4a) min 𝛾max ⋅Δmax + ∑ i∈N 𝛾iΔ i (4b) s.t Constraints (1b)−(1e), (4c) yi+𝜏i,j−yj≤Mi,j(1−xi,j,k)∀k∈K,(i,j)∈AN, (4d) y i,k+𝜏 k i,j −yj,k≤Mi,j(1−xi,j,k)∀k∈K,(i,j)∈AK , (4e) ak ≤ y0,k ∀ k ∈ K, (4f) yn + 1,k≤bk∀k∈K, (4g) ti ≤ yi∀i∈N, (4h) yi− t i ≤ Δi∀ i ∈ N , (4i) 0 ≤ Δi ≤ Δmax ∀i∈N, (4j) xi,j,k∈{ 0, 1 }∀k∈K , (i , j)∈A, (4k) yi , k ≥ 0∀i∈N,k∈K. Γ ∶= {( 1, {Δ i ∣i∈N} )} ∪ {( 𝛾 max ,{Δ max } )}, 582 D.Adelhütte et al. The remaining constraints of Model(4a) that are not directly taken over from the general formulation model the following: Constraints(4e) and (4f) are hard bounds that ensure shift times are met and feasible schedules as introduced in Definition2 are obtained. Constraint(4g) prevents a vehicle from starting a transport before its target time. With the solution of Model(4a), we can consequently establish a feasible schedule: If xi,j,k=1 then vehicle k carries out transport Tj after carrying out transport Ti . Thus, from the optimal solution (x∗ ,y∗) , it is possible to reconstruct the path of vehicle k from 0 to n+1 to the form (vk1,…,vks), where s∈ℕ denotes the number of transports for the respective vehicle. Along with the optimal arrival times y∗ , an optimal schedule is obtained. 4.2 Extending theplannable formulation So far, we have modeled the problem of finding optimal schedules for transports for which all information is known, i.e., plannable transports. This model is now extended to handle transports with incomplete information, including ad hoc transports. In addition, using the Covid-19 pandemic as an example, we propose and model how to treat the situation of endemic diseases, or, to be more precise, when a patient is at least suspected to be infected with a highly infectious disease. We begin by introducing labels for transports: Definition 9 (Transport labels) A (transport) label is a function 𝜙∶T plan ∪T semi ∪T dummy ∪T ad hoc → { 0, 1 } that indicates whether a transport T∈Tplan ∪Tsemi ∪Tdummy ∪Tad hoc fulfills some property. Multiple labels can be collected in a label set Φ . Label information may include whether a transport involves infectious diseases, needs to fulfill certain priorities, or the question whether certain equipment is needed. Another example can be the information about the type (plannable, semiplannable, ad hoc, dummy) of a transport. Recall that all types of transports are defined in Definitions1, 5, 6 and 7. A similar set can also be introduced for vehicles, e.g., for indicating whether certain equipment is available. In this case, only such vehicles can handle transports that need this equipment. Using the definition of labels from Definition9, we can introduce additional constraints for the patient transport problem on an abstract level. These constraints can be hard or soft, the latter using penalty weights and additional variables. Now we are presenting different modeling possibilities that allow us to extend Model (4a) in various ways. Let Φ be a set of labels. One possibile extension is to limit the number of transports per vehicle with a label 𝜙∈Φ to a fixed number a∈ℕ . This can be modeled by (5) ∑ (i,j)∈A xi,j,k⋅𝜙(Ti)≤a∀k∈K . 583 Minimizing delays ofpatient transports withincomplete… If a specific label is not of importance then we can just omit it. With a=1 , each vehicle can handle at most one transport of a specific type. Let 𝜙1,𝜙2∈Φ and assume that it is not allowed to handle a transport j with 𝜙2(Tj)=1 immediately after a transport Ti with 𝜙1(Ti)=1 . This is represented by adding constraints to Model(4a). Naturally, it is also possible to set 𝜙1=𝜙2 and, thus, prohibit the handling of similar transports after another. 4.2.1 Incorporation oftransports withincomplete information We now look at how to modify the plannable formulation, first to handle semiplannable transports, and then to handle ad hoc transports. Therefore, we apply the strategy for the operational phase that have been proposed in Sect.3. In fact, similar to the planning phase, this means creating or extending the VRP formulation and solving the resulting MIP. Whenever possible, we estimate the target times of semiplannable transports and treat dummy transports like plannable transports. In other words, in Model(4a), N is modified such that the nodes corresponds to the transports in Tplan ∪Tdummy and the extended VRP is solved. To take the data-driven nature of dummy transports into account, we establish the following rules: Firstly, for the maximum delay as a measure of quality, delays of dummy transports are not taken into account, i.e., only the delays of the initial plannable transports are relevant. Secondly, the individual delay of dummy transports is a quality of measure and is weighted by some parameter 𝛾i for Ti∈Tdummy . Thus, after incorporating the dummy transports, Objective (4a) of Model(4a) is With the scheduling of Tplan , the planning phase is completed. In addition to semiplannable transports, the dispatchers usually need to incorporate ad hoc transports. They are called whenever such a transport has to be scheduled at a certain time 𝜎 on the fly. With a schedule already in place, some vehicles are already on their tour. Therefore, we need to reoptimize our schedule. We now introduce some notation. Let 𝜎∈ℝ+ be a given point of time. The set V𝜎⊆V denotes the nodes that correspond to transports known before an ad hoc transport is requested at 𝜎 . Using the optimal solution (x∗ ,y∗) of Model(4a) at 𝜎 , the set denotes the schedule that is carried out at 𝜎 . If no ad hoc transports have been requested before 𝜎 , we have P𝜎 =P0 , i.e., the solution of the plannable model. Transports already in operation are not changed. They are elements of the set (6) 𝜙1(Ti) ⋅ 𝜙2(Tj) ⋅ xi,j,k=0∀k∈K,(i,j)∈A. (7) 𝛾 max ⋅Δmax + ∑ i∈N, T i ∉T dummy 𝛾iΔi+ ∑ i∈N, T i ∈T dummy 𝛾imax{0, yi−test i} . P 𝜎∶= { (i,k,y∗ i)∈V𝜎×K×ℝ+∣∃j∈V𝜎∶x∗ i,j,k=1 } 584 D.Adelhütte et al. that contains all transports where the vehicle is either on the way from D T i to O T j or has started or finished transport Tj . If an ad hoc transport is requested for some time point 𝜎 then transports of P𝜎 fixed are not changed while the transports in P𝜎⧵P𝜎 fixed are removed of the schedule. This ensures that vehicles not carrying out transports at 𝜎 are available again since the schedule after 𝜎 was deleted. Thus, every transport scheduled after 𝜎 , including the ad hoc transport, can be rescheduled by solving Model(4a) with the additional restriction that all transports in P𝜎 fixed are unchanged. Therefore, we first update G by including the new ad hoc transport in V𝜎 and A𝜎∶= {(i,j)∈A∶i,j∈V𝜎} , respectively. Thereupon, to ensure that fixed transports are not changed, we introduce two additional constraints to Model(4a), namely and If we have dummy transports, we need to be cautious about their waiting times since, whenever a transport T∈Tdummy exceeds its waiting time, it is deleted and treated as an ad hoc transport (once requested). Then, in order to use the vehicle that should have handled T, we reoptimize our schedule. 4.2.2 Adjusting themodel duringtheCovid‑19 pandemic To decrease the risk of infections for patient transports during the Covid-19 pandemic, it is desirable that transports are distinguished into two types, depending on whether a patient is (suspected to be) infected with Covid-19 or not, resulting in an additional property of transports. From now on, we refer to patients with a suspected infection with Covid-19 as ‘infected’ as well. In the following, we will discuss some ideas how such Covid-19 transports can be handled and proceed with a mathematical formulation how minimizing the risk of infections can be incorporated in our Model(4a) using Definition9. There are different possibilities to decrease the risk of infections. In practice, when dealing with dangerous infectious diseases like Covid-19, the staff needs to wear protective clothing and the vehicle is disinfected after every transport. In addition to these protective measures, it can be helpful to minimize the number of changes from a Covid-19 transport to a non-Covid-19 transport. This will reduce the number of contacts between patients and staff and thus the risk of infection even further, even if vehicles are disinfected after each transport. We present two different approaches: reducing the number of vehicles that are allowed to carry infected patients and limiting the number of infected patients per vehicle. In addition to the goal of reducing the number of changes, these approaches have been developed due to the fact that the supply of protective clothing is limited and therefore should be distributed as efficiently as possible. Nevertheless, in both P 𝜎 fixed ∶= { (i,k,y∗ i)∈P𝜎∣∀j∈V𝜎∶x∗ i,j,k=1⇒𝜎≥y∗ j,k−disti,j } (8) x i , j , k = x ∗ i,j,k∀( i,j,k,y ∗ i)∈P𝜎 fixed (9) y j=y ∗ j ∀(i,j,k,y ∗ i )∈P 𝜎 fixed. 585 Minimizing delays ofpatient transports withincomplete… cases, we still aim to minimize the delays for patients. This is incorporated by using different penalty parameters for, e.g., the delay and the number of changes in the objective function. The additional time for disinfection and changing of clothes needs to be taken into account when establishing schedules. This is easily done by increasing the duration di of each transport by a constant. Thus, it is not necessary to introduce additional constraints to Model(4a). To indicate, for which transports additional Covid-19 requirements are necessary, we introduce a label c∶T → {0, 1} where T⊆Tplan ∪Tsemi ∪Tdummy ∪Tad hoc . A value of 1 corresponds to a patient’s infection. This label is used to create additional constraints. For sake of notation, we write ci instead of c(Ti) . Furthermore, we write c , meaning a transport is not a Covid-19 transport, with ci=1−ci for all Ti∈T . To model travels from and to the depot adequatly, we further define c0∶= cn+1∶= 0 and, consequently, c0∶= cn+1∶= 1 . 4.3 Minimizing thenumber ofchanges To formalize minimizing the number of changes, we use the labels c and c with Constraint(6): Equation(10) models that no vehicle is allowed to carry a non-Covid-19 transport directly after a Covid-19 transport. We do not wish to prohibit all changes because otherwise, the solution quality w.r.t. the delay would decrease or we would not able to create feasible schedules at all. Therefore, we use a soft constraint. Instead of minimizing the number of changes, we introduce the additional variable 𝜆change i,j,k ∈{0, 1 } for (i,j)∈AN , k∈K and modify (10) accordingly: Now the variables 𝜆change i,j,k are penalized using 𝛾change and we modify Γ by appending the tuple ( 𝛾change,{𝜆 change i,j,k ∣(i,j)∈AN,k∈K }) . 4.4 Approach 1: Minimizing thenumber ofCovid‑19 vehicles An option to reduce contact between uninfected and infected persons is dividing the vehicle fleet into different pools, i.e., one pool of vehicles that only handle Covid-19 transports and one pool for non-Covid-19 transports. It is possible to additionally use so-called floater vehicles that are allowed to handle both types of transports to maintain some degree of flexibility. Here, the protective clothing can be distributed among the Covid-19 vehicles and the floater vehicles so that no vehicle is carrying it needlessly. The corresponding constraint is (10) ci ⋅ cj ⋅ xi,j,k=0∀k∈K,(i,j)∈AN. (11) c i⋅cj⋅xi,j,k=𝜆 change i,j,k ∀k∈K,(i,j)∈AN . (12) ci ⋅x i,j,k ≤𝜆 vehicle k ,∀k∈K,(i,j)∈A . 586 D.Adelhütte et al. Here, for k∈K , 𝜆vehicle k are new binary variables. They are penalized using 𝛾vehicle k , i.e., we update Γ ←Γ∪(𝛾 vehicle ,{𝜆 vehicle k ∣k∈K }) . 4.5 Approach 2: Limiting thenumber ofCovid‑19 transports foreach vehicle Another approach to incorporate Covid-19 requirements is to distribute protective clothing equally among all vehicles. In this case, every vehicle is able to serve a limited number of Covid-19 transports before it needs to return to its depot to obtain new sets of clothing. An advantage of this approach is that each vehicle is able to carry out Covid-19 transports with less delay than when separating the fleets completely. Nevertheless, this modeling approach might increase the number of switches between infected and non-infected patients in vehicles. To implement the limitation of protective clothing, we use a tuple of a penalty weight and integer variables 𝜆 clothing ∈ℕ |K| 0 , namely (𝛾clothing,Λclothing) where Λ clothing ∶= {𝜆 clothing k ∣k∈K } . The objective function is increased by the penalty value every time a vehicle has to return to the depot to obtain new clothing. Thus, for all k∈K , we introduce the constraint where 𝛼∈ℕ is the amount of sets of clothes per vehicle. Inequality (13) is Constraint(5), with the difference that not every exceedance of 𝛼 is penalized. Instead, every time 𝛼 is reached again, we increment the variable 𝜆clothing k by one. In our model, it is not possible that vehicles return to the depot during their shift, and, thus, we prohibit this by choosing the penalty for this scenario quite high. This means that a vehicle only exceeds its limit when it is not avoidable, i.e., if there are more than 𝛼|K| Covid-19 transports. However, this never happens in our numerical study. This concludes the modeling of the patient transport problem. In the next section, we present and discuss our numerical experiment and show the efficiency of our plannable approach and its extensions. 5 Implementation andnumerical results In this section, we provide details on the implementation as well as the insights that can be obtained from the optimized schedules. The models presented in the earlier section are solved via state-of-the-art available global MIP solvers like Gurobi (Gurobi 2021) or SCIP (Bestuzheva etal. 2021) which are applying solution approaches for MIPs, cf. Land and Doig (2010), Wolsey (2020) or Wolsey and Nemhauser (1999). The rationale behind the usage of available solvers is to enable possible transfer of the developed approaches to the practitioners so that they can also maintain the program in the future. Moreover, using a MIP formulation, we are able to incorporate the extensions for pandemic requirements. (13) ∑ (i,j)∈A ci⋅xi,j,k≤𝛼(1+𝜆 clothing k ) 587 Minimizing delays ofpatient transports withincomplete… All models and algorithms were implemented in Python 3.7.7. To solve the MIPs, we used Gurobi 9.0.2 on the NHR@FAU clusters with Intel Xeon E3-1240 v5 or Intel Xeon E3-1240 v6 CPUs, respectively. Each of these has four cores with 3.5 GHz each and a RAM of 32 GB. We start with the description of a simulated reality to evaluate our schedules in Sect.5.1. Thereupon we present some heuristic approaches in Sect.5.2 and, finally, we evaluate the performance of our approach in Sect.5.8. There, we also cover the incorporation of semiplannable transports and the extensions to cover issues and problems for patient transports during the Covid-19 pandemic. For all numerical results, we use historical data from 2019 to mid-2021, provided by the ILS that covers regions in Middle Franconia. In practice, this area is divided into different counties, and each one is scheduled individually, with a transport T assigned based on its origin location OT . With our optimization strategy, we proceed in a similar manner. Counties are different in size and population density. We have rural counties with a low population density in comparison to their size, as well as urban counties with a high population density, what causes a higher number of transports and, thus, more difficult instances. We optimize each day separately because they do not influence each other as during the night almost no transports are requested. Unless otherwise mentioned, we specify a time limit of 60min. We will elaborate on the time limit in Sect.5.8. We must overcome some issues with the available historical data: On the one hand, some transports are stated incorrectly, such as missing timestamps or locations. Missing data have been handled during preprocessing by either estimating travel times using a distance matrix or deleting the corresponding transports if too much data were missing. For the estimation of travel times, we refer to Leithäuser etal. (2022). On the other hand, there are cases where the dispatcher needs to make decisions on the fly that could have not been planned beforehand. For example, vehicles, can be lent between different counties. Technically, each vehicle is assigned to a specific county but in exceptional circumstances and if necessary, this can be relaxed. Further, the distinction between patient and rescue transports can be neglected when absolutely necessary. Moreover, if a transport’s delay is excessive, it can be postponed for another day. We do not consider any decisions out of the set of rules or usual decision makings in our model since we are not in a position to make them. In practice, the set of feasible schedules can possibly be improved by incorporating expert decisions. 5.1 Implementation ofasimulated reality For the reason mentioned above, we cannot compare our schedules directly to the ones in the historical data. So, in order to evaluate the optimized schedules, we require a baseline solution. To ensure the most accurate comparison, we have implemented a simulation of the ILS’s decision making that operates similarly to the practice. They apply a greedy approach: Every time a transport is necessary, the vehicle that would arrive 588 D.Adelhütte et al. the fastest is assigned to it. However, vehicles currently involved in a transport cannot be used, and shift times need to be respected whenever possible. For the baseline implementation, we thus sort all plannable transports by their target time given in the historical data. Then the vehicles are assigned in that order: For each vehicle, we calculate the earliest time it could reach the requested transport’s origin by adding the travel time to the time it is expected to become available, which is either the start of its shift or the expected end of the previous transport. Furthermore, we check whether the vehicle could reach its depot without violating its shift times using the estimated duration, i.e., expected travel times, of the transport. The vehicle that can carry out the transport request with the smallest delay is assigned to it. If there is more than one vehicle with minimal delay then the one with the shortest travel time is chosen. In the case that no vehicle can handle the transport without violating its shift times, we choose the vehicle with the smallest shift time violation. 5.2 Heuristic methods fortheMIP solver We present some algorithmic approaches for speeding up the MIP solution process for the arising models. This is necessary because, while conducting our numerical study (see Sect.5.8), we have realized that without any improvements, our solution approach is incapable of solving many instances to optimality. For the evaluation of the heuristic methods, we use a subset of real historical data, namely data corresponding to 59 days (January and February 2020) from two counties, for a total of 118 instances. The counties differ in size; the smaller one has about 100,000 residents, the larger one about 500,000. 5.3 Using aprimal heuristic The first heuristic we have implemented is a primal heuristic that aims to find good feasible solutions early in the MIP solution process. At every kth node of the branchand-bound tree within the MIP solver, we tentatively round a part of the optimal solution of the LP relaxation. In every feasible solution, the number of variables xi,j,k that are set to 1 is given by |K|+|V| . For a primal heuristic, all values for xi,j,k in the solution of the LP relaxation are sorted and a number of them are fixed in order to faster obtain a feasible MIP solution. Here, we have chosen the number of vehicles |K| and set the |K| greatest variables to 1. If a feasible solution is found by using this start solution then it is used for the following solving process. Otherwise, it is discarded. It is important not to fix too many variables as the solution may then become infeasible since we could, e.g., accidentally schedule two vehicles to the same transport. However, we also note that fixing too few variables will not speed up the solving process and that the respective values are based on empirical analysis. 595 Minimizing delays ofpatient transports withincomplete… working a shift at this time, so the average delay for these patients becomes very high. This continues with the transports starting shortly after 6am. As the morning shift times do not start earlier than 6am and they first need to drive to the origin of a transport, it is not possible to reach these patients without a delay. In general, the night shifts end at 6am. Thus, they can probably not handle these transport requests without risking shift time violations. A more detailed evaluation is given in Fig.6. The light gray area represents the total number of available vehicles over one year. For instance, at 4 am, there are 365 vehicles available, as each day there is one vehicle handling the night shift. The dark gray area indicates the level of vehicle utilization. This evaluation shows that the vehicles with earlier, i.e., morning shift times have to handle considerably more transports. Vehicles are working almost at full capacity at least until noon. Afterwards, less ad hoc transports are requested and the situation eases. This means that as soon as a vehicle becomes available, it will be assigned to some transport. As few vehicles are available at the beginning of a day, some transports cannot be handled on time. These delays then cause delays for later transports. This occurs because vehicles are occupied by earlier transports that are preferred as we minimize the maximum delay. In the afternoon, less transports are requested. Thus, more vehicles are available and the delays finally decrease. This data is important for practitioners as it highlights the critical periods of high vehicle utilization and the resulting delays. Understanding these patterns allows for better scheduling and resource allocation, ultimately improving transport efficiency and reducing delays. Fig. 6 Aggregated number of available and utilized vehicles over time 596 D.Adelhütte et al. 5.9.2 Examples forsemiplannable transports andfurther requirements This section contains some sample schedules for our modeling approach extensions from Sects.4.2.1 and 4.2.2. We have been unable to conduct a full numerical study due to a lack of data, but we were able to identify some exemplary days where our extensions worked well. For both, using dummy transports for semiplannable transports as well as incorporating Covid-19 requirements, we explain the problems with the given data before presenting some examples. 5.10 Using dummy transports forsemiplannable transports While trying to handle semiplannable transports (Definition 5) using dummy transports (Definition7), the following data issues have occurred: At the beginning of the optimization process, each transport T is assigned to the county of the origin location OT . Often, the destination DT is located in another county. In this case, patients have to be transported between different counties, causing outward and return trips optimized in different models. This leads to dummy transports that are not applied in the actual return trip. In practice, the dispatcher can assign such transports to the same county. Furthermore, in more recent data provided by the ILS, a type of dummy node is used for dialysis transports. As soon as a dialysis is requested, two transports are created, including the return trip on 23:59 on the same day. Its target time is corrected as soon as it becomes known. Thus, if a dialysis is created at least one day before, then it is a plannable transport but its return trip is not, although it is stated to be plannable in the data. Due to these reasons, we provide an example day where the incorporation of a dummy transport leads to a significantly better result. Example 1 (Advantages of using dummy transports) In Table2, one can see two schedules that have been established on an example day in 2019. Table2a is the current schedule shortly before 11:00. At 11:00, a new transport is requested. This transport is a return trip for a previous dialysis transport for which a dummy node has been created. The dummy node’s target time was estimated based on the duration of previous dialysis appointments at the same location, i.e., in the same hospital. The outward journey has ID 28 and the dummy node is denoted by d28. It is determined that the new transport with ID 20 corresponds to this dummy node. Thus, it is deleted and replaced by the new transport using the new information, i.e., the actual target time. Table2b shows the schedule created at 11:00. As can be seen, the vehicles allocated to the transports not contained in P𝜎 fixed for 𝜎= 11:00, have changed. This is due to the fact that the transport is requested a little later than expected and vehicle 7 is available at that time. The schedule shows that it finishes its previous transport 597 Minimizing delays ofpatient transports withincomplete… Table 2 A schedule before and after transport 20 has been replaced by its dummy node d28.The second dummy node, d24 for transport 24, does not correspond to a future transport and will thus not be replaced before the end of the day.The information about the return trip has become known at 11:00, all fixed transports are given below the line, so the remaining ones could be rescheduled. As can be seen, the delays remain the same for all transports. Note that there are relatively few transports in the afternoon as they are often ad hoc ones and thus are not known at this point. ID (i) ti kStart ( yi ) End Δi (a) Schedule before 11:00 28 06:45 0 06:45 07:52 0 4 07:30 13 07:30 11:57 0 24 08:00 0 08:00 08:33 0 23 08:00 6 08:03 11:01 3.8629 25 08:30 0 08:33 10:00 3.2262 11 08:45 7 08:45 09:46 0 6 09:00 5 09:40 10:02 4.2565 0 09:00 8 09:40 11:10 4.2565 26 09:45 10 09:45 11:01 0 2 09:45 7 09:47 10:37 2.0320 13 10:00 10 10:45 11:59 45.0436 3 10:00 1 10:33 11:46 33.8629 12 10:00 0 10:00 10:58 0.5156 14 10:00 5 10:14 10:56 14.6932 15 10:00 7 10:37 11:48 37.1338 21 10:00 10 10:05 10:43 4.8170 7 10:15 5 10:59 12:18 44.0412 16 10:30 0 10:58 11:44 27.8051 9 10:30 11 11:03 12:30 33.8629 18 10:40 10 11:23 12:22 43.1832 1 11:00 0 11:44 12:31 44.0945 d28 11:52 1 11:52 12:59 0 d24 12:33 10 12:33 13:08 0 17 15:30 2 15:30 18:21 0 (b) Schedule at 11:00 28 06:45 0 06:45 07:52 0 4 07:30 13 07:30 11:57 0 24 08:00 0 08:00 08:33 0 23 08:00 6 08:03 11:01 3.8629 25 08:30 0 08:33 10:00 3.2262 11 08:45 7 08:45 09:46 0 6 09:00 5 09:40 10:02 4.2565 0 09:00 8 09:40 11:10 4.2565 26 09:45 10 09:45 11:01 0 2 09:45 7 09:47 10:37 2.0320 13 10:00 10 10:45 11:59 45.0436 3 10:00 1 10:33 11:46 33.8629 12 10:00 0 10:00 10:58 0.5156 14 10:00 5 10:14 10:56 14.6932 15 10:00 7 10:37 11:48 37.1338 21 10:00 10 10:05 10:43 4.8170 7 10:15 5 10:59 12:18 44.0412 598 D.Adelhütte et al. at 11:48, the new transport is requested at 12:00 instead of the presumed 11:52. So, this vehicle can reach the origin of the return trip in time. The maximum delay in this example county is reduced by 20min when compared to the schedule created without dummy nodes. As a result, the total delay decreases. In this case, we only create one dummy node, which is later replaced, and, the penalty weight was set to 𝛾=0.5 for dummy transports. Taking this into account, this is a very positive result, and an even greater improvement can be predicted if more dummies are used whenever appropriate data is available. 5.11 Incorporating further requirements Now, we consider schedules when dealing with Covid-19 transports. The dispatcher does not have a special course of action in the Covid-19 pandemic. Instead, it treats transports of infected patients in the same manner as other transports. As a result, evaluating our extension from Sect.4.2.2 against the (simulated) reality is no longer useful, because explicit minimization of infection risks is not taken into account. Instead, we aim to obtain new insights into how the pandemic requirements could be handled. The first example shows how a computed pool division can look, while the second one attempts to compare our two different approaches discussed in Sect.4.2.2 to handling Covid-19 transports. In a pool division, the first and second pools contain vehicles that transport either only Covid-19 patients or no Covid-19 patients at all. Floater vehicles make up a third pool. We evaluate the results and devise a strategy for implementing this pool division in practice. Example 2 (Distribution of vehicles in an optimized pool division) We have collected all information about transports that took place in some county between 1st January, 2020 and 30th June, 2021. The percentage of Covid-19 transports is quite low, as days with very few (or even zero) transports are included. In Table3, the pool division aggregated over all Tuesdays is given. Floater vehicles are mostly used in the earlier shifts. Later in the day, it is often possible to use Covid-19 Table 2 (continued) ID (i) ti kStart ( yi ) End Δi 16 10:30 0 10:58 11:44 27.8051 9 10:30 11 11:03 12:30 33.8629 18 10:40 9 11:23 12:22 43.1832 1 11:00 0 11:44 12:31 44.0945 20 12:00 7 12:00 13:10 0 d24 12:33 0 12:33 13:08 0 17 15:30 2 15:30 18:21 0 599 Minimizing delays ofpatient transports withincomplete… vehicles. This might be caused by a higher number of transports in the morning, as discussed in Sect.1. We can gain an intuition which vehicles are a good choice for fixed Covid-19 vehicles using such tables. Depending on the number of Covid-19 transports on one day, some of these vehicles should be assigned to the Covid-19 vehicle pool. Similar peculiarities are obtained for different combinations of counties and weekdays. Because the exact distribution of transports, i.e., how many infected patients should be transported, is not known in advance, it is helpful to decide on the number of vehicles for each pool depending on the current number of Covid-19 cases. We assumed previously in Sect.1 that these numbers can have a high correlation. Furthermore, it can be helpful to hold an additional floater vehicle in reserve to allow for any discrepancies. We now compare the two options for handling Covid-19 transports that have been discussed in Sect.4.2.2. In total, there are little data containing a high percentage of Covid-19 transports. Thus, we consider an example that yields the same maximum and total delay for both heuristic approaches, but the transports are handled very differently depending on the approach used. We will discuss these differences concerning the vehicle fleet. Example 3 (Comparison of the approaches for handling Covid-19 transports) On our example day in April 2020, 45 transports are requested, 17 of which are for Covid-19 patients. Semiplannable transports are treated as ad hoc transports. For the second approach, limiting the number of Covid-19 transports per vehicle, we assume that each vehicle has two sets of protective clothing. In our example, there are 17 vehicles available. In both schedules, 15 of them are used. In particular, both Table 3 Optimized pools for vehicles in one example area and the example shift times for Tuesdays. For each shift time, the number of handled transports, as well as the percentage of the allocation to each pool are given Shift time Number of Number of vehicles Covid-19 transports (%) Non-Covid vehicles (%) Floater vehicles (%) 06:00–14:00 1 189 2.9 94.2 2.9 07:00–15:00 1 191 1.5 91.2 7.3 08:00–16:00 1 161 2.9 90.0 7.1 08:30–16:30 1 135 1.5 93.9 4.6 09:00–17:00 2 237 0.8 95.2 4.0 10:00–18:00 2 128 4.6 94.3 1.1 10:30–18:30 1 119 2.9 97.1 0.0 11:00–19:00 1 37 6.7 93.3 0.0 14:00–22:00 1 69 7.3 90.9 1.8 15:00–22:00 1 14 9.1 90.9 0.0 16:00–24:00 1 20 10.5 89.5 0.0 22:00–06:00 1 9 0.0 100.0 0.0 600 D.Adelhütte et al. approaches use the same vehicles. Those with a shift early in the morning are not required because no transport is requested. If we minimize the number of Covid-19 vehicles used, three of the fifteen vehicles are Covid-19 vehicles, with five additional vehicles serving as floater vehicles. There are four Covid-19 and six floater vehicles in the other case. Because the number of transports it can handle is limited, a larger pool is required (and not penalized). In fact, when minimizing the number of Covid-19 vehicles, some Covid-19 and floater vehicles carry out at least three Covid-19 transports, which is hardly penalized when distributing the clothing equally. One thing that stands out in both schedules is that every vehicle that transports any infected patient ends its shift with all transports of infected persons. As a result, the penalty 𝛾change is never applied. The fact that this is possible with both approaches and also results in a relatively short delay is a positive result in terms of reducing infection risks. The longest delays occur later in the evening and cannot be avoided even if we do not include any Covid-19 requirements aside from increasing transport duration. This is due to a lack of available vehicles at the same time. To summarize, both approaches have advantages and produce similar results especially when the number of Covid-19 transports is relatively low in practice. For example, the amount of protective clothing available may influence the dispatcher’s approach. As this number grows, the need to consider this limitation diminishes and the dispatchers’ focus may shift to minimizing contact between infected and noninfected patients and drivers. Another possibility is to combine both approaches, distributing protective clothing to all vehicles but providing more to those that are likely to have more Covid-19 transports. A fleet division, such as the one previously mentioned, could be useful in this regard. 6 Conclusion andfuture research In this work, we have proposed a solution approach for scheduling patient transports that are not rescue transports. Information about these transports can be incomplete and may only be partly known several hours before they are required. Our objective is minimizing the delay for patients in a fair manner while respecting shift times. We apply a VRPGTW formulation that can then be solved by state-of-the-art MIP solvers. We implemented the MIP formulation for the cases of full and incomplete information. We classify required transports into plannable transports (full information), semiplannable transports (almost full information but the target time is unknown) and ad hoc transports (no information about the transport at all). Ad hoc transports are incorporated by an iterative algorithm that solves Model (4a) every time that full information about a transport becomes known. Semiplannable transports can, on the one hand, be treated like ad hoc transports or, on the other hand, by introducing dummy transports with an estimated target time. When using the second approach, they are treated like plannable transports. We have compared our modeling approach 601 Minimizing delays ofpatient transports withincomplete… to the current scheduling practice of the dispatcher. Thereby, we have exemplarily observed that the waiting times in the optimized schedules are significantly lower than those obtained via a simulation of the current scheduling practice. To incorporate semiplannable transports where significant improvements can be seen, we require more data that includes such transports. Using the current data, we were only able to elaborate on some examples. We have extended the model so that Covid-19 transports can be handled by different vehicle fleets. Still, the model remains solvable in real time and can be solved with MIP-based algorithms. We have outlined algorithmic approaches, which speed up the solution process. In summary, we have proposed a formulation for the scheduling problem of patient transports that can be used in practice, also with further extensions to the pandemic situation. However, extensions are not limited to this application. We are able to decrease the delays for patients. Further, we can adhere to drivers’ shift times more often than a simulation of the reality can, while, in almost all instances, even preserving smaller delays. With the availability of more data, it is expected that the proposed approach will work even better. Several research directions are of interest for the future. As already mentioned, the usage of multi-objective optimization might be helpful as we have conflicting goals, e.g. minimizing delays and adhering to shift times. Another potential for improvement lies in incorporating semiplannable transports, where—assuming more data is available—other methods, e.g., further estimations of the duration and target time of transports, can be implemented. Furthermore, the usage of dummy nodes can be extended, so that they can be created for more types of transport than those presented here for dialysis. Our approach can also be transferred to different scheduling or routing problems. Acknowledgements We are grateful for continuous support from the ILS, Nuremberg, and for many fruitful and stimulating discussions with Dr.Marc Gistrichovsky and Ludwig Fuchs (both ILS). Research reported in this paper was supported by project HealthFaCT under BMBF grant 05M16WEC. Furthermore, this paper has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No 764759. The authors gratefully acknowledge the scientific support and HPC resources provided by the Erlangen National High Performance Computing Center (NHR@FAU) of the Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU). The hardware is funded by the German Research Foundation (DFG). Author contributions Not applicable. Funding Open Access funding enabled and organized by Projekt DEAL. Research reported in this paper was supported by project HealthFaCT under BMBF grant 05M16WEC. Furthermore, this paper has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No 764759. Data availibility Not applicable. Code availibility Not applicable. Declarations Conflict of interest There are no Conflict of interest. 602 D.Adelhütte et al. Ethics approval Not applicable. Consent to participate Not applicable. Consent for publication Not applicable. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/ licenses/by/4.0/. References Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper Res Lett 33(1):42–54 Allen M, Bhanji A, Willemsen J, Dudfield S, Logan S, Monks T (2020) A simulation modelling toolkit for organising outpatient dialysis services during the covid-19 pandemic. PLoS One 15(8):1–13 Beaudry A, Laporte G, Melo T, Nickel S, Jeppesen AB, Laporte G, Melo T, Nickel S (2010) Dynamic transportation of patients in hospitals. OR Spectrum 32(1):77–107 Bektas T, Repoussis PP, Tarantilis, CD (2014) Chapter 11: dynamic vehicle routing problems, pp 299–347 Berbeglia G, Cordeau J-F, Laporte G (2010) Dynamic pickup and delivery problems. Eur J Oper Res 202(1):8–15 Berhan E, Beshah B, Kitaw D, Abraham A (2014) Stochastic vehicle routing problem: a literature survey. J Inf Knowl Manag 13:10 Bertsimas D, Jaillet P, Martin S (2019) Online vehicle routing: the edge of optimization in large-scale applications. Oper Res 67(1):143–162 Bertsimas DJ, van Ryzin G (1991) A stochastic and dynamic vehicle routing problem in the Euclidean plane. Oper Res 39:601–615 Bestuzheva K, Besançon M, Chen WK, Chmiela A, Donkiewicz T, van Doornmalen J, Eifler L, Gaul O, Gamrath G, Gleixner A, Gottwald L, Graczyk C, Halbig K, Hoen A, Hojny C, van der Hulst R, Koch T, Lübbecke M, Maher SJ, Matter F, Mühmer E, Müller B, Pfetsch ME, Rehfeldt D, Schlein S, Schlösser F, Serrano F, Shinano Y, Sofranac B, Turner M, Vigerske S, Wegscheider F, Wellner P, Weninger D, Witzig J (2021) The SCIP Optimization Suite 8.0. ZIB-Report 21-41, Zuse Institute, Berlin Chen D, Pan S, Chen Q, Liu J (2020) Vehicle routing problem of contactless joint distribution service during covid-19 pandemic. Transp Res Interdiscip Perspect 8:100233 Chen Z-L, Xu H (2006) Dynamic column generation for dynamic vehicle routing with time windows. Transp Sci 40(1):74–88 Cordeau JF, Desaulniers G, Desrosiers J, Solomon MM, Soumis, F (2002) VRP with Time Windows Cordeau JF, Laporte G, Potvin JY, Savelsbergh MW (2007) Transportation on demand. Handbooks Oper Res Manag Sci 14:429–466 Cordeau JF, Laporte G, Savelsbergh MW, Vigo D (2007) Vehicle routing. Handbooks Oper Res Manag Sci 14:367–428 Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manage Sci 6(1):80–91 Doerner KF, Hartl RF (2008) Health care logistics, emergency preparedness, and disaster relief: New challenges for routing problems with a focus on the austrian situation. In: Golden B, Raghavan S, Wasil E (eds) The vehicle routing problem: latest advances and new challenges. Springer, Boston, pp 527–550 Ehrgott M (2005) Multicriteria optimization. Springer-Verlag, Berlin, Heidelberg 603 Minimizing delays ofpatient transports withincomplete… Ferrucci F, Bock S, Gendreau M (2013) A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods. Eur J Oper Res 225(1):130–141 Fiegl C, Pontow C (2009) Online scheduling of pick-up and delivery tasks in hospitals. J Biomed Inform 42:624–632 Flatberg T, Hasle G, Kloster O, Nilssen EJ, Riise A (2007) Dynamic and stochastic vehicle routing in practice. Oper Res/Comput Sci Interfaces Series 38:41–63 Gamchi NS, Torabi SA, Jolai F (2021) A novel vehicle routing problem for vaccine distribution using sir epidemic model. OR Spectrum 43:155–188 Gendreau M, Guertin F, Potvin J-Y, Taillard E (1999) Parallel tabu search for real-time vehicle routing and dispatching. Transp Sci 33(4):381–390 Gendreau M, Laporte G, Semet F (2001) A dynamic model and parallel tabu search heuristic for realtime ambulance relocation. Parallel Comput 27(12):1641–1653 Gurobi Optimization, LLC (2021) Gurobi Optimizer Reference Manual Hanshar FT, Ombuki-Berman BM (2007) Dynamic vehicle routing using genetic algorithms. Appl Intell 27:89–99 Ho SC, Szeto WY, Kuo YH, Leung JM, Petering M, Tou TW (2018) A survey of dial-a-ride problems: literature review and recent developments. Transp Res Part B: Methodol 111:395–421 Hulshof PJ, Kortbeek N, Boucherie RJ, Hans EW, Bakker PJ (2012) Taxonomic classification of planning decisions in health care: a structured review of the state of the art in or/ms. Health Syst 1:129–175 Ibaraki T, Imahori S, Kubo M, Masuda T, Uno T, Yagiura M (2005) Effective local search algorithms for routing and scheduling problems with general time-window constraints. Transp Sci 39(2):206–232 Kergosien Y, Lenté C, Piton D, Billaut J-C (2011) A tabu search heuristic for the dynamic transportation of patients between care units. Eur J Oper Res 214(2):442–452 Kim G, Ong YS, Cheong T, Tan PS (2016) Solving the dynamic vehicle routing problem under traffic congestion. IEEE Trans Intell Transp Syst 17:2367–2380 Kim S, Lewis ME, White CC (2005) Optimal vehicle routing with real-time traffic information. IEEE Trans Intell Transp Syst 6:178–188 Kok AL, Hans EW, Schutten JM (2012) Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Comput Oper Res 39:910–918 Land AH, Doig AG (2010) An automatic method for solving discrete programming problems. In: Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA (eds) 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art. Springer, Berlin Heidelberg, pp 105–132 Leithäuser N, Adelhütte D, Braun K, Büsing C, Comis M, Gersing T, Johann S, Koster AMCA, Krumke SO, Liers F, Schmidt E, Schneider J, Streicher M, Tschuppik S, Wrede S (2022) Decision-support systems for ambulatory care, including pandemic requirements: using mathematically optimized solutions. BMC Med Inf Decis Making 22:132 Madsen OB, Ravn HF, Rygaard JM (1965) A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Ann Oper Res 60:193–208 Margolis JT, Song Y, Mason SJ (2022) A Markov decision process model on dynamic routing for target surveillance. Comput Oper Res 141:105699 Melachrinoudis E, Ilhan AB, Min H (2007) A dial-a-ride problem for client transportation in a healthcare organization. Comput Oper Res 34(3):742–759 Mitrović-Minić S, Laporte G (2004) Waiting strategies for the dynamic pickup and delivery problem with time windows. Transp Res Part B: Methodol 38:635–655 Oyola J, Arntzen H, Woodruff DL (2017) The stochastic vehicle routing problem, a literature review, part II: solution methods. EURO J Transp Logist 6:349–388 Oyola J, Arntzen H, Woodruff DL (2018) The stochastic vehicle routing problem, a literature review, part I: models. EURO J Transp Logist 7:193–221 Pacheco J, Laguna M (2020) Vehicle routing for the urgent delivery of face shields during the covid-19 pandemic. Journal of Heuristics 26(5):619–635 Parragh SN, Cordeau J-F, Doerner KF, Hartl RF (2010) Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints. OR Spectrum 34:593–633 Pillac V, Gendreau M, Guéret C, Medaglia AL (2013) A review of dynamic vehicle routing problems. Eur J Oper Res 225(1):1–11 Psaraftis HN, Wen M, Kontovas CA (2016) Dynamic vehicle routing problems: three decades and counting. Networks 67(1):3–31 604 D.Adelhütte et al. Ritzinger U, Puchinger J, Hartl RF (2015) A survey on dynamic and stochastic vehicle routing problems. Int J Prod Res 54:215–231 Robert Koch Institute (2020) Coronavirus disease 2019 (covid–19) – daily situation report of the Robert Koch Institute Savaşer SK, Kara BY (2022) Mobile healthcare services in rural areas: an application with periodic location routing problem. OR Spectrum 44:875–910 Schilde M, Doerner KF, Hartl RF (2014) Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem. Eur J Oper Res 238:18–30 Secomandi N, Margot F (2008) Reoptimization approaches for the vehicle-routing problem with stochastic demands. Oper Res 57:214–230 Soeffker N, Ulmer MW, Mattfeld DC (2022) Stochastic dynamic vehicle routing in the light of prescriptive analytics: a review. Eur J Oper Res 298:801–820 Thomas BW (2007) Waiting strategies for anticipating service requests from known customer locations. Transp Sci 41:319–331 Ulmer MW, Goodson JC, Mattfeld DC, Thomas BW (2017) Dynamic vehicle routing: Literature review and modeling framework Ulmer MW, Goodson JC, Mattfeld DC, Thomas BW (2020) On modeling stochastic dynamic vehicle routing problems. EURO J Transp Logist 9:100008 van den Berg PL, van Essen JT (2019) Scheduling non-urgent patient transportation while maximizing emergency coverage. Transp Sci 53(2):492–509 Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur J Oper Res 286:401–416 Vigo D, Toth P (eds) (2014) Vehicle Routing. SIAM, Philadelphia, PA Wang A, Subramanyam A, Gounaris CE (2021) Robust vehicle routing under uncertainty via branchprice-and-cut. Optim Eng 23:1895–1948 Wolsey LA (2020) Mixed integer programming. John Wiley & Sons, Ltd, Hoboken, pp 1–10 Wolsey LA, Nemhauser GL (1999) Integer and combinatorial optimization. John Wiley & Sons, Ltd, Hoboken Yu X, Gao S, Hu X, Park H (2019) A Markov decision process approach to vacant taxi routing with e-hailing. Transp Res Part B: Methodol 121:114–134 Yu X, Shen S, Wang H (2021) Integrated vehicle routing and service scheduling under time and cancellation uncertainties with application in nonemergency medical transportation. Serv Sci 13(3):172–191 Zhang J, Liu F, Tang J, Li Y (2019) The online integrated order picking and delivery considering pickers’ learning effects for an O2O community supermarket. Transp Res Part E: Logist Transp Rev 123:180–199 Zhang J, Wang X, Huang K (2017) On-line scheduling of order picking and delivery with multiple zones and limited vehicle capacity. Omega 79:104–115 Zhang Y, Zhang Z, Lim A, Sim M (2021) Robust data-driven vehicle routing with time windows. Oper Res 69:469–485 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.