Transcription
INTEGRATED SCHEDULING FORAMBULANCES AND AMBULANCE CREWSClaire Elspeth ReevesBachelor of Science(Physics and Mathematics) with HonoursUniversity of QueenslandPrincipal Supervisor: Professor Erhan KozanAssociate Supervisor: Professor Vo AnhSubmitted in fulfilment of the requirements for the degree ofDoctor of Philosophy (Mathematics)Statistics and Operations Research DisciplineMathematical Sciences SchoolScience and Engineering FacultyQueensland University of TechnologyJuly 2015
KeywordsAmbulances, Ant Colony Optimisation, Constructive Heuristics, Disjunctive Graph,Dispatching, Flexible Flow Shop, Heuristics, Hybrid Heuristics, Scheduling, TabuSearch.Integrated Scheduling for Ambulances and Ambulance Crewsii
AbstractAmbulance and ambulance crews operate in a complex, budget constrainedenvironment where demand is expected to increase. This thesis addresses questionssurrounding the optimisation of ambulance services through the development ofInteger Programming (IP) models, utilising Flexible Flow Shop Scheduling (FFSS)techniques, for integration of ambulance scheduling and ambulance crew scheduling.Shift scheduling rules are included as constraints in a model that schedules theprocessing of each incident on available ambulances.Three models are developed and tested using realistic data based on incidentdata provided by Queensland Ambulance Services (QAS). The first model is static,allowing ambulances to be dispatched from only one location each, and is testedusing deterministic data. The second model allows dynamic relocation andreassignment of ambulances during a shift. It is tested with deterministic data using arolling horizon approach; the results show a reduction in the number of ambulancecrew shifts required compared to the static model. The third model is a real timemodel which searches for the best ambulance assignments and locations each time achange in the system occurs. Overtime is considered in dynamic and real timemodels through innovative use of disjunctive constraints that compel a job that isintroduced to return an ambulance to the appropriate station to be scheduled at theend of every ambulance shift. The real time model is planned to be of use as adecision aid tool for ambulance dispatchers.The FFSS formulations for the integrated scheduling models are NP-hard. Thenumber of cooperating ambulances and facilities in a metropolitan region leads to alarge number of decision nodes. Heuristic algorithms, based on the extendeddisjunctive graph, are developed to solve large problems. Promising results are beingobtained from Constructive Heuristics (CH), Tabu Search (TS), Ant ColonyOptimisation (ACO) and hybrid heuristics.Integrated Scheduling for Ambulances and Ambulance Crewsiii
Table of ContentsKeywords . iiAbstract. iiiList of Figures. viiiList of Tables . xiList of Abbreviations . xiiiGlossary . xvStatement of Original Authorship . xviiAcknowledgements . xviiiCHAPTER 1: INTRODUCTION . 11.1Problem Statement . 11.2Scope and Significance . 51.3Research Aims. 81.4Thesis outline . 9CHAPTER 2: LITERATURE REVIEW . 112.1Optimising Ambulance Resources . 122.1.1 Coverage Models . 122.1.1.1 Deterministic Coverage Models . 132.1.1.2 Expected Coverage Models . 132.1.1.3 Dynamic Coverage Models . 142.1.1.4 Hypercube Models . 152.1.2 Relocation Models . 162.1.3 General Assignment Models . 192.1.4 Simulation and Dispatching Strategies. 202.2Shift Scheduling and Rostering for Ambulances . 212.2.1 EMS Crew and Shift Scheduling . 212.2.2 EMS Rostering . 232.3Patient Transportation Models . 232.3.1 Estimating Travel Times for EMS . 232.3.2 Dial-A-Ride Problems . 242.4Links to Emergency Department and Disaster Relief Scheduling . 272.5Implications and Summary . 29CHAPTER 3: RESEARCH OUTLINE . 313.1Research proposal. 313.2Background . 323.2.1 Operations Research. 323.2.2 Mathematical Programming . 323.2.3 Job Shop Scheduling Problems . 333.3Methodology . 353.3.1 Model Formulation. 353.3.2 NP-hardness . 363.3.3 Solution Techniques . 373.4Procedure . 383.4.1 Model 1: Static Model with Deterministic Data. 403.4.2 Model 2: Dynamic Model with Deterministic Data . 403.4.3 Model 3: Real time Model . 40Integrated Scheduling for Ambulances and Ambulance Crewsiv
3.4.4 Sensitivity Analysis . 413.4.5 Contribution to the Literature . 41CHAPTER 4: HEURISTICS . 434.1Basic Heuristics . 444.2Metaheuristics . 454.2.1 Local Search Algorithms . 454.2.1.1 Tabu Search . 464.2.1.1.1 Applications of TS . 474.2.1.2 Variable Neighbourhood Search . 484.2.1.2.1 Applications of VNS . 504.2.1.3 Simulated Annealing . 504.2.2 Evolutionary Algorithms . 514.2.2.1 Genetic Algorithms . 524.2.2.1.1 Applications of GA . 534.2.2.2 Particle Swarm Optimisation . 554.2.2.2.1 Applications of PSO . 574.2.2.3 Ant Colony Optimisation . 584.2.2.3.1 Applications of ACO . 594.2.2.4 Harmony Search . 614.2.2.4.1 Applications of HS. 624.3Hyper Heuristics . 634.3.1 Applications of Hyper Heuristics . 634.4Selection of Heuristics . 64CHAPTER 5: CASE STUDY . 675.1Environment . 675.1.1 Available Data . 695.1.1.1 Workforce Modelling Data . 695.1.1.2 Incident Data for the QAS 2011/2012 Financial Year . 695.1.1.3 Ambulance activity . 705.1.2 Shift Scheduling Rules . 725.2Analysis of actual data . 735.2.1 Seasonality . 775.2.2 Priority Type . 775.2.3 Demand Distributions . 775.2.4 Response Times . 815.2.5 Dispatch to Clear . 835.2.6 Time on Scene . 855.2.7 Hospital transfers . 855.2.8 Time at Hospital . 885.3Generating New Data . 895.3.1 Shift Patterns. 925.3.2 Generating Incident Data . 965.3.2.1 Incident arrivals . 965.3.2.2 Hospital Transfer and Time Spent at Hospital . 975.3.2.3 Ambulance Vehicle and Hospital Preferences . 985.3.2.4 Due Dates . 1005.3.3 Estimating Travel Times . 1015.4Verifying New Data . 1025.4.1 Incident Arrivals . 1025.4.2 Priority Type and Ambulance Vehicle Requirements . 1035.4.3 Time Spent at Incident Scene . 1085.4.4 Hospital Transfers and Time Spent at Hospitals . 1085.4.5 Travel Times . 109CHAPTER 6: STATIC MODEL . 111Integrated Scheduling for Ambulances and Ambulance Crewsv
6.1Formulation . 1116.1.1 Assumptions . 1126.1.2 Parameters . 1166.1.3 Variables . 1176.1.3.1 Decision Variables . 1176.1.3.2 Dependent Variables . 1176.1.4 Objective . 1186.1.5 Constraints . 1186.2Solution Approach . 1236.2.1 Case Study. 1236.2.2 Constructive Heuristic . 1236.2.3 Hybrid Heuristic . 1286.2.3.1 Smart Swap Method . 1306.2.3.2 Constructive Heuristic for the Hybrid TS CH . 1336.2.4 MIP solver (CPLEX). 1376.3Results and Discussion . 1376.3.1 Small Problem Size . 1376.3.2 Weekly schedule . 1436.3.3 Sensitivity Analysis . 1466.4Variations . 1506.5Implications and Further Work . 152CHAPTER 7: DYNAMIC MODEL . 1557.1Extensions to the Previous Model . 1557.1.1 Assumptions . 1567.1.2 Disjunctive Graph Representation . 1597.2Formulation . 1617.2.1 Parameters . 1617.2.2 Variables . 1657.2.2.1 Decision Variables . 1657.2.2.2 Dependent Variables . 1657.2.3 Objective . 1677.2.4 Constraints . 1677.3Solution Approach . 1817.3.1 Case Study. 1817.3.2 Rolling Horizon. 1827.3.3 Constructive Heuristic . 1867.3.4 Hybrid Tabu Search and Constructive Heuristic . 1947.3.5 Ant Colony Optimisation . 1947.3.6 Hybrid Ant Colony Optimisation and Constructive Heuristic . 2017.4Results and Discussion . 2067.4.1 Quality of Heuristics . 2067.4.1.1 Reduced problem . 2067.4.1.2 Small sample problems . 2087.4.2 Weekly Shift Schedule . 2117.4.3 Utilisation of Ambulance Stations . 2177.4.4 Objective Weights Analysis . 2177.4.5 Sensitivity to Demand . 2187.5Variations . 2207.5.1 Parameters . 2207.5.2 Variables . 2217.5.3 Objective . 2227.5.4 Constraints . 2227.5.5 Solution Approach . 2237.5.6 Results and discussion. 225Integrated Scheduling for Ambulances and Ambulance Crewsvi
7.6Implications and Further Work . 226CHAPTER 8: REAL TIME MODEL. 2298.1New Additions in the Real time model . 2308.1.1 Coverage . 2308.1.1.1 Coverage Requirements . 2318.1.1.2 Look Ahead Time . 2328.1.2 Breaks . 2338.2Formulation . 2348.2.1 Assumptions . 2348.2.2 Parameters . 2368.2.3 Variables . 2428.2.3.1 Decision Variables . 2428.2.3.2 Dependent Variables . 2438.2.4 Objective . 2458.2.5 Constraints . 2478.3Solution Approach . 2628.3.1 Real Time Information . 2628.3.2 Problem Size . 2638.3.3 Case Study . 2668.4Results and Discussion . 2698.4.1 Decomposition of objective criteria . 2708.4.2 Sensitivity of look ahead time . 2728.4.3 Results Summary . 2728.5Heuristic Solution Approaches . 2748.5.1 Constructive Heuristic . 2748.5.2 Hybrid Heuristics . 2758.6Implications and Summary . 276CHAPTER 9: CONCLUSIONS . 2819.1Response to Research Aims . 2829.2Comparison of each Model . 2859.3Future Research Directions . 289BIBLIOGRAPHY . 291Integrated Scheduling for Ambulances and Ambulance Crewsvii
List of FiguresFigure 1-1 Example of dispatch rules for a simplified ambulance system where solid arcsrepresent paths travelled and dotted arcs represent possible decisions . 4Figure 4-1 Generic algorithm for Tabu Search . 47Figure 4-2 Generic algorithm for Variable Neighbourhood Search . 49Figure 4-3 Generic algorithm for Simulated Annealing . 51Figure 4-4 Process for a generic Genetic Algorithm . 53Figure 4-5 Generic algorithm for Particle Swarm Optimisation . 57Figure 4-6 Generic algorithm for Harmony Search . 62Figure 4-7 Structure of the proposed hybrid heuristic . 65Figure 5-1 Ambulance stations (represented by blue vehicles) and public hospital locations(denoted by orange crosses) across the Brisbane metropolitan area . 68Figure 5-2 Annual ambulance incidents and responses across QLD. Source: (QueenslandTreasury, 2007) . 72Figure 5-3 Example time window for meal breaks . 75Figure 5-4 Example of feasible weekly shift schedule obeying all rules . 75Figure 5-5 Ambulance incidents per hour across Brisbane for 2011/2012 . 76Figure 5-6 All ambulance incidents across Brisbane for 2011/2011, split into priority types foreach hour of the week . 76Figure 5-7 Density of demand across Brisbane for 2011/12 . 78Figure 5-8 Demand density in the busy inner northern region of Brisbane,
techniques, for integration of ambulance scheduling and ambulance crew scheduling. Shift scheduling rules are included as constraints in a model that schedules the processing of each incident on available ambulances. Three models are developed and tested using realistic data based on incident data provided by Queensland Ambulance Services (QAS
