# optimal road layout problem - how to convert to maths and see the shapes it makes?

I have this puzzle going round my head about optimal road layouts, but I'm a programmer not a mathematician and I don't really know how to specify it as a maths problem. Once it's well-specified I can solve it (or more likely get help to solve it) and then write some code based on the solution to generate images and visualize the solutions (or use some tool that does this kind of thing). I want to see what it looks like as the inputs change.

Here's what I have so far:

I have a large (but finite) flat and featureless area of land and I want to cover it entirely with grass and roads while minimizing some function of my building costs and average trip-time. Trips can originate and terminate anywhere on my land, all with equal probability and trips are always optimized for speed. Travel on grass is slower than travel on roads.

My inputs are:

• Cost per unit-area to lay grass (cheap)
• Cost per unit-length to lay road (expensive)
• Fixed width of a road
• Speed of travel on grass (slow)
• Speed of travel on road (fast)

My first problem is that I don't really know how to define the function of building cost vs. average trip-time. Build cost would tend towards irrelevant; if you can make infinite trips then the cost-saving of better trip-time would mean the entire land would be paved with road and no grass. So do I need to specify another input for how many road-units you can travel before you have to rebuild some roads? I can't help but feel this is not actually an issue because the average trip time for all possible trips doesn't need a number-of-trips, does it?

Next, should the cost (time) of a trip be defined relative to what it would cost if everything was paved over and you just go in a straight line straight there at road-speed? Or is the absolute time the thing to use? Also, how do I map the time-cost to the build-cost, do I need another input for the cost-per-second-of-average-trip?

Lastly, does the shape and size of the land matter? I want it to not matter, that's why I said large but finite, because I don't want to know the shape of the roads when distorted by the edges of the land, I want to see the middle section. I imagine it's some repeating tessellated pattern like hexagons or triangles, or maybe octagons and squares or triangles with the corners cut off making smaller triangles.

Update: To be clear, the answer I'm looking for is a well-specified version of the problem, with any changes or additions or reasonable simplifications if necessary. It should be clear enough that it can be solved (or at least attempted if it's really that difficult).

-
Ooh, this sounds like an interesting problem that will probably be very hard to solve. You may enjoy reading about the somewhat related Steiner tree problem. – Rahul Aug 8 '13 at 2:53
Actually, if walking on grass is so much slower than walking on roads that the fastest path is always to walk to/from the nearest road, then the time spent walking on roads is effectively negligible. Then what you're optimizing is just the average distance from a point on the region to its nearest road. A natural formulation of the problem would be to minimize this average distance for a given total length of the road network. – Rahul Aug 8 '13 at 5:16
@RahulNarain maybe that's a badly-specified part of my problem then? – jhabbott Aug 8 '13 at 9:35
@RahulNarain I understood what you were saying - in order for my specification of the shortest trip to be true, road-travel would have to be infinitely faster than grass-travel - I removed that part as it was obviously wrong, thanks. – jhabbott Aug 8 '13 at 9:57