VRPTW: Routing Problems recalculating a given solution fixing time windows and adding new locations

[I. Sanzol]

Hello!

Version: ortools-V2015-09.jar
Language: Java 

Solver: Linear VRPTW

Windows 10

Initially posted at github (https://github.com/google/or-tools/issues/2142), but I've been told to ask here 

My problem: No solution found when setting fixed time windows based on a previous solution and adding feasible locations

I'm using a linear VRPTW with time windows also on vehicles
A vehicle starts on depot and goes firstly to a node assigned to him with a fixed time window based on the start of his working day, then goes A->B->C->D....->last node (assigned with a fixed time window based on the end of his working day) and then depot

When the solver gives a solution, I use the times given from that solution to set a fixed time windows to each location (imagine I call to my client to notify him that time), but when I add some new locations, it dont want to return any solution.

Google api says it takes 139 minutes to go from Vehicle 12 node 70 to that new location (since 9:00), and that new location has a wide time window (until 15:00) so the location is highly feasible

Find attached two minimum examples, one of them is working while the other (with 1 location more) is not, so the question is: why is the solver not returning any solution?

I'm using time dimensions:

    routing.addDimension(transitCallbackIndex, // transit callback

            30000000, // allow waiting time

            30000000, // vehicle maximum capacities

            false, // start cumul to zero

            "Time");

    RoutingDimension timeDimension = routing.getMutableDimension("Time");

Setting time windows is done this way: 

 // Add time window constraints for each location except depot.

for (int i = 1; i < timeWindows.length; ++i) {
long index = manager.nodeToIndex(i);
timeDimension.cumulVar(index).setRange(timeWindows[i][0], timeWindows[i][1]);
}
// Add time window constraints for each vehicle start node, which is the depot.
for (int i = 0; i < vehicleNumber; ++i) {
long index = routing.start(i);
timeDimension.cumulVar(index).setRange(timeWindows[0][0], timeWindows[0][1]);
}
// Add time window constraints for each vehicle end node, which is the depot.
for (int i = 0; i < vehicleNumber; ++i) {
long index = routing.end(i);
timeDimension.cumulVar(index).setRange(timeWindows[0][0], timeWindows[0][1]);
}
for (int i = 0; i < vehicleNumber; ++i) {
routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));
routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));
}

This is my solver config: 

    RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters()

.toBuilder()

.setFirstSolutionStrategy(FirstSolutionStrategy.Value.SEQUENTIAL_CHEAPEST_INSERTION)

.setTimeLimit(Duration.newBuilder().setSeconds(30))

.setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GENERIC_TABU_SEARCH)

.setSolutionLimit(1)

 .build();

 Solution limit is 1 because otherwise, solver cannot return solutions after fixing time windows, sequential_cheapest_insertion because only sequential or parallel cheapest are returning a result in a low amount of time (the others take +20 minutes to never)

I readed about linear programming, quite a lot ortools documentations and looked at the examples but I don't really know why this is failing, I'm not 100% familiar to constraint-programming so I appreciate that any suggestions comes with a little code snippet

I am surely missing something although it looks like my solution should be working

Initial solution (before fixing time windows) is:
Vehicle 0 node 0 (0-0)
Vehicle 0 node 2 (480-480)
Vehicle 0 node 27 (540-558)
Vehicle 0 node 37 (589-607)
Vehicle 0 node 40 (670-688)
Vehicle 0 node 56 (718-736)
Vehicle 0 node 45 (765-783)
Vehicle 0 node 39 (873-900)
Vehicle 0 node 63 (983-1021)
Vehicle 0 node 1 (1200-1200)

Vehicle 1 node 0 (0-0)
Vehicle 1 node 4 (480-480)
Vehicle 1 node 35 (519-522)
Vehicle 1 node 28 (598-601)
Vehicle 1 node 44 (647-650)
Vehicle 1 node 29 (717-720)
Vehicle 1 node 34 (816-840)
Vehicle 1 node 49 (915-966)
Vehicle 1 node 3 (1200-1200)

