UBC Theses and Dissertations
The application of cluster analysis on a post office scheduling problem Wong, Siu-Sik
The application of computerized clustering methods in outlining the truck route boundaries for street letter box collection runs is believed to be an effective tool for use by the Vancouver Post Office. This study investigates and analyses the characteristics, algorithms, and applicability of 12 cluster analysis techniques in grouping sets of two-dimensional data units for the Post Office. A broad view of cluster analysis is presented, including a review of the methodology and the potential problems associated with nine hierarchical and three nonhierarchical clustering methods. Two sets of contrived data and two empirical data sets (consisting of street letter box locations in the Burnaby area) are used to test the suitability of the grouping methods in clustering both evenly and unevenly distributed data units in a 2-dimensional Cartesian space. Computer programs for various clustering procedures are used to generate tree diagrams showing the linkages of the members within each group as well as the membership lists for the four data sets. The results are then plotted onto maps for evaluation. Results of the evaluations, based on group sizes, distributions of distances within groups, and travel times and distances, can be summarized as follows: a. Ward's method and the three nonhierarchical methods are better clustering techniques in grouping evenly distributed data sets; b. the complete linkage method, and the two average linkage methods are more suitable for grouping visually identifiable clustered data units; c. the single linkage methods and the centroid methods are generally less satisfactory in grouping all four sets of data; and d. clustering techniques provide a useful tool for outlining the route boundaries for street letter box collections. A comparative study for the Vancouver area would substantiate the feasibility of cluster analysis as an aid to solving the scheduling problem.
Item Citations and Data