Node-Shift-Encoding Genetic Algorithm with fuzzy-enhanced reference tour to solve the bi-objective service-oriented TSP

• Distance-only formulations assume homogeneous service requirements, although healthcare visits and robotic inspections can have heterogeneous priorities.Source: §1 · p. 1
• Service-oriented routing must balance travel efficiency with dissatisfaction when mandatory clients have target or maximal visit ranks.Source: §1 · p. 1
• Classical NSE uses a static reference tour that can limit exploration and contribute to premature convergence; fuzzy reasoning updates it when evolution stagnates.Source: §1 · p. 2
• TSPLIB experiments show consistent improvements over classical NSE in solution quality and robustness.Source: §1 · p. 2

• Unlike subset-selection variants, service-oriented routing can require every node to be visited while making service order critical.Source: §2 · pp. 2–3
• Related extensions include time windows, which add temporal constraints, prize collection, and order-based customer preferences.Source: §2 · p. 2
• The proposed service-oriented TSP assigns each customer a maximum visit rank and penalizes deviations while minimizing travel distance and dissatisfaction.Source: §2 · p. 3

3. Problem formulation

• The model jointly considers travel distance and dissatisfaction from deviations from each mandatory customer’s preferred maximum visit rank.The preliminary model uses a weighted sum of the two objectives, with nonnegative weights summing to 1.Source: §3 · p. 3, §3.1 · pp. 3–4

3.2. Origin-independent formulation

• The preliminary MTZ model fixes node 1 as the tour start, a restriction that can exclude valid tours when customer ranks affect the objective.The origin-independent formulation adds a zero-weight-linked dummy node to an augmented graph, with original vertex indices shifted by one.Source: §3.1 · p. 3, §3.2 · p. 4

3.1. Preliminary MTZ-based modelling

• Unlike the compared priority-based TSP, this model assigns explicit maximum ranks that may be shared and uses a modified MTZ formulation solvable by off-the-shelf ILP solvers.The modification removes dependence on a fixed city ordering, allowing arbitrary sequences without positional bias.Source: §3.1 · pp. 3–4

3.2. Origin-independent formulation

• An auxiliary binary variable identifies the open path’s final-to-first connection, restoring the complete Hamiltonian cycle and including its closure-edge cost.The model also adjusts dissatisfaction to compensate for positional bias introduced by the dummy node.Source: §3.2 · pp. 4–5
• The origin-independent formulation improves the example objective from F=0.37897 to F=0.32466, with distance falling from 73.61 to 69.85 and dissatisfaction from 14 to 10.The standard MTZ tour forces customer 1, with loose rank p1=9, to start, leaving highly constrained customer 9 at position 9 and incurring penalty 8.Source: §3.2 · p. 5, Table 2 · p. 5

3.3. Linearization

• The formulation linearizes rank dissatisfaction with an integer variable and a revised objective that sets it to positive lateness beyond the preferred rank, or zero otherwise.Combining the objectives and constraints yields an integer linear program that can be solved with off-the-shelf optimization solvers.Source: §3.3 · p. 5

4. NSE-based Genetic Algorithm

• The tailored genetic algorithm encodes each feasible tour as a shift vector relative to a reference tour and evaluates individuals after decoding them into complete tours.Its design uses Node Shift Encoding to manipulate solutions while preserving feasibility.Source: §4 · p. 6

4.1. Node Shift Encoding

• Node Shift Encoding applies a sequence of shift operations to a reference tour rather than directly encoding a permutation, keeping generated solutions feasible without repair.The shift vector has n−1 elements; each specifies a node’s repositioning relative to the reference tour, while the first node remains fixed.Source: §4.1 · p. 6

4.2. Genetic operators and evolutionary scheme

• The evolutionary scheme uses roulette-wheel selection with elitist replacement, single-point crossover on shift vectors, and localized shift-perturbation mutation.Initial shift vectors are generated uniformly at random within valid bounds; crossover offspring remain valid because their components stay within those bounds.Source: §4.2 · p. 6

