Next: Car 54
Up: Applications of LP
Given a set of cities, find the shortest route that visits
each city exactly once and returns to the home city.
- Vehicle routing -- eg, how do we route
school buses to pick up children, how do Federal Express
and UPS assign packages to trucks?
- VLSI chip board manufacturing:
holes need to be drilled on the board. How do we route the
drill to visit all these holes so it takes the shortest
Largest problem solved to date has more than 13000 cities.
John E Mitchell