# How should I calculate the average repositioning distance for empty trucks given known supply and demand at the postal code level?

I have calculated estimates of the daily supply of empty trucks and daily demand for empty trucks at the US postal code level. I would like to optimize the routing of supply to demand to minimize the total distance travelled. I would use that result to calculate the average repositioning miles required for a unit of demand in each postal code.

• There are approximately ~29,000 postal codes with either supply or demand.
• I'd like to vary the minimum demand that must be met, but it will always be close to 100%.
• A 100% optimal solution is not necessary.
• I'd like to solve this problem monthly from within a ruby program.
• Solving speed isn't extremely important.

How should I formulate the problem?

• What form is your distance information in? If you have a the travel distances between all pairs of nodes, I feel like linear programming would solve the problem. – Godric Seer Aug 16 '12 at 13:01
• I do have travel distance between all pairs of nodes (I'll just use straight line). – barelyknown Aug 16 '12 at 13:33
• I'm going to be the guy that says that Ruby is really not a great language to be solving a problem like this in. If you're looking for a freely available solution to code yourself for solving a problem like this, you might want to consider loosening this restriction. – Aron Ahmadia Aug 17 '12 at 19:51
• rglpk interfaces Ruby into the GNU Linear Programming Kit, but seems pretty alpha and not very actively developed, do let us know if you give it a try and how well it works out :) – Aron Ahmadia Aug 17 '12 at 19:59

Since you said you have the distances between all the nodes, one possibility would be linear programming. Formulating the program would be fairly straight forward. Your objective would be to minimize $\sum{c_{ij}t_{ij}}$ where $t_{ij}$ is the number of trucks sent from node i to node j and $c_{ij}$ is the distance. You would only have two constraints. The first constraint would be that $\sum_{\forall i}t_{ij}\ge D_{j}$ which states that the number of trucks from all sources to node j is greater than the demand at j. You could formulate a similar constraint for supply at each node.