mTSP_problem.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o23N8-O5BJpf"
      },
      "source": [
        "# Multiple Traveling Salesman Problem (_mTSP_)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xk1BV4xgBckt"
      },
      "source": [
        "### Objetivos:\n",
        "\n",
        "- **Modelar** soluções para o problema de programação linear para _mTSP_.\n",
        "- **Implementar** a solução do problema em Julia."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1_wX44H2Byi4"
      },
      "source": [
        "No _mTSP_, problema das rotas de cidades você recebe um conjunto de cidades e as distâncias entre cada par de cidades. Sua tarefa é determinar um conjunto de **m** rotas percorrida por caixeiros vianjantes que começam em uma cidade específica e seguem um percurso que visita cada cidade exatamente uma vez, garantindo que cada uma das rotas retorne à cidade inicial.\n",
        "\n",
        "Fique a vontade para checar os [rascunhos](https://www.canva.com/design/DAFvtaC7sSk/D_y2dgRoxvZvA8Ri5RxS1Q/edit?utm_content=DAFvtaC7sSk&utm_campaign=designshare&utm_medium=link2&utm_source=sharebutton) escritos durante a modelagem do problema original."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gdf5FMZnCFcA"
      },
      "source": [
        "## Variáveis do problema:\n",
        "\n",
        "- Descreve o **índice** de cada cidade _i_ no momento da construção das rotas, para cada caixeiro _k_:\n",
        "$$indice_{cidade_icaixeiro_k} \\in \\mathbb{R}$$\n",
        "\n",
        "- Descreve as **rotas** do caixeiro _k_ em relação a cidade _i_ e a cidade _j_:\n",
        "$$viajou_{cidade_icidade_jcaixeiro_k}\\in \\{0,1\\}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ug3OpW8-CJfm"
      },
      "source": [
        "## Função Objetivo:\n",
        "\n",
        "O objetivo do problema é fazer com que todas as cidades sejam percorridas e que no final, os caixeiros andem menos. A distancia percorrida pelos carteiros é dada por:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\\begin{align*}\n",
        "distanciapercorrida(args[]) = \\min \\{\\sum_{k=1}^{caixeiros} \\sum_{j=1}^{cidades} \\sum_{i=1}^{cidades} distancia_{cidade_icidade_j}.viajou_{cidade_icidade_jcaixeiro_k}\\}\n",
        "\\end{align*}\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "A fórmula percorre a matriz somando a distância da rota iterada da cidade i para a cidade j caso o carteiro k tenha viajado usando aquela rota. Portanto, os argumentos args da função são descritos por:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\\begin{align*}\n",
        "args[] = [carteiros, distancia[cidades][cidades]]  \n",
        "\\end{align*}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CWwXZTZsCLZ8"
      },
      "source": [
        "## Restrições:\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Para garantir que as condições sejam satisfeitas, foram modeladas <strong>restrições</strong>. Para assegurar que os carteiros saiam da mesma cidade e cheguem na mesma cidade obrigatoriamente, foram modelas as seguintes restrições as seguintes restrições:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\\begin{align*}\n",
        "  carteiros = \\sum_{k=1}^{caixeiros} \\sum_{i=2}^{cidades} viajou_{cidade_icidade_1caixeiro_k}\n",
        "\\end{align*}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\\begin{align*}\n",
        "  carteiros = \\sum_{k=1}^{caixeiros} \\sum_{j=2}^{cidades} viajou_{cidade_1cidade_jcaixeiro_k}\n",
        "\\end{align*}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Para garantir que não haja repetição de cidades entre os caxeiros, devemos limitar as rotas da matriz da variável _viajou_:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\\begin{align*}\n",
        "  \\sum_{k=1}^{caixeiros} \\sum_{i=1}^{cidades} viajou_{cidade_icidade_jcaixeiro_k} = 1\n",
        "\\end{align*}\n",
        "$$\\forall i!=j$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\\begin{align*}\n",
        "  \\sum_{k=1}^{caixeiros} \\sum_{j=1}^{cidades} viajou_{cidade_icidade_jcaixeiro_k} = 1\n",
        "\\end{align*}\n",
        "$$\\forall j!=i$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Para fins de garantir evitar uma rota com mais de um ciclo para todo caixeiro _k_ usamos a várivel _indice_ que garante que exista uma sempre exista uma \"progressão\" na rota do caixeiro:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\\begin{align*}\n",
        "  cidades-1 \\geq indice_{cidade_icaixeiro_k} - indice_{cidade_jcaixeiro_k} + cidades.viajou{cidade_icidade_jcaixeiro_k}\n",
        "\\end{align*}\n",
        "$$\\forall j!=i$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Por último, devemos garantir que cada rota escolhida pelo carteiro _k_ seja necessariamente um ciclo:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\\begin{align*}\n",
        "  \\sum_{k=1}^{caixeiros} \\sum_{i=1}^{cidades} viajou_{cidade_icidade_jcaixeiro_k} = \\sum_{i=1}^{cidades} viajou_{cidade_jcidade_icaixeiro_k}\n",
        "\\end{align*}\n",
        "$$\\forall j!=i$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xXpMZeJUBZS7"
      },
      "source": [
        "## Implementação em Julia:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h-zRQzWIzG4x"
      },
      "source": [
        "Prepare o ambiente de execução (Google Colab):"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "uEi5MADlBJTx"
      },
      "outputs": [],
      "source": [
        "%%shell\n",
        "set -e\n",
        "\n",
        "#---------------------------------------------------#\n",
        "JULIA_VERSION=\"1.6.7\" # any version ≥ 0.7.0\n",
        "JULIA_PACKAGES=\"IJulia BenchmarkTools\"\n",
        "JULIA_PACKAGES_IF_GPU=\"CUDA\" # or CuArrays for older Julia versions\n",
        "JULIA_NUM_THREADS=2\n",
        "#---------------------------------------------------#\n",
        "\n",
        "if [ -z `which julia` ]; then\n",
        "  # Install Julia\n",
        "  JULIA_VER=`cut -d '.' -f -2 <<< \"$JULIA_VERSION\"`\n",
        "  echo \"Installing Julia $JULIA_VERSION on the current Colab Runtime...\"\n",
        "  BASE_URL=\"https://julialang-s3.julialang.org/bin/linux/x64\"\n",
        "  URL=\"$BASE_URL/$JULIA_VER/julia-$JULIA_VERSION-linux-x86_64.tar.gz\"\n",
        "  wget -nv $URL -O /tmp/julia.tar.gz # -nv means \"not verbose\"\n",
        "  tar -x -f /tmp/julia.tar.gz -C /usr/local --strip-components 1\n",
        "  rm /tmp/julia.tar.gz\n",
        "\n",
        "  # Install Packages\n",
        "  nvidia-smi -L &> /dev/null && export GPU=1 || export GPU=0\n",
        "  if [ $GPU -eq 1 ]; then\n",
        "    JULIA_PACKAGES=\"$JULIA_PACKAGES $JULIA_PACKAGES_IF_GPU\"\n",
        "  fi\n",
        "  for PKG in `echo $JULIA_PACKAGES`; do\n",
        "    echo \"Installing Julia package $PKG...\"\n",
        "    julia -e 'using Pkg; pkg\"add '$PKG'; precompile;\"' &> /dev/null\n",
        "  done\n",
        "\n",
        "  # Install kernel and rename it to \"julia\"\n",
        "  echo \"Installing IJulia kernel...\"\n",
        "  julia -e 'using IJulia; IJulia.installkernel(\"julia\", env=Dict(\n",
        "      \"JULIA_NUM_THREADS\"=>\"'\"$JULIA_NUM_THREADS\"'\"))'\n",
        "  KERNEL_DIR=`julia -e \"using IJulia; print(IJulia.kerneldir())\"`\n",
        "  KERNEL_NAME=`ls -d \"$KERNEL_DIR\"/julia*`\n",
        "  mv -f $KERNEL_NAME \"$KERNEL_DIR\"/julia\n",
        "\n",
        "  echo ''\n",
        "  echo \"Julia `julia -v` instalado com sucesso!\"\n",
        "  echo \"Recarregue esta página (pressione Ctrl+R, ⌘+R ou a tecla F5) e depois\"\n",
        "  echo \"vá para a seção 'Verificação da Instalação'.\"\n",
        "fi"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Rm2yFTY8zJkn"
      },
      "source": [
        "Importe os pacotes do Solver de problemas lineares:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "bq6UOgnnzLPN"
      },
      "outputs": [],
      "source": [
        "import Pkg; Pkg.add(\"JuMP\"); Pkg.add(\"Cbc\");Pkg.add(\"Arrow\");Pkg.add(\"Plots\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Funções Utiliárias"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "function generate_distance_matrix(n, random_seed = 2)\n",
        "    rng = Random.MersenneTwister(random_seed)\n",
        "    X = 100 * rand(rng, n)\n",
        "    Y = 100 * rand(rng, n)\n",
        "    return X, Y\n",
        "end\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oXdVXYKUzRjq"
      },
      "source": [
        "Declare o modelo, e defina tempo limite para processamento:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "using JuMP, Cbc, Plots, Arrow\n",
        "model = Model(Cbc.Optimizer)\n",
        "set_time_limit_sec(model,30) # 30 segundos\n",
        "set_optimizer_attribute(model, \"LogLevel\", 0)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oxbZulcmz0Pq"
      },
      "source": [
        "Exemplos de entrada:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "vC5AWxOkHkgz"
      },
      "outputs": [],
      "source": [
        "m = 3"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "foiM7p11Hlp0"
      },
      "outputs": [],
      "source": [
        "m = 2"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "NCFT8apKz61S"
      },
      "outputs": [],
      "source": [
        "# Exemplo 1:\n",
        "c =\n",
        "[ 0 3 5 48 48 8 ;\n",
        "3 0 3 48 48 8 ;\n",
        "5 3 0 72 72 48 ;\n",
        "48 48 74 0 0 6 ;\n",
        "48 48 74 0 0 6 ;\n",
        "8 8 50 6 6 0 ]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cZYUqBacz_ej",
        "outputId": "6376824d-72cb-40c8-bd85-314c747a58bb"
      },
      "outputs": [],
      "source": [
        "# Exemplo 2:\n",
        "c =\n",
        "[ 0 3 5 48 48 8 8 5 5 3 3 0 3 5 8 8 5;\n",
        "3 0 3 48 48 8 8 5 5 0 0 3 0 3 8 8 5;\n",
        "5 3 0 72 72 48 48 24 24 3 3 5 3 0 48 48 24;\n",
        "48 48 74 0 0 6 6 12 12 48 48 48 48 74 6 6 12;\n",
        "48 48 74 0 0 6 6 12 12 48 48 48 48 74 6 6 12;\n",
        "8 8 50 6 6 0 0 8 8 8 8 8 8 50 0 0 8;\n",
        "8 8 50 6 6 0 0 8 8 8 8 8 8 50 0 0 8;\n",
        "5 5 26 12 12 8 8 0 0 5 5 5 5 26 8 8 0;\n",
        "5 5 26 12 12 8 8 0 0 5 5 5 5 26 8 8 0;\n",
        "3 0 3 48 48 8 8 5 5 0 0 3 0 3 8 8 5;\n",
        "3 0 3 48 48 8 8 5 5 0 0 3 0 3 8 8 5;\n",
        "0 3 5 48 48 8 8 5 5 3 3 0 3 5 8 8 5;\n",
        "3 0 3 48 48 8 8 5 5 0 0 3 0 3 8 8 5;\n",
        "5 3 0 72 72 48 48 24 24 3 3 5 3 0 48 48 24;\n",
        "8 8 50 6 6 0 0 8 8 8 8 8 8 50 0 0 8;\n",
        "8 8 50 6 6 0 0 8 8 8 8 8 8 50 0 0 8;\n",
        "5 5 26 12 12 8 8 0 0 5 5 5 5 26 8 8 0]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Declare as variáveis:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "n = length(c[1,:])\n",
        "@variable(model,x[i in 1:n, j in 1:n, k in 1:m; i != j],Bin)\n",
        "@variable(model,0 <= u[i in 1:n, k in 1:m] <= n-1)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Declare a função objetivo:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "z = sum(x[i,j,k]*c[i,j] for i in 1:n, j in 1:n, k in 1:m if i!= j)\n",
        "@objective(model,Min, z)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Declare as restrições do modelo:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Garante que todos os caixeiros saiam no nó inicial\n",
        "@constraint(model, depart1, m == sum( x[1,j,k] for k in 1:m, j in 2:n))\n",
        "# Garante que todos os caixeiros retornem ao nó inicial\n",
        "@constraint(model, comeback1, m == sum( x[j,1,k] for k in 1:m, j in 2:n))\n",
        "# Nova constraint\n",
        "# Garante que o k-ésimo caixeiro saia do primeiro nó apenas uma vez\n",
        "@constraint(model, leaving1[ k in 1:m], 1 == sum( x[1,j,k] for j in 2:n))\n",
        "# Garante que o k-ésimo caixeiro volte primeiro nó apenas uma vez\n",
        "@constraint(model, arriving[ k in 1:m], 1 == sum( x[j,1,k] for j in 2:n))\n",
        "# Garante que o k-ésimo caixeiro chegue em um nó apenas uma vez\n",
        "@constraint(model, arriving[i in 2:n], sum(x[j, i, k] for k in 1:m, j in 1:n if i != j) == 1)\n",
        "# Garante que o k-ésimo caixeiro saia de um nó apenas uma vez\n",
        "@constraint(model, leaving[i in 2:n], sum(x[i, j, k] for k in 1:m, j in 1:n if i != j) == 1)\n",
        "# Evita subrotas\n",
        "@constraint(model,subtourelim[i in 2:n, j in 2:n, k in 1:m ; i!= j], u[i,k] - u[j,k] + n*x[i,j,k] <= n-1)\n",
        "# Garante que todos os caixeiros retornem ao nó inicial\n",
        "@constraint(model, grantCycle[j in 1:n, k in 1:m], sum( x[i,j,k] for i in 1:n if i != j) == sum( x[j,i,k] for i in 1:n if i != j))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Imprima detalhes do modelo:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "print(model)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Otimize o modelo:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "optimize!(model)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Verifique os resultados:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "using Plots\n",
        "using Arrow\n",
        "using Random\n",
        "\n",
        "plot = Plots.plot()\n",
        "cores = [:blue, :red, :green, :purple, :orange, :cyan]\n",
        "\n",
        "X, Y = generate_distance_matrix(n,4)\n",
        "min_value = objective_value(model)\n",
        "Plots.annotate!(maximum(X), maximum(Y) , text(\"Objective Value: $min_value\", :right))\n",
        "\n",
        "for i in 1:n\n",
        "    Plots.annotate!([X[i]], [Y[i]], \"$i\")\n",
        "end\n",
        "\n",
        "for i in 1:n, j in 1:n, k in 1:m\n",
        "    if i!= j && value(x[i,j,k]) == 1\n",
        "        quiver!([X[i]], [Y[i]], quiver = ([X[j] - X[i]], [Y[j] - Y[i]]), color = cores[k])\n",
        "    end\n",
        "end\n",
        "\n",
        "plot"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FdE2jsrwy_Gf"
      },
      "source": [
        "---\n",
        "\n",
        "[Fernando Schettini](https://linktr.ee/fernandoschett) <br/>\n",
        "Intern at the SENAI-CIMATEC Supercomputing Center [CS2I](https://www.senaicimatec.com.br/). <br/>\n",
        "[João Bernardino]() <br/>\n",
        "Computer Science Student at UFBA.<br/>"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.11.3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}