ISyE 6203 Transportation and Supply Chain` Systems Spring 2013 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| At no point in time do the above two conditions hold, therefore it is never possible to do an Eulerian walk in the steel bridges of Konigsberg. 2) Consider the current situation in Kaliningrad (with the Estacada connecting Altstadt and Vorstadt, but not Kant Island, and with bridge 10 not connected yet). What bridge(s) would you construct to make an Eulerian walk possible? All the nodes are connected as of now. We have to add one more bridge between nodes A and L to make all the nodes have even degree. So, add a bridge between Altstadt and Kneiphof.
Roadway Snow and Ice Control 1) What factors contribute to the complexity of roadway snow and ice control problems? There were tremendous variations in the RSIC operations themselves due to differences in climate, level of service, network complexity and size. a) Weather conditions (temperature, wind precipitation type and amount , accumulation rate, total accumulation etc. ). b) Traffic conditions were also dynamic and had a strong effect on the snow removal operations. c) Types of roadways encountered – different mixes of roads – one lane roads, two lane roads, multi lane roads, alleys, gravel roads etc. ) Policy decisions and operational decisions also added to the problem complexity. For eg, should you consider a two lane road as two directed arcs, or as a single undirected arc. 2) What idealized arc routing problems have been used for roadway snow and ice control? Idealized models treat RSIC problems as a variant of a) Chinese Postman Problem b) Rural postman problem c) Capacitated Arc Routing Problem d) Sometimes node routing problem instead of arc routing problem 3) What reasons are given for the problems encountered when attempting to implement routing software for roadway snow and ice control?
Inability to consider all the nuances of real world operations. Poor implementation and user unfriendly software, distrust of computer based (black box) approaches by public work personnel, unappreciated operational complexities. 4) What bene? ts were contributed by early roadway snow and ice control software? They focussed attention on savings from better routes. They recogonized the importance of savings from using a rational and analytical approach to fleet size and service level. For eg. , the SnowMaster system provided a major advance in the trend towards optimization by encouraging user involvement in route design. ) Explain the relationship between the duration of a route and the service level provided to the road segments on the route. Service level is the time limit for traversing a route. Trucks usually travel at 20 mph while servicing and 40 mph while deadheading. So, it might not be possible to satisfy a route which is very long. The service level can be thought of as the deviation in route time from a target time. The target level is usually specified as range and different classes of routes may have different service level requirements.
You can penalize very long routes to increase the service level (frequency of getting serviced). 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 ) 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 $150,000/ year or @ 15,000 per storm. Suffolk County, UK : Planning of routes was done manually in Suffolk County prior to 1996, PSR group was hired to design new routes according to GeoRoute and to explore whether computerized analysis combined with geographically accurate network databases could proved an alternative to manually designed routes.
The cost of route redesign was estimated to be GBP 70,000 including staff time and software time. The cost of manually redeisning would have been GBP 30,000. Manual solutions would have produced less sufficient routes and prevented evaluation of different levels of service. Total saving GBP 22,000 to GBP 44000 per year depending on the service. 9) What technological advances are identi? ed that will a? ect roadway snow and ice control in the future?
Road Weather Information System : Using pavement based sensors that collect, monitor and communicate weather and pavement information real time . This could result in dynamic routing for RSIC to treat only those areas that need it at that time. Truck mounted pavement sensors could help to determine when and how to treat a road. It could also have electronic spreader contrls that can adjust the amount of materials being spread based on vehicle speed and store data on spreading for later.
Anti icing is a preventive approach to RSIC, by spreading chemicals prior to start of ice and snow. Good routes for anti- icing may or may not coincide with good routes for plowing and spreading during a storm. Automatic Vehicle Location using GPS technology can be used to track and monitor and give real time data on vehicle status and location. It can help to reallocated the equipment and personnel in real time and better inform public about current operations, verifications of work completed and identification of unauthorized travel.
Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.
You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.Read more
Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.Read more
Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.Read more
Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.Read more
By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.Read more