A column generation approach to capacitated \(p\)-median problems.

*(English)*Zbl 1048.90132Summary: The Capacitated \(p\)-median problem (CPMP) seeks to solve the optimal location of p facilities, considering distances and capacities for the service to be given by each median. In this paper we present a column generation approach to CPMP. The identified restricted master problem optimizes the covering of 1-median clusters satisfying the capacity constraints, and new columns are generated considering knapsack subproblems. The Lagrangean/surrogate relaxation has been used recently to accelerate subgradient like methods. In this work the Lagrangean/surrogate relaxation is directly identified from the master problem dual and provides new bounds and new productive columns through a modified knapsack subproblem. The overall column generation process is accelerated, even when multiple pricing is observed. Computational tests are presented using instances taken from real data from São José dos Campos City.

##### MSC:

90B85 | Continuous location |

##### Keywords:

Location problems; Capacitated \(p\)-median problems; Column generation; Lagrangean/surrogate relaxation
PDF
BibTeX
Cite

\textit{L. A. N. Lorena} and \textit{E. L. F. Senne}, Comput. Oper. Res. 31, No. 6, 863--876 (2004; Zbl 1048.90132)

Full Text:
DOI

##### References:

[1] | Bramel, J.; Simchi-Levi, D., A location based heuristic for general routing problems, Operations research, 43, 649-660, (1995) · Zbl 0857.90030 |

[2] | Klein, K.; Aronson, J.E., Optimal clusteringa model and method, Naval research logistics, 38, 447-461, (1991) · Zbl 0721.92031 |

[3] | Mulvey, J.M.; Beck, M.P., Solving capacitated clustering problems, European journal of operational research, 18, 339-348, (1984) · Zbl 0547.62039 |

[4] | Osman, I.H.; Christofides, N., Capacitated clustering problems by hybrid simulated annealing and tabu search, International transactions in operational research, 1, 317-336, (1994) · Zbl 0857.90107 |

[5] | Koskosidis, Y.A.; Powell, W.R., Clustering algorithms for consolidation of costumes orders into vehicle shipments, Transportation research B, 26, 365-379, (1992) |

[6] | França, P.M.; Sosa, N.M.; Pureza, V., An adaptive tabu search algorithm for the capacitated p-Median problem, International transactions in operations research, 6, 665-678, (1999) |

[7] | Maniezzo, V.; Mingozzi, A.; Baldaci, R., A bionomic approach to the capacitated p-Median problem, Journal of heuristics, 4, 263-280, (1998) · Zbl 0913.90201 |

[8] | Lorena, L.A.N.; Furtado, J.C., Constructive genetic algorithm for clustering problems, Evolutionary computation, 9, 1, 309-327, (2001) |

[9] | Beasley, J.E., Or-librarydistributing test problems by electronic mail, Journal operational research society, 41, 1069-1072, (1990) |

[10] | Lorena, L.A.N.; Lopes, F.B., A surrogate heuristic for set covering problems, European journal of operational research, 79, 138-150, (1994) · Zbl 0813.90096 |

[11] | Lorena, L.A.N.; Narciso, M.G., Relaxation heuristics for a generalized assignment problem, European journal of operational research, 91, 600-610, (1996) · Zbl 0924.90119 |

[12] | Lorena, L.A.N.; Senne, E.L.F., Improving traditional subgradient scheme for Lagrangean relaxationan application to location problems, International journal of mathematical algorithms, 1, 133-151, (1999) · Zbl 0973.90043 |

[13] | Lorena LAN, Senne ELF. Local search heuristics for capacitated p-median problems. Networks and Spatial Economics 2002, to appear. |

[14] | Narciso, M.G.; Lorena, L.A.N., Lagrangean/surrogate relaxation for generalized assignment problems, European journal of operational research, 114, 165-177, (1999) · Zbl 0946.90035 |

