Today I put a new video online showing an ongoing calculation of a No-depot CVRP, meaning, a Vehicle Routing Problem (VRP) that limits routes by capacity (C) and that has no depot.
The parameters in this problem are just one maximum time per route and a delivery time at each customer. OsmSharp will calculate a solution to this problem either using a genetic algorithm or a variable neighbour search method.
How can all this be done using OsmSharp?
There are a few steps that need to be taken first.
- Do you start from a list of adresses then you will have to Geocode them first. You can use any existing API out there including Nominatim (using OpenStreetMap data). An upcoming feature in OsmSharp will also support geocoding, but in a simpler form compared to Nominatim.
- The second step is to get the OSM data for your area. If your area of interest is small enough you can just use the export tab on the OSM website, if not just use one of the download pages on the wiki and export your area.
- Once the data is available you can use this to calculate a giant matrix of weights between all your datapoints containing the travel times between each pair of points. This can be done by using the default router class and calling CalculateManyToManyWeights similar to the default routing tutorial.
- Last but not least a genetic algorithm or variable neighbourhood search can be used to search a solution. The genetic algorithm will perform better but is slower and can only be applied to problems of about 500 datapoints or less.
- IRouter<RouterPoint> router; // the router should have been created already.
- double weights; // the weights should be calculated already.
- RouterPoint points; // the resolved points should also be available already.
- // parameter tuning defaults. You can play around with these if you think this might
- // improve performance but be sure to read up on genetic algorithms first!
- double elitism_percentage = 5;
- double cross_percentage = 80;
- double mutation_percentage = 10;
- int population = 40;
- int stagnation = 75;
- // the two parameters for the problem.
- Second max_time = 5400; // 5400 seconds.
- Second delivery_time = 20; // 20 seconds.
- // create the vrp-router.
- var vrp_router = new MaxTimeRouterWrapper<RouterPoint>(
- new RouterGeneticSimple(max_time, delivery_time, population, stagnation,
- elitism_percentage, cross_percentage, mutation_percentage,
- // call the router and calculate the end result.
- OsmSharpRoute real_routes = vrp_router.CalculateNoDepot(VehicleEnum.Car, points, weights);
The results can be saved as GPX file or routing instructions could be generated. All information can also be serialized and saved to any database.
To show the intermidiate solutions you can hook to an event that spits them out as they are available:
- vrp_router.IntermidiateResult+=new OsmSharp.Routing.Core.VRP.RouterVRPWrapper<RouterPoint,RouterMaxTime>.