I cannot find a solution to a "simple" problem.

[Jens Magnus Mogensen]

Hey

Okay so I've the example from from https://developers.google.com/optimization/routing/vrptw.

If I change the time matrix to

public long[,] TimeMatrix = { {0, 16 }, {16, 0 } };

which is calculated using some addresses through Google's matrix API to get corresponding minutes between locations. I've about 100 locations in total, but I've simplified the example here, since that doesn't even work. I cannot figure out what is wrong? Can anybody be so kind as to explain why it does not work? Even if I try with 2, 3, 4 and 5 locations it still doesn't work, so I took the simplest example here.

I've set the time windows to allow any time of day, so it shouldn't be a problem. I'm using the C# wrapper and the latest version. 

[blind.line]

Hard to guess based on the information you’ve shared. If you post runnable code or share a link t a gist it will be easier to spot your error. 

Regards,

James

On Aug 30, 2021, at 09:48, Jens Magnus Mogensen <je...@cfx.dk> wrote:

Hey

--
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/240d583b-3d5f-40fe-ab50-9c58e2442b78n%40googlegroups.com.

[Jens Magnus Mogensen]

Hey James

This is a link to my gist: https://gist.github.com/JensMagnus/89da3036b1bd7e99cf1bcd5667a66ff7
Its the same as the example from the developers page, but I've modified it to accept some sort of DTO that matches the Google Matrix API response and then it proceeds to build the matrix. Here's the data I've been testing with, in a 8x8 grid.

0 16 4 9 15 14 8 24

16 0 13 21 15 15 11 16

4 13 0 11 12 11 4 20

10 22 12 0 15 13 14 22

15 15 12 13 0 1 14 10

14 15 11 12 1 0 13 10

8 11 5 13 14 13 0 18

25 18 21 21 11 11 19 0

I've attempted to change the vehicle(s) from 1 to 8 to no avail.

Notes:

• The time matrix is overridden (DataModel), so that it uses my time matrix instead of the 16,0 example I gave.
• I don't have any time constraints added to ease the possibility for a solution (doesn't work with a valid and doable timetable)

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

One thing I noticed is that you've set time windows to be empty, but
then you say:

```
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.VehicleNumber; ++i)
{
long index = routing.Start(i);
timeDimension.CumulVar(index).SetRange(data.TimeWindows[0, 0], data.TimeWindows[0, 1]);
}
```
not sure why that isn't throwing an error of some sort.

Second, you are allowing at most one iteration:

```
searchParameters.SolutionLimit = 1;
searchParameters.TimeLimit = new Google.Protobuf.WellKnownTypes.Duration() { Seconds = TimeSpan.FromDays(1).Seconds};
```

One second is probably fine, but I believe solution limit = 1 means
just run the solver for one iteration, which might not produce a
solution.

Hope that helps,
James

On Mon, Aug 30, 2021 at 10:48:18AM -0700, Jens Magnus Mogensen wrote:
> Hey James
>
> This is a link to my
> gist: https://gist.github.com/JensMagnus/89da3036b1bd7e99cf1bcd5667a66ff7
> Its the same as the example from the developers page, but I've modified it
> to accept some sort of DTO that matches the Google Matrix API response and
> then it proceeds to build the matrix. Here's the data I've been testing
> with, in a 8x8 grid.
>
> 0 16 4 9 15 14 8 24
> 16 0 13 21 15 15 11 16
> 4 13 0 11 12 11 4 20
> 10 22 12 0 15 13 14 22
> 15 15 12 13 0 1 14 10
> 14 15 11 12 1 0 13 10
> 8 11 5 13 14 13 0 18
> 25 18 21 21 11 11 19 0
>
> I've attempted to change the vehicle(s) from 1 to 8 to no avail.
>
> Notes:
>

> - The time matrix is overridden (DataModel), so that it uses my time

> matrix instead of the 16,0 example I gave.

> - I don't have any time constraints added to ease the possibility for a

> > <https://groups.google.com/d/msgid/or-tools-discuss/240d583b-3d5f-40fe-ab50-9c58e2442b78n%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/341e2ed0-3328-4754-8e80-380eb3903c75n%40googlegroups.com.


--

James E. Marca
Activimetrics LLC

[Jens Magnus Mogensen]

I commented out the lines:

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

            for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)

            {

                long index = manager.NodeToIndex(i);

                timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);

            }

            // Add time window constraints for each vehicle start node.

            for (int i = 0; i < data.VehicleNumber; ++i)

            {

                long index = routing.Start(i);

                timeDimension.CumulVar(index).SetRange(data.TimeWindows[0, 0], data.TimeWindows[0, 1]);

            }

And even 

            // Instantiate route start and end times to produce feasible times.

            for (int i = 0; i < data.VehicleNumber; ++i)

            {

                routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i)));

                routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));

            }

But it still does not work. I tried running it again with a feasible time window configuration.

searchParameters.SolutionLimit = 1; 

I tried changing it to 100000 and 0, but it still won't solve the problem.

I've also upped the 

 routing.AddDimension(transitCallbackIndex, // transit callback

                                 120,                   // allow waiting time

                                 15000,                   // vehicle maximum capacities

                                 false,                // start cumul to zero0

                                 "Time");

settings to some absurdly high values to increase the chance of success. 

