GraphHopper.com | Forum | GitHub | Maps | Blog

Strategy to solve assignment problem with periodictiy constraint


#1

Hi all,

I am looking for a strategy to find solutions for a problem where customers need to be served periodically in a given planning horizon (of P = 20 (work)days (4 weeks à 5 days each)). Customers have (multiple) time windows, service durations and a frequency value k, meaning a customer needs to be served k times during the planning horizon with a time gap between services (or periodicity) p of exactly P / k days. For example: a customer with k = 2 needs to be served 2 times exactly every p = 10 days.

My current approach is as follows.

Step 1) (weekday-assignment): First I solve the problem with 20 vehicles, one for each day, to assign customers to single days in the schedule. Since customers with high k will be served more often and hence restrict the solution more strongly than customers with low k, I have chosen to model this by assigning a virtual demand equal to k to each customer and assign a limited load capacity to my vehicles. Ergo, if a customer with, e.g. k = 4 is assigned to the first Monday, the corresponding vehicle will spend a relatively large portion of its load capacity on this customer and will have to return to the depot after serving a relatively smaller amount of customers on that day. At the end of step one I have an interim solution for all of the 20 days in P, with every customer appearing exactly once.

Step 2) (week-clustering): Then, for each weekday, I decide which customers to serve in the same week. For a customer with k = 4, the week assignment is trivial, since he/she will be served every week (and the day of the week has already been determined in step 1)). Since a customer with, e.g., k = 2 can be served in (week 1 and week 3) or (week 2 and week 4), I have to assign the customer to one of the two possibilities. The same goes for customers with k = 1, only now there are 4 possibilities to assign the customer to a week: (week 1) or (week 2) or (week 3) or (week 4). So I cluster the customers geometrically into k clusters for each occurring k elem{1,2,4} (I basically do a k-means clustering, but with approximately equal cluster size, if anyone is interested). These clusters then represent weeks in the schedule.

Step 3) (week-assignment): Then I assign the clusters from step 2) to actual weeks in P. I start with the clusters with k = 4 (trivial) and then assign the two clusters with k=2 in such a way, that the overall driving distance is minimized; then repeat for clusters with k = 1.

Step 4) (day-optimization): I then solve the TSP for each day in P.

The approach returns plausible results, which is nice. It has, however, its weaknesses.

  1. If the customers are not homogeneous, i.e. if a customer is either located very far from the others or has a much greater service duration than the others, the trick with the load capacity from step 1 can fail; such a customer would need to displace more customers from that day to other days than given by its k. In extreme cases – even if I make sure that the “strange” customer is the only one who gets served on a certain day in step 1) – there might still be too many customers assigned to the same weekday in different weeks to find a feasible solution for some of the days in step 4).

  2. Another effect, very much associated with problem 1): As the planning horizon gets longer – more precisely: as the number of weeks (and hence the number of possible values for k grows) – the load capacity crutch also gives less and less plausible approximations for the number of customers that can be served on a given weekday.

My questions are: How can I make the approach more robust to include outliers / “strange” customers as described in step 1)? How can I make the approach more generic for longer planning horizons? What do you think about the general idea?

TL;DR: I am using jsprit to find solutions (robustly and as generically as possible) to assignment problems with periodicity constraint. My current approach has wekanesses. Pls help.


#2

Hi Goetz,

I am looking for a solution to a similar problem as described by you.

I found this link which might help you but requires coding for jsprit which I’m not yet familiar with. https://github.com/graphhopper/jsprit/issues/148

At the moment, I am researching this problem and hope to find a reasonable solution that doesn’t require months of work.

If you have progressed on this issue, please share your experience.


#3

Hey Guys. Any update on this? Did you finally came with a solution?


#4

Hi Juan,

no news from me; except that Philip Welch’s approach seems to be promising. Unfortunately at the moment I neither have the time nor the client to go ahead and try it.

Cheers
Götz


#5

Thanks mate.