Case Study: Arc Routing
The Bridges of Konigsberg 1) Was there ever a date at which an Eulerian walk over the steel bridges of Konigsberg were possible, without using any wooden bridges? If so, when? If not, show that it was never possible.
For a Eulerian walk to be possible two conditions must hold a) The undirected graph must be connected b) Each node must be of even degree.
Name of the bridge | Date built | Honey Bridge (7) | 1879-1882 | Slaughter Bridge (3) | 1886 | Blacksmith’s Bridge (4) | 1896 | Salesman Bridge (1) | 1900 | Timber Bridge (5) | 1904 | Emperor’s bridge (8) | 1905 | Green Bridge (2) | 1907 | High Bridge (6) | 1937 | …show more content…
6) What objectives were taken into account in the CASPER system?
The objective was to minimize cost by reducing the number of routes and reducing the deadhead miles travelled, while meeting specified service levels and maintaining class continuity.
7) What are the two major phases in the heuristic used in the CASPER system?
Arc routing in CASPER was done in two steps a) Heuristic route generation algorithm b) Interactive tabu search based route improvement heuristic
8) Discuss the case studies described in the chapter
GeoRoute was used to optimize snow removal activities in these case studies
Ottawa Canada: This case study reports the analysis performed by the PSR group and the city wide costs and savings identified from the implementation of a winter long field trial.
They compared the original route with the revised route and optimized route. The revised route was done by simply re-allocating the arcs in the original route. The optimized route was calculated according to the optimal policy.
The optimized routes showed good improvements. The total plowing time decreased from 165.6 hrs for the 24 original single routes and to 114 hrs for 19 single optimized routes. Projected savings were 17 per cent of the hired plow hours per storm which equated to