Modified traveling salesman problem

[luboxing]

Greetings!

I am faced with a slightly modified TSP problem as below:

There are 4 nodes with directional values:

FRIDX	TOIDX	INC
1	2	-0.23548
1	3	-0.14027
1	4	-0.22685
2	1	0.014942
2	3	-0.02719
2	4	-0.11378
3	1	0.076665
3	2	-0.06068
3	4	-0.05206
4	1	0.059285
4	2	-0.07806
4	3	0.017148

However INC above is not the cost in a TSP problem. TO calculate the costs, here is another table:

Trip #	HIST_INC
1	-0.072240154
2	-0.075171085
3	-0.077492213

Where trip # represent the subtrip number traveling to all nodes above without return. That is, 4 -->2 --> 1 --> 3 requires 3 subtrips.

HIST_INC is a historical value for INC I want to align with by defining the cost as:

cost = sum (sq(INC - HIST)) for all 3 trips (across 4 nodes).

Therefore, the costs are not only determined by the starting and ending nodes and their directions, but also by the order of each subtrip within the entire iteration acorss all nodes. For example, the cost of subtrip from 4 to 1 could take any of the three values, depending on the order of the subtrip within the enture trip (without return):

sq(0.059285 + 0.072240154)

sq(0.059285 + 0.075171085)

sq(0.059285 + 0.077492213)

I hope my explanation is clear; if not I'd be glad to further clarify. I looked up PROC OPTNETWORK used it for a standard TSP, but no luck with this one.

Thanks in advance!

Bo

[RobPratt]

The standard TSP model does not allow time-dependent costs.  Instead, you can solve your problem as a side-constrained shortest path problem in a directed acyclic network with 18 nodes:

• (0,0): this is a dummy source node
• (i,t) for i in 1..4 and t in 1..4
• (5,5): this is a dummy sink node

The arcs are from (i,t) to (j,t+1), where i in 0..4, j in 1..5, and t in 0..4, and you can compute the arc costs according to your formula.

The decision variables are UseArc[i,j,t], and you need a flow balance constraint for each node, as well as a side constraint sum {<i,(j),t> in ARCS} UseArc[i,j,t] >= 1 for j in 1..4.

This approach is a simpler version of the one illustrated in the "Network Formulation" section of https://support.sas.com/resources/papers/proceedings14/SAS101-2014.pdf.

[luboxing]

Thanks for your quick reply, Rob! 

Could you help me with the syntax? I am a beginner with Proc optmodel and here is what I have so far. 

PROC OPTMODEL;
SET TS = 1..4;
SET IDX = 1..4;
NUM SOURCE = 0;
NUM SINK = 1 + MAX {I in IDX} I;
SET NODES = IDX UNION {SOURCE, SINK};
SET <NUM, NUM> ARCS INIT {};

NUM INCS {IDX, IDX};
NUM INCAVG {TS};
READ DATA DYINC_M INTO [I=FRIDX]{J IN IDX} <INCS[I,J]=COL('INC'||J)>;
READ DATA HISINCAVG_M INTO [DYIDX] INCAVG=INC;
VAR USEARC {ARCS} BINARY;

NUM COST {I IN IDX, J IN IDX, T IN TS} = (INCS[I,J] - INCAVG[T])**2;

MIN TOTALCOST = SUM{I IN IDX, J IN IDX} COST[I,J]*USEARC[I,J];

...

QUIT;

[RobPratt]

Here are the requested modifications to your code, together with optional PUT, PRINT, and EXPAND statements to help see what is going on:

data DYINC_M;
   input FRIDX TOIDX INC;
   datalines;
1	2	-0.23548
1	3	-0.14027
1	4	-0.22685
2	1	0.014942
2	3	-0.02719
2	4	-0.11378
3	1	0.076665
3	2	-0.06068
3	4	-0.05206
4	1	0.059285
4	2	-0.07806
4	3	0.017148
;

data HISINCAVG_M;
   input DYIDX INC;
   datalines;
1	-0.072240154
2	-0.075171085
3	-0.077492213
;

PROC OPTMODEL;
   num n = 4;
   SET TS = 1..n;
   SET IDX = 1..n;
   NUM SOURCE = 0;
   NUM SINK = 1 + MAX {I in IDX} I;
   SET NODES = (IDX cross TS) UNION {<SOURCE,0>, <SINK,n+1>};
   SET ARCS = 
      setof {i in IDX} <SOURCE,i,0>
      union
      setof {i in IDX, j in IDX diff {i}, t in TS} <i,j,t>
      union
      setof {i in IDX} <i,SINK,n>
   ;
   put NODES=;
   put ARCS=;

   NUM INCS {IDX, IDX};
   NUM INCAVG {TS};
   READ DATA DYINC_M INTO [FRIDX TOIDX] INCS=INC;
   print INCS;
   READ DATA HISINCAVG_M INTO [DYIDX] INCAVG=INC;
   print INCAVG;

   VAR USEARC {ARCS} BINARY;

   NUM COST {<i,j,t> in ARCS} = if t in 1..n-1 then (INCS[I,J] - INCAVG[T])**2;
   print cost;

   MIN TOTALCOST = SUM{<i,j,t> in ARCS} COST[i,j,t]*USEARC[i,j,t];

   con FlowBalance {<i,t> in NODES}:
      sum {<(i),j,(t)> in ARCS} UseArc[i,j,t] - sum {<j,(i),(t)-1> in ARCS} UseArc[j,i,t-1]
    = (if <i,t> = <SOURCE,0> then 1 else if <i,t> = <SINK,n+1> then -1 else 0);

   con VisitOnce {j in IDX}:
      sum {<i,(j),t> in ARCS} UseArc[i,j,t] = 1;

   expand;
   solve;
   print {<i,j,t> in ARCS: UseArc[i,j,t].sol > 0.5} cost;
QUIT;

The resulting optimal solution uses the following arcs:

[1]	[2]	[3]	COST
0	1	0	0.00000000
1	3	1	0.00462806
2	5	4	0.00000000
3	4	2	0.00053412
4	2	3	0.00000032

The corresponding path is 1->3->4->2.

[luboxing]

Thanks, Rob! I did encounter one error, however:

57 con FlowBalance {<i,t> in NODES}:
58 sum {<(i),j,(t)> in ARCS} UseArc[i,j,t] - sum {<j,(i),(t)-1> in ARCS} UseArc[j,i,t-1]
59 = (if <i,t> = <SOURCE,0> then 1 else if <i,t> = <SINK,n+1> then -1 else 0);
_
22
76
ERROR 22-322: Syntax error, expecting one of the following: IN, NOT, ~.

ERROR 76-322: Syntax error, statement will be ignored.

Any ideas?

[RobPratt · Accepted solution]

It looks like you are using an older version that does not support comparison of tuples.  I recommend upgrading, but until then here are three workarounds:

    = (if <i,t> in {<SOURCE,0>} then 1 else if <i,t> in {<SINK,n+1>} then -1 else 0);

    = (if i = SOURCE and t = 0 then 1 else if i = SINK and t = n+1 then -1 else 0);

   = (if i = SOURCE then 1 else if i = SINK then -1 else 0);

[luboxing]

Thanks, Rob! It works like a charm!

My actual usage has i=0..30, j=1-30, and t=1..30. With your code it takes around 15 seconds to solve.