itinero / optimization Goto Github PK

We can make the SequenceEnumerable faster by using a circular pointer in the array instead of moving items:

https://github.com/itinero/optimization/blob/feature/cvrp/src/Itinero.Optimization/Tours/Sequences/SequenceEnumerable.cs

Is it possible to solve CVRP with fixed departure/arrival and weight constraint? If I add departure or arrival in CVRP-ND test Run1WechelderzandeCapacitated - I get "Object not set to an instance..." exception.

Hi !

After new version, i taking this error in Optimize method.

The entire error is as follows

The given model cannot be mapped by any of the registered mapppers: No vehicle found with a turn penalty..
Vehicle at index 0 could not be mapped: Departure location is in error: NotRoutable - Location could not routed to or from..

The same worked in the previous version. What does that mean ?

Hi!
I would like to ask if there is a way to pre assign the order of sequence for all of the locations. In this case we want only to calculate the time of arrivals and the route's path.
Thank you in advance

What is the best way to match the coordinates going into CalculateTSP with the resulting stops? I'd like to pass in attributes but it doesn't look like that is currently supported. Thanks.

Is there any documentation available for the Optimization library that I am missing. I am a bit confused about how to specify the solver you wish to use and when attempting to specify turn weighting it is giving me an error, which I assume is because it is using the wrong solver. Before I take a deep dive into the source code I figured I would check to see if there is documentation that I am missing.

Thanks in advance for any help or guidance!

Currently the router extensions in the optimization module only allow passing in a set of locations which are then resolved with a MassResolvingAlogrithm.

In our case we want to have more finely-grained control about the resolving before starting calculations. We also cache coordinates/routerpoints for improved performance as long as the router works on the same map.

The 'simplest' way I currently see this is as follows:

• added routerextension methods with routerpoints instead of coordinates (or both coordinates and routerpoints)
• use a 'pre-resolved' massresolver which just returns the preset coordinates/routerpoints
• append the model with routerpoints
• in MappedModel.BuildAbstract, use the new massresolver if the model has known routerpoints, otherwise keep as-is

This solution allows for this change to be limited to the optimization module and is quite small in scope to implement.

Alternatively this could be implemented further downstream as well by giving the WeightmatrixAlgorithm and DirectedWeightMatrixAlgorithm overrides which take routerpoints. There wouldn't be a custom massresolver then but the new overrides of the algorithms would just handle the passed routerpoints. This requires a change in both routing and optimization.

I'm happy to take this up myself. What do you think of the above approach(es)?

Hello I am trying to calculate a route with the algorithm TSP TW, but I do not understand the Time Window.

But I do not understand the Time Window.

I need to calculate the route with this data for example:

-> Departure: 41.2483368,-8.625592
-> Customer 1: 41.1915741, -8.627647 | 09h-> 18h
-> Customer 2: 41.1169434,-8.625565 | 09h-> 09h30h
-> Customer 3: 41.1220551,-8.603654 | 09h-> 18h
-> Customer 4: 41.122985, -8.605524 | 09h-> 18h

Client 2 should be the first but the program says that the first is the Customer 3, all time windows is 0 except Customer 2, time windows is 0 -> 1800.

Any help?

Thanks

Hi,

I want to use the Tsp with time windows restriction but i can not understand how to define the time window for the next example:
I have 4 points and each one have his time window:
point 1: 09:00 - 12:00
point 2: 08:30 - 11:00
point 3: 10:00 - 12:30
point 4: 14:00 - 17:00

Is it possible? how should i define the time window in TimeWindows.TimeWindow[] array?
I will appreciate for any help.

Regards
Ben

Migrate and refactor this VRP code from the old version in OsmSharp:

https://github.com/OsmSharp/ui/tree/supported/via/OsmSharp.Routing/VRP

Try to support:

• Time-constrained CVRP with one Depot.
• Time-constrained CVRP without a Depot.

I already have a distance matrix calculated. may I use the TSPRouter class with and already calculated distance matrix?

Hi. I would like to know how to go about optimizing a given route of say around 100 drop-off points with a fleet of 4 vehicles.

I am able to get the code working to optimize the route but how/where do I set a restriction to number of vehicles used for an optimization?

Thanks!

This is an issue to remind @xivk of creating a stable release after the new stable routing core has been released.

Hi,
We use the CalculateTspTW algorithm but we get a results that is not optimal in some cases - it return round trip route. For example:
We defined locations array with 9 coordinates, some of the points located in one city and others in other city (20 kilometers southern).
We have defined that all points will have the same 24-hour time windows: [min=0,max=86400]
As I mentioned the result is non optimal route - back and forth - The route passes through several points in the first city and then performs all the points in the second city and then returns to the first city to perform the other points. You can see images below.
The optimal route should pass through all the points in the first city and then perform the points in the second city. Especially when the time window is 24 hours.

