16
$\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$
7
  • 1
    $\begingroup$ Are we assuming that all possible start->finish combinations are equally travelled? $\endgroup$
    – f''
    Jul 20, 2015 at 13:55
  • 3
    $\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, 2015 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, 2015 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, 2015 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, 2015 at 19:31

5 Answers 5

Reset to default
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$
5
  • 4
    $\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, 2015 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, 2015 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, 2015 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, 2015 at 23:16
  • $\begingroup$ Aren't you using brute force here? Trying all the different answers? $\endgroup$
    – Ben Aveling
    May 10, 2017 at 13:02
2
$\begingroup$

This is a network design problem, and an alternative to brute force is to use integer linear programming, as follows.

Let $E$ be the set of (undirected) edges corresponding to the solid and dotted lines in the figure, and let $A$ be the set of (directed) arcs. Let $N=\{1,\dots,9\}$ be the set of nodes. Let $P=\{o\in N, d \in N \setminus \{o\}\}$ be the set of origin-destination pairs. For $(i,j)\in E$, let binary decision variable $y_{i,j}$ indicate whether $(i,j)$ is used. For $(o,d)\in P$ and $(i,j)\in A$, let binary decision variable $x_{o,d,i,j}$ be the flow of "commodity" $(o,d)$ along arc $(i,j)$. The problem is to minimize $$\sum_{(o,d) \in P, (i,j) \in A} x_{o,d,i,j}$$ subject to \begin{align} \sum_{(i,j) \in A} x_{o,d,i,j} - \sum_{(j,i) \in A} x_{o,d,j,i} &= [i = o] - [i = d]; &&\text{for $(o,d) \in p$ and $i \in N$} \tag1 \\ x_{o,d,i,j} &\le [(i,j) \in E] y_{i,j} + [(j,i) \in E] y_{j,i} &&\text{for $(o,d) \in P$ and $(i,j) \in A$} \tag2 \\ \sum_{(i,j) \in E: j \not= i+1} y_{i,j} &\le 1 \tag3 \end{align} Constraint $(1)$ sends one unit of flow from $o$ to $d$. Constraint $(2)$ forces $y_{i,j}=1$ if arc $(i,j)$ or $(j,i)$ is used. Constraint $(3)$ allows at most $1$ new edge.

The linear programming relaxation turns out to yield an optimal integer solution with $y_{2,8}=1$ and objective value $166$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ linear programming is such a powerful tool. $\endgroup$
    – Eric
    May 17, 2022 at 6:23
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$
2
  • 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, 2015 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, 2015 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$
1
  • $\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, 2015 at 5:53
0
$\begingroup$

The existing scenario is as follows.

[The key move herein is that, for instance, $1+2+3+4+5+6$ can be solved by adding the numbers in pairs -- 1+6, 2+5, 3+4 -- giving $3*7$. If the count is odd, add the middle number as a special case.]

1 to each = $1+2+3...+8$ = $4*9$=36.
9 is the same.
2 to each is 1 + $1+2+...+7$ = $(3*8)+4 + 1$ = 29.
8 is the same.
3 to each is 2+1 + $1+2+...+6$ = $(3*7) + 1+2$ = 24.
7 is the same.
4 to each is 3+2+1 + $1+2+...+5$ = $(2*6)+3 + 1+2+3$ = 21.
6 is the same.
5 (being the middle) is $4+3+2+1+1+2+3+4$ = $2*(2*5)$ = 20.

+= $2*36+ 2*29+ 2*24+ 2*21 +20$ = $2*(36+29+24+21) +20$ = 240.

[If it was very many stations, one would generate a formula... again treating the odds and evens differently.]

It is fairly obvious that adding the new connection near the existing middle one -- from 4 to 6 -- will have less effect than adding it further away from the existing middle one.

At the other end... the, or a, limit case is connecting 1 to 9 -- completing the/a loop. That gives 9 instances of (1+2+3+4+4+3+2+1) , which = $9*( 4*(5) )$ = 180. [Any journey more than 4 should be done in the opposite direction.]

The question then is that of whether the foregoing is the best case, or not. (If it is not, the best case will (presumably) be around the middle (of the halves) somewhere.)
It it is the best case, the next connection would be worse. [If, conversely, the next connection is better, then we have to work out where the sweet spot is.]
Connecting 2 to 9 gives us a loop, again -- 8 instances of $1+2+3+4+3+2+1$ = 104 -- plus (for station 1) $1+2+2+3+3+4+4+5$ = 24. That is a total of 128... which is better than the simple loop [180]... so it is improving... so we have to work out where the sweet spot is.

The question was whether or not we have to solve this puzzle just by brute force.

I daresay that the remainder of the working-out would be apparent to someone who had been following so far. (No doubt there are some maths geniuses out there who would have already been able to see that the limit loop case was, or was not, optimal.)

If there was a large number of stations, we could work out the pattern as I have detailed, and find the limit case (somewhere around the middle) by eliminating corresponding elements [e.g. "$2*(1+1+2+2+3)$" appearing in two different candidate solutions] and just looking at the remaining items.

It happens that, to see the pattern, we have to work out (I suspect) at least 4 more variants (2 even and 2 odd). Thus, for this small example, we end up doing most of it by brute force, in working out the pattern.

For a large case, we would still have to work out the pattern, but we would solve the problem by looking at the pattern, without doing the calculations. [There would by many instances of "n" and "n/2" and "(n+1)/2", before simplifying. ...Also "nCr".]

On the one hand, I imagine that a professional statistician could work out the pattern without actually going through all of the above "manually" as I did. On the other hand, even a professional statistician has to get their head around a novel problem, to see what equations emerge.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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