[OSRM-talk] points order

Daniel Patterson daniel at mapbox.com
Thu Aug 2 14:49:04 UTC 2018


Hi Valerio,

  What you're describing falls under the title of "Vehicle Routing Problem"
(https://en.wikipedia.org/wiki/Vehicle_routing_problem).  OSRM includes a
basic solver for the Travelling Salesman Problem solver with the `/trip`
API, but it doesn't have a lot of options - it will re-order all points to
the best order it can find, you can't set any constraints.

  The usual way this type of problem gets solved is in 3 steps:

    1. Generate a travel time matrix with the `/table` plugin.
    2. Feed that matrix, along with your additional constraints, into a
constraint solver, like https://github.com/VROOM-Project,
https://github.com/google/or-tools, or one of several commercial constraint
solvers that support VRP.  Whichever one has parameters for your particular
problem constraints.
    3. Use the returned coordinate order from the solver to request the
full route from `/route` using the final order of points as route waypoints.

  Implementing a fully-featured constraint solver for Vehicle Routing
Problems is a huge undertaking, and so far, we've considered it mostly
outside OSRM's responsibilities.

daniel


On Thu, Aug 2, 2018 at 6:14 AM Valerio Paruscio <valerio.paruscio at gmail.com>
wrote:

> Hi,
> i'm wandering if its possible to set the order of some points in the
> routing service.
> I mean, I need to keep 3 out of 10 points in a certain order, while the
> remaining 7 can be in whatever order.
> Is that possible
>
> Thank you very much
>
> Valerio
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20180802/bd1da4d2/attachment.html>


More information about the OSRM-talk mailing list