Essec\Faculty\Model\Contribution {#6196`
#_index: "academ_contributions"
#_id: "12156"
#_source: array:25 [``
"id" => "12156"
"slug" => "the-undirected-capacitated-general-routing-problem-with-profits"
"yearMonth" => "2017-03"
"year" => "2017"
"title" => "The Undirected Capacitated General Routing Problem with Profits"
"description" => "ARCHETTI, C., BERTAZZI, L., LAGANÀ, D. et VOCATURO, F. (2017). The Undirected Capacitated General Routing Problem with Profits. <i>European Journal of Operational Research</i>, 257(3), pp. 822-833."
"authors" => array:4 [``
0 => array:3 [``
"name" => "ARCHETTI Claudia"
"bid" => "B00773540"
"slug" => "archetti-claudia"
`]
1 => array:1 [`
"name" => "BERTAZZI Luca"
`]
2 => array:1 [`
"name" => "LAGANÀ Demetrio"
`]
3 => array:1 [`
"name" => "VOCATURO Francesca"
`]
]
"ouvrage" => ""
"keywords" => array:4 [`
0 => "General routing"
1 => "Profits"
2 => "Aggregate formulation"
3 => "Branch-and-cut"
`]
"updatedAt" => "2021-09-24 10:33:27"
"publicationUrl" => "https://doi.org/10.1016/j.ejor.2016.08.001"
"publicationInfo" => array:3 [`
"pages" => "822-833"
"volume" => "257"
"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 introduce and study the Undirected Capacitated General Routing Problem with Profits (UCGRPP). This problem is defined on an undirected graph where a subset of vertices and edges correspond to customers, which are associated with a given profit and demand. The profit of each customer can be collected at most once. A fleet of homogeneous capacitated vehicles is given to serve the customers. The objective is to find the vehicle routes that maximize the difference between the total collected profit and the traveling cost in such a way that the demand collected by each vehicle does not exceed the capacity and the total duration of each route is not greater than a maximum given time limit. We propose a mathematical formulation of the problem and introduce valid inequalities to strengthen the corresponding continuous relaxation. Moreover, we provide an aggregate formulation that allows us to introduce further inequalities. Then, we propose a two–phase exact algorithm for the solution of the UCGRPP. In the first phase, a branch-and-cut algorithm is used to solve the aggregate formulation and to identify a cut pool of aggregate valid inequalities to be used in the second phase, where a branch-and-cut algorithm is implemented to optimally solve the UCGRPP. Computational results on a large set of problem instances show that the use of the aggregate formulation is effective, making the two-phase exact algorithm able to optimally solve a large number of instances."
"en" => "In this paper we introduce and study the Undirected Capacitated General Routing Problem with Profits (UCGRPP). This problem is defined on an undirected graph where a subset of vertices and edges correspond to customers, which are associated with a given profit and demand. The profit of each customer can be collected at most once. A fleet of homogeneous capacitated vehicles is given to serve the customers. The objective is to find the vehicle routes that maximize the difference between the total collected profit and the traveling cost in such a way that the demand collected by each vehicle does not exceed the capacity and the total duration of each route is not greater than a maximum given time limit. We propose a mathematical formulation of the problem and introduce valid inequalities to strengthen the corresponding continuous relaxation. Moreover, we provide an aggregate formulation that allows us to introduce further inequalities. Then, we propose a two–phase exact algorithm for the solution of the UCGRPP. In the first phase, a branch-and-cut algorithm is used to solve the aggregate formulation and to identify a cut pool of aggregate valid inequalities to be used in the second phase, where a branch-and-cut algorithm is implemented to optimally solve the UCGRPP. Computational results on a large set of problem instances show that the use of the aggregate formulation is effective, making the two-phase exact algorithm able to optimally solve a large number of instances."
`]
"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-09T11:22:13.000Z"
"docTitle" => "The Undirected Capacitated General Routing Problem with Profits"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/archetti-claudia">ARCHETTI Claudia</a>, BERTAZZI Luca, LAGANÀ Demetrio, VOCATURO Francesca"
"docDescription" => "<span class="document-property-authors">ARCHETTI Claudia, BERTAZZI Luca, LAGANÀ Demetrio, VOCATURO Francesca</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">2017</span>"
"keywordList" => "<a href="#">General routing</a>, <a href="#">Profits</a>, <a href="#">Aggregate formulation</a>, <a href="#">Branch-and-cut</a>"
"docPreview" => "<b>The Undirected Capacitated General Routing Problem with Profits</b><br><span>2017-03 | Articles </span>"
"docType" => "research"
]
+lang: "fr"
+"_type": "_doc"
+"_score": 9.017484
+"parent": null
}