Algorithm for generating an array of non-equal costs for a transport problem optimization

Question

I have an optimizer that solves a transportation problem, using a cost matrix of all the possible paths.

The optimiser works fine, but if two of the costs are equal, the solution contains one more path that the minimum number of paths. (Think of it as load balancing routers; if two routes are same cost, you'll use them both.)

I would like the minimum number of routes, and to do that I need a cost matrix that doesn't have two costs that are equal within a certain tolerance.

At the moment, I'm passing the cost matrix through a baking function which tests every entry for equality to each of the other entries, and moves it a fixed percentage if it matches. However, this approach seems to require N^2 comparisons, and if the starting values are all the same, the last cost will be r^N bigger. (r is the arbitrary fixed percentage). Also there is the problem that by multiplying by the percentage, you end up on top of another value. So the problem seems to have an element of recursion, or at least repeated checking, which bloats the code.

The current implementation is basically not very good (I won't paste my GOTO-using code here for you all to mock), and I'd like to improve it. Is there a name for what I'm after, and is there a standard implementation?

Example: {1,1,2,3,4,5} (tol = 0.05) becomes {1,1.05,2,3,4,5}

Answer 1

instead of comparing all the values to each other try a more linear approach:

danger! pseudo-code ahead...

seen = {}
for i=0:
  for j=0:
    if cost_matrix[i,j] in seen:
      cost_matrix[i,j] = cost_matrix[i,j]+percentage
    append cost_matrix[i,j] to seen
    j++
  i++

Answer 2

Not to be too picky, but I think you're describing a shortest path problem.

The "Transportation Problem" in OR is a much more specific problem with one set of origins and one set of destinations. In your problem, you have paths through several points, but sometimes you get two shortest paths because the costs add up to the same total. Right?

Here's a good paper on dealing with redundancy in all pairs shortest path problems.