What is it about?
The present study considers a parcel dispatching method based on a solution to 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 the historical delivery data and the couriers’ location data, which comes from their mobile device’s global positioning system (GPS). The solution to the vehicle routing problem is based on a two-stage algorithm: obtaining an initial feasible (greedy) solution at the first stage and sequentially improving this initial solution at the second stage. Improving the initial feasible solution is achieved by selecting an appropriate simulated annealing (SA) temperature and applying a saving-matrix-based ant colony optimization (ACO) algorithm using the Ruin and Recreate (R&R) method. This research aims to improve existing dispatching systems by reducing the number of vehicles as the first objective and the total route duration for the minimal available number of vehicles as the second objective. The application to real industrial delivery tasks shows that the proposed approach is highly effective.
Featured Image
Photo by Arron Choi on Unsplash
Why is it important?
The Vehicle Routing Problem (VRP) determines a set of vehicle routes originating and terminating at a single depot such that each customer is visited exactly once and the total customer demand on each route does not exceed the vehicle’s capacity. Time windows are imposed on customer destinations, meaning the vehicle is permitted to arrive only within a specific time window and remain at the customer site for the customer’s service time. Sometimes, when waiting is permitted (soft time window), the vehicle can arrive before the time window and wait until the early bounce of the time window (waiting before the delivery) or wait at the previous customer’s site to arrive at the next customer on its early bounce of the time window (waiting after the delivery). However, in megapolises, early arrivals pose a problem due to unavailable or too expensive parking for waiting (Figliozzi, 2012; Qureshi et al., 2010) and are strictly prohibited, so hard or strict time-window constraints or VRPHTW are imposed (Yıldırım and Çatay, 2009).
Perspectives
This paper presented a solution to a time-dependent vehicle routing problem with hard time-window constraints using a saving ant colony approach. Recently, the problem has received increasing attention due to the popularity of parcel dispatching in megacities, limited parking abilities, and traffic congestion. The approach developed here is based on a real-world, auto-updated static traffic model using a multi-layer distance-duration matrix, without imposing the FIFO property. Various constraints and multiple objective functions are addressed using the saving ant colony optimization. The fuzziness of the saving ant colony optimization allows the incorporation of additional diverse constraints, such as open VRP, package compatibility, and courier lunch break time, through minor adaptations of the proposed algorithms.
Dr Uri Lipowezky
Tel Aviv University
Read the Original
This page is a summary of: , Novel Journal of Applied Sciences Research, September 2025, MK Science Set Publishers LLC,
DOI: 10.63620/mknjasr.2025.1054.
You can read the full text:
Contributors
The following have contributed to this page
