Print Email Facebook Twitter The impact of soft time windows with penalties on the objective values of large real-world Vehicle Routing Problems Title The impact of soft time windows with penalties on the objective values of large real-world Vehicle Routing Problems Author Slotboom, Cynthia (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor van Essen, Theresia (mentor) Gijswijt, Dion (graduation committee) Keijzer, Marleen (graduation committee) Degree granting institution Delft University of Technology Programme Applied Mathematics Date 2019-12-06 Abstract 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. Subject VRPSoft time windowsReal-world problemsLocal search To reference this document use: http://resolver.tudelft.nl/uuid:4ddd6740-2f74-4fcd-aa9f-c0477015f5ba Part of collection Student theses Document type master thesis Rights © 2019 Cynthia Slotboom Files PDF 20191206_ThesisCynthiaSlo ... Public.pdf 1.31 MB Close viewer /islandora/object/uuid:4ddd6740-2f74-4fcd-aa9f-c0477015f5ba/datastream/OBJ/view