Fire Company Relocation
When a fire erupts in a city, units near the fire are dispatched to handle the fire. In doing so, they leave their firehouse empty. If another fire starts in the same area, a more distant unit must be summoned. If the unit is too far away, the house may be a smoldering pile of ashes by the time the unit arrives. In order to combat this, most cities have defined a minimal response requirement. Often, it is something like the following: of the three closest units to a fire call box (this example is taken from New York City, where call boxes are common), at least one must be available to handle a fire. As units respond to fires, other units may be temporarily moved into other quarters in order to meet this requirement. The difficulty is in determining which units to move where.
In a classic, mid 70s paper, Kolesar and Walker described a system in use in N.Y. for this problem. To simplify matters, let's just examine one piece of their system: determining which empty firehouses to use. A later stage will then determine which other companies to put in the firehouse. This method of breaking a problem up into pieces is a good meta-heuristic:
Break the problem up into solvable pieces. In general, first try to get a handle on critical aspects, leaving less important decisions to later pieces.
We can define a Response Neighborhood (RN) to be the aggregation of all areas with the same three closest firehouses. Suppose there are k uncovered RN's and there are l vacant firehouses that might service one or more of the RN's. Then an integer program to minimize the number of empty fire houses used is:
Minimize 
Subject to
for all i
where 
is 1 if house j is used (j runs from 1 to
l) and 
is 1 if location j covers RN i, where i runs
from 1 to k.
This model is known a a set covering model. Despite many, many papers on the subject, no algorithm is known which could solve it in an appropriate time (seconds) for the size of problems of interest (up to 40 firehouses and 100 RN's. Many people have worked on heuristics for this type of problem.
Try to use standard models so that much work has been done already. Then adapt for your particular application.
Vehicle Routing
In many industries, it is necessary to manage a fleet of trucks or other vehicles. A plan for each truck must be devised each day giving the customers (or Coke machines, or garbage dumps) that the vehicle must visit. The goal is to minimize some cost function, often by minimizing the distance travelled. This problem is difficult enough even for one truck and no further restrictions (the so-called Traveling Salesman Problem (TSP)). The problem gets even more difficult when there are multiple trucks, and restrictions on which customers a truck may visit. For instance, a truck might only be able to travel a certain number of miles, or visit a certain number of customers. Or customers might only be open for deliveries at set times, so the truck must arrive during these periods. The possibilities are endless.
In the rest of these notes, we will discuss methods for finding and improving solutions to problems like these. There are some things to worry about, though, when using heuristics. Let me describe one in story form.