10
$\begingroup$

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.

$\endgroup$
2
6
$\begingroup$

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
$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is there some web/mobile applications that already solve the problem? $\endgroup$ Sep 18 at 16:12
  • $\begingroup$ I'm not aware of any, but maybe someone else is. $\endgroup$
    – prubin
    Sep 18 at 19:03
5
$\begingroup$

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.).

$\endgroup$
4
$\begingroup$

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.)

$\endgroup$
3
  • 1
    $\begingroup$ I agree with you. However, I am wondering how to forecast. I mean, I certainly need lots of data from each potential customer ! It seems complicated to me. Any hints? $\endgroup$ Sep 19 at 12:31
  • $\begingroup$ Good question. The forecasting aspect could be made as complicated as the optimization part, or you could aim for something that is good enough (in both aspects!), then figure out where an improvement would yield the greatest benefit. For travel time forecasting, you might be able to leverage an API that provides not only expected travel times, but actual probabilistic predictions. (Which in turn require sophisticated spatial statistics, because delays are highly spatially correlated.) $\endgroup$ Sep 19 at 18:34
  • $\begingroup$ To forecast, e.g., the time required for field work like repairing a piece of machinery, you might be able to build a classical statistical model, or use Machine Learning. Inputs would likely be what type of machine you need to service, how old it is, possible at what customer it is running, perhaps any diagnostic information or error messages you have. More data is always better, but "small data" can also be useful. Best to tailor your approach to what data you have or can make available (don't train a neural network with only 100 data points). $\endgroup$ Sep 19 at 18:37
1
$\begingroup$
  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.
$\endgroup$
3
  • $\begingroup$ Thanks for your reply. 1. I don't understand your remark. I am making an assumption that all the vehicles are equivalent. 3. What do you mean by "you need a sub-second answer to see whether a job fits in to the current schedule". $\endgroup$ Sep 23 at 13:36
  • $\begingroup$ In terms of 1) Drivers can be "available" in your problem but that doesn't mean that they can work all of their availability. They might be available between Monday to Friday, for example, but when they are deployed, they can only use 3 of those available days due to restrictions around the tachograph $\endgroup$
    – roganjosh
    Sep 24 at 11:19
  • $\begingroup$ In regards to sub-second responses; in online shopping, you'll get given available timeslots for your delivery. These can actually be calculated on-the-fly. It's not a case of "we have 50 slots from 9am-10am on Monday" - those services can actually take your specified location, plus all the current schedules for the driver fleet, and give you dynamic timeslots that are unique to you. To be able to do that, and not have a customer sat looking at a spinner, you need your system to be hyper responsive to see where they could fit into the current schedules $\endgroup$
    – roganjosh
    Sep 24 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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