[pgrouting-users] Multiple Origins/Multiple Destinations

pgRouting pgrouting-users
1

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

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 <spencergardner@gmail.com> 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
Pgrouting-users@lists.osgeo.org
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](http://georepublic.de)
Web: [https://georepublic.info](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