首页    期刊浏览 2024年12月05日 星期四
登录注册

文章基本信息

  • 标题:The Team Orienteering Problem: Formulations and Branch-Cut and Price
  • 本地全文:下载
  • 作者:Poggi, Marcus ; Viana, Henrique ; Uchoa, Eduardo
  • 期刊名称:OASIcs : OpenAccess Series in Informatics
  • 电子版ISSN:2190-6807
  • 出版年度:2010
  • 卷号:14
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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
  • 关键词:Branch-Cut and Price; Team Orienteering Problem; Column Generation
国家哲学社会科学文献中心版权所有