Evolutionary Giant Tour for CVRP using NSE and ML Heuristic]{Evolutionary Giant Tour approach for CVRP using Node Shift Encoding and Machine Learning repair heuristic

1 Introduction

• Unconstrained splitting can produce more routes than the available fleet K, while enforcing K inside splitting or adding evolutionary penalties introduces constraint-management overhead.The proposed framework treats evolution and route construction sequentially.Source: §1 · p. 1
• The paper adapts Node Shift Encoding to CVRP giant tours and benchmarks it against Path Representation and Double Chromosome.NSE represents relative node shifts rather than absolute positions and is designed to preserve structural patterns during crossover and mutation.Source: §1 · p. 2
• The ML repair embeds the distance matrix in two-dimensional Euclidean space and reallocates surplus customers using centroid guidance and capacity-aware insertion.It is a standalone post-processing layer compared with Vidal’s fleet-constrained dynamic-programming split.Source: §1 · p. 2
• On 24 Augerat instances, NSE achieved better solution quality than PR and DC, while linear split plus ML repair improved feasibility, solution quality, and convergence speed versus Vidal’s constrained split.The proposed repair is applied after splitting when the resulting route count exceeds K.Source: §1 · p. 2
• The paper organizes its remaining sections around related work, the CVRP model, the proposed approach, experiments, results, discussion, and conclusions.Source: §1 · p. 2

2 Related works

• The review identifies fleet-size enforcement as a persistent issue in giant-tour approaches, motivating the paper’s contribution.It covers giant-tour methods, genetic algorithms, splitting procedures, and fleet-size strategies.Source: §2 · p. 2

2.1 Giant-Tour paradigm

• The giant-tour paradigm first constructs one Hamiltonian cycle, then partitions it into feasible routes; Beasley modeled partitioning as a shortest-path problem on a directed acyclic graph.Prins integrated the paradigm with a genetic algorithm, separating tour construction from capacity handling.Source: §2.1 · p. 2

2.2 Genetic Algorithms for Giant-Tour construction

• Path Representation encodes a tour as a customer permutation, but standard genetic operators can create duplicate or omitted visits; specialized operators may require O(n^2) to O(n^3) time.Double Chromosome and Node Shift Encoding were developed for the TSP, motivating their comparison with PR in CVRP.Source: §2.2 · p. 2

2.3 Splitting procedures

• The classical splitter uses O(n^2) dynamic programming, while Vidal’s Monge-based routine reduces splitting to O(n).These procedures enforce capacity but not a fleet-size limit K; Vidal’s constrained extension can return an infeasible result when the tour lacks valid cut points for exactly K routes.Source: §2.3 · pp. 2–3

2.4 Contribution

• The paper compares NSE with PR and DC, and adds an unsupervised repair heuristic after linear splitting produces excess routes.The heuristic embeds the distance matrix in two dimensions, computes surviving-route centroids, and reallocates surplus customers through capacity-aware insertion.Source: §2.4 · p. 3

3 Problem statement

• The model assumes one central depot, identical capacity-limited vehicles, known static demands, and exactly one full visit per customer.Source: §3 · p. 3
• CVRP is modeled on a graph with a depot and customers, seeking at most K routes that minimize total travel cost.The model defines K as the available vehicle count, Q as vehicle capacity, q_i as customer demand, and c_ij as travel cost.Source: §3 · p. 3
• Binary decision variable x_ijk indicates whether vehicle k travels directly from node i to node j.The variable is defined for node pairs and vehicles.Source: §3 · p. 3
• The constraints require vehicle capacities to hold, each customer to be visited once, depot departure and return, and flow conservation.Source: §3 · pp. 3–4
• Auxiliary cumulative-load variables u_ik support subtour elimination, with inequalities bounding loads and linking them to selected arcs.The formulation also specifies binary decision variables.Source: §3 · p. 4

4 Proposed methodology

• The method constructs a giant tour with relaxed capacity and fleet-size constraints, then partitions it into capacity-feasible routes.The section presents giant-tour construction, splitting, and machine-learning repair as three operational steps.Source: §4 · p. 4

4.1 Giant Tour construction

• A genetic algorithm optimizes the giant tour by balancing exploration and exploitation across the CVRP search space.Source: §4.1 · p. 4

4.1.1 Population representation

• NSE represents a tour with a fixed reference vector and a shift vector decoded sequentially; the study compares it with PR and DC.PR stores a customer permutation, while DC uses a map chromosome and a guide chromosome of swap instructions.Source: §4.1.1 · p. 4

4.1.2 Evaluation

• Fitness equals B minus total tour distance, so shorter-distance solutions receive higher fitness; B is based on the n largest sorted distances.The objective minimizes total travel distance, while the fitness transformation makes the genetic algorithm’s maximization procedure suitable for that objective.Source: §4.1.2 · p. 5

4.1.3 Evolutionary operators

• DC and NSE operators preserve structurally valid tours, whereas PR can produce invalid permutations handled with a zero-fitness death penalty.The GA selects individuals by roulette wheel and uniform random selection, applies one-point crossover and simple mutation, and preserves elites between generations.Source: §4.1.2 · p. 5, §4.1.3 · p. 6

• Vidal’s linear split partitions the giant tour into capacity-feasible routes using a shortest-path procedure on an auxiliary directed acyclic graph.Each feasible arc represents a consecutive customer segment served by one vehicle, with cost equal to that isolated route’s distance.Source: §4.2 · p. 6
• The shortest-path procedure runs in O(n) by exploiting the Monge property and pruning dominated candidate paths; the optimal partition is recovered by backtracking.Source: §4.2 · p. 6
• Unrestricted splitting may exceed fleet size K; the O(nK) constrained extension enforces the limit but may find no feasible partition, while excess routes trigger ML repair.Source: §4.2 · pp. 6–7

4.3 Proposed Machine Learning repair heuristic

• When splitting produces more than K routes, the unsupervised online repair heuristic reallocates customers using route centroids that update after each insertion.The centroids serve as adaptive prototypes rather than fixed, precomputed assignment rules.Source: §4.3 · p. 7

4.3.1 Coordinate construction

• The heuristic embeds the benchmark distance matrix into 2D Euclidean coordinates using distance geometry, with linear overall localization complexity for d = 2.The embedding uses sequential node localization via sphere intersection.Source: §4.3.1 · p. 7

4.3.2 Centroid-based route reconstruction

• It randomly dismantles the surplus routes, pools their customers, and rebuilds the fleet by inserting them into the remaining K routes using dynamic spatial centroids.Centroids exclude the depot to represent each route’s customer service area, and are recalculated after each insertion.Source: §4.3.2 · p. 7

4.4 Complexity analysis

• The heuristic’s overall complexity is O(n + |U| log |U| + |U| · (K log K + n/K)), where U is the pool of customers from surplus routes.Embedding and centroid initialization each require O(n); the reassignment loop accounts for the terms involving |U|.Source: §4.4 · p. 7
• In the realistic setting described, only a small number of surplus routes keeps U modest and runtime dominated by the linear embedding, despite a theoretical O(n^2) worst case.The worst case occurs when surplus routes contain O(n) customers.Source: §4.4 · p. 7

4.4.1 Illustrative example

• For the example, customers from a dismantled route are reassigned sequentially to capacity-feasible routes using spatial centroids that update after each insertion.Customers in the unassigned pool are sorted by descending demand; the example uses a depot and twelve customers.Source: §4.4.1 · p. 9
• The example ends with exactly three routes, each within the capacity limit Q = 15, with each customer inserted to minimize incremental travel distance.The final route loads are 15, 14, and 15.Source: §4.4.1 · p. 10, Figure 4 · p. 10

5 Experimental study

• The study compares the computational performance of three encoding schemes and the proposed ML heuristic, with results organized around benchmark configuration, parameter tuning, and feasibility penalties.Source: §5 · p. 10

5.1 Benchmark instances

• The evaluation uses Augerat benchmark instances spanning different problem scales, customer distributions, and capacity tightness, with customer counts, fleet availability, and vehicle capacities specified per instance.Source: §5.1 · p. 11, Table 4 · p. 11

5.2 Experimental protocol

• Each encoding is run independently 30 times per instance, and the repair heuristic is triggered when splitting exceeds the fleet limit; unrepaired cases receive an experimentally derived penalty.Parameters were selected for the overall trade-off between convergence speed and solution quality.Source: §5.2 · p. 11

5.3 Implementation environment

• The framework was implemented in C# on .NET and evaluated on an Intel Core i3 at 2.00 GHz with 4 GB of RAM.Source: §5.3 · p. 11

6.1 Encoding comparison

• Before repair, NSE has the strictly lowest Best cost on 10 of 24 instances, compared with one each for DC and PR, with 12 ties.On P-n20-k2, Best cost is 244.69 for NSE, 270.23 for DC, and 330.41 for PR.Source: §6.1 · p. 12, Figure 5 · p. 12, Table 5 · p. 12
• Before repair, NSE has the strictly lowest Kerr on 13 instances, versus six for DC and one for PR, and the highest feasible-solution count on six instances.Kerr measures the average number of vehicles exceeding the fleet limit.Source: §6.1 · p. 12, Figure 7 · p. 13, Figure 6 · p. 13

6.2 ML heuristic effect

• After repair, NSE has the lowest Best cost on 18 instances, while all three encodings reach full feasibility on 14 instances; overall recovery rates range from 70.46% to 72.84%.The recovery rates are 70.46% for NSE, 72.84% for DC, and 71.48% for PR.Source: §6.2 · p. 13, Figure 9 · p. 15, Figure 10 · p. 15
• The ML repair adds very little runtime, and its reported recovery varies by instance, including zero recovery on P-n55-k15.For the 24 instances, surplus routes were typically two to three above the fleet limit.Source: §6.2 · pp. 14–15

6.3 Linear split + ML heuristic vs. Constrained linear split

• LSWH has lower best costs on 14 of 24 instances and lower mean costs on 21; across 720 runs, it yields 521 feasible solutions (72.4%) versus SWLF’s 321 (44.6%).The best-cost comparison has one SWLF win and nine ties; mean costs tie on three instances.Source: §6.3 · pp. 15–16, Figure 14 · p. 17, Table 7 · p. 17
• Against GLPK, LSWH produces feasible tours on several larger instances where GLPK finds no feasible solution within four hours, although LSWH costs remain above known optima on several reported instances.On P-n76-k5, LSWH costs 1074.07 while GLPK obtains 1076 after four hours.Source: §6.3 · pp. 17–18

7 Discussion

• NSE outperforms PR significantly (p = 0.038), but its lead over DC is not statistically significant (p = 0.319).NSE also leaves fewer excess routes after splitting, reducing repair work and improving the chance of repair success.Source: §7 · p. 18
• The repair heuristic restores feasibility in approximately 72% of evaluated cases through centroid updates after each insertion.These updates adapt the cluster model to changing partial-route layouts.Source: §7 · p. 18
• The Linear Split plus ML Heuristic pipeline delivers lower best and average costs and higher feasibility counts on most instances than the constrained split.The constrained split can become fragile when the giant tour lacks good breakpoints for exactly K feasible segments.Source: §7 · pp. 18–19
• The repair heuristic may fail on instances with very tight capacities and large demands, especially when poor giant-tour ordering fills routes quickly.NSE decoding also takes roughly 66 seconds on P-n101-k4, versus about 28 seconds for PR.Source: §7 · p. 19
• The modular design keeps the evolutionary core separate from splitting and repair, allowing operational constraints to be adapted in the repair layer.The authors identify time windows and heterogeneous fleets as possible extensions requiring changes to insertion rules and capacity checks.Source: §7 · p. 19
• Future work could refine random route dismantling, adapt GA parameters during search, and include route-workload equity alongside total distance.The current framework optimizes total distance alone.Source: §7 · p. 19

8 Conclusion and future directions

• The combined Linear Split and ML heuristic reports 72.4% feasibility versus 44.6% for literature methods, alongside lower costs and greater robustness.The repair heuristic restores feasibility in approximately 72% of infeasible cases.Source: §8 · p. 19

Funding

• The research received no specific grant from any funding agency.Source: Funding · p. 19