# 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 48 48 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 52 52 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 127 127 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 150 150 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 8 8 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 195 195 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 8 8 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)
subject to
Linear ≤ Const (constraint on budget allocated for “building roads”)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–

Dataset 8 8 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”)
subject to
Linear(TSP) ≤ Const (constraint on the length of tour)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–

Dataset 8 8 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 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.