Exact solution for the vehicle routing problem with semi soft time windows and its application

Abstract

This paper reflects on a soft time windows variant of the Vehicle Routing Problem (VRP) that only considers penalties on late arrival while waiting on early arrival is allowed without cost, namely the Vehicle Routing and scheduling Problem with Semi Soft Time Windows (VRPSSTW). A column generation (Dantzig-Wolfe decomposition) based exact optimisation approach is presented to obtain exact solutions for the VRPSSTW. While the computation time for the exact approach is adequate for smaller instances, the computation time for large-sized problems is very large for the exact solution technique, which favours the use of heuristics for the soft time windows variants of the VRP, in city logistics-related research. Therefore, as an application, this paper shows that how these exact solutions can be used as benchmark solutions to evaluate the performance of heuristics on smaller instances before applying these heuristics to large VRPSSTW instances. Errors between the optimal solutions and approximate solutions were used to calibrate a genetic algorithm heuristic for the VRPSSTW. Large errors instigated a change in the initialization procedure in the genetic algorithm heuristic, which resulted in the improved performance in terms of cost and computation time.