Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

🔒 This topic is **solved** and **locked**.
Need further help from the community? Please
sign in and ask a **new** question.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Posted 01-13-2021 12:08 PM
(548 views)

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.

1 ACCEPTED SOLUTION

Accepted Solutions

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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;
```

PG

7 REPLIES 7

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Sorry- UK postal regions obviously.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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;
```

PG

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

Registration is open! SAS is returning to Vegas for an AI and analytics experience like no other! Whether you're an executive, manager, end user or SAS partner, SAS Innovate is designed for everyone on your team. Register for just $495 by 12/31/2023.

**If you are interested in speaking, there is still time to submit a session idea. More details are posted on the website. **

Multiple Linear Regression in SAS

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.