Vehicle 2 node 0 (0-0)
Vehicle 2 node 6 (480-480)
Vehicle 2 node 62 (540-576)
Vehicle 2 node 60 (604-640)
Vehicle 2 node 30 (684-720)
Vehicle 2 node 58 (783-840)
Vehicle 2 node 46 (956-1016)
Vehicle 2 node 5 (1200-1200)

Vehicle 3 node 0 (0-0)
Vehicle 3 node 8 (480-480)
Vehicle 3 node 31 (540-574)
Vehicle 3 node 51 (626-660)
Vehicle 3 node 50 (786-840)
Vehicle 3 node 7 (1200-1200)

Vehicle 4 node 0 (0-0)
Vehicle 4 node 10 (480-480)
Vehicle 4 node 48 (480-488)
Vehicle 4 node 32 (605-613)
Vehicle 4 node 69 (701-709)
Vehicle 4 node 9 (1200-1200)

Vehicle 5 node 0 (0-0)
Vehicle 5 node 12 (480-480)
Vehicle 5 node 33 (566-588)
Vehicle 5 node 47 (638-660)
Vehicle 5 node 68 (751-784)
Vehicle 5 node 61 (867-900)
Vehicle 5 node 11 (1200-1200)

Vehicle 6 node 0 (0-0)
Vehicle 6 node 14 (480-480)
Vehicle 6 node 38 (540-545)
Vehicle 6 node 36 (627-632)
Vehicle 6 node 41 (743-748)
Vehicle 6 node 66 (835-840)
Vehicle 6 node 13 (1200-1200)

Vehicle 7 node 0 (0-0)
Vehicle 7 node 16 (480-480)
Vehicle 7 node 57 (480-497)
Vehicle 7 node 42 (613-630)
Vehicle 7 node 55 (800-840)
Vehicle 7 node 15 (1200-1200)

Vehicle 8 node 0 (0-0)
Vehicle 8 node 18 (480-480)
Vehicle 8 node 43 (540-543)
Vehicle 8 node 54 (627-630)
Vehicle 8 node 17 (1200-1200)

Vehicle 9 node 0 (0-0)
Vehicle 9 node 20 (480-480)
Vehicle 9 node 52 (510-570)
Vehicle 9 node 64 (630-720)
Vehicle 9 node 19 (1200-1200)

Vehicle 10 node 0 (0-0)
Vehicle 10 node 22 (480-480)
Vehicle 10 node 53 (480-534)
Vehicle 10 node 59 (636-690)
Vehicle 10 node 21 (1200-1200)

Vehicle 11 node 0 (0-0)
Vehicle 11 node 24 (480-480)
Vehicle 11 node 65 (510-511)
Vehicle 11 node 67 (659-660)
Vehicle 11 node 23 (1200-1200)

Vehicle 12 node 0 (0-0)
Vehicle 12 node 26 (480-480)
Vehicle 12 node 70 (544-664)
Vehicle 12 node 25 (1200-1200)

I've been dealing with this problem since may, so any help is hugely appreciated

Thank you a lot in advance

[Iván Babic]

Hi Sanzol,

Seems like you are assigning the same time window to start and end nodes, which seems odd. If you also need a time window in the end node I would advice to create a dummy end node with the same distances as the depot, and 0 to the depot itself.

I'm not 100% sure because I never followed your approach but I think the solver wont work assigning the same TW to start and end, even though they are for the same node, this is because you are specifically saying you want the starting node and ending node to be visited in the same timeframe.

PD: just checked your files seems like the tw for start node includes all the others, try to delete the end tw loop:

// Add time window constraints for each vehicle end node, which is the depot.

Let me know if that helps,

Cheers,

Iván

[Inti S.]

Hi Iván, thank you for your reply

That worth a try without success, deleting the end tw loop didn't help

Those loops (start tw and end tw for each vehicle) sets up (as I understand) a range to start and a range to end for vehicles, which is from 0 to 1440 (12pm), that means the vehicles can start it's route anytime between 00:00 and 24:00 and end anytime between 00:00 and 24:00

What is really dictating time windows for the vehicles are the assigned nodes for each vehicle with fixed time windows (one for the start of the working journey and the other for the end), that is the loop below "// Add time window constraints for each location except depot." comment

--
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/rvnbHeftYzs/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/d41dc657-6c5e-412d-8fd2-90aa553dd674n%40googlegroups.com.

