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
Scheduled
GT1-3 Location
September 3, 2019 6:30 PM
I3L8. Georgina Blanes building