Here is an interesting situation for which i need some algorithmic advice. I'm going to make this as simple as possible so as not to pollute the issue with unecessary details. If you want the actual context of the problem, see the bottom of the post. Thanks for your input! THE SITUATION: Suppose we have a random number of "towns" sprinkled across an area. Each town is connected to at least one other town via a "road". Like so: Each town can be a producer and/or consumer of "resources". The goal is to get resources from producers to consumers. Now we have "trucks" which transport the resources across the roads. Each truck can hold a limited amount of "resouces". Finally, put this whole situation into a turn-based model. Every turn, producers produce some resources and consumers consume some. Each town is a little different in the amount. Some towns produce nothing, only consume. Others vice versa. Some towns do both, so no intercity transportation is necessary in that case. Every turn, trucks move along the roads a little bit. If they are empty, trucks need to collect resources from producers. If they are full, trucks need to deliver them to consumers. Basically, we are modelling "traffic" here. Here is another illustration showing the towns, the roads, production numbers (blue), consumption (red), and the little green dots are trucks en route. Sounds simple enough. The problem is that this needs to be automated. The goal is to "build trucks" and have them "go into service" picking up and making deliveries automatically with no user input. The computer needs to figure out which trucks go where and how often. So the issue is: can you think of an algorithm to do this? What i've considered so far: - User specified routes. Let the user manually define a route such as A->B. Then just have a truck "subscribe" to a particular route. The problem is that this gets more complex with more towns. It's also not very dynamic in case the needs of towns change. - 1-to-1 Need-based algorithm. Basically, each town gets matched up with another town that fulfills it's "need" (consumers need producers, producers need consumers). This works, but not very efficiently. Consider: Ideally, a truck should be able to make a chain of stops, not just go back and forth between A and B. It would strategically lay out it's route so that it can pick up and deliver the most resources using the least amount of movement. - Propagated need-based algorithm. I imagines that each town could "broadcast" it's "need" to each of it's connected neighboring towns. That need, if unmet by the town, would get re-broadcast to all of it's neigboring towns and so on, like a game of telephone. In this model, trucks only move resources from one town to another neighboring town. No cross-county hauling. This situation makes for a "bucket brigade" model. Caveat: you need enough trucks for at least one per road. THE CONTEXT: I'm designing an abstract strategy game, so it's not about towns and trucks. My game deals with points (towns), transports (trucks) and several different kinds of resources (4, specifically). Each "point" produces these resources in varying amounts. Other points consume them and make them into things. I want to develop a system that has very little user-input because this situation could easily get overwhelming and tedious if it grows. with 3 or 4 nodes, it's easy, but with 2 dozen, it could be a nightmare. To make it worse, some of the nodes only need some of the resources some of the time. 3 of the 4 resources are constant and there is always a need for them, but the 4th resources is like "materials" or "work". You move this resource to other points to build things with. So this is only done when there is a need to build something. Once built, the point stops requiring that resource. Anyway, if you have any ideas on this or if i did not clearly explain what i am looking for, i look forward to hearing from you. Thanks!

The game transport typcoon addressed this by letting the user define the routes and assign the trucks. This was the player's main job in game.

Another game called settlers used the bucket brigade algorithm and propagated each request from the consumer to the neareast supplier. Since the carry capacity of each road was limited to 1 item a time in 1 direction, the algorithm had to check for the wait queues at each intersection. The terrain could also influence the speed of the transport, so the length and height difference of each road also contributed to its weight. (interesting that workers were handled as a reusable resource that can carry itself)

Viktor

ps: If you are aiming for a transport tycoon kind of game, let the user do it. If you are aiming for a settlers kind of game, you can automate it. But beware that automating everything without using bucket brigades is a complex problem. (see: travelling salesman problem)

Do the trucks incur a resource cost for the distance they must travel to deliver or pickup resources? (From your description I assume that the cost of travel is only time).

Yes it's only time.

The gotcha is that while trucks are hauling, the map points are continually producing resources. Just like any production company with a warehouse, there is a limit to how much resource can be output before it fills up "warehouse capacity". Then production stops.

So if trucks don't pick up in regular fashion on time, it actually hurts production. The object is to keep warehouses under their local max capacity.

It's interesting you're working on this... I'm assisting in the supervision of a PhD student who is working on a similar problem, although it's in the area of Sensor Networks and collecting data using mobile robots. You're problem is a little harder I believe because you don't have a single sink of information (resources), but you have very similar production constraints (discrete production centers, limited storage capacity, constrained transport paths, etc)... his problem has transport costs though.

There's certainly no easy solution to this problem. The easier (but less optimal approach) is to employ dynamic programming methods for the optimisation. You might gain some further insights into solution strategies by computing the minimal spanning trees for the separated production and consumption networks. I'll discuss this form of the problem with my student and see if we come up with any particularly useful/interesting insights.

Cheers,

Timkin

Thanks for the response. I guess i feel good tackling problems in my free time that bona fide smart people are also working on in an academic setting ;-) (not that i don't consider myself smart as well. But those extra few letters on the end of a name are very expensive you know!)

Yes, definately let me know if you come up with anything. While it's a very interesting problem indeed, i think in terms of a strategy game, it might be best to let the player define their own routes. That could be part of the strategy of playing the game.

The only problem with that is that AI players would need to do this as well. So i guess i need some kind of solution, even if simple. Otherwise, i might have to redesign my game!

Is there any reason why you need an optimal (or even near-optimal) solution?

We certainly don't move resources around in an optimal fashion in real life.

Most of the time we simplify the problem, moving resources/goods to distribution centers. Additionally, most companies cycle from a centralized stored-distribution to a "just in time" JIT-distribution system.

They don't do this to have a more optimal distribution system however -> they do this to offset storage overhead - basically turning their unused stock into cash.

----

If you use a sloppy automated distribution system as we do in real life, you can greatly reduce configuration information. The AI problem then becomes the optimisation of those simple variables

City X is a central distributor of commodity Y or it isnt.. the human decides for the human.. the AI simply needs to decide the same thing.

Regardless of who/what made the decision, the automated sloppy distribution goes into effect.

That's actually not a bad idea. It does not need to be optimal, as you mentioned, so i would consider this.

This would basically boil down to the 1-to-1 idea i originally posted. Producers get matched to consumers and just move resources over. No optimization takes place here. This requires more transportation units and time, but it's much simpler to work out.

Thanks for the reply