[Iván Babic]

ok, but why setting the start tw then? seems like the end tw is enough to enforce that

[Inti S.]

Well, I don't think there is any specific reason for it right now as long as it doesn't break any solution in any specific case, neither start or end tw for vehicles

I guess it's there because of thousands of things I (or my team) tried to make it work as I need it. No effect removing it.

Mizux answered me in the github topic before closing it, I don't completely understand what he said (if someone understands it):

1. When you are adding new solution, the solver may not found an new initial solution.
2. When you add new node, did you use a disjunction ? sometime it's better to start from the previous initial solution, then let the local search try to insert the new location (if possible)
3. If you add a new location without using disjunction, then your previous solution is NOT an initial solution for the new problem since you are not visiting the new mandatory location.

What's the point on adding a disjunction here (or removing it) if I have an initial solution?

I think there's no difference with or without disjunctions here as I need to visit every node with any vehicle

The problem is I added some things to this based on answers to problems very similar as mine that I don't completely understand because they are not working as expected (or as I expect) so as disjunctions or forcing a specific location after a specific node

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e3fc56a7-adb0-4144-9f5c-8f99d6f4fd7bn%40googlegroups.com.

[blind.lin...@gmail.com]

My two cents:

I would also recommend adding disjunction to the new node to allow the
solver to drop it.

You asked what's the point? The point is that the solver must come up
with a valid solution. Without disjunctions, you are asking it to
serve all destinations, or no destinations at all. Sometimes it can't
find the initial solution, and so it will quit. Adding a disjunction
on the new node will give the solver the opportunity to find your
original solution, using the fixed time windows, and then try to slot
in the new destination where it can fit.

I would also change some of your initialization settings. You have
something like this (I edited because the copied version is formatted
strangely in email message)

parameters.setFirstSolutionStrategy(FirstSolutionStrategy.Value.SEQUENTIAL_CHEAPEST_INSERTION)
parameters.setTimeLimit(Duration.newBuilder().setSeconds(30))
parameters.setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GENERIC_TABU_SEARCH)
parameters.setSolutionLimit(1)

I have issues with the first and the last of these.

Going through these:

I never use sequential cheapest insertion, but if it works for you
great. I sometimes make a block with all of the first solution
strategies and then just successively try all of them and see which
ones work. Some find a good solution, some fail completely. I put a
little note in the code, and then keep the best. But as the problem
changes sometimes the initial solution heuristic must also change.

For example, here is a snippet from something I did back in 2019ish
(so the strategies might be different in the latest version)

search_parameters.first_solution_strategy = (
# routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_ARC) # works
routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC) # works
# routing_enums_pb2.FirstSolutionStrategy.SAVINGS) # works
# routing_enums_pb2.FirstSolutionStrategy.FIRST_UNBOUND_MIN_VALUE) # crazy suboptimal
# routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC) # suboptimal
# routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # suboptimal
# routing_enums_pb2.FirstSolutionStrategy.PATH_MOST_CONSTRAINED_ARC) # suboptimal
# routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION) # no assignment
# routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_INSERTION) # no assignment
# routing_enums_pb2.FirstSolutionStrategy.ALL_UNPERFORMED) # no assignment
# routing_enums_pb2.FirstSolutionStrategy.BEST_INSERTION) # no assignment
# routing_enums_pb2.FirstSolutionStrategy.CHRISTOFIDES) # no assginment
# routing_enums_pb2.FirstSolutionStrategy.SWEEP) # no assignment
# routing_enums_pb2.FirstSolutionStrategy.SEQUENTIAL_CHEAPEST_INSERTION) # no assignment

The time limit might be too short. Depending how big your problem is,
30s might not be enough time. However, I'm guessing this isn't an
issue here.

On the metaheuristic, I've never used the GENERIC_TABU_SEARCH, but
that isn't likely to be an issue here, as you aren't getting the
initial solution.

Finally, not sure why you are asking for a solution limit of 1. You
should either remove this and rely on your time limit to stop the tabu
search step, or else you should bump this up to a higher value. When
you put in a disjunction for the new destination, then the initial
solution will likely drop that destination, and will need to iterate
around to figure out how best to insert it. So quitting after the
first solution is not what you want.

