A tabu search heuristic procedure for the fixed charge transportation problem. (English) Zbl 0991.90010
Summary: We develop a tabu search approach for the fixed charge transportation problem using recency based and frequency based memories, together with two strategies for each of the intermediate and long term memory processes, making use of a network based implementation of the simplex method as the local search method. Our approach is evaluated computationally on randomly generated problems of different sizes and of different ranges of magnitude of fixed costs relative to variable costs. Comparisons are made with two leading methods previously proposed, one in the category of exact methods and one in the category of heuristic methods. Our tabu search procedure obtains optimal or near-optimal solutions more than a thousand times faster than the exact solution algorithm for simple problems, and thoroughly dominates the exact algorithm on all dimensions for more complex problems. Compared to the heuristic approach, on very small and easy test problems the tabu search procedure required about the same amount of solution time and found solutions at least as good. However, for larger problems and for problems with higher fixed relative to variable costs, the tabu search procedure was 3-4 times faster than the competing heuristic, and found significantly better solutions in all cases.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C10 | Integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90B40 | Search theory |
Keywords:
networks/graphs; flow algorithms; programming; integer algorithms; integer heuristic; fixed charge transportation problem; tabu searchReferences:
| [1] | Aronson, J. E., A survey of dynamic network flows, Annals of Operations Research, 20, 1-66 (1989) · Zbl 0704.90028 |
| [2] | Balinski, M. L., Fixed cost transportation problem, Naval Research Logistics Quarterly, 8, 41-54 (1961) · Zbl 0106.34801 |
| [3] | Barr, R. S.; Glover, F.; Klingman, D., A new optimization method for large scale fixed charge transportation problems, Operations Research, 29, 3, 448-463 (1981) · Zbl 0455.90055 |
| [4] | Bradley, G. G.; Brown, G.; Graves, G., Design and implementation of large scale primal transshipment algorithms, Management Science, 24, 1, 1-35 (1977) · Zbl 0373.90079 |
| [5] | Cabot, A. V.; Erenguc, S. S., Some branch-and-bound procedures for fixed-cost transportation problems, Naval Research Logistics Quarterly, 31, 145-154 (1984) · Zbl 0537.90074 |
| [6] | Cabot, A. V.; Erengue, S. S., Improved penalties for fixed cost linear programs using lagrangean relaxation, Management Science, 32, 7, 856-869 (1986) · Zbl 0599.90084 |
| [7] | Cooper, L., The fixed charge problem-1: A new heuristic, Computers and Mathematics with Applications, 1, 1, 89-96 (1975) · Zbl 0332.90029 |
| [8] | de Werra, D.; Hertz, A., Tabu search techniques: A tutorial and an application to neural networks, OR Spectrum, 11, 131-141 (1989) · Zbl 0672.90089 |
| [9] | Dwyer, P. S., Use of completely reduced matrices in solving transportation problems with fixed charges, Naval Research Logistics Quarterly, 13, 3, 289-313 (1966) |
| [10] | Evans, J. R.; Minieka, E., Optimization Algorithms for Networks and Graphs (1992), Marcel Dekker: Marcel Dekker New York |
| [11] | Fisk, J.; McKeown, P. G., The pure fixed charge transportation problem, Naval Research Logistics Quarterly, 26, 631-641 (1979) · Zbl 0496.90055 |
| [12] | Glover, F., Candidate Strategies and Tabu Search, (CAAI Research Report (1989), University of Colorado: University of Colorado Boulder, CO) · Zbl 0891.68031 |
| [13] | Glover, F., Tabu search: Part 1, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054 |
| [14] | Glover, F., Tabu search: Part II, ORSA Journal on Computing, 2, 1, 4-32 (1990) · Zbl 0771.90084 |
| [15] | Glover, F., Tabu search: A tutorial, Interfaces, 20, 4, 74-94 (19906) |
| [16] | Glover, F., Solving zero-one mixed integer programming problems using tabu search (1993), Graduate School of Business, University of Colorado: Graduate School of Business, University of Colorado Boulder, CO |
| [17] | Glover, F., Tabu search fundamentals and uses (1994), Graduate School of Business, University of Colorado: Graduate School of Business, University of Colorado Boulder, CO |
| [18] | Glover, F., Tabu search: Improved solution alternatives, (Birge, J. R.; Murty, K. G., Mathematical Programming: State of the Art 1994 (1994), The University of Michigan: The University of Michigan Ann Arbor, MI) |
| [19] | Glover, F.; Klingman, D.; Phillips, N. V., Network Models in Optimization and Their Applications in Practice (1992), Wiley: Wiley New York |
| [20] | Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Hingham, MA · Zbl 0930.90083 |
| [21] | Glover, F.; Taillard, E.; de Werra, D., A user’s guide to tabu search, Annals of Operations Research, 41, 1-4, 3-28 (1993) · Zbl 0772.90063 |
| [22] | Gray, P., Exact solution of the fixed-charge transportation problem, Operations Research, 19, 6, 1529-1538 (1971) · Zbl 0224.90036 |
| [23] | Hirsch, W. M.; Dantzig, G. B., The fixed charge problem, Naval Research Logistics Quarterly, 15, 413-424 (1968) · Zbl 0167.48201 |
| [24] | Kennington, J. L., The fixed-charge transportation problem: A computational study with a branch-and-bound code, AIIE Transactions, 8, 241-247 (1976) |
| [25] | Kennington, J. L.; Helgason, R. V., Algorithms for Network Programming (1980), Wiley: Wiley New York · Zbl 0502.90056 |
| [26] | Kennington, J. L.; Unger, E., A new branch-and-bound algorithm for the fixed charge transportation problem, Management Science, 22, 10, 1116-1126 (1976) · Zbl 0329.90039 |
| [27] | Klingman, D.; Napier, A.; Stutz, J., NETGEN - A program for generating large scale (Un)Capacitated assignment, transportation, and minimum cost flow network problems, Management Science, 20, 5, 814-822 (1974) · Zbl 0303.90042 |
| [28] | Kuhn, H. W.; Baumol, W. J., An approximate algorithm for the fixed-charge transportation problem, Naval Research Logistics Quarterly, 9, 1, 1-16 (1961) · Zbl 0109.13903 |
| [29] | Malek-Zavarei, M.; Frisch, I. T., On the fixed cost flow problem, International Journal of Control, 16, 5, 897-902 (1972) · Zbl 0243.90047 |
| [30] | McKeown, P. G., A vertex ranking procedure for solving the linear fixed charge problem, Operations Research, 23, 1183-1191 (1975) · Zbl 0329.90041 |
| [31] | McKeown, P. G., A branch-and-bound algorithm for solving fixed charge problems, Naval Research Logistics, 28, 607-617 (1981) · Zbl 0535.90066 |
| [32] | McKeown, P. G.; Ragsdale, C. T., A computational study of using preprocessing and stronger formulations to solve general fixed charge problems, Computers and Operations Research, 17, 9-16 (1990) · Zbl 0681.90061 |
| [33] | McKeown, P. G.; Sinha, P., An easy solution to a special class of fixed charge problems, Naval Research Logistics Quarterly, 25, 621-624 (1980) · Zbl 0447.90066 |
| [34] | Murty, K. G., Solving the fixed charge problem by ranking the extreme points, Operations Research, 16, 268-279 (1968) · Zbl 0249.90041 |
| [35] | Murty, K. G., Network Programming (1992), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [36] | Palekar, U. S.; Karwan, M. K.; Zionts, S., A branch-andbound method for the fixed charge transportation problem, Management Science, 36, 9, 1092-1105 (1990) · Zbl 0718.90068 |
| [37] | Rousseau, J.-M., A cutting plane method for the fixed cost problem, (Doctoral dissertation (1973), Massachusetts Institute of Technology: Massachusetts Institute of Technology Cambridge, MA) |
| [38] | Schaffer, J. E., Use of penalties in the branch-and-bound procedure for the fixed charge transportation problem, European Journal of Operational Research, 43, 305-312 (1989) · Zbl 0702.90056 |
| [39] | Shetty, U. S., A relaxation decomposition algorithm for the fixed charge network problem, Naval Research Logistic Quarterly, 37, 2, 327-340 (1990) · Zbl 0699.90090 |
| [40] | Steinberg, D. I., The fixed charge problem, Naval Research Logistics Quarterly, 17, 2, 217-236 (1970) · Zbl 0203.52301 |
| [41] | Steinberg, D. I., Designing a heuristic for the fixed-charge transportation problem (1977), Southern Illinois University at Edwardsville: Southern Illinois University at Edwardsville Edwardsville, IL, Reprints in Mathematics and the Mathematical Sciences |
| [42] | Sun, M.; Aronson, J. E.; McKeown, P. G., Solving fixed charge transportation problems using tabu search, (Presented at the ORSA/TIMS Joint National Meeting. Presented at the ORSA/TIMS Joint National Meeting, San Francisco, CA (1992)) |
| [43] | Sun, M.; Drinka, D.; Aronson, J. E., Implementation data structures for a tabu search heuristic procedure for solving the fixed charge transportation problem, (Proceedings of the Decision Sciences Institute 1995 Annual Meeting. Proceedings of the Decision Sciences Institute 1995 Annual Meeting, Boston, MA (1995)), 915-917 |
| [44] | Sun, M.; McKeown, P. G., Tabu search applied to the general fixed charge problem, Annals of Operations Research, 41, 1-4, 405-420 (1993) · Zbl 0775.90287 |
| [45] | Walker, W. E., A heuristic adjacent extreme point algorithm for the fixed charge problem, Management Science, 22, 3, 587-596 (1976) · Zbl 0316.90041 |
| [46] | Wright, D.; Haehling von Lanzenauer, C., Solving the fixed charge problem with lagrangian relaxation and cost allocation heuristics, European Journal of Operational Research, 42, 304-312 (1989) · Zbl 0679.90045 |
| [47] | Wright, D.; Haehling von Lanzenauer, C., COLE: A new heuristic approach for solving the fixed charge problem — Computational results, European Journal of Operational Research, 52, 235-246 (1991) · Zbl 0725.90070 |
| [48] | Zangwill, W. I., A deterministic multiperiod production scheduling model with backloggings, Management Science, 13, 105-119 (1966) · Zbl 0143.22101 |
| [49] | Zangwill, W. I., Minimum concave cost flows in certain networks, Management Science, 14, 7, 429-450 (1968) · Zbl 0159.49102 |
| [50] | Zangwill, W. I., A backlogging model and a multi-echelon model of a dynamic economic lot size production system — A network approach, Management Science, 15, 9, 506-527 (1969) · Zbl 0172.44603 |
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.
