The Traveling Salesman Problem

Prerequisites

• Please look at Getting Started first for the most basic functions and the setup of OPTANO.Modeling

The mathematical Model

Sets: \begin{array}{l} V = \text{Set of }n\text{ nodes}\newline E = \text{Set of edges }(VxV) \end{array}

Parameters: $$d_{ij} = \text{distance from node }i\text{ to node }j$$

Variables: $$y_{ij} = \begin{cases} 1, \text{ if you travel on the edge from}i\text{ to }j\newline 0, \text{ else} \end{cases}$$ $$z_{i} \in {0 .. |V|-1}: \text{Position of Node } i \text{ in tour}$$ Objective: $$min \sum\limits_{(i,j)\in E} d_{ij} y_{ij}$$

Restrictions: \begin{array}{l} \sum\limits_{{i:(i,j)\in E}} y_{ij} = 1 & \qquad \forall j\in V & \text{(Exactly one incoming edge)}\newline \sum\limits_{{k:(j,k)\in E}} y_{jk} = 1 & \qquad \forall j\in V & \text{(Exactly one outgoing edge)}\newline z_i - z_j + |V| * y_{ij} \le |V| - 1 & \qquad \forall (i,j) \in E: i, j \text{ are no start node} & \text{(Exactly one outgoing edge)} \end{array}

The Traveling Salesman Problem

• Step 1: Create Business objects for your Model
• Step 2: Create your Model Class
• Step 3: Retrieve the Solution of your Model