 <p>As Baltimark said, this is basically a Linear programming problem. If only the coefficients for the shippers (1 for included, 0 for not included) were not (binary) integers for each leg, this would be more easily solveable. Now you need to find some (binary) integer linear programming (ILP) heuristics as the problem is NP-hard. See <a href="http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns" rel="nofollow noreferrer" title="Wikipedia on integer linear programming">Wikipedia on integer linear programming</a> for links; on my linear programming course we used at least <a href="http://en.wikipedia.org/wiki/Branch_and_bound" rel="nofollow noreferrer" title="Branch and bound">Branch and bound</a>.</p> <p>Actually now that I think of it, this special case is solveable without actual ILP as the amount of days does not matter as long as it is &lt;= 5. Now start by choosing the cheapest carrier for first choice (Conway 5:1000). Next you choose yet again the cheapest, resulting 8 days and 4000 currency units which is too much so we abort that. By trying others too we see that they all results days > 5 so we back to first choice and try the second cheapest (FedEx 2:3000) and then ups in the second and fedex in the last. This gives us total of 4 days and 9000 currency units.</p> <p>We then could use this cost to prune other searches in the tree that would by some subtree-stage result costs larger that the one we've found already and leave that subtree unsearched from that point on. This only works as long as we can know that searching in the subtree will not produce a better results, as we do here when costs cannot be negative.</p> <p>Hope this rambling helped a bit :). </p>