# An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem
## 1 Introduction  
The Vehicle Routing Problem (VRP) [1] is a classical combinatorial optimization problem. Since the problem was proposed, it has attracted extensive attention from researchers. As research has deepened, many variants of the VRP have been developed by integrating practical applications, such as the VRP with time windows [2], two-echelon VRP [3], multi-compartment VRP [4], electric VRP [5], green VRP [6], pickup and delivery VRP [7], stochastic VRP [8], multi-objective VRP [9], and so on. The Clustered VRP (CluVRP) [10] and the Soft Clustered VRP (SoftCluVRP) [11] are two other variants of the VRP. In the CluVRP, customers to be served are divided into several subsets, each of which is called a cluster. A feasible route requires that customers within each cluster must be served continuously by the same vehicle without interruption. That is, once a vehicle enters a cluster to serve customers, it must serve all customers within that cluster before entering the next cluster for service or returning to the depot. The SoftCluVRP is a relaxed version of the CluVRP, in which the service of customers within a cluster is allowed to be interrupted, as long as they are served by the same vehicle. The CluVRP was originally developed to simulate the package delivery operations of courier companies [10]. All customers are divided into several clusters based on their geographical locations. According to the information of these clusters, the packages tobe delivered are sorted into corresponding containers. During the delivery process, the packages in a cluster must be delivered completely before moving on to deliver the packages in the next cluster. The CluVRP can also be used to simulate many other practical scenarios, such as urban solid waste collection [12], medical services in emergency environments [13], services within gated communities [14], and so on. In the CluVRP, if a deliveryman can always access all containers carried by the vehicle, it then becomes a SoftCluVRP [11]. In the SoftCluVRP, when a vehicle is serving clusters assigned to it, it is assumed that any cluster can be interrupted by other clusters, which is too loose. In the CluVRP, it is assumed that all clusters are not allowed to be interrupted, which is too strict. Therefore, this paper considers a problem that falls between these two assumptions, namely the SemiSoft CluVRP (SemiSoftCluVRP). In the SemiSoftCluVRP, all clusters are classified into two categories: hard clusters and soft clusters. Customers within hard clusters are not allowed to interrupt service, while customers within soft clusters are allowed to interrupt service. By setting the hard and soft attributes of clusters, decision-makers are provided with greater operational flexibility and richer decision-making insights, ultimately improving delivery efficiency and reducing operational costs. Specifically, the main contributions of this paper are as follows:  
(1) The SemiSoftCluVRP is proposed, which is a generalization of the CluVRP and the SoftCluVRP. Therefore, the SemiSoftCluVRP can simulate a wider range of practical scenarios, and designing solution methods for it holds greater practical significance. (2) Based on the existing mathematical models of the CluVRP and the SoftCluVRP in the literature, an integer linear programming model is established. (3) A two-level genetic algorithm integrated with a variable neighborhood descent (VND) method is designed. The algorithm decomposes the original problem into a low-level traveling salesman problem (TSP) and a high-level capacitated VRP (CVRP), and then solves each using a specific genetic algorithm. In addition, to enhance the local search ability of the algorithm, a VND method with inter-route and intra-route neighborhood search operators is applied after each generation of genetic operations. (4) Extensive computational experiments are conducted using a set of instances adapted from the existing literature, which includes 77 instances, thereby verifying the effectiveness of the proposed algorithm.