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).