The clustered prize-collecting arc routing problem

Resumen

In this thesis we study the Clustered Price-collecting Arc Routing Problem (CPARP) defined on an undirected graph, In Price-collecting Arc Routing Problems (PARPs) there is no specific link subset to be serviced, but there are profits associated with the links that are serviced (in addition to the costs of the links). That is, the set of required links is not given and it must be decided, together with the route that will serve the selected links, so as to maximize the net profit. In PARPs we assume that the profit of each serviced link is collected only once, independently of the number of times the edge is traversed. The CPARP is an ARP where, in addition, we consider components (clusters) defined by the edges with demand. For each cluster we require that either all its links are serviced or no link of the cluster is serviced. The motivation for studying the CARP comes both from its theoretical interest and from its potential applications. In the context of private companies looking to maximize operational profits, a demand edge would not be serviced unless it would result on a profit for the company, and each demand edge would be serviced at most once. Potential applications of CPARP include, among others, determining the service for garbage collection or street cleaning in districts or neighborhoods in a given area. While it is not acceptable that only a part of a neighborhood be serviced, the whole neighborhood might not be profitable for the servicing company. When we pose the additional requirement that either all the links of a cluster are serviced or no link of the cluster is serviced, we prove some dominance conditions that otherwise do not hold. These properties allow some transformation of the original graph resulting in a stronger formulation of the problem. The formulation has an exponential number of inequalities of two types: Inequalities to guarantee the connectivity of the traversal with the depot, and inequalities to guarantee the parity of the nodes. Due to the exponential number of constraints it is important to address the separation problems for both types of inequalities. In both cases we can solve exactly the separation problem. This enables us to propose an LP based iterative scheme that at each iteration reinforces the current formulation with violated inequalities. We also study heuristics for generating feasible solutions to the CPARP whose values can be compared with the upper bounds associated with the optimal LP solution. For the sake of completeness, we propose an exact branch-and-cut algorithm to optimally solve the CPARP. At the root node we obtain an upper bound by solving the LP relaxation of the model and a lower bound with a heuristic which exploits the information of the optimal LP solution. In this thesis we have also considered the Windy version of the CPARP (WCPARP). As with other arc routing problems the WCPARP generalizes all possible versions of the problem. We assume that profit function on the demand edges is symmetric, but the cost function associated with the traversal of edges is asymmetric. Several properties that hold when the cost function on the edges is symmetric, no longer hold for the WCPARP. The numerical results from a series of computational experiments with the proposed algorithms are very satisfactory. More than 75% of the instances were optimally solved at the root node of the search tree. The remaining instances required, in general, very few nodes of the search tree. All but two instances of the 118 considered ones were optimally solved in less than two minutes of cpu time. The thesis is structured in 8 chapters and one Appendix. Chapter 2 gives an overview on different types of routing problems. Chapter 3 presents the CPARP; we study its properties and propose a formulation as a Linear Integer Problem. Chapter 4, addresses the separation problem for the two exponential families of inequalities, and presents the iterative LP solver algorithm for solving the LP relaxation of the CPARP and the exact branch and cut algorithm. In Chapter 5 we present the heuristics that we have considered whereas in Chapter 6 we describe the computational experiments with the proposed algorithms and we analyze the obtained numerical results. In Chapter 7 we propose a formulation for the WCPARP and we give some preliminary computational results. The thesis ends in Chapter 8 with some conclusions and comments on future research. The Appendix presents filògrafus, which is an user friendly application developed simultaneously by the author of this thesis, that gives a visual and interactive interface for different types of optimization problems in graphs.