Non Emergency Medical transport from United States to India

Non-emergency medical transport has been faced from different points of view, giving importance to different issues each time. The first thing to have in mind is that non-emergency medical transport has to be faced separately from emergency medical transport. For example, Huggins and Shugg (2008) made clear this need, and explained how non-emergency medical transport started to be treated in a separate way from the emergency one in a specific case. Also, authors remarked that the non-emergency sector would grow in size and the scope of practice would change as the population ages, and health needs change. Despite such studies, specific non-emergency medical transportation services are not often found, so novel approaches are appearing in the last years, such as the one by Safaei (2011). The specific approach mentioned in that paper, however, did not provide details about vehicle routing problems when carrying out the patients’ transport. Further studies have analyzed the quality and safety issues that have to be taken into account when dealing with non-emergency patient transport, for instance the one by Hains et al. (2011). As this paper states, quality and safety issues relating to non-emergency patient transport services have rarely been discussed compared to the transport of emergency patients. Therefore, authors identified communication, efficiency and appropriateness as the key factors that 4 are advanced as impacting on the quality and safety of non-emergency transport services. Lastly, it is worth noting that vehicular networks are having a great importance recently, and of course, they are being used in patient transport situations. However, they are mostly found in emergency transport, as stated by Lee et al. (2014). In this paper, the literature is searched for suggested methods for assisting emergency vehicles, and evaluations are used simulations to evaluate them. Thus, from this review we can conclude that non-emergency medical transport is a relevant field, which should be treated in a separate way from the emergency one, as it owns some very specific features. Non-emergency medical transport should be made as efficient as possible so that medical care is given properly to patients who make use of such service.Genetic algorithms (GAs) have found usefulness in several problems in which a complex solution must be found in a wide range of options. The Vehicle Routing Problem (VRP) is one of such problems. The basic Vehicle Routing Problem consists of a number of customers, each requiring a specified weight of goods to be delivered (Baker and Ayechew, 2003). Vehicles dispatched from a single depot must deliver the goods required, and then return to the depot. Thus, medical transport can be seen as a specific application of the VRP where patients are being transported to medical centers, instead of goods to customers. In particular, Baker and Ayechew (2003) considered the application of a genetic algorithm to the VRP and compared it to both tabu search and simulated annealing, which are the two techniques that have usually been used to solve the VRP. In their paper, authors show that genetic algorithms are an effective approach to solve the basic VRP, although they give more value to genetic algorithms as a means of diversifying the exploration of the solution space rather than being the only way of solving the problem. This is one of several approaches that apply genetic algorithm to the VRP. Another remarkable one is the approach proposed by Prins (2004), in which the author tried to develop some 5 effective metaheuristics for hard combinatorial optimization problems faced in vehicle routing. Thus, he presented a hybrid genetic algorithm for the VRP able to compete with powerful tabu search algorithms in terms of average solution cost. There are also some approaches that focused on solving some variations of the VRP, such as the VRP modified with additional time constraints. More specifically, Hwang (2002) tried to improve a genetic algorithm in order to solve such a problem. Thus, the author found that the proposed model could be potentially efficient and useful in certain conditions. More recently, Pisinger and Ropke (2007) tried to give a solution to such problems by defining a unified heuristic. In this work, authors conclude that a mixture of good and less good heuristics lead to better solutions than using good heuristics solely. According to this, we consider that the Vehicle Routing Problem adapted to medical transport issues is a problem that can be solved by means of genetic algorithms or similar approaches. Therefore, in the following sections we are going to explain how we have addressed the problem of non-emergency medical transport. Our solution, namely NURA, consists of a route planning algorithm for non-emergency patient transport. In particular, NURA uses a genetic algorithm to assign the services to the set of available ambulances, and provides a scheduling algorithm that, given the assigned services to a specific ambulance, determines its schedule.So far, genetic algorithms have been applied to different fields and applications. In particular, we previously proposed an approach focused on traffic accidents urgent sanitary resource allocation based on multi-objective genetic algorithms (Fogue et al., 2013), and a system able to reduce the emergency services arrival time by using vehicular communications and Evolution Strategies (Barrachina et al., 2014). In this work, we propose the Non-Urgent transport Routing Algorithm (NURA), 6 a route planning algorithm for non-emergency patient transport that is able to allocate non-urgent medical transport services to a set of ambulances available. In particular, NURA uses a genetic algorithm to assign the services, and it also determines the schedule of ambulances ensuring the feasibility of the solution provided. The main goal of our system consists on obtaining a complete schedule for each available ambulance including all the stops to perform during the day, indicating the estimated time of arrival and the patients that should be picked up or left at each stop. Determining the route for the ambulances can be divided into two subproblems, easing their solving separately: 1. Assigning a set of services to each ambulance, achieving a complete coverage of the services to perform during the day, that is, each service is assigned to exactly one of the ambulances available that day. 2. Determining the daily schedule for each ambulance taking into account the previous assignment. It is possible to find wrong or unfeasible distributions of services, mainly due to the time necessary to travel from one point to the next of the route, and the time constraints to complete the services. These issues must be considered and avoided during the design of the algorithm.Our proposed system requires data from three sources as input to compute the necessary routes: • Set of services to complete during the day. Each service represents the transport of individual patients, either from their homes to the corresponding health center, or the opposite trip. The essential information that should be provided for each service includes: (i) initial and final address of the service, (ii) time of the day when the service should have finished, and (iii) transport features of the involved patient, i.e., whether 7 the patients are able to walk on their own, or they need wheelchairs or stretchers. These issues are critical to correctly allocate patients in each ambulance. • Available ambulances. These data include the resources available during the day to complete the assistance routes and they will limit the possible solutions of the problem. Additionally, each ambulance is characterized by the number of seats reserved for patients able to walk, seats for patients on wheelchairs, the presence or absence of stretchers in the ambulance, and the presence of additional staff occupying seats. The available schedule of the ambulance is also required to compute the routes. • Ambulance bases. They represent the places where the ambulances start and finish their work shifts (i.e., their headquarters). The information about their location is necessary to determine the initial and final time of ambulance use, as well as the total distance traveled by each ambulance, and hence, the total cost of the assistance operation.Service assignment to ambulances. The distribution of services to the different available ambulances is a problem with high computational cost. As an example, given a day with 80 services to complete using 5 available ambulances (supposing that we could assign each service to any of the ambulances), it makes a total of 580 possible combinations, i.e., 8.27 · 1055 possibilities. A simple “brute force” algorithm computing and checking 10,000 combinations per second would require 2.62 · 1044 years to generate all the possibilities. Obviously, this is not feasible and only a subset of the combinations can be checked in an acceptable time. As the search process must be guided by an algorithm that avoids generating inade8 quate solutions, focusing on those providing positive results, we chose an evolutionary algorithm to fulfill these objectives. 2. Generation of ambulance daily schedules. Once the services are distributed, the route for each ambulance must be computed and its feasibility checked. The subsystem in charge of this part relies on on an algorithm based on actual information from previously generated routes provided by human experts working on the ambulance company. Our algorithm sorts the stops to minimize waiting times, while ensuring the services being assisted on time. The travel time between stops must be determined using a geographic routes generation system, e.g., Google Maps API (Gibin et al., 2008; Svennerberg, 2010), to determine whether the intermediate points can be reached in the required time. It is worth noting that both sub-systems are not independent, since they need the information provided by each other. The genetic algorithm provides the scheduling algorithm with the potential assignment of services to each ambulance, and the scheduling algorithm provides information about the feasibility and optimality of the assignment that will be later used by the genetic algorithm to compute the fitness function of a given individual. Figure 1 shows the structure of the system, including a module in charge of the data acquisition required for the algorithm, which could be obtained from a database or files adequately structured.Genetic algorithms are a sub-set of evolutionary algorithms, which are based on Darwinian theories of evolution. Given a population formed by individuals, natural selection due to the limited resources and environmental pressure increase the level of adaption of the individuals to their environment, i.e., the fittest individuals are able to survive and transfer their beneficial features to their offspring. The new individuals will compete again in the environment. 9 Figure 1: Structure of the NURA algorithm. These individuals are formed by: (i) their external properties affecting their fitness or phenotype, and (ii) a set of genes codifying the corresponding phenotype or genotype (Mester and Br¨aysy, 2005). Evolutionary algorithms belong to the category of search-and-test. In order to determine the level of adaptation of the individuals, also called fitness, an evaluation function estimating the quality of the solution is used. Here, fitness refers to a measure of profit, utility, or goodness to be maximized while exploring the solution space. The evolutionary process depends on two operators: crossover and mutation. The recombination or crossover operator combines two or more genotypes (parents) to form new genotypes (offspring). Individuals with higher values of fitness are more likely to be selected as parents, allowing their offspring to inherit their genes. To increase diversity in the population, the mutation operator is in charge of introducing random changes in the chromosomes. The probability of change in a gene is usually very small to avoid excessive changes in the offspring that could move the individual away from the area that it is currently exploring, and it allows exploring new areas of the solution state space avoiding local optima. There are different variants of evolutionary algorithms, such as genetic algorithms, evolution strategies, evolutionary programming, and genetic programming. In the problem of assigning services to ambulances, the final solution will determine which ambulance is in charge of each service. That is, each possible solution can be represented by a vector representing the resources, and indicating which ambulance will take care of the service. Since the number of available ambulances is finite, and taking into account that GAs represent candidate solutions as strings over a defined alphabet, it makes them the most appropriate type of algorithm for our problem. Evolutionary algorithms are able to obtain solutions with a decent quality in environments where little or none experience is available. However, in practice they are frequently applied to problems in which a considerable amount of experience and knowledge is available, and introducing heuristic methods usually improve the performance of the search process. Hybrid algorithms combining evolution and heuristics are based in the idea of “memes” (Dawkins, 1976), which are units of cultural transmission transmitted through interpersonal communication, making these hybrid approached often known as Memetic Algorithms Representation of individuals: Individuals representing a solution of the problem must be coded into the genetic algorithm; in particular, their genotypes, phenotypes, and the link between them. The phenotype for the ambulance scheduling problem consists on the assignment of services to each ambulance. Each individual, i.e., possible solution, is represented in the population by using a vector of characters where 11 Figure 2: Example of representation of individuals in the genetic algorithm used in NURA. each position is associated with one of the services to be performed during the day, and the value of the vector represents the ambulance in charge of the corresponding service. Due to the limited number of available ambulances, the possible symbols for each gene are finite, thus allowing the use of genetic algorithms in this scope. This representation allows the most efficient crossover and mutation, since varying the assignment of a given service only requires modifying the associated position in the genotype vector. Obtaining the set of services for an ambulance can be determined by searching all the positions in the vector in which the code of the ambulance appearsThe Solutions to be the parents of new generations are selected depending on their fitness values. The main objective of our system is to maximize the quality of the service provided to the patients, which can be represented by the reduction of time spent by the patients in the ambulances. We define the 12 waiting time (WT ) for a patient on a service depending on the destination of the service: • If the destination of the service is a health facility for the treatment of the patient, the waiting time is computed as the difference between the time of the appointment and the time when patient is estimated to be picked up. • If the destination of the service is a home address after the treatment, the waiting time is computed as the difference between the estimated time when the appointment ends and the time when patient is estimated to be left home. We can define the fitness function as the average waiting time for all the services to be performed during the day. Equation 1 shows the computation performed to determine the fitness of an individual (ind) formed by N services labeled as si : F itness(ind) = 100 PN i=1 WT (si) N + 1 (1) Therefore, the fitness value for a theoretical perfect individual without any waiting time would be 100, whereas lower values represent more unsuitable solutions to the problem. • Population: The population contains the candidate individuals corresponding with solutions during a generation. In genetic algorithms, populations usually contain a fixed number of individuals, because the benefits of varying the number of individuals are merely spatial (Affenzeller et al., 2007). The speed of the algorithm is affected by the size of the population, since small populations allow higher speeds but produce premature convergence of the solutions (Koljonen and Alander, 2006).During the parent selection process, the individuals of the population are tested to determine which of them should transmit their genes to the next generation of individuals. In NURA, this phase is performed through tournament selection in which k random individuals in the population are chosen for each possible father, and the best of them all becomes father of the next generation. • Crossover operator: The recombination or crossover operator joins the information of the parents in one or more offspring individuals. This operator is n-ary, even if only two parents are frequently combined. NURA makes use of the classical operator of 1-point crossover as it is the default version for this type of algorithms. Given two parent genotypes, a cutoff point is chosen and the offspring genes take values from the first parent before the point, and from the second parent after the point.Mutation operator: The mutation operator introduces diversity in the population, and it is traditionally defined as the change probability for a single gene. NURA uses a probability of 0.05, i.e., one change for every 20 genes on average. Mutation also takes into account the requirements of the patient to avoid assigning the corresponding service to ambulances without the necessary equipment, for example, if the transport must be performed using a stretcher and the ambulance does not include at least one. • Survival selection: 14 Determining the individuals that should form the population in the new generation is not a trivial process. It is usual to use generational replacement, where the new offspring completely replaces the individuals from last generation. However, NURA uses a steady-state scheme where only a fraction of the individuals are replaced (those with the lowest fitness values) to ensure the best values obtained so far survive in future generations. In our approach, the fraction of individuals replaced in each generation is set to 50%. 4.2. Constraint Handling In most engineering problems, not all the possible solutions of a problem are feasible due to limited resources or other constraints. Hence, using only the fitness value of two solutions is not enough to compare them, and new techniques should be used to compensate this limitation. An interesting approach (Deb et al., 2002) makes use of the constraint-dominance concept, where a solution i is fitter than (dominates) another solution j if any of these conditions is true: 1. Solution i is feasible, while solution j is not. 2. Both solutions are unfeasible, but solution i presents less violation to the feasibility condition. 3. Both solutions are feasible, but solution i dominates over j. Using this approach, we can compare feasible and unfeasible solutions during the search process. In NURA, a solution is considered unfeasible if one of the following conditions is fulfilled: • One of the services assigned cannot be completed due to inability of the ambulance to arrive on time to the health center. Ambulances with too many services assigned may be unable to complete the trip on time, due to long routes or being too far away in the moment they are needed. A good example is found if an ambulance has more services assigned for a trip than its actual capacity, hence the ambulance would make two trips in order to complete them all with the subsequent loss of time. The feasibility violation of an individual is obtained as the total delay time for all the 15 patients, computed as the difference between the time when the patient should arrive and the moment when he/she actually arrives. • The duration of a patient’s trip exceeds more than 1 hour the time required to reach its destination in a direct trip. That is, the additional stops added to a trip to pick up or leave a patient should not delay another patient’s trip more than 1 hour. This condition follows the Spanish legislation regarding non-urgent patient transport (Ministerio de Sanidad, Servicios Sociales e Igualdad.Hybridization in NURA Hybrid or memetic algorithms make use of local search in evolutionary algorithms to reduce the level of randomness in the search process, adding knowledge about the problem to improve the efficiency of the search. In our case, local search is used to increase the quality of the solutions found when the search process has achieved almost feasible solutions. When more than 90% of the services included in the solution are assigned to suitable ambulances, the local search focuses in the rest of services, trying all the possible ambulances for them. Generating neighboring solutions to the problem at hand can be simple using gene modification, since the new solution only differs from the original one in one gene: a service is assigned to a different ambulance. The local search process will finish when the first better solution is found in the vicinity, or when there are no more neighbors left to explore. Table 1 contains a summary of the values selected for the different parameters of the genetic algorithm proposed in NURA. 5. Schedule Generation Algorithm Obtaining the fitness value for a particular solution requires knowledge of the average travel time per patient, which can only be obtained if the daily scheduling of each ambulance is known.

In NURA, the ambulance scheduling process is based on the real procedure followed by human experts in an actual ambulance company. The process followed for planning consists of a series of steps until all services are distributed in ambulance trips: 1. Step 1: Sort. The services are sorted according to the time of day. In the case of services in which the destination is a hospital, the time to consider is the time when the patient should arrive to the health facility (arrival time). If the service represents a transfer to the patient’s home, the arrival time is not as important as the departure time, since more time waiting in a hospital for an available ambulance would reduce the quality of the service. 2. Step 2: Group. Once the services are sorted, they must be grouped into trips. The trips determined by the experts have their destination in the 17 same city, even if the health facility is not the same. Ambulance trips should contain a number of patients not exceeding the capacity of the ambulance, but also minimizing the length of the itinerary and ensuring that the arrival time is not compromised by picking up additional passengers. Hence, all the combinations of the candidate services are considered to find the most adequate groups of services for the given ambulance. 3. Step 3: Time scheduling: After the groups of patients for a trip are obtained, the specific stops for a trip and the corresponding times are computed. The reference for trips with hospitals as destination are determined by the earliest arrival time of the patients transferred, since none of them should arrive later than their appointment. However, if the destinations are patients’ homes, the departure time of the ambulance is set as the latest of the times when the appointments of the patients are estimated to finish. The times are computed taking into account: (i) the travel time of the ambulance between locations, (ii) the time needed to pick up or leave each patient in their homes, set as 5 minutes on average, (iii) the time needed to pick up or leave the patients in a hospital and their transfer to the appropriate area of the health facility, set as 10 minutes on average. These steps are shown in Figure 4 using a small set of services. Once the time scheduling is finished, it is easy to determine if a solution is feasible or not: if the ambulance is not able to reach some destination in time, if would delay all the system and thus it would be considered unfeasible. This information is used by the genetic algorithm to evaluate the solutions and guide the search process.

To schedule a Non emergency Medical transport - do get in touch with email - admin@hiflyingllc.com or call us on 0091 98211 50889 or USA tel no +1 646 480 6268