Intra-hospital transports are often required for diagnostic or therapeutic reasons. Depending on the hospital layout, transportation between nursing wards and service units is either provided by ambulances or by trained personnel who accompany patients on foot. In many large German hospitals, the patient transport service is poorly managed and lacks workflow coordination. This contributes to higher hospital costs (e.g. when a patient is not delivered to the operating room on time) and to patient inconvenience due to longer waiting times. We have designed a computer-based planning system - c -that supports all phases of the transportation flow, ranging from travel booking, dispatching transport requests to monitoring and reporting trips in real-time. The methodology developed to solve the underlying optimization problem -a dynamic dial-a-ride problem with hospital-specific constraints -draws on fast heuristic methods to * Corresponding author. 1 ensure the efficient and timely provision of transports. We illustrate the strong impact of Opti-TRANS c on the daily performance of the patient transportation service of a large German hospital. The major benefits obtained with the new tool include streamlined transportation processes and workflow, significant savings and improved patient satisfaction. Moreover, the new planning system has contributed to increase awareness among hospital staff about the importance of implementing efficient logistics practices. Medical diagnostic facilities and treatment units are among the most daily visited departments of a hospital, both by inpatients and outpatients. In particular, inpatients with limited mobility are accompanied by trained staff from and to these service areas. If intra-hospital movement is required between health care units within the same building then patients are pushed on gurneys, beds or wheelchairs. In campus-based hospitals, inter-building transportation is provided by appropriate vehicles, mostly ambulances, which can be shared by several patients. The organization and provision of intra-hospital transportation for patients, as well as for supplies and equipment, are among the daily logistics activities conducted in a hospital. Although these ancillary services seem simple and straightforward, they impact significantly on the quality of health care and on hospital costs. For example, the late delivery of a patient to a high cost service facility, such as an operating theater or a magnetic resonance imaging department, leads to the underutilization of valuable (staff and equipment) resources. In addition, it disrupts the initially planned schedules of these units. On the other hand, missing an appointment often results in extended waiting time for the patient or even in rescheduling the appointment, thus impacting negatively on patient satisfaction. Despite its importance, the role played by logistics is often overlooked by health care organizations. A recent study by Landry and Philippe (2004) has revealed that logistics related activities account for about 46% of a hospital's total budget. The continuously increasing pressure on the German health care system through the recent implementation of clinical pathways and diagnosis related groups calls for streamlined processes in hospitals. Transportation services cannot be excluded from this. Hence, the aim of this paper is to contribute to the implementation of efficient logistics practices for intra-hospital transportation. We start by describing our experience in two major hospitals which helped us identify the major problems, analyze planning needs and assess the optimization potential of using operations research-based methods. We then describe the development of Opti-TRANS c , a computer-based planning system, that supports all parties involved in the transportation workflow, ranging from nurses, transportation 2 staff, dispatchers to logistics managers and financial controllers. Our approach stems from the practical experience gathered over the past few years through conducting projects in a number of large German hospitals. The new system covers the complete workflow, including travel booking, scheduling, dispatching, monitoring, and reporting transports. The optimization routines include various heuristic methods specially tailored to handle the complexity of the underlying routing and scheduling problem. We illustrate how the new system helped improve considerably the performance of the patient transportation service at the Municipal Clinics Frankfurt am Main-Höchst, a large hospital that was involved during the software development process. Since the hospital started using the new software, it has experienced significant savings with improved patient satisfaction. Many German hospitals have a central patient transportation department (PTD), which is responsible for the coordination and provision of transportation for inpatients. The core of a PTD is the central dispatch office where new requests for transportation are received while vehicles or transport teams operating on foot are en-route servicing other requests. As we will show, much of the day-to-day running of the operations is paper based, fairly ad-hoc and lacks workflow coordination. A patient care unit or a service department books a request by calling the dispatcher at the PTD, who enters the relevant data (e.g. patient information, origin and destination, specific transport requirements) on paper. Dispatching decisions are usually based on the dispatcher's intuition and expertise. In most cases, he assigns a new request on a first-come-first-served basis to the next available vehicle or transport team and adds this information to his handwritten notes (see Figure 1 ). Urgent requests are handled separately, normally by immediately notifying a given vehicle via beeper or hand-held radio transceiver. After completion of a transport, the vehicle crew calls the dispatcher to receive the next assignment. Often, the dispatcher consigns multiple requests to a vehicle or team which only reports back to the PTD after having completed all jobs. This modus operandi has a number of shortcomings: 1. The phone line tends to get busy during peak hours (specially in the morning) so that calls for new requests do not get through. As a result, many transport bookings only reach 3 Figure 1 : An example of handwritten notes describing transport requests and their assignment to PTD staff (these notes stem from one of the hospitals that we visited). the dispatcher very close to their desired time for pickup or even too late. Moreover, this communication mode is particularly unsuitable for urgent transports; 2. Since the phone line is frequently busy, it is difficult for a hospital unit to cancel or change the data of a previously booked request in time; 3. Due to the fact that the dispatcher only assigns incoming requests to vehicles without specifying the sequence in which the service points are to be visited (this decision is made independently by each crew), the duration of each route is unknown and therefore, the dispatcher cannot estimate when a vehicle will be available again; 4. Hospital units have restricted access to the status of their booked requests. In particular, they are not informed in advance of the expected time of pickup of a patient. This is, however, important when some preparatory procedures need to be carried out prior to the transport (e.g. special equipment is required, the patient needs certain medication); 5. PTD staff (including the dispatcher) are often overloaded, or at least workload is distributed unevenly over the vehicles and teams; 4 6. To avoid empty trips, sometimes staff carry patients without explicit notification from the dispatcher. As a result, double dispatching occurs when the request is assigned to another vehicle; 7. In the absence of an electronic order processing system it is not possible to automatically create management records of the completed journeys by the end of the day. Consequently, service quality cannot be measured. 8. Transports are frequently delayed resulting in waiting times for patients, idle times in service departments awaiting the patients, and underutilization of staff and vehicles. However, exact figures are unknown due to the previous remark. The above list, which is by no means exhaustive, includes issues that were repeatedly reported by all hospitals that we visited. To understand the degree to which inconvenience can be caused to patients, we monitored closely in-house transports in a university hospital with a bed capacity of about 1,500. Figure 2 shows the waiting time experienced by each patient that was serviced by the PTD on a given day. About 25% of the patients waited longer than 30 minutes for their transport. Some patients even waited more than two hours.  The Patient Transportation Problem In the last few years we visited several German hospitals with a bed capacity of at least 800 and gathered information on their patient transportation services. We realized that prior to the development of a support system, we needed to get a clear understanding of the core problem. We summarize next the main features of the transportation problems encountered. We believe that for the most part, they are prevalent not only in Germany but also in other hospitals all over the world. Each request for transportation has an origin location where the patient is picked up (e.g. Given the above characteristics, the aim of the PTD is to provide an efficient and timely transport service to intra-hospital requests. The daily tasks of the dispatcher bear strong resemblance to solving a dial-a-ride problem (DARP) in a dynamic environment where new events occur as time unfolds. However, the patient transportation problem is more complex than the classic DARP due to the presence of hospital-specific requirements. The DARP belongs to the class of pickup and delivery problems with time windows (PDPTW), Cordeau et al. (2006) . In contrast to the standard PDPTW, the DARP focuses on reducing user inconvenience. This objective is often controlled by imposing a limit on the ride time of each user (i.e. the time spent by a user in a vehicle), on the excess ride time (i.e. the difference between the actual and the minimum possible ride time of a user), and on deviations from the desired times for pickup and delivery. Maximizing service quality (i.e. minimizing user inconvenience) is weighed against minimizing fleet operating costs, the latter being related to the number of vehicles used, total route duration and total distance traveled. We refer the reader to the excellent survey by Cordeau and Laporte (2007) for details on the DARP. As in the DARP, the patient transportation problem also aims at determining a set of vehicle routes and schedules that balance the above conflicting objectives subject to a number of sideconstraints. Recently, Paquette et al. (2007) discussed extensively the notion of service quality in dial-a-ride services and surveyed different measurement scales used in practice. Based on discussions with logistics managers, dispatchers and financial controllers, as well as our own 7 observations, we developed the following set of performance indicators to assess the quality of a solution to the problem: 1. total lateness; 2. total earliness; 3. total driving time; 4. total transport time for patients. The first objective is related to patient inconvenience. Although each transport request is booked with a time window, either for pickup at the origin or for delivery at the destination, deviations to the latest desired time are allowed but penalized. The penalty factor incurred for late pickup or delivery depends on the priority level of the request. Lateness may also impact negatively on hospital indirect costs. This is the case when the destination point is a service department (e.g. operating theater), since late delivery results in equipment and staff underutilization. The second objective is related to fleet operating costs. If the vehicle arrives before the lower time limit set for the transport, it is common practice to wait. This is due to the fact that patients often need to be prepared for transport by the nursing staff, specially when the designated origin is a bed ward. Hence, early arrivals cause idle time for the vehicle crew and thus, yield increased direct costs. A penalty factor is imposed on early arrival. The third objective -driving time -can be seen as a cost criterion measuring the utilization level of vehicles and teams. Finally, transport time is a measure of patient satisfaction since it corresponds to the actual duration of a patient transport from the origin to the destination. The overall objective is to minimize a weighted sum of the above four criteria. The weights assigned to these criteria reflect hospital preferences on individual objectives. For example, a hospital that operates its own fleet of ambulances usually gives more importance to cost effectiveness (criteria 2 and 3), while a hospital working with an external ambulance provider tends to give preference to patient convenience (criteria 1 and 4). In all hospitals that we visited, the patient transportation problem exhibited a high degree of dynamism due to unforeseen events. The most common sources of uncertainty are: (a) The majority of the transport requests are not known in advance (typically less than 10% are booked the day before). The number of bookings increases considerably after the morning ward rounds with physicians, in particular to diagnostic and treatment units. to elevator congestion during certain periods of the day. (d) A PTD staff member is absent from work due to illness, a vehicle breaks down or has an unscheduled rest period. As time unfolds and new information reaches the central dispatch office, previously planned routes need to be modified and updated by the dispatcher in real-time. During peak activity periods, the dispatcher often resorts to ad-hoc decisions, without fully understanding their ramifications. Moreover, decisions made at an early stage of the planning horizon may affect the possibility of making good decisions at a later stage. Two of our early projects provided the first step towards understanding the optimization problem, identifying weak points in the transportation workflow, assessing the optimization potential of operations research-based methods, and analyzing the practical needs for a transportation planning system. The starting point of our research and development work was the Saarland University Hospital, a health care organization located in south-west Germany with about 1,300 beds. The hospital campus spreads over a large area with more than 100 buildings. A heterogeneous fleet of 11 hospital-owned ambulances transports up to 400 patients daily. Each ambulance is operated by a team of two people, comprising the driver and an assistant, who work day shifts from Monday to Friday. At night and on weekends transports are provided by a private ambulance service. The hospital supplied data regarding all requests serviced during a given month in 2001. The data included the characteristics of each request (required transportation mode, accompanying personnel, equipment, etc.) along with the corresponding booking time. A first analysis of the data showed that the majority of the daily transports (about 98.5%) were provided to elective patients while the remaining 1.5% referred to urgent requests. Moreover, a comparison between the booking time and the desired time window at the origin of each transport revealed that there was no strict policy on request notification: almost half of the bookings reached the dispatch office at most ten minutes before their desired earliest pickup time and only 3.8% were ordered one day in advance. Furthermore, the data did not include the actual arrival and departure times at/from each location visited by a vehicle and thus, it was not possible to reconstruct the routes of the ambulances. This lack of information was due to the fact that the dispatcher assigned multiple requests to a vehicle without specifying the sequence in which each service location should be visited. In other words, routing and scheduling decisions were made by each 9 ambulance crew and the dispatcher was only contacted after the completion of a batch of jobs. Hence, both ride and dwell times were not known, the latter being defined as the time dedicated by PTD staff to assisting the patient at the origin and destination locations. Although management records of the completed journeys by the end of the day were not available, both patients and hospital staff complained that transports were frequently delayed. This caused excessive waiting time for patients as well as underutilization of equipment and staff at the therapeutic and diagnostic units awaiting the patients. Since exact figures could not be produced, the logistics department asked us to look into the problem, identify the bottlenecks and suggest various ways of improving the service quality of the PTD. We decided to develop a simulation model to reproduce the behavior of the patient transportation system. Simulation has become a popular managerial tool in health care organizations in the last years, Jacobson et al. (2006). Our choice was guided by the following objectives: (i) the performance of the system could be measured by a set of quality criteria previously discussed with the hospital; (ii) using the visual interface of the simulation software, a realistic reproduction of the patient transportation system could be conveyed to the decision-makers, thus enhancing the acceptance of the model; (iii) different scenarios could be simulated and their outcome could be evaluated with respect to various performance measures; (iv) the simulation would help us understand better how the transportation service works and later support the development of optimization-based methods. Prior to developing a discrete-event simulation model, further data were collected with the assistance of the PTD. In addition to data on the actual ambulance routes over several days, we also gathered information on the layout of the campus and its 9.3 mile road network. We estimated vehicle ride times and the statistical distribution of dwell times depending on patient mobility. Figure 3 shows a snapshot of the simulation model. Our simulation study confirmed some previously held beliefs and shed new light on other issues, Beaudry et al. (2006) . We realized that the poor management of transport bookings was to a great extent responsible for the long waiting times experienced by patients and hospital staff. Most of the demand for transportation originated for appointments at diagnostic and treatment units. Bed wards contacted these units to set up the appointments, which were normally granted for the same or the following day. Nursing wards were responsible for communicating their transport needs to the PTD and although this information was usually available in advance, in most cases it was conveyed quite late. Moreover, the PTD was almost never notified as soon as an appointment was made. Another aspect which was also impacting negatively on the service quality of the PTD was the limited means of communication between the vehicles and the dispatch office (radio transceivers were used). Finally, we run the simulation with a simple heuristic procedure to assess the optimization potential (a more sophisticated method will be described in the section "OR Methodology"), and realized that patient waiting times could, on average, be decreased by 20% with a 10% travel time reduction. We observed similar findings in a second university hospital. This is the large organization reported in Figure 2 . The outcome of embedding a simple heuristic in the simulation model that we developed for that hospital is shown in Figure 4 . Compared to manual dispatching rules, the optimization-based procedure could, on average, reduce patient waiting time by 26%. Through the two projects briefly described we identified a number of problems faced by the hospitals. We realized that although operations research-based methods could greatly enhance the performance of the PTD, optimization alone could not resolve all the flaws in the system. Transportation processes and workflow required major streamlining. To support all planning and operational phases we decided to develop a planning system. We describe next the main features of the system and in particular the optimization approach for real-time dispatch of vehicles. Furthermore, we illustrate the impact achieved with the new system in a large German hospital which was involved during the software development process. Opti-TRANS c is a software application designed to support all phases of the transportation flow, ranging from request booking, scheduling, dispatching to monitoring and reporting (www.opti-trans.com). While we focused on the development and implementation of the optimization procedures, two other partner companies, SIEDA in Germany and COMEXAR Engineering in Switzerland, focused on the graphical user interface (GUI), data management system and interfaces to the hospital information system (HIS). Prior to its deployment, the software has to be configured to meet the specific requirements of the hospital. This comprises storing baseline data in a central database, that is, all relevant data regarding the hospital layout and the availability of transportation resources. For example, the nursing and service units involved in transportation have to be defined along with their location (building, floor) and opening hours. Regarding the PTD, vehicles and staff need to be specified together with their attributes (vehicle capacities, work schedules and individual skills of transporters). To be able to automatically create routes and schedules, the software relies on a detailed representation of the road network of the hospital campus as well as of walkways 12 and elevators inside the buildings. In addition, estimated travel and walking times are stored in the database. The system is configured to search for fastest routes and can take into account differing traffic conditions at different times of day (e.g. longer walking times in the morning due to elevator congestion) as well as the availability of certain paths for given transportation modes (e.g. access to a building via a ramp, elevator not suited for bed use). Transport requests are booked over the hospital intranet system via a standard order formthe software is fully web-based and a client installation is not necessary (see Figure 5 ). Patient related information can be retrieved from the HIS, thus eliminating the need for typing all patient data. Booking can be made for immediate or future transportation. In addition, transport needs (e.g. medical escort, equipment) and other information (e.g. priority level) are selected from a list of alternatives. Transport requests can also be pre-registered for later completion. Nursing wards and service departments can access information about the status of their requests at any time. They can also modify or cancel their bookings as long as service has not begun. Upon order entry, the system automatically suggests a suitable vehicle and schedules the request in its current route, based on trip requirements (pickup and drop-off locations and times), available transportation resources, calculated travel times, and existing commitments 13 to other requests. Although planning is completely automatic, the dispatcher is always able to make adjustments by altering a route and rescheduling assignments. Trip allocations and routing plans are revised by the software in response to events, as they occur in real-time, and to changes in the spatial and temporal patterns of demand. The dispatcher can continuously monitor the precise situation of transportation activity regarding vehicles on duty, scheduled trips, and driver assignments. As a result, he is able to track all transports, and to identify and respond to unforeseen events in real-time (e.g. the treatment of a patient is not finished by the expected time and so the transport has to be postponed). Different colors to reflect the status and priority of each booking are displayed on screen. The quality of the routes and schedules produced by the optimization procedures is to a  The patient transportation problem is a DARP with several complicating constraints due to hospital-specific requirements. Most research on the DARP has been devoted to the static ver- Opti-TRANS c includes several optimization routines that can be combined depending on the time available for planning. Typically, during morning peak hours much faster response times are required compared to afternoon or night periods. Upon order entry, a decision must be taken about the allocation of the new request to a particular vehicle and its scheduling within the vehicle's planned route. Two alternative ways are considered for request assignment. The load balancing (LB) strategy aims at distributing workload evenly over all vehicles. Therefore, vehicles are sorted by increasing number of assigned requests. Ties are broken by taking the vehicles in increasing order of their earliest possible time to service a new request. A new booking is then assigned to the first feasible vehicle according to these criteria. A vehicle is regarded to be feasible if it has enough capacity, appropriate equipment and suitable working hours to service the request, independently of its current scheduled trips. Alternatively, a best fit (BF) strategy can be used by considering every feasible vehicle for the new request. The suitability of each vehicle is then assessed by scheduling the request within its current route according to a given strategy (see below). The best route with respect to the weighted sum of the four objectives previously described is then selected. Although this approach is more time consuming than the LB strategy, it increases the chances of finding a better solution. Upon assigning a request to a vehicle, routing and scheduling decisions are to be made. Again, we developed three alternative strategies. First fit (FF) mimics the hand-made schedules produced by the dispatcher. It consists of inserting the request in the first feasible position in the vehicle route. A more promising approach is to consider all feasible insertion positions without modifying the scheduled times (i.e. estimated arrival and departure times) of already planned stops in the route. The best feasible alternative in terms of route quality is then chosen. We call this the best fit (BF) strategy. Finally, a best insert (BI) scheme is also available which examines the impact of inserting the request in any position in the route, even if that means having to adjust the planned arrival and departure times of other stops in the route. The sequence of stops already in the route is always maintained in this strategy. Recently, we have also developed an evolutionary algorithm (EA) as an alternative to the various combinations of the above strategies. The basic idea of an EA is that there is a set of entities (called a population) which represent solutions to the optimization problem under consideration. This set of entities evolves through a number of generations. In each generation 15 step, an offspring population is created using data of the previous population (the parents) and random modifications (mutations). It is also possible that data from two parents are introduced into an offspring entity (recombination). Among the parents and offsprings, the best entities are selected to become parents of the subsequent generation. The whole process starts with a population of randomly generated entities (or based on solutions obtained from earlier planning) and results in the best entity of the final population, the solution to the problem. The developed EA controls the assignment of requests to vehicles and so each entity consists of an array of numbers specifying the vehicle assigned to each transport request. Mutations are performed by randomly assigning a new feasible vehicle to a request. Recombination is done by combining two different sets of assignments in some consistent way. To select best solutions, an entity needs some evaluation which means that specific vehicle routes are built by a given route construction scheme. The selection criterion is then the overall objective function introduced before. The EA is tuned by a number of parameters. In particular, a larger number of performed generations or a larger population size frequently improves the results but requires longer computation times. Since these parameters do not allow for a direct control of running times (which is essential in real-time planning where optimization runs are performed at regular time intervals), an additional parameter prescribes the maximum allowed runtime of the EA. The Municipal Clinics Frankfurt am Main-Höchst (MCFH) are a 1,000-bed facility in Germany (see Figure 6 ). MCFH provides health care to about 34,000 inpatients and performs approximately 20,000 surgeries each year. The PTD has a staff of sixteen employees that are divided into three eight hour shifts. In units were using Opti-TRANS c to book and monitor their requests for transportation. During this initial phase we refined and improved the GUI and the interface to the HIS. Moreover, we tailored the heuristic procedures and tested them with data generated according to the characteristics of a particularly busy period of the day. 60 transport requests were generated with earliest desired pickup times occurring within a one-hour interval. The requests were classified into three priority levels (high, normal, low) and included varying requirements for equipment and medical escort. At most 21 transporters were available, meaning that on average three requests could be serviced by each staff member during one hour. Figure 7 shows the results obtained by combining different strategies for assigning and scheduling requests. The solutions obtained were assessed by their quality (objective value) and computing time. Although we knew beforehand that some combinations would not yield good quality solutions, it was important to consider them since they were closer to the manual dispatching rules, and thus enabled the hospital to recognize the enhancement potential of the optimization methods. This is clearly the case of using the first fit strategy in the routing and scheduling stage. As expected, there is  MCFH started experiencing the benefits of using the software already during the first deployment phase. The new system helped streamline transportation processes and workflow. As a result, the organization and coordination of intra-hospital transports was greatly enhanced. Many procedures that lacked clarity were replaced by consistent rules. For example, on-line data entry, via the web-based booking system, completely transformed the order entry process and the information flow between the hospital units and the central dispatch office. The optimization-based methods, which started being used in the second deployment phase, brought further benefits. However, it is difficult to measure the savings directly attributable to the heuristic procedures because hand-made solutions were never recorded and therefore, comparison of automated versus manual dispatching rules is not possible. Yet, both the PTD and the logistics department feel that significant savings have been achieved in terms of the quality of the new routes and schedules. As a result, service level was enhanced through the overall reduction of patient waiting times and at the same time, the workload became more evenly divided among PTD staff. Hence, Opti-TRANS c has contributed to improve patient satisfaction and to cut down hospital costs. Furthermore, with the help of the new tool management realized that the workforce coverage in the afternoon was not enough to cope with demand, while a surplus was detected in the morning. This led to moving some PTD personnel from the morning to the afternoon shift. The reporting tools also showed that some diagnostic units ordered transports in batches. This procedure created sudden demand peaks for patient transports which could not be properly satisfied with the available resources. Although an increase of the PTD capacity seemed to be the right decision to take, we noticed that the problem had an organizational background. The service units were actually not sized to attend so many patients at the same time and therefore, a timely arrival of the patients at those units would simply yield intolerable waiting times. Hence, the problem was solved by reviewing the rules for appointment scheduling in 19 those hospital departments. Currently, MCFH is focusing on enhancing the communication mode between the central dispatch office and the transporters. Ideally, PTD staff would carry mobile devices capable of maintaining full two-way data communication at any time instead of using in-house telephones. In addition, the exact location of each transporter could be known thus allowing the diversion of the transporter away from his immediate destination to service a new request in the vicinity of his current position. However, the hospital does not have enough financial resources at the moment to invest in a wireless local-area network infrastructure. In the meantime, alternative technological solutions are being sought. One possibility is to install access points in central locations within the hospital (e.g. elevator banks) that are visited during most of the transports. Finally, the new planning system has played an important role in bringing more robustness not only to intra-hospital transports but also to patient flow management in general. MCFH has also recognized the role of the new system to support strategic planning. In the long-run, the tool helps to obtain a better insight into the main transport paths within the hospital. This knowledge is important for layout planning, where the location and size of new medical and nursing units is to be decided so as to minimize the total distance that patients and staff must walk. MCFH is currently conducting a study on the future layout of the hospital to respond to population aging and growing demand for ambulatory medical care. Intra-hospital transportation is an essential building block for increasing efficiency in hospital logistics. This conclusion is supported by the results obtained not only at MCFH but also at other large German hospitals where we conducted similar projects. The growing patient-oriented view in German health care organizations reinforces the importance of providing efficient and timely transport service to patients. In addition, the continuing pressure on hospitals to cut down costs also drives the development of planning systems to support decision making processes. Although the health care industry in Germany has been relatively slow in adopting information technology and operations research techniques, this study reveals that there is a significant potential for using these tools. We have shown that optimization-based methods can give a major contribution to enhancing patient satisfaction and at the same time generating important cost savings. However, operations research methods alone are not sufficient to resolve all the flaws in the transport system. Improvements can only be achieved by streamlining work 20 processes and increasing awareness among hospital staff about the importance of implementing efficient logistics practices, Hall et al. (2006) . Opti-TRANS c is a transport planning system that has been designed to support all phases of the transportation flow, ranging from request booking, scheduling, dispatching to monitoring and reporting. Finally, we point out that although the interrelation between patient transportation (and more generally hospital logistics) and clinical pathways is evident, it has not yet been fully investigated. The DARP is concerned with finding a set of minimum-cost routes and schedules for a given fleet of vehicles to transport passengers between specific origins and destinations at the request of users, Cordeau and Laporte (2007) . The patient transportation problem is a DARP with several complicating constraints that are specific to a hospital context. Instead of presenting a formal mathematical formulation of the problem, we rather give a verbal description of the constraints that must be satisfied by any feasible solution. Our choice is motivated by the computational intractability of the problem (the DARP is a well-known N P-hard problem) so that a formal mixed integer linear programming model does not provide useful insights into the structure of good feasible solutions. The interested reader is referred to Cordeau (2006) and Cordeau and Laporte (2007) (viii) Hospital service constraints: requests for single transportation (e.g. for patients on isolation) must be fulfilled; a transport booking requiring nursing or medical assistance is to be handled as a chain of requests that cannot be interrupted by servicing other requests (e.g. the following sequence is to be performed by a vehicle: pickup doctor -pickup patient -deliver patient -deliver doctor ). The (24 pages, 1998) 7. I. Choquet Heterogeneous catalysis modelling and numerical simulation in rarified gas flows Part I: Coverage locally at equilibrium (24 pages, 1998) 8. J. Ohser, B. Steinbach, C. Lang Efficient Texture Analysis of Binary Images (17 pages, 1998) 9. J. Orlik Homogenization for viscoelasticity of the integral type with aging and shrinkage (20 pages, 1998) 10. J. Mohring Helmholtz Resonators with Large Aperture (21 pages, 1998) 11. H. W. Hamacher, A. Schöbel On Center Cycles in Grid Graphs (15 pages, 1998) 12. H. W. Hamacher, K.-H. Küfer Inverse radiation therapy planninga multiple objective optimisation approach (14 pages, 1999) 13. C. Lang, J. Ohser, R. Hilfer On the Analysis of Spatial Binary Images (20 pages, 1999) 14. M. Junk On the Construction of Discrete Equilibrium Distributions for Kinetic Schemes (24 pages, 1999) 15. M. Junk, S. V. Raghurame Rao A new discrete velocity method for NavierStokes equations (20 pages, 1999) 16. H. Neunzert Mathematics as a Key to Key Technologies (39 pages (4 PDF-Files), 1999) 17. J. Ohser, K. Sandau Considerations about the Estimation of the Size Distribution in Wicksell's Corpuscle Problem (18 pages, 1999) 18. E.
These problems also have been applied to intra-hospital routing (see REF ), mainly through a computer-based planning system designed to support the transportation flow in real-time.
Bringing robustness to patient flow management through optimized patient transports in hospitals
Interfaces
Interfaces
Engineering Computer Science