Hope that helps,
James

On Tue, Sep 01, 2020 at 03:23:55PM +0200, Inti S. wrote:
> Well, I don't think there is any specific reason for it right now as long
> as it doesn't break any solution in any specific case, neither start or end
> tw for vehicles
> I guess it's there because of thousands of things I (or my team) tried to
> make it work as I need it. No effect removing it.
>
> Mizux answered me in the github topic before closing it, I don't completely
> understand what he said (if someone understands it):
>
> >

> > 1. *When you are adding new solution, the solver may not found an new
> > initial solution.*
> > 2. *When you add new node, did you use a disjunction ? sometime it's

> > better to start from the previous initial solution, then let the local

> > search try to insert the new location (if possible)*
> > 3. *If you add a new location without using disjunction, then your

> > previous solution is NOT an initial solution for the new problem since you

> > are not visiting the new mandatory location.*

> >>> *// Add time window constraints for each vehicle end node, which is the
> >>> depot.*
> >>>
> >>> *Let me know if that helps,*
> >>> *Cheers,*
> >>>
> >>> *Iván*

> >>> On Tuesday, 1 September 2020 at 03:06:58 UTC-3 I. Sanzol wrote:
> >>>
> >>>> Hello!
> >>>>
> >>>> Version: ortools-V2015-09.jar
> >>>> Language: Java
> >>>> Solver: Linear VRPTW
> >>>> Windows 10
> >>>>
> >>>> Initially posted at github (
> >>>> https://github.com/google/or-tools/issues/2142), but I've been told to
> >>>> ask here
> >>>>

> >>>> *My **problem:* No solution found when setting fixed time windows

> >>>> based on a previous solution and adding feasible locations
> >>>>
> >>>> I'm using a linear VRPTW with time windows also on vehicles
> >>>> A vehicle starts on depot and goes firstly to a node assigned to him
> >>>> with a fixed time window based on the start of his working day, then goes
> >>>> A->B->C->D....->last node (assigned with a fixed time window based on the
> >>>> end of his working day) and then depot
> >>>>
> >>>> When the solver gives a solution, I use the times given from that
> >>>> solution to set a fixed time windows to each location (imagine I call to my
> >>>> client to notify him that time), but when I add some new locations, it dont
> >>>> want to return any solution.
> >>>>
> >>>> Google api says it takes 139 minutes to go from Vehicle 12 node 70 to
> >>>> that new location (since 9:00), and that new location has a wide time
> >>>> window (until 15:00) so the location is highly feasible
> >>>>
> >>>> Find attached two minimum examples, one of them is working while the

> >>>> other (with 1 location more) is not, so *the question is: why is the
> >>>> solver not returning any solution?*

> >>>>
> >>>>
> >>>> I'm using time dimensions:
> >>>>

> >>>> * routing.addDimension(transitCallbackIndex, // transit callback*
> >>>>
> >>>> * 30000000, // allow waiting time*
> >>>>
> >>>> * 30000000, // vehicle maximum capacities*
> >>>>
> >>>> * false, // start cumul to zero*
> >>>>
> >>>> * "Time");*
> >>>>
> >>>> * RoutingDimension timeDimension =
> >>>> routing.getMutableDimension("Time");*

> >>>>
> >>>>
> >>>> Setting time windows is done this way:
> >>>>
> >>>>

> >>>> * // Add time window constraints for each location except depot.*
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> *for (int i = 1; i < timeWindows.length; ++i) {long index =

> >>>> manager.nodeToIndex(i);timeDimension.cumulVar(index).setRange(timeWindows[i][0],
> >>>> timeWindows[i][1]);}// Add time window constraints for each vehicle start

> >>>> node, which is the depot.for (int i = 0; i < vehicleNumber; ++i) {long

> >>>> index =
> >>>> routing.start(i);timeDimension.cumulVar(index).setRange(timeWindows[0][0],
> >>>> timeWindows[0][1]);}// Add time window constraints for each vehicle end

> >>>> node, which is the depot.for (int i = 0; i < vehicleNumber; ++i) {long

> >>>> index =
> >>>> routing.end(i);timeDimension.cumulVar(index).setRange(timeWindows[0][0],
> >>>> timeWindows[0][1]);}for (int i = 0; i < vehicleNumber; ++i)

> >>>> {routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));}*

