Modeling Interval Constraints in Multi-day VRPTW for Bi-Weekly Operations

[Alexander Lidén]

How can I model interval constraints in a multi-day VRPTW to ensure subsequent visit days adhere to specified intervals post the initial day, especially over a bi-weekly schedule, without early-week choices overly dictating the schedule?

I'm solving a multi-vehicle, multi-day VRPTW for a two-week schedule, contemplating varying weekday-based time window constraints.

Example: Some nodes require at least two weekly visits with a two-day interval, others have fixed or mixed visit days, and some require daily visits. Additionally, bi-weekly time windows may affect interval suitability each week.

I'm considering duplicating locations for all possible time window combinations, as only 62 out of 286 locations have 2 or 3-day intervals. Adding penalty if more than one is chosen.

Considering many locations lack this interval requirement, would initiating a solution for non-interval nodes and then building from there make anything easier?

Best regards,
Al

[blind.line]

Is the routing part of the problem all that difficult?  Because it seems to me you have a complicated scheduling problem with a little bit of routing. Perhaps it might be easier to try to model this using CPSAT solver with circuit constraints for the routing part. 

James

On Oct 23, 2023, at 12:26, Alexander Lidén <alexande...@gmail.com> wrote:

How can I model interval constraints in a multi-day VRPTW to ensure subsequent visit days adhere to specified intervals post the initial day, especially over a bi-weekly schedule, without early-week choices overly dictating the schedule?

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/2fc9e0d7-9b91-42ce-a982-9d1292bbeb08n%40googlegroups.com.

[Alexander Lidén]

Hi James,
Thanks for the reply and sorry for not answering sooner. The project got slightly postponed until now.
Yes, it is a combination of scheduling and VRPTW, where there are scheduling constraints in some locations.
A location can have the following constraints:

Constraint 1: Minimum service days per week.

Constraint 2: Possible service days a week, for example, "any day of the week", or "any weekday". But 95% have "any weekday".

Constraint 3: Biweekly or weekly, but all biweeklies are 1-day "any weekday" visits. So it results in one location with a big-time window for all weekdays over 2 weeks where I have removed the intervals between which is working fine.

Constraint 4: Minimum time interval between visits. Ideally, I want to use it to set daily visits to be between the 23-25 hour range after the first is chosen. And then use the same for 2 day intervals where I just increase that time interval. 

 
Constraint 6: Some locations also have multiple service times a week. So it can become a constraint of "Come 30 minutes one day, come 90 minutes the second day, come 2 times a week 2 days minimum between". But this one is not that important and I will hardcode this if needed.

For most of these constraints, I do agree that it looks like a scheduling problem, but the scheduling day is dependent on the time between locations and the time windows of other locations.
Thus, for locations with minimum service days per week above 1, I am trying for every Possible service day a week, to create duplicates, with a time-window for that day.

Then using Constraint 4, combined with service times at location, the time matrix and time windows steer how the route is scheduled, if that is possible. I have been looking into some solutions but could not find a real good solution to Constraint 4. There was something similar in this discussion where you also commented, I am unsure if I understood him though. He did something like this:

for j in range((i+1), len(set)):
                # A comes before B by at least N
                A_then_B_constraint = time_dimension.CumulVar(set[i]) <= time_dimension.CumulVar(set[j]) - constants['MIN_BETWEEN_ORDERS']

                # or B comes before A by at least N

                B_then_A_constraint = time_dimension.CumulVar(set[j]) <= time_dimension.CumulVar(set[i]) - constants['MIN_BETWEEN_ORDERS']

                gap_constraint = A_then_B_constraint + B_then_A_constraint == 1

                routing.solver().Add(gap_constraint)

I also have time constraints on the vehicles that will affect scheduling and routing, but that I don't need guidance on.

Once again, sorry for the late reply. Thanks in advance!

Best regards,
Alexander

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/I9wVqetbyfk/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/901B4FE5-0816-4C3E-B430-56463C4C1AF3%40gmail.com.

[Alexander Lidén]

Hi James,
Ok so my bad, looks like this is pretty simple by adding different cumulvar expressions to the solver for all the duplicates I am adding. 

[blind.line]

Cool. Glad you figured it out!

James

On Nov 23, 2023, at 16:15, Alexander Lidén <alexande...@gmail.com> wrote:



Hi James,
Ok so my bad, looks like this is pretty simple by adding different cumulvar expressions to the solver for all the duplicates I am adding. 

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAPkMAE3PfpEKUgUy%2BmvoZcmc_-wxz%2BqZ3mfWtPptYVetpcDrTw%40mail.gmail.com.