Skip to main content

RED TEMATICA: LOCALIZACION Y PROBLEMAS AFINES

RED2018-102363-T

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Redes Investigación /Redes Excelencia
Call year 2018
State Plan 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A modified single-objective genetic algorithm for solving the rural postman problem with load-dependent costs

  • De Santis, David
  • Landete, Mercedes
  • Cabezas, Xavier
  • Peiró, Juanjo
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] This study addresses the rural postman problem with load-dependent costs, a variant of the arc routing problem where the traversal cost of an edge depends on its length and the vehicle's load. The objective is to find a minimum-cost tour that services all required edges, a problem of particular importance when the demand weight is significant compared to the vehicle's curb weight. We present an integer linear programming model for the problem and propose a heuristic algorithm based on bio-inspired methodologies to efficiently obtain near-optimal solutions within short computing times. The effectiveness of the approach is demonstrated through computational experiments on benchmark instances, and the results highlight the practicality of the proposed methods., This work was supported by Gobierno de Espana through Ministerio Ciencia, Innovacion y Ministerio de Universidades and Fondo Europeo de Desarrollo Regional (FEDER) , Spain under projects PID2021-122344NB-I00, and RED2018-102363-T, by Generalitat Valenciana, Spain under projects PROMETEO/2021/063 and CIGE/2022/57. The authors would like to thank the anonymous reviewers for their comments and suggestions, which have contributed to improving the content and readability of the article.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

On the complexity of the upgrading version of the maximal covering location problem

  • Baldomero Naranjo, Marta
  • Kalcsics, Jörg
  • Rodríguez Chía, Antonio Manuel
In this article, we study the complexity of the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem is NP-hard on general networks. However, in some particular cases, we prove that this problem is solvable in polynomial time. The cases of star and path networks combined with different assumptions for the model parameters are analysed. In particular, we obtain that the problem on star networks is solvable in (Formula presented.) time for uniform weights and NP-hard for non-uniform weights. On paths, the single facility problem is solvable in (Formula presented.) time, while the (Formula presented.) -facility problem is NP-hard even with uniform costs and upper bounds (maximal upgrading per edge), as well as, integer parameter values. Furthermore, a pseudo-polynomial algorithm is developed for the single facility problem on trees with integer parameters., 15 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

The profit-oriented hub line location problem with elastic demand

  • Cobeña, Brenda
  • Contreras, Ivan
  • Martínez Merino, Luisa Isabel
  • Rodríguez Chía, Antonio Manuel
This paper deals with an extension of the hub line location problem considering demand elasticity with respect to travel times. The proposed model aims to capture the impact the hub network topology has on demand. The objective is to maximize the total revenue generated by each unit of demand using the hub line. We propose mixed-integer nonlinear formulations to model this problem. We study some properties of the nonlinear objective function associated with these formulations. Due to the inherent complexity involved in solving these nonlinear formulations with state-of-the-art solvers, we also present alternative mixed-integer linear programming formulations. Computational results compare the proposed formulations and the benefits of the presented model using benchmark instances commonly used in hub location. Moreover, a sensitivity analysis study is carried out with real data from the city of Montreal, Canada, to demonstrate the added value of incorporating demand elasticity when using the proposed model for public transportation planning.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

A new formulation and branch-and-cut method for single-allocation hub location problems

  • Espejo Miranda, Inmaculada
  • Marín, Alfredo
  • Muñoz Ocaña, Juan Manuel
  • Rodríguez Chía, Antonio Manuel
A new compact formulation for uncapacitated single-allocation hub location problems with fewer variables than the previous Integer Linear Programming formulations in the literature is introduced. Our formulation works even with costs not based on distances and not satisfying triangle inequality. Moreover, costs can be given in aggregated or disaggregated way. Different families of valid inequalities that strengthen the formulation are developed and a branch-and-cut algorithm based on a relaxed version of the formulation is designed, whose restrictions are inserted in a cut generation procedure together with two sets of valid inequalities. The performance of the proposed methodology is tested on well-known hub location data sets and compared to the most recent and efficient exact algorithms for single-allocation hub location problems. Extensive computational results prove the efficiency of our methodology, that solves large-scale instances in very competitive times.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Facility location problems on graphs with non-convex neighborhoods

  • Espejo Miranda, Inmaculada
  • Páez Jiménez, Raúl
  • Puerto Albornoz, Justo
  • Rodríguez Chía, Antonio Manuel
In this paper, we deal with some variants of classical facility location problems on graphs in which both the customers and the facilities belong to a non-necessarily convex neighborhood. Therefore, a point in each neighborhood representing the customer/facility has to be determined, and the customers have to be assigned to the facilities depending on a criterion. In particular, the p-median, the p-center, and the p-maximal covering versions of this problem on graphs are analyzed. An important difference with respect to their classical versions is that the lengths of the arcs depend on the location of the points chosen in the neighborhoods. Therefore, the lengths are not part of the input but part of the decision process. Assuming that the neighborhoods are Mixed-Integer Second Order Cone representable, different mixed-integer non-linear programming formulations are proposed for each one of the considered problems. Moreover, solution procedures providing bounds and a preprocessing phase are developed to reduce the number of variables and constraints of the proposed formulations. The results of an extensive computational experience are reported.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

An exact approach for the reliable fixed-charge location problem with capacity constraints

  • Albareda Sambola, Maria
  • Landete, Mercedes
  • Monge Ivars, Juan Francisco
  • Sainz Pardo, José Luis
Introducing capacities in the reliable fixed charge location problem is a complex task since successive failures might yield in high facility overloads. Ideally, the goal consists in minimizing the total cost while keeping the expected facility overloads under a given threshold. Several heuristic approaches have been proposed in the literature for dealing with this goal. In this paper, we present the first exact approach for this problem, which is based on a cutting planes algorithm. Computational results illustrate its good performance, Postprint (published version)