In standard vehicle routing problems, an optimal solution is found by building a set of routes to perform each visit and minimizing the cost of the routes. The cost of any vehicle is usually a linear combination of the length and duration of its route.

However, in the real world, the number of available vehicles may be limited or the distances so great that it may not be possible to perform all visits within the specified time windows. This may mean additional costs to the customer as a lack of stock leads to lost sales or a slowdown in a manufacturing line. This introduces a new type of cost into the solution, a cost based on the lateness of deliveries.

In Dispatcher, this type of problem can be modeled by "softening" the delivery deadlines by introducing an associated cost for "tardy" deliveries.

In soft deadline problems, the best delivery time is usually just the earliest possible delivery time. However, in some cases, costs can arise for early deliveries as well. For example, a customer may incur extra storage and handling expenses if a delivery is too early to be used immediately, or if it exceeds the customer's normal storage capacity.

The example in this chapter considers both late and early delivery costs. This substantially increases the difficulty, since making an initial delivery on time may cause subsequent deliveries to be late and costly; making the subsequent deliveries on time may cause the initial delivery to be costly as it is too early. Each visit in a route has more interdependencies; in some cases, it may be beneficial to have a vehicle wait to make a delivery.