pgr_TSP() argument "end_id" doesn't work on MacOS and Ubuntu for PgRouting versions 2.6.2 ... 3.0.1

[AlexeyPechnikov]

Describe the bug
On MacOS in resulting routing sequence 1...N addresses the "end_id" node is N-1 sequential address instead of N. So we can't define the last address.

To Reproduce
Use pgr_TSP() function with defined "end_id" argument. With also defined "start_id" argument the "end_id" probably ignored.

Specifications (please complete the following information):
Use the commands:

SELECT version();
                                                      version                                                      
-------------------------------------------------------------------------------------------------------------------
 PostgreSQL 12.3 on x86_64-apple-darwin18.7.0, compiled by Apple clang version 11.0.0 (clang-1100.0.33.17), 64-bit

SELECT postgis_full_version();
                                                                       postgis_full_version                                                                        
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
 POSTGIS="3.0.1 ec2a9aa" [EXTENSION] PGSQL="120" GEOS="3.8.1-CAPI-1.13.3" PROJ="7.1.0" LIBXML="2.9.10" LIBJSON="0.14" LIBPROTOBUF="1.3.3" WAGYU="0.4.3 (Internal)"

SELECT pgr_version();
 pgr_version 
-------------
 3.0.1

SELECT pgr_version();
              pgr_version               
----------------------------------------
 (2.6.3,v2.6.3,b14f4d56b,master,1.72.0)

[AlexeyPechnikov]

On Ubuntu "end_id" is N-2 address (instead of N) when "start_id" is not defined and it's probably ignored when the both "end_id" and "start_id" arguments defined.

SELECT version();
                                                                version                                                                 
