Exact Algorithms for the Vehicle Routing Problem with Soft Time Windows

This paper studies a variant of the Vehicle Routing Problem with Soft Time Windows (VRPSTW) inspired by real world distribution problems. Soft time windows constraints are very common in the distribution industry, but quantifying the trade-off between routing cost and customer inconvenience is a hard task for practitioners. In our model, practitioners impose a minimum routing cost saving (to be achieved with respect to the hard time windows solutions) and ask for the minimization of the customer inconvenience only. We propose two exact algorithms. The first algorithm is based on standard branch-and-cut-and-price. The second algorithm uses concepts of bi-objective optimization and is based on the bisection method.