Essec\Faculty\Model\Contribution {#6196
  #_index: "academ_contributions"
  #_id: "12112"
  #_source: array:26 [
    "id" => "12112"
    "slug" => "reoptimizing-the-traveling-salesman-problem"
    "yearMonth" => "2003-10"
    "year" => "2003"
    "title" => "Reoptimizing the traveling salesman problem"
    "description" => "ARCHETTI, C., BERTAZZI, L. et SPERANZA, M.G. (2003). Reoptimizing the traveling salesman problem. <i>Networks</i>, 42(3), pp. 154-159."
    "authors" => array:3 [
      0 => array:3 [
        "name" => "ARCHETTI Claudia"
        "bid" => "B00773540"
        "slug" => "archetti-claudia"
      ]
      1 => array:1 [
        "name" => "BERTAZZI Luca"
      ]
      2 => array:1 [
        "name" => "SPERANZA Maria Grazia"
      ]
    ]
    "ouvrage" => ""
    "keywords" => array:1 [
      0 => "reoptimization problems"
    ]
    "updatedAt" => "2021-07-13 14:31:59"
    "publicationUrl" => "https://onlinelibrary.wiley.com/doi/abs/10.1002/net.10091"
    "publicationInfo" => array:3 [
      "pages" => "154-159"
      "volume" => "42"
      "number" => "3"
    ]
    "type" => array:2 [
      "fr" => "Articles"
      "en" => "Journal articles"
    ]
    "support_type" => array:2 [
      "fr" => "Revue scientifique"
      "en" => "Scientific journal"
    ]
    "countries" => array:2 [
      "fr" => null
      "en" => null
    ]
    "abstract" => array:2 [
      "fr" => "In this paper, we study the reoptimization problems which arise when a new node is added to an optimal solution of a traveling salesman problem (TSP) instance or when a node is removed. We show that both reoptimization problems are NP‐hard. Moreover, we show that, while the cheapest insertion heuristic has a tight worst‐case ratio equal to 2 when applied to a TSP instance, it guarantees, in linear time, a tight worst‐case ratio equal to 3/2 when used to add the new node and that also the simplest heuristic to remove a node from the optimal tour guarantees a tight ratio equal to 3/2 in constant time."
      "en" => "In this paper, we study the reoptimization problems which arise when a new node is added to an optimal solution of a traveling salesman problem (TSP) instance or when a node is removed. We show that both reoptimization problems are NP‐hard. Moreover, we show that, while the cheapest insertion heuristic has a tight worst‐case ratio equal to 2 when applied to a TSP instance, it guarantees, in linear time, a tight worst‐case ratio equal to 3/2 when used to add the new node and that also the simplest heuristic to remove a node from the optimal tour guarantees a tight ratio equal to 3/2 in constant time."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d’Information, Sciences de la Décision et Statistiques"
      "en" => "Information Systems, Decision Sciences and Statistics"
    ]
    "indexedAt" => "2024-04-18T21:22:06.000Z"
    "docTitle" => "Reoptimizing the traveling salesman problem"
    "docSurtitle" => "Articles"
    "authorNames" => "<a href="/cv/archetti-claudia">ARCHETTI Claudia</a>, BERTAZZI Luca, SPERANZA Maria Grazia"
    "docDescription" => "<span class="document-property-authors">ARCHETTI Claudia, BERTAZZI Luca, SPERANZA Maria Grazia</span><br><span class="document-property-authors_fields">Systèmes d’Information, Sciences de la Décision et Statistiques</span> | <span class="document-property-year">2003</span>"
    "keywordList" => "<a href="#">reoptimization problems</a>"
    "docPreview" => "<b>Reoptimizing the traveling salesman problem</b><br><span>2003-10 | Articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://onlinelibrary.wiley.com/doi/abs/10.1002/net.10091" target="_blank">Reoptimizing the traveling salesman problem</a>"
  ]
  +lang: "fr"
  +"_type": "_doc"
  +"_score": 8.72674
  +"parent": null
}