> >>>>
> >>>>
> >>>> This is my solver config:
> >>>>

> >>>> * RoutingSearchParameters searchParameters =
> >>>> main.defaultRoutingSearchParameters()*
> >>>>
> >>>> *.toBuilder()*
> >>>>
> >>>>
> >>>> *.setFirstSolutionStrategy(FirstSolutionStrategy.Value.SEQUENTIAL_CHEAPEST_INSERTION)*
> >>>>
> >>>> *.setTimeLimit(Duration.newBuilder().setSeconds(30))*
> >>>>
> >>>>
> >>>> *.setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GENERIC_TABU_SEARCH)*
> >>>>
> >>>> *.setSolutionLimit(1)*
> >>>>
> >>>> * .build();*

> >>> <https://groups.google.com/d/msgid/or-tools-discuss/d41dc657-6c5e-412d-8fd2-90aa553dd674n%40googlegroups.com?utm_medium=email&utm_source=footer>
> >>> .

> >>>
> >> --
> > 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/rvnbHeftYzs/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/e3fc56a7-adb0-4144-9f5c-8f99d6f4fd7bn%40googlegroups.com
> > <https://groups.google.com/d/msgid/or-tools-discuss/e3fc56a7-adb0-4144-9f5c-8f99d6f4fd7bn%40googlegroups.com?utm_medium=email&utm_source=footer>
> > .
> >
>
> --
> 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/CA%2B-XnZbfCdqCDkjUEmDaFjw7XbnmgpPJPSJurywq5y8931h1Og%40mail.gmail.com.

--

James E. Marca
Activimetrics LLC

[Inti S.]

Wow, It seems to work

I have to do heavy tests but initially it gets solved, if this works I can't thank you enough

If it don't I'll reply here this week

So the explanation is (correct me if i'm wrong) : It initially calculates a solution unsuccessfully dropping every optional node, then it tries to put little by little optional nodes until it finds a solution (based on solution limit and solution time)

Also changed from sequential to parallel, this may solve many issues I was having, otherwise I'll post them separately as I'm dealing with them since may and I think I readed everywhere

Thank you!

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/20200901145952.GA1%40099d5fd9ec1a.

[Inti S.]

Well, this opens up a problem I already had while increasing solution limit from 1

Now my configuration is like:

    RoutingSearchParameters searchParameters =
        main.defaultRoutingSearchParameters()
            .toBuilder()

            .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PARALLEL_CHEAPEST_INSERTION)
            .setTimeLimit(Duration.newBuilder().setSeconds(30))
            .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GENERIC_TABU_SEARCH)
            .setSolutionLimit(1000)
            .build();

Changed sequential to parallel and solution limit from 1 to 1000

When I calculate a solution with wide time windows, it shows an initial solution. When I fix the time windows of the locations already solved BASED on the previous solution and try to recalculate it, it returns null as solution

i.e. for a node with a solution like "Vehicle 12 node 48 (659-720)" I fix that time window to 659-659 to fix the time

I tried to set solution limit 100.000 but it returns null solution almost instantly, I'll keep looking at it but I don't have idea what could be happening

If any ideas, please share with me

Thanks

El mar., 1 sept. 2020 a las 17:00, blind.lin...@gmail.com (<blind.lin...@gmail.com>) escribió:

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/20200901145952.GA1%40099d5fd9ec1a.

[I. Sanzol]

Update: (Sry for double post)

Tried to make every node optional when fixing time windows, but increasing time to 180 drops some nodes, it seems it can't find a solution.

Is there a way to pre-define the solution to make it solve faster?

Thanks!

[blind.line]

Quick guess is your time windows are too tight. 

Do a super small example that you can do by hand easily to check the calculations. 

James

On Sep 2, 2020, at 05:20, I. Sanzol <intis...@gmail.com> wrote:

Update: (Sry for double post)

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/2d4cae19-31ca-45d5-9d9d-0a0db51a0e6bn%40googlegroups.com.

[I. Sanzol]

Time windows are tight but possible (see below), 

