pith. sign in

arxiv: 1907.11910 · v1 · pith:KUNJJMQZnew · submitted 2019-07-27 · 💻 cs.NE

SOM-Guided Evolutionary Search for Solving MinMax Multiple-TSP

Vlad-Ioan Lupoaie , Ivona-Alexandra Chili , Mihaela Elena Breaban , Madalina Raschip This is my paper

Pith reviewed 2026-05-24 14:46 UTC · model grok-4.3

classification 💻 cs.NE
keywords multiple traveling salesman problemself-organizing mapsevolutionary algorithmsant colony systemshybrid metaheuristicsmin-max mTSPTSPLIB benchmarkscombinatorial optimization
0
0 comments X

The pith

Hybridizing self-organizing maps with evolutionary algorithms and ant colony systems improves solutions to the min-max multiple-TSP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops and tests combinations of self-organizing maps, evolutionary algorithms, and ant colony systems to address the min-max version of the single-depot multiple traveling salesman problem. Experiments on TSPLIB instances show that the hybrids produce better results than the individual methods or earlier published approaches. A sympathetic reader would care because the multiple-TSP sits at the core of vehicle routing problems that affect logistics and resource allocation in practice. The work focuses on how the neural component can steer the meta-heuristic search toward higher-quality balanced route sets.

Core claim

The paper claims that hybridization between the neural network approach using self-organizing maps and the two meta-heuristics of evolutionary algorithms and ant colony systems brings significant improvements to solving the MinMax formulation of the Single-Depot Multiple-TSP, outperforming results reported in the literature on a set of problem instances taken from TSPLIB.

What carries the argument

SOM-guided evolutionary search, in which self-organizing maps direct the population-based search of evolutionary algorithms and ant colony systems toward promising regions of the solution space for balanced route assignments.

If this is right

  • The hybrids produce higher-quality solutions than standalone meta-heuristics on the tested min-max mTSP instances.
  • Better balanced route lengths become achievable for single-depot multiple-TSP problems drawn from standard benchmarks.
  • Neural guidance can be combined with existing evolutionary and ant colony frameworks to raise solution quality without changing the core search operators.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same hybridization pattern could be applied to multi-depot or capacitated versions of the multiple-TSP to test transferability.
  • Isolating the SOM component in controlled ablations would clarify how much of the gain is due to the neural guidance versus the meta-heuristic alone.
  • The approach might scale to larger instances if the map training cost is managed through incremental or approximate SOM updates.

Load-bearing premise

The observed gains come from the hybridization itself rather than from particular parameter settings or implementation details, and the comparisons to prior literature are fair without needing re-implementation of those methods.

What would settle it

Re-implement the best literature methods under identical computational limits and instance conditions as the proposed hybrids and check whether the performance gap disappears.

Figures

Figures reproduced from arXiv: 1907.11910 by Ivona-Alexandra Chili, Madalina Raschip, Mihaela Elena Breaban, Vlad-Ioan Lupoaie.