I just attempted to use the example solution from https://developers.google.com/optimization/routing/vrp#c_4 with my own set of times and it still won't give me a solution...

Just to completely rule out any "wrongly or unfair" time windows.

[blind.line]

Some suggestions:

Start with example code make sure it runs. 

Cut the destinations in the distance matrix to match your test case, see if it runs. 

Change a single number in the distance matrix, see if it runs. 

Etc etc and so on and so on. 

At some point it will stop running. There is the issue. 

Also turn on logging output in the settings so you can see what is happening. 

My current guess is that you have a mismatch between what you are doing in the distance matrix and what the solver expects…like the scale of the real distances are wrong compared to your dimension’s limits. 

Also you never show what the output actually looks like. What do you mean by “won’t give me a solution”?

James

On Aug 31, 2021, at 09:28, Jens Magnus Mogensen <je...@cfx.dk> wrote:



To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e5faf79c-59d4-4631-ac5d-10570640a2a9n%40googlegroups.com.

[Jens Magnus Mogensen]

Hey again

Sorry for the late reply

The example from https://developers.google.com/optimization/routing/vrptw runs just fine with 1 or 4 vehicles.

Reducing the example to half (8) works just fine. Now if I reduce it all the way down to 1 delivery;

https://i.imgur.com/gOsnPdi.png it works with the example given... now if I change these ways to match an actual example from my problem (changed from 6 minutes to 17 each way): blob:https://imgur.com/f95eb2c3-22f8-4c22-9b25-40a5e87daa77

I don't know how to turn on logging. I've searched far and wide, and even attempted to check all the methods on all objects...

When I say I don't see a solution it's because Console.WriteLine(routing.GetStatus()) tells me "2"; which accordingly to this is: 

https://developers.google.com/optimization/routing/routing_options#search-status "no route found" Secondly, the "PrintSolution" method in the example crashes on a null-reference (since "solution" is null) Best regards.

[blind.line]

For the search logging, go to 

https://developers.google.com/optimization/routing/tsp?hl=en#search_strategy

Scroll to the bottom, looking for Changing the Search Strategy

James

On Jan 4, 2022, at 14:25, Jens Magnus Mogensen <je...@cfx.dk> wrote:

Hey again

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7784329c-f6da-4062-a04d-d923e88abb3en%40googlegroups.com.

[Jens Magnus Mogensen]

Hello

Thanks for the reply.

Just to clarify some stuff here's what I'm actually entering;

TimeMatrix is time in minutes between destinations (calculated using distance matrix in Google Maps, and then using the "duration" field")

TimeWindows is the time of day?

public long[,] TimeMatrix = {

            { 0, 15 },
            { 15, 0 }
        };
        public long[,] TimeWindows = {
            { 0, 5 },   // depot
            { 5, 23 },  // 1
        };

I read this as "delivery between 5 am and 23 pm", but start at depot between 0 am and 5 am?

The above example works fine, but as soon as my minutes (TimeMatrix) between points start to exceed 15 (minutes) I get an error;

WARNING: Logging before InitGoogleLogging() is written to STDERR
I0105 17:05:11.260917  9844 search.cc:264] Start search (memory used = 34.70 MB)
I0105 17:05:11.261915  9844 search.cc:264] End search (time = 1 ms, branches = 0, failures = 2, memory used = 34.82 MB, speed = 0 branches/s)

[blind.line]

Units must be consistent. 

The solver is just a program…it knows nothing of minutes or seconds. 

Time windows and time matrix are the same units. If you say that time matrix is in minutes, then do is time windows. 

So you are saying the depot window is from 0 to 5 minutes, and the depot is from 5 minutes to 23 minutes. 

James

On Jan 5, 2022, at 08:07, Jens Magnus Mogensen <je...@cfx.dk> wrote:

Hello

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/b3f33aed-be51-4832-ae29-5515c5edc479n%40googlegroups.com.

[Jens Magnus Mogensen]

Hey again

Thanks for the clue, that was not obvious to me in any way! All my times are now in minutes.

Either I simply don't get how it works or it's broken. Here's the example I am trying now:

 public long[,] TimeMatrix = {
            { 0, 16 },

            { 16, 0 },

        };
        public long[,] TimeWindows = {

            { 0, 180 },   // depot
            { 5, 180 },  // 1
        };
        public int VehicleNumber = 1;
        public int Depot = 0;

This should be easily solvable. Here's how I read it;

Be at the depot between 0 and 180 (minutes). It takes 16 minutes to get to objective 1, which we'll have to reach 5 - 180 minutes from now.

Isn't this correctly understood? Or am I missing (yet) another piece...

WARNING: Logging before InitGoogleLogging() is written to STDERR

I0112 23:05:13.020190 15096 search.cc:264] Start search (memory used = 34.19 MB)
I0112 23:05:13.021093 15096 search.cc:264] End search (time = 1 ms, branches = 0, failures = 2, memory used = 34.32 MB, speed = 0 branches/s)

[Mizux Seiha]

could you provide a repo or a gist with a full reproducible example instead ?

[Jens Magnus Mogensen]

Hey

Here you go: https://gist.github.com/JensMagnus/70e665657012188cd0445308642cc468

This is practically just the example from the documentation.

[Jens Magnus Mogensen]

Any suggestions?