The travelling salesman problem
The WikiPedia defines the travelling salesman problem, or TSP, like this:
Given a number of cities and the costs of travelling from one to the other, what is the cheapest roundtrip route that visits each city and then returns to the starting city?
The problem is of considerable practical importance, apart from evident transportation and logistics areas. A classical example is in printed circuit manufacturing – scheduling of a route of the drill machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single machine job sequencing problem).
The most direct solution would be to try all the combinations and see which one is cheapest, but given that the number of combinations is N! (the factorial of the number of cities), this solution rapidly becomes impractical.
The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see the function problem article), and the decision problem version ("given the costs and a number x, decide whether there is a roundtrip route cheaper than x") is NP-complete.
The bottleneck traveling salesman problem is also NP-hard.