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
——————————————————————–————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset1 2304 – 10628.0 8.34
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data
# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset2 2704 – 7542.0 0.23
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
R R Code Data
# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset3 16129 – 118282.0 375.73
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset4 22500 – 6528.0 713.46
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset5 64 – 95.0 0.02
Environments
Run-File Problem Statement Data Solution
Matlab Toolbox Data
Matlab Subroutines Matlab Code Data
# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset6 38025 – 2323.0 419.77
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
——————————————————————–————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset 64 – 281.0 0.05
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)
subject to
Linear ≤ Const (constraint on budget allocated for “building roads”)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset 64 – 194.0 0.03
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”)
subject to
Linear(TSP) ≤ Const (constraint on the length of tour)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–

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

 

CASE STUDY SUMMARY
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 VanGrb for solving problems with TSP operator.
Problems were solved with data downloaded from the link [1].

 

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