Kaybee Amusements, Inc. is developing a theme park for the city of Baton Rouge, Louisiana. It is tentatively titled Heritageland; the concept is to build theme areas based on heritages common to six of the cultures that have influenced the Southern and Midwestern regions of the United States: (1) English; (2) French; (3) Spanish; (4) African; (5) German; and (6) Native American. Each of the six theme areas will have a theme restaurant, a cultural center with a 360 degree theater, a stage show pavilion, and amusement attractions. In addition, the park will include a main plaza area with a multicultural atmosphere and a parking lot.
The following map of the park includes all pedestrian corridors between the theme areas, the plaza, and the parking lot. (For example, the distance from the Main Plaza to the Spanish Pavilion is 1250 feet, and the distance from the Spanish Pavilion to the Native American Pavilion is 1850 feet.)
Click here for Network Diagram
One of the proposed attractions is the Far West Streetcar Line, which, for a fee, will transport visitors in streetcars powered by underground cables. Because of costs, the park will only run seven streetcars, each starting in one theme area, traversing to a second area, and then returning to the original one through the same corridor. Each streetcar ride will move directly down the center of the pedestrian corridor running between the two theme areas. Kaybee would like to use the minimal distance of underground cable while enabling patrons to travel to any theme area, the plaza, and the parking lot via street cars.
For those who prefer a more modern form of transportation, a circuitous monorail system will be constructed to provide transportation among all areas. The links for the monorail system among areas will be constructed directly above pedestrian corridors. The monorail system will start at the parking lot and visit each theme area and the plaza once before returning to the parking lot for another run. To conserve costs, the minimum distance monorail line should be constructed. (This part is for Extra Credit only.)
Finally, for those who prefer walking (or do not wish to pay for the other modes of transportation within the park), the park will provide every visitor with a welcome brochure. One page in the brochure will include a map, together with a table showing the visitor how to get "From Here to There" in the shortest walking distance, as well as the shortest walking distance itself.
Prepare a report for Kaybee Amusements suggesting the design of the most cost-effective streetcar (and, for extra credit, monorail) routes. Also provide the copy for the page entitled "From Here to There" in the welcoming brochure that gives visitors the routes of shortest distance between any two theme areas, the plaza, and the parking lot.
DIRECTIONS
1. Do the streetcar design by hand. This is a minimal spanning tree problem. Show the step by step construction of the minimal spanning tree in your appendix, and show a diagram of the streetcar design in your Executive Summary, noting the total distance for all links.
2. Do the shortest route analysis by hand, generating 8 shortest route spanning trees by hand, one tree for each starting node. These go in your Appendices. Transcribe the results into a single "From Here To There" table which shows both distance and route from any point in the park to any other point in the park.
3. As a reminder, your project report has two parts: Executive Summary and Appendices. The Executive Summary contains a description of the problems solved, the solution methods used, and the principal results in a form the non-technical "boss" can understand. The Appendices contain supporting information and intermediate results obtained. The Appendices should be named or numbered so that they can be referred to at the appropriate points in the Executive Summary.. Please, no handwritten reports. You are supposed to be using computer tools for the reports as well as the computations.
EXTRA CREDIT - 25 points
4. Do the monorail design using the Branch-and-Bound option for the Traveling Salesman Solution in the Networks component of the software program WinQSB (see WinQSB links in Course Content; it is already installed in the computer lab.). Include the computer printouts (inputs, outputs, graphic) in the Appendices. Transcribe the solution onto the original park map for presentation of this result in the Executive Summary. This is the Traveling Salesman Problem, for which no easy hand solution is available.
