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.
... View more
