Entwicklung von Algorithmen zur Verbesserung des Zugangs zu Servicezentren durch optimale Platzierung der Zentren und Verbesserung der Zugangswege
Final Report Abstract
We have presented new solution strategies for solving fixed charge and budget facility location-network design problems. On the upper bound side, we contributed a suite of heuristics for budget FLND, the first in the literature for this problem, for finding good feasible solutions. The basic variable neighborhood search heuristic performed the best, achieving solutions within 0.6% of optimal on average for the problems in our test suite. There were interesting differences among the neighborhood based heuristics: some did better with Hamming neighborhoods and some with step neighborhoods. Future work might explore other types of neighborhoods, or non-neighborhood-based heuristics. The IP formulation of Melkote and Daskin for fixed charge FLND has an LP relaxation that obtained the optimal solution for the problems in the test suite. However, their IP formulation for budget FLND leaves room for improvement and we contributed a separation routine for knapsack cuts based on the budget. On average, these cuts closed the gap an additional 48%, and in some cases produced the optimal solution. Noting that the knapsack separation routine requires significant time and memory resources, we introduced a more efficient alternative. However, the trade-off produced cuts that were not as good. Investigating efficient methods of generating stronger knapsack cuts may be worthwhile. We have combined our upper and lower bound techniques in an exact branch-and-cut solver using Melkote and Daskin's IP formulation. The number of nodes in the branch-and-cut tree using this solver was much lower than when solving with CPLEX's default branch-and-cut process. One aspect we did not explore that could improve these results further is a clever, problemspecific branching strategy. A heuristic based on a fractional solution for use at subproblem nodes might also deliver improvements. As an alternative, we introduced a new IP formulation that aggregates the clients and thus is much smaller, with a linear number of variables and constraints instead of a quadratic number. Using this formulation, some of the problem instances could be solved more quickly (using CPLEX to solve to optimality). However, the lower bounds produced by the LP relaxation of our aggregate formulation were not nearly as good. We introduced cuts that greatly improve these lower bounds, but not enough to better those obtained from the disaggregate formulation. Future work strengthening the aggregate formulation may result in a more competitive alternative to the disaggregate formulation. We have also considered practical aspects and examined a case study in which the accessibility of health facilities in Nouna health district was to be improved. We demonstrated the usefulness of FLND results as a decision-making aid in this real-world context. Individually, facility location and network design have received attention in the combinatorial optimization research community over the years. The combined problem of facility location-network design has received much less attention. FLND is an interesting problem with practical applications. Furthermore, the fact that FLND has facility location and network design as subproblems means it could provide insights into the problems in these separate fields as well. The work of this project, coupled with the earlier work of Melkote and Daskin, provides a solid base and a springboard into deeper pursuits in FLND, a field ripe for further research.
Publications
- 05.11.2007: Facility Location-Network Design: Optimizing Access to Facilities, University of Kaiserslautern, Germany
C. Cocking
- 10.07.2007: A Heuristic for the Reverse p-Median Problem, 22nd European Conference on Operational Research, Prague, Czech Republic
C. Cocking
- 13.11.2007: Approaches to Optimizing Access to Facilities, Siemens Workshop on Applied Discrete Optimization, Fulda, Germany.
C. Cocking
- 19.09.2007: Optimizing Access to Health Facilities in Nouna District, Burkina Faso, 13th Czech-French-German Conference on Optimization, Heidelberg, Germany
C. Cocking
- (2008), A heuristic for the reverse p-median problem, Technical report, Uni Heidelberg
Cocking, C. and Reinelt, G.
- 03.09.2008: Neighborhood Based Heuristics for Facility Location-Network Design, Operations Research 2008, Augsburg, Germany
C. Cocking
- 28.05.2008: Improved Lower Bounds for Facility Location-Network Design Problems, International Conference on Applied Mathematical Programming and Modelling, Bratislava, Slovak Republic
C. Cocking
- (2009), Heuristics for budget facility location-network design problems with minisum objective, in: Fleischmann, B., Borgwardt, K.-H., Klein, R. and Tuma, A. (eds.), Operations Research Proceedings 2008, Springer, 2009
Cocking, C. and Reinelt, G.
- (2009), New models for integrated facility location and transportation network design, Technical report, Uni Heidelberg
Contreras, I., Fernández, E. and Reinelt, G.
- (2009), Using discrete optimization for designing dental shade guides, Color Research and Aplication, 2009
Cocking, C , Helling, S., Oswald, M., Rammelsberg, P., Reinelt, G. and Hassel, A.
