15
$\begingroup$

Metro station points

The picture above shows a map of 9 train stations. These stations are connected by a single track running from station 1 to 9 as represented by the solid line (the trains runs both ways from 1->9 and 9->1). Let's say each station is 1 km distance apart from the adjacent station, along the railway track (solid line). Distance between 4 and 6, 4 and 7, 3 and 7, 3 and 8, 2 and 8, 2 and 9, 1 and 9 is also 1 km.

Now people from station 1 are only 1km far from station 9, but they have to go all the way round traveling 8km to reach station 9. Similarly, it is inefficient for people at other stations as well.

So the engineers decide to connect the stations on both sides. But they can only use a 1km railway track, due to budget constraints.

Which two stations do they connect so that it benefits all the people the most? They are supposed to consider the collective benefit. More specifically, they are to optimize the average travel time of the passengers, assuming that people embark and disembark at all stations with equal probability.

Note: I am new on this forum, and new at creating puzzles so please bear with me if I didn't give sufficient information for this puzzle to work. And I don't know the answer to the puzzle yet, I myself am trying to solve it.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Are we assuming that all possible start->finish combinations are equally travelled? $\endgroup$ – f'' Jul 20 '15 at 13:55
  • 2
    $\begingroup$ "benefits all the people the most" is a bit subjective for optimization problems such as this. For example, we might try to optimize the average travel time assuming people embark and disembark at all stations with equal probability. Or we might minimize the worst-case travel time over all possible embark-disembark combinations. Or (a more complex approach), we might try minimizing average travel time subject to the restriction that worst-case travel time not exceed some limit. Unfortunately, whether the optimal solution can be found efficiently depends on which metric we're optimizing. $\endgroup$ – COTO Jul 20 '15 at 15:28
  • $\begingroup$ @COTO I had assumed that people embark and disembark at all stations with equal probability. And as for the optimizing metric, thanks for pointing out the complexity, I didn't really think of that. How about we try to calculate to optimize the average travel time? I'll specify in the question. Also, could using a particular number of stations make this problem easier? I've used 9 because I just had a hunch having a mid-station might help. But still only way I could attempt it was brute force. Could any particular number make it easier? $\endgroup$ – thereisnospoon Jul 20 '15 at 16:04
  • $\begingroup$ By 'single track', do you mean the train only runs from 1->9 and not in the reverse direction? Or do we assume that each segment is bidirectional? $\endgroup$ – Alok Jul 20 '15 at 19:20
  • $\begingroup$ @thereisnospoon: For $n$ stations, my understanding is that you have $O\left( n\right)$ choices of where to put the extra track. For each possible choice, computing the uniform-in-uniform-out average transit time is an $O\left( 1\right)$ (constant time) calculation, hence the most obvious "brute force" algorithm runs in $O\left( n\right)$. Without any kind of precompiled data, it's really hard to beat an $O\left( n\right)$ algorithm for something like network optimization. Is an $O\left( n\right)$ algorithm acceptable? If so, I can post a solution. If not, why? How big is $n$ going to get? $\endgroup$ – COTO Jul 20 '15 at 19:31
4
$\begingroup$

Solution

Add link between stations 2 and 8

Details

To begin with, let's consider a layout with stations organized on a grid following a rectangular path with the stations on one end connecting to one another. It would be clear upon inspection that the best location to place a single additional connecting line would be 2/3 of the way from the closed end of the rectangle. Below are the figures for even and odd side lengths.

enter image description here

Extending this to the trapezoid in the problem statement we see that the best solution would most likely be 2-8 as it is roughly 2/3 of the way from 5-6. However 3-8 could also be a solution.

enter image description here

Algorithm

  1. Select potential candidate links that are approximately 2/3 from closed end
  2. For each candidate link evaluate the minimum distances between stations (1-9, 2-9, 2-8, 3-8, 3-7, 4-7, 4-6, and 5-6)
  3. Total distances for each candidate link
  4. Select candidate link with minimum total distance

Results

  • Candidate link 2-8 totals 17km
  • Candidate link 3-8 totals 18km

Choose

Link 2-8

