Traveling Doctor Problem
his problem is related in some ways to a TSP, or a Quota-TSP, but has a lot more information that must be taken into account:
There are a number of clinics, all run by the same organisation, employing a number of doctors, who are free to work at any of the clinics. Each clinic is open 6 days a week, 10 hours a day. There need not be a doctor at each clinic during every, but each week, a certain number of patients have to be seen at each clinic (a number which is different for each of the clinics). each doctor makes a salary based on how many hours they work per week, regardless of which clinic they are at. each doctor is able to see a certain number of patients per hour, again, not necessarily the same for each doctor.
Furthermore, the problem takes into account travel time for each of the doctors. The doctors are reimbursed for their travel time to and from work each morning, from their home to the clinic, then from the clinic back home. To complicate things, doctors may travel between clinics during the day. For the time they spend traveling between clinics, doctors are paid their salaries, but cannot see any patients. The patients lost during this time are split between the starting clinic and the destination clinic (for example, if a doctor can see 4 patients in an hour, and travels at 4 pm from a clinic to another that is half an hour away, 1 patient fewer is seen at each of these clinics than would be if travel time were not considered).
The goal of the problem is to minimise the cost to the organisation, making sure that the requisite number of patients are seen weekly at each of the clinics.