Skip to main content

OPTIMIZACION DISCRETA PARA PROBLEMAS INTEGRADOS EN LOGISTICA Y TRANSPORTE

MTM2015-63779-R

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos I+D+i Retos de Investigación
Call year 2015
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Management unit Dirección General de Investigación Científica y Técnica
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 8
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Location routing problems on trees

  • Aráoz Durand, Julián Arturo
  • Fernández Aréizaga, Elena|||0000-0003-4714-0257
  • Rueda, Salvador
This paper addresses combined location/routing problems defined on trees, where not all vertices have to be necessarily visited. A mathematical programming formulation is presented, which has the integrality property. The formulation models a directed forest where each connected component hosts at least one open facility, which becomes the root of the component. The problems considered can also be optimally solved with ad-hoc solution algorithms. Greedy type optimal algorithms are presented for the cases when all vertices have to be visited and facilities have no set-up costs. Facilities set-up costs can be handled with low-order interchanges, whose optimality check is a re-statement of the complementary slackness conditions of the proposed formulation. The general problems where not all vertices have to be necessarily visited can also be optimally solved with low-order optimal algorithms based on recursions., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A branch-and-cut algorithm for the multidepot rural postman problem

  • Fernández Aréizaga, Elena|||0000-0003-4714-0257
  • Laporte, Gilbert
  • Rodríguez Pereira, Jessica|||0000-0002-9726-7531
This paper considers the Multidepot Rural Postman Problem, an extension of the classical Rural Postman Problem in which there are several depots instead of only one. The aim is to construct a minimum cost set of routes traversing each required edge of the graph, where each route starts and ends at the same depot. The paper makes the following scientific contributions: (i) It presents optimality conditions and a worst case analysis for the problem; (ii) It proposes a compact integer linear programming formulation containing only binary variables, as well as a polyhedral analysis; (iii) It develops a branch-and-cut algorithm that includes several new exact and heuristic separation procedures. Instances involving up to four depots, 744 vertices, and 1,315 edges are solved to optimality. These instances contain up to 140 required components and 1,000 required edges., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Exact solution of hub network design problems with profits

  • Alibeyg, Armaghan
  • Contreras Aguilar, Iván
  • Fernández Aréizaga, Elena|||0000-0003-4714-0257
This paper studies hub network design problems with profits. They consider a profit-oriented objective that measure the tradeoff between the revenue due to served commodities and the overall network design and transportation costs. An exact algorithmic framework is proposed for two variants of this class of problems, where a sophisticated Lagrangian function that exploits the structure of the problems is used to efficiently obtain bounds at the nodes of an enumeration tree. In addition, reduction tests and partial enumerations are used to considerably reduce the size of the problems and thus help decrease the computational effort. Numerical results on a set of benchmark instances with up to 100 nodes confirm the efficiency of the proposed algorithmic framework. The proposed methodology can be used as a tool to solve more complex variants of this class of problems as well as other discrete location and network design problems involving servicing decisions., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Solving the optimum communication spanning tree problem

  • Zetina, Carlos Armando
  • Contreras Aguilar, Iván
  • Fernández Aréizaga, Elena|||0000-0003-4714-0257
  • Luna Mota, Carlos
This paper presents an algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. The algorithm integrates within a branch-and-cut framework a stronger reformulation of the problem, combinatorial lower bounds, in-tree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to three orders of magnitude compared to state-of-the-art exact algorithms. In addition, our algorithm is able to prove optimality for five unsolved instances in the literature and four from a new set of larger instances., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A branch-and-cut algorithm for the multidepot rural postman problem

  • Fernández Aréizaga, Elena
  • Laporte, Gilbert
  • Rodríguez Pereira, Jessica
This paper considers the Multidepot Rural Postman Problem, an extension of the classical Rural Postman Problem in which there are several depots instead of only one. The aim is to construct a minimum cost set of routes traversing each required edge of the graph, where each route starts and ends at the same depot. The paper makes the following scientific contributions: (i) It presents optimality conditions and a worst case analysis for the problem; (ii) It proposes a compact integer linear programming formulation containing only binary variables, as well as a polyhedral analysis; (iii) It develops a branch-and-cut algorithm that includes several new exact and heuristic separation procedures. Instances involving up to four depots, 744 vertices, and 1,315 edges are solved to optimality. These instances contain up to 140 required components and 1,000 required edges., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Location routing problems on trees

  • Aráoz Durand, Julián Arturo
  • Fernández Aréizaga, Elena
  • Rueda, Salvador
This paper addresses combined location/routing problems defined on trees, where not all vertices have to be necessarily visited. A mathematical programming formulation is presented, which has the integrality property. The formulation models a directed forest where each connected component hosts at least one open facility, which becomes the root of the component. The problems considered can also be optimally solved with ad-hoc solution algorithms. Greedy type optimal algorithms are presented for the cases when all vertices have to be visited and facilities have no set-up costs. Facilities set-up costs can be handled with low-order interchanges, whose optimality check is a re-statement of the complementary slackness conditions of the proposed formulation. The general problems where not all vertices have to be necessarily visited can also be optimally solved with low-order optimal algorithms based on recursions., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Solving the optimum communication spanning tree problem

  • Zetina, Carlos Armando
  • Contreras Aguilar, Iván
  • Fernández Aréizaga, Elena
  • Luna Mota, Carlos
This paper presents an algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. The algorithm integrates within a branch-and-cut framework a stronger reformulation of the problem, combinatorial lower bounds, in-tree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to three orders of magnitude compared to state-of-the-art exact algorithms. In addition, our algorithm is able to prove optimality for five unsolved instances in the literature and four from a new set of larger instances., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Exact solution of hub network design problems with profits

  • Alibeyg, Armaghan
  • Contreras Aguilar, Iván
  • Fernández Aréizaga, Elena
This paper studies hub network design problems with profits. They consider a profit-oriented objective that measure the tradeoff between the revenue due to served commodities and the overall network design and transportation costs. An exact algorithmic framework is proposed for two variants of this class of problems, where a sophisticated Lagrangian function that exploits the structure of the problems is used to efficiently obtain bounds at the nodes of an enumeration tree. In addition, reduction tests and partial enumerations are used to considerably reduce the size of the problems and thus help decrease the computational effort. Numerical results on a set of benchmark instances with up to 100 nodes confirm the efficiency of the proposed algorithmic framework. The proposed methodology can be used as a tool to solve more complex variants of this class of problems as well as other discrete location and network design problems involving servicing decisions., Peer Reviewed, Postprint (author's final draft)