An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem

The Semi-Soft Clustered Vehicle Routing Problem (SemiSoftCluVRP) is a relaxed version of the Clustered Vehicle Routing Problem (CluVRP) and an enhanced variant of the Soft Clustered Vehicle Routing Problem (SoftCluVRP). In the SemiSoftCluVRP, all customers are partitioned into several clusters, and these clusters are further divided into two types: hard clusters and soft clusters. Within a hard cluster, customers must be served by the same vehicle without interruption, whereas within a soft cluster, customers must also be served by the same vehicle, but interruptions are permitted. To solve this problem, a mathematical model is first developed, followed by the design of a two-level genetic algorithm that integrates a variable neighborhood descent method. Computational experiments demonstrate that the proposed algorithm produces high-quality solutions and exhibits excellent performance. Compared with the results of CluVRP and SoftCluVRP, the results of SemiSoftCluVRP can reduce and increase logistics costs by up to 6.50% and 7.52%, respectively. In practical applications, by adjusting the hard and soft attributes of clusters, more flexible decision-making references can be provided for relevant decision-makers.