This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps).
Everyday I am receiving job offers, and I have to schedule interview with them. I have already noticed, that there are two "hot" areas, where is large amount of offices, and around $30-40\%$ of all interviews are taking place in those two spots. I want to go to all interviews, however I want to start working at the end of this month, and this means, I won't be able to meet all employers, if I won't cluster them.
My modeling approach:
The most simple version of this is of course Vehicle routing problem however, in real life I am not getting all $100$ offers with location at the same time, but rather smaller amount ($5-10$) every day, and at the same time so I cannot wait to gather all of them to start computing. This means that I need greedy solution. Additional constraint is that not every recruiter will accept any hour. It can be assumed, that I can do interviewing from $10:00$ to $19:00$, one interview takes $1$ hour, last interview can start at $18:00$. Given $2$ points, I am able (using Google Maps) to tell distance between them (counted in minutes). They can be broken down into three abstraction classes - near (0-15 minutes), medium (16-30), far (31-45). I am not accepting interviews farther than $45$ minutes away. Being late less than $10$ minutes, rescheduling meeting at most one time and offering recruiter less than four dates are constraints for professionalism, and can be exploited, only if this will allow me to schedule additional interview (being late $10$ minutes implies fact, that interview will end $10$ minutes later than expected). Interviews are taking place from Monday to Friday. It is also possible to hold response to offer for $24$ hours. From my empiric experiment, expected time to receive job offer by email is $10:00$ each day (most at Mondays), with standard deviation of $1$ hour.
I am pessimistically assuming, that I will be 15 minutes late for every interview and every two locations are at maximum distance, that is $45$ minutes. In addition to $1$ hour of interview, it given me two full hours per each interview. Considering hours, each day is broken down into five free sports for interviews, starting at $10$, $12$, $14$, $16$ and $18$. I am maintaining list of all open spots for all days in week (five working days) and I am sending full list to each and every recruiter. First recruiter that accepts free spot is assigned to it, and I am marking spot as occupied in Google Calendar, and telling every next recruiter, that he needs to pick other date. When I will see, that recruiter wants to meet somewhere near (0-$15$ minutes) other location, and in the same time, next spot is open, I am suggesting this spot. If he accepts, I am appending him there, and then shifting all starting hours after him by plus 1 hour. If he does not accept, I am offering all available dates. As You can see, this algorithm guarantees me $5$ days times $5$ spots, $25$ interviews each week, plus around $2-3$ more from clustering near interviews. I need at least $30$ guaranteed spots to attend all meetings, and it would be great if it could be $35$, so I could finish them faster and be able to offer more dates for last interviewers. I am also trying to reschedule interviews, so that no two interviews, that first is immediately after seconds, are far, however, rescheduling is transactional operation, that usually takes around $24$ hours.
I am trying to figure out algorithm, that given current state of my Google Calendar (that includes start time and location of each interview) and set of buffered offers, will allow me to maximize amount of scheduled meetings. It can be assumed, that I am immediately informed about each offer (I have mobile Internet). I have same problem each year (as a full-time student, I am looking for job at the start of holidays and dropping it at the end of holidays), and as I suspect to study 5 more years, I need efficient solution.