The generalized form of most logistics problems reduce to NP-complete, but we are also almost always working in a system with much more structure than the gener

The generalized form of most logistics problems reduce to NP-complete, but we are also almost always working in a system with much more structure than the general problem, so a polynomial time solution may be available. Also, many NP-complete problems can find 'near' optimal solutions in polynomial time. For example, consider the traveling salesman problem in a metric space. We can construct a minimum spanning tree in polynomial time, and we know that traversing this tree takes no more than twice as long as traversing an optimal solution to the traveling salesman problem. By using the triangle inequality, we can further optimize our solution, still in polynomial time.