An application of calculus: finding optimal road networks

academics calculus math
By Jane

Suppose that we have many towns spread across the country and we are trying to connect them with a network of roads. If we would like to do so by laying as little road as possible, how do we do it? In this blog post, we will use Calculus to tackle a special case of this optimization problem.

The case of four towns arranged in a square

Let us suppose that we have four towns arranged so that they form the four vertices of a square. Our task is then to connect them by the shortest network of roads possible so that each town is still connected to each other town. To make our problem more concrete, let us label our four towns A, B, C, and D, and assume that they are at the vertices of a square with side lengths 1 each.

Screen Shot 2019-09-17 at 2.34.02 PM

 

Our first guess for such a road network might be to just join the four towns by a road network consisting of the four edges of the square. Four edges at length 1 each give a network of total length 4.

We then quickly notice that one of our roads is superfluous. If we remove any one of our four roads, we get a road system of length 3 that still connects our four cities.

 

Screen Shot 2019-09-17 at 2.34.42 PM

 

We might assume that we are done now, but a little thinking outside of the box can get us a more efficient road system. The key insight here is that we could add extra junctions that aren’t cities. For example, something like this:

 

Screen Shot 2019-09-17 at 2.35.30 PM

 

Reasoning Our Way to the Ideal Configuration of Roads

 

It turns out that a similar pattern of roads will be the most efficient way of connecting our four cities. To see why, we could imagine that we had an optimal configuration of roads. Clearly, this set of roads should never venture outside of our original square as that would be suboptimal. There must be a path connecting city A to city C, and a path connecting city B to city D. These paths must cross each other at least once but may do so many times. Let us call the first time that they cross point P and the last time that they cross point Q. Then, our network must have just consisted of the straight segments AP, BP, PQ, QC, and QD, as any other such network would have been longer.

 

Screen Shot 2019-09-17 at 2.36.09 PM

 

We can also convince ourselves that an optimal road system should be vertically and horizontally symmetric, so our optimal network of roads must look something like this.

 

Screen Shot 2019-09-17 at 2.36.56 PM

 

Most Efficient Road System Using Calculus

 

We suppose that the amount of inset of the center joining road from each side of the square is x. Then, our goal is to find the x that minimizes the total length of the road.

As with most calculus minimization functions, our process has three steps:

  1. Find the function ƒ(x) that we need to minimize.
  2. Find the first derivative ƒ'(x) and set it equal to zero. The minimum must occur at one of the zeroes of ƒ'(x).
  3. To test which zero is the minimum, we can then use the second derivative test. A local minimum occurs when ƒ"(x) > 0. Alternatively, we can check is the first derivative is negative right before our zero and positive right after our zero.

Step 1: Finding the function that we are minimizing

The middle portion PQ of our road system has length 1 - 2x and by the Pythagorean theorem, each of the other pieces AP, DP, QB, and QC has the following length:

Therefore, the function that we are trying to minimize is:

 

We notice that given the setup of our problem, the domain of our function is 0 ≤ x ≤ 0.5 since an x smaller than 0 would give a road system that exits the square and an x greater than 0.5 would give a negative length for one of our roads.

Step 2: Finding the zeroes of the first derivative

Now that we have our function, we have a calculus problem on our hands. To minimize the total length, we find the first derivative, set it equal to zero, and then solve for x.

 
 
This gives us the following:
 

Step 3: Checking if we have a minimum

We can ignore our zero at x = -1/(2√3) since this is outside the domain of our function.

We then want to check that our zero x = -1/(2√3) is a minimum to our function. We can see this by testing a point less than and greater than our zero. For example, we can see that ƒ'(0) < 0 and ƒ'(10) > 0. Since the first derivative goes from negative to positive near our zero, we know that we have a minimum. This also helps us conclude that the minimum does not occur at one of the boundary points of our domain, 0 or 0.5, since the function decreases and then increases as it traverses this domain.

Substituting x = -1/(2√3) back into ƒ(x), we get that ƒ(x) = 1 + √3, the minimum amount of road needed to connect our four cities. With a little further thought, we can even see that the optimal placement of roads occurs when the junctions at P and Q are placed very symmetrically: when each of the three angles based at P or Q has measure 120 degrees. 

Voila! We have successfully used calculus to build the most efficient road network connecting our four towns.

Comments

topicTopics
academics study skills MCAT medical school admissions SAT expository writing college admissions English MD/PhD admissions strategy writing LSAT GMAT GRE physics chemistry math biology graduate admissions academic advice ACT interview prep law school admissions test anxiety language learning premed MBA admissions career advice personal statements homework help AP exams creative writing MD study schedules test prep computer science Common Application summer activities history mathematics philosophy organic chemistry secondary applications economics supplements research 1L PSAT admissions coaching grammar law psychology statistics & probability legal studies ESL CARS SSAT covid-19 dental admissions logic games reading comprehension engineering USMLE calculus PhD admissions Spanish mentorship parents Latin biochemistry case coaching verbal reasoning DAT English literature STEM excel medical school political science skills AMCAS French Linguistics MBA coursework Tutoring Approaches academic integrity chinese letters of recommendation Anki DO Social Advocacy admissions advice algebra art history artificial intelligence astrophysics business cell biology classics diversity statement gap year genetics geometry kinematics linear algebra mechanical engineering mental health presentations quantitative reasoning study abroad technical interviews time management work and activities 2L DMD IB exams ISEE MD/PhD programs Sentence Correction adjusting to college algorithms amino acids analysis essay athletics business skills careers cold emails data science dental school finance first generation student functions graphing information sessions international students internships logic networking poetry resume revising science social sciences software engineering tech industry trigonometry writer's block 3L AAMC Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian Lagrange multipliers London MD vs PhD MMI Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture argumentative writing art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser campus visits cantonese capacitors capital markets central limit theorem centrifugal force chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism escape velocity evolution executive function freewriting genomics harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports linear maps mandarin chinese matrices mba medical physics meiosis microeconomics mitosis mnemonics music music theory nervous system neurology neuroscience object-oriented programming office hours operating systems