Models and Algorithms for Location-Routing and Related Problems

Abstract

The most common decisions to be taken in the design of logistic systems are related to the location of facilities and the management of vehicle fleets.<br><br/>In this thesis, we study three of the optimization problems arising around this kind of decisions; namely the LRP, the SGAP and the SLRP. The first problem analyzed in this work is a capacitated LRP with one single uncapacitated vehicle at each open plant. To model this problem we resort to an auxiliary network that allows us to represent feasible solutions as families of paths satisfying a series of side constraints.<br/>The solutions of a reinforced LP relaxation of this model are used as the basis of a rounding heuristic designed to build feasible solutions of the problem. Those solutions are then improved with a TS heuristic.<br><br/>Two lower bounds, distinct from that obtained with the LP relaxation of the model, are proposed for this problem. The first one is obtained by bound ing separately the two different parts of the cost of any feasible solution, namely the fixed costs for opening plants and the route costs. The second lower bound is the result of applying CG to the Lagrangian dual obtained by dualizing the assignment constraints. The pricing problem obtained from our formulation is an ESPPRC. The complexity of this problem, and the fact that optimality of the obtained solutions is not always necessary, have motivated us to develope a simple heuristic for it.<br><br/>The computational experiences show a very good behavior of the TS procedure both, for the computational effort required and the quality of the solutions. The first lower bound proposed gives satisfactory results in reasonable amounts of time. In the case of the CG approach, results are very encouraging. In some of the tested instances the program terminated because of the CPU time limit specification, before succeeding to find a valid lower bound.<br><br/>In those instances, the algorithm was always stalled in the exact resolution of an ESPPRC. The difficulties encountered to solve this problem represent a limitation of this approach and suggest the future study of alternative solution methods. In spite of this limitation, in a high proportion of the instances the algorithm succeeded, and the final gap between the upper and the lower bound was always 0. The success in these instances is partially due to the use of our heuristic to generate new columns whenever this is possible.<br><br/>The second problem studied in this thesis is a SGAP. In this assignment problem the jobs are interpreted as customers that can request a service with a given probability, and each agent can serve a limited number of customers. This uncertainty about the presence of each customer is represented by modelling the demands of the customers as Bernoulli distributed independent random variables. The problem consists of finding an a priori assignment of customers to agents. Once the actual requests for service are known, an adaptive action is taken to tackle violations of the capacity constraints. On the one hand, part of the customers assigned to overloaded agents can be reassigned. On the other hand, some of the service requests can be disregarded. Different penalties for reassignment and for unattended service requests are pre-specified. The problem is formulated as a recourse model, where the recourse function gives the expected penalties for reassignments and unattended service requests.<br><br/>Since this recourse function is defined as the expected value of an integer programming recourse model, it does not have the regularity properties characteristic of those defined by linear recourse models. To overcome the difficulties caused by this, we construct a convex approximation of the recourse function that is tight in all feasible points. Moreover, as illustrated in the computational experiences, the use of this approximation reduces the computational effort required to evaluate the recourse function is some orders of magnitude. The convex approximation of the recourse function allows us to adapt the well-known L-shaped method to our problem. Integrality of the first stage variables is tackled in three different ways, giving raise to three versions of the algorithm. The difference among them resides in the hierarchy between the branching and the addition of violated cuts. On the one hand, we present a version where cuts are only added when integer solutions are found. On the other hand, a version is proposed where branching is only performed when no more violated cuts can be identified. The remaining version is designed as a tradeoff of these two; at each node of the search tree, new optimality cuts are added, if needed, and branching is performed if the solution at hand is fractional. Computational experiences point out this last version as the best of the three, since the efforts devoted to obtain a rich approximation of the recourse function and to achieve integrality are more balanced.<br><br/>We have also derived both, lower and upper bounds for this specific SGAP. Upper bounds are obtained from three simple heuristics. All them are based on solving deterministic approximations of the SGAP and provide good quality solutions in small amounts of CPU time. A lower bound is derived from a family of linear stochastic subproblems. Althoug in some of the tested instances the gap between the bounds exceeded the 30%, in the general case we obtained small gaps.<br><br/>One of the heuristics was used in the exact algorithm to provide it with a good upper bound. The lower bound is also used in the three versions of the algorithm, as the basis of some of the optimality cuts and also to identify optimal solutions. The quality of these bounds is one of the factors that explain the success of the exact algorithm.<br><br/>The last problem studied in this thesis is a SLRP. The stochasticity considered here is of the same type as that considered for the SGAP. Again, customers may request a service with a given probability and this is modeled by introducing Bernoulli random variables to represent the demands. A two stage model is proposed for this problem. In a first stage, a set of plants to open has to be chosen together with a family of disjoint routes (one rooted at each open plant) that visit all the customers. In the second stage, once all the demands become available, the actual routes have to be designed. For plants whose number of service requests does not exceed the capacity, the actual route is derived from that designed a priori by skipping customers with no demand. When the requests for service allocated to a plant exceed its capacity, a subset of them is randomly chosen to be served, and they are visited in the order defined by the a priori route.<br><br/>Penalties are paid for the unattended service requests. The expected total cost of the actual routes and the expected penalties for unserviced customers are contained in the recourse function.<br/>We present a two phase heuristic to solve this problem. In the first phase, a series of subproblems are sequentially solved to build an initial solution. In the second phase, this solution is successively improved using LS. This improving phase requires a high number of evaluations of the recourse function. Although we have developed an analytical expression for this recourse function, the computational effort required for its evaluation is considerable due to its combinatorial nature. For this reason, we approximate it with a simpler auxiliary function that has allowed us to obtain solutions in small computational times.<br><br/>We also propose a lower bound obtained from bounding different parts of the objective function independently. Unfortunately, we only could find reasonable bounds for the sum of fixed costs for opening the plants plus the expected penalty paid for unserviced customers. Further research is intended to improve the bounding of the expected total cost of the routes.<br><br/>The evaluation of the quality of the solutions obtained with our heuristic is not easy due to the lack of a tight global lower bound. However, the partial bound on the costs relative to the plants allows to conclude that the heuristic makes in general a good choice of the set of plants. As for the allocation of customers to plants and the design of the routes we can only evaluate the evolution along the search. In the computational experiences reported it can be seen that this evolution is satisfactory.