I'm trying to solve this problem:
Given a collection of cities and the number of commuters between cities, design a network of roads for minimal cost where cost includes the cost of building the roads, and traveling of commuters. (So if more commuters use one edge, that edge will have a modified cost since the commuters want to get to their destination quickly)
I've been treating the cities as nodes in a graph and the roads as edges. I want the weight of the edges to be dependent on the length of the edge (longer edges cost more) and somehow dependent on how many commuters are using that edge.
My thought was to try doing something like a Minimum Steiner Tree, which if cost didn't depend on the commuters would minimize the cost of building the roads, but I'm not convinced that the solution to this should be a tree. And if I try to find a Minimal Spanning Tree or Minimum Steiner Tree I'm not sure how to deal with the fact that I don't know the edge cost until I know the full tree/graph. That is if people want to travel from A to B and we remove the edge from A to B, those people will now have to travel from A to C then from C to B which will modify the edge cost between A and C and C and B.
Does anyone have any ideas on how to deal with the changing edge costs or know of a better way to solve this problem?
edit: You can make any sort of network you want, the roads can go straight from one city to another, or to any intermediate node(s) which can be placed anywhere in the plane. I'm planning on making the cost of building a road just a constant times the length of the road. For the cost of commuters I think another fractional constant times the distance they have to travel along the roads times the number of commuters traveling along that section of road.