Mathematical Modeling (Urban Operations Research) (Summer 2018)
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
Mathematics has an impressive record of being useful. As a small sample, it's useful for making compact cell phones, streaming video, designing bridges, getting spacecraft to land on a comet, scheduling airplanes, predicting the weather, helping governments make money off running lotteries, and blending gasoline. Perhaps this is surprising because in school one typically only sees mathematical techniques and algorithms - procedures to multiply fractions, methods to solve linear and quadratic equations, etc. If one sees "applications" at all, sometimes they seem very artificial. This divide between the theory of mathematics and putting mathematics to use in the world is sometimes described as the difference between theoretical and applied mathematics.
The branch of mathematics which is concerned with using mathematics "outside" of mathematics, sometimes ironically referred to as the real world, is known as mathematical modeling. While theoretical aspects of mathematics are usually developed by professional mathematicians or hobbyists, mathematics modeling is often carried out by people with mathematical training but often by individuals who would not call themselves mathematicians. People in the business world and government, for example, use and invent new mathematical models all of the time.
The purpose of the "situations" below is to both allow for the opportunity to practice the doing of mathematical modeling, but also to inform you about the kinds of situations where mathematics can be put to use.
Let us consider several problems, all of which will use as "input data" the diagram above.
A contractor located at B has been hired to check the streets in the urban area shown above for potholes. All the street segments shown will take the same time to traverse. The contractor wishes to traverse (walk) each segment of street at least once and return to B, following a route which will minimize the total amount of time for the inspection. What is this minimum amount of time?
(As part of your solution, explain why it is not possible to traverse each section of street once and only once on a tour that starts and ends at B.)
You live at A and must run errands by foot that take you to the sites B, C, D, E, and F in any order you might want, and then return to A. What route makes the most sense? How far do you have to walk to achieve your "best" result? Are there different routes that are "best," and if so, how many are there?
A company must lay cable to connect up the sites A, ..., F so that messages can be sent between any pair of sites by relay if necessary. Thus, if cable is laid from A to B and B to C, it does not have to be laid between A and C because one can relay a signal from A to C via B. If the cost of laying cable is proportional to the "distance" between two sites, what site pairs should be joined to minimize the cost of providing the cable service between the sites?
Students live at sites A, ..., F. A teacher wishes to group the students in pairs for the purpose of working on projects. If X and Y are paired it is assumed that X will walk to Y's house or the other way around to work together. What pairing will minimize the "average" distance that must be walked to have the students work together?
There are apartment blocks (or single family homes at A,...,F. Where would be an optimal location to place a mobile medical facility which would:
a. Minimize the maximum distance that it would take to reach the mobile facility.
b. Minimize the total distance from all of the locations (A-F) to reach the mobile medical facility.
For each of the Situations 0, 1, 2, 3 and 4 above, give as many examples of "real world situations" as you can which seem to you to be similar to these.
Suppose you have described a group of problems which appear to you to be similar to Situation 1. Now for each of these problems explain how you think the problem is like Situation 1 and how you think it differs from Situation 1. Carry out this same process for the problems you found similar to Situation 0, 2, 3 and to Situation 4.
Make up a new problem of your own invention based on the diagram and information implicit in the diagram given at the start. Perhaps you may want to ask that more information be added to the diagram to make up your problem. For example, you might want to know if there are traffic lights at any of the corners, or in what directions the automobile traffic can move on the streets shown.
The activities above can be treated at a variety of grade levels. Solving the problems that arise from these situations involves making assumptions about the information that has been provided. The purposes of the activities include:
a. Using a graph to help construct a mathematical model of information that comes up in everyday life.
b. Using a matrix to help construct a mathematical model of information that comes up in everyday life. (The matrix can be used to "store" the information which gives the taxicab or the Euclidean distance between the lettered points in the diagram.)
c. The difference between taxicab distance and Euclidean distance.
d. Situation 0 leads to the important mathematical model known as the Chinese Postman Problem. This problem generalizes ideas used by Leonard Euler in 1736 to solve the Königsberg Bridge problem, and gave birth to a geometrical set of ideas known as graph theory. This problem involved the question of whether or not a collection of bridges joining various river banks and an island could be traversed once and only once. Although this problem may not seem of much interest to urban students, when set as an operations research problem that involves municipal services, it often catches their interest.
e. Situation 1 leads to the important mathematical model known as the traveling salesman problem (TSP). While this small problem can easily be solved by trial and error, large versions of the problem have been shown to belong to a class of computationally difficult problems. However, various easy "heuristics" (e.g. fast procedures that do not guarantee optimal answers) are often "rediscovered" by students. Common names for these heuristics are "nearest neighbor" and "sorted edges."
f. Situation 2 leads to the important mathematical model known as the minimum cost spanning tree (MST) problem. This problem can be solved by trial and error but there are variants of the heuristics listed above that lead to "fast" algorithms for this problem. These algorithms are know as Kruskal's and Prim's methods. There is also a lovely "parallel" algorithm known as Boruvka's method which also will solve this problem.
g. Situation 3 leads to the important mathematical model known as the minimum weight matching problem. This problem can be solved by trial and error here but although it is known that there is a "fast" algorithm to solve the problem, it is rather involved. Special cases of this problem can be solved more easily and involve ideas about shortest path algorithms in graphs.
h. Situation 4 has connections to ideas in statistics. The ideas of range, midrange value, mean, median and mode can be discussed. It belongs to a class of problems known as facility location problems. One needs to decide what distance function is most appropriate and also which optimization objective should be used. What adjustment might make sense if there are different numbers of people located at A,...,F?
a. The "HOP ON-HOP OFF" bus company wants to design a simple circuit C (which does not pass through a dark dot point) of grid points with the shortest length, so that the sum of the distances from the dark dot points in the grid graph above to some point of C is as small as possible. Find C, and what is the value of the sum of the distances for this choice of C?
b. Find a short simple circuit C' so that instead of the sum of the distances from the black points being minimized, the maximum distance from a point on C' is minimized. How does the length of C compare with C'?
c. Discuss variants of the problems above, perhaps where C goes through some dark dot points,