Looking for some advice on how to approach this combo scheduling + routing problem. I am a supply chain OR consultant, and was recently approached by a potential client. Without giving too much away, they do preventative maintenance for commercial buildings. Some of their customers, they visit 1x a year; some 2x/3x/4x a year (at even spacing between visits), some weekly. All customers are on a defined visit cadence. Visits usually take about an hour so they can do several a day. A technician may be assigned an entire metropolitan area by himself/herself.

Thing is, their visit cadence makes no sense geographically, as the client readily admits (and why they came to me). They may have six customers in a single neighborhood. Three clients are on a January & July visit schedule; two others on a March & September; and one other on an April & November schedule. So the technician could likely get all of them done in one day, twice a year; but instead has to visit this neighborhood six times over the year instead of two. This is destroying their route density and the technicians are doing a lot of unnecessary windshield time.

I've been asked to recommend a "calibration" of when each customer is serviced, to improve route density and cut down on total hours necessary by reducing windshield time. This has a few challenging components that are different than most VRPs:

  1. For customers with more than one servicing a year, there needs to be a time linkage between the multiple services. e.g., whenever the first service is, the second service needs to be six months later (for a 2x annual customer). This isn't easily accounted for in TW settings.

  2. After calibration, a customer can be next serviced sooner than previously planned, but not later. e.g., if they started new schedules on January 1 2024, it's OK for a customer that's currently on the March & September service schedule to be bumped up to February & August; but not pushed back to April & October.

#1 and #2, at least to me, makes this different than a VRPTW and thus can't just be fed into a VRP solver.

  1. Work hours need to be approximately equal by month... I can't just do everything in four months out of the year and nothing the other eight.

Initially, I'm thinking of making an MILP where the integer decision variables are, for each service call, what month to do it in (decision variable value options {1,2,3...12}). The MILP output would then be put through a CVRP solver to quantify total impact of the calibration.

MILP constraints will ensure the even-spaced timing of service calls for customers with multiple visits per year. Constraints can also make the monthly total work roughly equal. What I'm struggling with is how to incorporate the geographic factor, so that each month has (more so than now) tight clusters of demand. I don't know if it's even possible to calculate intra-node distance as part of the objective function and keep the model linear.


1 Answer 1


One possibility might be to start by constructing feasible one-day schedules for techs (service just A, service A and B in some order, service A, B and C in that order, ...). The MILP model would then select combinations of technician, schedule and month subject to constraints on how many days per month a tech can work, satisfying customer demands, and not scheduling the same customer too often or too close in time. If the number of one-day schedules proved too large, you could try column generation (either branch-price-and-cut or a heuristic column generation approach).


Your Answer

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

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