Solving the Time-Dependent Vehicle Routing Problem with Hard Time Windows using the Saving Ant Colony Algorithm
Abstract:
The present study considers a method of parcel dispatching based on a solution of a capacitated vehicle routing problem with hard time windows per customer (no waiting is available) and an auto-updated static time-dependent traffic model. The static traffic model update is based on the actual duration from historical delivery data and the couriers’ location data, which comes from their mobile devices’ global positioning systems (GPS). The solution to the vehicle routing problem is based on a two-stage algorithm: obtaining an initial feasible (greedy) solution at the f irst stage and sequentially improving this initial solution at the second stage. The improvement of the initial feasible solution is based on the combination of selecting the appropriate simulated annealing (SA) temperature in the SA process and applying a saving matrix-based ant colony optimization (ACO) algorithm, which is accomplished using the Ruin and Recreate (R&R) method. This research aims to enhance existing dispatching systems by reducing the number of vehicles as the primary objective and minimizing the total route duration for the minimum number of available vehicles as the secondary objective. The application to real industrial delivery tasks shows that the pro posed approach is highly effective.