|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Could you elaborate on how exactly by inspection you concluded that 2/3 of the way from the closed loop would be the best case for the simplified version you showed? $\endgroup$ – thereisnospoon Jul 21 '15 at 5:06
  • $\begingroup$ @thereisnospoon Looking at the paths DBAC, DFEC, and HFEG we see that they all have the same distance and thus the network of stations with adjoining lines is optimal. $\endgroup$ – Stephen Donecker Jul 22 '15 at 22:54
  • $\begingroup$ @thereisnospoon Please ignore the previous post as I accidentally hit add before I was finished editing and then timed out. $\endgroup$ – Stephen Donecker Jul 22 '15 at 23:16
  • $\begingroup$ @thereisnospoon Given the included connecting line at the end of the layout we may service a group of stations to the right only, and by carefully placing an additional line we may service a group of stations to the left and another group of stations to the right. In order to benefit the set of all stations optimally we would like each groups service area to be equal. Given that we have 3 possible service areas it follows that the optimal location for the additional line is 2/3 of the distance from the closed end. Think of the paths DBAC, DFEC, and HFEG as the three service areas. $\endgroup$ – Stephen Donecker Jul 22 '15 at 23:16
  • $\begingroup$ Aren't you using brute force here? Trying all the different answers? $\endgroup$ – Ben Aveling May 10 '17 at 13:02
1
$\begingroup$

Assuming that the traffic between stations are the same, a non-brute-force solution is

to start with a completely filled diagram and take out tracks. It should be obvious that constructing every track will be best at reducing travel time between any two stations. To pick a track to remove, we make the observation that a track near the middle (e.g 3-7) will be much more useful than a track near the edge (e.g 1-9). So we see how much removing a track on the edge will affect the total travel distances between pairs of stations.

Taking out the track 1-9, we notice that stations 2 through 8 are unaffected by the change. In fact, only stations 1 and 9 are affected because they lost their direct path! So removing this track will add a total of 1km x 2 = 2 km to the total travel distance between pairs of stations.

For our next track to remove, we look for another edge; 5-6. However, track 5-6 is not a possible choice for being removed, so we look at the next track inside: 4-6. Removing this track, we can see that only stations 4 and 6 are affected since they lost their direct path.

So we continue to remove tracks that are on the outside, which will bring the least amount of change in the total travel distances between pairs of stations. Doing this removes tracks 2-9, 4-7, 2-8, and 3-7, leaving us with only track 3-8 intact.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ How did you conclude that a track near the middle will be much more useful than a track near the edge? $\endgroup$ – thereisnospoon Jul 21 '15 at 5:36
  • 1
    $\begingroup$ In a non-rigorous way (again avoiding making any calculation): we know that the shortest distance between two points is a line. If we were to draw a line between each pair of stations, we have a lot of lines intersecting the middle of the diagram with only a few lines on the outside. Thus a track in the middle is much more efficient, and therefore useful, to keep in order to reduce travel distance. $\endgroup$ – dzastergamer Jul 21 '15 at 13:24
0
$\begingroup$

If you connect 9->1, then worst case it would take n/2 segments between 2 stations (eg. 1->5 or 1->6 via 9 is 4 segments). Moving the segment 1 node inwards on both sides, now the worst case is reduced and becomes 3 (e.g. 2->6 thru 8 when 2-8 is connected). If you further change it to use 3-8 then 1->9 is 4 segments, while the inner loop worst case is still 3 segments.

Hmm, in the specific example above it seems 2-8 is the best choice to minimize worst case length. It should be possible to come up with a generalized formula to connect the mth & (n -m)th nodes, where 1->m-(1 segment)->(n-m)->m is half the length of inner loop of m->(n-m)-(1 segment)->m

Note: I changed my answer while updating it to answer the OP's comment, earlier one was 3-8 which is wrong for this case.

|improve this answer
$\endgroup$
  • $\begingroup$ How did you make sure that it would be the most optimal solution for people at each stations who are equally likely to travel to any of the remaining stations? You only gave the explanation for travel from 1 to 9, what about other possibilities? Or does that somehow cover all other possibilities? If so, how? $\endgroup$ – thereisnospoon Jul 21 '15 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.