1 Search Results for "Viana, Henrique"


Document
The Team Orienteering Problem: Formulations and Branch-Cut and Price

Authors: Marcus Poggi, Henrique Viana, and Eduardo Uchoa

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)


Abstract
The Team Orienteering Problem is a routing problem on a graph with durations associated to the arcs and profits assigned to visiting the vertices. A fixed number of identical vehicles, with a limited total duration for their routes, is given. The total profit gathered by all routes is to be maximized. We devise an extended formulation where edges are indexed by the time they are placed in the route. A new class of inequalities, min cut, and the triangle clique cuts of Pessoa et. al., 2007 are added. The resulting formulation is solved by column generation. Branching is done following the work of Boussier et al. 2007, to which the branch-cut-and-price algorithm here proposed is compared. A few new upper bounds were obtained. Overall the presented approach has shown to be very competitive.

Cite as

Marcus Poggi, Henrique Viana, and Eduardo Uchoa. The Team Orienteering Problem: Formulations and Branch-Cut and Price. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 142-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{poggi_et_al:OASIcs.ATMOS.2010.142,
  author =	{Poggi, Marcus and Viana, Henrique and Uchoa, Eduardo},
  title =	{{The Team Orienteering Problem: Formulations and Branch-Cut and Price}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{142--155},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.142},
  URN =		{urn:nbn:de:0030-drops-27561},
  doi =		{10.4230/OASIcs.ATMOS.2010.142},
  annote =	{Keywords: Branch-Cut and Price, Team Orienteering Problem, Column Generation}
}
  • Refine by Author
  • 1 Poggi, Marcus
  • 1 Uchoa, Eduardo
  • 1 Viana, Henrique

  • Refine by Classification

  • Refine by Keyword
  • 1 Branch-Cut and Price
  • 1 Column Generation
  • 1 Team Orienteering Problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2010

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail