Essec\Faculty\Model\Contribution {#6196`
#_index: "academ_contributions"
#_id: "12114"
#_source: array:25 [``
"id" => "12114"
"slug" => "complexity-and-reducibility-of-the-skip-delivery-problem"
"yearMonth" => "2005-05"
"year" => "2005"
"title" => "Complexity and Reducibility of the Skip Delivery Problem"
"description" => "ARCHETTI, C., MANSINI, R. et SPERANZA, M.G. (2005). Complexity and Reducibility of the Skip Delivery Problem. <i>Transportation Science</i>, 39(2), pp. 182-187."
"authors" => array:3 [``
0 => array:3 [``
"name" => "ARCHETTI Claudia"
"bid" => "B00773540"
"slug" => "archetti-claudia"
`]
1 => array:1 [`
"name" => "MANSINI Renata"
`]
2 => array:1 [`
"name" => "SPERANZA Maria Grazia"
`]
]
"ouvrage" => ""
"keywords" => array:5 [`
0 => "vehicle routing"
1 => "skip delivery problem"
2 => "split delivery"
3 => "triangle inequality"
4 => "computational complexity"
`]
"updatedAt" => "2021-07-13 14:31:59"
"publicationUrl" => "https://pubsonline.informs.org/doi/10.1287/trsc.1030.0084"
"publicationInfo" => array:3 [`
"pages" => "182-187"
"volume" => "39"
"number" => "2"
`]
"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 the skip delivery problem (SDP), a fleet of vehicles must deliver skips to a set of customers. Each vehicle has a maximum capacity of two skips, and has to start and end its tour at a central depot. The demand of each customer can be greater than the capacity of the vehicles. The objective is to minimize the cost of the total distance traveled by the vehicles to serve all the customers. We show that the SDP is solvable in polynomial time, while its generalization to the case where all vehicles have a capacity greater than two, known as the split delivery vehicle routing problem (SDVRP), is shown to be NP-hard, even under restricted conditions on the costs. We also show that, if the costs are symmetrical and satisfy the triangle inequality, the SDP is reducible in polynomial time to a problem of possibly smaller size, where each customer has unitary demand. This property allows a remarkable simplification of the problem."
"en" => "In the skip delivery problem (SDP), a fleet of vehicles must deliver skips to a set of customers. Each vehicle has a maximum capacity of two skips, and has to start and end its tour at a central depot. The demand of each customer can be greater than the capacity of the vehicles. The objective is to minimize the cost of the total distance traveled by the vehicles to serve all the customers. We show that the SDP is solvable in polynomial time, while its generalization to the case where all vehicles have a capacity greater than two, known as the split delivery vehicle routing problem (SDVRP), is shown to be NP-hard, even under restricted conditions on the costs. We also show that, if the costs are symmetrical and satisfy the triangle inequality, the SDP is reducible in polynomial time to a problem of possibly smaller size, where each customer has unitary demand. This property allows a remarkable simplification of the problem."
`]
"authors_fields" => array:2 [`
"fr" => "Systèmes d’Information, Sciences de la Décision et Statistiques"
"en" => "Information Systems, Decision Sciences and Statistics"
`]
"indexedAt" => "2023-12-10T23:22:14.000Z"
"docTitle" => "Complexity and Reducibility of the Skip Delivery Problem"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/archetti-claudia">ARCHETTI Claudia</a>, MANSINI Renata, SPERANZA Maria Grazia"
"docDescription" => "<span class="document-property-authors">ARCHETTI Claudia, MANSINI Renata, 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">2005</span>"
"keywordList" => "<a href="#">vehicle routing</a>, <a href="#">skip delivery problem</a>, <a href="#">split delivery</a>, <a href="#">triangle inequality</a>, <a href="#">computational complexity</a>"
"docPreview" => "<b>Complexity and Reducibility of the Skip Delivery Problem</b><br><span>2005-05 | Articles </span>"
"docType" => "research"
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.847877
+"parent": null
}