I tweaked my application so I added 5 minutes to non-fixed time windows so that when I fix them, they should have 5 minutes less travel time to make it possible but it won't work.

Time windows with a small example before fixing them were this:

Vehicle 0 node 0 (0-0) 

Vehicle 0 node 2 (480-480) 

Vehicle 0 node 7 (540-691) (540 here. 49 travel to next, total 589)

Vehicle 0 node 9 (589-740) (589 here. 81  travel to next  , total 670)

Vehicle 0 node 12 (670-821) (670 here. 79  travel to next  , total 749)

Vehicle 0 node 16 (840-900) (840 here)

Vehicle 0 node 1 (1200-1200) 

Vehicle 1 node 0 (0-0) 

Vehicle 1 node 4 (480-480) 

Vehicle 1 node 18 (544-664)  (544 here. 77  travel to next  , total 621)

Vehicle 1 node 10 (621-840)  (621 here)

Vehicle 1 node 3 (1200-1200) 

Vehicle 2 node 0 (0-0) 

Vehicle 2 node 6 (480-480) 

Vehicle 2 node 8 (519-560) (519 here. 21  travel to next  , total 540)

Vehicle 2 node 17 (540-581)  (540 here. 71  travel to next  , total 611)

Vehicle 2 node 14 (630-652)  (630 here. 57  travel to next  , total 687)

Vehicle 2 node 13 (687-709) (687 here. 71  travel to next  , total 758)

Vehicle 2 node 15 (758-780) (758 here. 75  travel to next  , total 833)

Vehicle 2 node 11 (833-900) 

Vehicle 2 node 5 (1200-1200) 

As I understand, "Vehicle 0 node 7 (540-691)" means stay at 540 and you can wait until 691 to start the next travel but it depends on the previous travels. Anyways I'm fixing time window based on the first number (solution.min)

I didn't reproduce this problem in a simple case but having like 10 vehicles - 50 locations

[blind.line]

I haven’t looked in detail at your posts, but...I think there are two problems. First your time windows might be too tight. But maybe not if you’ve relaxed travel time as you said. Second I think you are giving the solver a problem with incredibly tight tolerances and asking it to find the solution. Like a bunch of needles in a pile...yes there might be a way to thread them as you want, but it is not likely the solver can find it easily given all the possible alternatives. 

I don’t understand why you’re not also feeding the solver your prior solution as the initial route in addition to your tight time windows. 

James

On Sep 3, 2020, at 02:50, I. Sanzol <intis...@gmail.com> wrote:

Time windows are tight but possible (see below), 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f1a63b74-9f29-45ee-a2ac-e7d1ce0696a7n%40googlegroups.com.

[I. Sanzol]

Yeah, that's what I asked in the last post but atm I don't know how to do it.

I've been busy checking everything to be sure that's the only problem

I thought that, by fixing time windows should be easier for the solver, as it is a solution already found by him, but I understand your point

I'm gonna google it and hopefully it helps, the bad thing is the routes should be defined but not fixed  to a specific vehicle (I imagine is not possible and I can discuss it with the client 'cause I guess it's not critical..)

Thank you for your reply

[I. Sanzol]

I confirm that does not solve my problem.

It seems to work for problems with less than 20 locations

Without fixing time windows, with predefined routes it won't solve, exact data input.

Solution without fixing anything:

Vehicle 0 node 0 (0-0) 

Vehicle 0 node 2 (480-480) 

Vehicle 0 node 30 (510-559) 

Vehicle 0 node 15 (651-700) 

Vehicle 0 node 20 (707-756) 

Vehicle 0 node 32 (791-840) 

Vehicle 0 node 1 (1200-1200) 

Vehicle 1 node 0 (0-0) 

Vehicle 1 node 4 (480-480) 

Vehicle 1 node 16 (540-565) 

Vehicle 1 node 29 (635-660) 

Vehicle 1 node 3 (1200-1200) 

Vehicle 2 node 0 (0-0) 

Vehicle 2 node 6 (480-480) 

Vehicle 2 node 36 (510-578) 

Vehicle 2 node 17 (652-720) 

Vehicle 2 node 25 (708-795) 

Vehicle 2 node 27 (956-1016) 

Vehicle 2 node 5 (1200-1200) 

Vehicle 3 node 0 (0-0) 

