MATHEMATICAL ANALYSIS
research grant
EC-00309
Johns Hophins
Uniuersity
-------
MATHEMATICAL ANALYSIS
OF SOLID WASTE COLLECTION
This final report (SW-5rg) on work performed under
Research Grant No. EC-00309 (formerly UI-00828)
to the Johns Hopkins University
was written by DAVID H. MARKS and JON C. LIEBMAN
Department of Geography and Environmental Engineering
and has been reproduced as received from the grantee.
U.S. DEPARTMENT OF HEALTH, EDUCATION, AND WELFARE
Public Health Service
Environmental Health Service
Bureau of Solid Waste Management
1970
-------
Public Health Sew-iee Publ-Loot-ion No. 2104
Library of Congress Catalog Card No. 73-608768
For sale by the Superintendent of Documents, U.S. Government Printing Office
Washington, D.C., 20402 - Price $1.50
-------
FOREWORD
An important objective of the Bureau of Solid Waste Management is
to aid in developing economic and efficient solid waste management
practices. As authorized under the Solid Waste Disposal Act (Public
Law 89-272) , the Bureau has made almost 100 research grants to nonprofit
institutions in this effort to stimulate and accelerate the development
of new or improved ways for handling the Nation's discarded solids. The
present document, which is reproduced as received from the grantee,
reports on work completed under one of these research grants.
The general problems were investigated by the grantee in an ana-
lytical framework. These are the location of transfer stations and the
routing of collection vehicles. Mathematical optimization models for
these problems were constructed, using existing or slightly modified
algorithms. These models, particularly the ones for transfer facility
site selection, may be used in choosing the economically optimal plan
from among a large number of alternatives. This information serves as
nonquantifiable information in making the final choice.
Several of the models were tested by the grantee using data taken
from the City of Baltimore. Feasibility of transfer stations, the de-
sirability of rail haul, and the cost of increased collection frequency
were investigated in the testing process. These applications serve to
demonstrate the final usefulness of the models.
—RICHARD D. VAUGHAN, Director
Bureau of Solid Waste Management
iii
-------
ABSTRACT
The application of operations research to the analysis of
solid waste collection systems is studied. Models and techniques
for facility location and routing are discussed and extended.
Three different types of problem areas are viewed. Chapter II
covers facility location, in particular the location of transfer
facilities within a large-scale system. Chapter III deals with
finding optimal flow through given systems with added constraints.
In particular, a multi-commodity truck assignment problem where
a common vehicle fleet is used to carry several commodities
between supply and demand points is extended and ,solved.
Chapter IV is concerned with vehicle scheduling problems where
routes are to be found for individual collection vehicles among
various tasks. In Chapter V, the analysis of an actual large-
scale solid waste collection system, that of Baltimore, Maryland,
is carried out using some of the methods developed. Results of
the analysis indicate that the use of such models in the study
of large-scale public systems can supply a great deal of
information about, and insight into, the management and planning
of the system.
IV
-------
TABLE OF CONTENTS
Page
ABSTRACT
ACKNOWLEDGMENTS
TABLE OF CONTENTS
LIST OF TABLES
LIST OF FIGURES
CHAPTER I. OPERATIONS RESEARCH AND SOLID WASTE COLLECTION 1
A. The Scope of the Solid Waste Problem 2
B. Literature Review of Operations Research 6
in Solid Waste Collection
C. The Analysis of Solid Waste Collection 9
CHAPTER II. THE LOCATION OF TRANSFER FACILITIES 13
A. Problem Description and Literature Review 13
B. The Capacitated Trans-shipment Facility 26
Location Problem
C. Method of Solution 30
D. A Sketch of the Algorithm 35
E. A Detailed Algorithm for Solving the Capacitated 45
Trans-shipment Facility Location Problem
F. Computational Results 52
G. Augmenting the Algorithm to Consider Additional 55
Side Conditions
CHAPTER III. LARGE SCALE SINGLE AND MULTICOMMODITY ROUTING 58
IN GIVEN NETWORKS
A. Literature Review and Problem Description 60
B. Formulation and Solution of a General Multi- 69
Commodity Truck Assignment Problem
-------
TABLE OF CONTENTS (continued)
CHAPTER III. (continued)
C. An Algorithm for Constructing a Graph to 77
Represent the General Multicommodity Truck
Assignment Problem
D. Decoding the Solution of the Graph to Obtain 79
Routings
CHAPTER IV. VEHICLE SCHEDULING FROM GIVEN LOCATIONS 80
A. Literature Review 84
B. An Optimal Solution Method for the m Salesman 105
Traveling Salesman Problem
C. A Sketch of the Algorithm 108
D. A Detailed Algorithm for the m Salesman 120
Traveling Salesman Problem
E. Computational Experience with the Algorithm 125
CHAPTER V. THE ANALYSIS OF A SOLID WASTE COLLECTION SYSTEM 128
A. Characterization of the Baltimore Solid Waste 129
Collection System
B. Study Objectives 132
C. Calculations and Data for the Baltimore Study 134
D. Results of the Analysis 151
E. Summary of the Experimental Analysis ^34
CHAPTER VI. CONCLUSIONS AND EXTENSIONS 187
BIBLIOGRAPHY 191
vi
-------
LIST OF TABLES
Page
2-1. Results of Trial Runs of the Algorithm with 54
Randomly Generated Data
3-1. Computation Time to Solve Multicommodity Truck 76
Assignment Problems Using the Out-of-Kilter
Algorithm
4-1. Computational Experience on Truck Dispatching 96
Problems of Various Sizes Reported by Pierce (1968)
4-2. Computational Experience for Problems with Randomly 127
Generated Data
5-1. Cost of Operations and Services Provided by the 131
Bureau of Sanitation, City of Baltimore, Maryland, 1965
5-2. Pertinent Data Concerning the Forty Census Tracts 135
of the Northwestern Division of Baltimore, Maryland
5-3. Classification of Neighborhood Types 136
5-4. Average Collection Rate in Pounds per Hour for 141
Different Days Since Last Collection and Neighborhood
Type
5-5. Collection Costs in Dollars per Hour 141
5-6. X, Y Coordinates for Proposed Transfer Stations 145
5-7. Cost of Transfer Station as Function of Weekly 148
Capacity
5-8. Characteristics of Baltimore Incinerators 150
5-9. Description of Runs with Baltimore Data 154
5-10. Different Waste Load Assumptions and Their Effect 168
on Percent Differences Between Twice and Three
Times a Week Collection Without Transfer
5-11. Different Waste Load Assumptions and Their Effect 173
on Percent Difference Between Twice and Three Times
a Week Collection with Transfer
5-12. Effects of Regional Cooperation 183
vii
-------
LIST OF FIGURES
Page
2-1. The Fixed Charge Cost Function of Problem One and 37
Its Approximation in Problem Two
2-2. A Capacitated Node Representing Flow Through 50
Facility i
2-3. A Graph Representation for a Problem with m=2, 51
n=3, k=2
3-1. Graph Representation of the Szwarc Truck Assignment 72
Problem with m=2, n=2 and p=2
4-1. Graph for a Problem with N=4, s=l, m=2, k=2 113
4-2. Feasible Solution to Problem A 115
4-3. Regular Infeasible Solution to Problem A 116
4-4. Phantom Infeasible Solution to Problem A 117
5-1. Operating Divisions of Bureau of Sanitation, 137
Baltimore, Maryland
5-2. Map Showing Census Tracts in Northwestern Division 138
of Baltimore, Maryland
5-3. Map Showing Location of Proposed Transfer Sites and 139
Present Incinerator Sites, Baltimore, Maryland
5-4. Plot of Total System Cost vs. Size of Transfer Station 177
5-5. Plot of Average Haul Distance vs Dollars per Week 178
Cost of Operating System. Collection Frequency =
Three Times per Week
5-6. Plot of Average Haul Distance vs. Cost of Total 179
System. Collection Frequency = Two Times per Week
5-7. Plot of Cost of Solution vs. Estimate of Percent 180
Increase in Waste Load
5-8. Plot of Transfer Speed in MPH vs. Cost of Solution 181
5-9. Plot of Varying Collection Rate vs. Cost of Solution 182
viii
-------
- 1 -
CHAPTER I. OPERATIONS RESEARCH AND SOLID WASTE COLLECTION
Introduction
This thesis is concerned with the development of analytical
techniques to aid in the management and planning of solid waste
collection systems. Specifically, the techniques to be presented
are operations research models of routing and facility location
problems that are an inherent part of any collection or delivery
system. The models are most applicable in the private sector of the
economy, since they seek to minimize a well-defined and quantifiable
cost subject to explicit constraints. Solid waste collection
systems, however, are for the most part functions of the public
sector rather than the private sector. There is a divergence be-
tween the objectives of a public and private system, with the public
objective function being more vague and difficult to express formal-
ly. Constraints on the public system, especially those of a
political or social nature, may be difficult to measure, and criteria
of effectiveness may not exist in units which are commensurate.
All this does not mean that operations research models and
tools should not be applied to public sector problems such as solid
waste collection system management. As with private sector models,
analysis is performed as an aid to the decision maker and not as a
replacement for him. Careful use, based on an appreciation of the
factors that the models cannot consider explicitly, will allow
meaningful analysis to be carried out. The amount of analysis
-------
- 2 -
attempted in such large scale systems until recently has been
limited by the sheer size and complexity of the problems. Now with
the availability of operations research techniques and the aid of
high speed computers, the potential to increase greatly the under-
standing of such systems is apparent. It is hoped that this will
be an essay both in the advantages to be gained by systematic
investigation and the pitfalls involved in blindly following models
as a substitute for judgment and intuition.
The purpose of this work is twofold. First, the routing and
facility location problems of a collection system will be analyzed
and specific techniques suggested for approaching their solution.
Second, the application of these techniques to the investigation of
a large scale solid waste collection system as an indication of the
questions amenable to analysis by these models will be presented.
A. The Scope of the Solid Waste Problem
The solid waste system is defined to include the generation of
waste at a source, its collection and transport and the disposal
methods available. It is a large, expensive and vital on-going
system with peculiarities and problems that are in urgent need of
analysis. The yearly cost of operating the system in the United
States is reported by Black (1964) to be 3 billion dollars per year.
This amount makes it one of the foremost public works expenditures,
ranking after education, highways, welfare, and fire and police
among local government expenditures. The amount of waste generated
-------
- 3 -
in the United States from all sources approaches 125 million tons
per year. With increasing indications that these costs and volumes
will continue to rise drastically (Ludwig and Black, 1968), it seems
that detailed analysis of the system would be in great demand.
The main difficulty in analysis is determining some measure of
effectiveness for the service provided. The evolution through the
years of solid waste management from a private to a public problem
is indicative that the service provided is a public good. The
entire community suffers from the viewpoint of public health and
aesthetics when even one of its members refuses to dispose properly
of his solid wastes. The cost of enforcing sanitation ordinances
within a private system may far outstrip the cost of a publicly
owned system. A measure of efficiency of a public system might be
the degree of service offered to the customer in terms of frequency
of collection, types of wastes removed, locations from which waste
is collected, and the general level of satisfaction shown by the
consumers in order to provide the incentive for all to dispose
properly of waste material.
Management to achieve some desired level of service at minimum
cost is the goal, then, of the system operator, and he must study
the various control alternatives available to improve the efficiency
of the system. Cost analyses by Ludwig and Black (1968) reveal that
85 percent of the solid waste system cost is due to collection and
only 15 percent to disposal. This does not necessarily mean that
the only approach to the problem is through improvements in
-------
- 4 -
collection. In spite of the fact that most analysts consider that
waste loads are given and begin designing a system from that point,
it would seem that collection costs could be decreased by eliminating
wastes before they require collection and transport. From a techno-
logic point of view, materials which are difficult or expensive to
handle or dispose of might be replaced by those which are not. The
impetus for such a move could be either legislative, through laws
preventing the use of objectionable material, or economic, through
special taxes which would make using the material economically
infeasible. Economic incentives might also change current waste
material into production inputs. Education of the public might also
reduce waste load produced. Technologic advance in the form of
better in-home disposal units is a hope for the future even though
present devices are less than adequate. Present day incinerators
create an air pollution hazard and still have an ash disposal
problem. Garbage grinders simply trade a solid waste collection
system for an underground liquid waste system, and disposal problems
continue.
Some ideas have already been advanced for improving collection.
Prominent among these is the building of transfer facilities within
a city at which the special purpose collection vehicles could dis-
charge their loads to special purpose transport vehicles and thus
return to their collection jobs sooner. The suggested transport
vehicles have ranged from large tractor trailers to barges and rail-
road cars. Recommendations have also been heard for even more
-------
- 5 -
specialized collection vehicles such as small carts hauled in tandem
by a jeep or motor scooter to a rendezvous with a larger transport
vehicle. Zandi (1968) has proposed an extensive pipe line system
for moving solid wastes under pressure as an alternative to surface
collection. All of these control methods require some amount of
investigation and testing. Yet, the most important thing to realize
about the solid waste system is that it is too big, complex, and
vital to allow actual experimentation without great expense or the
potential of great chaos. Coupled with this are all the other
problems involved with studying large scale public systems. A rele-
vant data base is probably non-existent. The political implications
of who controls the system and who pays for which service may be the
most persuasive argument for throwing out a scheme that might
otherwise seem quite efficient. Since large investment has already
been made in attempting to manage the system, the designer is denied
the ,luxury of starting from the beginning and is often saddled with
working around the blunders of the past. To this morass the
analyst hopes to bring some order.
Since collection makes up 85 percent of the cost of the solid
waste management system, it is to this phase that the attention of
this work will be directed. Successful analysis of the collection
process could result not only in means for making it run more
efficiently, but also provide a means for measuring how non-
collection alternatives which reduce waste load must be priced in
order to make them better choices than the current approach to the
problem.
-------
- 6 -
B. Literature Review of Operations Research in Solid Waste Collection
A search of the pertinent literature reveals that very few
authors have concerned themselves with the application of operations
research to the study of solid waste collection systems. The work
that does appear falls into two categories: broad scale attempts at
outlining the nature and interactions of the entire waste management
system, in which collection is but one part, and narrower, more
specific investigations of the collection and disposal operations
suited to the detailed study of present operating systems. The most
complete of the broad scale studies is one still under way at the
University of California at Berkeley entitled "Comprehensive Studies
of Solid Waste Management". In the first annual report of the study
(Golueke and McGauhey, 1967) one of the stated objectives of the
study is "to explore the potential of operations research to help
in the definition and solution of the solid waste disposal problem".
Basically, two problems were investigated. The first was to find a
means for evaluating solutions for the total refuse disposal problem
that would not only be applicable to a wide spectrum of alternatives
but would be sensitive to environmental and governmental constraints
as well. This involved the development of conceptual models which
gave insight into the operation of the system. As a second problem,
the study undertook to build mathematical models for the conceptual
models. These included a waste generation model, a waste collection,
treatment and disposal model, a regional economic model, and models
-------
— 7 —
for population, public health aspects, land use and process techno-
logy. The most interesting of these models from the viewpoint of
operations research techniques was the waste collection, treatment
and disposal model. The subgroup working with this problem looked
at the means of determining how solid wastes should move from
sources through treatment and processing to disposal sinks. They
identified the problem as one of network analysis and noted that
solution should be gained by a graph theoretic approach. The out-
come of the development of specific techniques for solving the model
as formulated is reported by Anderson (1968), who was one of the
study group. Anderson was interested in modeling how the flow would
be optimized through a given system which contained existing
facilities and potential new facilities. He identified the problem
as a study of a trans-shipment network with some peculiarities due
to the nature of the processes involved. In considering a total
waste management model including intermediate treatment facilities,
it is necessary to consider the changes in volumes and in the state
of the wastes which is not possible using ordinary network algorithms,
He suggests two solution techniques: if the number of disposal sinks
is small, a branch and bound model may be used to generate optimal
flow through the system. If not, he also presents an out-of-kilter
algorithm for solution which includes an added feature of allowing
flow through a node to be proportioned in a fixed ratio. In both
models all costs are linear, and the system under investigation
considers the gross shipment between points and not the routing of
-------
individual vehicles among small collection tasks. Also, Anderson
dealt with the problem of finding flows through a known or given
configuration. To consider various combinations of new facilities,
each scheme must be evaluated separately. No methodology is
presented for a systematic search over facility location possibili-
ties. The assumption of linear costs omits some of the important
aspects of the problem. Although nonlinear costs may be given
linear approximations, this is only valid if the nonlinear costs
are convex. Facilities costs are commonly concave or quasi-concave
(fixed charge). Thus linear approximation either will not be
successful or must be clone in such a manner that one loses
confidence in the meaning of the results of the solution.
Other studies defining the solid waste system have been carried
out by consulting organizations for governmental units, but few if
any have gone beyond the characterization of the system and attempts
at simulation of the process. Such studies include reports by
Management Technology, Inc. (Anon. 1966b) for the State of Maryland,
and by Aerojet General (Anon. 1965) for the State of California.
The first work in attempting to understand the complicated
microstructure of the detailed collection process at the individual
block and vehicle level has been by simulation models. Quon, Charnes
and Wersan (1965) presented a model of a collection system with
particular attention to queuing problems at the disposal point,
using data from Winnetka, Illinois. Truitt, Liebman and Kruse (1968,
1969) constructed a simulation model in which the effect of a
-------
- 9 -
proposed transfer station may be investigated. Their results are
based on data from Baltimore, Maryland. Quon, Tanaka and Wersan
(1969) continue their earlier simulation work with a model for
studying changes in work rules and collection policy.
Other authors have dealt with different aspects of the collec-
tion problem that are more amenable to analytical attack. Coyle
and Martin (1967) presented a heuristic method based on dynamic
programming for aggregating small collection areas into work
schedule assignments for crews and vehicles. Skelly (1968) presen-
ted a fixed charge model for looking at the large scale problem of
transportation of wastes in which the variables include the alter-
native location of transfer stations. He used for a solution
technique a heuristic fixed charge algorithm developed by Walker
(1968). Skelly's work is discussed in greater detail in Chapter II.
Wolfe and Zinn (1967) have presented a simple model for an overall
crude evaluation of a large system as an example of systems appli-
cation in public works problems. A small trial problem was solved
using linear programming.
C. The Analysis of Solid Waste Collection
The analyst involved with a solid waste collection system is
concerned with answering a set of questions about the system so that
he can better understand it. This understanding will lead to
improved decision making. The sort of questions he might ask are
the following:
-------
- 10 -
1. What are the goals of the system? What frequency of
collection and types of service should be offered by the
system? How will changing the service affect cost?
2. What types of vehicles should be used, and how many?
3. How many personnel are needed and what should their
duties and work rules be?
4. What route should be assigned to each vehicle? How should
the city be divided into administrative subgroups?
5. Are there parameters of the system to which system costs
and variables are particularly sensitive?
6. If there is additional money available for research, into
what aspect of the system should further study be encouraged?
7. Should there be intermediate transfer stations for the
deployment of wastes to more specialized transport vehicles?
Where should they be located and what type of equipment
should they contain?
8. What type of transport vehicle would be used in transfer
from a transfer station to final disposal?
9. What type of disposal alternative should be chosen and
where should it be located?
10. What would be the effect on the system of new technology
in in-house waste reduction? In new disposal technology?
11. How will the stochastic nature of waste generation affect
the analysis? How will the solution change as the area to
be served continues to grow and spread?
-------
- 11 -
12. What are the effects of political, social and economic
constraints? Row much should be spent on aesthetic
factors? Is regional grouping a feasible alternative?
Ideally, to answer all these questions, the analyst would like
to build a model that would be able to follow the collection process
in its minutest detail and be able to manipulate all of the myriad
parameters that could possibly affect the solution. However, its
magnitude and complexity are such that to consider the system in its
entirety and encompass every possible detail is quite difficult, if
not impossible. For this reason, simplifying assumptions will be
made in model development which do not allow the detail mentioned
but will allow some approximation of the problem. Basically, two
different approaches are taken. If one is willing to neglect the
problems of routing of the individual vehicles through their collec-
tion tasks, the large scale problem of how material should move
through the system and how transfer facility location may be chosen
can be approached optimally. This will be called the "macro-scale"
or "flow of materials" subproblem. If the location of facilities
and the collection areas assigned are known for a set of collection
vehicles, the small scale problems of routing vehicles among
individual collection tasks may be approached. This second sub-
problem will be called the "micro-scale" problem. Extensive
discussion and development of both of these problems will be pre1-
sented. Application of the proposed models to the investigation of
a solid waste collection system will be emphasized.
-------
- 12 -
The general outline of this thesis is as follows: Chapter II
is concerned with the location of transfer facilities. If the
problem is treated as a large scale "flow of materials" problem, it
is found to belong to a class of problems known in the literature
as location problems, warehousing problems and plant location
problems. Techniques for solving these problems are discussed and
a special method is developed that is particularly adaptable to the
solid waste collection problem.
Chapter III also deals with the large scale flow of goods
problem. In this case, the network structure of the system is given
and optimal flow through it is found for more extensive constraints
than were allowed in Chapter II. In particular, multicommodity flow
using a common vehicle fleet is studied. Extension of a multicom-
modity truck assignment problem by Szwarc (1967) is presented and
computational experience is discussed.
Chapter IV deals with the micro-scale routing problems. These
are found to be represented by several classes of problems in opera-
tions research. The most general problems discussed are known as
vehicle scheduling problems and traveling salesman problems. An
original algorithm for the m-salesman traveling salesman problem is
presented. Problems of routing in street networks are shown in some
cases to be Chinese postman problems, and this problem is discussed.
Chapter V deals with the analysis of an actual system using some
of the techniques developed in the thesis with fairly crude data.
Chapter VI presents a summary, and some conclusions and
suggestions for further research.
-------
- 13 -
CHAPTER II. THE LOCATION OF TRANSFER FACILITIES
A. Problem Description and Literature Review
Determining the location of intermediate facilities where
transfer of solid waste may take place from specialized collection
vehicles to vehicles more suited for long-haul transportation is a
problem that has received considerable attention within the past few
years. The fundamental questions involve the desirability of
transfer stations, their number, location, and capacity, and the
specific functions which they should perform. These decisions may
be viewed as a trade-off between the building of facilities and the
cost of transportation. Two points are immediately clear. First,
this is a general problem of facilities location in both the private
and public sector rather than a problem specific to solid wastes,
and studies in the genei~al area of facilities planning may be
applicable. Second, assuming that facility costs and transportation
costs can be defined, it may be possible to derive some, mathematical
formulation of the problem.
A search of the operations research and economics literature
reveals that a considerable interest has been generated and mathe-
matical formulation for certain aspects of the problem has been
developed. The methods developed have been for the large scale
"flow of goods" features of the problem in which the concern has
been with selecting paths over which materials flow from collection
areas to facilities for transfer and disposal. The routing of
-------
- 14 -
vehicles within collection areas is usually ignored, as it would
add a complexity to the problem that would make it intractable.
However, since the goal of model formulation is to obtain some
structure that may be solved and manipulated in order to gain better
understanding of the system as a whole, such work is still of great
importance. Care should be taken, though, in the use of the solu-
tions generated. An optimal answer to a subproblem may have little
meaning in the context of the larger problem, even though manipula-
tion of the subproblem to show the sensitivity of its optimal
solution to changes in parameters and control methods may provide
a great deal of insight and information for the analyst.
The problem area as discussed in the general literature is
known by several names: the location-allocation problem, the plant
location problem, the central facilities problem and the warehousing
problem. To a large extent, all of these names imply the same
general problems, with differences depending on the assumptions made
in order to facilitate modeling and solution techniques for the
models. As noted, the general formulation is based on trading off
facility cost versus transportation cost. The problem is to find
that system configuration that minimizes the sum of the two costs.
Analysts who have worked on this problem have been faced with
two basic problems in definition and assumptions which have led to
two different structures for analytical approach. The first assump-
tion is whether demand is spread, uniformly or otherwise, continuous-
ly across the entire area to be served, or is located at discrete
-------
- 15 -
points. The second assumption is whether potential facilities sites
are infinite in number or are limited to a discrete number of
feasible alternatives. If the assumption is made that both demand
and facilities locations are infinite the analysis procedure is
quite ill-defined and little analytical success has been obtained
in such problem solutions. However, once some form of limiting
assumption is made of the solution space, considerable progress in
solution technique has been found. It should be pointed out that
such discrete assumptions are not severe from an engineering point
of view. In fact, within a city there are not an infinite number
of sites for solid waste facilities, but a finite number based on
available land, zoning and concentrations of population and the
location of existing structures. Demand, too, does tend to cluster
and an assumption dividing a region into areas with each represented
by its demand at some centroid is not unreasonable in most cases.
The two approaches may be structurally distinguished by regarding
the problem with infinite solution space for demand and facility
location as location on a plane, and the discrete problem as
location on a network.
The problem names most associated with location on a network
are the warehousing problem and the plant location problem. In the
warehousing problem, warehouses or central facilities are built to
serve as supply points for satisfying demand in the region and the
flow of goods takes place from the facility to the demand area. In
the plant location problem, the central facility is a production
facility which requires a flow of goods to it from the surrounding
-------
- 16 -
regions. From an analysis point of view, the problems are identical
and the problem names may be used interchangeably. Thus the following
description of a warehouse problem may be converted to a description
of the plant location problem by changing the direction of flow of
goods.
The statement of the warehouse problem is: Given a number of
demand areas for a certain product, each with a demand D-, and a
number of alternative sites where facilities may be built to satisfy
these demands, determine where facilities should be built and which
demand areas are to be served by each facility. The objective is
that the sum of the transportation cost and the amortized facility
cost is minimized.
The general mathematical formulation is:
n m m
Minimize: I I d^x^) + E Fi(yi) (2-1)
n
subject to: j; x^ = y.._ i=l, 2 m (2-2)
m
I xi, = D. j=l, 2, n (2-3)
J
xij^ ° i=l, 2, , m (2-4)
J=l, 2, ...., n
vi » 0 i=l, 2, m (2-5)
where: x = amount shipped from warehouse i to
demand area j (a decision variable)
-------
- 17 -
y. = total amount shipped from warehouse i
(a decision variable)
d.j.(x£.j) = cost of shipping x^ . from i to j (dollars)
F^Cy^) = cost of building and operating warehouse i
when y^ is to be shipped from it (dollars)
D. = demand at area j
n = number of demand areas
m = number of proposed warehouse sites.
If the functions F^(y^) and d- -(x^.:) are linear, the problem
becomes a simple transportation problem. Unfortunately, the function
F^(y^) is frequently nonlinear, and generally exhibits a large fixed
investment for land, foundations, utilities, etc., before any amount
may be manufactured or shipped. Once the facility is begun, the
marginal cost of another unit of storage or manufacture may decrease
(economies of scale). Such a function is termed concave and is not
amenable to linear programming. This is the feature which has drawn
the most attention from researchers in this field, and the method of
treating the concave cost function is the key element of most
procedures.
Among the earliest work in the literature is a paper by Baumol
and Wolfe (1958), in which the authors approach the problem by using
a linear facility cost instead of a fixed charge. Then the problem
may be formulated as a transportation problem. The resulting solu-
tion is then adjusted, using a heuristic procedure, to reflect the
fixed charge aspects of the problem. This discussion will be
limited to five fairly recent approaches, all thought to have some
-------
- 18 -
application and validity. The papers by Feldman, Lehrer and Ray
(1966) and by Kuehn and Hamburger (1963) represent two early formu-
lations of the problem which rely on heuristics to achieve good
solutions. Balinski (1965) formulated the problem as an integer
programming problem which is capable of solution for small cases.
Efroymson and Ray (1966), Spielberg (1969) and the author of this
thesis propose methods which achieve optimal solutions to larger
mathematical problems as structured through branch and bound
techniques.
As noted before, Kuehn and Hamburger used a heuristic algorithm
to find good solutions to the warehousing problem. They assumed
that transportation costs are linear functions of the amount trans-
ported and that facility costs are of the form,
Fi(Yi) = a^ + ^±y± if tne facility exists
=0 if it does not
Thus F^(yi) consists of a fixed charge that is independent of
the storage and a linear cost which does depend on storage, if the
facility exists.
The method starts with one facility and tries adding another
facility to see if the total cost can be decreased. The general
assumption is that the best N facilities contain the set of the best
N-l facilities. Termination of the procedure occurs when it amjears
that another facility cannot be added without increasing the total
cost.
One difficulty in working with heuristics is that there is no
-------
- 19 -
way to tell how far the final answer obtained is from the true
optimal solution. This difficulty tends to decrease the validity
of an analysis of sensitivity by obscuring the cause of a change in
the solution which might occur when a parameter is altered. An
improvement could be due to the parameter change or to luck in the
computations. Thus, extreme care should be taken in using a
heuristic for sensitivity analysis.
Feldman, Lehrer and Ray assumed a more general form for the
facility cost, that of a continuous concave function. They also
assumed that transport cost is linear in the amount shipped between
points. Since F^(y^) does not have a linear variable cost but a
variable cost that is dependent on how many demand areas are being
served by the facility, the problem of assigning demand areas to
existing facilities is not as easy as before. An approximation
method is used to accomplish this assignment. Whereas Kuehn and
Hamburger began with one facility, Feldman et al. started with all
potential facilities existing and dropped some out. Termination
occurs when no further savings can be obtained by dropping facili-
ties. Balinski (1964, 1965) developed a formulation for the plant
location problem that could be solved by integer programming tech-
niques. In order to do this, F^y^) is specified as a single fixed
charge, Ft, if the facility exists. Capacity constraints are not
specified for the facilities. The formulation is as follows:
n m m
Minimize: z I cii xij + £ Fi ^i <2"6>
J
-------
- 20 -
m
subject to: £ x^ = 1 j=l, 2, ...., n (2-7)
0 4x±j S yi$ 1 i=l, 2, m (2-8)
3=1, 2, ...., n
yi - (0, 1) i=l, 2, , m (2-9)
where: c^. = t.. * D.
t-- = the unit transportation cost from facility i
to customer j
Dj = demand at j
x^ = the fraction of D^ supplied from facility i
F£ = the fixed charge associated with facility i
n = the number of customers
m = the number of proposed facilities
Equation (2-7) specifies that each customer must have all his
demands satisfied and inequality (2-8) requires that demand may not
be satisfied by a facility unless it exists. Note that even for a
small problem the above formulation has a formidable number of con-
straints and variables. For an N-customer, M-plant problem there
are N x M + N + M constraints and N x M + M variables. Thus, for
the case M=10 and N=30, the problem to be solved has 340 constraints
and 310 variables.
It would seem, at first glance, that if the integer requirement
(2-9) were replaced by the simple constraint y.^ £ 1, the solution to
the resulting linear programming problem would be integer. However,
a counter example is reported and the means of solution first
-------
- 21 -
attempted is an integer programming cutting plane technique of
Gomory (1958). This is shown to have a very slow convergence even
for small problems, and is abandoned for larger problems. Balinski
suggests another scheme for solution which involves partitioning
the problem using a method of Benders (1962). This requires the
successive solution of more complex integer programming problems.
A proof is supplied that the method will converge to the optimal
solution in a finite number of steps, but it appears that computation
time will be quite large for this type of solution as well.
Efroymson and Ray (1966) presented a method of solution to the
same problem using a branch and bound scheme that has been tested
computationally with good results. Their formulation of the
problem is:
Minimize:
m n
E Z
m
I
(2-10)
subject to:
m
Z x.
j-l, 2, n
(2-11)
where:
j-l
1=1, 2, . . . . , m
(2-12)
cr> yi = (°> 1) (2-13)
:.. = cost of supplying the entire demand area j
from warehouse i
?* - fixed charge for establishing warehouse i
7. = 1 if the i'th warehouse is built, 0 if not
-------
- 22 -
x.. = 1 if the demand area j is served by warehouse
1J i, 0 if not
n. = maximum number of demand areas that may be
assigned to facility i
m = number of possible warehouse sites
n = number of demand areas
An examination of the constraint set shows that Balinski's
explicit constraints on the value for each allocation to a facility
(2-8) have been collapsed into a smaller set of constraints on the
maximum amount that may be assigned to a facility (2-12). This con-
straint specifies that if the i'th facility does not exist (i.e. y.^
no assignments may be made to it. However, if it does exist, assign-
ments may be made to it up to the value of n.. The value of n^
becomes an important point in the development of the algorithm. The
solution method involves an implicit search of all the possible
feasible solutions. Suppose all the feasible solutions were repre-
sented as branches of a tree with each branch exhibiting a specific
value, zero or one, for each variable. In order to avoid searching
the entire tree to find the optimal solution, means for estimating
the lower bound on the solution by continuing down the tree are
available. If at any point on a branch the estimate of the lower
bound is greater than a known feasible solution, that branch is
dominated and may be abandoned. The speed with which such a
procedure progresses to an optimal solution depends on the method
used to obtain lower bounds and the rules used for determining
which branch to investigate next.
-------
- 23 -
In establishing their branch and bound scheme to solve the
problem, Efroymson and Ray had to specify a means for finding a
lower bound at each node on a branch. They specified that this
could be accomplished by solving the problem denoted by the objec-
tive function (2-10) plus constraints (2-11) and (2-12), while
ignoring the integer requirement (2-13). If n^ is a capacity con-
straint such that it is limiting, i.e. areas that might assign to i
are excluded because there is not enough capacity at i, the problem
to be solved at each node requires the solution of a transportation
problem. However, if n^ is greater than or equal to all the areas
that could possibly assign to i, the lower bound problem at each
node may be solved by a very simple iterative procedure that is
very fast. Simply assign the area to the open facility such that
transportation cost plus expansion cost at the site is minimized.
In order to speed their algorithm, the authors abandoned the
requirement for a capacity constraint on facilities by setting n^
at a number greater than or equal to the total number of demand
areas that could possibly assign to that facility. Solution of
problems with 50 possible warehouse locations and 200 demand areas
in 10 minutes on the IBM 7094 is reported.
Spielberg (1969), in a more recent paper, discussed largely
the same problem. His algorithm for solution is also branch and
bound, but contains many added features which shorten computation
time. A great deal of computational experience is reported with
problems as large as 100 facilities and 150 demand areas. The
-------
- 24 -
author also suggested extensions of the problem, but reported no
computational experience for these.
Looking at the special problem of the location of transfer
facilities for solid wastes, it is noted that there is an added
dimension beyond that of the warehousing formulation. The facilities
to be located are intermediate points within a trans-shipment net-
work between the sources and sinks of flow. Thus the transportation
cost involves two elements, transportation from source to inter-
mediate point, and from intermediate point to the sink. There are
possible facility costs at the intermediate point as well as
variable costs at the sources and sinks.
One of the weaknesses of all the previous work in warehousing
problems is that there may be no capacity restrictions on the amount
of flow through a central facility when in fact the cost estimates
and the physical reality of the problem require that there be such
a constraint. The problem of locating an intermediate facility with
capacity constraints on flow will henceforth be called the capaci-
tated trans-shipment facility location problem. The only previous
work on this problem is that of Skelly (1968). In addition to
recognizing the above features of the problem, Skelly was also
interested in time-staging of construction of facilities and disposal
points. He formulated the problem with a series of linear constraints
which define the trans-shipment and time requirements. This leaves
a large fixed charge integer programming problem.
Skelly chose as his solution method an algorithm by Walker (1968)
-------
- 25 -
for the fixed charge problem. This algorithm is simplex-based, i.e.
it requires that a basis the size of the constraint set be estab-
lished and manipulated. Furthermore, it is a heuristic and may not
yield a global optimum. The fact that the Walker algorithm is
simplex-based leads to some problems in computational efficiency.
Trans-shipment problems belong to a class of network flow problems
as described by Ford and Fulkerson (1962), which may be written in
linear programming form but because of the sparseness and special
structure of the constraint matrix, can be solved much more quickly
and efficiently by primal-dual labeling procedures. Because of the
simplex approach, the size of the problem that Skelly may consider
is severely limited. Furthermore, since the value of such models
is in the repeated solution using different parameters to show
sensitivity, the use of a heuristic algorithm may be self-defeating.
-------
- 26 -
B. The Capacitated Trans-Shipment Facility Location Problem
The remainder of this chapter is devoted to a new solution
method for the capacitated trans-shipment facility location problem
where there are fixed charges associated with the intermediate
facilities. The algorithm guarantees an optimal solution and will
solve fairly large problems within moderate computation time. The
problem to be solved is stated as follows:
There is a set, K, of sources for a product with an amount S,
at each source. In addition, there is a set of sinks, J, for the
product, each with an upper and lower bound on demand of D.u and D, .
A set of proposed intermediate facility sites, I, has been suggested
as trans-shipment points between the sources and sinks. Each pro-
posed facility has a fixed charge, F., a variable unit cost, Vj,
which is a linear function of the amount shipped through the
facility, and a capacity, Q±. The problem is to find which facilities
should be built and which sources and sinks each facility serves, so
that the total cost of facilities and trans-shipment is minimized.
In the context of a solid waste collection system, the flow
through the system is solid waste material with the sources represen-
ting the locations of waste generation and the sinks representing
the disposal methods and locations. A lower bound on the amount of
solid waste reaching a sink is motivated by the fact that for some
types of present disposal processes such as incineration, a minimum
throughput is necessary to keep the process operating. Future
-------
- 27 -
development in waste disposal technology may also lead to other
processes which require continuous operation. The intermediate
facilities are transfer stations where transfer may take place from
smaller collection vehicles to some other means of transport to the
disposal points (sinks). The means of transport from the transfer
station may be by vehicles such as large trucks or trains, or by
non-vehicle methods such as pipelines. In addition to simple
transfer, the activity which takes place at a transfer station may
include some form of processing such as sorting, compacting and/or
incineration.
In mathematical form this problem becomes the following:
Problem One
m m n m p ^ ^
Minimize: I ?±y± + E I Cij*ij + E E ckixki <2'14)
subject to the constraints:
m ^
* xki ^ Sk k=1> 2> •'••» P (2
1-1
n * p **
I x., = X x, . 1-1, 2, ...., m (2-16)
1J k
X xj* ^ Qi7 1-1, 2, ..... m (2-17)
k=l
u m *
(2-18)
-------
- 28 -
_ t&aSft .
xii» xki are non~ne8ative integers (2-18)
yi = (0, 1) (2-18a)
where: y^_ = 1 if the i'th facility is built
= 0 otherwise
x*. = flow of material from facility i to sink j
r*rttj
x^j^ = flow of material from source k to
intermediate point i
c*. = c.. + r. - unit cost associated with a transfer
1J 1J J of material from facility i to sink j
(dollars per unit)
c.. = unit shipping cost from facility i to sink j
(dollars per unit)
r^ = unit variable cost associated with using sink j
(dollars per unit)
•£••£• I
GJ^^ = c, . -f t. + V. = unit cost associated with
transfer of material from
source k to facility i
(dollars per unit)
t
c. . = unit shipping cost from source k to facility i
(dollars per unit)
t^ = unit variable cost associated with using source k
(dollars per unit)
V^ = unit variable cost associated with using
facility i (dollars per unit)
F..^ = fixed charge for establishing facility i
(dollars)
S^ = amount supplied at source k
Dj = upper bound on amount demanded at sink j
DJ = lower bound on amount demanded at sink j
Q-j^ = capacity of the i'th facility
-------
- 29 -
m = number of proposed facility sites
n = number of demand areas
p = number of supply points
Inequality (2-15) expresses the requirement that flow from the
source cannot exceed the supply of material there. Equation (2-16)
states the conservation of flow requirement that the flow entering
the i'th facility must be equal to the flow leaving it. In
inequality (2-17) the fixed charge nature of facility location is
expressed. If the i'th facility does not exist, y. = 0 and no flow
may take place through it. If the i'th facility does exist, y^ = 1
and flow up to Q^ may pass through it. Inequality (2-18) specifies
that flow to sink j must be between the upper and lower bound on
the capacity of the sink.
There are several additional constraints or side conditions
that might be of interest in the above formulation. A budget con-
straint on the number or cost of the facilities to be built, or a
mutual exclusivity constraint which allows a particular facility to
exist only if another does not, might be included. As noted with
sinks (disposal points) a lower bound requirement different from
zero on the flow through a facility or a particular arc due to
technical requirements might also be imposed. The side conditions
will be discussed in detail later in this chapter.
-------
- 30 -
C. Method of Solution
It is desired to find a solution to Problem One that will give
. •?.'i»li
values to the variables x*., xki and y± so that the constraint set
is satisfied and the objective function is minimized. One means for
doing this would be to set up the problem as an integer linear pro-
gramming problem and attempt to solve it by a cutting plane method
such as that of Gomory (1958). However, for an M-facility, N-
demand-area, P-supply-point problem there are
2(M + N + P) constraints
and MxN+Mx P+M variables which are
required to be integer.
Thus for a problem of M=10, N=10, P=10, the integer program
would have 60 constraints and 210 variables. Solution of the
corresponding linear programming problem with the integer
constraints relaxed will not necessarily yield integer solutions.
However, there are some linear programming problems which have
special structure that may be related to a network, which may be
solved optimally by procedures other than the simplex method of
linear programming in a much shorter time and yield integer solu-
tions. An example is the trans-shipment problem which represents a
supply-demand relationship where demands for a product at some
points are satisfied by shipments from sources of the product
through intermediate points. The resulting linear programming prob-
lem may be shown to have the form of a network, and finding the
-------
- 31 -
minimum cost maximum flow through the network gives the solution
to the trans-shipment problem.
Consider Problem One. It has some elements of network struc-
ture, but it may not be represented as a network problem.
Inequalities (2-15), (2-16) and (2-18) exhibit an incidence matrix
which by themselves icould form a trans-shipment problem and would
yield integer solutions. The addition of inequality (2-17) which
has a coefficient of one variable that may be different from zero
or one, destroys this property. However, a related but similar
problem may be written in a form that will allow it to be solved
by a network algorithm. Consider the problem of determining the
flow through the system from supply source through intermediate
facilities to demand areas if the facilities to be built are known.
This implies that the values for the y^'s (the variable which
determines which facilities are built) are known and given. Let S
equal the set of indices representing the values of y.j_=l. Then
the problem may be written in the following form:
Problem One (a)
n mo
" '
+ I P (2-19)
Minimize :
subject to
m
Z
i=l
the
m
£
i=l
P
^
k=l
n m
•=1 CijX*J + i=l
constraints :
"KTf _
Xki ^ Sk
**
x. . 5 4^
P
E
k=1' 2 ..... ' p (2"20)
(2-21a)
-------
- 32 -
** - 0 ±SS (2-21b)
ki
I x*. - I x** 1-1, 2, ..... m (2-22)
Z xJj^D.1 J-1, 2, ...., n (2-23)
* **
(2-23a)
where the variables are defined in the same manner as for Problem
One , and
S = the set of indices for which y.j-1'
This problem has the form of a network problem as described by
Ford and Fulkerson (1962), and can be solved by finding the minimum
cost maximum flow in the network. The method for finding the minimum
cost maximum flow through the network is the out-of-kilter algorithm
If
which was developed by Fulkerson (1961). One of the computer codes
for the IBM 7000 and 360 series computers is in Fortran IV by Clasen,
£/
and is available through the IBM Share Distribution System.
It should be noted that without the upper and lower bound on
demand at the sink expressed in inequality (2-23), the above problem
- Those interested in following the development and. proofs of the
out-of-kilter algorithm are directed to Ford and Fulkerson (1962)
or Fulkerson (1961). A good description of a more primary nature
is found in Durbin and Kroerike (1967). A discussion of numerical
techniques is found in Clasen (1968).
2/
-IBM Share Distribution #3536, "Out-of-Kilter Network or Transpor-
tation Problem Solver", IBM, White Plains, New York.
-------
- 33 -
would be a simpler trans-shipment problem rather than an out-of-
kilter problem. However, the existence of the need for such
constraints for this and other aspects of the problem means that
an out-of-kilter problem rather than a simpler trans-shipment
problem will be used for the basis for algorithmic development.
The advantages of being able to formulate this subproblem as a net-
work problem solvable by a network algorithm such as the out-of-
kilter are twofold. First, network algorithms are very fast when
compared to simplex based linear programming techniques. Second,
the out-of-kilter algorithm may be started with any existing
solution after constraints or costs have been changed. This re-
start capability will be of considerable interest in the solution
scheme to be developed. Because of the network structure of the
problem, both the network algorithm and a simplex algorithm will
always yield integer solutions.
The network structure of a location problem has been recognized
by other authors. Efroymson and Ray (1966), and Spielberg (1969),
while working on simpler location problems noted this structure and
took advantage of it in a branch and bound scheme. In their case,
the resulting structure was that of a transportation problem and
the means of finding a lower bound on a branch might involve the
solution of such a problem at each node of the branch. However, if
the simplifying assumption is made that facilities do not have an
upper bound on capacity, the transportation problem decomposes into
a simple iterative scheme which is quite fast. Both authors
-------
- 34 -
attempted to save time by ignoring capacity constraints and using
the simple iterative scheme. This limited their work to transpor-
tation problems.
The technique to be proposed below arose from the need to
include both a trans-shipment network structure, and capacity con-
straints on facilities in the formulation of transfer station
location problems. It was clear from the outset that this more
general formulation would require greater computation time, but
it was anticipated that the increased cost of finding a solution
would be more than offset by the greater generality of the solution.
Much of the success of the algorithm is based on the ability to
restart the out-of-kilter algorithm at each stage, so that little
computational effort was necessary to calculate successive lower
bounds. Trans-shipment and transportation algorithms, with slight
manipulation of the solution, also exhibit this restart capability.
-------
- 35 -
D. A Sketch of the Algorithm
It is desired to solve Problem One, which is repeated here for
convenience.
Problem One - The Capacitated Trans-shipment Facility Location Problem
mi1** mP****m ,„ ,x
Minimize: E E c^x... + E E ckixki + E F±yi (2-24)
i-1 j-1 i=l k=l i=l
subject to the constraints:
I x** I S k-1, 2, ..... p (2-25)
ki k
n P **
E x*. = E x, . i-1, 2, ____ , m (2-26)
J-l 1J k-1
P **
E xki , D X j-1, 2, ..... n (2-28)
J i-1 J J
* **
x , x . are non-negative integers
^- J KX
where the notation is as previously stated.
This problem has two elements that make it difficult to solve.
First, it is a fixed charge problem with the fixed charge variable,
y., appearing in inequality (2-27) with a coefficient Q. which may
be different from plus or minus one. Second, an integer solution
-------
- 36 -
is required. However, as has been previously noted, if the values
of the fixed charge variables, y , are known, then the resulting
*
problem of finding the values of the flow variables, the x..^ s and
the x..'s, becomes a form of trans-shipment problem whose solution
K: 1
may be found by using the out-of-kilter algorithm to find the
minimum cost maximum flow of the corresponding network. In order
to solve Problem One, some approximations will be made.
The flow of materials through the i'th facility is given by
P **
and the cost function of the i'th facility is
/ P **\
F. + V. I E x, . I if the i'th facility exists,
M k=l k1/ i.e. if y.-l
(2-29)
0 if the i'th facility does not
exist, i.e. if y.=0
The slope of this cost function is shown in Figure 2-1, along with
a linear approximation of the cost. The approximation is arrived at
in the following manner. Convert the fixed charge, F., into a unit
charge by dividing by the capacity of the facility Q.. Then the
approximate cost function is
(2-30)
and it underestimates the true cost function given in (2-29) except
at two points where they are equivalent. These are when there is
-------
- 37 -
DOLLARS
TO
BUILD
AND
OPERATE
FACILITY
FIXED CHARGE
COST FUNCTION
OF PROBLEM ONE
(Fj/Qj
LINEAR APPROXIMATION
OF COST FUNCTION IN
PROBLEM TWO
FLOW THROUGH FACILITY
Figure 2-1.
The Fixed Charge Cost Function of Problem One and
Its Approximation in Problem Two.
-------
- 38 -
no flow through the facility, and when the flow equals the capacity.
The original idea for this approximation is due to Baumol and Wolfe
(1958).
Suppose that all the facilities are given such an approximate
cost function, and the constraint on the capacity of each facility
(2-27) is adjusted to
P **
rki * Qi
i=l, 2, ...., m
k=l
as if all facilities existed. Then an approximation problem may be
written as
Problem Two - Linear Approximation Problem
Minimize:
m n
1-1 J-l
* *
c. .x.. +
ij ij
m P ** ** m F / n \
E Z Cki\i + * oM E Xiil (2'32)
•—1 L. —1 *StJL K1 4—1 W» I 4—1 •'-J I
L"~JL. IX^J. 1"~1 JLlj^JL *
subject to the constraints;
m
z xi • ^ s,
i=1 ki '' k
n * P **
Z x = Z x
ij k=1 "k!
j=l ij
P **
^ Q
£• ""•*•» 4.} ...»J P
i=l> 2, . ..,, m
i=li 2, ....,
(2-33)
(2-34)
(2-35)
j=l> 2, ...., n
(2-36)
-------
- 39 -
* **
x , x, . are positive integers
ij KI
(2-36a)
y - (o, i)
Problem Two has a linear objective function and the constraints
take the form of a network problem solvable by the out-of-kilter
algorithm.
Problem One and Problem Two have similar constraint sets so
that a feasible solution to Problem Two is also a feasible solution
to Problem One. However, because of the differences in the cost
functions, the solution of Problem Two gives a lower bound for the
cost of the optimal solution to Problem One. If the flow through
each facility in Problem Two is
P **
£ x. . = Q. or 0 i=l, 2, ...., m
k-1 lci
then the cost of Problem Two is the same as that of Problem One and
an optimal solution has been found. If for some facility the flow
through the facility is
P **
0 < = Xki < Q!
k=l
then a lower bound and not an exact solution has been found for
Problem One and the search for the optimal solution must continue.
This is accomplished by a method of search through the set of
feasible solutions by either branch and bound or implicit enumera-
tion methods. While both are search method's based on branching
-------
- 40 -
and the use of bounds for eliminating areas of search, the two
methods do differ somewhat in the search procedure. Implicit
enumeration implies that a branching scheme will be set up so that
all possible feasible solutions will be enumerated either implicitly
or explicitly. Bounds are used to avoid searching branches which
are obviously dominated by existing feasible solutions. Examples of
such techniques are Glover (1965), Balas (1965), Balas (1967) and
Geoffrion (1966, 1967). Branch and bound implies that the set of
feasible solutions is divided into mutually exclusive sets and
lower bounds estimated until an optimal solution has been found
and verified. In implicit enumeration, the goal is to enumerate
all solutions while in branch and bound the goal is to subdivide
into subsets until lower bound estimates show that an optimal
solution has been found. Examples of branch and bound techniques
are the work of Land and Doig (1960) and Little (1963). An example
of implicit enumeration in the field of environmental engineering
is a solution to a water pollution control problem by Liebman and
Marks (1968).
The method of solution chosen to solve Problem One is branch
and bound. The basic reasoning behind the technique is that it is
possible to solve a highly structured problem by solving less highly
structured surrogates. A feasible solution to the surrogate problem
is always a feasible solution to the highly structured problem being
approximated as well. However, the value of the objective function
of the surrogate is not necessarily the value of the objective
-------
- 41 -
function of the problem it approximates with the same feasible
solution. Because of the linear approximation used, the cost of
the surrogate is lower than or equal to the cost of solving the
original problem. Define an exact solution as an optimal, feasible
solution to the surrogate where the value of the objective function
for both the surrogate problem and the original problem are the
same. A lower bound solution represents the case when the cost of
the surrogate problem is lower than the cost of the original
problem. The surrogate problems are generated in such a manner
that the solution space for the original problem is subdivided into
mutually exclusive collectively exhaustive sets. The solution of
the problem representing each set is a lower bound for that set.
The optimal solution is found when the smallest of the lower bounds
for all the sets is an exact solution to the original problem.
Consider solving Problem One. The less constrained Problem Two
will be solved as a surrogate for it. A solution is generated by
the out-of-kilter algorithm and the cost and exactness of the solu-
tion to Problem One are investigated. If, for each facility the
flow through it is exactly zero or the capacity of the facility, an
exact solution to Problem One has been found as well. Since this
solution represents the only lower bound estimate of Problem One,
and it is feasible to Problem One, the optimal solution of the
original problem has been found as well. The algorithm terminates.
However, suppose that for some facility, i , the flow is greater
than zero but less than capacity. Choose this facility to branch on.
-------
- 42 -
In all feasible solutions to Problem One only two situations may
occur regarding i*. Either y^l and the i* facility exists, or
y^O and the i* facility does not exist. Construct two new
problems: Problem Two(a), (i*), is Problem Two plus the constraint
yi*=l. in order to set up this problem, the linear approximation
associated with i* -i* + V±* , is replaced by its true cost which
. ...
is a constant, F. , plus a variable cost of Vi . No change is made
in the constraint matrix since it has already been assumed that all
&
y^l in the original formulation of Problem Two. Since ?^ is a
constant, it is simply added to the cost of the solution of
it
Problem Two (a), (i ), found by solving the resulting network using
the out-of -kilter algorithm. Since Problem Two (a), (i ), is more
constrained than Problem Two, its cost must be greater than or
*
equal to the cost of Problem Two. Note that the flow through the i
facility may take on any value between zero and capacity. The
correct cost will be assigned, since the fixed charge for the
facility is included in the cost, and the variable charge is a
function of flow through the facility. Now construct Problem Two(b),
•to j.
i , which is Problem Two plus the constraint y* =0. This may be
handled in two ways. Either set the variable cost at facility i* to
infinity or set the capacity at facility i* to zero. Both proce-
dures will produce the result of blocking flow through facility i*.
The solution to the txro problems represents lower bounds of two
mutually exclusive sets of feasible solutions to the original problem.
The lower bound with the lowest objective function is examined for
-------
- 43 -
exactness to Problem One. If it is exact, it is optimal. If not,
"kit
a new variable, i , is chosen for branching, and two new problems
are set up. One problem has y^ =1, y. -I, and the other has y^ =1
1.
and y^ =0. The cost of these solutions, along with the remaining
lower bound from the first branch, are searched for a minimum once
more, and the exactness check is made. The procedure is continued
until the optimal solution is found. The procedure must terminate
since the process of adding constraints continues only until total
enumeration of all possible feasible solutions has been found.
To present the subproblem solution in a general form, define:
S = the set of all indices representing facilities
S = the set of facilities constrained to be built
(i.e. yj=l)
S° = the set of facilities constrained not to be built
(i.e. y.=0)
S_ = the set of facilities not yet constrained
Then S* = S1U S° U S
and SLr\ S°r\ S. = <£>;
that is, the sets are mutually exclusive and totally exhaustive.
Then a general subproblem may be written as:
Minimize:
m n j. a, p m ... ..
E £ cV.x. + 2 £
1-1 j-i lj 1J k-i 1-1
F / P **\
-i( I x. .1
Qilk-i%V
E 00 K I £ x7. + Z F (2-37)
i€S°
-------
- 44 -
subject to the constraints:
p (2-38)
4 Qi 1 « i U S1 (2-39)
S x* - S x* i 6 S* (2-40)
X k=l
D4ufc Z x*. >XD11 J-l, 2 n (2-41)
J i=l 1J J
xij' xt,- are non-negative integers (2-4la)
and all symbols are as previously defined.
The ease of keeping track of the various solutions in a com-
puter is aided by the use of associative lists which allow solutions
to be kept in order of increasing cost, and makes location of the
lowest cost solution relatively simple.
The choice of a variable on which to branch can make a great
deal of difference in the speed of finding the solution. The rule
used in the procedure for solving Problem One involves searching
the facilities which have flow greater than zero but less than the
capacity of the facility. Denote the fraction of flow through
facility i as f. (defined as the flow divided by the capacity).
Select for branching that facility whose value of f. is closest
to 0.5, which is the rule that Land and Doig (1960) suggest.
-------
- 45 -
E. A Detailed Algorithm for Solving the Capacitated Trans-Shipment
Facilities Location Model
1. The following data are given:
m = the number of proposed facility sites
n = the number of demand areas
p = the number of sources
For each facility site, i, the following are known:
FJ = the fixed cost of establishing the i'th facility
Vj_ = the unit variable cost of operating the
established facility
QjL = the capacity of the facility
For each demand area, j, the following are known:
D^U = the upper bound on quantity demanded at
the j'th demand area
D. = the lower bound on quantity demanded at
the j'th demand area
r.: = unit variable cost of satisfying demand at j
For each supply point, k, the following are known:
S, u = the upper bound on quantity supplied at point k
rC
S, = the lower bound on quantity supplied at point k
cC
t. = unit variable cost of providing supply from point k
*
In addition, the m x n matrix c±^, and the p x m matrix cki are
assumed known where
c.. = the unit cost of transportation from facility i
1J to demand area j
cv- - the unit cost of transportation from source k
to facility i
-------
- 46 -
2. Initialization:
Define S = the set of all indices of facilities that
have been fixed at zero or one
S_ = the set of all indices not yet set
S* = the set of all indices = (1, 2, 3, ...., m)
Then S U £ = S* S/1S.= 4> (the empty set)
Initialize S = £
S_ = S* = (1, 2, 3, , m) = all indices repre-
senting facilities
3. Construct a graph in the following manner: There will be three
sets of nodes (I, J, K) which make up the graph., plus a source
3/
node S#. The graph will be in circulation form so that the
source = sink = S#-
Define I = (set of nodes which represent the facility site
alternatives)
For each of the m sites, a capacitated node is established,
This is accomplished by representing the site as two nodes
with a directed arc joining them (see Figure 2-2). The
upper bound capacity of the arc is the capacity, Q^, of
the facility it represents. The lower bound capacity is
zero. The unit eost on the arc is Z., which will be
defined later.
Define J = (set of nodes which represent the demand areas)
Define K = (set of nodes which represent the supply points)
_
Circulation form means an arc exists from the sink back to
the source.
-------
- 47 -
Arcs connecting the nodes:
From S# to set K; Define a directed arc from S# to each
node in K. The unit cost on the arc is t^. The upper bound
on capacity of the arc is S. u and the lower bound is S, .
Assume the upper bound is equal to the lower bound.
From set K to set I; Define a directed arc from each node in
K to the receiving end of each capacitated node in I. The
*
cost of the arc is c,-, and the upper and lower bound capacity
of the arc may be set as desired. Assume the upper bound is
infinity and the lower bound is zero.
From set I to set J; Define a directed arc from the trans-
mitting end of each capacitated node in I to each node in J.
The unit cost of the arc is c,., and the upper and lower
bound capacity may be set as desired. Assume the upper bound
is infinity and the lower bound is zero,
From set J to S#: Define a directed arc from each node in J
to S#. The unit cost on the arc is r., and the upper bound
and lower bound capacities are respectively D, and D.I.
Figure 2-3 shows a graph representation for m=3, n«3, k=2.
4. Establish the unit cost, Z. for the capacitated nodes in set I.
Define y. = a decision variable
Define y. = 1 if the i'th variable is in the set S and if
1 the i'th facility is to he built
-------
- 48 -
Define y. = 0 if the i'th variable is in the set S and
1 the i'th facility is not to be built, or
if the i'th variable is in the set S_
Define Z£ = 0 if yi=l and it S
Define Z± = <*> if y±=0 and i*S
F-!
Define Z± - — if y^O and
Qi
5. Find the minimum cost maximum flow through the graph using the
out-of-kilter algorithm. Define this cost as CGRAPH. If this
is the first time through this step and the attempt to solve
the graph using the out-of-kilter method indicates no feasible
solution, no feasible solution to the problem exists. TERMINATE.
If not, continue.
6. Define the total cost of the solution, COST, as
COST = CGEAPH + I F.y-
i€S
7. Examine the solution to see if it is exact:
Define X.^ as the flow through the capacitated node
representing the i'th facility
The solution is exact if for all it S
Xt = 0 or Xi = Qt
If the solution is not exact, find the index of one of the
members of the set S for which 0 < X. < 0 . as the next
_ .,, X.^)
X
candidate for branching. Select that member for which JL is
QI
nearest to 0.5.
-------
- 49 -
8. Store information about the solution. File on a list ranked on
the cost of the solution information about the exactness, the
members of the S set and the values to which they are set, and
the next candidate for branching.
9. Remove the first problem on the list', i.e. the lowest cost
solution found so far. If the solution is exact, it is
optimal. TERMINATE.
10. If the solution is inexact, set up subproblems (a) and (b):
(lOa). For subproblem (a):
Set y.=l for the index stored as the candidate for
branching and switch that index from S_ to S
Then do steps 4 through 8 and return to do sub-
problem (b) in (lOb)
(lOb). For subproblem (b):
Set y.=0 for the same index as in (a) and switch
that index from S_ to S
Then do steps 4 through 8.
Go to step 9.
-------
ARCS FROM ALL
MEMBERS OF SET K
ARCS TO ALL
MEMBERS OF SET J
(Ql.O.Zj)
RECEIVING
NODE
SENDING
NODE
Qj sUPPER BOUND ON FLOW THROUGH FACILITY i .
Z| = UNIT COST ASSOCIATED WITH USING FACILITY i,
Ui
o
figure 2-2, A Capacitated Node Representing Flow Through Facility i.
-------
SET K
SUPPLY POINTS
CAPACITATED
NODE FOR
FIXED CHARGE VARIABLE
(Qj.O.Zj)
(CD.O.Cjj)
SET I
PROPOSED FACILITIES
SET J
DEMAND AREAS
Ul
(UPPER BOUND, LOWER BOUND, UNIT COST)
Figure 2-3. A Graph Representation for a Problem with m=2, n=3, k=2.
-------
- 52 -
F. Computational Results Using the Algorithm
The algorithm as described was coded in ASA Fortran IV and
executed on an IBM 7094 computer. The out-of-kilter algorithm used
to solve the lower bound problem at each branch was a Share Library
Distribution Program written by Clasen; the list processing sub-
routine package used in keeping track of the various solutions was
written by Bellmore (1966). In Chapter V results based on the use
of data from example problems in solid waste collection are presented.
General impressions of this type of algorithm gained by running it
with randomly generated data are as follows: The usual case for
branch and bound algorithms is that they are data dependent. The
same size problem with different data can lead to very different
running times. In the case of the algorithm tested, the problems
that ran the fastest for a given size were those where the facility
costs were sufficiently high so that only a few facilities were
built. From computational experience with such algorithms, it has
been.found that problems where the optimal solutions are to build
either a few or all of the facilities, generally run the fastest.
Problems where there is a delicate trade-off between facility and
transportation costs, so that several facilities are built, tend to
take longer to derive optimal solutions. Further, the number of
out-of-kilter problems solved in obtaining the optimal answer
definitely exhibited the value of the algorithm's restart capability.
As the number of out-of-kilter solutions increased, the time per
solution decreased.
-------
- 53 -
A possible limiting factor on the use of this algorithm is
that the amount of storage space needed within the computer for a
problem is quite large.
Let F = the number of proposed facilities
D = the number of demand areas
S = the number of supply points
Then the number of arcs and nodes in the resulting graph is:
Number of arcs = D(l + F (1 + S))
Number of nodes = D + 2F + S
The maximum size problem that could be run on the 7094 with its
32,768 word memory was 300 nodes and 1500 arcs. The number of
feasible alternatives is dependent on the number of facilities
being investigated. However, comparing two solutions with the
same number of facilities but different numbers of supply points
will show that there is a significant difference in time to. solve
the out-of-kilter algorithm due to its larger number of arcs. The
computational results are shown in Table 2-1.
-------
- 54 -
Table 2-1.
Results of Trial
F
6
12
* 10
* 10
15
30
10
20
30
+ 35
-1- 35
+ 35
50
D
12
10
30
30
20
20
20
20
25
10
10
10
10
S
2
2
3
2
3
3
3
3
2
3
3
3
3
Runs of the Algorithm with Randomly Generated Data
No. of Al-
ternatives
64
4,096
1,024
1,024
32,000
!010
1,024
io6
io10
io12
io12
io12
4 x IO15
No. of
Arcs
104
194
382
382
388
733
293
503
866
478
478
478
713
No. of
Nodes
27
35
73
53
54
84
44
64
88
84
84
84
114
No. of
OKA's**
8
8
8
8
3
15
8
6
30
30
11
6
20
7094
Time
(minutes)
0.14
0.20
0.25
0.54
0.28
1.01
0.22
0.37
1.24
1.60
0.84
0.56
1.19
* These two solutions have decreasing fixed costs (in order given).
+ These three solutions have increasing fixed costs (in order given)
** Number of times out-of-kilter algorithm applied.
-------
- 55 -
G. Augmenting the Algorithm to Consider Additional Side Conditions
There are several additional constraints that might also be
added to the problem to give more generality. Consider the following
conditions and the way the algorithm must be adjusted to allow for
their inclusion.
1. Mutual exclusivity constraints of the form of
£ y, $1 (2-42)
16 E
where E is some subset of facilities for which only one member of the
subset may be constructed. This constraint is used in the case where
the set E represents several treatment alternatives that might be
built at a possible site. Then either none or one of the possible
alternatives may be built. It might also be used as an informal
budget or political constraint. If one facility is built at one
site, another cannot be built at a different site. The way that
this is handled in the algorithm is as an additional feasibility
requirement. In order to be an exact feasible solution to Problem
One, the solution to Problem Two must not only satisfy flow through
facility constraints but the mutual exclusivity constraints as well.
If it is violated, an exact solution has not been found. A fast and
convenient way to set up a branching rule for this procedure is the
*
following: Suppose that the variable chosen for branching is i
and i*€ E. Since no other member of E may appear in a feasible solu-
tion if y£* is set to one, set y^^ = 1 and yi = 0 for all i 6 E but
not equal to i*. Switch all indices i 6 E from S_ to S.
-------
- 56 -
2. Budget constraints of the form
I aty $B (2-43)
w
where W may be a subset of the facilities or the entire set. The
mutual exclusivity constraint in (2-42) is a special case of (2-43)
(with all a. = 1, and B = 1). Each time a member of the set E is a
candidate for branching, a check is made to see if establishing that
facility will violate the budget constraint. If it will not, then
branching may proceed. If it will, the variable is only allowed in
the solution at a value y. = 0, and the search for another variable
on which to branch is carried out.
3. Upper and lower bounds on flow through a facility if it
exists. Equipment may exist for which a certain minimum use is
necessary to keep it from deteriorating. The constraint takes the
form
1 ** ** u
Qi 7i £ Z x.. £ Qi y. (2-44)
k=l K1 X
i
where Q.^ and Q.^ are respectively the lower and upper bound on the
capacity of the facility if it exists. The change in the algorithm
that will allow this condition is in step 4. When Z+, the cost of
the arc, is defined, the capacity of the arc is defined as well.
-------
- 57 -
Substitute these rules in step 4.
Z.=V. and the upper and lower bounds are Q^u and Q^
if ig S and y^l
Z^ = oO and the upper and lower bounds are zero
if i fe S and y^O
p _
Z^^jr—h V^ and the upper and lower bounds are Q^ and zero
^1 if i« S
4. Upper and lower bounds on individual arcs such as
r 1 x v £ r u f9-4S"i
ii * ii * ii
may be added without any change in the algorithm since the out-of-
kilter algorithm allows such restrictions on arcs.
-------
- 58 -
CHAPTER III. LARGE SCALE SINGLE AND MJLTICOMMODITY ROUTING IN
GIVEN NETWORKS
Introduction
In this chapter, the problem of routing a flow of commodities
from sources through intermediate points to sinks in given networks
is approached. As with the facility location problem of Chapter II,
the assumption is that the capacity of the vehicle which comprises
the means of transport is smaller than the quantity of material to
be moved, so that the small scale collection problems of routing
between sources for collection, or between sinks for distribution,
may be avoided. In the narrowest sense, finding the flow through a
given network is a simplification of the facility location problem
and may be readily solved by the use of a transportation or trans-
shipment algorithm. However, there are often additional considera-
tions that might be introduced to the problem which increase the
generality of the formulation and the difficulty of finding solu-
tions. The first such consideration is the addition of time and
capacity constraints on vehicles, tmdget constraints on certain
types of expenditures and constraints on manpower allocation. Work
in the general area has been done by Garvin et al. (1957) and Barton
(1967), and work in the specific area of solid waste collection has
been done by Wolfe and Zinn (1967) and Anderson (1968). Another
area of interest is in the use of a common vehicle fleet to carry
several distinct commodities between supply and demand points for
-------
- 59 -
the individual commodities. The work of Szwarc (1967) on multi-
commodity transportation problems has been extended in this
dissertation and will be discussed. Another area of interest is
a problem considered by Ford (1958), Bomberault and White (1968)
and White (1968) called the dynamic trans-shipment problem, in
which it is desired to route vehicles not only in a spatial sense
but in a temporal sense as well. This work finds application in
the scheduling of empty railroad cars and may have application in
solid waste collection.
-------
- 60 -
A. Literature Review
The earliest report in the literature of a vehicle routing
problem through a given network with added conditions was made by
Garvin et al. (1957) in an article showing applications of linear
programming in the oil industry. Included in the problems surveyed
was that of routing vehicles from bulk refineries to service
stations. The problem statement is as follows:
There is a given set of stations, k, each with a demand for a
product D^, and located at known distances from the bulk refinery
and from all other stations. There are several different types of
trucks available for delivering to the stations, each with a capacity
Cs, a given unit cost of operation and a given number of hours per
time period when that type of truck may be used. The problem is to
find the delivery schedule that will meet the demands for the product
at the stations within the capacity and time constraints while
minimizing the transportation costs.
For this particular problem, it is assumed that any of the
demands are greater than any of the vehicle capacities. The authors
presented a linear programming formulation as follows:
Minimize:
n n k=l, 2, , n
subject to: Z yijk = I y j-1, 2, ,...,n (3-2)
i=l u=l J but k t j
-------
- 61 -
k=sl> 2, -..., n (3-3)
n l n n
D I y - Z D (3-4)
n n
E xius j=1> 2' •••" n (3"5)
u=l JUS s=l, 2, ..... p
n p i=l, 2, ---- , n
I yik < I Csx.. j=l, 2, ..... n (3-6)
1K
..
k=i s=l J but k
n n
.f .£ hijsxijs < hs
x.. , y, are non-negative integers (3-7a)
1 1 S 1 j K,
where:
c.^a - cost per unit for shipping from i to j in vehicle type s
= the number of vehicles of type s sent from i to j
y.., = the quantity shipped from i to j with final destination k
1JK
D^ = quantity demanded at k
C = carrying capacity of s'th type vehicle
S
h^*s = time required to go from i to j in vehicle type s
h0 = time that an s type vehicle can be used
S
n = number of customers (or cities)
p = number of vehicle types
Expression (3-1) specifies the minimization of the cost of
-------
- 62 -
vehicle operation. Equations (3-2), (3-3) and (3-4) are a set of
trans-shipment constraints and exhibit an incidence matrix.
Equation (3-2) specifies that all material shipped into a node
destined for sink k must equal the amount of material shipped out
of the node destined for sink k. Equation (3-3) is a destination
constraint which sets the demand at the k'th station, and Equation
(3-4) is a source constraint specifying the amount to be shipped.
Equation (3-5) expresses a node constraint on trucks by specifying
that the number of trucks of type s that enter a station must equal
the number that leave it. Inequality (3-6) relates material trans-
shipment to the capacity available to ship it, while inequality (3-7)
specifies a time constraint on the availability of different types
of vehicles.
The authors have ignored the integer constraints (3-7a) and
solved the problem by using a linear programming code with rounding
of variables that take non-integer values. The problem very quickly
becomes unwieldy for any reasonable number of sources and sinks.
For n sinks and s different types of service vehicles there are
and
2
2n + ns constraints
3 2
n + n s variables.
A 10 sink problem has more than 200 constraints and 1100 variables.
The authors did note the network structure of part of the constraint
set and suggested that some improvement in running time might be
gained by exploiting it. So far, however, nothing further has
-------
- 63 -
appeared in the literature. The linear programming approach con-
tinues to appear as bigger, faster codes become available. Barton
(1967), in work on aircraft scheduling and routing, wrote essentially
the same formulation and used the same technique to solve it. In
this case, C.E.I.R.'s LP/90 code and an IBM 7094 allowed him to
solve a 202 row, 515 column problem in 16 minutes. The solution is
reported to have non-integer elements which are rounded to integer.
In application of models of this form to problems of solid
waste collection, the sources are the locations from which solid
waste is to be collected, the sinks are disposal points and the
intermediate points are transfer stations where some form of pro-
cessing such as incineration or compacting might take place in
addition to the transfer operation. Arcs joining these points
represent alternative routes or methods by which the material may
pass from sources to sinks. Solving the problem will show the over-
all cost of collection and which alternative routes are used to
obtain it. Some authors have looked at the problem of modeling the
overall collection system in this manner. Wolfe and Zinn (1967)
resorted to linear programming to solve the problem for a small
example problem. The model they proposed would be an ordinary trans-
shipment model which might then be solved by a primal-dual algorithm
quickly, except for problems that arise in the representation of
incinerators. Any waste flow that enters this node is decomposed
into several different forms whose amounts are given proportions of
the inflow into the node. This means that flows leaving the node
-------
- 64 -
have coefficients between zero and one and an incidence matrix no
longer exists. Since there are advantages to using a primal-dual
algorithm over a simplex algorithm, Anderson (1968) proposed an out-
of-kilter algorithm for solving this problem which allows flow from
nodes to be separated into given proportions. He showed a few
examples solved by hand and did not indicate if the algorithm had
been coded. Thus, while it would be expected that such an algorithm
would be much faster than solving the same problem by a simplex
linear programming code, there is no evidence yet to support it.
In many cases in vehicle routing, it is desired to consider
the use of a common vehicle fleet to move more than one commodity
between supply and demand points for a commodity. This is particu-
larly true in solid waste collection, since many different classes
of wastes such as residential, industrial, construction, salvageable
materials, ashes, leaves and even Christmas trees are presently
collected separately. Adding multicommodity aspects to such problem
formulations as Garvin et al. (1957) proposed for single commodity
flow may be done quite simply. Additional constraints defining the
shipment network requirements for the additional commodities and how
the commodities interact in their competition for shipment vehicles
are easily formulated and added to the problem. However, since the
formulation is already so complex that even a small problem is
unmanageable in terms of computation technique and time, the addition
of more commodities makes the formulation unworkable.
To be able to deal efficiently with a multicommodity routing
-------
- 65 -
problem it will be necessary to drop all consideration of additional
constraints such as those on time, vehicles and work rules which
obscure the simple network structure of the problem. This leads to
the formulation of multicommodity transportation or trans-shipment
problems and to solution methods which will prove faster than linear
programming using the simplex method. Szwarc (1967) formulated and
presented a solution technique for a multicommodity transportation
problem which he calls the truck assignment problem. He formulated
it in the following manner:
There exist m production sites each capable of producing p
commodities, and n demand locations where there is a demand for each
of the commodities. The demand for a commodity is such that the
entire capacity of a vehicle is allocated to only one commodity and
is destined for one demand location only. Thus the problem of
routing a vehicle between supply locations or demand locations is
avoided and a vehicle's assignment will consist of loading a commo-
dity at a production source, delivering its contents to one demand
location and returning empty to a production source for reassignment.
The objective is to find the vehicle assignments that will minimize
the total distance traveled while meeting the supply-demand constraints,
This problem, because of the requirements that a vehicle
traveling from source to sink may carry only one commodity and that
the return from the sink to the source is done empty, is a far easier,
less complicated problem than the general multicommodity flow problems
considered by Ford and Fulkerson (1958). Each arc in the traditional
multicommodity flow problem may carry many different commodities at
-------
- 66 -
the same time. But with the special formulation, each arc from a
source of a commodity to a sink of a commodity may carry only that
commodity. Thus the problem may be decomposed into a series of
simpler single commodity problems in which loaded vehicles are
shipped from sources to sinks, and empty vehicles from sinks back
to sources. Arcs representing flow between sources and sinks of
different commodities are not allowed. However, arcs from the sinks
back to the sources represent empty trucks and any source may be
reached from any sink.
Szwarc presents no mathematical formulation of the problem,
but proceeds to a solution method based on solving two separate
transportation problems for an enlarged network in which a source
of several commodities becomes a distinct source for each of the
commodities. Sinks are treated in the same manner. If there are m
production sources each supplying p commodities and n demand sites,
then he solves first an mp by np transportation problem based on
routing full trucks from sources to demand sites, with routes be-
tween supply and demand for different commodities blocked out.
Then, the problem of routing the empty vehicles back to the source
is presented as another transportation problem. A procedure is then
shown which reconciles the two solutions into a set of vehicle
assignments. A proof of optimality is included in the paper. This
is a very quick, efficient method since solution time for even large
transportation problems is quite small. A later section of this
chapter gives an extension to multicommodity trans-shipment problems
-------
- 67 -
of the type described by Szwarc with the addition of many
considerations which make the formulation more general.
Dynamic trans-shipment networks deal with the problem of the
movement of goods and vehicles from location to location over time.
Dealing with networks where there are time as well as spatial
aspects to the problem often changes the type of analysis performed.
The concern may shift from routing to finding the maximum flow
through a point that may occur in a given time sequence. The
routing of vehicles must specify not only which arcs of the network
are traveled, but in what time period as well.
The first work to appear in the literature on dynamic flow
problems was by Ford (1958) and is also reported in the textbook by
Ford and Fulkerson (1962). The problem was to find the maximum
dynamic flow through a given network where the dynamic flow at a
point is defined as the total flow that passes that point during a
specified time period. The normal concept of a capacity of an arc
in a static or time-independent problem becomes a capacity per unit
time in the dynamic problem and the cost on the arc represents the
travel time through it. Ford showed that there is a direct relation-
ship between static and dynamic problems and that the maximum flow
through the network as obtained by a trans-shipment algorithm could
be used directly to construct the solution to the dynamic problem.
Bomberault and White (1968) were interested in the problem of routing
empty shipping containers from sources where they exist to demand
for them. In this case demand exists in only specified time periods
-------
- 68 -
and there is both a travel time and a cost associated with travel
along an arc. The authors wished to apply a travel cost to transfer
between nodes as well as a time constraint and then minimize the
cost of shipping the containers to meet the temporal demand for
them. By enumerating the feasible routes that exist for a con-
tainer to reach a demand point before or as it is needed, they
construct an expanded network through which flows which minimize
transportation costs may be found by the use of a trans-shipment
algorithm, much in the spirit of the Ford and Fulkerson algorithm.
White (1969) suggested an improved algorithm for solving the empty
container problem, which involves decomposing into a nested sequence
of subproblems and uses an out-of-kilter algorithm for solution.
Applications of the work on dynamic trans-shipment networks
to problems of solid waste collection are of interest particularly
in the scheduling of large scale vehicles used for transport from
transfer sites to disposal areas. Such vehicles may be either trucks
or railroad cars, and questions such as how many of what type are
needed may be approached using this formulation.
-------
- 69 -
B. Formulation and Solution of a General Multicommodity Truck
Assignment Problem
Szwarc (1967) described a method for solving multicommodity
transportation problems which is discussed in the preceding section.
His work is limited in application because it cannot deal with trans-
shipment networks. In the paper on his method, Szwarc did not give
a mathematical formulation for the problem he was attempting to
solve. However, such a formulation gives a hint as to how it may
be extended to a far more general form, and solved optimally using
an out-of-kilter algorithm.
Consider the following definitions:
Let
x.,, = the number of vehicle loads of commodity k to be sent
^ from production source i to demand site j
x.!- = the number of empty vehicles sent from demand site j
back to production source i
c'ik = cost Per vfihicle load of shipping commodity k
from i to j
c*. = cost per vehicle of returning an empty vehicle from
demand site j to production source i
D-v = demand in vehicle loads for commodity k at demand
J site j
S , = supply in vehicle loads for commodity k at production
IrC *
source i
m = number of production sources
n = number of demand sites
p = number of commodities
-------
- 70 -
Then the general mathematical formulation for Szwarc's
delivery problem is:
Minimize:
m n p
E E E
1=1 j-1 k=]
n
subject to: E x
m
E x
1-1
m n ^ *
* * CJiXJi
j=l i=l
(3-8)
i=l, 2, m
k-1, 2, ...., p (3-9)
j=l, 2, . ..., n
k-1, 2, , p (3-10)
p m m
E E x, ., = E x . 1-1, 2 , m (3-11)
k-1 1-1 1Jk 1-1 J1
P n n
E E x. .. = E x.. 1-1, 2, , m (3-12)
ciik' x-- are non"negative integers (3-12a)
The objective function in (3-8) is to minimize the cost of
loaded trips from source to site and of empty return trips.
Inequality (3-9) requires that the amount of commodity k shipped
from source i to all sites must not exceed the supply of commodity k
at that source. Similarly, inequality (3-10) specifies that the
total amount of commodity k shipped to j from all sources must be
greater than or equal to the demand for commodity k at that site.
Equations (3-11) and (3-12) are flow equations requiring respectively
-------
- 71 -
that the number of empty vehicles sent out of a demand site must equal
the number of loaded vehicles arriving there, and that the number of
loaded vehicles sent out of a source must equal the number of empty
vehicles arriving there. Inherent in this formulation is that
vehicles must return to a source after leaving a demand site. The
integer requirement (3-12a) will be shown to be automatically satis-
fied since the problem may be set up in network form and the
solution found by finding the minimum cost-maximum flow using the
out-of-kilter algorithm. Figure 3-1 shows the graph corresponding
with this problem for the case of m=2 sources, n=2 sinks, p=2 commo-
dities.
The computational difference between the two methods is shown
by the fact that the Szwarc method requires the solution of two tacU
transportation problems and some manipulation with the solution.
For a solution by the out-of-kilter algorithm a graph of np + mp +
mpn + mn arcs and (m+n)(p+l) nodes (or, for the example case,
20 arcs and 12 nodes), must be solved, which will take longer to
compute. There are several advantages of the out-of-kilter approach
which make it a recommended procedure for general cases, however.
1. It is possible to consider any sort of routing network
with intermediate facilities. In this case, it may easily be shown
that adding intermediate node equations to the model formulation
still leaves a graph solvable by the out-of-kilter algorithm, but
not by Szwarc's algorithm. Since most vehicle routing systems, in-
cluding solid waste systems, involve the consideration of intermediate
points such an extension is of considerable analytic value.
-------
SOURCE
I
SOURCE
2
SINK
1
SINK
2
INDICATES COMMODITY
NUMBER
(UPPER BOUND, LOWER BOUND, UNIT COST)
Figure 3-1. Graph Representation of Szwarc Truck Assignment Problem with m=2, n=2 and p=2.
-------
- 73 -
2. Many additional constraints may be added that will make
the problem more realistic. First among the constraints are upper
bounds on flows along particular routes of the form
where Q is the upper bound on flow through arc x . A finite
ijk ijk
upper bound might reflect a capacity constraint on the usage of a
route.
The most general form of the truck assignment problem to be
solved using the out-of -kilter algorithm is as follows, where a is
an index relating to a set of intermediate nodes that are neither
sources nor sinks of commodities. This form may be called the multi-
commodity truck assignment problem.
mnp m f p ^ ^
Minimize: E E E b-X+ EEL biakx
iak
f n p m n
E E E b . x^Yk + E E c^x.. (3-15)
a=l j=l k=l i-1 j=l ^
m f * i=1> 2» '•' m
subject to: E x.,k + Z xiak ^ Sik k-1, 2, p (3-16)
=l J a=l
n a-1, 2 , f
V k-1, 2, ..... p (3-17)
m j=l, 2, ...., m
k=1' 2> ••••• P
-------
- 74 -
m **
Xiak
p m p f ^ m
I Z X...+ Z I xaik = E
k-1 1-1 ljk k-1 a-1 ajk i-1
, •, i
l j=l k=l a
x
i-1,
i=l,
j-1,
k-1,
i=l
2,
2,
2,
2,
2
. . . . , m
. . . . , m
. . . . , n
P
..... m
^
I Z X...+ Z I xaik = E xii (3-20)
- ljk ajk - J
Q j-1, 2, ..... n (3-22)
«-J* 2, ...., f (3-23)
k-1, 2, ---- , p
* * a»l, 2, ..... f
Xajk x< Qajk J-1, 2, ..... n (3-24)
K— I, ^, . . . . , p
j=l, 2, . . . . , n
X $ Q i-1, 2, ...., m (3-25)
, "r-f
x , x , x , x are non-negative integers (3-25a)
ijk ajk lak ji
where:
a = index relating to intermediate nodes
i = index relating to supply points
j = index relating to demand points
k = index relating to commodities
x = number of truck loads of commodity k sent directly
J from source i to demand j
-------
- 75 -
**
x. , = number of truck loads of commodity k sent from
source i to intermediate point a
*
number of truck loads of commodity k sent from
intermediate point a to demand j
x.. = number of empty trucks returned from demand j
directly to source i
b. = unit cost of supplying demand for commodity k at
1J sink j directly from source i = c. ., + t.. + r .,
ik jk
unit cost of shipping to a as an intermediate point
for commodity k from source k = ciak "*" t-t,
T*r>lr
b ., = unit cost of using a as an intermediate point for
supplying demand for k at j = c .. + u . + r.,
c.., = cost per truck load of commodity k from i
directly to j
c. , = cost per truck load of commodity k from i to a
c .1 = cost per truck load of commodity k from a to j
c-. = cost per empty truck from j to i
t.-. = cost per truck load of shipping commodity k from
source i
r., = cost per tnuck load of receiving commodity k at
demand j
u , = cost per truck load of trans-shipping commodity k
at intermediate point a
S.. = supply in truck loads of commodity k at source i
3-K.
D = demand in truck loads for commodity k at demand j
Q. = upper bound on flow of k from i to j
,1 i..
= upper bound on flow of k from i to a
f
Q ., = upper bound on flow of k from a to j
Q'-i ~ upper bound on flow of k from j to i
V = upper bound on trans-shipment of commodity k at
intermediate point a
-------
- 76 -
Inequalities (3-16), (3-17) and (3-18) express the constraints
on (respectively) the amount of each commodity shipped from i, trans-
shipped through a, and received by j. Equations (3-19), (3-20) and
(3-21) express the conservation of flow constraints that the number
of truck loads that leave a point must be equal to the number of
trucks that enter the point. Inequalities (3-22), (3-23), (3-24)
and (3-25) restrict the flow between points to be less than a bound.
The integer requirement (3-25a) is satisfied by the solution of the
problem as an out-of-kilter graph.
Table 3-1 shows some typical running times for the out-of-
kilter solution using randomly generated data.
Table 3-1. Computation Time for Solving Some Multicommodity Trans
Shipment Problems Using the Out-of-Kilter Algorithm
Number Number Number Number Number Number Execution
of of Int. of of of of Time
Sources Nodes _ Sinks Commodities Arcs Nodes (minutes)
5
10
15
7
5
3
5
4
5
3
2
4
2
3
2
3
205
285
304
288
42
59
56
59
0.04
0.08
0.08
0.08
*
Using IBM Share Code 3536 - "Out-of-Kilter or Transportation
Problem Solver" and an IBM 7094 computer.
^ftjt
Includes time to generate graph and costs.
-------
- 77 -
C. An Algorithm for Constructing a Graph to Represent the Truck
Assignment Problem
1. For each source i, a set of p+1 nodes is created and the nodes
are named y^, y.,, ...., y^, where y., represents the k'th
commodity produced at the source i, and y^ represents the
i'th source.
2. Directed arcs are drawn from y. to each of the y^. The lower
and upper bounds on capacity of the arcs are zero and S .
IK.
The unit cost is t..^.
3. For each intermediate point a, a set of capacitated p nodes
z = (a1, a , ap) is constructed. The upper and lower
SL
bounds on flow through the capacitated nodes are Vflk and zero.
The unit cost is uak,
4. For each demand j, a set of p+1 nodes is created and the nodes
are named q j, q^, , qjp, where qjk represents the k'th
commodity received at demand j, and q. represents the j'th
demand. Directed arcs are drawn from each node qjk to q . The
lower and upper bounds on each arc are zero and D.^. The unit
cost is r ....
5. Directed arcs are drawn from each node yik to each capacitated
node z , with upper and lower bounds Qi&k and zero, and unit
cost Ciak.
6. Directed arcs are drawn from each node yik to each node qjfe,
with upper and lower bounds Qijk and zero, and unit cost
-------
- 78 -
7. Directed arcs are drawn from each capacitated node z to each
3.
node q , with upper and lower bounds Q and zero, and unit
J *£ 3- J *£
cost C ., .
ajk
8. Directed arcs are drawn from each node q. to each node y. with
HJ Ji
upper and lower bounds Q.. and zero, and unit cost C...
-------
- 79 -
D. Decoding; the Out-of-Kilter Solution of the Graph to Obtain
Routings
1. No feasible solution for the graph means no feasible
solution for the problem.
2. The flow from node y. to node y.« represents the number of
truck loads of k supplied at i.
3. The flow from node y.« to z represents the number of truck
loads of k shipped from i to a.
4. The flow from node y., to q., represents the number of truck
loads of k shipped from i to j.
5. The flow from node z,, to q., represents the number of truck
a JK
loads of k shipped from a to j.
6. The flow from node q. to node y. represents the number of
empty trucks returned from j to i.
7. The cost of the solution to the graph is the cost of the
solution to the delivery problem and is optimal.
-------
- 80 -
CHAPTER IV. VEHICLE SCHEDULING FROM GIVEN LOCATIONS
Introduction
The previous chapters have been devoted to large scale "flow
of goods" problems with the routing of individual vehicles among
collection tasks neglected. This chapter will deal with the problem
of routing of individual tasks through networks for the case where
the capacity of the vehicle is such that it may service more than
one demand before returning to its terminal. The problems of col-
lecting from a demand area and delivering to it are analogous and
will be mentioned interchangeably. Such operations are the basic
service provided by a multitude of agencies in the private and public
sectors of the economy, and have attracted a great deal of analytic
attention.
Distinct areas of application and solution in vehicle
scheduling may be classified on the following criteria:
a. What is the capacity of the collection vehicle in
relation to the demands for service?
b. Is demand continuous or discrete?
c. Is the demand for service uniform or nonuniform?
d. Are there any additional constraints besides requiring
that all demand for service be satisfied by a collec-
tion vehicle that starts from and returns to a terminal?
The first main division may be made on the relationship between
the capacity of the collection vehicle and the size of the demand for
-------
- 81 -
collection services. In this chapter, it is assumed that the service
vehicle capacity is greater than an individual service demand. If
it is also greater than the sum of all demand, the vehicle may visit
all demand locations before returning to its terminal. These
problems are referred to as single route problems, since only one
route need be fashioned. If the sum of demand is such that the
collection vehicle must return to its terminal before collection is
completed, and then return to service additional tasks, the problem
becomes a multi-route problem.
Referring to demand as discrete or continuous is done within
the context of a network framework. Discrete demand implies demand
located at the nodes of a network with travel between the nodes
taking place along arcs. Continuous demand implies that demand is
spread along the arcs of the network and is satisfied for any arc
by having the collection vehicle move along that arc. An example
of a discrete case might be routing problems for the delivery of
petroleum products to gas stations, while the continuous case is
illustrated by snow removal on streets or the delivery of mail.
Uniform demand means that the demand for service at any point is
the same as any other point such as would occur in snowplowing or
with reasonable accuracy in residential solid waste collection. Non-
uniform demand could be exemplified by the service stations, each of
which could require different quantities of product.
Turning to classifications of problems, discrete, uniform
problems fall into an area of scheduling theory known as traveling
-------
- 82 -
salesman problems, and research on these problems has been widespread.
In the traveling salesman problem, a route or schedule must be made
up which includes all demand locations once and returns to the start-
ing point while minimizing the distance traveled. The term
traveling salesman problem is generally applied only to the single
route problem, while multi-route problems are called m salesman
traveling salesman problems, where m is the number of routes to be
fashioned. Since demand is uniform, a knowledge of the capacity of
the salesman or service vehicle and the number of demand points to
be visited, uniquely determines the number of routes.
If the demand is discrete but nonuniform, the single route
problem may still be approached as a traveling salesman problem. The
multi-route problem, however, becomes more complex since the number
of routes to be fashioned depends on how the various demands may be
agglomerated into individual route assignments. Dividing the total
demand by the capacity of the vehicle gives only a lower bound on the
number of routes since it may be necessary because of the different
size of demand to return to the terminal with a less than full load.
This problem has been discussed in the literature in detail under
many different problem names, such as the delivery problem, the
cloverleaf problem, the farmer's daughter problem, the vehicle
scheduling problem, the truck dispatching problem and the truck
routing problem. All describe roughly the same problem, and since
most recent work refers to the truck dispatching problem, this term
will be used as a general problem reference. Some authors have
-------
- 83 -
extended this problem to consider not only that all demands must be
served, but that each demand must be serviced within a particular
time period or in a certain order. With the addition of such con-
straints, the single route problem as well as the multi-route
problems may no longer be approached directly as traveling salesman
problems. Most of the work done for the case without additional
constraints is adaptable with modification to this more difficult
problem.
If the nature of the demand is uniform and continuous, some
interesting techniques from graph theory may be brought to bear.
For single route problems, the Chinese postman problem describes the
problem of traveling all arcs of a network at least once in a con-
tinuous tour and minimizing the total distance traveled. The problem
is made more difficult if some of the arcs in the network are directed
(one-way) rather than nondirected (two-way). No evidence of work on
multi-route problems in this area has been found, although it would
appear to have great application for many municipal services.
Turning to the solid waste collection problem, it is obvious
that because of the size and complexity of demand it is necessary to
deal with multi-route problems. Arguments may be made as to whether
additional constraints are applicable. In the next section, a
literature search of work done in all these areas is presented to
give a feeling for the state of the art to this time. Original work
by the author of this dissertation on some problem areas in m sales-
man problems is also presented.
-------
- 84 -
A. Literature Review
1. The Traveling Salesman Problem. This is the name given
to the following problem: A salesman is to visit a group of N cities
and the distances from each city to every other city are known. Find
the tour that the salesman should follow that will allow him to visit
all the cities and return to his starting point while minimizing the
total distance traveled.
Implicit in the problem formulation is the assumption that
this is a single route problem. This means that the capacity of the
salesman in terms of the number of cities he may visit without re-
turning to the starting point is greater than, or equal to N. If
this is not true, the problem becomes a multi-route problem and is
called the m salesman problem which is defined in the following
manner: A terminal from which a salesman starts and finishes his
tours, and a group of N cities with known intercity distances are
given. Assume that the salesman can only visit k cities (k less than
N) at one time before he must return to the terminal. Find the m
tours that the salesman must make so that he may visit all the cities
and minimize the distance traveled. Each tour must be of exactly
length k plus the terminal, so m is uniquely determined as N divided
by k. If the result of the division is non-integer; dummy cities
must be added or real cities dropped in order to make m integer.
By assuming that the salesman must visit exactly k cities on
each tour, all considerations of the demand at that city have been
-------
- 85 -
taken care of and the possibility of making more than m tours by
visiting less than k cities on a tour has been ignored.
The literature is full of research on the traveling salesman
problem because it contains the elements of so many scheduling
problems in such diverse areas as job shop scheduling, aircraft
routing, vehicle routing and production planning, but little has
been written about the m salesman problem. Since most solid waste
collection problems are multi-route problems, particular attention
will be paid in this section to those authors' work on the traveling
salesman problem that might be extended to the m salesman problem.
The traveling salesman problem, while being rather simple to
formulate, has been quite difficult to solve. This is because of
the large number of feasible solutions that exist for even a moderate
sized problem. Consider a 20-city traveling salesman problem. For
I/
a nonsymmetric distance matrix there are 19 factorial possible
ways that the 20 cities may be ordered on the route. This means
that there are 1.2165 x 10 possible feasible solutions, which can
be appreciated as being a very large number by noting that if one
were able, on a computer to enumerate one million of these solutions
per minute, it would take over 27,500 years to search all feasible
solutions. Thus attention has turned towards analytic methods for
finding solutions to the problem. A definitive and complete review
of the theoretical development and computational experience with
In a nonsymmetric distance matrix, the distance from city i to city
j is not necessarily the same as the distance from city j to city i.
-------
- 86 -
the traveling salesman problem was presented by Bellmore and
Nemhauser (1968). They included a complete bibliography and dis-
cussion of the literature devoted to the subject. Those interested
in following the development of the traveling salesman problem in
greater detail are directed to that article. In discussing different
approaches to the problem, Bellmore and Nemhauser distinguished
between three basic procedures. These are tour to tour improvement,
tour building, and subtour elimination. So far, all tour to tour
y
improvement methods are heuristics in which rearrangements of the
ordering of cities on the tour are made until the analyst is satis-
fied that the ordering obtained is a good solution. At all times
the tour under consideration is feasible in that each city appears
only once. Switches in ordering of cities that will improve the
tour are made, and termination occurs when it appears that enough
time has been spent searching or no other improvement seems apparent.
Of course, such methods do not guarantee optimal results, but they
do have the feature of being quite fast.
Tour building involves choosing a starting city and then
electing which city to visit next. The procedure terminates when a
tour returning to the original city and including all others has
2f
— In discussing these methods, the terms heuristic solution and
optimal solution will be used. A heuristic solution is one that
is feasible and that is found by using a set of rules that insure
that it is a "good" solution but there is no assurance that the
solution found is the best, or optimal. Optimal solution implies
that the procedure, if followed to completion, guarantees that
the answer found is a best solution.
-------
- 87 -
been generated. An example of a heuristic method using this tech-
nique is the nearest city rule, which uses as a criterion for
selecting the next city to be visited, the unvisited city which is
closest. Tour building has also been used in optimal procedures,
such as one developed by Little, Murty, Sweeny and Karel (1963). Of
particular interest is a technique developed by Pierce and Hatfield
(1966) to deal with a production sequencing problem which has additio-
nal constraints dealing with job deadlines. The algorithm is based
on solving the traveling salesman problem using a tour building
optimization technique. Reference is made later in this literature
review to extensions of Pierce's work to single and multi-route
truck dispatching problems. Held and Karp (1962) developed a
dynamic programming algorithm for the optimal solution of the
traveling salesman problem that is limited to about 15 cities by
storage requirements on present day computers. Some aspects of
Held and Karp's tour building scheme are also applicable to tour
building for the m salesman problem but the matter has not been
pursued in great detail. Such tour building techniques also always
work with feasible solutions. This is not true for subtour elimina-
tion methods, where a less constrained problem is solved which may
or may not give feasible solutions. If the solution to the traveling
salesman problem is feasible, it is also optimal. However, it may
be infeasible in the sense that all cities are visited but several
disconnected subtours, instead of one tour, are found. The solution
is then sought by adding constraints to force the elimination of
subtours.
-------
- 88 -
A later section of this dissertation presents a subtour
elimination scheme for approaching optimal solution of the m
salesman problem.
2. Single and Multi-Route Truck Dispatching Problems. As noted in
the preceding section, the problem to be dealt with here has been
at various times referred to as the truck dispatching problem, the
vehicle scheduling problem, the delivery problem, the cloverleaf
problem, the farmer's daughter problem and the truck routing problem.
Briefly, it deals with the scheduling of vehicles of a given capacity
among discrete, nonuniform demands for the services afforded by the
vehicles. Since demand is nonuniform, the number of routes to be
fashioned is one of the unknowns. In addition to constraints that
demand for service must be met, additional constraints on optional
deliveries, earliest and latest arrival times and vehicle types
are also added by some authors.
The earliest description of the problem occurs in a paper by
Garvrn et al. (1957). In an article on operations research in
various aspects of the oil refinery industry, the authors touched on
the large scale problems discussed in Chapter III, and also mentioned
the problem of routing of individual vehicles. Motivated by the
similarity between the vehicle scheduling problem and the traveling
salesman problem, they named the problem the farmer's daughter
problem, since the salesman visited certain nodes more than once and
that presumably was where the daughter was. No attempt at formula-
tion or solution was reported.
-------
- 89 -
Dantzig and Ramser (1959) discussed a problem they called the
truck dispatching problem. The problem they defined is as follows:
Given N points or cities each with a demand for deliveries of q.,
and a terminal point that does not have a demand. Let C = the
capacity of the vehicle, and in this problem
N
max q^^ < C < I q.
i=l
Further, a distance matrix D=d.. which shows the distance from any
city i, or the terminal to any city, is known. The matrix is sym-
metric (i.e., d. .=6.^). Find the routing for the vehicle that will
satisfy the demand for deliveries and the capacity constraint on
the vehicle while minimizing the distance traveled.
The authors were unable to provide a model formulation that
would solve the problem optimally, but presented an interesting
heuristic which forms the basis for solution of large scale truck
dispatching problems to this day. This is done by investigating the
problem where it is desired to aggregate the various demands into
pairs. This means that for every city i, the vehicle must make
either the trip from the terminal to the city or the return trip
from the city to the terminal. Since the distance matrix is symmetric,
the distance traveled by the vehicle between the terminal p, and the
cities is a constant found by calculating
N
tii dfi1'
The problem of minimizing the total distance traveled then reduces
-------
-go-
to the problem of minimizing only the distance traveled between
cities. This may be thought of as finding the pairing of cities
that minimizes the distance between cities of each pair.
Define x.. = 1 if city i and city j are paired
= 0 otherwise
Then by solving
N N
Minimize £ £ d.-.x.. (4-
N
subject to: £ x. . = 1 j=l, 2 ...... N (4-2)
i-1, 2, ---- , N
Xji j-1, 2, ..... N (4-3)
x.. = (0, 1) i-1, 2, ---- , N (4-3a)
1J j=l, 2, ...., N
The set of resulting x.. variables gives the desired pairs and con-
sequently the routing for the two city problem. In order to conserve
time to solve the integer programming problem, the authors suggested
solving the problem with constraint (4-3a) replaced by 0^ x. . £ 1,
which may yield fractional solutions in some cases. In that case the
solution is rounded to an integer solution. The problem has been
called the matching problem, and may be solved optimally very quickly,
using an algorithm by Edmonds (1965). The authors' solution for
larger problems is to consider the pairs formed at this iteration as
a single point for the next iteration. In this manner routes are
built up until the capacity of the vehicle is met. At each stage
-------
- 91 -
the authors used a simple exchange technique to switch pairings if
any improvement might be found. However, once two cities have been
paired at one stage of aggregation, they will never be separated at
a future level of investigation. The authors noted that the method
is heuristic, and presented computational experience for a 12 city
problem for which the method does not find what they suspected to
be the optimal solution.
Clarke and Wright (1964) presented a heuristic method based
on Dantzig and Ramser's technique, but one which will allow vehicles
with different capacities. Their method varies in the means for
agglomerating the subparts of the problem and in the means for
searching for possible switches at each level. Using the procedure
they developed, they found a better feasible solution to the Dantzig
and Ramser trial problem but could not prove that it is optimal.
Their work serves as the basis for the main computerized vehicle
scheduling package available from IBM as a software service to its
users. This package, "System/360 Vehicle Scheduling Program", Anon.
(1968), available for running on the IBM series 360 computers has
two main parts, a network analysis section and a schedule producing
section. The network analysis is designed to find travel distance
and travel times between potential delivery points and to do some
preliminary sorting to eliminate obviously dominated schedules.
Input data may be in the form of coordinates or distances and the
location of barriers and congested areas may be specified as well.
The algorithm used for finding shortest paths through the network is
-------
- 92 -
Mills' (1966) work in the decomposition properties of shortest paths
problems in large networks. The scheduling procedure has additional
heuristics to allow the inclusion of constraints on such factors as
priority ratings, earliest and latest possible starting times,
several commodities carried by one vehicle and different vehicle
capacities. To date this program is the best large scale analytical
tool available for analysis of vehicle scheduling problems.
Balinski and Quandt (1964) presented a formulation for a
problem they called the delivery problem, which may be used to solve
small multi-route truck dispatching problems. They formulated the
problem as a set covering problem which requires that feasible
single vehicle schedules be enumerated and then chooses from among
these schedules an optimal set meeting the requirement that all
demands be satisfied. For a large problem, this would require that
a great many schedules be generated first before the optimization
technique could be applied. However, if some intuition is available
or the problem is highly constrained so that the number of feasible
routes may be reduced, the method offers some appeal. The problem
statement is as follows:
n
Minimize: £ c.x^ (4-4)
j-1 J
n
subject to the constraints: I A.x. = E (4-5)
x- = (0, 1) (4-5a)
-------
- 93 -
where Aj is an m by 1 column vector representing the j'th feasible
vehicle route, and whose elements
a^j = 1 if the i'th city is visited on the j'th route
= 0 otherwise,
and
c. = cost of the j'th feasible route
X.. = 1 if the j'th route is used
= 0 otherwise
E = an m by 1 column vector of 1's
n = number of feasible routes
m = number of cities to be visited-
Each feasible route is represented as a column vector with a one in
the i'th position of the vector if the route visits the i'th city
and a zero if it does not. It is desired to find the set of x.'s
that minimize cost and satisfy the requirement that each city be
visited exactly once. Running the problem as a linear programming
problem without integer constraints on the variables does not
usually yield integer solutions. The authors suggested obtaining a
solution using an integer programming cutting plane algorithm. They
report computational experience with a problem of 15 cities and 388
feasible routes. The feasible routes were examined for dominance
and reduced to 270. Optimal solution was obtained in 23 iterations,
but a similar problem ran 200 iterations without solution.
—'One route dominates another if both deliver to the same cities
and one has a lower cost than the other.
-------
- 94 -
The idea of using a two phase algorithm in which the first
phase involves generating a set of feasible solutions and the second
phase is used to select from among that set the optimal routing is
quite intriguing. Some form of branch and bound or selective search
of the feasible solutions will allow the discarding of many dominated
feasible solutions before the second phase begins. As constraints
on the charcter of the routes become more demanding, the process of
searching for feasible routes in phase one may even be speeded up,
since many branches may be terminated early and fewer feasible solu-
tions become candidates for phase two. What is needed is a better
algorithm for solving the set covering problems of phase two, rather
than cutting plane algorithms, and the work of Pierce provides a
substantial step in this direction.
Pierce has written on several aspects of scheduling and truck
dispatching, as well as on the development of combinatorial program-
ming algorithms for solving set covering problems. As noted earlier,
Pierce and Hatfield (1966) made use of a traveling salesman problem
to look at production problems with additional time constraints.
This led to Pierce's (1967) major work on truck dispatching. In the
first part of this work the main concern is with single route problems
with additional constraints that include earliest and latest arrival
times at a specific point, optional deliveries, split deliveries and
constraints on the service vehicles such as volume limit, maximum
number of stops and maximum time per trip. The solution methods
suggested by Pierce do not use a set covering approach but are
-------
- 95 -
branch and bound tour building techniques. The basic element on
which branching takes place is whether or not a particular arc
leading from one demand to another is used in the solution, and
lower bound estimates are found using an assignment procedure
similar to that of Little et al. (1963). Two ways for searching
the branches are suggested. One is "flooding", in which many
branches are started at once, and the choice of which branch to
investigate next depends on which seems the most promising at that
time. The other is to follow one branch to completion (i.e.,
either infeasibility, a new feasible solution, or dominance by an
existing feasible solution). Then backtracking may take place up
the branch until it is exhausted and another branch is started.
Since the problem is characterized by extremely long computation
time to find and verify optimal solutions, Pierce was more interested
in the techniques that generate feasible solutions early so that the
procedure may be terminated and the best feasible solution used as a
heuristic. For this purpose, he feels that on the average the
second technique will yield feasible solutions sooner.
In a later paper (Pierce, 1968) the author developed a
combinatorial algorithm for solving general set covering problems
and chose as his trial problems a set of truck dispatching problems.
Computational results based on using the algorithm for different
size problems are shown in Table 4-1.
Pierce also found that in dealing with the largest of his
examples, problem 13, the first feasible solution was reached in
-------
- 96 -
Table 4-1. Computational Experience on Truck Dispatching Problems
of Various Sizes Reported by Pierce (1968)
Problem Problem
No. Size
(m*n)*
1 5 x
2 6 x
3 8 x
4 13 x
5 11 x
6 11 x
7 11 x
8 11 x
9 12 x
10 12 x
11 12 x
12 15 x
13 19 x
31
62
92
91
231
561
1023
1485
298
538
793
575
1159
Solution Time in Seconds*** for Different
Forms of the Algorithm
Alg 1
0.
0.
0.
35.
9.
12.
27.
34.
89.
131.
77.
600.
--
050
167
567
167
183
917
267
950
133
033
767
000**
-
Alg 2
0.
0.
0.
6.
1.
2.
14.
19.
3.
7.
4.
69.
2400.
050
117
200
367
383
867
383
317
500
117
567
483
000**
IPM2
1.867
0.367
2.067
4.933
m - number of cities, n = number of feasible routes
Termination without proving optimality
**
***.
Using the IBM 7094
-------
- 97 -
5.617 seconds, and the best feasible solution at termination had
been found quite early (in 349.767 seconds). In a new work on
improvements to the combinatorial algorithm, for which only an
abstract has been circulated, Pierce and Lasky (1969) indicate that
they have found an optimal solution to problem 13 in one-half
minute. This is a considerable time saving, and makes an optimal
procedure quite competitive with the heuristic solutions for
moderate size problems for the first time.
Pierce (1969) is continuing work on solving multi-route
problems both by tour building branch and bound algorithms, and by
two phase, set covering methods. Garfinkel and Nemhauser (1969)
have worked on a problem of political redistricting using a two
phase, set covering approach as well.
Andrew and Hamann (1967) also suggested a tour generating
branch and bound technique. Their work is based on the work of
Little et al. (1963), and they branch on whether a particular arc is
included or excluded from the tour. A single source for starting
the vehicles, unequal demands at cities, and route capacities (i.e.,
vehicle capacities) that do not have to be equal, are features of
the model formulation. A bound on each branch is computed by
searching the remainder of the possible arcs which have not yet been
branched upon. If a route exists which is below capacity but to
which no additional load may be added, a branch must be put in back
to the starting point. If some branches exist that could possibly
put a route over capacity, they are eliminated as well. Then a
-------
- 98 -
lower bound may be estimated by using an assignment procedure which
makes branch assignments based on minimum cost, but may produce
subtours.
The authors reported a great deal of difficulty in conver-
gence to optimality. They attempted to solve Dantzig and Ramser's
trial problem and found the same solution as Clarke and Wright did
after 560 iterations, but could not show that it was optimal. They
terminated after 47,000 iterations without having finished the
total implicit enumeration. At 14 seconds per thousand iterations,
over 10 minutes were spent without having proved optimality on a
12 city problem. Since a very good solution was developed early,
the authors suggested that the procedure be terminated early and
the best solution found be used as a heuristic solution.
Hausman and Gilmour (1967) dealt with a complicated heuristic
based on solving a traveling salesman problem. They considered a
single source and multi-period demands. Their formulation is as
follows:
n m
j max f V
(l*8J J
Minimize E Ci E Z + C2D. xj max f.,.7 (4-6)
where
DJ = min £ E Wikdik (4-7)
Wik its. kts.
subject to: Z . = 1 j=l, 2, ...., n (4-8)
n
E Z.. - 1 i-1, 2, , m (4-9)
-------
- 99 -
m
E wik = 1 k=l, 2, ...., m (4-10)
m
Wok = n
m
E Wi0 = n (4-12)
Wu = 0 i=i, 2, ...., m (4-13)
Zij' Wij integers; Z..., Wik >x 0 (4-13a)
?• ng 1 all s, all j (tour requirements)
nC s ge- j (4-14)
where: S. = set of all customers in group j
s = any subset of S.; s=S.-s
i = a customer; 0 is the terminal
f. = frequency of delivery required by customer i
d., = distance from customer i to customer k
IrC
j = a group of customers, or route; j=l, 2, ....,
n = number of groups (a decision variable)
Ci = cost per customer delivery
C = cost per mile of truck travel
Z.. = 1, if customer i assigned to group j
= 0, if not
m = number of customers
-------
- 100 -
W-k = 1, if truck travels directly from customer i
to customer k
= 0, if not
D. = optimal (minimum) distance to serve group j.
The problem requires in Equation (4-7) that for each group of
customers considered the minimum cost route for a vehicle be found.
This is done using the traveling salesman algorithm developed by
Held and Karp (1962). For the formulation only the cost of the
traveling salesman solution and not the actual routing is required,
and the Held and Karp algorithm can produce the cost of the route
quickly even though finding the route itself takes longer.
Equations (4-8) and (4-9) require that all customers be assigned to
a group and the terminal be assigned to all groups. Equations (4-10)
and (4-11) state that a customer may be visited from only one other
customer, and the vehicle leaving it may go to only one other
customer. Sending a vehicle back to one self is prohibited in (4-13)
and the assignment of flow from and to the terminal must be equal to
the number of groups (4-12) and (4-11). Inequality (4-14) is a tour
requirement that states that for any partition of the customers,
there must be at least one trip of the vehicle between the two sets.
This requirement is also used in some traveling salesman problems
to restrict subtours. For an N city problem there must be 2^-1 such
constraints.
To solve the problem the authors generated possible groupings
of the customers, calculated the value of D^ for each group j using
-------
- 101 -
the Held and Karp procedure, and evaluated the solution. Then some
of the groups were shifted and a new solution found. The algorithm
may be terminated at any point and is obviously heuristic. Computa-
tional time for a 120 customer (city), fifteen group (route) problem
was reported to be 30 minutes on a Control Data Corporation 1604,
and there is no way of measuring how good the solution is.
Hayes (1967) took a different tack in developing a tour to
tour improvement heuristic method where the assignments are generated
randomly from a weighted probability distribution. The weighting for
each demand location is based on its demand for service, its distance
from the terminal and from other demands and a random element.
These weightings are then used in grouping customers on routes, and
heuristic traveling salesman procedure is used to order the demand
in each group. The author suggested that since the above procedure
takes very little time it might be repeated for a great number of
trials and the best solution kept. He found the conjectured optimum
solution of the Dantzig and Ramser 12 city problem in 14 out of 40
runs of the algorithm (35 percent of the time).
The only attempts found for an analytical approach to the
routing of solid waste collection vehicles were by Coyle (1967) and
Coyle and Martin (1967). They developed a heuristic method for
looking at the overall collection frequency selection and assignment
of collection areas to crews for given manpower and vehicle alloca-
tions. The routing procedure is based on dividing a city into small
areas, and then agglomerating them into collection assignments based
-------
- 102 -
not directly on the distance between them, but on some indirect
measure of the compactness of the area. A final collection area
assignment for a crew per work period does not specify an order in
which it is to be done. The method used for grouping the small
areas into work assignments is Hess and Weaver's (1965) work on
political redistricting which is itself a heuristic. The authors
used this technique to generate several feasible solutions and then
looked for local improvements by switching some assignments. They
have dealt with a fairly large case of an English city of 150,000
population and showed a $25,000 per year decrease in collection
costs for the solution generated over the present method of
collection.
3. A Note About the Truck Dispatching Problem. All of the authors
who have written about the problem to date characterize it as an
easy problem to formulate and a difficult one to solve optimally.
For this reason, many heuristics have been developed, some of which
are based on optimization techniques and some of which are not.
Spitzer (1969) in an article directed towards the practitioners in
scheduling, raised the question of using heuristics to find workable
solutions versus the use of optimization techniques to find optimal
answers. He pointed out that real world problems may often have
advantages over theoretical problems in that they may naturally lead
to some form of partitioning or decomposition. While the first
thing taught in a basic systems course is that the best solution for
-------
- 103 -
a subsystem is not necessarily the best solution for the system as
a whole, such approximations might be made along geographic lines.
Due to the exponential increase in computation time as the number
of cities increase, it is much easier to analyze three 10 city
problems than one 30 city problem. Hayes (1967) suggested that the
best use of optimization techniques may be to test the heuristics.
To this date, little has been done to show how far off a feasible
solution generated by a knowledgeable operator of a complex vehicle
system is from the optimal solution. Pierce (1967) and Andrew and
Hamann (1967) both suggested that the branch and bound routines they
have devised to find optimal solutions are so slow that they should
be used as heuristics by stopping the procedure at some specified
time and using the best feasible solution to date.
4. The Chinese Postman Problem. Turning now to the problems of
finding routes for vehicles in networks where demand for service is
uniform and continuous along every arc in the network, some early
work in graph theory paves the way for some interesting analytical
approaches. In 1763, the famous Euler was given the problem of
routing a parade through streets of his native city of Konigsberg
so that it would cross all seven bridges in the city only once.
Investigating the problem, Euler found that because of the configu-
ration of the street network and the location of the bridges, the
task was impossible, and in the process postulated some general
rules about finding routes that must cover all arcs of a network.
An euler tour is defined as a tour that is continuous, covers every
-------
- 104 -
arc in a network exactly once and returns to the starting point. In
4/
an undirected network, simple rules exist for checking to see if an
euler tour exists or not. A node is even if the number of arcs that
touch it is even. An euler tour exists if all of the nodes are even.
If some of the nodes are odd then some arcs will have to be traced
more than once. In a directed network where all the arcs may have
travel limited to only one direction, similarly an euler tour exists
if every node is pseudo-symmetric, or the number of arcs directed
towards the node is equal to the number of arcs directed away from
it. Rules for establishing an euler tour as well as more detailed
description of the graph theory involved in the process, are found
in the textbook by Berge (1966).
Finding the optimal route to be taken when an euler tour does
not exist is called the Chinese postman problem. In this problem, a
route is to be found that minimizes the distance traveled on an arc
more than once. Investigators such as Glover (1967) and Edmonds
(1965.) have both suggested optimal algorithms that have been
successful. Work by Edmonds" associates at the National Bureau of
Standards (Santone, 1968), has been proposed for a case of solid
waste truck routing in Columbus, Ohio, but the actual work has not
yet been carried out.
i.e., a network where travel may be in either direction along an
arc.
-------
- 105 -
B- An Optimal Solution Method for the m-Salesman Traveling
Salesman Problem
An algorithm for the solution of the m salesman traveling
salesman problem under some special conditions is presented in this
section. The problem to be solved is the following:
Define:
N = the number of cities to be visited
excluding the terminals
s = the number of terminals for salesmen
k = the number of cities a salesman may visit
excluding the terminals before returning
to a terminal
m = the number of salesmen leaving and entering
each terminal (the number of tours to be
established from each terminal)
Given, N cities each with the same demand for services. The
maximum number of cities which a salesman may visit is k. There
are s terminals from which salesmen may begin their tours, visit
exactly k cities and return to a terminal which need not be the one
from which the salesman started. Each city is to be visited only
once. Find the route for each salesman that satisfies all of the
above constraints and minimizes the total distance traveled by all
the salesmen.
To eliminate some of the computational problems it is assumed
that each salesman visits exactly k cities. Thus smk=N, which
implies that once s, N and k are known, and N/(k*s) is integer,
-------
- 106 -
then m is uniquely determined. If N/(kxs) is not an integer,
adjustments such as adding dummy cities or subtracting real cities
are made.
In the context of the solid waste collection, this problem
represents the routing of solid waste collection vehicles from
transfer stations through their individual collection tasks. The
traveling salesmen are solid waste collection vehicles, the
terminals are transfer stations and the cities are small collection
areas, each of which generates the same amount of solid waste per
time period. The assumption that a vehicle leaves a terminal and
does not return until it has visited exactly k cities closely
resembles the actual work rules of collection vehicles within a
city. Lacking any means of monitoring actual load on the vehicle
during the collection process, the driver is usually given his route
assignment and then learns by trial and error at which points col-
lection should be stopped in order to dump the material. Usually a
day's work assignment will consist of several collection routes so
that the assumption that a vehicle does not necessarily return to
the transfer station from which the route started is not inconvenient
as long as the last collection route of the day puts the crew back
at the place from which they started in the morning, in order to
pick up their belongings and transportation home. The assumption
that a truck may visit exactly k cities or collection areas implies
that each collection area contributes 1/k truck loads. In turn,
this load must be characterized as a load at a discrete point when
-------
- 107 -
in fact it is fairly uniformly spread along the street network to be
followed in the collection task. This discrete assumption is less
real than a continuous assumption. As noted in the literature
survey, continuous problems are Chinese postman problems and no
results are known for multi-route Chinese postman problems.
An important feature of the formulation of the above problem
is that it will allow more than one terminal from which salesmen
may leave and return. This situation is common to many routing
problems including solid waste collection. The work of some authors
in set covering solutions to truck dispatching problems, particularly
Balinski and Quandt (1964) and Pierce (1967) might also be readily
expanded to consider the multi-terminal case. In their work, a two
phase procedure is necessary, with the first phase used for genera-
ting feasible routes, and the second phase used for solving the set
covering problem necessary to choose the best set of the generated
feasible routes. Phase one could be adjusted to allow the generation
of routes from multiple terminals and the procedure used to solve
the set covering problem in phase two, slightly modified so that
multi-terminal requirements might be met as well.
-------
- 108 -
C. A Sketch of the Algorithm for the Solution of the m-Salesman
Traveling Salesman Problem
As described in the preceding section the problem for which
a solution technique is desired is that of finding routes visiting
exactly k cities for each of m salesmen operating from each of s
terminals that will visit N cities exactly once and minimize the
total distance traveled. A mathematical programming formulation of
the above problem would indeed be cumbersome with respect to number
of variables and constraints necessary to describe even a small
problem. However, the mathematical formulation of a simpler problem
which considers all the constraints except that on the number of
cities each salesman must vilsit, is capable of fairly straight-
forward exposition. Consider the following:
Problem B.
Minimize f..Xij + (d^ + d*^**) (4.15)
subject to:
N
y * **
xct = xtc t=1» 2> ••••» s (4-16)
C=l C=l
N N
(4-17)
N
xij • 1 J-l, 2, ..... N (4-18)
-------
where
c=l
- 109 -
**
xtc = m c=1' 2> ..... s (4-19)
* **
xct' xtc' xii are non-negative integers (4-19a)
x.jj = the number of salesmen who travel from city i
to city j
*
x = the number of salesmen who travel from city c
to terminal t
**
xfcc = the number of salesmen who travel from
terminal t to city c
fis = distance from city i to city j (d.. =oO)
dc. = distance from city c to terminal t
dtc = distance from terminal t to city c
m = number of salesmen dispatched from each terminal
N = number of cities
s = number of terminals
Expression (4-15) is the objective function which is the
minimization of the distance traveled by the salesmen. Equations
(4-16) and (4-17) express continuity of flow requirements for each
terminal and for each city, respectively. They require that the
number of salesmen entering a terminal or city must equal the number
leaving it. In Equation (4-18) the requirement that exactly one
salesman must visit each city is expressed, while in Equation (4-19)
m salesmen must visit each terminal.
No explicit constraint has been written on the number of
-------
- 110 -
cities a salesman must visit before returning to a terminal. Denote
as Problem A, the form of Problem B with the added constraint on the
number of cities a salesman must visit. If Problem B is solved and
the solution is a feasible solution for Problem A as well, then an
optimal solution has been found for Problem A. If not, a branch
and bound scheme based on solution of Problem B with added
constraints will be used to find Problem A.
The constraint set of Problem B has an incidence matrix with
a plus one and a minus one in each column, thus indicating it is a
network problem. This insures that solutions will be integer and
that some form of network algorithm may be used to find solutions
in a smaller amount of time than a simplex linear programming
approach. The graph is in circulation form, which means that there
is continuous flow in the graph from sources to sinks and then back
through directed arcs to the sources. The method of solution will
be the out-of-kilter algorithm, but in order to use it some changes
in the form of the problem will be made. Equations (4-18) and (4-19)
express the requirements that flows through nodes representing
cities must be exactly one, and through nodes representing terminals
exactly m. This may be accomplished in a graph by the use of a
capacitated node, as described in Chapter II.
Each city is represented by a capacitated node with the upper
bound U£, equal to the lower bound 1^, equal to one. Entering the
receptor of the capacitated node are two sets of arcs: set A.
represents arcs from other cities to i, and set A represents arcs
-------
- Ill -
•^ i
from the terminals to i. Note that k^ O A.^ = £, the empty set.
Leaving the transmitter node of the capacitated node are arcs which
also comprise two sets: B. is the set of arcs which go to other
*
cities from i, and B^ is the set of arcs that return to the termi-
* ,
nals from i. B^ r\ B. = (p .
In a similar manner the terminals may be represented by a
capacitated node with upper bound equal to lower bound equal to the
number of salesmen who must enter and leave a terminal m. The
receptor of the capacitated node receives arcs from all cities and
the transmitter sends arcs to all cities.
Consider the following sets of arcs:
P = (the set of arcs that makes up the capacitated
nodes representing cities)
T = (the set of arcs that makes up the capacitated
nodes representing terminals)
Then the problem may be shown in simple circulation form as:
P
Minimize I CX
subject to: I X± = Z Xj k-1, 2, ---- , a (4-20)
i/PUT (4-21)
Xi = 1 i 6 P (4-22)
Xi = m i t T (4-23)
X.- = non-negative integer (4-23a)
-------
- 112 -
where X^ = flow in arc i
p = number of arcs
a = number of nodes
C. = unit cost of using arc i
= 0 if i € P
=0 if i e T
= f.. if i is an arc joining cities i and j
= d if i is an arc joining city c
c and terminal t
= d if i is an arc joining terminal t and
city c (where these symbols have been
defined previously)
A~v = arcs leaving node k
B,,, v = arcs entering node k
m = number of salesmen
An example of the graph representing this formulation is
shown in Figure 4-1 for the case of N=4 cities, m=2 salesmen per
terminal, s=l terminal and k=2 cities to be visited by each salesman.
As indicated earlier, such a problem could be solved by a matching
algorithm instead of the techniques under discussion now. However,
this case is presented here to give an example for a graph that is
easily drawn and understood. The number of arcs and nodes required
to characterize a problem is quite large. For an N city, s terminal
problem when all cities may be reached from all other cities and
terminals, the number of nodes is
2s + 2N
-------
- 113 -
(I.
(2,2,0)
(UPPER BOUND, LOWER BOUND, UNIT COST)
NOT ALL POSSIBLE ARCS ARE SHOWN.
Figure 4-1. Graph for a Problem with N=4, p=l, m=2, k=2.
-------
- 114 -
and the number of arcs is
N2 + 2s UN + s
For N=16, s=2 there are 34 nodes and 322 arcs.
The relationship of the solution of Problem B to Problem A
may be summarized in the following three cases:
Case 1. The solution of Problem B is also a feasible
solution for Problem A. This is shown in Figure 4-2.
This case will be referred to as a feasible solution.
Case 2. The solution of Problem B is such that m
routes are found from each of the terminals, but not
all visit exactly k cities before returning. All
cities are visited by a route starting from and re-
turning to a terminal. Such a solution is shown in
Figure 4-3. This will be called a regular infeasible
solution.
Case 3. The solution of Problem B generates more than
ms routes and only ms of these start and end at a terminal.
A feasible solution to Problem B might contain some routes
that start at a city, visit other cities and then return
to the starting city without ever touching the terminal.
This will be called a phantom infeasible solution. An
example is shown in Figure 4-4.
If an infeasible solution such as Case 2 or Case 3 appears,
additional work will have to be done to find the optimal solution
-------
- 115 -
(UPPER BOUND, LOWER BOUND, UNIT COST )
Figure 4-2. Feasible Solution to Problem A.
-------
- 116 -
( I, 1,0)
(UPPER BOUND, LOWER BOUND, UNIT COST)
Figure 4-3. Regular Infeasible Solution to Problem A.
-------
- 117 -
(UPPER BOUND, LOWER BOUND, UNIT COST)
Figure 4-4. Phantom Infeasible Solution to Problem A.
-------
- 118 -
to Problem A. The type of infeasibility will suggest the way that
the branch and bound procedure can be developed.
The general plan of attack will be the same as for the
capacitated trans-shipment facility location algorithm. Solve
Problem B. If the solution to Problem B is Case 1, it is feasible
to Problem A. Then since Problem A is more highly constrained than
B the optimal solution to A has been found. If the solution to B is
of Case 2 or Case 3 and therefore infeasible to A, the problem will
be broken into a series of subproblems which divide the set of
feasible solutions to B into mutually exclusive collectively
exhaustive subsets. This is done by taking some infeasible route in
the problem solution and prohibiting arcs involved in that route
from being in a further solution. Suppose the solution to Problem B
contains a route which starts at terminal t, visits h cities,
a^, &2> ••••» ah and returns to terminal t . Then the set of
feasible solutions may be divided into h + 1 subsets with the first
subproblem having all arcs broken from t to all the cities a,
through a^. The second subproblem breaks all arcs from a, to all
4f
other cities (a-^ through ah) and the terminal t . This is continued
until the h + 1'st subproblem breaks all arcs from a^ to a^ through
ah-l and to t • The arcs are broken by setting their unit costs to
infinity. Each subproblem is solved to find its lower bound. Since
in each subproblem an arc has been broken which previously had flow
into it, the flow pattern will change and the cost of the new
solution will be the same or higher than the previous solution. The
-------
- 119 -
cost of each of the subproblems is examined and the one with the
least cost is found. If its solution is feasible to A, an optimal
solution to A has been found. If it is not feasible to A, more
subproblems are generated in the same manner and the lowest cost
subproblem is again investigated. This is continued until the
lowest cost subproblem is a feasible solution to Problem A.
The rules used to set up the subproblems are called break
rules. Since there are two different types of infeasible routes,
it is possible to have several different break rules. One break
rule might be to choose for branching the smallest regular
infeasible route. Another is to choose for branching the smallest
phantom route and break its arcs. Experience with both break
rules is reported.
-------
- 120 -
D. A Detailed Algorithm for the m-Salesman Traveling Salesman
Problem
1. The following data are given:
N = the number of cities to be visited excluding
the terminals
s = the number of terminals
m = the number of salesmen leaving each terminal
k = the number of cities excluding the terminals
that a salesman must visit before returning
to a terminal
N
The number of salesmen, m, is an integer determined by m = :—r-
(ks;
If this calculation is not integer, N is adjusted by adding
dummy cities or subtracting real cities until m is integer.
d t = distance from city c to terminal t
*
dt(, = distance from terminal t to city c
f.. = distance from city i to city j
These distances are not necessarily symmetric. That is, d «
it
need not be equal to d^a nor f.. equal to f...
2. Construct a graph in the following manner:
There will be two sets of nodes, P and T, which make up
the graph.
Define P = (the set of nodes that represent cities)
For each of the N cities, a capacitated node is estab-
lished. This is accomplished by representing the capacitated
node by two nodes with a directed arc between them, as shown
-------
- 121 -
in Figure 4-2. The node that sends the directed arc is
known as the receptor node, and the node that receives the
directed arc will be known as the transmitting node of the
capacitated node. It will be required that the flow through
the capacitated node be exactly one unit. This is accom-
plished by setting the upper and lower bound on flow through
the arc joining the receptor and transmitting nodes equal to
one unit. Refer to the capacitated node representing a city
as a city node.
Define T = (the set of nodes that represent terminals)
For each of the s terminals, a capacitated node is con-
structed in the same manner as for the cities. It will be
required that the flow through each capacitated node repre-
senting each terminal be exactly m units, since m salesmen
will pass through each terminal. This is accomplished by
setting the upper and lower bounds on the flow through the
directed arc joining the receptor and transmitting node as
m units. Refer to the capacitated node representing each
terminal as a terminal node.
Arcs of the graph are defined in the following manner:
From T to P; define a directed arc from the transmitting
node of each terminal node to the receptor node of each city
i-
1*
tc
node. The unit cost on the arc is d and there is an upper
bound of one on the arc.
-------
- 122 -
From P to T; define a directed arc from the transmitting
node of each city node to the receptor node of each terminal
node with a unit cost of d and an upper bound of one.
Within P; from any city node i to any other city node j,
i ? j, define a directed arc with unit cost f.j.. and an upper
bound of one, from the transmitting node of i to the
receptor node of j.
3. Define S = (set of all arcs of the graph that have been
excluded from the solution and hence must
have zero flow)
S_ = (set of all arcs of the graph not yet excluded
from the solution)
*
S_ - (set of all arcs of the graph)
Then S \J S_ = S_ and S f\ £ = ^> , the empty set
Initialize S =
4. Find the minimum cost, maximum flow through the graph
using the out-of-kilter algorithm. If this is the first time
step 4 has been entered and there is no feasible solution
to the graph, there is no feasible solution to the problem.
Define the cost of this flow as CGRAPH.
5. Examine the solution of the graph to see if it is a
feasible solution to the m salesman traveling salesman problem.
This is done by decoding the solution to determine the routes
for each salesman. From each terminal node only m arcs
-------
- 123 -
leaving it may have non-zero flow and for each city only one
arc entering and one arc leaving it may have non-zero flow.
The routes for each of the salesmen may then be calculated
by starting at a terminal and selecting an arc to a city, say
*
city i , from that terminal with non-zero flow. Then examine
if
the city node i , and find the single non-zero arc leaving it.
If this arc goes to a terminal the route is complete. If it
JUJLn -ffijf
goes to another city, say i , examine the city node i and
apply the same rules until the route is terminated. Continue
until each of the m routes at each of the s terminals has
been enumerated. If each of the routes enumerated visits
exactly k cities, the solution is feasible.
6. If the solution is feasible, go to step 7- If it is not,
one of the infeasible routes is chosen for branching. Select
the smallest route in terms of number of cities visited as
the candidate for branching. In case of a tie for the
smallest, choose the first enumerated.
7. Store information about the solution. File on a list,
ranked on the cost CGRAPH, of all solutions generated, data
about the feasibility, members of the S set and the candidate
for branching.
8. Remove the first solution on the list. If that solution
is feasible, it is optimal.
-------
- 124 -
9. If the solution is infeasible, several subproblems are
set up. Suppose the route chosen as the candidate for
branching starts at terminal t, visits h cities, a,, a£, ...
..., a, , and returns to terminal t . Then h + 1 subproblems
will be generated. First eliminate all arcs listed in the
S set by setting their costs to infinity.
9a. Subproblem 1 - Break all arcs from t to each of
the cities a,, a.* , a, , by setting the costs of
these arcs to infinity and add these arcs to the S set.
Repeat steps 4 through 7. Restore the arcs just broken
to their original costs and go to 9b.
9b. Subproblem 2 through h + 1 - If this is the g'th
subproblem, break all arcs from a , to each of the
other h-1 cities and to t and add these arcs to the
S set. Repeat steps 4 through 7 and restore the arcs
just broken and go to the next subproblem. When all
h + 1 subproblems are completed, go to step 8.
-------
- 125 -
E. Computational Experience
The algorithm was programmed in ASA Fortran IV and run on an
IBM 7094 computer. The out-of-kilter algorithm was written by
Clasen and made available through the IBM SHARE Library. The list
processing subroutines used for keeping track of solutions were
written by Bellmore (1966). Two possible break rules were considered
for setting up subproblems. Break rule A selected the smallest
infeasible route that passed through a terminal as the route for
branching. Break rule B involved selecting a phantom route (Case 3
infeasibility) which by definition does not pass through a terminal,
as the candidate for branching. If no phantom routes exist, rule A
is employed. Both rules were tried in early runs for some 8 city
problems and showed little difference. Only break rule A was used
in the larger city cases. Because of dimension limitations and the
use of decimal packing instead of binary packing for the storage of
information about solutions, many problems were limited by exceeding
storage rather than by time limits. Future attempts at working with
this algorithm will require better programming techniques and more
careful packing of data to insure greater efficiency, but such pro-
gramming efforts were not deemed necessary for this trial demon-
stration of the method. Runs were made with one and two terminals
for cases of 8, 12 and 16 cities. Results of these runs are shown
in Table 4-1. Runs were made with symmetric and asymmetric data.
The symmetric case generally took longer to solve. This same
-------
- 126 -
property in traveling salesman problems is explained by Bellmore
and Malone (1968). The procedure has a tendency to produce very
few feasible solutions before an optimum is found. This works to
a considerable disadvantage in the last two runs, since considerable
time was invested before termination without finding one feasible
solution. The algorithm could be speeded up and have more feasible
solutions generated, by taking each infeasible solution and applying
some heuristic procedure to round it to a feasible solution. The
development of the feasible solution would not take long, and if
found to be lower than the current best feasible solution, a tighter
bound on the problem has been found. At termination before optimal
solution, a good feasible solution would still exist.
Edmonds and Johnson (1969) are presently working on a problem
area known as degree constrained subgraphs which would appear to
have application to the above problem. Basically, the problem is
to minimize the cost of using arcs subject to constraints that a
specified number of arcs must enter and leave each node. This could
form the basis for generating tours for each vehicle. The algorithms
Edmonds and Johnson deal with are as fast as the matching problem
algorithms. Based on Bellmore and Malone's (1968) experience, it
would be expected that this would alleviate the problem of vastly
different computation time for symmetric and nonsymmetric data
cases.
-------
Table 4-2. Computational Experience for Problems with Randomly Generated Data
No. of
Terminals
(s)
1
1
1
1
1
1
2
1
2
2
2
2
No. of
Vehicles
at each
Terminal
(m)
2
4
4
2
3
3
2
4
4
2
4
5
No. of
Cities
(N)
8
8
12
12
12
12
12
16
16
16
16
20
Data
Type
ASYM***
ASYM
ASYM
ASYM
ASYM
SYM***
SYM
ASYM
ASYM
ASYM
SYM
ASYM
Features
No. of
Arcs
73
73
169
169
169
169
169
289
322
322
322
1,682
of Graph
No. of
Nodes
18
18
26
26
26
26
26
34
36
36
36
44
No. of
Feasible
Sol'ns
1,680
27
1,360
665,280
11,880
5,940
47,520
43,680
50,000
174,720
25,000
4.4xl06
No. of
Times
OKA
Called
8
27
76
150
101
101
46
251
210
215
230
330
No. of
Feasible
Sol'ns
Found
2
2
1
2
2
2
1
4
8
3
0
0
Running
Time on
IBM 7094
(minutes)
0.03
0.10
0.48
0.75
0.52
0.52
0.32
1.87
2.39
1.87*
**
2.12
3.21**
i
i-1
Ni
1
**
Stopped because of storage with lower bound close to a generated feasible solution.
Stopped because of storage with no feasible solution found.
'ASYM means asymmetric data,
SYM means symmetric data.
-------
- 128 -
CHAPTER V. THE ANALYSIS OF A SOLID WASTE COLLECTION SYSTEM
Introduction
In this chapter, a large scale solid waste collection and
disposal system will be investigated, using some of the techniques
suggested in previous chapters. The system chosen for examination
was that operated by the City of Baltimore, Maryland. This
selection was based on several factors. First, Baltimore is a
good example of a large city with extensive investment in a public
solid waste collection system. Second, a great deal of data has been
collected concerning the operation of the system, and is available.
Analysis of the Baltimore system has already been attempted by
Truitt (1968, 1969), who used the city as an example in the
development of a simulation model of collection. Through his
excellent work, considerable data and insight into the system are
available for use with the models proposed in this study. All data
taken from Truitt's work will be referenced.
-------
- 129 -
A- Characterization of the Baltimore Solid Waste Collection System
The City of Baltimore, Maryland, had a population in 1960 of
just over one million, a land area of 80.3 square miles and physical
characteristics that ranged from high density urban slums to verdant
low density residential subdivisions. The municipal functions of
solid waste collection and disposal as well as general sanitation
activities are carried out by the Bureau of Sanitation of the
Department of Public Works. For purposes of logistics and super-
vision, the city is subdivided into five autonomous districts, the
northwestern, the northeastern, the central, the eastern and the
western. These districts are shown on the map in Figure 5-1. The
I/
Bureau employs 1271 persons and owns approximately 340 vehicles
and pieces of equipment, and operates on a budget of over seven
million dollars per year. A breakdown of the functions and their
costs is shown in Table 5-1. As indicated in the table, collection
accounts for almost 85 percent of the department's operation and
the predominant collection operations are mixed refuse collection
and street cleaning.
The Bureau collects mixed refuse from residential and non-
commercial sites twice a week, once on either Monday, Tuesday or
Wednesday, and once on either Thursday, Friday or Saturday. Since
collection in the earlier part of the week represents the pick up
of four days' accumulation of wastes, crew size is one driver and
-/From Report of Department of Public Works (Anon, 1966a)
-------
- 130 -
three laborers. In the later part of the week crew size is reduced
to one driver and two laborers. Two types of vehicles are generally
used for collection. They are both equipped with compaction equip-
ment and have capacities of 20 and 13 cubic yards of compacted solid
wastes each. The larger vehicle is often referred to as a five ton
truck and the smaller as a three ton truck. The larger vehicle is
thought to be more efficient than the smaller and is assigned to the
general tasks while the smaller is saved for alleys and other size
restricting jobs. In 1965 the Bureau collected 336,893 tons of
mixed refuse, 31,395 cubic yards of ashes and 216,622 cubic yards of
street dirt. The collection of the mixed refuse from residences
involves 92 vehicles, each with three daily route assignments per
week for a total of 276 routes. There are two city owned incinera-
tors for the disposal of wastes, and the solid waste collected is
taken directly from the collection area to the incinerator by the
collection vehicle. One of the incinerators is the Number Three
(Reedbird) with a capacity of 600 tons per 24 hour day, and the
other is the Number Four (Pulaski) with a capacity of 800 tons per
24 hour day. The location of these facilities is also shown in
Figure 5-1.
-------
- 131 -
Table 5-1. Cost of Operations and Services Provided by the Bureau
of Sanitation, City of Baltimore, Maryland, 1965.
Operation
Street Cleaning
Ash Cleaning
Mixed Refuse Collection
Other Miscellaneous
Collection Expenses
Incinerators
Dumps
Disposal Expenses
Yearly Expense
2,792,000
202,000
3,034,000
324,000
6,352,000
1,110,000
40,000
1,150,000
Percent of Total
37.2
2.7
40.4
4.4
84.7
14.8
0.5
15.3
Totals 7,502,000 100.0
-------
- 132 -
B. Study Objectives
Analysts involved in the study of, and planning for, large
scale public systems such as the solid waste collection and disposal
systems must be concerned with both long range and short range
planning. Not only must they study the evolution of new technology
and methods that may dramatically change alternatives and options
in the future, but they must be concerned with the present on-going
vital existence of the system. This study will be directed towards
the analysis of the system within the short range picture, in order
to give some feeling for the alternatives that are available for
immediate introduction into the system. These alternatives may be
physical changes such as the building of new structures, policy
changes such as changes in the manner and character of the services
and rules of operation of the system, or changes in the methods for
carrying out certain objectives of the system. Short range alterna-
tives that fall into each of these categories make up the prominent
issues that require analytical attention.
The three questions that make up the theme of this study are:
1. Are transfer sites within the city a feasible alternative?
If so, where should they be located and to what capacity
should they be built?
2. What is the cost and effect of increasing collection
frequency from twice a week to three times a week?
3. Under what conditions and at what price would rail
haul become a feasible alternative for the city?
Subordinate to these main questions but still of great interest to
-------
- 133 -
the analyst and planner are such additional questions as:
4. How sensitive is the system to changes in parameters
and cost estimates?
5. What are the effects of political and esthetic
constraints that might force a change from the
solution most economically efficient from the
engineering point of view to one that is perhaps
more acceptable to segments of the community?
6. Are there advantages to cooperation between
governmental units within a region where such
cooperation does not now exist?
These questions will be subject to some preliminary investigation
in the next sections, using the large scale facility location model
of Chapter II. More detailed study would also require some of the
routing techniques of Chapter IV to achieve overall efficiency of
operation, but these have not been included in this overview.
-------
- 134 -
C. Calculations and Data for the Baltimore Study
1. Collection area to be investigated
The area chosen for study was the same area studied by
Truitt (1968, 1969). It comprises the northwest division of the
City of Baltimore,and a map of the area and its relationship to
the city are shown in Figure 5-1. Within this area it is necessary
to subdivide into smaller subareas for analysis. A convenient way
to do this is to consider each census tract within the area as a
subarea. Exact population and neighborhood density type, based on
the 1960 census, are accurately known. There is a total of 40
census tracts within the northwest quadrant and these are shown in
the map of Figure 5-3. A coordinate system has been set up with its
zero point at the northwest corner. Information about the population,
number of housing units, neighborhood density type and the x-y
coordinates of the approximate centroid of the tract are given in
Table 5-2. Neighborhood density types are based on estimates made
from census data by the City of Baltimore, Department of Planning,
as reported by Truitt (1968). These definitions are shown in
Table 5-3. The housing unit density is important because it gives
some indication of the speed of collection within a subarea. It
would be suspected that the more closely spaced the pick up points
are, the faster the collection process may be in terms of pounds
per hour collected. Truitt, in a statistical study of the Baltimore
data, shows that there is a significant difference between density
-------
- 135 -
Table 5-2. Pertinent Data Concerning the Forty Census Tracts of the
Northwestern Division, Baltimore, Maryland
Tract
Number
28-1B
28-2
28-3
28- 1A
27-19
27-20
27-17
15-12
15-13
27-16
27-18
15-7A
15-8A
15-8B
15-9
15-10
15-11
27-11
27-12
27-13
27-14
27-15
12-1
13-5
13-6
13-7
13-8
12-2
12-3
12-4
12-6
12-7
13-1
13-2
13-3
13-4
15-4
15-5
15-7B
15-6
Neighborhood
Density
1
1
1
2
1
1
2
3
3
3
3
2
2
2
2
2
2
1
1
1
1
1
2
3
3
3
3
4
4
4
4
4
4
4
4
4
3
3
3
3
Number of
Household
Units
2,482
2,035
1,194
1,099
1,490
4,634
2,079
2,011
1,910
1,979
3,207
865
1,787
493
1,574
2,249
2,691
780
2,159
913
1,543
1,904
1,887
523
1,426
1,918
2,039
3,839
1,987
1,687
1,532
1,474
1,917
2,062
1,598
1,154
1,576
741
1,787
2,150
^
Population
1960
2,482
5,646
3,546
3,531
4,622
13,437
6,756
6,091
5,623
6,127
9,808
2,944
4,811
1,390
4,950
6,193
7,677
2,786
6,648
3,183
4,398
6,427
3,495
1,762
4,336
5,429
6,824
7,499
5,483
5,469
3,177
4,705
4,648
5,859
4,904
4,026
5,800
2,064
4,298
7,725
?yt
Coordinates
x
3,750
3,806
4,000
4,000
10,000
5,750
14,500
17,500
15,000
16,000
10,500
14,000
11,500
11,500
9,000
9,250
13,500
31,500
31,000
25,000
26,500
20,000
32,000
27,500
27,500
27,500
22,500
32,000
33,000
33,000
32,000
30,000
27,500
27,500
23,500
22,500
20,500
18,000
14,500
14,000
-E-l*n*r
WVOv
y
13,000
9,000
26,000
8,500
6,500
3,000
8,500
17,000
14,500
12,000
11,000
22,500
21,500
25,000
24,500
16,500
17,000
10,500
3,500
4,000
11,000
6,500
15,000
20,500
18,000
15,000
15,500
16,500
22,000
24,500
22,000
22,500
23,500
25,000
20,000
20,500
25,000
22,000
25,000
27,000
*Tract number is U. S. Census designation.
**Population and number of household units from 1960 census.
***Coordinates are in feet measured to the approximate centroid of the
tract. Point x=0, y=0 is located at the extreme northwest corner
of the Baltimore City boundary.
-------
- 136 -
type 1 and density types 2, 3, and 4, but no significant differences
between 2, 3, and 4. Thus only two sets of neighborhood density
types need be considered, type 1 and other than type 1.
Table 5-3. Classification of Neighborhood Types
Classification Housing Units per Acre
1 Ten or less
2 Eleven to twenty
3 Twenty-one to forty
4 More than forty
-------
- 137 -
NORTHWESTERN
DIVISION
NORTHEASTERN
DIVISION
EASTERN
DIVISION
WESTERN
DIVISION
N
CENTRAL.
DIVISION
INCINERATOR
NUMBER 4
PULASKI
INCINERATOR
NUMBER 3
REEDBIRD*
PATAPSCO
RIVER
Figure 5-1. Operating Divisions of Bureau of Sanitation,
Baltimore, Maryland.
-------
- 138 -
N
Figure 5-2. Map Showing Census Tracts in Northwestern Division
of Baltimore, Maryland.
-------
- 139 -
NORTHWEST
QUADRANT
D
*
A
*
B
*
C
*
*
RR
F
*
"\J
INCINERATOR
NUMBER 4
*
PULASKI
N
INCINERATOR
NUMBER 3
Figure 5-3.
Map Showing Location of Proposed Transfer Sites and
Present Incinerator Sites, Baltimore, Maryland.
-------
- 140 -
2. Speed of collection within a subarea
The speed of collection within a subarea is a function of the
neighborhood density and the number of days since the last collec-
tion. When the collection frequency is two times a week as it is in
Baltimore, one collection is of four days of solid waste accumulation,
and the other of three. Normally the City of Baltimore system uses a
driver plus three laborers for the larger collection, and a driver
plus two laborers for the smaller one.
On pages 174-176 of Truitt (1968) several histograms are
presented for collection rates in pounds per hour as a function of
days since last collection and neighborhood type. The histograms
based on twice a week collection are computed from actual observa-
tions within the system. Estimates were made of histograms of three
times a week collection frequency. In this case the first collection
of the week has three days accumulation and the remaining two have
two days accumulation. The number of personnel assumed is one driver
and tw.o laborers. Table 5-4 presents weighted averages of the histo-
grams for different conditions which will be used in the analytical
models.
3. Cost of collection within a subarea
Cost of collection is assumed to be a function of the collection
frequency, the speed of collection, the neighborhood type and popula-
tion, and the work rules assumed. The following data are pertinent
to this computation:
-------
- 141 -
Table 5-4. Average Collection Rate in Pounds per Hour for Different
Days Since Last Collection and Neighborhood Type
Days Since Last
Collection
Neighborhood Type
Average Pounds per
Hour Collected
2
2
3
3
4
4
1
2, 3, 4
1
2, 3, 4
1
2, 3, 4
2,500
4,580
3,000
6,300
5,000
6,300
Table 5-5. Collection Costs in Dollars per Hour
Days Since
Last
Collection
4
3
2
Labor Necessary
1 driver +
3 laborers
1 driver +
2 laborers
1 driver +
2 laborers
Labor Cost
Dollars/Hr
12.63
9.33
9.33
Vehicle Cost
Dollars/Hr
4.40
4.40
4.40
Total
Cost /Hr
16.73
13.73
13.73
-------
- 142 -
a) Collection vehicle costs - The City of Baltimore
estimates its cost per hour of vehicle use for the 20 cubic yard
collection vehicle as $4.40 per hour.
b) Typical labor rates are twenty dollars per day for a
driver and eighteen dollars per day for a laborer. The normal crew
assignment for a collection of four days since last collection is
one driver and three laborers per vehicle. This drops to one driver
and two laborers for shorter intervals between collections.
c) To compute an hourly labor rate from the daily rate it
is necessary to compute the average time spent in actual work tasks.
Truitt (1968) has estimated that between 45 and 50 minutes per hour
are spent in actual productive time, with the remaining time being
spent in start up, repairs, off service time, etc. For the purpose
of this study, 45 minutes per hour or 6 hours per day will be used
as the productive time. This yields a productive hourly rate for
drivers of $3.33 per hour, and for laborers of $3.00 per hour.
Table 5-5 shows labor, vehicle and total costs for different
types of collection.
d) Waste load generated - The waste load generated per
person per day is a statistic that shows great variation. Truitt
(1968) after extensive study of Baltimore residential data, used
1.95 pounds per person per day and calculated a standard deviation
of 0.09 pounds per day. This figure will be varied to show the
sensitivity of the solution to it.
e) Total collection cost in a subarea per week - The total
-------
- 143 -
collection cost per week in a subarea is calculated in the following
manner:
Define p^ = population of the i'th subarea
k^ = weight of solid waste generated per person
per day with twice a week collection
frequency
i
k^ = weight of solid waste generated per person
per day with three times a week collection
frequency
lj = labor cost per hour for a crew of one
driver plus j laborers
= collection rate in pounds per hour for
neighborhood type k for i days since
last collection
The reasons that the waste generation is shown to be different
for different types of collection frequency are pointed out in statis-
tical studies by Quon, Tanaka and Charnes (1968). They show a
significant increase in waste per household per week when collection
frequency increases from once to twice a week.
Total collection cost in the subarea is C^.
13 19
. = P.jk.; (4 - — + 3 — — )
§4,j
Ci = Piki
+ 2
+
dollars per week for a
collection frequency of
twice a week, and
dollars per week for a
collection frequency of
three times per week
The collection cost per ton
x 2000.
No extra charges were made for overhead or supervision as there was
no way to obtain a reliable estimate of these figures.
-------
- 144 -
4. Cost of Transport by Collection Vehicle from the Subarea
to Transfer Facilities or Disposal Points
a) The speed in traffic of a collection vehicle is shown
not to differ significantly between a loaded and an unloaded
condition by Truitt (1968), whose histograms also indicate an
average speed of 16 miles per hour.
b) The cost of the vehicle and crew per hour is the same as
calculated in 3 (c) above for collection within a subarea.
c) The distance between the subarea and a disposal or trans-
fer site is calculated in the following manner. A set of x, y
coordinates are given for all transfer stations and disposal points.
The location of the subarea is taken as its centroid. Since
vehicles usually cannot travel in straight lines between points,
travel distance is estimated using a metropolitan or rectangular
measure in which the travel distance between a and b is
lXa - Xbl + lYa * Ybl
where j I means absolute value.
d) The average weight carried per 20 cubic yard collection
vehicle at the disposal point is indicated in a histogram on page 161
in Truitt (1968). This is taken as 9,000 pounds per vehicle. Thus
the cost per truck for travel from the disposal point to the
collection area and return is measured in the following manner:
-------
- 145 -
Define d = travel distance in miles in one direction
li = cost of vehicle + driver + i laborers per hour
s = travel speed in miles per hour
Then cost per truck load for the two way trip is
s i
and since each truck carries on the average 9,000 pounds or 4.5 tons,
the cost per ton is
1 d
Table 5-6. X, Y Coordinates for Proposed Transfer Stations*
Identification Type X Coordinate Y Coordinate
Symbol (feet) (feet)
RR
A
B
C
D
E
F
Transfer to
railroad cars
Transfer to
trailer trucks
Transfer to
trailer trucks
Transfer to
trailer trucks
Transfer to
trailer trucks
Transfer to
trailer trucks
Transfer to
trailer trucks
24,000
16,000
14,000
28,000
22,500
37,000
34,500
21,000
11,000
22,000
20,500
7,000
9,500
21,000
* c o
See map, Figure 5-3.
-------
- 146 -
5. Transfer Facility Costs
Truitt (1968) listed four potential transfer sites which were
located within the northwest quadrant, which will be used in this
study as well. In addition, three more sites were chosen within the
quadrant at various locations including one that is intended as a
transfer to rail-haul selection. The coordinates X, Y, for each
site are given in Table 5-6 and are shown on the map in Figure 5-3.
The original Truitt sites are marked A, B, C, and D. The proposed
additional vehicle transfer sites are E and F, and the railroad site
is RR. The cost of building transfer facilities was also estimated
by Truitt (1968) in the following manner:
Land Cost: Fixed cost of $40,000 below 200 tons per day
capacity and a variable cost of $200 per ton
of additional capacity above 200 tons per day.
Labor Costs: Three men at $20 per day for a transfer
station of less than 200 tons per day or $60
per day. Four men at $20 per day or $80 per
day for a greater capacity.
Utility Cost: $1200 per year.
Capital Cost
of Structures: $125,000 for a capacity of less than 100 tons
per day. Above 100 tons per day there is a
variable cost of $500 per ton of additional
capacity added to the fixed charge.
-------
- 147 -
The total waste load per week from the northwest quadrant is
estimated as 14 pounds per week for each of the 203,500 persons, or
1428 tons per week. The peak day load would occur in the early part
of the week with three times a week collection. In this case on
Monday and again on Tuesday, one half of the northwest quadrant is
visited and 3/7 of the weekly waste load is collected. Thus the
maximum daily load is
1/2 x 3/7 x 1425 = 306 tons per day
The cost of a transfer facility as a function of weekly
capacity is shown in Table 5-7. The yearly cost of the structure
has been produced through discounting, assuming 30 year life and an
interest rate of 10 percent. The yearly cost of the land is based
on interest on investment and it is assumed that the land does not
depreciate. No estimates were made on taxes lost on the land,
since Truitt's sites A, B, C and D were chosen on land that was
already public. It is assumed for simplicity that the same type
of land is available at E and F.
6. Transfer from Transfer Station to Final Disposal Via
Transport Vehicles and Disposal Costs
a) Transfer costs - The vehicles suggested for transport to
the final disposal areas from the transfer station are of two types.
One type is a 75 cubic yard tractor trailer with a weight capacity
of an estimated 35,000 pounds. Truitt (1968) gives the cost of this
-------
Table 5-7. Cost of Transfer Stations as a Function of Weekly Capacity
Week ly
Capacity
(tons/wk)
600
900
1,200
1,500
1,800
2,100
Total
Structure
Cost
(dollars)
125,000
150,000
175,000
200,000
225,000
250,000
Total
Land
Cost
(dollars)
40,000
40,000
40,000
50,000
60,000
70,000
Year ly
Structure
Cost*
(dollars/yr)
13,300
16,000
18,700
21,400
24,100
26,800
Yearly
Land
Costs**
(dollars/yr)
4,000
4,000
4,000
5,000
6,000
7,000
Utilities
(dollars/yr)
1,200
1,200
1,200
1,200
1,200
1,200
Labor***
(dollars/yr)
18,720
18,720
18,720
24,960
24,960
24,960
Total
Cost
per Yr
37,220
39,920
42,620
52,560
56,260
59,960
Total
Cost
per Wk
719
770
820
1,010
1,080
1,145
jfearly structure cost based on capital recovery factor - 10 percent - 30 years.
'jiftff
Yearly land cbst based on 10 percent interest rate for opportunities foregone.
Based on 6 days a week, 52 weeks a year operation.
-P-
00
-------
- 149 -
vehicle at $11.00 per hour. Using $3.33 per hour for a driver gives
a cost of $14.33 per hour of truck use. The average speed is esti-
mated at 16 miles per hour. The other type would be rail-haul from
the transfer station to some far distant point for disposal.
Philadelphia, Pennsylvania, as reported by PUBLIC WORKS magazine,
(Anon, 1968), presently does this at a contracted rate of $5.40
per ton for shipping and disposal in abandoned coal mines 200 miles
away in western Pennsylvania. This cost will be used as an
estimate of rail-haul transport and disposal costs.
b) Estimates of tractor trailer vehicle cost per ton.
Define Xp, Y = coordinates of the facility
XQ, YD = coordinates of the disposal point
c = capacity of the vehicle in pounds
s = travel speed in miles per hour
d = distance to be traveled - one way
1 = cost per hour of vehicle plus labor
then cost per ton = (2 ^ x 1 x 2000)
s c
where d is measured as before by a rectangular metric
d - /xF - XD| + |YF - YD|
where | I means absolute value of the difference.
c) Costs and locations of disposal areas - The location of
the disposal points are given as the two existing incinerators, the
Reedbird and the Pulaski. One additional alternative, that of rail-
-------
- 150 -
haul, is also included. The unit cost used as based on the previous-
ly mentioned data accounts for a rail-haul of approximately 200 miles.
Therefore, it is not necessary to locate the rail-haul disposal
facility. The x-y coordinates for the two existing facilities and
the unit cost of operation as given in the 1965 Public Works Report
of the City of Baltimore are shown in Table 5-8. Refer to Figure 5-3
for location in relation to the collection area.
Table 5-8. Characteristics of Baltimore Incinerators
Name Location Capacity Cost
(tons/day) per Ton*
Reedbird - #3 x = 26,000 y = 45,000 600 3.60
Pulaski - #4 x = 49,000 y = 26,000 800 2.80
From Anon. (1966a), Baltimore Public Works Department Annual Report
-------
- 151 -
D. Results of the Analysis
1. Explanation of Symbols
I/
A total of 60 runs were made with the facilities location
model and the data case of section C. These runs represent a broad
spectrum of changes in parameters and conditions in order to show
the sensitivity of the system and to estimate the order of magnitude
of the cost of proposed system policy and operational changes. These
runs are summarized in Table 5-9. The headings of each column are
explained and referenced in the following manner:
Type of Transfer Station - For most runs, seven transfer
station site alternatives were allowed, A, B, C, D, E, F and RR.
These symbols and the locations of the sites have been shown
previously in Table 5-6. It was assumed in most runs that the same
capacity facility was proposed at each site. Any deviation from
this policy, or in the number of sites available, is noted in the
REMARKS column beside the run.
Collection Frequency - Two cases were considered: twice a
week (2) and three times a week (3).
Collection Costs - These are the costs of picking up the
solid waste within the collection areas. The basis for estimating
this cost is shown in section C (3) of this chapter. Units are in
dollars per week.
-/Each run took an average of 45 seconds, or for the 60 runs a total
of 45 minutes of execution time on the IBM 7094.
-------
- 152 -
Transfer Cost from Collection - This represents the transpor-
tation costs incurred by the collection vehicles in hauling their
collected load from the area where it was picked up to the point
where it will be discharged, and the return trip to the collection
area. The point of discharge in most cases may be either a transfer
facility or a final disposal point. In most cases when transfer
stations were built not all collection vehicles used them, for it was
still economically feasible for some collection subareas to ship
directly to final disposal. Units are dollars per week.
Facility Costs - Cost per week of building and operating a
facility of a given capacity. Computations to arrive at these
figures are shown in Table 5-7-
Transfer from Transfer Stations - This category represents the
cost incurred using specialized tractor trailer transport vehicles
to move wastes from the transfer site to the final disposal site. If
rail-haul is used, such transfer costs do not appear in this
category but as part of the disposal cost, since there is no way to
break apart the unit cost figure for rail-haul and disposal. Units
are dollars per week.
Disposal Costs - This reflects the unit cost of disposal. In
all cases where local disposal was chosen, the Pulaski incinerator
was chosen over the Reedbird incinerator because of its preferable
location with regard to the northwest quadrant that makes up the
study area, and because of the lower unit costs of disposal at the
newer Pulaski incinerator. In the case where rail-haul was chosen
-------
- 154 -
Table 5-9. Description of Runs with Baltimore Data
Run
No.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Type of
Transfer
Station
Proposed
Tons /Wk
1200
NONE
600
900
900
600
1200
1500
1500
NONE
NONE
1500
1500
NONE
NONE
1500
NONE
Collec-
tion
Freq.
Times
per Wk
2
3
3
3
2
2
3
3
3
3
3
3
3
3
3
3
2
Collec-
tion
Cost
Dollars
per Wk
8,103
9,361
9,361
9,361
8,103
8,103
9,361
9,361
9,361
9,361
9,361
9,361
9,361
9,361
9,361
9,361
8,103
Transfer
from
Collec-
tion
Dollars
per Wk
1936
4040
2226
1847
2097
1490
1699
1620
1780
5060
6087
1780
1780
1773
1773
1780
4563
Fac'l'ty
Costs
Dollars
per Wk
820
G>
719
770
770
1438
820
1010
1010
0
0
1010
1010
1010
1010
1010
0
Trans f er
from
Transfer
Station
Dollars
per Wk
742
0
540
630
630
840
742
765
914
0
0
1200
1600
0
0
7000
0
Disposal
Cost
Dollars
per Wk
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
7711
7711
3998
3998
-------
- 155 -
Fac'lty Load Load Total Total Cost
Built Sent to Directly Load Dollars/Wk
Fac'lVs to Tons/Wk
Tons/Wk Disposal
Tons/Wk
Remarks
B
NONE
A
B
B
A, C
B
B
C
NONE
NONE
C
C
RAIL
HAUL
RAIL
HAUL
C
NONE
1060
0
600
900
900
600
600
1060
1093
1428
0
0
1428
1428
1428
1428
1428
0
368
1428
828
528
528
228
368
335
0
1428
1428
0
0
0
0
0
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
15,599
17,399
16,844
16,606
15,598
15,869
16,620
16,754
17,063
18,419
19,449
17,349
17,749
19,855
19,855
18,149
16,664
Av'ge haul distance
10 miles
Av'ge haul distance
10 miles
Av'ge haul distance
12 miles
Av'ge haul distance
12 miles
Av'ge haul distance
14 miles
Av'ge haul distance
14 miles
Av'ge haul distance
16 miles
Av'ge haul distance
16 miles
-------
- 156 -
Table 5-9. Description of Runs with Baltimore Data (continued)
Run Type of Collec- Collec- Transfer Fac'l'ty Transfer Disposal
No. Transfer tion
Station Freq.
Proposed Times
Tons/Wk per Wk
tion from
Cost Collec-
Dollars tion
per Wk Dollars
per Wk
Costs from Cost
Dollars Transfer Dollars
per Wk Station per Wk
Dollars
per Wk
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1500
1500
NONE
NONE
1500
1500
NONE
NONE
1500
1800
1800
1800
1800
1800
2
2
2
2
2
2
2
2
2
2
2
2
2
2
8,103
8,103
8,103
8,103
8,103
8,103
8,103
8,103
8,103
9,245
10,107
10,967
11,795
12,674
1846
2020
5714
1967
2020
2020
1967
1967
2020
2028
2220
2408
2590
2781
1010
1010
0
1010
1010
1010
1010
1010
1010
1080
1080
1080
1080
1080
765
900
0
0
1350
1800
0
0
2250
841
920
999
1073
1154
3998
3998
3998
7711
3998
3998
7711
7711
3998
4398
4807
5216
5611
6028
-------
- 157 -
Fac'l'ty Load Load Total Total Cost
Built Sent to Directly Load Doliars/Wk
Fac'l't's to Tons/Wk
Tons/Wk Disposal
Tons/Wk
Remarks
B
C
NONE
RAIL
HAUL
C
C
RAIL
HAUL
RAIL
HAUL
B
B
B
B
B
B
1093
1428
0
1428
1428
1428
1428
1428
1428
1202
1315
1427
1534
1649
335
0
1428
0
0
0
0
0
0
369
402
436
470
504
1428
1428
1428
1428
1428
1428
1428
1428
1428
1571
1717
1863
2004
2153
15,722
16,031
17,815
18,791
16,481
16,931
18,791
18,791
17,381
17,592
19,134
20,670
22,149
23,717
Av'ge haul distance
10 miles
Av'ge haul distance
10 miles
Av'ge haul distance
12 miles
Av'ge haul distance
12 miles
Av'ge haul distance
14 miles
Av'ge haul distance
14 miles
Av'ge haul distance
16 miles
Av'ge haul distance
16 miles
Increase waste load
by 107,
Increase waste load
by 20%
Increase waste load
by 307.
Increase waste load
by 407.
Increase waste load
1 C f\9l
-------
- 158 -
Table 5-9. Description of Runs with Baltimore Data (continued)
Run Type of Collec-
No. Transfer tion
Station Freq.
Proposed Times
Tons/Wk per Wk
Collec- Transfer Fac'l'ty Transfer Disposal
tion from Costs from Cost
Cost Collec- Dollars Transfer Dollars
Dollars tion per Wk Station per Wk
per Wk Dollars Dollars
per Wk per Wk
32
33
34
3.5
36
37
38
39
40
41
42
1800
1800
1800
1800
1800
1800
1800
1800
1800
1800
1500
2
2
2
2
2
2
2
2
2
2
2
13,501
14,356
15,220
16,074
8,103
8,103
8,103
8,915
7,310
6,660
11,264
2965
3212
3507
3818
1700
1688
1684
1846
1846
1846
2918
1080
1080
1080
1080
1080
1080
1080
1080
1080
1080
1010
1229
1260
1260
1260
778
454
344
765
765
765
1050
6428
6829
7240
7646
3998
3998
3998
3998
3998
3998
6028
43 2100
15,043 3808 1145
1470
8050
-------
- 159 -
FacYty Load Load Total Total Cost
Built Sent to Directly Load Dollars/Wk
Fac'lV's to Tons/Wk
Tons/Wk Disposal
Tons/Wk
Remarks
B 1756
B 1800
B 1800
B 1800
A 1112
A 1135
A 1147
B 1093
B 1093
B 1093
B 1500
538
639
706
931
316
293
281
335
335
335
653
2294
2439
2586
2731
1428
1428
1428
1428
1428
1428
2153
25,198
26,737
27,869
29,818
15,659
15,323
15,209
16,604
14,999
14,349
22,270
Increase waste load
by 607,
Increase waste load
by 707=
Increase waste load
by 807=
Increase waste load
by 907«
Transfer vehicle speed
20 mph
Transfer vehicle speed
30 mph
Transfer vehicle speed
40 mph
Vary collection rate
by -10%
Vary collection rate
by +107o
Vary collection rate
by +207,
B is only alternative
_ _ _ . _ i _ _ .1
B
2100
775
2875 24,516
Increase waste load
by 507,
B is only alternative
Increase waste load
by 100%
-------
- 160 -
Table 5-9. Description of Runs with Baltimore Data (continued)
Run Type of Collec- Collec- Transfer Fac'l'ty Transfer Disposal
No. Transfer tion tion from Costs from Cost
Station Freq. Cost Collec- Dollars Transfer Dollars
Proposed Times Dollars tion per Wk Station per Wk
Tons/Wk per Wk per Wk Dollars Dollars
per Wk per Wk
44
45
46
47
48
49
50
51
52
53
54
55
56
1500
1500
1500
1500
1500
1500
1500
1500
1500
1500
1500
1500
1500
3
2
3
2
3
2
3
2
3
2
3
3
3
9,361
8,103
9,361
8,103
9,361
8,103
9,361
8,103
9,361
8,103
9,361
9,828
10,291
1620
1498
1230
1754
1780
1846
1620
1846
1620
4564
4040
1700
1780
1010
2020
2020
1010
1010
1265
1265
1518
1518
0
0
1010
1010
765
851
591
940
714
765
765
765
765
0
0
804
841
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
3998
4197
4398
-------
- 161 -
Fac'l'ty Load Load Total Total Cost
Built Sent to Directly Load Dollars/Wk
Face's to Tons/Wk
Tons/Wk Disposal
Tons/Wk
Remarks
B
B, D
C, F
A
C
B
B
B
B
NONE
NONE
B
B
1093
746
411
700
415
1044
1428
1093
1093
1093
1093
0
0
1148
1202
335
271
313
384
0
335
335
335
335
1428
1428
351
369
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1428
1499
1571
16,752
16,471
17,200
15,805
16,863
15,977
17,009
16,230
17,262
16,664
17,399
17,539
18,321
B is only alternative
Increase waste load 0%
Political jurisdiction
case
Political jurisdiction
case
Deny B as an alterna-
tive
Deny B as an alterna-
tive
Increase fixed costs
by 25%
Increase fixed costs
by 25%
Increase fixed costs
by 50%
Increase fixed costs
by 50%
Increase fixed costs
by 100%
Increase fixed costs
by 100%
Increase waste load
by 5%
Increase waste load
1 1 f\0t
by 10%
-------
- 162 -
Table 5-9. Description of Runs with Baltimore Data (continued)
Run Type of Collec- Collec- Transfer Fac'l'ty Transfer Disposal
No. Transfer tion tion from Costs from Cost
Station Freq. Cost Collec- Dollars Transfer Dollars
Proposed Times Dollars tion per Wk Station per Wk
Tons/Wk per Wk per Wk Dollars Dollars
per Wk per Wk
57 1500 3 10,758 1861 1010 880 4594
58 NONE 3 9,828 4245 --- --- 4197
59 NONE 3 10,290 4443 --- --- 4398
60 NONE 3 10,757 4646 --- --- 4594
-------
- 163 -
Fac'l'ty Load Load Total Total Cost Remarks
Built Sent to Directly Load Dollars/Wk
FacTt's to Tons/Wk
Tons/Wk Disposal
Tons/Wk
B
NONE
NONE
NONE
1257
0
0
0
384
1499
1571
1641
1641
1499
1571
1641
19
18
19
19
,103
,270
,132
,998
Increase
by 15%
Increase
by 5%
Increase
by 10%
Increase
waste
waste
waste
waste
load
load
load
load
by 15%
-------
- 164 -
as the disposal method, the disposal costs include the cost of
hauling to the distant disposal point. Where local disposal was
chosen, the cost includes only the actual disposal process. The
sources of these costs are shown in section C (6) of this chapter
and are in dollars per week.
Facilities Built - If transfer sites were chosen by the
models, this indicates at which sites transfer stations of the
given capacity would be built.
Load Sent to Facilities - Tons of waste per week from the
collection areas that would be sent to transfer facilities rather
than directly to final disposal.
Load Directly to Disposal - Tons per week sent directly to
disposal without trans-shipment to a transfer site.
Total Load - The total waste load in tons per week collected.
Represents the sum of the previous two categories.
Total Cost - The sum of the collection, transfer from
collection, facility, transfer from facilities and disposal costs.
Units are dollars per week.
2. Explanation of Runs
Estimation of Present System Costs and Verification - The most
important aspect of the study is to establish some bench mark against
which the results of changing the system may be measured to determine
their efficiency. The present system runs with two times a week
collection frequency so the computation of this cost will serve not
-------
- 165 -
only as a bench mark but also as a check on the validity of the
model, since published figures are available for the cost of running
the actual system (Anon, 1966a). Run number 17 represents this
verification since its data inputs are the best estimates of all
data, collection frequency is twice a week and no transfer stations
are allowed. The yearly cost of collection by the city from the
northwest division for the year 1965 was $722,000. The model
reports this cost as $12,666 per week, or $688,632 per year, which
is a difference of 4.5 percent. The difference between the two
estimates is slight and may be explained by the fact that 1960
population estimates were used in the model while the actual cost
figure represents the cost of collecting from the 1965 population
of the same region. Since the northwest division of the city,
particularly at its outermost fringes, is gaining in population, it
would be expected that the model estimates would be slightly lower.
Estimation of a Three Times a Week Collection Frequency Bench
Mark - In run number 2, an estimate was made of the cost of three
times a week collection frequency without transfer stations, with a
resulting total system cost of $17,399 per week. When compared to
the twice a week bench mark of $16,664 per week this shows only a
4.6 percent increase in cost to increase in collection frequency.
However, this estimate is really only a lower bound on the actual
cost of three times a week collection and thus should be viewed with
care. There are several assumptions buried in the calculation of
-------
- 166 -
the cost of three times a week collection that should be clearly
stated. The first is that the routes for the vehicles will be
changed from those of the twice a week collection vehicles, to
insure that the truck is close to capacity before it makes the trip
to the transfer or disposal point. As noted, there is no instru-
mentation on a vehicle which tells the driver the present load of
his vehicle. Routes are usually assigned in terms of definite areas,
with the driver returning when he reaches a certain place. Since,
in three times a week collection, less waste is generated in a given
area as there has been less time since the last collection, the
vehicle must travel farther to get a complete load. The load on a
vehicle is an important factor in the calculation. The average
load for twice a week collection was 9000 pounds. Should the
average load for three times a week collection drop because routes
are improperly designed, say by 10 percent, the cost difference
between twice and three times a week would rise to 8 percent. Should
the average collected weight drop by 25 percent, the cost difference
between twice and three times a week collection would rise to 14 per-
cent. Thus extreme care must be taken in designing the routes to
make sure that enough load is picked up before transportation. A
factor to be watched in the design of the routes is the time factor.
Most operations work under a "no overtime" constraint, which means
that at a certain time the truck will return, regardless of its
present load. Since it takes longer to collect under a three times
a week policy careful attention must be paid to the time length of
-------
- 167 -
the routes. Models as suggested in Chapter IV on routing would be
used to assign routes correctly.
A second assumption that has been made in these computations
is that the waste load is the same for twice a week and three times
a week collection. This may not be a valid assumption, but no
published evidence exists to disprove it. However, work by Quon et
al. (1968) based on actual observations in a controlled experiment
in Chicago shows significant increases in waste loads when collec-
tion frequency was increased from once to twice a week. They found
waste load increases in the order of 30 to 50 percent. To test the
effect of waste load increase on the three times a week collection
calculation, runs 58-, 59 and 60 were made. These runs represent
three times a week collection with no transfer, and a waste load
increase of 5, 10 and 15 percent respectively. These runs show that
the estimation of the difference between twice and three times a
week collection is quite sensitive to the assumption made about
waste load. These computations are shown in Table 5-10. Great care
should be taken in estimating the difference between twice and three
times a week collection, as the cost difference is very sensitive
to the new waste load estimates.
However, in measuring and comparing differences between indi-
vidual runs when both have the same collection frequency, the type
of assumption made does not have a serious effect on the calculation
since the same assumptions appear in both. The remainder of the runs
made with a collection frequency of three times a week are all made
-------
- 168 -
with the assumption that the average truck load does not decrease
from twice a week collection and that individual waste load
generated does not change.
Table 5-10. Different Waste Load Assumptions and Their Effect on
the Percent Difference Between Twice and Three Times
a Week Collection with no Transfer
Waste Load Assumption Total System Cost
Dollars per Week
Cost Difference
Between Twice a Week
and Three Times a
Week Collection
Same as 2 times a week
5% greater
10% greater
15% greater
17,399
18,270
19,132
19,998
4.5%
10.0%
15.0%
20.0%
Is Transfer Feasible? - With the best data available for the
various cost parameters and for the cost of facilities, a series of
runs was carried out with different capacity transfer stations at
the proposed transfer sites to show if transfer stations lower the
cost of collection. In every case they did. The results of the
analysis also give some interesting insights into the system. Runs
3, 4, 7 and 8 were made for three times a week collection and for 4
different sized transfer stations ranging from 40 percent of the
-------
- 169 -
estimates of weekly waste loari (600 tons per week) to over 100 per-
cent (1500 tons per week). Similarly, runs 6, 5, 1 and 18 were
made for the twice a week collection rate and the results of all
these runs are presented in Figure 5-4. First, notice that beyond
the 600 ton per week alternative, the cost function for the higher
capacity stations is more favorable and quite flat, indicating little
sensitivity to size x^ithin that range. More important, for each
solution only one transfer site was chosen and for all six cases
that site was B. Thus this preliminary analysis would seem to favor
B for the present system. In all cases, the building of only one
transfer station indicated that some waste load was still going
directly to the final disposal point without transfer. Both the
1200 and 1500 ton capacity per week facilities were used at less
than capacity with about 40 percent of the waste in both cases going
directly to disposal. Later runs will show that this proportion is
very sensitive to the location of the final disposal points. The
cosf for three times a week collection with transfer is comparable
with the present two times per week collection without transfer.
Later calculations will show how comparable these costs are if
waste load should be increased for the higher frequency case.
For the smaller capacity (600 tons per week) stations, a
different alternative (A) was chosen and in one case two alternatives
(A and C) were chosen. In general, the difference between the solu-
tion with transfer stations and the one without is in the range of
-------
- 170 -
4 to 7 percent with the two times a week collection frequency
allowing a better decrease. The absolute difference between the
transfer and non-transfer solution is a rough measure of how much
facility costs can increase before transfer is no longer favorable.
More will be said about this later.
Effect of Increased Haul Distance to Final Disposal - The
present average haul distance from the northwestern division to
disposal at the Pulaski incinerator was shown to be 8 miles one way
by Truitt (1968) and was verified by this author. Now suppose that
the haul distance was increased. Such a case is possible because as
the city expands, the tendency is to move waste disposal farther out
in order to avoid creating a nuisance to nearby neighbors, and
because of the lack of availability of unused sites near the city.
Runs were made to see what the effect would be if the disposal
points were moved so that average haul distance was increased to 10,
12, 14 and 16 miles. In this analysis there is an additional
possibility which was not considered in Truitt's work. This is rail-
haul to far distant disposal points. As average haul distance
increases, transfer facilities become more and more favorable until
finally the most dominant choice is rail-haul. A set of runs was
made to see how moving the disposal point would affect a system with
and without transfer stations. Runs 10, 11, 14 and 15 represent the
case of increasing haul distance without allowing transfer, for
three times a week collection frequency. Runs 9, 12, 13 and 16
-------
- 171 -
allow transfer under the same conditions. Figure 5-5 shows the
results of these runs compared to the cost of the rail-haul alter-
native. It is evident that as the haul distance increases,
transfer becomes more favorable to non-transfer. In fact with non-
transfer, rail-haul becomes feasible at 12.9 miles average haul
distance. If transfer is allowed, rail-haul is not a suitable
alternative until almost 26 miles average haul distance. This
indicates that as pressure mounts to move disposal out farther from
the city, a transfer facility system would preclude rail-haul for
some time, given that the relative costs of the alternatives would
remain the same. Further, the transfer site chosen in each of the
runs was the same site C, indicating that the site selection in
this case is quite stable. Also, as soon as the disposal point has
been moved only 2 miles, all waste in the system goes through the
transfer facilities and none is taken directly to the disposal point.
This is the reason C was chosen for this case while B was chosen for
the previous cases with present location of facilities. The choice
between B and C favors B only slightly, and when conditions are
changed to cause more load to go through a facility, C becomes the
best alternative.
In Figure 5-6, results of runs 19, 20, 21, 22, 23, 24, 25 and
26 are plotted to show how a twice a week collection system would
react under the same haul distance changes. The results are quite
similar, with C being chosen as the transfer site and the rail-haul
alternative becoming feasible at a slightly smaller haul distance
-------
- 172 -
than in the previous case.
Thus it would appear that the questions concerning transfer
and rail-haul are intimately linked. Under present conditions,
rail-haul is not a feasible alternative. At a cost of $18,791 per
week for the present system it represents a 12.8 percent increase in
cost over the system with no transfer^ and an 18.3 percent increase
over the system with transfer. However, if haul distance should
increase, rail-haul would become a feasible alternative in a fairly
short time if no transfer is established. If transfer facilities
are built they reduce costs to the extent that rail-haul would not
be feasible for a considerable time. As for transfer itself, it
does exhibit some, but not extraordinary, savings over non-transfer
for the present system. For future conditions, however, these
savings will increase, thus making transfer even more favorable.
Sensitivity to other Parameters - Other runs were made to
show how sensitive the system was to estimates of the various
parameters. Since waste load estimation in three times a week
collection has been shown to have an effect on the solution, several
additional runs were made to study this situation. Runs 55, 56 and
57 represent runs with transfer facilities allowed, three times a
week collection frequency and an increase in the waste load of 5, 10
and 15 percent, while runs 58, 59 and 60 represent the system
without transfer. The results are shown in Table 5-11. The cost
of the transfer station decision is even more sensitive than the
-------
- 173 -
Table 5-11. Different Waste Load Assumptions and Their Effect on
Percent Difference Between Twice and Three Times a
Week Collection with Transfer
Increase in
Waste Load
(%)
0
5
10
15
Increase in Cost
with no Transfer
(%)
4.5
10.0
15.0
20.0
Increase in Cost
with Transfer
(%)
6.4
11.4
16.6
21.5
Site
Alternative
Selected
B
B
B
B
non-transfer solution. However, in all cases the site selected was
B, indicating that only the cost estimate but not the site chosen
is sensitive to this parameter. Twice a week collection was tested
for its sensitivity to waste load increase in runs 27, 28, 29, 30,
31, 32, 33, 34 and 35, where the waste load was progressively
increased until it almost doubled. Results of these runs are shown
in Figure 5-7. Even though waste load was increasing, the solution
cost responded linearly and the same alternative B, was chosen for
all solutions. Even when waste load was almost double the transfer
station capacity it was not optimal to build a second facility at
a different site.
Runs 36, 37 and 38 show how sensitive the solution is to the
-------
- 174 -
speed of the transfer vehicle from the transfer facility to the
disposal point. Results are plotted in Figure 5-8. Present esti-
mates place this speed at 16 miles per hour since this is the
approximate speed in traffic of the collection vehicles, and the
transfer vehicles are larger tractor trailers which must operate
under largely the same traffic conditions. The plot indicates that
an increase in the traffic speed from 16 to 30 miles per hour would
bring about a decrease of about 7.5 percent in the cost of the
solution. However, it would be expected that the cost of the
remedial measures necessary to bring about this increase in speed
would more than outweigh any savings in transportation costs.
An attempt was also made to see how collection rates affect
the solution. In runs 39, 40 and 41 collection rates are varied
by -10 percent, +10 percent and +20 percent. Increasing or decreasing
the collection rate by 10 percent leads to about a 5 percent change
in the solution cost, which falls into the range of being somewhat
sensitive. Thus care should be taken in estimating these rates.
Further, work rules that tend to increase collection rate without
too great an increase in cost or inexpensive time saving devices
would also bear some investigation.
The effect of changing the estimates of the facilities costs
is also of interest. This gives some feeling for how carefully cost
estimates have to be made for preliminary studies. Runs 49, 50, 51,
52, 53 and 54 show how fixed cost increases of 25, 50 and 100 percent
would affect the solution. At about a 75 percent increase in fixed
-------
- 175 -
costs, transfer facilities are no longer feasible, but up to that
point the same facility was chosen each time. A rough estimate of
how much facilities costs could increase could have been found from
earlier runs simply by looking at the absolute difference in cost
between the transfer and non-transfer solutions. If the facility
cost increase exceeded this difference, transfer was no longer
feasible.
Political, Aesthetic and Regional Constraints - Many times
constraints occur which preclude the use of an alternative that
would otherwise seem to be the best from an economic point of view.
Examples are political constraints when a site might better be put
to use for other municipal functions, aesthetic constraints where
the neighborhood around a site strongly opposes a. facility there,
and regional constraints which do not allow for cooperation between
different political subdivisions. Consider first an example where
a particular site is not allowed to be used. The results of the
analysis to this point show that B is the best transfer site. Runs
47 and 48 show what happens when this site is excluded from the set
of alternatives. In the case of two times a week collection, Site A
is chosen and the increase in the cost is about $60 per week. For
three times a week collection the site chosen is site C and the
difference is about $110 per week. Both of these changes are
minuscule compared to the total cost of operating the system. This
indicates that there may be readily available alternatives to the
-------
- 176 -
best site that will not raise the cost of the solution significantly.
Thus the cost of satisfying additional constraints which prohibit
certain sites is not particularly high, and the decision maker has
a great deal of leeway in choosing between alternatives when other
criteria must also be considered.
The effect of regionalization will only be treated briefly in
this example, as neither the time nor data were available for
assembling an extremely large regional case. However, the question
can be looked at implicitly by assuming that the northwestern
division is a unified region, and asking how much costs would
increase if it were subdivided into two non-cooperating regions.
Suppose the region were divided into two so that the northern areas
could use only transfer sites A, D and E, and the southern areas
could use only sites B, C and F. The results of these runs are
shown in Table 5-12. In this case subdividing the region still
makes transfer feasible, but only at an extremely slight advantage
over no transfer at all. This would suggest that regionalization
would mean increased savings. Although this analysis was not
extended to the entire city, it might be expected that each of the
administrative divisions would not have a transfer facility, but
only two or three would be built.
-------
17000
UJ
u
(T
UJ
Q.
(A)
(B)
( B)
-o—
3 COLLECTIONS
PER WEEK
(B)
O
o
• 16000
O
o
UJ
CO
JA.C)
( ) INDICATES THE SITE LOCATION
OF THE TRANSFER STATIONS
TO BE BUILT.
(B)
(B)
o —
2 COLLECTIONS
PER WEEK
( B)
15000
_L
J_
JL
J
600 900 1200
TRANSFER STATION CAPACITY IN TONS PER WEEK
1500
Figure 5-4. Plot of Total System Cost vs. Size of Transfer Station
-------
COST OF OPERATING SYSTEM
WITH RAIL HAUL
MILES
COST OF OPERATING
SYSTEM WITHOUT
TRANSFER
STATIONS
COST OF OPERATING
SYSTEM WITH
TRANSFER
STATIONS
) INDICATES THE SITE LOCATION
OF THE TRANSFER STATION
TO BE BUILT.
00
I
8 10 12 14 16 18 20 22 24
AVERAGE ONE WAY HAUL DISTANCE
26 28 30
IN MILES
Figure 5-5.
Plot of Average Haul Distance vs. Cost of Total System.
Collection Frequency = Three Times per Week.
-------
/'
COST OF OPERATING SYSTEM
RAIL HAUL
COST OF OPERATING
SYSTEM WITHOUT
TRANSFER
STATIONS
(C)
X(c)
^
/(C)
22.5 MILES
COST OF OPERATING SYSTEM
WITH TRANSFER STATIONS
( ) INDICATES TRANSFER
SITE CHOSEN
8 10 12 14 16 18 20 22 24 26 28 30
AVERAGE ONE WAY HAUL DISTANCE IN MILES
Figure 5-6. Plot of Average Haul Distance vs. Cost of Total System.
Collection Frequency = Two Times per Week.
-------
28000
LJ
UJ
g= 26000
a.
v>
IT
O
O
24000
V)
O
0 22000
S
UJ
CO
20000
18000
( ) INDICATES TRANSFER
SITE CHOSEN
00
o
(B)
10
20
PERCENT
30
INCREASE
40 50
IN WASTE LOAD
60
Figure 5-7. Plot of Cost of Solution vs. Estimate of Percent
Increase in Waste Load.
-------
ID
LJ
cr
IS!
o
Q
O
O
UJ
16000
to
1
H
00
I
15000
10
20 30
TRANSFER VEHICLE SPEED IN MILES PER HOUR
40
Figure 5-8. Plot of Transfer Speed in MPH vs. Cost of Solution
-------
UJ
ui
o:
UJ
a.
CO
O
o
UJ
CO
CO
_J
<
o
17000
o
0 16000
15000
14000
(B)
( ) INDICATES THE SITE
LOCATION OF THE TRANSFER
STATION TO BE BUILT.
(B)
10% 0
PERCENT CHANGE
(B)
00
ro
(B)
+ 10% + 20%
IN COLLECTION RATE
Figure 5-9. Plot of Varying Collection Rate vs. Cost of Solution.
-------
Table 5-12. Effects of Regional Cooperation
Collection
Frequency
2
Northwestern Division Northwestern Division Northwestern Division
is Two Districts with is One District Without Transfer
Transfer Without Transfer
Cost /Week
$16,471
Sites Cost/Week Site
B and D $15,720 B
Cost /Week
$16,664
17,200 C and F 16,752 B 17,399
M
03
-------
- 184 -
E. Summary of the Experimental Analysis
The following general statements about the system can be
made, based on the rough analysis with estimated data for the
northwestern division. These runs have been intended as a demon-
stration of the techniques of this thesis, rather than a detailed
analysis of the system. The actual findings would need verifica-
tion with better cost data before they could be viewed as
completely reliable.
1. The building of transfer facilities appears to be feasible
and would result in an annual savings, under present condi-
tions, of 7 percent in the total cost of operating the solid
waste collection system. This saving would be expected to
increase in the future, as the system expands and grows.
2. For the northwestern division only one transfer facility
would be built, with site B chosen as the location. Site C
is also a good alternative and selecting C over B would
show little disadvantage.
3. The most favorable size of the facility to be built is
1500 tons per week capacity. At this size some of the
waste material will be taken to transfer and some will
still be taken directly to the disposal point. These
assignments are shown by the model.
-------
- 185 -
4. A rail-haul alternative would cost about 12 percent more to
operate than the present system and about 18 percent more
than the system with a transfer facility. Haul distance
would have to increase an average of from 3.5 to 5 miles
for rail-haul to be favorable without transfer, and from
14 to 18 miles to be favorable with transfer.
5. The cost of changing from two times a week frequency of
collection to three times a week is difficult to estimate
because of the sensitivity of this calculation to estimates
of how much the waste load would be with three times a week
collection. Estimates of the added cost range from 4.5 per-
cent if there is no increase in the waste load, up to
21.5 percent with a 15 percent increase in the waste load.
All of these figures are based on the assumptions that
routes for vehicles under three times a week collection be
redesigned for efficiency purposes. It is strongly advised
that more studies of the waste load question in this region
be carried out before any firm decision be made on changing
collection frequency.
6. While differences in assumptions make estimating the cost of
some programs difficult, the site selection B, for a transfer
facility is remarkably insensitive to parameter change. Re-
gardless of the collection frequency, site B is the best site
for the transfer facility.
-------
- 186 -
7. The system shows some sensitivity to collection rates,
which indicates that care should be taken in measuring
them and investigation of means of altering them will be
of some help.
8. If for some reason site B could not be used, site C first
and then site A are good alternatives, and it would cost
little extra to change the selection to them. The effects
of regionalization are such that the northwestern division
is better operated as one division than as two. It is
further expected that extension of this type of analysis
to the entire city might show even greater efficiency with
transfer, and this is recommended as the next step in the
analysis procedure.
9. The amount of computer time necessary for this analysis of
60 runs was 45 minutes, using the IBM 7094. At commercial
rates of $500 per hour, this represents a cost of
approximately $375.
-------
- 187 -
CHAPTER VI. CONCLUSIONS AND EXTENSIONS
The goal of this thesis has been the development of tools to
gain a better understanding of a large-scale public system. Thus
it is on the basis of the results of the example rough analysis of
the Baltimore, Maryland, solid waste collection system in Chapter V
that the success of such an undertaking should be measured. While
most of the data used for the analysis were less than elegantly
obtained, a firm body of facts and conclusions emerge from the
exercise. Answers to many of the basic questions with which the
analyst is concerned were found. Most important, a feeling for the
sensitivity of the system to many of its parameters was established.
The decision to change from twice a week to three times a week
collection was shown to be quite sensitive to estimates of waste
generation under the two regimes. Thus, it is recommended that
additional study in this area be carried out before a decision is
made about a policy change. On the whole, however, the problem of
choosing transfer facility location appears to be quite stable, with
the same location being elected under a severe change in system
conditions.
Some drawbacks in the analysis were encountered because of
the need to subdivide the problem in order to solve it. At one
point it was necessary in the study of facility location to assume
that the new routes for vehicles would be set up efficiently if
service policy whould change. However, the model could not
-------
- 188 -
determine how this was to be done, and the problem would have to be
looked at as a separate vehicle scheduling problem as described in
Chapter IV.
From a computational point of view the analysis in Chapter V
was a success. Sixty different problems, each involving generating
data for forty waste sources and considering nine intermediate
alternatives, were solved in about three-quarters of an hour on the
IBM 7094. This represents a cost at commercial rates of less than
400 dollars, or about two weeks' salary for a medium level
engineering analyst. In terms of the information generated, it
seems like a considerable bargain.
Looking at the individual models developed, the large-scale
"flow of goods" models developed for the facility location problem
of Chapter II and the multi-commodity truck assignment problem of
Chapter III proved to be the most successful. When programmed for
the computer, they were of sufficient size and speed to handle a
very large complex system and find solutions quickly. Since much
of the value of the models is in repeated solution with changing
parameters to determine sensitivity, efficient solution time is of
great importance. The vehicle scheduling models of Chapter IV do
not display the same qualities. People working in this field have
uniformly found that securing an optimal solution to even a small-
scale problem in a reasonable amount of time was difficult to
impossible. Although the author's work in a problem area of this
general category extended theoretical concepts involving the use of
-------
- 189 -
more than one terminal, the same type of problem occurred. Thus,
there are no existing optimization techniques that will allow the
investigation of a city-sized routing problem. The development
of heuristic methods has advanced, however, and feasible solutions
for quite complex problems can be found quickly. No one has yet
investigated the difference between a good feasible solution and
an optimal solution in vehicle routing to determine if the search
for optimal procedures is worthwhile. Meanwhile, sensitivity
analysis using heuristic rather than optimal procedures must be
viewed with extreme caution and care.
Perhaps the problems of routing would benefit from a shift
in emphasis from discrete problems to continuous problems. Vehicle
scheduling is viewed as a problem of finding routes between
discrete points or in terms of a network example, in finding which
arcs to travel to visit all nodes. The rapidly increasing
combinatorial nature of the problem is what makes computation of
optimal solutions so difficult. Studying public services in city
street networks would reveal a continuous distribution of demand
along an arc with a requirement that all arcs be traveled. For
certain cases, this turns out to be a problem that is remarkably
easy and quick to solve. The Chinese postman problem asks how a
continuous route for one vehicle can be found through a network
that travels all arcs and minimizes total distance traveled. The
extension of these techniques to problems of more than one service
-------
- 190 -
vehicle, each with a capacity constraint, while retaining the
property of efficient solution would mean a dramatic increase in
the type of analysis done on vehicle routing in solid waste
collection.
The overall conclusion of this thesis is that models such
as developed, limited though they may be by applying only to sub-
problems of the total collection system, can still provide a
great deal of insight into the system. The types of questions
amenable to study using these techniques, provide a wealth of
information to the decision maker charged with the operation of
the system. It is hoped that such models will become increasingly
valuable tools in the management and planning of large-scale solid
waste collection systems.
-------
- 191 -
BIBLIOGRAPHY
Anderson, L. E., A mathematical model for the optimization of a
wastes management system, Sanitary Engineering Research Laboratory,
University of California. Berkeley, SERL Report 68-1. February 1968.
Andrew, G. M., and J. R. Hamann, Truck routing: a branch and bound
solution, mimeo, presented at the meeting of the Operations
Research Society of America, September 1967.
Anonymous, California waste management study: report to the State
of California, Department of Public Health, by Aerojet General
Corporation, Azuza, California, 1965.
Anonymous, The annual report of the Department of Public Works for
the year ending December 31, 1965, Department of Public Works,
Baltimore, Maryland, 1966.
Anonymous, The applicability of a systems approach to solid waste
management problems, report presented to the Maryland State
Department of Health, Division of Solid Wastes, by Management
Technology, Inc., July 1966.
Anonymous, System 360 vehicle scheduling program (360A-ST-06X)
application description, International Business Machines Corp.,
Technical Publications Department. White Plains, New York, 1968.
Anonymous, System 360 vehicle scheduling program - program description
and operations manual (360A-ST-06X), International Business Machines
Corp.. Technical Publications Department, White Plains, New York,
1968.
Anonymous, Refuse disposal via railroads, Public Works. July 1968.
Balas, E., An additive algorithm for solving linear programs with
zero-one variables, Operations Research. 13. 517-546, July-August
1965.
Balas E., Discrete programming by the filter method, Operations
Research. 15. September-October 1967-
Balinski, M. L., On finding integer solutions to linear programs,
Mathematica. Princeton, N. J., 1964.
Balinski M. L. Integer programming: methods, uses, computation,
Management Science, 12. November 1965.
-------
- 192 -
Balinski, M. L. , and R. E. Quandt, On an integer program for a
delivery problem, Operations Research, 12, 300-304, 1964.
Barton, R. A., and R. J. Gumaer, The optimum routing for an air
cargo carrier's mixed fleet, presented at the Sesquicentennial
Forum on Transportation Engineering, New York, N. Y., August 28-
30, 1967. American Society of Mechanical Engineers, publication
67-TRAN-18.
Baumol, W. J., and P- Wolfe, A warehouse location problem, Operations
Research. 6. 1958.
Bellmore, M., List processing subroutines, mimeo, The Johns Hopkins
University, February 1968.
Bellmore, M., and G. Nemhauser, The traveling salesman problem - a
survey, Operations Research, 16, May-June 1968.
Benders, J. F., Partitioning procedures for solving mixed variable
programming problems, Numerische Mathematik, 4, 238-252, 1962.
Berge, Claude, The theory of graphs and its applications, John Wiley
and Sons, Inc., New York, 1966.
Black, R. J., The solid waste problem in metropolitan areas,
California Vector Views, 11, September 1964.
Bomberault, A. M., and W. W. White, Networks and transportation:
the empty freight car allocation problem, IBM New York Scientific
Center. Technical Report No. 320-2952, July 1968.
Clarke, G., and J. W. Wright, Scheduling of vehicles from a central
depot to a number of delivery points, Operations Research Society
of America, 12, 568-581, 1964.
Clasen, R. J., The numerical solution of network problems using the
out-of-kilter algorithm, The Rand Corp.. RM 5456-PR, Santa Monica
California, March 1968.
Coyle, R. G., Ph.D. thesis, Bradford University, England, 1967.
Coyle, R. G., and M. J. C. Martin, Case study: the cost minimization
of refuse collection operation, ORSA Meeting, May 1968.
Dantzig, G. B., and J. H. Ramser, The truck dispatching problem,
Management Science, 6. 81-91, October 1959.
Durbin, E. F., and D. M. Kroenke, The out-of-kilter algorithm: a
primer, The Rand Corporation. RM 5472-PR. Santa Monica, California,
December 1967-
-------
- 193 -
Edmonds, J., Maximum matching and a polyhedron with 0, 1 vertices,
Journal of Research of the National Bureau of Standards, B.
Mathematics and Mathematical Physics, 69B, January-June 1965.
Edmonds, J., and E. Johnson, Private communication with
M. Bellmore, 1969.
Efroymson, M. A. , and T. L. Ray, A branch and bound algorithm for
plant location, Operations Research 14, 361, 1966.
Feldman, E. , F. A. Lehrer, and T. L. Ray, Warehouse location under
continuous economies of scale, Management Science. 12, 670-684,
May 1966.
Ford, L. R., Jr., Constructing maximal dynamic flows from static
flows, Operations Research. 6, 419-433, 1958.
Ford, L. R. , Jr., and D. Fulkerson, Flow in networks, Princeton
University Press, Princeton, N. J., 1962.
Fulkerson, D. R., An out-of-kilter method for minimal cost flow
problems, Journal of the Society for Industrial and Applied
Mathematics, 9. 18-27, 1961.
Garfinkel, R. S., and G. Nemhauser, Set covering with equality
constraints, Paper IIG.4, 35th National Meeting, Operations
Research Society of America, Denver, Colorado, July 1969.
Garvin, W. W., H. W. Crandall, J. B. John, and R. A. Spellman,
Application of linear programming in the oil industry,
Management Science. 3, 407-430, 1957.
Geo£frion, A. M., Integer programming by implicit enumeration and
Balas' method, The Rand Corporation. RM-4793-PR, Santa Monica,
California, February 1966. Also published in SIAM Review. 9
178-180, April 1968.
Geoffrion, A. M. Implicit enumeration using an imbedded linear
program, The Rand Corporation. RM-5406-PR. Santa Monica,
California, September 1967-
Glover, F. , A multiphase-dual algorithm for the zero-one integer
programming problem, Operations Research. 13. 879-919, November-
December 1965.
Glover, F., Finding an optimal edge-covering tour of a connected
graph (the Chinese postman's problem), Operations Research Center,
University of California. Berkeley, ORC 67-13, March 1967.
-------
- 194 -
Golueke, C. G., and P. H. McGauhey, Comprehensive studies of solid
wastes management, first annual report, Sanitary Engineering
Research Laboratory, University of California, Berkeley, SERL
Report No. 67-7, May 1967.
Gomory, R. E., Outline of an algorithm for integer solutions to
linear programs, Bulletin of the American Mathematical Society,
64, 275-278, 1958.
Hausman, W. H., and Peter Gilmour, A multi-period truck delivery
problem, Transportation Research. Volume 1. 349-357, Pergamon
Press, 1967.
Hayes, R. L., The delivery problem, doctoral dissertation,
Carnegie Institute of Technology, 1967.
Held, M., and R. M. Karp, A dynamic programming approach to
sequencing problems, Journal of the Society for Industrial and
Applied Mathematics, 10, 196-210, 1962.
Hess, S. W., and Weaver, J. B., Nonpartisan political redistricting
by computer, Operations Research, 13, 998, 1965.
Kuehn, A. A., and M. J. Hamburger, A heuristic program for locating
warehouses, Management Science, 9, 643-666, 1963.
Land, A. H., and A. G. Doig, An automatic method of solving discrete
programming problems, Econometrics, 28, 497-520, 1960.
Liebman, J. C., and D. H. Marks, A Balas algorithm for the zoned
uniform treatment problem, Journal of the Sanitary Engineering
Division, American Society of Civil Engineers, 94, SA4, August 1968.
Little, J. D. C., K. G. Murty, D. W. Sweeney, and C. Karel, An
algorithm for the traveling salesman problems. Operations
Research. 11. 972-989, 1963.
Ludwig, H. F., and R. J. Black, Report on the solid waste problem,
Journal of the Sanitary Engineering Division, American Society of
Civil Engineers, 94, SA2, April 1968.
Mills, G., A decomposition algorithm for the shortest-route problem,
Operations Research Society of America, 14, 279-291, 1966.
Pierce, J. F., On the truck dispatching problem - Part 1, IBM
Cambridge Scientific Center Report 320-2018, Cambridge, Massachu-
setts, July 1967- Revised December 1967.
-------
- 195 -
Pierce, J. F. , Application of combinational programming to a class
of all-zero-one integer programming problems, Management Science,
15_, 191, November 1968.
Pierce, J. F. , Private communication, February 1969.
Pierce, J. F., and D. J. Hatfield, Production sequencing by combi-
national programming, IBM Cambridge Scientific Center Report 320-
2000, Cambridge, Massachusetts, 1966.
Pierce, J. F. , and J. S. Lasky, An improved combinational programming
algorithm for zero-one integer programming, to be presented at the
meeting of the Operations Research Society of America, June 17,
1969, Denver, Colorado, as paper III D.5. Abstract in Bulletin of
the Operations Research Society of America, 17, Sup. 1, Spring 1969.
Quon, J. E., A. Charnes, and S. J. Wersan, Simulation and analysis
of a refuse collection system, Journal of the Sanitary Engineering
Division, American Society of Civil Engineers; 91, SA5 , October
1965.
Quon, J. E. , M. Tanalca, and A. Charnes, Refuse quantities and the
frequency of service, Journal of the Sanitary Engineering Division,
American Society of Civil Engineers, 94, SA2, April 1968.
Quon, J. E. , M. Tanaka, and S. J. Wersan, Simulation model of refuse
collection policies, Journal of the Sanitary Engineering Division,
American Society of Civil Engineers, 95, SA3, June 1969.
Santone, L. , National Bureau of Standards, Gaithersburg, Maryland,
private communication, July 1968.
Skelly, Michael J. , Planning for regional refuse systems, Ph.D. thesis,
Cornell University, September 1968.
Spielberg, K. , An algorithm for the simple plant location problem
with some side conditions, Operations Research, 17, January-
February 1969.
Spitzer, Murray, The computer art of schedule making, Datamation,
84-86] April 1969.
Szwarc W. , The truck assignment problem, Naval Logistics Review
, 529-557, 1967-
Truitt, M. M. , J. C. Liebman, and C. W. Kruse, An investigation of
solid waste policies, Department of Environmental Engineering
Science, The Johns Hopkins University, Baltimore, Maryland,
August 1968.
-------
- 196 -
Truitt, M. M. , J. C. Liebman, and C. W. Kruse, Simulation model of
urban refuse collection, Journal of the Sanitary Engineering
Division, American Society of Civil Engineers, 95, SA2, April 1969.
Walker, W., Adjacent extreme point algorithm for the fixed charge
problem, Center for Environmental Quality Management and
Department of Operations Research, Cornell University, Ithaca,
New York, January 30, 1968.
White, W. W., Dynamic transshipment networks: an algorithm and its
application to the distribution of empty containers, IBM New York
Scientific Center, Technical Report No. 320-2966, February 1969.
Wolfe, H., and R. Zinn, Systems analysis of solid waste disposal
problems, Public Works, 98. September 1967.
Zandi, I., and J. Hayden, Collection of municipal solid wastes in
pipelines, American Society of Civil Engineers National Meeting
of Transposition Engineering, Preprint #640, San Diego,
California, February 1968.
------- |