TSP Algorithm Lab

A full-stack educational laboratory for exploring and comparing algorithms for the Travelling Salesperson Problem (TSP).

The project combines a Spring Boot REST backend, a React and TypeScript visualization frontend, and a custom TSPLIB parser. It was developed as a team project for the Efficient Algorithms module at Hochschule Bremen.

Highlights

• Browse and parse TSPLIB benchmark instances and known tours
• Visualize Euclidean instances as interactive graphs
• Explore geographical instances with Leaflet maps and route overlays
• Run multiple exact, approximate, heuristic, and metaheuristic algorithms
• Compare several Simulated Annealing implementations in an LLM Battle view
• Inspect runtime, tour length, path validity, and implementation characteristics
• Use a project-specific TSPLIB parser instead of relying only on an external parser library

Implemented algorithms

Algorithm	Category	Purpose
Nearest Neighbor	Greedy heuristic	Fast construction of a valid tour
Dynamic Programming	Exact algorithm	Optimal solution for small instances; limited to 26 nodes
Christofides	Approximation algorithm	Structured approximation for metric TSP instances
Simulated Annealing	Metaheuristic	Stochastic search with controlled acceptance of worse solutions
Dantzig–Fulkerson–Johnson ILP	Integer linear programming	Iterative subtour elimination using the project's own simplex/ILP components
Claude SA variant	LLM comparison	Alternative Simulated Annealing implementation
Gemma SA variant	LLM comparison	Alternative Simulated Annealing implementation
Qwen3-Coder-Next SA variant	LLM comparison	Alternative Simulated Annealing implementation

The LLM-generated variants are included for comparative and educational purposes. They are evaluated using the same project data structures and common parameters.

Architecture

flowchart LR
    UI[React + TypeScript frontend] -->|REST / JSON| API[Spring Boot API]
    API --> ALG[Algorithm implementations]
    API --> ADAPTER[TSPLIB adapter]
    ADAPTER --> PARSER[Custom TSPLIB parser]
    PARSER --> DATA[TSPLIB benchmark files]
    ALG --> UI

Loading

Modules

tsp-algorithm-lab/
├── ealg-application/        # Spring Boot API and TSP algorithms
├── ealg-own-tsp-lib/        # Custom TSPLIB parser and data model
├── ealg-react-frontend/     # React, TypeScript, graph and map visualizations
├── docs/                    # Architecture and algorithm documentation
├── .github/workflows/       # Continuous integration
├── CONTRIBUTORS.md
├── THIRD_PARTY_NOTICES.md
└── pom.xml                  # Multi-module Maven parent

More detail is available in:

• Architecture
• Algorithm overview
• Backend documentation
• Frontend documentation
• Parser library documentation

Technology stack

Area	Technology
Backend	Java 17, Spring Boot 2.7, Spring Web
API documentation	OpenAPI / Swagger UI
Frontend	React 18, TypeScript, Webpack
UI components	RSuite
Graph visualization	Cytoscape and Graphology-based components
Maps	Leaflet and React Leaflet
Build tools	Maven and npm
Benchmark format	TSPLIB
CI	GitHub Actions

Prerequisites

• Java 17 or newer
• Maven 3.9 or newer
• Node.js 18 or newer
• npm 9 or newer

The repository does not include generated dependency folders or build output. Run the installation commands after cloning.

Running locally

1. Start the backend

Install the Maven modules once from the repository root:

mvn install -DskipTests -Dskip.frontend.assets=true

Then start the application module:

mvn -f ealg-application/pom.xml -Dskip.frontend.assets=true spring-boot:run

The backend is available at:

http://localhost:8080/tsp

2. Start the frontend

In a second terminal:

cd ealg-react-frontend
npm install
npm start

The frontend is available at:

http://localhost:3100

Production build

Build the frontend first so its static output can be included by the backend build:

cd ealg-react-frontend
npm ci
npm run build
cd ..
mvn clean verify

Frontend output is generated in ealg-react-frontend/assets/. Build output is ignored by Git.

API overview

The backend uses the /tsp context path. Important routes include:

Method	Route	Description
GET	/tsp/api/tspInstances/meta	List metadata for bundled TSP instances
GET	/tsp/api/tspInstances/geo/meta	List geographical TSP instances
GET	/tsp/api/tspInstance?tspName=berlin52	Parse and return one TSP instance
GET	/tsp/api/tourInstances	Return bundled known tours
GET	/tsp/api/possibleAlgorithms	List registered algorithms
GET	/tsp/api/possibleAlgorithms/{algorithm}/tspInstance/{instance}	Solve an instance using the selected algorithm

Swagger UI is normally available at:

http://localhost:8080/tsp/swagger-ui/index.html

Validation

Frontend:

cd ealg-react-frontend
npm run typecheck
npm run build

Backend and parser library:

mvn clean verify

Contributors

This was a collaborative course project by:

• Serkay Celik
• Nour Ahmad
• Ahmet Kislali

See CONTRIBUTORS.md for project roles and contribution notes.

Data and third-party material

The repository contains TSPLIB benchmark instances and generated API client code. The project team does not claim ownership of third-party benchmark data or libraries. See THIRD_PARTY_NOTICES.md.

Course slides, papers, presentation exports, dependency folders, and generated build artifacts have intentionally been excluded from this public portfolio package.

License

No open-source license is granted for the project-specific source code. The repository is shared as academic and portfolio work. Third-party components remain subject to their respective licenses and terms.