Here the code:
`Coordinate[] locations = new Coordinate[]
{
new Coordinate((float)31.803462982177734,(float)34.64567184448242),
new Coordinate((float)31.798843383789062,(float)34.6540412902832),
new Coordinate((float)31.794118881225586,(float)31.794118881225586),
new Coordinate((float)31.78878402709961,(float)34.65801239013672),
new Coordinate((float)31.787199020385742,(float)34.662925720214844),
new Coordinate((float)31.651636123657227,(float)34.55881118774414),
new Coordinate((float)31.652114868164062,(float)34.55542755126953),
new Coordinate((float)31.776153564453125,(float)34.632301330566406),
new Coordinate((float)31.7714900970459,(float)34.63166046142578)
};

        var windows = new TimeWindow[]
        {
            new TimeWindow() { Max = 86400, Min = 0 },
            new TimeWindow() { Max = 86400, Min = 0 },
            new TimeWindow() { Max = 86400, Min = 0 },
            new TimeWindow() { Max = 86400, Min = 0 },
            new TimeWindow() { Max = 86400, Min = 0 },
            new TimeWindow() { Max = 86400, Min = 0 },
            new TimeWindow() { Max = 86400, Min = 0 },
            new TimeWindow() { Max = 86400, Min = 0 },
            new TimeWindow() { Max = 86400, Min = 0 }
        };

        route = router.CalculateTSPTW(Itinero.Osm.Vehicles.Vehicle.Car.Fastest(), locations, windows, 0);`

How we can avoid from the result of a round trip? I will appreciate for any help.

Round trip route:

Round trip route-ZOOM:

Optimal route:

Regards
Ronen

im currently using itenero to calculate the TSP Route.

I loaded the osm file (3gb) of Germany, converted it to a routing file (1GB).
The calculation works, but it needs 3 minutes for 4 stops, i tried to check it with 18 stops but this took to long.

It is restricted to "Vehicle.Car"
Are there more Options / Methods to increase the speed (40 stops should take not longer than 5 minutes)

var routerDb = new RouterDb();
routerDb.AddContracted(Vehicle.Car.Fastest());

            using (var stream = new FileInfo(routingFile).OpenRead())
            {
                routerDb = RouterDb.Deserialize(stream);
            }


var router = new Router(routerDb);
var route = router.CalculateTSP(Vehicle.Car.Fastest(), addresses.Select(x => x.Coordinate).ToArray());

Update to latest Itinero after profile changes:

itinero/routing#28

I'm getting the below error with Itinero.Optimization 1.0.0-pre003.

var router = new Router(routerDb);
var route = router.CalculateTSP(profile, points);

'Router' does not contain a definition for 'CalculateTSP' and no accessible extension method 'CalculateTSP' accepting a first argument of type 'Router' could be found (are you missing a using directive or an assembly reference?)

I am using:

using Itinero;
using Itinero.Optimization;
using Itinero.Osm.Vehicles;

Refactor out Pair and Triple enumerators after CVRP is merged.

Hi,
I'm experimenting with Time Windows.
I have a route that i want it to start at 8:00 am , with 80 stops without time windows and one with time window 12:00 -14:00.
I tried setting the time window to min =28800 (08:00) , max =61200 (17:00) to all stops except the one that I set it to min =43200 (12:00) , max = 50400 (14:00), but i seems like the time window is not working.
Any suggestions how to set the correct time windows for this route?

I used the version 0.14.5 of Itinero.Optimization.
When I need to optimize I used:
var routerTSP = new TSPRouter(new WeightMatrixAlgorithm(router, InstanceProfile, massResolver), 0);

I've updated the Itinero.Optimization library to the lastest beta and now the class TSPRouter is in Itinero.Optimization.Abstract.Solvers.TSP.Directed namespace only.

I'm missing something? How can I calculate a tour with undirected graph?

Thanks in advance

Hi there
Just did optimization with

IEnumerable<Result> mroute = router.Optimize(vp, visitList.ToArray(), out _, laction);

mroute does not list a single correct time frame fit. Briefly, driver starts at 8:00 AM and at 10:15AM should serve a certain stop. Nevertheless, the result shows the driver is at that stop in 15 .2 min (i.e. at 8:15), long before the time window starts. But driver is not idling and by 10:15 she servers 6 stops more. That's not correct.
If you want more details, I will be glad to attach.
Thanks

Calculations become impossible when the depot failed to resolve properly. In this case calculation needs to stop with a proper error message and not fail because the depot isn't set.

