A quadratic integer program for the location of interacting hub facilities. (English) Zbl 0627.90030
This paper reports a new formulation of a general hub location model as a quadratic integer program. Non-convexity of the objective function makes the problem difficult. A variety of alternative solution strategies are discussed. Computational results from two simple heuristics are presented for the task of siting 2, 3 or 4 hubs to serve interactions between sets of 10, 15, 20 and 25 U.S. cities. The effects of different computational shortcuts are examined.
MSC:
| 90B05 | Inventory, storage, reservoirs |
| 90C10 | Integer programming |
| 65K05 | Numerical mathematical programming methods |
| 90C20 | Quadratic programming |
Software:
Algorithm 431References:
| [1] | Bellman, R., (Introduction to Matrix Analysis (1970), McGraw-Hill: McGraw-Hill Amsterdam) · Zbl 0216.06101 |
| [2] | Brotchie, J. F., A general planning model, Management Science, 16, 265 (1969) |
| [3] | Cottle, R. W.; Mylander, W. C., Ritter’s cutting plane method for nonconvex quadratic programming, (Abadie, J., Integer and Nonlinear Programming (1970), North-Holland: North-Holland New York), 257-283 · Zbl 0332.90033 |
| [4] | Francis, R. L.; White, J. A., (Facility Layout and Location (1974), Prentice-Hall: Prentice-Hall Amsterdam) |
| [5] | Gallo, G.; Hammer, P. L.; Simeone, B., Quadratic knapsack problem, (Padberg, M. W., Mathematical Programming Study 12, Combinatorial Optimization (1980)) · Zbl 0462.90068 |
| [6] | Hansen, P., Quadratic zero-one programming by im- plicit enumeration, (Lootsma, F. A., Numerical Methods for Non-linear Optimization (1972), Academic Press: Academic Press Englewood Cliffs, NJ), 265-278 · Zbl 0267.90071 |
| [7] | Hansen, P., Methods of nonlinear 0-1 programming, (Hammer, P. L.; Johnson, E. L.; Korte, B. H., Discrete Optimization II (1979), North-Holland: North-Holland New York), 53-70 · Zbl 0426.90063 |
| [8] | Hansen, P.; Peeters, D.; Thisse, J.-F., Public facility location models: A selective survey, (Thisse, J.-F.; Zoller, H. G., Location Analysis of Public Facilities (1983), North-Holland: North-Holland Amsterdam), 223-262 |
| [9] | Jacobson, D. H., (Extensions of Linear-Quadratic Control, Optimization and Matrix Theory (1977), Academic Press: Academic Press Amsterdam) · Zbl 0446.49001 |
| [10] | Lundqvist, L., Integrated location-transportation analysis: A decomposition approach, Regional and Urban Economics, 3, 233-262 (1973) |
| [11] | McBride, R. D.; Yormark, J. S., An implicit enumeration algorithm for quadratic integer programming, Management Science, 26, 282-296 (1980) · Zbl 0443.90067 |
| [12] | O’Kelly, M. E., The location of interacting hub facilities, Transportation Science, 20, 92-106 (1986) |
| [13] | Ravindran, A., A computer routine for quadratic and linear programming problems, Algorithm 431, Communications of the ACM, 15, 818-820 (1972) |
| [14] | Ravindran, A.; Lee, H. K., Computer experiments on quadratic programming algorithms, European Journal of Operational Research, 8, 166-174 (1981) · Zbl 0464.90064 |
| [15] | ReVelle, C.; Swain, R., Central facilities location, Geographical Analysis, 2, 30-42 (1970) |
| [16] | Ross, G. T.; Soland, R. M., Modeling facility location problems as generalized assignment problems, Management Science, 24, 3, 345-357 (1977) · Zbl 0378.90066 |
| [17] | Snickars, F., Convexity and duality properties of a quadratic intraregional location model, Regional Science and Urban Economics, 8, 5-20 (1978) |
| [18] | West, D. H., Approximate solution of the quadratic assignment problem, (Algorithm 608. Algorithm 608, Transactions on Mathematical Software, 9 (1983)), 461-466 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
