J. Aráoz, E. Fernández Areizaga, M. Muñoz Márquez

We study Prize-collecting Location Routing Problems (PLRPs) on trees. There is a set of users with demand, located at the vertices of a tree, each of them associated with a profit, and each edge has a cost. To serve the demand a set of routes must be set up, each of them starting and ending at a nodes.
The objective is to maximize the total net profit, defined as the total income from serving the selected demand vertices, minus the total cost that includes the overall set-up cost of activated facilities and the routing cost of the edges used in the routes.
A mathematical programming formulation is presented, with the integrality property. The formulation models a directed forest where each connected component hosts one open facility, which is the root of the component. PLRPs can also be optimally solved with ah-hoc solution algorithms.
Optimality conditions are developed, which can be exploited algorithmically in a preprocess phase and reduce substantially the size of the initial graph.

Keywords: Prize-collecting, location and routing, trees


GT1-3 Location
September 3, 2019  6:30 PM
I3L8. Georgina Blanes building

Other papers in the same session

A heuristic algorithm for solving a competitive facility location and design MINLP problem for firm expansion

L. Anton-Sanchez, B. G.-Tóth, J. Fernández, J. L. Redondo, P. M. Ortigosa

Formulaciones para el problema de la mediana ordenada discreto con capacidades

I. Espejo Miranda, J. Puerto Albandoz, A. M. Rodríguez Chía

Wildfires containment and location of limited resources: A continuous approach

M. Marcos Pérez, J. A. Mesa López-Colmenar, F. A. Ortega Riejos

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.