Solving Dynamic Vehicle Routing Problem with Soft Time Windows basing on the Static Problem Resolution by a Hybrid Approach

More and more companies in routing industry are interested in dynamic transportation problems that can be found in several real-life scenarios. In this paper, we addressed a dynamic vehicle routing problem with soft time windows (D-VRPSTW) in which new requests appear at any point during the vehicle’s route. We presented a mathematical formulation of the problem as well as a genetic algorithm hybridized with a variable neighborhood search (VNS) metaheuristic designed for the considered problem. Then, using the time discretization in intervals with new features, we focused on the proposed solution method to solve each partial static problem. We extended the dynamic vehicle routing problem (D-VRPSTW) by considering several objective functions, i.e. minimizing the transportation time by producing better planning, improving the quality of service by minimizing the delay time for each customer, and minimizing time loss by increasing the stopping time for each vehicle. The solution quality of this method has been compared against the existing results on benchmark problems.