[15] | Senne, E.L.F.; Lorena, L.A.N., Lagrangean/surrogate heuristics for p-Median problems, (), 115-130 |

[16] | Cooper, L., Location-allocation problems, Operations research, 11, 331-343, (1963) · Zbl 0113.14201 |

[17] | Dantzig, G.B.; Wolfe, P., Decomposition principle for linear programs, Operations research, 8, 101-111, (1960) · Zbl 0093.32806 |

[18] | Barnhart, C.; Johnson, E.L.; Nemhauser, G.L.; Savelsbergh, M.W.P.; Vance, P.H., Branch-and-pricecolumn generation for solving huge integer programs, Operations research, 46, 316-329, (1998) · Zbl 0979.90092 |

[19] | Carvalho JMV. Exact solution of bin-packing problems using column generation and branch-and-bound. Universidade do Minho, Departamento Produção e Sistemas. Working Paper, 1996. |

[20] | Day, P.R.; Ryan, D.M., Flight attendant rostering for short-haul airline operations, Operations research, 45, 649-661, (1997) · Zbl 0902.90115 |

[21] | Desrochers, M.; Desrosiers, J.; Solomon, M., A new optimization algorithm for the vehicle routing problem with time windows, Operations research, 40, 342-354, (1992) · Zbl 0749.90025 |

[22] | Desrochers, M.; Soumis, F., A column generation approach to the urban transit crew scheduling problem, Transportation science, 23, 1-13, (1989) · Zbl 0668.90043 |

[23] | Gilmore, P.C.; Gomory, R.E., A linear programming approach to the cutting stock problem, Operations research, 9, 849-859, (1961) · Zbl 0096.35501 |

[24] | Gilmore, P.C.; Gomory, R.E., A linear programming approach to the cutting stock problem—part II, Operations research, 11, 863-888, (1963) · Zbl 0124.36307 |

[25] | Vance P. Crew scheduling, cutting stock and column generation: solving huge integer programs. PhD thesis, Georgia Institute of Technology, 1993. |

[26] | Vance, P.H.; Barnhart, C.; Johnson, E.L.; Nemhauser, G.L., Solving binary cutting stock problems by column generation and branch-and-bound, Computational optimization and applications, 3, 111-130, (1994) · Zbl 0801.90080 |

[27] | Minoux, M., A class of combinatorial problems with polynomially solvable large scale set covering/set partitioning relaxations, Rairo, 21, 2, 105-136, (1987) · Zbl 0644.90061 |

[28] | Kelley, J.E., The cutting plane method for solving convex programs, Journal of the SIAM, 8, 703-712, (1960) · Zbl 0098.12104 |

[29] | du Merle, O.; Goffin, J.L.; Vial, J.P., On improvements to the analytic centre cutting plane method, Computational optimization and applications, 11, 37-52, (1998) · Zbl 0912.90230 |

[30] | du Merle, O.; Villeneuve, D.; Desrosiers, J.; Hansen, P., Stabilized column generation, Discrete mathematics, 194, 229-237, (1999) · Zbl 0949.90063 |

[31] | Marsten, R.M.; Hogan, W.; Blankenship, J., The boxstep method for large-scale optimization, Operations research, 23, 389-405, (1975) · Zbl 0372.90078 |

[32] | Neame PJ. Nonsmooth dual methods in integer programming. PhD thesis, Department of Mathematics and Statistics, The University of Melbourne, 1999. |

[33] | Martello, S.; Toth, P., Knapsack problems: algorithms and computer implementations, (1990), Wiley New York · Zbl 0708.68002 |

[34] | Reinelt, G., The traveling salesman problem: computational solutions for TSP applications, Lecture notes in computer science, vol. 840, (1994), Springer Berlin |

[35] | ESRI Environmental Systems Research Institute, Inc. Avenue Customization and Application Development for ArcView, 1996. |

[36] | ILOG CPLEX 6.5. ILOG Inc. Cplex Division, 1999. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.