3
$\begingroup$

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.

Here is some additional info about the problem:

  • 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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Godric Seer
    Aug 16, 2012 at 13:01
  • $\begingroup$ I do have travel distance between all pairs of nodes (I'll just use straight line). $\endgroup$
    – barelyknown
    Aug 16, 2012 at 13:33
  • $\begingroup$ 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. $\endgroup$
    – Aron Ahmadia
    Aug 17, 2012 at 19:51
  • $\begingroup$ 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 :) $\endgroup$
    – Aron Ahmadia
    Aug 17, 2012 at 19:59

1 Answer 1

Reset to default
2
$\begingroup$

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.

The linear programming approach would also guarantee a global optimum for you, but there is a glaring issue with the above formulation. Your decision variables are an integer for every pair of nodes. That turns your 29,000 nodes into just shy of 900,000,000 decision variables, which isn't exactly a trivial computational problem. Of course you could do things like remove pairs whose distance is above some threshold, which could greatly reduce the problem size, but make the implementation more complicated.

Also, for linear programming, I do not know what interfaces there are in ruby. I personally learned using glpk (a free solver) and pyomo (a python framework). The wikipedia page has a nice list of different free libraries.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the answer. What if I went for a non-optimal answer using a nearest-neighbor approach. How would you approach that? $\endgroup$
    – barelyknown
    Aug 16, 2012 at 15:03
  • $\begingroup$ If you wanted to loop through the locations with demand, then select the nearest supply to meet some/all of it. This doesn't give you any sort of optimality however, it would simply meet the constraints. I don't know if this is what you mean by nearest-neighbor. $\endgroup$
    – Godric Seer
    Aug 16, 2012 at 15:12
  • $\begingroup$ I think that I'm going to use that approach to see how sensible it looks (since I'm trying to approximate how things happen more than optimize the network). Then LP from there... $\endgroup$
    – barelyknown
    Aug 16, 2012 at 16:42
  • $\begingroup$ I can't guarantee how realistic/good the solutions will be. Also, I would guess there are others on this site that know of decent heuristics for this sort of problem. $\endgroup$
    – Godric Seer
    Aug 16, 2012 at 16:44
  • 1
    $\begingroup$ @Godric, technically, you are describing "integer programming", not "linear programming", but your description of the problem and general approach are good. An obvious thing to do here is sparsify the graph by only including, say, the 10 or 100 nearest neighbors for each vertex. The other clear thing to do is to not impose integer constraints. If you are interpreting these statistics as averages, then this can physically make sense anyway. This problem would them be computationally quite tractable. $\endgroup$
    – Aron Ahmadia
    Aug 17, 2012 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.