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.
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;
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.
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;
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.
Unfortunately i can't contribute anything useful, except for moving the question to OR/MS.
Are you ready for the spotlight? We're accepting content ideas for SAS Innovate 2025 to be held May 6-9 in Orlando, FL. The call is open until September 16. Read more here about why you should contribute and what is in it for you!
Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.
Find more tutorials on the SAS Users YouTube channel.