What is the state-of-art (in industry and academy) of this scheduling + routing problem?

Question

I have a startup idea and I am coming from a CS background.

The startup tries to solve the following problem. A company having a set of employees that needs to visit several "customers" each day. The employees' mission consist of charge vending machines, repair elevators, install furniture etc.

There are several aspects to take into account:

• Each employee has some availability: working hours, week-ends, vacancies etc.
• Each task can be done only by a subset of the employees that have the required set of "skills".
• The "clients" have real-geographical points and the employees use the GPS in their vehicles to move between points. So, somehow the "distances" are the time to get from one point to another.
• Some clients have only time windows in which they are available. An employee cannot visit a non-available client.

My questions:

1. Is there other real-world aspects that are crucial and that I need to take into accounts?
2. Is there a name for this problem?
3. Is there some books/papers etc. that talk thoroughly about the problem?
4. Do you know about existing applications in industry that solve the same problem?

PS: Sorry, I am not a native english-speaker.

Answer 1

This is a variant of a workforce scheduling and routing problem.

Here are two recent surveys where you can find variants, resolution methods and applications:

• "Workforce scheduling and routing problems: literature survey and computational study" (Castillo-Salazar et al., 2016) DOI

• "Routing and scheduling in Home Health Care: A literature survey and bibliometric analysis" (Mascolo et al., 2021) DOI

You can find many other articles on Google scholar

For practical considerations, you might be interested in:

• "Vehicle Routing: Problems, Methods, and Applications, Second Edition", Chapter 12: Software Tools and Emerging Technologies for Vehicle Routing and Intermodal Transportation (Bräysy and Hasle, 2014) DOI

Answer 2

Real world consideration: Time to reach a customer should take into account road network layout and traffic considerations (which are time dependent).

In addition to the suggestions in other answers and comments, you might want to look at the vehicle routing problem with time windows.

Answer 3

Besides other useful answers, there is a nice introduction for Technician Routing and Scheduling Problem which has been found in the Gurobi host.

About the existing application, by googling you can easily find a lot of start-up or web-based firms that use many different techniques to solve such a complex problem. (e.g. this or this one would be interested.).

Answer 4

One potentially important aspect: you will not know many of your inputs, but have to forecast them. The most important example is likely time requirements. You don't know ahead of time how long you will take to repair that elevator, nor how long it will really take you to get to the place where you will do so.

If you spend a lot of effort in developing your optimization routine, but find out later that the uncertainty in the inputs is far more important in terms of the quality of the output, your effort investment may not have been optimal. It may be better to spend effort to forecast the inputs more accurately. Or allow for more slack.

For instance, you may be able to create a perfect route that squeezes the last bit of productivity out of a day - but then the first job takes ten minutes longer, then your driver falls prey to a traffic jam, and suddenly your beautiful plan is shot, and the driver will need to push one job to the next day. Which makes the customer unhappy, who was told to expect the driver today. It might have been better to plan a different route entirely in the first place.

From my (very) limited understanding of the literature, this uncertainty - and in particular how to forecast the inputs - is not given the emphasis it should have. (Then again, I'm probably biased, coming from the forecasting side of things.)

Answer 5

1. Yes - Being available for work does not mean that you've not exceeded your weekly working hours. So a vehicle might be available in the problem setup, but it doesn't account for what they might have worked until that date. Regulations vary, but this will be important in the Working Time Directive with tachographs, for example.
2. "Real Life". I haven't found many papers that actually don't default back to ideal conditions - it's a great area for your own imagination to work. I hate to sound like the person that puts on their Facebook "Education: School of Life" crap, but it's true here. The nature of the problem itself gives you scope to be "smart"
3. I think it would be useful to learn about Large Neighbourhood Search and also Simulated Annealing. There's "Ruin and Recreate" as a named example; but the actual problem you need to solve can be on different timescales. 1) You want a global optimum and 2) you need a sub-second answer to see whether a job fits in to the current schedule. If you know research that can cover both of these, I'd be very interested. In my opinion, that's trade secret and just systems-design.
4. Yes; I've worked on several solutions for companies in the FTSE and continue to work for one of them in development. I can't say too much, but this is a big problem in the real world.