The opportunity cost of time window violations

This paper studies a variant of the vehicle routing problem with soft time windows (VRPSTW), inspired by real-world distribution problems. In applications, violations of the prescribed delivery time are commonly accepted. Customers’ inconvenience due to early or late arrival is typically modelled as a penalty cost included in the VRPSTW objective function, added to the routing costs. However, weighting routing costs against customer inconvenience is not straightforward for practitioners. In our problem definition, practitioners evaluate solutions by comparison with the hard time windows solution. The desired routing cost saving is set by the practitioners as a percentage of the nominal solution’s routing costs. The objective function minimizes the time window violations, or the customer inconvenience, with respect to the nominal solution. This allows practitioners to quantify the opportunity cost (i.e. the customer inconvenience), when a target routing cost saving is imposed. To solve the problem, we apply two exact algorithms: the first is based on a standard branch-and-cut-and-price (BCP), the second is a BCP nested in a bisection algorithm. Computational results demonstrate that the second algorithm outperforms the standard implementation. Solutions obtained with the opportunity cost interpretation of soft time windows are then compared with solutions obtained using both hard time windows and the standard interpretation of soft time windows.