----------------------------------------------------------------------------------------------------------------------------------------
 PostgreSQL 10.12 (Ubuntu 10.12-0ubuntu0.18.04.1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0, 64-bit

SELECT postgis_full_version();
                                                                                                    postgis_full_version                                                                                                    
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 POSTGIS="2.5.2 r17328" [EXTENSION] PGSQL="100" GEOS="3.7.0-CAPI-1.11.0 673b9939" PROJ="Rel. 5.2.0, September 15th, 2018" GDAL="GDAL 2.4.0, released 2018/12/14" LIBXML="2.9.4" LIBJSON="0.12.1" LIBPROTOBUF="1.2.1" RASTER

SELECT pgr_version();
              pgr_version               
----------------------------------------
 (2.6.2,v2.6.2,b14f4d56b,master,1.65.1)

[cvvergara]

Can you give us a problem to reproduce please

[cvvergara]

@mobigroup If you can give us the query using the sample data of the documentation would be better.

[AlexeyPechnikov]

@cvvergara That's very easy to reproduce. See the code below where we have the same output for end_id := 1 and end_id := 2:

SELECT * FROM pgr_TSP(
    $$
	SELECT * FROM pgr_dijkstraCostMatrix(
		$___$
			SELECT
				1 as id, 1 as source, 2 as target, 1 as cost, 1 as reverse_cost
			UNION
			SELECT
				2 as id, 2 as source, 1 as target, 1 as cost, 1 as reverse_cost
		$___$,
		ARRAY[1,2],
		directed := false
	)
    $$,
    end_id := 1,
    randomize := false
);

seq	node	cost	agg_cost
1	1	1	0
2	2	1	1
3	1	0	2

SELECT * FROM pgr_TSP(
    $$
	SELECT * FROM pgr_dijkstraCostMatrix(
		$___$
			SELECT
				1 as id, 1 as source, 2 as target, 1 as cost, 1 as reverse_cost
			UNION
			SELECT
				2 as id, 2 as source, 1 as target, 1 as cost, 1 as reverse_cost
		$___$,
		ARRAY[1,2],
		directed := false
	)
    $$,
    end_id := 2,
    randomize := false
);

seq	node	cost	agg_cost
1	1	1	0
2	2	1	1
3	1	0	2

Note: we have different output for start_id := 1 and start_id := 2.

[cvvergara]

hmm, I see the same output in the two queries you posted.

[AlexeyPechnikov]

hmm, I see the same output in the two queries you posted.

Yes, that’s the same but it needs to be different because end_id is different in the queries above.

[cvvergara]

with start_id 1

SELECT * FROM pgr_TSP(
    $$
 SELECT * FROM pgr_dijkstraCostMatrix(
  $___$
   SELECT
    1 as id, 1 as source, 2 as target, 1 as cost, 1 as reverse_cost
   UNION
   SELECT
    2 as id, 2 as source, 1 as target, 1 as cost, 1 as reverse_cost
  $___$,
  ARRAY[1,2],
  directed := false
 )
    $$,
    start_id := 1,
    randomize := false
);
 seq | node | cost | agg_cost 
-----+------+------+----------
   1 |    1 |    1 |        0
   2 |    2 |    1 |        1
   3 |    1 |    0 |        2
(3 rows)

with start_id = 2

SELECT * FROM pgr_TSP(
    $$
 SELECT * FROM pgr_dijkstraCostMatrix(
  $___$
   SELECT
    1 as id, 1 as source, 2 as target, 1 as cost, 1 as reverse_cost
   UNION
   SELECT
    2 as id, 2 as source, 1 as target, 1 as cost, 1 as reverse_cost
  $___$,
  ARRAY[1,2],
  directed := false
 )
    $$,
    start_id := 2,
    randomize := false
);
 seq | node | cost | agg_cost 
-----+------+------+----------
   1 |    2 |    1 |        0
   2 |    1 |    1 |        1
   3 |    2 |    0 |        2
(3 rows)

So, here is what I see:
Suppose that a solution of a 4 node problem in terms is:

v1 -- v3 -- v4 -- v2 -- v1

when you want v3 to be the start_id the solution is:

v3 -- v4 -- v2 -- v1 -- v3

when you want the end_vid to be v4 (start_vid is v1 from the original problem)

v1 -- v3 -- v2 -- v4 -- v1

which forces v4 -- v1 (when v1 is the start_vid)

This would be ok

v3 -- v4 -- v2 -- v1 -- v3

The reason it is ok, is that the route can be written like

v3 -- v1 -- v2 -- v4 -- v3

[cvvergara]

I shouldnt have use ->, will change to --

[cvvergara]

In general,
given N 1 ...... N and w is one of them and is the furthest one from n1
maybe the algorithm chose the n1 as the first one
n1 ..................w................... , n1
when defining that w to be the end_vid what you are telling is to force this situation, and ignore the cost from w to n1
n1 ..........................................w, n1

[cvvergara]

Please tell me your thoughts

[AlexeyPechnikov]

Please tell me your thoughts

Here is issue for the end_id option. Why do you write about the different one (start_id)?

[cvvergara]

beacuse they are related
In general, a TSP solution looks like, (where s is chosen by the algorithm)
s, u...., v, ........................w , s

if you want the start_vid to be u for example, the the solution is just rotated to get that u as first node
u...., v, ........................w , s, u

but if you want the end_vid to be v where u...., v, ........................w , s, u is the best solution for tsp
then u............................w , s, v, u

So imagine a problem, the salesperson departs from the office, has to visit the customers and ends in his house
start_vid you would set to be the node of the office, and end_vid the node of the house

[AlexeyPechnikov]

Sorry, you are wrong. No, we can’t just replace end_id by start_id and reverse the route. Let’s think about the both options start_id and end_id defined at the same time.

[cvvergara]

Well I would need to read the code again but as far as my memory goes that is how it works.
(I didnt write the original signature of the function)
But
it needs a lot of unit tests:
if you can help me prepare unit tests, it would be cool:
A fixed input, what is the expected output
with very small examples like the ones you made
So instead of writing the output it currently gives, write what it is expected as result.
if you are up to this task, we can work it out on gitter chat

[AlexeyPechnikov]

Hi, maybe do you have some updates? I have the same results on MacOS and Linux for PgRouting 3.1.3.

[cvvergara]

@mobigroup Can you try develop branch with pgr_TSP?
we changed the code