Prize-collecting Location Routing on Trees

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

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

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

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