5. Approach

• The approach perturbs NSE’s reference tour adaptively to balance exploration and exploitation while retaining feasibility under genetic operators.The method addresses the dependence of classical NSE on a single static reference tour.Source: §5 · p. 6, §5.1 · p. 6

5.1. General framework

• The GA decodes random NSE chromosomes using an initial reference tour and scores solutions with a normalized weighted sum of travel distance and customer dissatisfaction.Roulette-wheel selection, random additions, crossover, mutation, and elitist reinjection guide the search.Source: §5.1 · pp. 6–7

5.2. Fuzzy Logic

• Fuzzy logic supplies the controller for updating the reference tour within the NSE-based genetic algorithm.The paper describes fuzzification, rule inference, and defuzzification as its general process.Source: §5.2.1 · p. 7, §5.2 · p. 7

5.2.1. Fuzzy system design

• The fuzzy system is triggered by stagnation and scores tours using route distance and customer dissatisfaction to select a new reference tour.Its four rules assign the highest selection score to tours with both small distance and low dissatisfaction, favoring balance between objectives.Source: §5.2.1 · pp. 7–8

5.2.2. Illustrative example

• In the illustrative example, centroid defuzzification gives each candidate a selection score, and tour s2 becomes the new reference tour for its highest score.Mamdani min–max inference aggregates the rule outputs before the centroid is calculated.Source: §5.2.2 · p. 8

5.2.3. Integration in GA process

• The GA monitors best fitness and invokes the fuzzy decision process after no significant improvement over a predefined number of consecutive generations.At activation, current-population candidates are assessed using route distance and dissatisfaction, and a high-quality tour guides continued search.Source: §5.2.3 · p. 9

6.1. Benchmark instances

• The evaluation uses 13 TSPLIB instances spanning 51 to 200 cities, with best-known single-objective distances serving only as reference benchmarks.Distance-optimal tours are not necessarily optimal under the combined objective that includes position-based service requirements.Source: §6.1 · p. 9, Table 7 · p. 10

6.2. Generating position-priority data

• Each city receives a maximum visit rank drawn uniformly from 1 to n, independently of its geographic location.The synthetic preferences are intended to avoid geographic structure that could favor either algorithm.Source: §6.2 · p. 10

6.3. Algorithm parameters

• Both objectives receive equal weights of 0.5 after normalization, and performance is measured over 30 independent runs per instance.The study records distance, dissatisfaction, combined fitness, and computational time; the stagnation threshold is tuned by instance.Source: §6.3 · p. 10

6.4. Computational environment

• Experiments run on an Intel Core i3 2.0 GHz workstation with 4 GB RAM, while GLPK solves the linear formulation under a four-hour limit per instance.The formulation is coded in GNU MathProg.Source: §6.4 · p. 10

7. Experiment results

• FL-NSE finds feasible tours for all 13 benchmarks, while GLPK finds no feasible incumbent on kroB100, pr144, kroA150, or kroA200 within four hours.Among the nine instances where GLPK succeeds, FL-NSE has lower minimum fitness on eight; its relative improvements range from +3.48% on lin105 to +18.90% on pr76.Source: §7 · p. 11
• Average fitness is lower with FL-NSE on every instance, with relative improvements from 2.0% on eil76 to 6.8% on pr76.Fitness standard deviation decreases on 8 of 13 instances, but increases on kroA150 and kroA200.Source: §7 · p. 11
• On kroA200, FL-NSE reduces average travel distance from 198,375 to 186,840 and dissatisfaction from 5,710 to 5,562.On pr76, dissatisfaction improves by 11.91%, the largest reduction reported across instances.Source: §7 · p. 11
• FL-NSE takes 1.2× to 2.2× as long on small and medium instances, while runtime is approximately 0.9× on the two largest instances.The authors caution that the limited number of large-scale instances prevents firm conclusions about runtime behavior.Source: §7 · pp. 11, 13
• V = 75 and p = 0.03979; FL-NSE has lower minimum fitness than classical NSE, with a median paired difference of +0.007737 and wins in over 75% of benchmark runs.The paired Wilcoxon test rejects equal median fitness distributions; Table 8 reports the comparative results.Source: §7 · p. 11, Table 8 · p. 12
• Distance-optimal tours incur substantial dissatisfaction in the rank-sensitive objective; across instances, their distance gap is +101% to +640%, while dissatisfaction falls by 25.7% to 53.5% for FL-NSE.The dissatisfaction for distance-optimal tours is measured after fixing node 1 as the start, rather than minimizing over cyclic shifts.Source: §7 · p. 13, Table 9 · p. 13
• The authors attribute the benchmark gains to fuzzy updates of the search baseline, which they report mitigate stagnation and sustain diversification.Their summary contrasts this adaptive process with static reference tours that progressively restrict neighborhood exploration.Source: §7 · p. 13

