BMTSP Optimization

01 Problem and context

The Bounded Multiple TSP distributes a set of cities among multiple salespersons departing from a single depot, subject to lower and upper bounds per route. It is NP-hard and translates directly to fleet routing. Because no single method dominates, the actionable question is not which algorithm solves it, but rather the trade-offs each family offers under an identical experimental budget.

The Bounded Multiple TSP splits a set of cities among several salesmen leaving from a shared depot, with a lower and an upper bound on how many cities each tour may cover. It is NP-hard and maps directly onto fleet routing, where those bounds stand in for shift length and vehicle capacity. Since no single method dominates, the useful question is not which algorithm solves it, but what each family of approaches buys and costs under an identical experimental budget.

02 Solution

A standardized experimental protocol across four approaches: an exact MIP benchmark in AMPL/CPLEX, state-of-the-art LKH-3, an Artificial Immune System built from scratch, and a Nearest Neighbor baseline with 2-Opt. Tested across five TSPLIB instances, with ten independent runs per instance, logged seeds, and reporting the full dispersion rather than just the best run.

1. 01MIP formulation of the BMTSP in AMPL, solved with CPLEX under a time limit, as the exact reference point.
2. 02Artificial Immune System written from scratch: 50 antibodies, 10 clones each, three mutation operators and an explicit penalty for solutions that break the bounds.
3. 03Nearest Neighbour plus 2-Opt local search as a constructive baseline, with a feasibility check before any cost is reported.
4. 04LKH-3 run on the same instances, so the comparison is against the state of the art rather than a weak opponent.
5. 05One experimental protocol shared by all four methods: five TSPLIB instances (berlin52, eil51, eil76, kroA100, rat99) and ten independent runs per instance with recorded seeds.
6. 06Per-iteration logging of best fitness and elapsed time, consolidated with minimum, maximum, mean and standard deviation.

03 Results

Verifiable figures in the repository and its documentation:

04 How it's built

An experimental study of the Bounded Multiple Traveling Salesman Problem (BMTSP), an NP-hard variant of the TSP featuring multiple salesmen and route size bounds. It implements and compares four approaches: an exact mixed-integer programming model in AMPL/CPLEX, the LKH-3 heuristic solver, a custom Artificial Immune System (AIS) metaheuristic, and a Nearest Neighbor heuristic with 2-Opt refinement. Experiments are automated in Python across five classic TSPLIB instances, with multiple runs per instance and results exported to CSV.

05 Ethical decisions

• ✦Every run stores its seed alongside its results, so any individual run can be reproduced and audited on its own.
• ✦All ten runs are reported with their spread, not just the best one, so a lucky result is never passed off as typical behaviour.
• ✦The in-house metaheuristic is measured against LKH-3, the strongest solver available, rather than against a comfortable baseline.

06 Highlights

• ✦MIP mathematical model for the BMTSP, formulated in AMPL and solved using CPLEX under a time limit.
• ✦Artificial Immune System metaheuristic implemented from scratch, featuring cloning, three mutation operators, and parallel execution.
• ✦Custom Nearest Neighbor heuristic + 2-Opt local search as a constructive baseline.
• ✦Automated experimental pipeline across 5 TSPLIB instances (berlin52, eil51, eil76, kroA100, rat99) with 10 runs per instance.
• ✦Quantitative cost comparison against the state-of-the-art LKH-3 benchmark, documented in the README.

07 Limitations

TSPLIB instances are Euclidean, symmetric and moderate in size, between 51 and 100 nodes. That makes them comparable and reproducible, but it leaves out what actually makes routing hard: one-way streets, time-dependent travel, delivery windows and fleets of hundreds of vehicles. Two limits of the method itself are worth stating: the infeasibility penalty is a single very large constant, which discourages exploring the feasible frontier, and the Nearest Neighbour plus 2-Opt baseline is deterministic and runs once, so it carries no spread of its own to compare against the metaheuristic's variance.