Traveling Salesman Problem

Question 1

Name typical TSP

Answer 1

• determination of cost-minimal tours for couriers or vehicles
• determination optimal operating sequences on machines
• several hard variants of postman problems can be solved as
  TSP
• subproblem of vehicle routing problems

Question 2

What are classical TSP

Answer 2

TSP without additional constraints; called
classical TSP

additional constraints:

• precedence constraints
• travel times and time windows
• time-dependent travel times

Question 3

How do we obtain the distance matrices D = (dij) for vehicles or couriers
in real-world TSPs?

Answer 3

• Geographic information systems (GIS): base data of street network
• -> types street segments
• -> lengths of street segments
• -> possible speeds
• -> turning possibilities

Question 4

Dantzig-Fulkerson-Johnson formulation (DFJ) - characteristics

Answer 4

• suitable for the ATSP (consequently also for the STSP)
• n(n − 1) binary variables, exponentially many constraints
• Advantage: strong LP relaxation

Question 5

Miller-Tucker-Zemlin formulation (MTZ)

- characteristics

Answer 5

• suitable for the ATSP (consequently also for the STSP)
• n(n − 1) binary and n − 1 continuous variables, quadratic number
  of constraints
• Disadvantage: weaker LP relaxation

Question 6

2-matching formulation - characteristics

Answer 6

• suitable for the STSP
• n(n − 1)/2 binary variables, exponentially many constraints
• Advantage: strong LP relaxation

Question 7

Comparisment of DFJ and MTZ

Answer 7

• MTZ advantage: number of variables and constraints is quadratic
  in number of nodes → smaller model, can be directly formulated
• MTZ disadvantage: objective value of LP relaxation of MTZ is
  usually clearly below objective value of LP relaxation of DFJ →
  inferior bounds
• High-quality off-the-shelf mixed integer programming solvers
  (CPLEX, SCIP, . . . ) solve MTZ formulation for Euclidean TSP
  instances with 30-40 nodes (or even bigger) without problems