6
$\begingroup$

Consider the following problem of Technician Routing and Scheduling Problem. We have:

  • A set of customers where each customer needs the intervention of a technician to do some job. Each customer has a time-window of presence and a geographical local. Each job requires a set of skills and has a known processing time.
  • A set of technicians, each with some skills and with time-windows of working hours.

The TSR problem involves assignment, scheduling, and routing of multi-skilled technicians to serve customers. The objectives are to minimise the cost (involving the distance and the time to move from one location to another) and to maximise customer satisfaction (this objective needs some interpretation).

The problem is that in real-life there is a lot of uncertainties. Jobs or travel-times may take longer than expected. The schedules are not so "robust", a 10-minutes lateness may create a big chaos. Some technicians will not have the time to visit all their assigned customers, which make them unhappy.

How to cope with that in some "clever" way? I don't have any data to forecast things.

For example, I thought about making each customer choose two time windows rather than one. This way, I always have a second chance if things go wrong. PS: The second time slot will not be used from the beginning but only if the first one is missed. Somehow, it's like having a "new" customer. The point is we don't bother him by asking a second time "when will you be be available?", we already know the answer (which is the time window of the second slot).

Any other suggestions?

Thanks.

Improve this question
$\endgroup$
8
  • $\begingroup$ If you assign a second slot to each customer, do you then route technician to that customer at both times? If yes, and the second slot is unneeded because the first technician arrives on time, you have missed the opportunity to use the second technician someplace else. If no, and the first technician misses their time window, what good did the second slot do you? $\endgroup$
    – prubin ♦
    Sep 20, 2021 at 21:30
  • $\begingroup$ In the real world, solutions are often "aspirational". You generate schedules that are "optimal" within the limitations of the validity of your model (which contains both approximations and uncertainty), with the belief that following these schedules as best you can will, over the long run, produce good results, and possibly better results than any other schedules you can produce. At the same time, you have to recognize the wisdom of an old saying: "The first casualty in every battle is the plan." $\endgroup$
    – prubin ♦
    Sep 20, 2021 at 21:38
  • $\begingroup$ The only good thing it does is, instead of telling the customer that we couldn't make it the first time and we need him to define another time slot, we directly use the second slot. $\endgroup$
    – BloodyOrange
    Sep 20, 2021 at 21:40
  • $\begingroup$ Meaning that you will hold the information in reserve and, when a technician falls behind, rerun the model using the updated status information and the new slot for that customer? $\endgroup$
    – prubin ♦
    Sep 21, 2021 at 15:18
  • $\begingroup$ yes, that's it. $\endgroup$
    – BloodyOrange
    Sep 21, 2021 at 15:35

1 Answer 1

Reset to default
6
$\begingroup$

There are many ways to approach your problem and there is a lot of literature on similar problems. You could look at the following article:

Gorissen, Bram L., et al. “A Practical Guide to Robust Optimization.” Omega, vol. 53, June 2015, pp. 124–37. ScienceDirect, https://doi.org/10.1016/j.omega.2014.12.006.

A simple approach would be to add 'safety slack' to your data. E.g. increasing travel times or service times by a factor of 10%.

I would not follow your approach because it adds way more complexity to the model and what about the case in which the second time window is missed? And if you assign two time slots to every customer but only one is needed, this will lead to inefficient plannings.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi, thanks for your answer. The second time slot will not be used from the beginning but only if the first one is missed. Somehow, it's like having a "new" customer. The point is we don't bother him/her by asking a second time "when will you be be available?", we already know the answer (which is the time window of the second slot). What do you think? $\endgroup$
    – BloodyOrange
    Sep 20, 2021 at 20:02
  • 1
    $\begingroup$ Yes that would be possible. It will then be a sort of dynamic traveling salesman problem, so you might want to check that out. $\endgroup$
    – PeterD
    Sep 20, 2021 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.