California State Capital dome (2/2007) |

**EVERY**so often I get asked really interesting questions that I'm not sure how to answer. I have to pause and think about the question, and then come up with an approach that will answer it.

Here's a question like that.

It involves trying to figure out the best place to live between different locations. You can think about it as trying to find the place that's nice and quiet--and maximally far from big city centers (the "blast zones"). Or you can think of this question as trying to find a place that minimizes the distance you have to travel to the city centers.

Imagine it this way: Suppose you have 4 cities that you want to visit regularly. Say, the capitals of California, Washington, Montana, and Nevada. (If you want, imagine that you have franchise businesses--or family members--in each of those locations and need to visit each place once a month. How can you minimize travel time between the locations? To simplify the problem, assume you'll drive from place to place.)

This gives us our question for the week:

1. Can you find the place that's "in the middle" of all four cities? (The capitals given above.)That is, find the place you'd like to live that's equidistant from all four city centers. (Feel free to ignore curvature of the Earth effects.)

Obviously, there's not a simple query that's going to solve this for you.

You'll have to step back and ask, "How CAN I solve this problem?"

Hint: You're probably going to use a map... but how?

I'll give another hint tomorrow (along with some thoughts about collections).

When you post your solution, be sure to say HOW you figured it out. (Just sticking a pin in the map roughly in the middle isn't the kind of solution I'm looking for...)

For today, enjoy thinking about this research Challenge!

Search on.

I know that there are several apps on iOS and Android that help people choose a meeting location that is in the middle so that no one has to drive longer than the other person. Began by searching for an online tool [ travel equidistant tool ] to

ReplyDeleteLet's Meet in the Middle looks good as a nice small town with outdoor activities and equidistant from all the relatives.

I inputted the 4 capital cities. Let's Meet In The Middle focuses on finding restaurants and I thought this would be a good gauge of finding a place to move to. LMITM returned 3 results. Ed's Fast Break Grill in Hines, OR also close to Burns, OR (pop. 2,729) and Malheur Lake.

Good day,

ReplyDeleteDr. Russell, fellow SearchResearchersSearched:

I was thinking about this SearchResearch Challenge and how to solve it.

My first thought was trying some of the Industrial Engineering techniques. Then I realized that a much simpler answer could be found.

This is what I did:

Searched for the capitals of California, Washington, Montana, and Nevada.

[California Capital] A. Sacramento

[Washington capital ] A. Olympia

[Montana capital] A. Helena

[Nevada capital] A. Carson City

[Find middle points between locations]

Let's Meet in the Middle

Site mentions: Finds the exact point that lies halfway between two or more places. Find your personal center of gravity--the geographical average location for all of the places you have lived in. See the results on a Google Map.

< Google Map with location

AnswerDon't know if this is the answer Dr. Russell is looking for. It was so easy so I think it is not.

1. Can you find the place that's "in the middle" of all four cities? (The capitals given above.) That is, find the place you'd like to live that's equidistant from all four city centers. (Feel free to ignore curvature of the Earth effects.)

A: Latitude:42.84476

Longitude:-119.04738

If we search for Center of minimum distance:This method uses a mathematical algorithm to find the exact point that minimizes the total travel distance from all locations in 'Your Places'.

Calculation Methods

Center of minimum distance: Latitude:39.98705 Longitude:-120.05832

nice find Ramón on the Fortune article… thought you would find this interesting too -

DeleteUPS Orion The Traveling Salesman Problem - Pogue "browning up"

this clears it up ;-⦘

Reducibility Among Combinatorial Problems, Karp

TSP, LS

I think the answer to this question depends on whether you or not you are a crow. If you are, you would probably want to choose Murphy, Idaho. If not, Boise would be the city to choose.

ReplyDeleteArriving at the answer to this question was tricky. I already knew all the state capitals, so I didn't need to look those up. I first plotted the four cities on a Google map and tried drawing intersecting lines, but that didn't help me. Then I thought about the headline you gave and thought that drawing intersecting circles would be more helpful. You can't draw circles on a Google map with the incorporated tools, so I searched for [nuclear blast zone calculator], which brought me to http://nuclearsecrecy.com/nukemap/. Unfortunately (although fortunate for the real world), I wasn't able to "blast" the cities in a big enough radius to see where they would overlap.

I searched [draw circles Google map] and found http://www.freemaptools.com/radius-around-point.htm, a tool that lets you draw, color, and resize multiple circles on a map and save the output. After playing around with various distances, I found that a radius of 675 km gave me a nice little zone where all four circles met. Zooming in on the map showed that the only marked town in the area was Murphy, Idaho, although the Idaho state capital, Boise, was just outside. The KML file I created can be downloaded here if you are interested: http://www.freemaptools.com/download/23072014-p2ufprg6.kml

Going back to my original map, I added Murphy and Boise to it. I used the distance calculator and the Get Directions tool, and I found that the total "crow flight" distance is slightly less from Murphy than from Boise (about 1468 total one-way miles from Murphy as compared to 1492 from Boise), as is the driving distance (total 1881 from Murphy, 2014 from Boise). However, the total one-way travel time from Boise to each of the cities is less than from Murphy (31 hours 13 minutes from Boise, 31 hours 31 minutes from Murphy). I assume this is because Boise is a major city and there is easier access to the highways while Murphy is a tiny county seat with a population of 97, according to Wikipedia. Personally, I prefer a larger city, so I would probably choose Boise anyway, but that's not what the question asked.

I look forward to seeing what other people find.

I remembered that I had presented on a tool that could tell you how far you could drive in a certain amount of time from a location. I was wondering if it could help me check on my previous answer.

ReplyDeleteSearched [ map how far can I drive ] and there on the list was the tool "How Far Can I Drive" on the same site Nancy used.

I went to Google Maps and got driving directions from Sacramento to Burns, Oregon. The shortest route was 495 miles.

Back to How Far Can I Drive and input Option (1) Sacramento, CA (2b) 500 miles. Proceeded with each of the other capital cities and each overlay was added to the map.

The intersection of all four was too far off from Burns, OR, but the answer I would give with this tool is Nampa, ID.

Looking at the options made me think. Is your question about distance in miles or distance in time?

I have no answer yet & came to see what ideas people had. Well I came up with the same capitals as Ramón so that's a start. To add to Fred's comments I am assuming we are driving to each location. I am assuming driving distance based on the shortest distance provided by Google Maps. I see it usually highlights the shortest distance plus route 2 other options. These appear to be based on time & distance which has me wondering how Google maps actually calculates these numbers. I did a quick trial & error method of picking a location from the map but I suspect that a process will do the work for me & much more accurately. I've thought how I would use triangulation/resection in terms of navigation but that doesn't deal with using existing interstates. I've also started thinking in terms of how Google Maps gathers data to create the maps in the first place. Everything is located in relationship to other locations. The maps displays this data visually. So how can we make the data work for us. I am sharing in hopes others may use their ideas as well to come up with an answer.

DeleteEDIT - The intersection of all four was NOT too far off from Burns, OR,...

ReplyDeleteI also looked at Nampa, but I decided I'd rather live in Boise. They are only 21 miles apart.

ReplyDeleteLooks like Doyle CA according to geomidpoint.com.

ReplyDeleteHardest bit for a Limey was finding the capital cities, but Wikipedia helped out.

Tried doing directions between the diagonally opposites, which actually comes close to the suggested Doyle.

But then, would I want to live 4,275 feet above sea level in a tiny village with a mean high of 30 degrees centigrade plus in Summer, no thanks! Let's add some sense into our decision.

Richard

Richard Law

Flying Shavings

Rose Cottage

Farnhill

KEIGHLEY

West Yorkshire

BD20 9BW

phone: 01535632182

Those using Meet in the Middle. Are you able to select "Route Halfway Point" and unselect "Midpoint" since we want the Route for driving purposes? I haven't been able to switch to "Route Halfway Point" on Chrome OS.

ReplyDeleteHope this isn't a double posting. First time I lost my comments using the PC which I rarely use.

DeleteI tried on a PC & discovered by testing that if I put my address & Google's address I could switch between the two modes, but adding a 3rd & 4th location only allows Midpoint Mode. When its in Route mode you see R= Route & the M = Midpoint which can be quite different. So back to the drawing board. I like Fred's method using "How Far Can I Travel" & perhaps I'm not doing it right. The image overlaid you provided certainly makes Nampa Id look ideal. My mileages on Google Maps are telling me another story. I'll give it another look & see what's up.

Riding on the shirt tails of Nancy & Fred I used Murphy Idaho as the centre marker (could have used Nampa ID as well). Then in Google Maps I used directions from Murphy to Helena Mt (mileage 500miles and then Murphy to Olympia (mileage 546 miles, Murphy to Sacramento (mileage 538) and Murphy to Carson City (mileage 423).I hadn't considered using Google Maps in this way. Have a look http://goo.gl/0B0sKA

DeleteSo we have a pretty solid case for Murphy Id but the Carson City leg about 123 miles shorter than the longest route which is significant.

…it's a shirttail train — for grins, modded your map for my preferred location - subjective choice, but I'd prefer the long leg to be Helena — more time to enjoy the Big Sky — I hadn't used the click & drag feature in maps either - handy and gives good info & alts.. How does one quantify zen miles vs regular road miles?

Deletefwiw; Boise is a nice place, but with an AFB - Mountain Home right there, it would be a strong candidate to be ground zero for a nBlastZone?? FIFI - was in Boise, 7/10-13

another factor for the data center locations in Prineville? Hard to be a green center if it is a smoking hole…

version

at any rate, I'm sure DrD will "like" the ID location. qualified like

could Dan be leaving Goo to start a In-N-Out Burger or Slaters

with family members in ID.?

"…imagine that you have franchise businesses--or family members-"…weird, now I'm too hungry to continue to search… if only a drone or driverless car or autonomous robot would bring me a burger…

took a more self contained, intuitive approach… looked at the lat/lons for the capitols and then just estimated a mid-point…

ReplyDeletelanded me here not exactly teeming with suitable communities to move to so zoomed

out and picked a town… given that you wanted to avoid larger settlements, nixed Boise & environs and picked Baker City, OR…

then went to the wiki mini atlas and looked around the area —

considered Bend and Mount Vernon, but decided on

Prinevilleas a suitable compromise… used Wolfram|Alpha to check the distances -this favors Olympia and makes Helena a stretch, but still inside the fuzzy parameters you set out and the spongy preferences I have - besides, like Apple says, "it just works" and facebook seemed to

"like" it too… know this is all probably too subjective & arbitrary, but this approach appealed to the inner Lewis & Clark need to roam an area - maps/tools not withstanding.

The Dalles was too close to Portland and Olympia, the river must have held some appeal for the GoogleGang?

Was encouraged to see that my guess landed me in the same general vicinity as Fred initially selected… found the ⌘F works on the mini atlas map and that helps navigate locales…

fwiw - given current events, seeing DrD headline

"nuclear blast zones"or "Nu-cu-lar" anyway, it makes me fret that the Goo algorithmthat crunches such topics is waving a red ⚑ (as opposed to those on the Brooklyn Bridge)… "Don't be evil, uh, cryptic"

OK used PUBLISH and it Vanished my comment. So will try PREVIEW.

ReplyDeleteA couple of things noticed so far. Dan says we are driving. LMITM says using more than 2 addresses picks the midpoint.

Remember you will be driving over high mountain passes in winter and you'll be stuck behind a Winnybaggo in the summer.

Is this the Chinese Postman puzzle obfuscated by Dan ?

I hope so.

Cheers

jon tU

Route Inspection Problem

DeleteW|A

Eulerian Cycle

glad this is simple…

result:

head…poof

Haring-esque

I wasn't THAT clever, Jon. I was really just trying to find the location that's closest to each of the cities--no traveling involved! (Chinese, Postal, or otherwise.)

DeleteI started my search with [calculate equidistant points map]. Borrowing "equidistant" from the challenge seemed like the best phrasing/keyword for the search. The first result looked promising - geomidpoint.com.

ReplyDeleteConfession, I had to look up the capitals. Just to be sure. I entered in the points and right away noticed that two options were given: calculate a halfway point or find a midpoint. Midpoint was the only option for more than 2 locations. I entered the four cities and the map calculated a midpoint.

Midpoint

Helena, Mt 12:40

Sacramento, CA 8:34

Olympia, WA 8:43

Carson City, NV 6:57

STDEV 2:25

TOTAL TIME 36 h 54 m

AVG 9:13

What? How can that be the best midpoint if one route is over 12 hours and another only 7? So, I manually adjusted the point studying the suggested routes to the midpoint to see if I could find something closer to Helena. Just by studying the map I was able to pinpoint a restaurant with: STDEV 0:45 TOTAL TIME 31 h 24 m AVG 7:51. So, each route is within an hour of the other. You are in the car for 5 hours less overall and your average time is over an hour less.

I believe I read on the site that the midpoint is treated as a center of gravity, as if you lifted the four corners of a blanket and placed a ball in the middle and it rolled to absolute center. From what I'm understanding of the map, not the best way to go about picking a central location. For a quick solution, I opted to study the routes between cities and then varied my "midpoints" to calculate those formulas: standard deviation, total time traveled (adding together total time traveled for one visit to each location), and average time spent in the car.

I zeroed in on Marsing, ID and used the 'search nearby' feature to locate schools, and some commerce (a Red Box). I chose this address/area to move to: 28 1st St S, Marsing, ID 83639

Nicely reasoned. I like it.

DeleteI'm still stuck to Nampa. :)

DeleteA 1029 square foot single family home with 3 bedrooms and 1 bathroom on 1121 N Midland Blvd, Nampa, ID 83651 dists only

Olympia, WA 7:31 (516 mi)

Sacramento, CA 7:56 (532 mi)

Carson City, NV 6:26 (417 mi)

Helena, MT 7:09 (504 mi)

STDEV 0:38 (51.5 mi)

TOTAL 29 h 02 m (1969 mi)

AVG 7:15:30 (492.25 mi)

I've been writing "a html" instead of "a href", which is why my links end up not showing up, although they're there when I hit the Preview button.

DeleteHere's the missing link: 1121 N Midland Blvd, Nampa, ID 83651.

This was an interesting approach to solving the same type problem: http://datascopeanalytics.com/what-we-think/2014/03/14/finding-the-ideal-spot-in-southeast-michigan

ReplyDeleteUnfortunately, I couldn't get their map to work. Particularly of interest, the section on geometric medians. "No such formula is known."

First PUBLISHED was vanished again

ReplyDeleteDan said ignore earth curvature. Wolfram Mathematica says this makes the problem Euclidean meaning just straight lines on a flat map. This is also known as TSP. Travelling Salesman Problem. I have tried several ways of figuring this but my brain cell is not up to the task.

However I found RouteXL in which one can use a real Google map and with the 4 Capital and a mythical place in the middle it drew a shortest path route

http://www.routexl.com/f=kELnpkDZ

So that's my 2 cents. Sorry we don't use pennies anymore do we.

jon

…interesting tool/map/route - surprisingly, almost identical distance/time to my pick of Prineville (see above 12:15 post - "modded map" -) yours:

Deleteoptimal travel time 40:56 hours distance 4128.8 km (2566 miles)to 2587 miles on mine & virtually the same travel times… shows there is more than one way to skin a postal route.…that's my 2¢… or wooden nickel (too bad it wasn't Mt. Vernon, OR) - worth about the same ≅

I am reexamining the elements of the problem because other than searching for another map app I haven’t figured out how I could get a result within 100 miles of each other for the four cities.

ReplyDelete--More than two locations-

Four that must be reached by car--Not looking for the geographical average center but a physical center reached by four different routes. Map projection formulas and mapping applications don’t seem to exist for routes. We can measure routes by

distance, time or both.--The equidistant center may be some distance from a town.Having Sacramento & Carson City very near each other & sharing interstates makes it difficult to get within 100 miles of equal distances to the center of all four cities. I have tried rerouting Google Maps manually from Sacramento on to different highways eg. 395 but tools not cooperating & I would think Google Maps being up to date knows the shortest routes. Perhaps it is one of those

we can’t get there from hereI realized the area we have is a triangle more or less so roughly I found the center of the triangle. Without taking into account routes however. http://goo.gl/fGyiCV

ReplyDeleteOn Google Earth, finding the directions [ from:Olympia, WA to:Sacramento, CA to:Carson City,NV to:Helena, MT to: Olympia, WA ] places the map center very close to their centroid (geographical center). This is as the crow flies, though, so I guess of no real use here. (This doesn't work on Google Maps because the search box shifts the center -- and everything -- to the right.)

ReplyDeleteJust looking at the map's roads and trying to guess, it's easy to realize Nampa, Idaho is probably the more equidistant you can find. (In geometry, there's no real equidistant point between more than three points unless they form a "cyclic polygon". In maps, this will be just as rare, just more difficult to find.) Nampa lies between 418 miles / 6h56 and 533 miles / 8h30 from those capitals. All other apparent midpoints I've checked have larger differences between the shortest and the longest one, so in that sense are "less equidistant".

The "Center of mimimum distance" on Geo Midpoint makes you rethink what should be the ideal spot. In fact, if you visit those four points with the same average frequency, and only one of them per travel (go tere and come back home), you might consider living in a place that minimizes total travelling radial distance, even if that means living very close from one of the locations and very far from another one. The sum of distances from Nampa to those four cities is 1977 miles / 31h27. The sum of distances from the "Center of minimum distance" (39.9864466,-120.0727352) to the same cities is 1767 miles / 26h52. Of course, if you live only 1h06 from a place and 13h02 from another one, I bet you wouldn't visit them equally often.

So I was thinking about the blast zone part of your question and how that might play out in the selection. Would a place so close to Boise, Idaho (State Capital, pop. 212,303) be a wise decision? Looking up [ population helena, mt ] shows it only has a population 29,134. Wouldn't Boise be a more dangerous choice? What would the fallout look like?

ReplyDelete[ nuclear blast zone map ] to Nukemap by Alex Wellerstein

1.Set the location to Boise, ID

2. Ivy King 500 kilotons

3. Airburst and radioactive fallout

Advanced options - Burst height 200 m

other effects wind speed 10 mph (after searching [ average wind speed boise idaho ]

to this Blast Zone Boise, Idaho

Maybe Nampa is OK or I'll just move in next door to remmij in Prineville.

I don't know Fred, Luís might be on the rational/logical train with Nampa - just have to hope the targeting is to the south and the wind is blowing that way too… more preppers in Nampa too. ;)

Deletecomparison tool

(although, the highlights box seems backwards, thee Nukemap should be part of the comparison categories.)

Driverless cars for everybody… who wants to be driverless…

neighborhood - who's going to blow up Mr. R.?

As Fred points out, there can be many different criteria for evaluating a particular place. I proposed just pure distance as the key metric. Others (Nancy, Luis, Rosemary, etc.) brought up "drive time" as one criterion. Protection from a nuclear blast could be another, flying time could be another metric, region with the lowest probable exposure to fallout might be the final metric.

ReplyDeleteIn all these cases, to find the "best midpoint" you have to create a "metric" to evaluate each point on the ground, and then find the location(s) that minimize that metric. In my case, the metric was "Euclidian distance from the other cities." This gets more interesting if you have more cities to deal with--say 12 or 20. But this becomes more of an interesting math question than a SearchResearch question. (Although as you can see, math creeps in everywhere, even in the simplest of questions. In this case when you have larger number of cities or complex metrics, optimization models such as dynamic or linear programming would be the best way to solve the challenge. But we won't go there. Yet.)