pith. sign in

arxiv: 2404.08157 · v6 · submitted 2024-04-11 · 🧮 math.OC · cs.RO

Equitable Routing--Rethinking the Multiple Traveling Salesman Problem

Abhay Singh Bhadoriya , Deepjyoti Deka , Kaarthik Sundar This is my paper

Pith reviewed 2026-05-24 01:44 UTC · model grok-4.3

classification 🧮 math.OC cs.RO
keywords multiple traveling salesman problemfairness constraintsequitable routingmixed-integer second-order cone programmingmixed-integer linear programmingPareto frontvehicle routing
0
0 comments X

The pith

Two new parametric fairness models for the multiple traveling salesman problem achieve equitable tour lengths while controlling total cost.

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

The paper aims to move beyond the min-max multiple traveling salesman problem, which is hard to solve, by introducing two tunable fairness variants that spread tour lengths more evenly among salesmen. The ε-Fair-MTSP is cast as a mixed-integer second-order cone program and the Δ-Fair-MTSP as a mixed-integer linear program, each equipped with algorithms that reach global optimality. These models let a user set how much disparity is allowed between any two tours, trading a controlled amount of extra total distance for greater equity. Experiments on benchmark sets and electric-vehicle fleet data show the models remain tractable and can trace the full Pareto curve between total length and balance. If correct, the approach supplies a practical, adjustable substitute for strict min-max balancing.

Core claim

The paper establishes that the ε-Fair-MTSP and Δ-Fair-MTSP, defined through fairness parameters ε and Δ that bound differences in individual tour lengths, admit globally optimal solutions via mixed-integer second-order cone and linear programming formulations respectively, and that the same algorithms also recover the Pareto front of the bi-objective problem that jointly minimizes total tour length and the spread of tour lengths.

What carries the argument

The ε-Fair-MTSP and Δ-Fair-MTSP formulations that impose parametric limits on the maximum difference between any pair of salesman tour lengths.

If this is right

  • The same algorithms recover the Pareto front between total tour length and tour-length balance.
  • The models are effective on both standard MTSP benchmarks and real electric-vehicle routing instances.
  • They remain solvable to global optimality by the developed branch-and-cut procedures.
  • They supply tunable control over equity that is absent from the strict min-max formulation.

Where Pith is reading between the lines

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

  • The parametric structure could be reused to enforce fairness in other vehicle-routing variants such as capacitated or time-window problems.
  • Operators could learn preferred ε or Δ values from historical route-acceptance data.
  • Embedding the models inside a rolling-horizon planner might keep daily workloads balanced under demand changes.

Load-bearing premise

The chosen values of the fairness parameters ε and Δ will produce routes that operators in practice regard as equitable.

What would settle it

Solve the models on the same benchmark instances used in the paper and check whether, for the reported ε and Δ values, the obtained solutions exhibit the claimed fairness bounds and remain solvable to proven optimality within the same time limits.

Figures

Figures reproduced from arXiv: 2404.08157 by Abhay Singh Bhadoriya, Deepjyoti Deka, Kaarthik Sundar.

