Data · AI · Research
BMTSP Optimization
Comparison of four optimization approaches for the Bounded Multiple TSP on TSPLIB instances.
procedural cover — real screenshots pendingProcedural cover for the project BMTSP Optimization.
01 Summary
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.
02 Results
Verifiable figures in the repository and its documentation:
4métodos comparados
5instancias TSPLIB
03 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.
04 Screenshots
Screenshot pending
Interface — pending