Case Study: Travelling Salesman

Back to main page

Case study background and problem formulations

Instructions for optimization with PSG Run-File, PSG MATLAB Toolbox, PSG MATLAB Subroutines and PSG R.

PROBLEM1: problem_TSP Minimize Linear(TSP) (solve plain TSP) ——————————————————————–————————————– TSP = Travelling Salesman Problem ——————————————————————–————————————–

Dataset1	2304	-	10628.0	8.34
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

Dataset2	2704	-	7542.0	0.23
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

Dataset3	16129	-	118282.0	375.73
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data

Dataset4	22500	-	6528.0	713.46
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data

Dataset5	64	-	95.0	0.02
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data

Dataset6	38025	-	2323.0	419.77
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data

PROBLEM2: problem_MAX_TSP Maximize Linear(TSP) (find tour in a graph with maximal weight) ——————————————————————–————————————– TSP = Travelling Salesman Problem ——————————————————————–————————————–

Dataset	64	-	281.0	0.05
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

PROBLEM3: problem_TSP_with_budget Minimize Linear(TSP) (minimize length of tour)nsubject to
Linear ≤ Const (constraint on budget allocated for “building roads”) ——————————————————————–————————————– TSP = Travelling Salesman Problem ——————————————————————–————————————–

Dataset	64	-	194.0	0.03
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

PROBLEM4: problem_TSP_in_constraint Minimize Linear (minimize budget allocated for “building roads”)nsubject to
Linear(TSP) ≤ Const (constraint on the length of tour) ——————————————————————–————————————– TSP = Travelling Salesman Problem ——————————————————————–————————————–

Dataset	64	-	1151.0	0.03
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

CASE STUDY SUMMARYn This case study solves several Travelling Salesman Problems (TSPs). PSG has TSP operator for a compact formulation of problems. The length of the path which goes through all vertices of the graph is calculated with the operator “linear(TSP(matrix_of_distances))”. TSP optimization problems can be solved only if Gurobi package is installed at the computer. PSG is using Gurobi-based solvers CarGrb or Va
Grb for solving problems with TSP operator. Problems were solved with data downloaded from the link [1].

References [1] https://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.