Development of optimization algorithms to vehicle routing problem - Amin, Muhammad; Efendi, Syahril; Nasution, Mahyuddin K. M.; Elveny, Marischa (Eastern-European Journal of Enterprise Technologies, 2025)
The Capacitated Vehicle Routing Problem with Time-Dependent Demands (CVRPTD) is a significant optimization challenge in the logistics and transportation domain, characterized by dynamic customer demands, strict time windows, and heterogeneous vehicle fleets. This study focuses on urban parcel delivery operations as the primary object of research. The problem addressed involves the inefficiency of conventional vehicle routing strategies in adapting to time-varying customer demands and operational constraints, which often lead to increased costs and service delays. This study aims to minimize total operational costs while ensuring compliance with capacity constraints, service continuity, and demand fluctuations. A comprehensive mathematical model is developed based on a fully connected, directed acyclic graph G=(V, A), incorporating decision variables that represent vehicle routing sequences, timing, and vehicle type assignments. This study addresses the Capacitated Vehicle Routing Problem with Time-Dependent Demands (CVRPTD) in urban parcel delivery, where traditional routing methods struggle with dynamic demands and operational constraints. A mathematical model using a directed acyclic graph is developed, optimized via a gradient-based method with Hessian approximation, LU decomposition, and quasi-Newton techniques. Experiments on datasets with up to 200 customers and 20 vehicles with reductions ranging from 1.79% to 12.75%. The most significant improvement was observed in Sidorame Timur, where the optimization distance decreased by 12.75%, indicating high accuracy in route optimization. For the SCP, the proposed algorithm achieved a 6.46% improvement in solution quality over traditional greedy algorithms