An Enhanced Three-Phase Heuristic Approach for the Capacitated Vehicle Routing Problem with Time Windows: Comparing Insertion-Based and Savings-Based Initialization

Articles in Press

Document Type : Original Article

Authors

1 M.Sc. GIS Department, Faculty of Geodesy and Geomatics, K. N. Toosi University of Technology

2 Associate Professor, GIS Department, Faculty of Geodesy and Geomatics, K. N. Toosi University of Technology

10.22059/eoge.2025.393777.1176

Abstract

Vehicle routing optimization in goods distribution helps reduce traffic congestion, lower air pollution, and cut operational costs. This study evaluates two three-phase heuristic methods for solving the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), focusing on minimizing both service time and the number of vehicles used. Each method consists of initialization, perturbation, and local search phases, differing primarily in their initialization algorithms: one employs an insertion-based heuristic, while the other uses a savings-based algorithm. To enhance efficiency, structured initialization was applied instead of random initialization, accelerating convergence to high-quality solutions. Additionally, solution feasibility was maintained at every step to avoid the need for a repair function. To escape local optima, the Variable Neighborhood Search (VNS) algorithm introduced controlled perturbations, while the Variable Neighborhood Descent (VND) algorithm refined solutions during the local search phase. The methods were tested on the Solomon benchmark dataset, which includes 100 customers distributed in random, clustered, and semi-clustered (random-cluster) patterns. Results showed that the insertion-based method produced better solutions in 66.1% of cases, whereas the savings-based method was computationally faster. Furthermore, the insertion-based approach outperformed a reference Genetic Algorithm (GA) in 53.6% of instances, demonstrating its effectiveness for time-sensitive distribution scenarios.

Keywords

Main Subjects

Earth Observation and Geomatics Engineering

Articles in Press, Accepted Manuscript
Available Online from 06 September 2025

Files

Share

How to cite

Statistics