[pgrouting-users] Multiple Origins/Multiple Destinations

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[pgrouting-users] Multiple Origins/Multiple Destinations

Spencer Gardner-2
Is there an efficient strategy for obtaining the shortest route from multiple origins to multiple destinations?

To be clear, I'm not talking about returning a shortest route for the pairing of each origin to each destination. (This is the current behavior when arrays are passed in for start and end vertices.) What I am talking about is returning a single shortest route that represents the shortest of all possibilities between the origin and destination vertices.

I hope that makes sense.

Thanks,
Spencer

_______________________________________________
Pgrouting-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-users
Reply | Threaded
Open this post in threaded view
|

Re: [pgrouting-users] Multiple Origins/Multiple Destinations

Vicky Vergara-2
Hello Spencer:

Do you mean something like pgr_TSP? that visits all the nodes?
http://docs.pgrouting.org/2.4/en/pgr_TSP.html#pgr-tsp

if you mean something like TSP, take into account that TSP is an NP-problem, so it will not give "the shortest" route that visits all the nodes, but "a" route that visits all the nodes that is a local minimum.
Suppose you used the pgr_dijkstraCostMatrix as input to pgr_TSP, once you have the ordering of the visits, you can get the path by calling pgr_dijkstraVia

http://docs.pgrouting.org/2.4/en/pgr_dijkstraCostMatrix.html#pgr-dijkstracostmatrix
http://docs.pgrouting.org/2.4/en/pgr_dijkstraVia.html#pgr-dijkstravia

regards
Vicky

On Thu, Mar 30, 2017 at 11:18 AM, Spencer Gardner <[hidden email]> wrote:
Is there an efficient strategy for obtaining the shortest route from multiple origins to multiple destinations?

To be clear, I'm not talking about returning a shortest route for the pairing of each origin to each destination. (This is the current behavior when arrays are passed in for start and end vertices.) What I am talking about is returning a single shortest route that represents the shortest of all possibilities between the origin and destination vertices.

I hope that makes sense.

Thanks,
Spencer

_______________________________________________
Pgrouting-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-users



--
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44, 
81739 München, Germany

Vicky Vergara
Operations Research

eMail: vicky@georepublic.de
Web: https://georepublic.info

Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl


_______________________________________________
Pgrouting-users mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-users