Implementation of routing with multiple stops using Pgrouting

Question

I have a network and pgrouting works well on it. I want to route from a start point and car stops at set of points as {point 1, point2, point3 etc}. there is not any order in destination points. well one way is as below:

1. find nearest point to start point and call it p1
2. route from start point to p1
3. find nearest point to p1 and call p2
4. route from p1 to p2
5. etc

well I could do this but results are not optimize.

Is there any better solution for this problem?

Answer 1

Here is the basic approach.

If you want to approximate the best order to visit your points, you would first use TSP (Travelling Salesman Problem) algorithm:

Let's say your table of points of interest is called pois. It has fields something like

id, geom, name, closest_node

closest_node is node id from your network that you computed to be closest to each point of interest.

If you are working within a small region, using long/lat units is fine for your geom, though using a measurement preserving spatial ref such as UTM or LAEA is always better.

Let's say you want to go from poi of id = 2 to poi of id = 7, you'd run a query something like

-- note if your start and end are the same then you might have 7,7 instead of 2,7

-- the id1, you can ignore since it's internal id in computed distance matrix, id2 correspondes to your visit_pois.id, and seq is the order you should visit each location, based on cartesian distance approximation.

WITH 
    T AS (SELECT * 
       FROM pgr_tsp($$SELECT id, ST_X(geom) AS x, ST_Y(geom) AS y 
        FROM visit_pois$$, 2, 7)
    )
 SELECT T.seq, T.id2 AS id, N.closest_node, n.name
    FROM T INNER JOIN visit_pois N ON T.id2 = N.id;

--next step is to insert this into pgr_dijkstraVia. pgr_dijkstraVia is a function that given an order of nodes to visit as an array will compute the full travel, going from one node to the next to the next in that order.

Note the seq from TSP tells us the approximate order we should visit each location which is why we order by TN.seq. I assumed you edges table network is called ways, but you should change it to match your network edges table.

I'm going to wrap the above in a CTE called TN

WITH 
    T AS (SELECT * 
       FROM pgr_tsp($$SELECT id, ST_X(geom) AS x, ST_Y(geom) AS y 
        FROM visit_pois$$, 2, 7)
    ), 
 TN (SELECT T.seq, T.id2 AS id, N.closest_node, n.name
    FROM T INNER JOIN visit_pois N ON T.id2 = N.id
    ) 
SELECT r.*, TN.name
    FROM pgr_dijkstraVia(
    $$SELECT gid AS id, source, target, cost
    FROM ways$$,
        ARRAY(SELECT TN.closest_node
        FROM TN
        ORDER BY TN.seq)
    ) AS r INNER JOIN TN ON r.node = TN.closest_node;

Note the example query above only joined back with TN, but if you want to show the route on a map for example, you'll want to join back with your edge or edge vertices table.