Vehicle 3 node 8 (480-480) 

Vehicle 3 node 31 (480-560) 

Vehicle 3 node 18 (640-720) 

Vehicle 3 node 22 (780-900) 

Vehicle 3 node 7 (1200-1200) 

Vehicle 4 node 0 (0-0) 

Vehicle 4 node 10 (480-480) 

Vehicle 4 node 35 (540-546) 

Vehicle 4 node 19 (567-573) 

Vehicle 4 node 21 (637-643) 

Vehicle 4 node 33 (723-729) 

Vehicle 4 node 26 (777-783) 

Vehicle 4 node 9 (1200-1200) 

Vehicle 5 node 0 (0-0) 

Vehicle 5 node 12 (480-480) 

Vehicle 5 node 28 (480-533) 

Vehicle 5 node 24 (607-660) 

Vehicle 5 node 11 (1200-1200) 

Vehicle 6 node 0 (0-0) 

Vehicle 6 node 14 (480-480) 

Vehicle 6 node 37 (544-664) 

Vehicle 6 node 23 (629-813) 

Vehicle 6 node 34 (840-900) 

Vehicle 6 node 13 (1200-1200) 

Exact data with pre-defined routes:

    final long[][] initialRoutes = {

            {2,30,15,20,32,1},

            {4,16,29,3},

            {6,36,17,25,27,5},

            {8,31,18,22,7},

            {10,35,19,21,33,26,9},

            {12,28,24,11},

            {14,37,23,34,13},

        };

    routing.readAssignmentFromRoutes(initialRoutes, true);

No solution found.

I think now I'm completely blocked here :/

[I. Sanzol]

Finally I ended up by fixing locations to specific vehicles this way:

routing.vehicleVar(node).setValue(vehicle);

Assigning it using makeEquality don't work

Finally, in resume I made the new locations optional with a high solution limit and assigning the fixed time windows location to specific vehicles

After deeply testing it, it seems it works

Thank you all

[blind.lin...@gmail.com]

Cool, glad to hear it. Nice idea to guide the solver to the solution
by fixing the vehicle as well as the time windows.

I was poking though some of the C++ examples yesterday for a different
reason, and noticed this snippet in cvrp_disjoint_tw.cc
```
routing.AddSoftSameVehicleConstraint(group, kSameVehicleCost);
```

So apparently one can encourage the solver to assign groups of
destinations to the same vehicle, without specifying exactly the
vehicle. Maybe this can apply in your case too?

(As a side note, the example programs often use lightly documented
tricks that are super helpful in certain situations.)

Regards,
James

> >>>>> solved *BASED on the previous solution* and try to recalculate it, it

> >>>>>> https://groups.google.com/d/msgid/or-tools-discuss/20200901145952.GA1%40099d5fd9ec1a

> >>>>>> .
> >>>>>>
> >>>>> --
> >>>> 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/2d4cae19-31ca-45d5-9d9d-0a0db51a0e6bn%40googlegroups.com
> >>>> <https://groups.google.com/d/msgid/or-tools-discuss/2d4cae19-31ca-45d5-9d9d-0a0db51a0e6bn%40googlegroups.com?utm_medium=email&utm_source=footer>

> >>>> .
> >>>>
> >>>> --
> >>> 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/f1a63b74-9f29-45ee-a2ac-e7d1ce0696a7n%40googlegroups.com
> >>> <https://groups.google.com/d/msgid/or-tools-discuss/f1a63b74-9f29-45ee-a2ac-e7d1ce0696a7n%40googlegroups.com?utm_medium=email&utm_source=footer>

> >>> .
> >>>
> >>>
>
> --
> 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/1c14916e-5d9c-423d-9b2a-ef14f4031d27n%40googlegroups.com.

[Inti S.]

Thanks for the idea. 

Unfortunately, if I let it change from one vehicle to another, fixed time windows (based on my program's logic) should change accordingly optimization based on ortools decision (i.e. not the whole route, but maybe change 1 location to another vehicle if it suits better) which I see it's not possible (or it may be hidden somewhere in the javadoc) as I have to fix to one vehicle if I want it to give me a solution

Cheers

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/20200904151822.GA1%40f8d28623015d.