1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Where to stay?

  1. May 11, 2014 #1
    Suppose you plan to visit a region in a foreign country, and you need to decide where to stay.
    You're going to stay for a week, and don't fancy moving from town to town with your luggage.
    So you prefer to find a hotel in one appropriately chosen location, and you'll do round-trips to the places you want to visit each day.

    My question is: what's the best way to select the hotel location?

    I guess the answer depends on what objective you want to achieve.
    For instance, you may want to minimise the time spent travelling or the distance travelled; and that either on a daily basis or on the total over your stay (if it makes a difference, which I'm not sure about).

    Suppose the places you want to visit are 5 points on the map.
    Assume that for any point X on the map corresponding to a hotel you can easily calculate the shortest travel time and road distance to each of the 5 places.

    How would you go about estimating the 'best' X?
    Would you start from the centroid of the 5 points and optimise from there?
    Is the best X necessarily only one, or could one find multiple ones?
    Can the best X be close (in time or space) to most places and far from one or two of them, or is it always going to be 'centrally' located?
    Do you know if there is already an algorithm that does this, for instance in GPS navigation systems?

    Thank you!
  2. jcsd
  3. May 11, 2014 #2


    Staff: Mentor

    Why not use google maps to get the distance to each location from some hotel location in the middle of the five points?
  4. May 12, 2014 #3
    Sure, that's what I considered initially, the 'middle' being the centroid of the 5 points (i.e. the point with coordinates equal to the average of the coordinates of the 5 points on each axis).
    Obviously though, we don't move in horizontal straight lines when we drive on a real landscape, so the 'middle' could be much more distant -in terms of actual road- from one of the points than from the other 4, for instance. And depending on the type of road, the same distance could take different times to cover.

    Also, say that after doing the calculation you suggest using Google, you discover that the distances are the following:
    X to P1 = 10
    X to P2 = 13
    X to P3 = 9
    X to P4 = 18
    X to P5 = 12

    How do you know if there is no 'better' X, for instance an X where X to P4 gets shorter, without increasing too much the other 4 distances?
    What is the next step you take to verify this?
    And can the problem be expressed using a single continuous function over a given domain, so one can look at the absolute and relative extremes, etc?

    I understand that the problem is somewhat vaguely formulated. I'll think about it and see if I can express it more clearly.
    I'm just wondering if there is already a mathematical theory about this kind of situations.
  5. May 12, 2014 #4
  6. May 13, 2014 #5
    Great, thank you micromass!
    'NP hard', not just 'hard'... sounds quite scary! :O( :O)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook