Abstract:
We consider a variant on a pick-up and delivery problem with time windows, where both early
and late delivery of items is penalized. This problem arises from an application in the area
of defence, but has wider applications in delivery of perishable goods. We develop a heuristic
for this problem - decomposing the problem into a higher level problem assigning items to
be delivered to trips of vehicles (which we solve using tabu search) and a lower level problem
choosing optimal delivery times for these trips (which we solve by an exact iterative approach).
We compare this approach with an integer programming model. For quite small instances of
the problem, the associated integer programming problem cannot be solved, but testing on small
problems suggests the heuristic is a promising approach for finding good solutions.
