This paper reviews and evaluates some of the major recent developments in combinatorial programming. General solution procedures are discussed. A variety of planning applications is then examined. These applications are initially categorized as either (a) network or graph-theoretic problems, or (b) grouping and partitioning problems. The role of these various methods and applications in the planning of urban and regional systems is then critically assessed.
Get full access to this article
View all access options for this article.
References
1.
BalasE., 1965a, “An additive algorithm for solving linear programs with zero-one variables”, Operations Research, 13, 517–549
2.
BalasE., 1965b, “Discrete programming by the filter method”, Operations Research, 13, 915–957
BellmanR., 1957, Dynamic ProgrammingPrinceton University Press, Princeton)
6.
BellmanR., and KalabaR., 1960, “On kth best policies”, Journal of the Society for Industrial and Applied Mathematics, 8, 582–588
7.
BellmoreM., and NemhauserG. L., 1968, “The travelling salesman problem: A survey”, Operations Research, 16, 538–558
8.
BerryB. J. L., 1961, “A method for deriving multi-factor uniform regions”, Przeglad Geograficzny, 33, 263–282
9.
BoyeY., 1965, Routing Methods: Principles for Handling Multiple Travelling Salesman Problems, Lund Studies in Geography, series C, number 5 (C. W. Gleerup, Lund, Sweden)
10.
BurtO. R., and HarrisC. C., 1963, “Apportionment of the U.S. House of Representatives: A minimum range integer solution allocation problem”, Operations Research, 11, 648–652
11.
ClarkeG., and WrightJ. W., 1964, “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, 12, 568–581
CooperL., 1967, “Solutions of generalized locational equilibrium models”, Journal of Regional Science, 7, 1–18
15.
CroesG. A., 1958, “A method for solving travelling salesman problems”, Operations Research, 6, 791–814
16.
DantzigG. B., 1963, Linear Programming and ExtensionsPrinceton University Press, Princeton)
17.
DantzigG. B., and RamserJ.H., 1959, “The truck dispatching problem”, Management Science, 6, 80–91
18.
D'EsopoD. A., and LefkowitzB., 1964, “Note on an integer linear programming model for determining a minimum embarkation fleet”, Naval Research Logistics Quarterly, 11, 79–82
19.
EcholsR. E., and CooperL., 1968, “Solution of integer linear programming problems by direct search”, Journal of the Association for Computing Machinery, 15, 75–84
20.
GarverL. L., 1962, “Power generation scheduling by integer programming: Development of theory”, Transactions of the American Institute of Electrical Engineers, 81, 730–734
21.
GilbertE. N., and PollakH. O., 1968, “Steiner minimal trees”, Journal of the Society for Industrial and Applied Mathematics, 16, 1–29
22.
GilmoreP. C., 1962, “Optimal and suboptimal algorithms for the quadratic assignment problem”, Journal of the Society for Industrial and Applied Mathematics, 10, 305–313
23.
GilmoreP. C., and GomoryR. E., 1964, “Sequencing a one state-variable machine: A solvable case of the travelling salesman problem”, Operations Research, 12, 655–679
24.
GodlundS., 1961, Population, Regional Hospitals, Transport Facilities and Regions: Planning the Location of Regional Hospitals in Sweden, Lund Studies in Geography, series B, number 21 (C. W. Gleerup, Lund, Sweden)
25.
GolombS. W., and BaumertL. D., 1965, “Backtrack programming”, Journal of the Association for Computing Machinery, 12, 516–524
26.
GomoryR. E., 1958, “Outline of an algorithm for integer solutions to linear programs”, Bulletin of the American Mathematical Society, 64, 275–278
27.
GomoryR. E., 1960, “Solving linear programs in integers”, American Mathematical Society, Proceedings of Symposia in Applied Mathematics, 10, Combinatorial Analysis, 211–216
28.
HakimiS. L., 1965, “Optimum distribution of switching centers in a communication network, and some related graph theoretic problems”; Operations Research, 13, 462–475
HarrisB., 1967, “The city of the future: The problem of optimal design”, Papers of the Regional Science Association, 19, 185–195
31.
HellerJ., 1960, “Some numerical experiments for an MXJ flow shop and its decision-theoretical aspects”, Operations Research, 8
32.
HessS. W.WeaverJ. B.SiegfeldtH. J.WhelanJ. N., and ZitlanP. A., 1965, “Nonpartisan political redistricting by computer”, Operations Research, 13, 998–1006
33.
HirschW. M., and DantzigG. B., 1968, “The fixed charge problem”, Naval Research Logistics Quarterly, 15, 413–424
34.
HoggJ. M., 1968, “The siting of fire stations”, Operational Research Quarterly, 19, 275–287
35.
HookeR., and JeevesT. A., 1961, “Direct search solution of numerical and statistical problems”, Journal of the Association for Computing Machinery, 8, 212–229
36.
Hua Lo-keng and others, 1962, “Application of Mathematical Methods to Wheat Harvesting”, Chinese Mathematics, 2, 77–91
37.
KalabaR., 1960, “On some communication network problems”, American Mathematical Society, Proceedings of Symposia in Applied Mathematics, 10, Combinatorial Analysis, 261–280
38.
KalabaR., and JuncosaM., 1956, “Optimal design and utilization of communication networks”, Management Science, 3, 33–44
39.
KargL. L., and ThompsonG. L., 1964, “A heuristic approach to solving travelling salesman problems”, Management Science, 10, 225–248
40.
KnowlesK.TaggR. M., and ThompsonP. N., 1967, “A heuristic tree-search method of selecting face schedules at a colliery”, Operational Research Quarterly, 18, 139–148
41.
KoopmansT. C., and BeckmannM., 1957, “Assignment problems and the location of economic activities”, Econometrica, 25, 53–76
42.
KruskalJ. B., 1956, “On the shortest spanning subtree of a graph and the travelling salesman problem”, Proceedings of the American Mathematical Society, 7, 48–50
43.
KuehnA.A., and HamburgerM., 1963, “A heuristic program for locating warehouses”, Management Science, 9, 643–666
44.
KuhnH. W., and BaumolW. J., 1962, “An approximative algorithm for the fixed charges transportation problem”, Naval Research Logistics Quarterly, 9, 1–15
45.
KuhnH. W., and KuenneR. E., 1962, “An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics”, Journal of Regional Science, 4, 21–34
46.
LampkinW., and SaalmansP., 1967, “The design of routes, service frequencies and schedules for a municipal bus undertaking: A case study”, Operational Research Quarterly, 18, 375–397
47.
LandA. H., and DoigA.G., 1960, “An automatic method of solving discrete linear programming problems”, Econometrica, 28, 497–520
48.
LawlerE. L., and BellM. D., 1966, “A method for solving discrete optimization problems”, Operations Research, 14, 1098–1112
49.
LawlerE. L., and WoodD. E., 1966, “Branch and bound methods: A survey”, Operations Research, 14, 699–719
50.
LevyJ., 1967, “An extended theorem for location on a network”, Operational Research Quarterly, 18, 433–442
51.
LinS., 1965, “Computer solution of the travelling salesman problem”, Bell System Technical Journal, 44, 2245–2269
52.
LittleJ. D. C., 1966, “The synchronization of traffic signals by mixed-integer linear programming”, Operations Research, 14, 568–594
53.
ManneA. S., 1958, “Programming of economic lot sizes”, Management Science, 4, 115–135
54.
MaranzanaF. E., 1964, “On the location of supply points to minimize transport costs”, Operational Research Quarterly, 15, 261–270
55.
MillsG., 1967, “The determination of local government electoral boundaries”, Operational Research Quarterly, 18, 243–255
56.
NugentC. E.VollmannT. E., and RumlJ., 1968, “An experimental comparison of techniques for the assignment of facilities to locations”, Operations Research, 16, 150–173
57.
ObrucaA. K., 1968, “Spanning tree manipulation and the travelling salesman problem”, The Computer Journal, 10, 374–377
58.
PollackM., and WiebensonW., 1960, “Solutions of the shortest route problem: A review”, Operations Research, 8, 224–230
59.
RevelleC. S., 1968, Central Facilities Location, Center for Environmental Quality Management, Cornell University, Report number 1002
60.
RidleyT. M., 1969, “Reducing the travel time in a transport network”, in Studies in Regional Science, Ed. ScottA. J. (Pion, London), pp. 73–87
61.
SakarovitchM., 1968, “The k shortest chains in a graph”, Transportation Research, 2, 1–11
62.
ScottA. J., 1967a, “A programming model of an integrated transportation network”, Papers of the Regional Science Association, 19, 215–222
63.
ScottA. J., 1967b, “An integer program for the optimization of a system of chromatic graphs”, Journal of Regional Science, 7, 291–296
64.
ScottA. J., 1968, Combinatorial Processes, Geographic Space, and Planning, Department of Town Planning, University College, London, Discussion Paper series, number 1
65.
ScottA. J., 1969a, “On the optimal partitioning of spatially distributed point sets”, in Studies in Regional Science, Ed. ScottA. J. (Pion, London), pp. 57–72
66.
ScottA. J., 1969b, “The optimal network problem: Some computational procedures”, Transportation Research, 3, 201–210
67.
ScottA. J., 1969c, A Bibliography on Combinatorial Programming Methods and Their Application in Regional Science and Planning, Centre for Urban and Community Studies, University of Toronto, Report number GS-1
SokalR. R., and SneathP. H. A., 1963, Principles of Numerical TaxonomyW. H. Freeman, San Francisco)
70.
StairsS., 1968, “Selecting an optimal traffic network”, Journal of Transport Economics and Policy, 2, 218–231
71.
TeitzM. B., and BartP., 1968, “Heuristic methods for estimating the generalized vertex median of a weighted graph”, Operations Research, 16, 901–1092
72.
TyagiM. S., 1968, “A practical method for truck despatching problem”, Journal of the Operations Research Society of Japan, 10, 76–92
73.
VietoriszT., 1964, “Industrial development planning models with economies of scale and indivisibilities”, Papers of the Regional Science Association, 12, 157–192
74.
VietoriszT., and ManneA. S., 1963, “Chemical processes, plant location, and economies of scale”, in Studies in Process Analysis, Eds. ManneA. S. and MarkowitzH. M., Cowles Commission for Research in Economics, Monograph 18 (John Wiley, New York), 136–158
75.
WalkerR. S., 1960, “An enumerative technique for a class of combinatorial problems”, American Mathematical Society, Proceedings of Symposia in Applied Mathematics, 10, Combinatorial Analysis, 91–94
76.
WangJ.SnellR. R., and FunkM. L., 1968, “Toward a solution for the optimal allocation of investment in urban transportation networks”, Highway Research Record, number 238, 23–45
77.
WardJ. H., 1963, “Hierarchical grouping to optimize an objective function”, Journal of the American Statistical Association, 58, 236–244
78.
WeingartnerH. M., 1966, “Capital budgeting of interrelated projects: Survey and synthesis”, Management Science, 12, 485–516
