How medical routing works - we tell on the example of the DOC + application
Each smartphone has GPS sensors, sensors, and Internet connection - they dramatically reduced the technological threshold for solving logistics problems. Now we are confronted with complex routing systems almost every day, even if we do not even notice it. With their help, we go around traffic jams, order a taxi, get food delivery. Each of these yuzkeys has its own characteristics - routes must be rebuilt as data is updated, drivers must find passengers, food must remain hot.
At DOC +, we also faced a routing task - we had to guarantee the efficiency of our field doctors. That's how we solved it.
"If you get sick, you can not go to the clinic - the doctor DOC + will come to your home"
We are not just “driving people down” with doctors according to the Uber principle. We are a full-fledged medical company, with a staff of physicians and limited human resources. When a call comes to us, we, first of all, determine how to help the client: in some cases, our specialists can provide advice remotely, in other situations (if it is a matter of too serious an accident), we explain that our service is not a complete replacement ambulance or emergency room. If it seems to you that something threatens your life, we will tell you who to address.
In all other cases, the application is considered valid and is confirmed by the dispatcher. Users of the application can call any available doctor with the necessary specialization, or his beloved doctor, if he is working that day and has the opportunity to reach the patient at a convenient time for him. For an urgent call, the doctor arrives in the next two hours. In a normal call, the doctor will arrive either within the next four hours from the moment of the call, or - if the patient chooses the inspection time in advance - at a time interval chosen by the client (in this case, the interval can be reduced to two hours - the system will help you choose a specific time interval taking into account the doctors ).
Time, as a doctor, and patients - a valuable resource that is important to use wisely. Therefore, in order to minimize the cost of travel and the intervals between receptions, the full route of his movements and work is built for each shift of the doctor. The route begins and ends with a specialist at home and automatically changes as orders arrive. At the same time, we try to calculate the route so that the movements are as convenient as possible, without abrupt movements between distant points on the map. Roughly speaking, a doctor is sent to the other end of Moscow only if someone specifically ordered his or her services (which explains the premium of this option), or an urgent call has come that no one else can accept.
Doctors move around the city in a convenient way for them, which they determine at the beginning of the shift. Owners of a driver's license can use a private car, car sharing or corporate car for this, the rest - public transport or taxi.
The waiting time for the doctor is calculated by our MIRA auto -dispatching system . All applications in the system are displayed on a map of the city and are marked with different markers. Statuses can be as follows:
The doctor changes these statuses independently in his application, and MIRA monitors and takes them into account when rebuilding the routes of other specialists.
Technologically, the MIRA system (Mildly Intellectual Routing Algorithm) solves the “ traveling salesman problem ”, in which you need to choose the optimal sequence of visits to cities and then return to the original city, but with some differences.
The closest to our task, found in the scientific literature, is called "The problem of dynamic routing of a fleet of vehicles, taking into account time intervals" ( PDF ). Its essence is to minimize total transportation costs when calculating car routes with constantly changing parameters: time windows, the length of the path, the number of cars and the number of parking spaces at points of destination.
Our MIRA system also faces the challenge of minimizing the cost of making all calls in a constantly changing environment. When solving it, the system takes into account the cost of all transfers of doctors (including arrivals home), salaries of doctors, the cost of being late for calls and idle time of a doctor without a call, the waiting time of customers. At the same time, MIRA has to handle unforeseen situations (for example, the patient has an urgent business at the time of the call) - in this case, the operator enters new data, and the system recalculates everything.
When calculating the doctor’s route, the doctor’s home address is chosen as the starting and ending point . The remaining points are patient addresses. During the day, the system regularly calculates and updates each route. To estimate the time it takes the doctor to reach the patient, the following factors are taken into account:
Estimation of the “time to reach” is optimized by the meta-heuristic algorithm once a minute, taking into account new data, new calls and cancellations.
As an algorithm, we chose TabuSearch because of its good speed. When searching for the optimal path, TabuSearch takes into account the prehistory of the search and does not consider those routes that he had once viewed and found to be non-optimal.
In order not to disappoint customers, we predict the arrival time of the doctor with a margin. If, for an unforeseen reason, we do not comply with these deadlines, then we notify the client in advance (and if the call was listed as urgent, we do not charge an extra charge for urgency in a situation where we do not have time to arrive within two hours of the call).
An illustration from our blog “ Just Ask ”
Responsibility for communication with the client before the arrival of the doctor are dispatchers. They are the links between the doctor and the patient. Half of the contact center employees have medical education, and the rest studied social disciplines. Their work is governed by strict internal standards, and no algorithms will replace them. This is what they do while the doctor goes to you:
But perhaps most importantly, they are responsible for "settling" the most problematic situations that may arise in the process of planning medical schedules.
If everything goes smoothly, the doctor arrives on time, fills out a medical card, examines the patient and switches to a new client. But in order to safely guarantee people such a well-established service, you need to have a system that provides it.
In the early days of the service dispatchers just followed the doctors on the map. On it you could see who is where and what he does - with the client, on the road or just doing nothing. The current load does not allow this, so the resolution of most problem situations is automated.
Thanks to the efforts of the dispatcher team and data analysis team, more than 90% of the assignments are made using an automated system. In the remaining cases (the client urgently asked to change the time of the reservation, force majeure from doctors, strong unplanned traffic jams), the operator himself makes the appointment.
An example of an emergency situation is the following scenario:
Situations that affect the deadlines for the execution of an application are also automatically detected and converted into standard tickets. These ticket operators are allowed manually. For example, if a doctor is delayed at the reception, his other patients will know about it even before he is released. If the doctor does something wrong - he is late for the shift, “freezes”, or does not follow the contents of the first-aid kit and the presence of forms, the dispatcher immediately receives the appropriate report form.
In particular, we have an order that standardizes the styling composition — the equipment in the doctor’s first-aid kit and the number of inspection forms — at the beginning of each shift, and the doctor is obliged to follow it. To replenish the package, the doctor must call in the office once a week. All this is controlled by the 1C ERP system.
If for some reason the employee will be replaced without the necessary equipment, the operator will remove it from the line and send it to the office. Although we have not yet had a single case when the doctor reported the end of the "consumables" right in front of the client's door.
At first glance, such nuances as the contents of the first-aid kit do not affect the “construction of the path from point A to point B”. However, they are directly related to the movements of doctors, and therefore, with their routing. Therefore, for us, routing is quite a complex set of logistical tasks.
The work of our service is provided both by technologies (applications, artificial intelligence systems and machine learning), and by specialists who can speak and listen: only when all these elements work in conjunction, service is at a height.
We have the thematic magazine “ Only to Ask ” - there we discuss the most popular questions about modern medicine:
At DOC +, we also faced a routing task - we had to guarantee the efficiency of our field doctors. That's how we solved it.
"If you get sick, you can not go to the clinic - the doctor DOC + will come to your home"
At the start: call the doctor
We are not just “driving people down” with doctors according to the Uber principle. We are a full-fledged medical company, with a staff of physicians and limited human resources. When a call comes to us, we, first of all, determine how to help the client: in some cases, our specialists can provide advice remotely, in other situations (if it is a matter of too serious an accident), we explain that our service is not a complete replacement ambulance or emergency room. If it seems to you that something threatens your life, we will tell you who to address.
In all other cases, the application is considered valid and is confirmed by the dispatcher. Users of the application can call any available doctor with the necessary specialization, or his beloved doctor, if he is working that day and has the opportunity to reach the patient at a convenient time for him. For an urgent call, the doctor arrives in the next two hours. In a normal call, the doctor will arrive either within the next four hours from the moment of the call, or - if the patient chooses the inspection time in advance - at a time interval chosen by the client (in this case, the interval can be reduced to two hours - the system will help you choose a specific time interval taking into account the doctors ).
Road to patient
Time, as a doctor, and patients - a valuable resource that is important to use wisely. Therefore, in order to minimize the cost of travel and the intervals between receptions, the full route of his movements and work is built for each shift of the doctor. The route begins and ends with a specialist at home and automatically changes as orders arrive. At the same time, we try to calculate the route so that the movements are as convenient as possible, without abrupt movements between distant points on the map. Roughly speaking, a doctor is sent to the other end of Moscow only if someone specifically ordered his or her services (which explains the premium of this option), or an urgent call has come that no one else can accept.
Doctors move around the city in a convenient way for them, which they determine at the beginning of the shift. Owners of a driver's license can use a private car, car sharing or corporate car for this, the rest - public transport or taxi.
The waiting time for the doctor is calculated by our MIRA auto -dispatching system . All applications in the system are displayed on a map of the city and are marked with different markers. Statuses can be as follows:
- a doctor is appointed;
- accepted the application;
- on my way;
- leads reception;
- finished reception.
The doctor changes these statuses independently in his application, and MIRA monitors and takes them into account when rebuilding the routes of other specialists.
Technologically, the MIRA system (Mildly Intellectual Routing Algorithm) solves the “ traveling salesman problem ”, in which you need to choose the optimal sequence of visits to cities and then return to the original city, but with some differences.
In particular, we do not have one traveling salesman, but many doctors (each has his own shift, starting and finishing points), while all the challenges at the beginning of the day are unknown - the situation changes dynamically (new doctors come out, applications come or change).
Also in our case, additional restrictions are introduced, for example, the doctor must get to the application in a certain time window, plus you have to take into account the wishes of patients and the doctors themselves.
The closest to our task, found in the scientific literature, is called "The problem of dynamic routing of a fleet of vehicles, taking into account time intervals" ( PDF ). Its essence is to minimize total transportation costs when calculating car routes with constantly changing parameters: time windows, the length of the path, the number of cars and the number of parking spaces at points of destination.
Our MIRA system also faces the challenge of minimizing the cost of making all calls in a constantly changing environment. When solving it, the system takes into account the cost of all transfers of doctors (including arrivals home), salaries of doctors, the cost of being late for calls and idle time of a doctor without a call, the waiting time of customers. At the same time, MIRA has to handle unforeseen situations (for example, the patient has an urgent business at the time of the call) - in this case, the operator enters new data, and the system recalculates everything.
When calculating the doctor’s route, the doctor’s home address is chosen as the starting and ending point . The remaining points are patient addresses. During the day, the system regularly calculates and updates each route. To estimate the time it takes the doctor to reach the patient, the following factors are taken into account:
- Some patients need more attention than others. And sometimes doctors themselves have a force majeure situation. This can cause delays, which are counted first.
- The time that the doctor spends on preparing for departure is added. Since external factors do not affect the performance of this task, this time is the same for all employees.
- The waiting time for a taxi or public transport is the same averaged figure, which was experimentally detected, and grows with distance from the Moscow Ring Road.
- Using the data of OpenStreetMap and OSM Routing Machine, the time that the route you would take without traffic jams is calculated.
- The Machine Learning model trained on historical data adjusts this number depending on the location of the doctor, the projected traffic situation, time of year and time of day. The model uses the history of travel of our doctors in a taxi.
- Finally, a fixed time is added to this, which the doctor can spend on finding a patient’s apartment.
Estimation of the “time to reach” is optimized by the meta-heuristic algorithm once a minute, taking into account new data, new calls and cancellations.
We use metaheuristics, because our problem is NP-complete, and the search for an exact solution in a reasonable time is a problem that has not been solved yet. Metaheuristic algorithms allow you to do a search (but not a complete search) and find, perhaps, not the best, but “good” solutions.
As an algorithm, we chose TabuSearch because of its good speed. When searching for the optimal path, TabuSearch takes into account the prehistory of the search and does not consider those routes that he had once viewed and found to be non-optimal.
In order not to disappoint customers, we predict the arrival time of the doctor with a margin. If, for an unforeseen reason, we do not comply with these deadlines, then we notify the client in advance (and if the call was listed as urgent, we do not charge an extra charge for urgency in a situation where we do not have time to arrive within two hours of the call).
An illustration from our blog “ Just Ask ”
While the doctor is traveling ...
Responsibility for communication with the client before the arrival of the doctor are dispatchers. They are the links between the doctor and the patient. Half of the contact center employees have medical education, and the rest studied social disciplines. Their work is governed by strict internal standards, and no algorithms will replace them. This is what they do while the doctor goes to you:
- Working with a consulting physician, dispatchers perform an initial assessment of the severity of a client’s condition. At the same time, they do not just interview the client, but also try to provide him with psychological support, if necessary.
- While the doctor is on the way, they take questions of a medical nature and refer them to the staff of the medical department. They may ask the deputy head doctor or the doctor who is now free from calling.
- If the client needs to contact the doctor who visits him, the dispatchers, monitoring the doctor’s workload, organize a call back.
- If the system is heavily loaded, and there are not enough specialists for everyone, such as during epidemics, dispatchers invite non-scheduled doctors who are not on the schedule.
But perhaps most importantly, they are responsible for "settling" the most problematic situations that may arise in the process of planning medical schedules.
Emergency situations
If everything goes smoothly, the doctor arrives on time, fills out a medical card, examines the patient and switches to a new client. But in order to safely guarantee people such a well-established service, you need to have a system that provides it.
In the early days of the service dispatchers just followed the doctors on the map. On it you could see who is where and what he does - with the client, on the road or just doing nothing. The current load does not allow this, so the resolution of most problem situations is automated.
Thanks to the efforts of the dispatcher team and data analysis team, more than 90% of the assignments are made using an automated system. In the remaining cases (the client urgently asked to change the time of the reservation, force majeure from doctors, strong unplanned traffic jams), the operator himself makes the appointment.
An example of an emergency situation is the following scenario:
The doctor has a shift from 8 to 20. He is scheduled for a morning call with a reservation from 8 to 10. At 8 am, the doctor did not open the shift. The system understands this and creates a corresponding ticket at 8:05. Operators should contact the doctor and decide whether to move the shift a little or remove it from the doctor. If nothing is done before 8:15, and the doctor hasn’t succeeded, then when building the routes, MIRA stops counting on it (until the doctor replaces or the operator does not make manual adjustments).
Situations that affect the deadlines for the execution of an application are also automatically detected and converted into standard tickets. These ticket operators are allowed manually. For example, if a doctor is delayed at the reception, his other patients will know about it even before he is released. If the doctor does something wrong - he is late for the shift, “freezes”, or does not follow the contents of the first-aid kit and the presence of forms, the dispatcher immediately receives the appropriate report form.
In particular, we have an order that standardizes the styling composition — the equipment in the doctor’s first-aid kit and the number of inspection forms — at the beginning of each shift, and the doctor is obliged to follow it. To replenish the package, the doctor must call in the office once a week. All this is controlled by the 1C ERP system.
If for some reason the employee will be replaced without the necessary equipment, the operator will remove it from the line and send it to the office. Although we have not yet had a single case when the doctor reported the end of the "consumables" right in front of the client's door.
At first glance, such nuances as the contents of the first-aid kit do not affect the “construction of the path from point A to point B”. However, they are directly related to the movements of doctors, and therefore, with their routing. Therefore, for us, routing is quite a complex set of logistical tasks.
The work of our service is provided both by technologies (applications, artificial intelligence systems and machine learning), and by specialists who can speak and listen: only when all these elements work in conjunction, service is at a height.
We have the thematic magazine “ Only to Ask ” - there we discuss the most popular questions about modern medicine: