Thursday, November 22, 2007

Within 50 km

Recently the Spanish government announced its goal that the national high-speed railroad network (AVE) be developed so that every town in Spain is within 50 km from an AVE station. On the other hand, the estimations by the government itself are that the AVE network total length will reach 2,230 km by 2010. Are these statements compatible?

Let us consider the problem of laying out a railroad network with minimum length such that every point within the considered area (the national territory) is not farther than some predefined distance away from the closest network node. Solving this problem for an arbitrary shape like that of Spain can only be done via computer simulation, but we can introduce drastic simplifications that allow us to come up with a reasonable estimate using only some elementary calculations.

Ignoring the boundary effects, an hexagonal grid is the most efficient way to distribute points on the plane so as to maximize the area covered by circles with a fixed radius centered at the points.

For our problem, we have

R = 50 km,
r = ((√3)/2) R = 43.30 km,
A = (3(√3)/2) R2 = 6,495 km2.

The continental area of Spain is 492,173 km2, so we need a total of n = 76 hexagons (or nodes) to cover the country. As an approximation to the optimum network, we can simply take a minimum spanning tree connecting all the 76 nodes. Again, finding such a tree is a computationally hard problem, but we need not do it, as we are only interested in its length L: a tree with n nodes has n-1 edges, and using the reasonable assumption that our minimum spanning tree connects nodes exclusively with their neighbors we have

L = 2r(n-1) = 6,495 km,

which is nearly three times the planned length of the AVE network by 2010.

5 comments :

  1. FYI: AVE is a product offered by Renfe, Spains rail operator. The High Speed railway network (which is not called AVE), is built, operated and maintained by ADIF.

    I would leave the comments field OPEN allowing for anonimous contributions... less control and more freedom!

    Regards!

    ReplyDelete
  2. ftf, you're absolutely right about the confusion between the train and the railroad network, thanks for the clarification.

    I've also just allowed anonymous comments as you suggested.

    Best,

    ReplyDelete
  3. Thank you!

    Also comment that the government's goal is that an AVE station is within 50 km of 90% of the population. I would be interested in how would you solve this problem with this new information.

    Thank you again.

    ReplyDelete
  4. Also comment that the government's goal is that an AVE station is within 50 km of 90% of the population. I would be interested in how would you solve this problem with this new information.

    Well, if "the population" means the entire Spanish population, including the inhabitants of the islands, I think we're also out of luck (pending a deeper analysis): According to the INE, the population of Spain in Jan 1st, 2006 was 44,708,964, and 90% of that is 40,238,068. But the continental population on the same date is 41,569,337, exceeding 90% of the total by a relatively small 1,331,269. This is only a hunch, but I think 1.3 million cannot make up for such an area as to make a difference in the original analysis.

    Of course, if we're talking about 90% of the continental population, things become more interesting. I'm going to publish another variation of the problem in a couple of hours: coverage of the 47 continental province capitals (stay tuned). The algorithms devised there could serve us to tackle this version, I'd need some days to work that out.

    BTW, can you provide a source for the 90% figure you claim?

    ReplyDelete
  5. Nice job your last post.

    Here it the source you requested:

    http://www.la-moncloa.es/ActualidadHome/161206AVE.htm

    Best regards

    ReplyDelete