Hi.
Is there a way to specify that the Itinero or Optimization modules respect the correct side of the road of the destination points?

Thanks.

There is a relatively simple fast algorithm to obtain always best solutions to the directed sequence problem.

Triple and pair can be represented as a sequence with resp. 3 or 2 elements. This way, lots of functions can be generalized, resulting in less code duplication without performance loss.

I will experiment a little with a decorator.

After updating the Version 1.3.2 to version 1.5 (1.4 also) I can not use the TSP Router anymore.
The TryCalculateTSP Function is still there but the DoRun Function is not implemented anymore.

I see there is a alpha of logistics module but i did not find a implementation of the Optimize Function that allows to optimize. I will get only the route in the order of input.
Have you a Demo for Optimize with the new Version.

Ben, I'm trying TSP and I have this case:

With this set of coordinates if I try to calculate route everything is ok but when I try TSP 2 of these routes give the "Location could not routed to or from".
If you inspect the result you can see result.WeightMatrix.Errors = 2.

        var lat = new double[] { 45.516299000000, 45.342569300000, 45.420742000000, 45.506180600000, 45.506180600000 };
        var lon = new double[] { 9.011622100000, 9.275663400000, 9.112615900000, 8.986078000000, 8.986078000000 };

        IList<Coordinate> coo = new List<Coordinate>();
        for (var i = 0; i < lat.Length; i++)
            coo.Add(new Coordinate((float)lat[i], (float)lon[i]));
        TSPRouter routerTSP = new TSPRouter(new WeightMatrixAlgorithm(router, profile, coo.ToArray())); //, 0, coo.Count - 1);
        routerTSP.Run();
        Console.WriteLine(string.Format("End OptimizeTSP: has succeeded = {0}", routerTSP.HasSucceeded));

They are not used.

Hi,

I am trying to optimize 12 Points, the result is perfect the only issue is that it takes 2-3 mins, so my question is that normal? if not so, how can we improve Itinero optimization's performance:

                        var optimizationResult = router.Optimize(profile.ToString(),
                            pointsArray,
                            out IEnumerable<(int location, string message)> error,
                            0,
                            1);
                        break;

Thanks.

Hi there, I'm facing the follow error when try to install the Itinero.Optimization command through PM:

Install-Package : NU1108: Cycle detected.
Itinero.Optimization -> Itinero.Optimization (>= 0.21.0-beta).
At line:1 char:16

• Install-Package <<<< Itinero.Optimization -IncludePrerelease
  • CategoryInfo : NotSpecified: (:) [Install-Package], Exception
  • FullyQualifiedErrorId : NuGetCmdletUnhandledException,NuGet.PackageManagement.PowerShellCmdlets.InstallPackageCommand

Install-Package : Package restore failed. Rolling back package changes for 'Itinero.Optimization'.
At line:1 char:16

• Install-Package <<<< Itinero.Optimization -IncludePrerelease
  • CategoryInfo : NotSpecified: (:) [Install-Package], Exception
  • FullyQualifiedErrorId : NuGetCmdletUnhandledException,NuGet.PackageManagement.PowerShellCmdlets.InstallPackageCommand

https://github.com/itinero/optimization/blob/develop/src/Itinero.Optimization/Models/Metrics.cs#L6

=> make them all const.

Change to MIT license.

Is there a overview of all the VRP's you want to implement into the optimization package?
Are you planning to provide a more flexible solution to let people build their own constraints?

The idea is to set a custom time to a specific location in order to arrive at the time specified to that specific waypoint.

Hi,

I try using Itinero for solving a DTSP as shown below:

DirectedWeightMatrixAlgorithm directedWeightMatrixAlgorithm = new DirectedWeightMatrixAlgorithm(mRouter, Vehicle.Car.Fastest(), wgsCoordArray);

// wgsCoordArray has 15 elements in it

Itinero.Optimization.TSP.Directed.Solvers.HillClimbing3OptSolver directedhillClimbingSolver = new Itinero.Optimization.TSP.Directed.Solvers.HillClimbing3OptSolver();

directedTsprouter = new Itinero.Optimization.TSP.Directed.TSPRouter(directedWeightMatrixAlgorithm, 1.0f, 0, 15, directedhillClimbingSolver);

directedTsprouter.Run();
if (directedTsprouter.HasSucceeded)
    itineroTour = directedTsprouter.Tour; // {[0] -> 51 -> 11 -> 2 -> 39 -> 40 -> ... -> [12]}

Determination works fine but the result is unclear to me.
directedTsprouter.Tour contains obscure indices that do not correspond to the wgsCoordArray in any way.

I cannot find any hint in the documentation how to map the given indices back to the given wgsCoordArray.

Investigate a simple Pickup & Delivery version of the TSP.