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.

  • $\begingroup$ Screams "flows" to me. $\endgroup$ – Raphael Mar 19 '14 at 0:09
  • $\begingroup$ Sounds like an exercise to me. So, what chapter of the book is this from? Or, what techniques are you studying currently in your class? That might be a big hint to you about what kind of approach to try... P.S. The problem doesn't seem clear to me. What kind of network am I allowed to build? Does each road have to go straight from one city to another? What is your model for the cost of building a road? Is it just a constant times the length of the road, or something more complex? What is your model for the cost due to traveling of commuters? $\endgroup$ – D.W. Mar 19 '14 at 0:26
  • $\begingroup$ I don't think it's from a book, or at least not one I know of. The class is sort of an independent study so we aren't exactly studying anything in particular, just what I find. This also isn't an area the professor has studied before. I edited the post to hopefully make the problem clearer. $\endgroup$ – Ryan Mar 19 '14 at 1:52
  • 1
    $\begingroup$ So, are you allowed to add steiner points? en.wikipedia.org/wiki/Steiner_tree_problem $\endgroup$ – Joe Mar 19 '14 at 2:35
  • 2
    $\begingroup$ Yeah, you can add Steiner points or any other type of point that would reduce the cost as long as the cities are connected and commuters can get where they need to go. $\endgroup$ – Ryan Mar 19 '14 at 2:38