The impact of soft time windows with penalties on the objective values of large real-world Vehicle Routing Problems

More Info


In a Vehicle Routing Problem with Time Windows (VRPTW), orders have to be picked up and delivered within certain time windows. In practice, planners often allow violations of these time windows, when the solutions with violations have better objective values. This is done by changing the problem into a Vehicle Routing Problem with Soft Time Windows (VRPSTW). In this thesis, the effect of soft time windows on the objective values of a real-world VRP is analysed for multiple single-day cases of a distribution company. The used algorithm is a heuristic, based on local search methods. At first, a sensitivity analysis is performed on the sensitivity of the number of planned tasks to the time window tolerance. The addition of time window tolerance increases the number of planned tasks in most of the cases. Furthermore, when the tolerance increases, the number of planned tasks generally increases as well, until the number of planned tasks is equal to the number of tasks that is planned when the time windows are completely removed. In the second part of the experiments, trade-offs between the cost function and the amount of violation are investigated, by varying the slope of the linear penalty function (for a fixed tolerance). In general, a higher penalty leads to a lower amount of violation and a higher cost (without penalties), but this is not a monotone correlation. For the smaller cases, the costs can be lowered by 4.8% to 9.0%. To reach this minimum cost, an average violation of 1 to 7 minutes per task has to be accepted. For the bigger cases, only the lowest penalty values lead to a cost improvement. Here, the lowest cost value is achieved by choosing the zero function as the penalty function, which means that the corresponding solution contains a large amount of violation.