Figure 1
Figure 1. Figure 1: SOM for Multiple-TSP on instance eil76 with 5 salesme [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Cross-tour gene sequence transposition Aiming at balanced tours in the case of MinMax mTSP, we propose a small modification in the selection of candidate pairs for cross-tour mutation: instead of randomly building pairs from the selected chromosomes, we introduce a chance psort for those selected to be sorted according to their individual fitness and the pairs built picking the first candidate from one end… view at source ↗
Figure 4
Figure 4. Figure 4: In-tour gene sequence inversion The in-tour gene sequence inversion operator depicted in [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figure 2
Figure 2. Figure 2: The multi-chromosome representation for 3 salesmen [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 5
Figure 5. Figure 5: In-tour gene insertion 17 5 18 11 3 4 16 17 5 4 11 3 18 16 [PITH_FULL_IMAGE:figures/full_fig_p004_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: In-tour gene transposition The in-tour gene transposition operator represented in Fig￾ure 6 acts like a double in-tour gene insertion, randomly picking two nodes with uniform probability ptr k , where ptr is the probability of transposition mutation and k is the number of cities in the mutated chromosome, and swaps the cities between them. The value of each mutation probability is derived from the global i… view at source ↗
Figure 7
Figure 7. Figure 7: Results obtained with SOM using a number of neurons [PITH_FULL_IMAGE:figures/full_fig_p005_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Convergence of the ACO and hybrid ACO algorithms, res [PITH_FULL_IMAGE:figures/full_fig_p006_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Results for the MinMax objective. Each group corresp [PITH_FULL_IMAGE:figures/full_fig_p008_9.png] view at source ↗
read the original abstract

Multiple-TSP, also abbreviated in the literature as mTSP, is an extension of the Traveling Salesman Problem that lies at the core of many variants of the Vehicle Routing problem of great practical importance. The current paper develops and experiments with Self Organizing Maps, Evolutionary Algorithms and Ant Colony Systems to tackle the MinMax formulation of the Single-Depot Multiple-TSP. Hybridization between the neural network approach and the two meta-heuristics shows to bring significant improvements, outperforming results reported in the literature on a set of problem instances taken from TSPLIB.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 1 minor

Summary. The paper develops a hybrid approach combining Self-Organizing Maps (SOM) with Evolutionary Algorithms (EA) and Ant Colony Systems (ACS) to solve the MinMax formulation of the single-depot Multiple Traveling Salesman Problem (mTSP). It reports that the SOM-guided hybridization yields significant improvements and outperforms results from the literature on selected TSPLIB instances.

Significance. If the reported outperformance is shown to arise from the hybridization under controlled and reproducible conditions, the work would provide concrete evidence for the utility of neural-network guidance within metaheuristics for routing problems. The manuscript does not yet supply the experimental controls needed to support that attribution.

major comments (3)
  1. [Experimental evaluation section] Experimental evaluation section: the manuscript states that the hybrid method outperforms literature results on TSPLIB instances but supplies no description of the parameter settings (population size, learning rates, pheromone evaporation, etc.), termination criteria, or hardware used. Because the central claim rests on these performance deltas, the absence of this information prevents assessment of whether the gains are attributable to the hybridization.
  2. [Comparison to prior work] Comparison to prior work: it is not stated whether the cited baseline results were obtained by re-implementing the competing algorithms under identical instance sets, objective functions, and stopping rules, or were taken directly from the original publications. Without such controls the reported improvements cannot be confidently ascribed to the proposed SOM-EA-ACS hybridization rather than differences in tuning or implementation.
  3. [Results tables] Results tables: no statistical significance tests (e.g., Wilcoxon or t-tests across multiple runs) or standard deviations are reported for the claimed improvements. This omission directly affects the strength of the outperformance assertion that constitutes the paper's main empirical contribution.
minor comments (1)
  1. [Abstract] The abstract should specify the exact number of TSPLIB instances used and the primary performance metric (e.g., maximum tour length) against which outperformance is measured.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments, which help strengthen the experimental rigor of the manuscript. We address each major point below and will revise the paper accordingly.

read point-by-point responses

  1. Referee: [Experimental evaluation section] Experimental evaluation section: the manuscript states that the hybrid method outperforms literature results on TSPLIB instances but supplies no description of the parameter settings (population size, learning rates, pheromone evaporation, etc.), termination criteria, or hardware used. Because the central claim rests on these performance deltas, the absence of this information prevents assessment of whether the gains are attributable to the hybridization.

    Authors: We agree that the absence of these details limits reproducibility and attribution of gains to the hybridization. In the revised manuscript we will insert a dedicated subsection (new Section 4.2) that lists all SOM, EA and ACS parameter values, learning rates, pheromone evaporation rates, population sizes, termination criteria (e.g., iteration limits or convergence thresholds), and the exact hardware platform and software environment used for the reported runs. revision: yes

  2. Referee: [Comparison to prior work] Comparison to prior work: it is not stated whether the cited baseline results were obtained by re-implementing the competing algorithms under identical instance sets, objective functions, and stopping rules, or were taken directly from the original publications. Without such controls the reported improvements cannot be confidently ascribed to the proposed SOM-EA-ACS hybridization rather than differences in tuning or implementation.

    Authors: The baseline numbers were taken directly from the cited publications; this is standard practice for TSPLIB-based comparisons when source code is unavailable. We will add an explicit statement in Section 4.3 clarifying the provenance of each baseline and noting that all methods were evaluated on identical TSPLIB instances and the same MinMax objective. We will also discuss why direct literature comparison remains informative while acknowledging the referee’s concern about implementation differences. revision: partial

  3. Referee: [Results tables] Results tables: no statistical significance tests (e.g., Wilcoxon or t-tests across multiple runs) or standard deviations are reported for the claimed improvements. This omission directly affects the strength of the outperformance assertion that constitutes the paper's main empirical contribution.

    Authors: We concur that standard deviations and statistical tests are necessary to support the outperformance claims. In the revised tables we will report mean and standard deviation over 30 independent runs for each instance and add Wilcoxon signed-rank tests (with p-values) comparing the hybrid method against each baseline. revision: yes

Circularity Check

0 steps flagged

No circularity; empirical comparisons are self-contained

full rationale

The paper describes algorithmic hybrids of Self-Organizing Maps, Evolutionary Algorithms, and Ant Colony Systems applied to the MinMax mTSP, then reports experimental results on TSPLIB instances that outperform previously published numbers. No derivation chain, fitted-parameter prediction, self-definitional equation, or load-bearing self-citation is present; performance claims rest on direct empirical comparison rather than any reduction to the paper's own inputs or prior author work.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The paper builds on established metaheuristic and neural network techniques, introducing several tunable parameters typical for such approaches, with no new invented entities.

free parameters (1)
  • Various algorithm parameters (population size, learning rates, pheromone evaporation, etc.)
    Metaheuristic algorithms typically require tuning multiple parameters to achieve reported performance.
axioms (1)
  • domain assumption Standard assumptions of evolutionary algorithms and ant colony optimization hold for this problem domain.
    The methods rely on the effectiveness of these metaheuristics without proving their optimality.

pith-pipeline@v0.9.0 · 5631 in / 1275 out tokens · 34217 ms · 2026-05-24T14:46:54.644591+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Necula, M

    R. Necula, M. Breaban, and M. Raschip, ”Performance eval uation of ant colony systems for the single-depot multiple traveling salesman TABLE I RESULTS OBTAINED BY ALL ALGORITHMS FOR EIL 51 AND BERLIN 52 INSTANCES eil51 berlin52 2 3 5 7 2 3 5 7 SOM min 236.95 172.81 134.94 120.45 4253.82 3475.55 2949.61 2724.73 max 319.19 266.96 190.28 164.79 6574.19 5130....

    work page

  2. [2]

    Necula, M

    R. Necula, M. Breaban, and M. Raschip, ”Tackling the Bi-c riteria Facet of Multiple Traveling Salesman Problem with Ant Colony Syst ems,” in Proceedings of the 2015 IEEE 27th International Conference on Tools with Artificial Intelligence, pp. 873-880, 2015

    work page 2015

  3. [3]

    Necula, M

    R. Necula, M. Raschip, and M. Breaban. ”Balancing the Sub tours for Multiple TSP Approached with ACS: Clustering-Based Approa ches Vs. MinMax Formulation.” EVOL VE-A Bridge between Probability , Set Oriented Numerics, and Evolutionary Computation VI. Sprin ger, Cham,

    work page

  4. [4]

    Bektas, T. (2006). The multiple traveling salesman prob lem: an overview of formulations and solution procedures. Omega, 34(3), 209 -219

    work page 2006

  5. [5]

    T. Bektas. Balancing tour durations in routing a vehicle fleet. In Proceedings of the IEEE Workshop on Computational Intellig ence In Production And Logistics Systems,pp. 9-16, 2013

    work page 2013

  6. [6]

    Franc ¸a, M

    P .M. Franc ¸a, M. Gendreau, G. Laporte, F.M. M¨ uller. The m-Traveling Salesman Problem with Minmax Objective. Transportation Sc ience, 29(3), 267-275, 1995

    work page 1995

  7. [7]

    Chandran, T.T

    N. Chandran, T.T. Narendran, K. Ganesh. A clustering app roach to solve the multiple travelling salesmen problem. Internati onal Journal of Industrial and Systems Engineering, 1(3), 372-387, 2006

    work page 2006

  8. [8]

    Y . Wang, Y . Chen, Y . Lin. Memetic algorithm based on seque ntial vari- able neighborhood descent for the minmax multiple travelin g salesman problem. Computers & Industrial Engineering, 106, 105-122 , 2017

    work page 2017

  9. [9]

    V allivaara

    I. V allivaara. A team ant colony optimization algorithm for the multiple travelling salesmen problem with minmax objective. In Proc eedings of the 27th IASTED International Conference on Modelling, Ide ntification and Control, pp. 387-392, ACTA Press, 2008

    work page 2008

  10. [10]

    Matsuura, K

    T. Matsuura, K. Numata. ”Solving Min-Max Multiple Trav eling Sales- man Problems by Chaotic Neural Network”. International Sym posium on Nonlinear Theory and its Applications, 2014

    work page 2014

  11. [11]

    Modares, S

    A. Modares, S. Somhom, T. Enkawa. ”A self-organizing ne ural network approach for multiple traveling salesman and vehicle routi ng problems”. International Transactions in Operational Research, 6(6) , 591-606, 1999

    work page 1999

  12. [12]

    Carter, C.T

    A.E. Carter, C.T. Ragsdale. A new approach to solving th e multiple traveling salesperson problem using evolutionary algorit hms. European Journal of Operational Research, 175(1), 246-257, 2006

    work page 2006

  13. [13]

    Kir´ aly, J

    A. Kir´ aly, J. Abonyi. Optimization of multiple travel ing salesmen problem by a novel representation based evolutionary algor ithm. In Intelligent Computational Optimization in Engineering, p p. 241-269, Springer, 2011

    work page 2011

  14. [14]

    Ang´ eniol, G

    B. Ang´ eniol, G. de La Croix V aubois, J.-y. Le Texier. ”S elf-organizing feature maps and the travelling salesman problem”. Neural N etworks. 1988;1(4):289–293, 1998

    work page 1988

  15. [15]

    ”Solving a combinatorial problem via self- organizing process: an application of the Kohonen algorithm to the traveling sal esman problem.” Biological Cybernetics

    J.-C.Fort. ”Solving a combinatorial problem via self- organizing process: an application of the Kohonen algorithm to the traveling sal esman problem.” Biological Cybernetics. 1988;59(1):33–40, 198 8

    work page 1988

  16. [16]

    J. Faigl. An application of self-organizing map for mul tirobot multigoal path planning with minmax objective. Computational intell igence and neuroscience, vol. 2016 (2016): 2720630

    work page 2016

  17. [17]

    G.A. Croes. A Method for Solving Traveling-Salesman Pr oblems. Op- eration Research, 6, 791-812, 1958

    work page 1958

  18. [18]

    Gavrilut, R

    D. Gavrilut, R. Benchea, C. V atamanu. Optimized zero fa lse positives perceptron training for malware detection. In 2012 14th Int ernational Symposium on Symbolic and Numeric Algorithms for Scientific Com- puting (pp. 247-253), 2012

    work page 2012

  19. [19]

    Building a practic al and reliable classifier for malware detection.Journal of Computer Virol ogy and Hacking Techniques, 2013

    C V atamanu, D Gavrilut ¸, RM Benchea. Building a practic al and reliable classifier for malware detection.Journal of Computer Virol ogy and Hacking Techniques, 2013

    work page 2013