8. Discussion

• Across all 13 instances, FL-NSE improved upon classical NSE, and the discussion attributes the static reference tour to structural barriers and localized stagnation.The fuzzy controller revisits the reference-tour choice when search stalls.Source: §8 · p. 13
• Fuzzy reasoning evaluates distance and dissatisfaction as separate linguistic concepts, unlike the GA’s weighted-sum objective.The authors argue that prioritizing the two objectives separately explains why FL-NSE discovers solutions dominating those accessible to classical NSE.Source: §8 · p. 14
• On eil76, FL-NSE had a lower mean fitness (0.2836 vs. 0.2893) and 35% lower standard deviation (0.0113 vs. 0.0175), despite NSE’s better single best-found solution.The comparison is presented as evidence of greater statistical reliability, rather than a better single best result.Source: §8 · p. 14
• FL-NSE found feasible solutions across all test cases, while GLPK failed to construct a feasible tour for 4 of 13 instances within four hours.FL-NSE outperformed GLPK on 8 of the 9 comparable instances.Source: §8 · p. 14
• Both travel distance and dissatisfaction decreased on 12 instances; on eil76, dissatisfaction fell to 619.93 from 669.67 while distance was effectively unchanged.The reported eil76 distance values are 1285.52 versus 1286.16.Source: §8 · p. 14
• 0.9× beyond 150 cities: the reported runtime ratio favors FL-NSE on larger instances, whereas small instances incur fuzzy overhead up to 2.2×.The authors qualify the larger-instance trend as requiring confirmation across a broader sample.Source: §8 · p. 14
• For eil51, FL-NSE reduced dissatisfaction by 53.5% against the distance-optimal tour; on pr144, that tour’s dissatisfaction was 3,053 versus 2,120 for FL-NSE.The discussion argues that distance-optimal tours can be poor benchmarks for preference-aware routing.Source: §8 · p. 14
• The weighted-sum formulation misses trade-off solutions in non-convex Pareto-front regions, and random preferences and tests up to 200 cities limit the study’s scope.The authors identify correlated spatial or temporal preferences and larger-scale testing as areas not covered by the current experiments.Source: §8 · p. 14

9. Conclusion

• The paper formulates service-oriented TSP as bi-objective optimization, assigning customers visit ranks and dissatisfaction costs for deviations, and proposes FL-NSE to update the reference tour upon stagnation.The formulation is described as not previously addressed in the literature to the authors’ knowledge.Source: §9 · p. 15
• Across 13 TSPLIB instances, FL-NSE improved fitness over classical NSE while simultaneously reducing travel distance and customer dissatisfaction.The conclusion also reports dissatisfaction reductions up to 53.5% against distance-optimal tours and faster execution at 0.9× beyond 150 cities.Source: §9 · p. 15
• Future work will test pure Pareto optimization and correlated preference distributions, including spatially clustered demand.Source: §9 · p. 15

CRediT authorship contribution statement

• Abdoune is credited with conceptualization, programming, writing, and analysis; Boulif with conceptualization, writing, correction, analysis, supervision, and validation.Source: CRediT authorship contribution statement · p. 15

Funding

• No specific grant funding is reported.Source: Funding · p. 15