J. Araoz, E. Fernández, S. Rueda
Location and routing problems (LRPs) are among core problems in combinatorial optimization.
The state of the art on LRPs deals with generic graphs where both location and routing decisions typically produce NP-hard optimization problems. To the best of our knowledge, the topology of the graph where problem is defined has not been exploited so far.
In contrast, the topology of the network has been exploited quite extensively to derive polynomial time solution algorithms for a number of location/allocation problems, which are NP-hard in the general case. This is particularly true for the case of tree networks, and is the focus of this work, in which we give polynomial time optimal algorithms for several LRPs formulated on a tree. These results can be extended to cacti (connected graphs in which any two simple cycles have at most one vertex in common), and can be used as the basis for heuristics for other LRPs on more general graphs.
We work on an undirected connected graph that we assume is a tree, with a cost function on the edge set and a given set of users with service demand, which can be located at both the vertices and the edges of the graph.
We assume there are no capacity constraints. We study several types of LPRs, which mainly differ from each other on the characteristics of the set of demand customers. Another possible difference among problems is whether or not open facilities incur setup costs.
In all cases, the LRP that we study consists of:
(i) selecting the best location for a set of facilities at vertices of the graph
(ii) allocating each demand customer to one selected facility
(iii) designing a set of closed routes through the given set of customers, each of them using as depot one of the selected facilities
All of these of minimum total cost.
Once the location of the facilities and the allocation of customers to the selected facilities are determined, the optimal routing problem can be decomposed into a number of smaller subproblems, one associated with each facility, which becomes the depot for its allocated customers.
Indeed, the routes must visit vertices or traverse edges, depending on the type of demand. Since we work on a tree and there are no capacity constraints, in all cases all optimal routes are bipaths where the edges that are used are traversed exactly twice.
In the absence of facilities setup costs, such a problem can be solved with a simple greedy algorithm, both for demand at the vertices or the edges of the tree. Solutions satisfying optimality conditions can also be obtained in polynomial time for the case with set-up costs.
We also study LRPs where not all vertices have demand or when the graph induced by demand edges does not span the complete vertex set. Now the interpretation of a solution as a partition of the vertex set does not hold.
Furthermore, such LRPs can no longer be solved with a greedy heuristic. The fact that it is not known a priori whether or not a non- demand vertex will be covered in an optimal solution, makes these LRPs substantially more difficult than when all vertices must be necessarily visited. As we will see, a dynamic programming algorithm can optimally solve LRPs of this type in polynomial time.
Keywords: locations, trees, good algorthms
Scheduled
T2 Location 1
October 1, 2015 11:30 AM
Salón de actos
