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
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
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
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
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),
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
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
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
• 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.
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
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
waiting time (WT ) for a patient on a service depending on the destination of
• 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
• 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
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
i=1 WT (si)
N + 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.
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:
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
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
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
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
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 - firstname.lastname@example.org or call us on 0091 98211 50889 or USA tel no +1 646 480 6268