The Travelling Salesman Problem - MTZ Model

image-4.png

Santa Claus needs to visit 15 chimneys as quickly as possible to deliver presents to the children who have been good in 2020 and stuck to social distancing rules.

Can you help him find the shortest route crossing each home exactly once and return to the first home to then go back to the North Pole from there?

Santa has asked you to obtain the best possible solution to this problem.

Since Santa has asked for the best solution, we need to use an exact solution technique. We can therefore proceed to implement a mathematical model that implements the Miller, Tucker and Zemlin subtour elimination constraints (SECs).

We proceed to implement the model using PuLP. For the purposes of this notebook, we obtain the locations of the chimneys using our trusty blob maker.

We are back again in using PuLP.