|
|
| GeoCommunity Mailing List |
| |
| Mailing List Archives |
| Subject: | [gislist] Seeking Resource Allocation/Cost Network Algorithm |
| Date: |
04/07/2005 03:10:02 PM |
| From: |
Bill Thoen |
|
|
I have a resource allocation network problem that I'm having a hard time
understanding and I hoping someone here can point me in the right
direction in either methodology or published research so that I can solve
it.
I'll use an imaginary example to describe the general problem. Suppose we
have three places in the north where they produce glod, and to the south
there's two places where there's a market for glod. There are connecting
road segments between all glod producers and markets, and it doesn't
matter if the route from one glod producer has to go through another glod
producer's town, or if glod is shipped from one market center to another.
If the demand warrants it, the glod teamsters will take it from anywhere
to anywhere, picking up more along the way as needed. There are no
requirements that nearer glod producers must first exhaust their
supply before more distant producers are allowed to move their glod. The
markets want the cheapest glod first, no matter where it comes from. Glod
production is measured in units per month, as is market capacity.
The flow of glod cannot exceed either the production capacity or the
market demand. Once a producer's supply is sold a market that wants more
must get it from another producer. Once a market demand has been filled no
more glod can be shipped to that market. Also, even if a market demand
exists and there's still some glod available, if it can't be delivered for
less than or equal to what the market will pay, then the glod doesn't
move, and the market just does without. Likewise, a producer will not sell
their glod for less than what they've fixed as the selling price at the
beginning of the month.
Delivery is handled by the glod teamsters, and they generally charge by
units of glod per road segment, but the price is not based solely on
distance. It's based on a complicated equation of distance, road quality,
bribes, etc. Simply assume that each road segment has a price per unit and
also that glod can move only one way along a road (two way movement is
implemented by adding an additional road segment going in the opposite
direction.)
However, there's also a maximum capacity limit for each road segment. Once
that limit is reached, no more glod can be shipped along that segment that
month. If there's still glod available and a market for it, the remaining
glod has to be shipped along a different route.
So each town in the network either produces or consumes so many units of
glod per month, and they each have a price per unit for which they are
willing to sell or buy it. Each road segment between the towns has a price
per unit and a maximum capacity of glod transport.
What I want to be able to do is answer questions like what is the cost of
glod in either market in any particular month? When and where should
roads be built or existing capacity expanded (or even abandoned)? From the
seller's point of view, how much and to which markets do you ship your
glod to maximize profits and likewise for the buyer, how much glod do you
buy from which producer to minimize your costs?
Because there are critical factors that limit glod flow that can
dynamically change the network topology, this isn't a simple least-cost /
shortest path problem. But is there general algorithmic solution, or is
this a problem that can only be solved in an iterative process?
- Bill Thoen
_______________________________________________
gislist mailing list
gislist@lists.geocomm.com
http://lists.geocomm.com/mailman/listinfo/gislist
_________________________________
This list is brought to you by
The GeoCommunity
http://www.geocomm.com/
|
|
Sponsored by:
For information
regarding
advertising rates
Click Here!
|
