Re: [OSRM-talk] points order

[Sasha Khapyorsky]

Hi Daniel,

That is really interesting, I will look deeper in this. Thanks for the point.

Sasha

On Mon, Aug 6, 2018 at 1:09 PM, Daniel Hofmann  wrote:
> Check out https://github.com/mapbox/node-or-tools#node-or-tools
>
> The pickup and delivery feature makes sure
> - the delivery location is served by the same car serving the pickup
> location
> - the delivery location is served after the pickup location
>
> For example for (pickup, delivery)-pairs (4, 12), (9, 8) you can set:
>
>   pickups: [4, 9],
>   deliveries: [12, 8]
>
> pickups Array with node indices for picking up good. The corresponding
> delivery node index is in the deliveries Array at the same position
> (parallel arrays). For a pair of pickup and delivery indices: pickup
> location comes before the corresponding delivery location and is served by
> the same vehicle.
>
> deliveries Array with node indices for delivering picked up goods. The
> corresponding pickup node index is in the pickups Array at the same position
> (parallel arrays). For a pair of pickup and delivery indices: pickup
> location comes before the corresponding delivery location and is served by
> the same vehicle.
>
> Hope that helps,
> Daniel J H
>
>
>
> On Sun, Aug 5, 2018 at 9:56 AM, Sasha Khapyorsky  wrote:
>>
>> Hi Guys,
>>
>> May be another "ordering" example: pickup and dropoff points . Let's
>> say I'm delivery man with 10 orders for today, each one should be
>> picked up first and dropped off later. This looks like 20 points TSP,
>> but there are also dependencies - some job(s) can be dependant from
>> another job(s). Any thoughts?
>>
>> I know, it is not really OSRM stuff, but related to the topic.
>>
>> Sasha
>>
>> On Sat, Aug 4, 2018 at 11:22 PM, Julien Coupey  wrote:
>> > Hi Valerio,
>> >
>> > In your example, if the 3 ordered points need to be visited in a row,
>> > then
>> > you can easily transform your problem into a TSP by treating them as a
>> > single "job". You'd just have to adjust the matrix by ensuring that from
>> > any
>> > other place, the cost to that job is the cost to the first point, and
>> > the
>> > cost from that job is the cost from the third point.
>> >
>> > HTH
>> > Julien
>> >
>> >
>> > On 02/08/2018 15:12, Valerio Paruscio 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@openstreetmap.org
>> >> https://lists.openstreetmap.org/listinfo/osrm-talk
>> >>
>> >
>> > ___
>> > OSRM-talk mailing list
>> > OSRM-talk@openstreetmap.org
>> > https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>> ___
>> OSRM-talk mailing list
>> OSRM-talk@openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>
> ___
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>

___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

Re: [OSRM-talk] points order

[Daniel Hofmann]

Check out https://github.com/mapbox/node-or-tools#node-or-tools

The pickup and delivery feature makes sure
- the delivery location is served by the same car serving the pickup
location
- the delivery location is served after the pickup location

For example for (pickup, delivery)-pairs (4, 12), (9, 8) you can set:

  pickups: [4, 9],
  deliveries: [12, 8]

- pickups *Array
*
with node indices for picking up good. The corresponding delivery node
index is in the deliveries *Array
*
at the same position (parallel arrays). For a pair of pickup and delivery
indices: pickup location comes before the corresponding delivery location
and is served by the same vehicle.

- deliveries *Array
*
with node indices for delivering picked up goods. The corresponding pickup
node index is in the pickups *Array
*
at the same position (parallel arrays). For a pair of pickup and delivery
indices: pickup location comes before the corresponding delivery location
and is served by the same vehicle.

Hope that helps,
Daniel J H



On Sun, Aug 5, 2018 at 9:56 AM, Sasha Khapyorsky  wrote:

> Hi Guys,
>
> May be another "ordering" example: pickup and dropoff points . Let's
> say I'm delivery man with 10 orders for today, each one should be
> picked up first and dropped off later. This looks like 20 points TSP,
> but there are also dependencies - some job(s) can be dependant from
> another job(s). Any thoughts?
>
> I know, it is not really OSRM stuff, but related to the topic.
>
> Sasha
>
> On Sat, Aug 4, 2018 at 11:22 PM, Julien Coupey  wrote:
> > Hi Valerio,
> >
> > In your example, if the 3 ordered points need to be visited in a row,
> then
> > you can easily transform your problem into a TSP by treating them as a
> > single "job". You'd just have to adjust the matrix by ensuring that from
> any
> > other place, the cost to that job is the cost to the first point, and the
> > cost from that job is the cost from the third point.
> >
> > HTH
> > Julien
> >
> >
> > On 02/08/2018 15:12, Valerio Paruscio 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@openstreetmap.org
> >> https://lists.openstreetmap.org/listinfo/osrm-talk
> >>
> >
> > ___
> > OSRM-talk mailing list
> > OSRM-talk@openstreetmap.org
> > https://lists.openstreetmap.org/listinfo/osrm-talk
>
> ___
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

Re: [OSRM-talk] points order

[Sasha Khapyorsky]

Hi Guys,

May be another "ordering" example: pickup and dropoff points . Let's
say I'm delivery man with 10 orders for today, each one should be
picked up first and dropped off later. This looks like 20 points TSP,
but there are also dependencies - some job(s) can be dependant from
another job(s). Any thoughts?

I know, it is not really OSRM stuff, but related to the topic.

Sasha

On Sat, Aug 4, 2018 at 11:22 PM, Julien Coupey  wrote:
> Hi Valerio,
>
> In your example, if the 3 ordered points need to be visited in a row, then
> you can easily transform your problem into a TSP by treating them as a
> single "job". You'd just have to adjust the matrix by ensuring that from any
> other place, the cost to that job is the cost to the first point, and the
> cost from that job is the cost from the third point.
>
> HTH
> Julien
>
>
> On 02/08/2018 15:12, Valerio Paruscio 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@openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/osrm-talk
>>
>
> ___
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk

___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

Re: [OSRM-talk] points order

[Julien Coupey]

Hi Valerio,

In your example, if the 3 ordered points need to be visited in a row, 
then you can easily transform your problem into a TSP by treating them 
as a single "job". You'd just have to adjust the matrix by ensuring that 
from any other place, the cost to that job is the cost to the first 
point, and the cost from that job is the cost from the third point.


HTH
Julien

On 02/08/2018 15:12, Valerio Paruscio 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@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk



___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

Re: [OSRM-talk] points order

[Daniel Patterson]

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 
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@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

[OSRM-talk] points order

[Valerio Paruscio]

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@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk