Math 300 Writing for Mathematics, Spring 2002, Exercise 2

In this essay You will analyze several different proposals and on the basis of your analysis provide a recommendation. Imagine that you are an analyst working for a company and that you are writing a memo to be read by your boss. Your boss has a mathematics background similar to that of the audience of your first essay: good knowledge of high school algebra but no knowledge of calculus.

Background: You work for Chicago Cargo Company (CCC), which is a small package delivery company. Each day they deliver packages to n different addresses within the Chicago area. On a typical day n=50 and the addresses change from day to day. One driver makes all these de]liveries. The packages and addresses recollected during the night. The driver starts driving at 9am. At each address it takes the driver about three minutes to leave the truck and drop off the package. The route the driver takes depends on the addresses of the packages that are to be delivered that day. In recent months CCC has used three different ways to select the route that the driver will take.

Exhaustive Method. A computer program considers all n! possible routes and using data about traffic conditions and travel times, chooses the route that will minimize the total travel tune to go from the warehouse to all n addresses and then return to the warehouse. If this method is used, then it typically takes the driver about 5 hours to complete the route if there are 50 addresses.

Greedy Method. A computer program uses a greedy algorithm to find a route. If this method is used, then for 50 addresses the elapsed time it takes the driver to complete the route is about 6 hours.

Method. No computer is used to select a route. An experienced driver selects a route based on the list of addresses. For 50 addresses it takes about 7 hours for the driver to complete the route. The expense for paying the driver and operating the truck is approximately $40 per hour. CCC pays a vendor for running the computer programs that find the route. This is expensive proprietary software since it computes travel times between arbitrary points for all times during the day based on the latest traffic data.

For the Exhaustive Method the charge for processing n addresses is .00001(ceil(n/.5))! + .4*(ceil(n/5))^2 dollars, where ceil(n/5) stands for the smallest integer at least as large as n/5. Thus for n=50 this gives a charge of .00001 x 10! + .4 x 100= 36+40=76 dollars. For the Greedy Method the charge for processing n addresses is 0.7*(ceil(n/5))^2 dollars.

CCC wants to expand the business and deliver about 100 packages per day instead of 50.The boss suggests thee following proposal for doing this. If the Exhau1stive Method takes a driver 5 hours to deliver 50 packages, then it should not take more than 10 (=2x5) hours to deliver 0 (=2x50) packages if we use the Exhaustive Method with n=IOO. One driver could do this in a long day. So the cost would be roughly double what it currently is for 50 addresses.

The boss's son has studied some geometry and has a different proposal. The son observes that currently50 packages are delivered by one driver who drives allover Chicago. He proposes dividing Chicago into two equal-sized regions and hire two drivers instead of one. Each driver would deliver about 50 packages in one half of the Chicago area. Since the area covered by each driver is one-half of all of Chicago, the length of the route for 50 addresses would be scaled down to one-half of the length of the path if all of Chicago were covered. So one driver can cover 50 addresses in this region in half the time it would take if they were spread allover Chicago. So two drivers could deliver to 100 addresses in this way in the same amount of time intakes to deliver to 50 addresses under any of the three current methods. So the cost of delivering to 100addresses under this method would be roughly the same as delivering to 50 addresses.

In your memo you are to analyze what the actual costs would be for these various proposals. In particular you should determine what the cost is for 50 addresses under each of the three current methods. Next, estimate what the cost would be for the boss's proposal in which n=100 and one driver works a long day - do this for each of the three methods. Then consider the son's proposal in which Chicago is divided into two equal sized regions and two drivers each get 50 addresses in each region. Again do this analysis for each of the three methods and determine the total cost for each.

Your essay will be a report to your boss on your analysis and will contain a recommendation as to what CCC should do. You'll need to explain with tact and care how you arrived at your conclusions since you will certainly come out against either the boss's proposal or the son's proposal, and possibly against both. Youmay find that there are errors in reasoning in the boss's or the son's proposal. So you will need to clarifyand correct these errors. Given the limited mathematical background of the audience for your memo youmight want to put long computations in an appendix rather than include them in the main part of the text.An explanation of the two computer algorithms and the associated cost functions will be given in class.The problem of finding a short route is called the Traveling Salesperson Problem and algorithms for it are presented in most books on computer algorithms. There will also be a discussion of the son's geometric scaling argument in class.

Additional, optional topics that you might want to include are:1) your own proposal for a cost-efficient way for CCC to handle 100 packages per day; 2) how CCC might handle 1000 packages per day; 3) in the son's proposal, how might the cost of an additional delivery truck be entered into the computation.