Figure 1
Figure 1. Figure 1: An illustration of the outer approximation procedure. The region shaded in red is the convex constraint, and the violated point is the [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The Pareto fronts for the two bi-objective formulations, the total tour length for the “min-sum” and “min-max” MTSP for the eil51 instance [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Cost of fairness of the optimal solutions of [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) shows the graph of the “Seattle” instance with the red dot representing the depot and the blue dots representing the different targets. [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗
read the original abstract

The Multiple Traveling Salesman Problem (MTSP) extends the traveling salesman problem by assigning multiple salesmen to visit a set of targets from a common depot, with each target visited exactly once while minimizing total tour length. A common variant, the min-max MTSP, focuses on workload balance by minimizing the longest tour, but it is difficult to solve optimally due to weak linear relaxation bounds. This paper introduces two new parametric fairness-driven variants of the MTSP: the $\varepsilon$-Fair-MTSP and the $\Delta$-Fair-MTSP, which promote equitable distribution of tour lengths while controlling overall cost. The $\varepsilon$-Fair-MTSP is formulated as a mixed-integer second-order cone program, while the $\Delta$-Fair-MTSP is modeled as a mixed-integer linear program. We develop algorithms that guarantee global optimality for both formulations. Computational experiments on benchmark instances and real-world applications, including electric vehicle fleet routing, demonstrate their effectiveness. Furthermore, we show that the algorithms presented for the fairness-constrained MTSP variants can be used to obtain the Pareto front of a bi-objective optimization problem in which one objective minimizes the total tour length and the other balances the lengths of the individual tours. Overall, these fairness-constrained MTSP variants provide a practical and flexible alternative to the min-max MTSP.

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

2 major / 2 minor

Summary. The paper introduces two parametric fairness-constrained variants of the Multiple Traveling Salesman Problem (MTSP): the ε-Fair-MTSP formulated as a mixed-integer second-order cone program (MISOCP) and the Δ-Fair-MTSP as a mixed-integer linear program (MILP). It develops algorithms that guarantee global optimality for both, reports computational experiments on benchmark instances and electric vehicle fleet routing, and shows that the models can be used to trace the Pareto front of the bi-objective problem that trades off total tour length against tour-length balance. The central claim is that these variants constitute a practical and flexible alternative to the standard min-max MTSP.

Significance. If the formulations are correct and the reported global-optimality algorithms scale as claimed, the work supplies a tunable family of equity-aware MTSP models that avoid the notoriously weak LP relaxations of the min-max formulation while still controlling total cost. The explicit construction of Pareto fronts and the EV-routing case study are concrete strengths that could be useful in sustainable logistics applications.

major comments (2)
  1. [Computational Experiments] Computational Experiments section: the reported solve times, optimality gaps, and achieved total costs for the ε-Fair-MTSP and Δ-Fair-MTSP instances are not accompanied by side-by-side results for the standard min-max MTSP on the identical benchmark sets. Without this direct comparison, the claim that the new models are a “practical and flexible alternative” cannot be evaluated, because the added fairness constraints could increase rather than decrease runtimes or gaps relative to the already weak min-max relaxation.
  2. [Formulation sections] Formulation of ε-Fair-MTSP (MISOCP) and Δ-Fair-MTSP (MILP): the parameters ε and Δ are introduced as free fairness tolerances, yet no sensitivity analysis or operational calibration is provided showing that the resulting route sets are perceived as equitable by dispatchers or drivers. This choice directly affects both tractability and the practical utility asserted in the abstract.
minor comments (2)
  1. [Formulation] Notation for the second-order cone constraint in the ε-Fair-MTSP formulation is introduced without an explicit reference to the standard SOCP form used by the solver; adding the precise cone definition would improve reproducibility.
  2. [Computational Experiments] Table captions in the computational results do not state the time limit or MIP gap tolerance used for the reported runs; this information is needed to interpret the “global optimality” claims.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the detailed and constructive report. We address each major comment below and indicate the revisions that will be incorporated.

read point-by-point responses

  1. Referee: Computational Experiments section: the reported solve times, optimality gaps, and achieved total costs for the ε-Fair-MTSP and Δ-Fair-MTSP instances are not accompanied by side-by-side results for the standard min-max MTSP on the identical benchmark sets. Without this direct comparison, the claim that the new models are a “practical and flexible alternative” cannot be evaluated, because the added fairness constraints could increase rather than decrease runtimes or gaps relative to the already weak min-max relaxation.

    Authors: We agree that a direct, side-by-side comparison on identical instances is necessary to substantiate the claim of practicality. In the revised manuscript we will add tables (and corresponding discussion) that report solve times, optimality gaps, and total costs for the standard min-max MTSP formulation alongside the ε-Fair-MTSP and Δ-Fair-MTSP results on the same benchmark sets. This will allow an objective assessment of whether the fairness constraints improve or degrade computational performance relative to the min-max baseline. revision: yes

  2. Referee: Formulation of ε-Fair-MTSP (MISOCP) and Δ-Fair-MTSP (MILP): the parameters ε and Δ are introduced as free fairness tolerances, yet no sensitivity analysis or operational calibration is provided showing that the resulting route sets are perceived as equitable by dispatchers or drivers. This choice directly affects both tractability and the practical utility asserted in the abstract.

    Authors: The parameters ε and Δ are intentionally tunable; the bi-objective Pareto-front extraction procedure we present is precisely intended to let users explore the cost–fairness trade-off. We acknowledge, however, that the original submission did not contain a systematic sensitivity study on how solution quality and runtimes vary with ε and Δ. In revision we will add such an analysis on the benchmark instances. A full operational calibration that measures perceived equity by dispatchers or drivers would require a separate human-factors study; this lies outside the algorithmic scope of the paper, but the Pareto fronts we generate can serve as input for such future calibration. revision: partial

standing simulated objections not resolved
  • Empirical validation that route sets produced for specific ε/Δ values are perceived as equitable by human dispatchers or drivers would require a dedicated user study that is beyond the algorithmic focus of the current work.

Circularity Check

0 steps flagged

No significant circularity; new formulations are independent of inputs

full rationale

The paper introduces two new parametric fairness-constrained MTSP formulations (ε-Fair-MTSP as MISOCP and Δ-Fair-MTSP as MILP) along with optimality-guaranteeing algorithms and a Pareto-front extraction method. These are presented as modeling choices and algorithmic extensions rather than derived predictions or results obtained by fitting to data. No self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or described contributions; the central modeling steps are explicit constructions that do not reduce to prior outputs by definition. The practicality claim rests on computational experiments, which are external to any derivation chain and therefore outside the circularity criteria.

Axiom & Free-Parameter Ledger

2 free parameters · 0 axioms · 0 invented entities

The central modeling contribution rests on the introduction of two tunable fairness parameters whose values are chosen by the user; no additional invented entities or non-standard axioms are stated.

free parameters (2)
  • ε
    Fairness tolerance parameter in the ε-Fair-MTSP formulation that bounds deviation of individual tour lengths from the average.
  • Δ
    Fairness spread parameter in the Δ-Fair-MTSP formulation that bounds the difference between longest and shortest tours.

pith-pipeline@v0.9.0 · 5769 in / 1189 out tokens · 28992 ms · 2026-05-24T01:44:05.216060+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Family of Convex Models to Achieve Fairness through Dispersion Control

    math.OC 2025-10 unverdicted novelty 6.0

    Develops a parameterized family of convex models that bound the coefficient of variation of decision variables to enforce tunable fairness in optimization problems.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · cited by 1 Pith paper

  1. [1]

    Solution of a min-max vehicle routing problem

    David Applegate et al. “Solution of a min-max vehicle routing problem”. In:INFORMS Journal on computing14.2 (2002), pp. 132–143. 24

    work page 2002

  2. [2]

    Balancing tour durations in routing a vehicle fleet

    Tolga Bektaş. “Balancing tour durations in routing a vehicle fleet”. In:2013 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS). IEEE. 2013, pp. 9–16

    work page 2013

  3. [3]

    The multiple traveling salesman problem: an overview of formulations and solution procedures

    Tolga Bektaş. “The multiple traveling salesman problem: an overview of formulations and solution procedures”. In:Omega34.3 (2006), pp. 209–219

    work page 2006

  4. [4]

    Usingℓp-norms for fairness in combinatorial optimisation

    Tolga Bektaş and Adam N Letchford. “Usingℓp-norms for fairness in combinatorial optimisation”. In:Computers & Operations Research120 (2020), p. 104975

    work page 2020

  5. [5]

    The price of fairness

    Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. “The price of fairness”. In:Operations Research59.1 (2011), pp. 17–31

    work page 2011

  6. [6]

    Cambridge university press, 2004

    Stephen P Boyd and Lieven Vandenberghe.Convex optimization. Cambridge university press, 2004

    work page 2004

  7. [7]

    Incomeinequalitymeasures

    FernandoGDeMaio.“Incomeinequalitymeasures”.In:JournalofEpidemiology&CommunityHealth61.10(2007), pp. 849–852

    work page 2007

  8. [8]

    Vehicle routing problems for drone delivery

    Kevin Dorling et al. “Vehicle routing problems for drone delivery”. In:IEEE Transactions on Systems, Man, and Cybernetics: Systems47.1 (2016), pp. 70–85

    work page 2016

  9. [9]

    The m-traveling salesman problem with minmax objective

    Paulo M França et al. “The m-traveling salesman problem with minmax objective”. In:Transportation Science29.3 (1995), pp. 267–275

    work page 1995

  10. [10]

    On the measure of concentration with special reference to income and statistics

    Corrado Gini. “On the measure of concentration with special reference to income and statistics”. In:Colorado College Publication, General Series208.1 (1936), pp. 73–79

    work page 1936

  11. [11]

    Multi-terminal network flows

    Ralph E Gomory and Tien Chung Hu. “Multi-terminal network flows”. In:Journal of the Society for Industrial and Applied Mathematics9.4 (1961), pp. 551–570

    work page 1961

  12. [12]

    Thebi-objectivemixedcapacitatedgeneralroutingproblem with different route balance criteria

    ElinEHalvorsen-WeareandMartinWPSavelsbergh.“Thebi-objectivemixedcapacitatedgeneralroutingproblem with different route balance criteria”. In:European Journal of Operational Research251.2 (2016), pp. 451–465

    work page 2016

  13. [13]

    Optimal UAV route planning for persistent monitoring missions

    Sai Krishna Kanth Hari et al. “Optimal UAV route planning for persistent monitoring missions”. In:IEEE Trans- actions on Robotics37.2 (2020), pp. 550–566

    work page 2020

  14. [14]

    Cambridge university press, 2012

    Roger A Horn and Charles R Johnson.Matrix analysis. Cambridge university press, 2012

    work page 2012

  15. [15]

    C-LHwangandAbuSyedMdMasud.Multipleobjectivedecisionmaking—methodsandapplications:astate-of-the-art survey. Vol. 164. Springer Science & Business Media, 2012

    work page 2012

  16. [16]

    A quantitative measure of fairness and discrimina- tion

    Rajendra K Jain, Dah-Ming W Chiu, William R Hawe, et al. “A quantitative measure of fairness and discrimina- tion”. In:Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA21 (1984)

    work page 1984

  17. [17]

    Exact algorithms for the equitable traveling salesman problem

    Joris Kinable et al. “Exact algorithms for the equitable traveling salesman problem”. In:European Journal of Operational Research261.2 (2017), pp. 475–485

    work page 2017

  18. [18]

    Polyhedralapproximationinmixed-integerconvexoptimization

    MilesLubinetal.“Polyhedralapproximationinmixed-integerconvexoptimization”.In:MathematicalProgramming 172 (2018), pp. 139–168

    work page 2018

  19. [19]

    Workload equity in vehicle routing problems: A survey and analysis

    Piotr Matl, Richard F Hartl, and Thibaut Vidal. “Workload equity in vehicle routing problems: A survey and analysis”. In:Transportation Science52.2 (2018), pp. 239–260

    work page 2018

  20. [20]

    Kaisa Miettinen.Nonlinear multiobjective optimization. Vol. 12. Springer Science & Business Media, 1999

    work page 1999

  21. [21]

    Themultipleflyingsidekickstravelingsalesmanproblem:Parceldeliverywith multiple drones

    ChaseCMurrayandRitwikRaj.“Themultipleflyingsidekickstravelingsalesmanproblem:Parceldeliverywith multiple drones”. In:Transportation Research Part C: Emerging Technologies110 (2020), pp. 368–398

    work page 2020

  22. [22]

    OpenStreetMap contributors.Planet dump retrieved from https://planet.osm.org.https://www.openstreetmap. org. 2017. 25

    work page 2017

  23. [23]

    Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey

    Alena Otto et al. “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey”. In:Networks72.4 (2018), pp. 411–458

    work page 2018

  24. [24]

    A resource allocation algorithm for multivehicle systems with nonholonomic constraints

    Sivakumar Rathinam, Raja Sengupta, and Swaroop Darbha. “A resource allocation algorithm for multivehicle systems with nonholonomic constraints”. In:IEEE Transactions on Automation Science and Engineering4.1 (2007), pp. 98–104

    work page 2007

  25. [25]

    TSPLIB—A traveling salesman problem library

    Gerhard Reinelt. “TSPLIB—A traveling salesman problem library”. In:ORSA journal on computing3.4 (1991), pp. 376–384

    work page 1991

  26. [26]

    Columngenerationforbi-objectivevehicle routingproblemswithamin-maxobjective

    BoaduMensahSarpong,ChristianArtigues,andNicolasJozefowiez.“Columngenerationforbi-objectivevehicle routingproblemswithamin-maxobjective”.In:ATMOS-13thWorkshoponAlgorithmicApproachesforTransportation Modelling, Optimization, and Systems-2013. Vol. 33. Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik. 2013, pp. 137–149

    work page 2013

  27. [27]

    Traveling salesperson problems for the Dubins vehicle

    Ketan Savla, Emilio Frazzoli, and Francesco Bullo. “Traveling salesperson problems for the Dubins vehicle”. In: IEEE Transactions on Automatic Control53.6 (2008), pp. 1378–1391

    work page 2008

  28. [28]

    Market approach to length constrained min-max multiple depot multiple traveling salesman problem

    Drew Scott et al. “Market approach to length constrained min-max multiple depot multiple traveling salesman problem”. In:2020 American Control Conference (ACC). IEEE. 2020, pp. 138–143

    work page 2020

  29. [29]

    A parametric, second-order cone representable model of fairnessfordecision-makingproblems

    Kaarthik Sundar, Deepjyoti Deka, and Russell Bent. “A parametric, second-order cone representable model of fairnessfordecision-makingproblems”.In:OptimizationandEngineering(2025),pp.1–16.doi:10.1007/s11081- 024-09946-9. arXiv:2412.05143 [math.OC]

    work page doi:10.1007/s11081- 2025

  30. [30]

    Fairly extreme: Minimizing outages equitably

    Kaarthik Sundar, Deepjyoti Deka, and Russell Bent. “Fairly extreme: Minimizing outages equitably”. In:arXiv preprint arXiv:2310.01348(2023)

    work page arXiv 2023

  31. [31]

    Algorithmsforheterogeneous,multipledepot,multipleunmanned vehicle path planning problems

    KaarthikSundarandSivakumarRathinam.“Algorithmsforheterogeneous,multipledepot,multipleunmanned vehicle path planning problems”. In:Journal of Intelligent & Robotic Systems88 (2017), pp. 513–526

    work page 2017

  32. [32]

    An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem

    Kaarthik Sundar and Sivakumar Rathinam. “An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem”. In:2015 International Conference on Unmanned Aircraft Systems (ICUAS). IEEE. 2015, pp. 366–371

    work page 2015

  33. [33]

    A branch-and-price algorithm for a team orien- teering problem with fixed-wing drones

    Kaarthik Sundar, Sujeevraja Sanjeevi, and Christopher Montez. “A branch-and-price algorithm for a team orien- teering problem with fixed-wing drones”. In:EURO Journal on Transportation and Logistics11 (2022), p. 100070

    work page 2022

  34. [34]

    SIAM, 2002

    Paolo Toth and Daniele Vigo.The vehicle routing problem. SIAM, 2002

    work page 2002

  35. [35]

    A two-stage approach for routing mul- tiple unmanned aerial vehicles with stochastic fuel consumption

    Saravanan Venkatachalam, Kaarthik Sundar, and Sivakumar Rathinam. “A two-stage approach for routing mul- tiple unmanned aerial vehicles with stochastic fuel consumption”. In:Sensors18.11 (2018), p. 3756

    work page 2018

  36. [36]

    To be fair or efficient or a bit of both

    Moshe Zukerman et al. “To be fair or efficient or a bit of both”. In:Computers & operations research35.12 (2008), pp. 3787–3806. 26

    work page 2008