Find the shortest distance between a set of vans and a set of depots (Travelling Salesman Problem?)

[Joe_O]

Having another crack at posting this since as Tom rightly suggested, I was asking about my attempted solution rather than the actual problem.

I have a list of ~150 van locations and ~100 depot locations. I need to assign a van to each depot in such a way that the total distance between van and depot is as small as possible. Each depot must have a van assigned but each van does not need to be assigned a depot (I can have vans leftover). Input data is similar to the following (these are US postal regions).

data vans;
input van_no van_location $;
datalines;
1 WF10
2 LS6
3 HD4
;
run;

data depots;
input depot_no depot_location $;
datalines;
1 HX8
2 BD2
3 LS1
;
run;

I have so far been able to find the latitude and longitude of each location and have performed a cross join between VANS and DEPOTS in order to create each combination and I have then calculated the distance between each location. This looks similar to the below,

data van_depot_xjoin;
input van_no depot_no distance;
format distance 8.2;
datalines;
1 1 4.20
1 2 4.76
1 3 8.43
2 1 4.25
2 2 4.97
2 3 5.24
3 1 9.50
3 2 17.33
3 3 17.81
;
run;

I'm looking for help with how to proceed.

I was previously attempting a brute force approach where I simply find every possible combination, sum the total distance of each combination and then find the shortest. However, it was pointed out that there are 100! combinations so this is not a feasible solution with a dataset of this size. I've also tried transposing my joined dataset into a matrix with vans in one dimension, depots in the other and distances in the body. It feels like that should get me there but I'm just not sure what to do next.

From memories of old maths lessons, I remember that this is similar to the Travelling Salesman problem. I've tried searching for solutions to this but haven't been able to adapt one. Maybe it's just not possible in SAS. Any help is greatly appreciated.

[Joe_O]

Sorry- UK postal regions obviously.

[FreelanceReinh]

Hello @Joe_O,

This is a classic "optimal assignment problem" and the best SAS tools for it (to my knowledge) are available in SAS/OR, as suggested in my last (too late) reply in the other thread.

Do you have access to SAS/OR (or "SAS Optimization")? Submit

proc setinit;
run;

proc product_status;
run;

and check the log to find out.

If you can confirm that SAS/OR or Optimization is listed there (or is available somewhere else in your organization), one of the Super Users or Community Managers will hopefully move this question to the Mathematical Optimization, Discrete-Event Simulation, and OR subforum. PROC OPTGRAPH might be suitable as well, but requires SAS Enterprise Miner. Otherwise, the next step would be to investigate if algorithms in available SAS modules (e.g., genetic algorithms in SAS/IML?) can be applied to your problem.

[Joe_O]

Thanks for your reply! I checked proc setinit and to my surprise, we do have SAS OR. I have tried the solution below and it seems to do the business.

[PGStats · Accepted solution]

If you have SAS/OR, it's as simple as:

/* Give Vans and Depots distinct names */
data links;
set van_depot_xjoin;
length from to $10;
from = catx("-","Van",van_no);
to = catx("-", "Depot", depot_no);
run;

proc optnet links=links direction=directed;
data_links_var weight=distance;
linear_assignment out=assignment;
run;

proc print data=assignment; run;

[Joe_O]

Wow, it looks like this works. Thanks for your help. Such a simple solution after 2 days of trying and failing with the brute force approach.

So proc optnet is literally designed to find the optimal network? That's fantastic. I'll have a good read through the documentation so that I can understand how it works its magic.

[RobPratt]

Thanks for mentioning PROC OPTNET, @PGStats.  With SAS/OR in SAS 9 or SAS Optimization in SAS Viya, you can also use the network solver in PROC OPTMODEL:

proc optmodel;
   set <str,str> LINKS;
   num weight {LINKS};
   read data links into LINKS=[from to] weight=distance;
   set <str,str> ASSIGNMENTS;
   solve with network / direction=directed lap links=(weight=weight) out=(assignments=ASSIGNMENTS);
   print {<i,j> in ASSIGNMENTS} weight;
   create data out from [from to]=ASSIGNMENTS distance=weight; 
quit;

In SAS Optimization in SAS Viya, you can also use PROC OPTNETWORK or the Network Optimization action set:

proc optnetwork links=mycas.links direction=directed;
   linksvar weight=distance;
   lap out=mycas.out;
run;

All these approaches also support several other network algorithms, including TSP.

[andreas_lds]

Unfortunately i can't contribute anything useful, except for moving the question to OR/MS.