rderveloy
asked on
Genetic Algorithm for Inventory Allocation
As part of a project, I'm attempting to write an algorithm that will optimize the allocation of inventory between different locations. Basically, I'm attempting to optimize equipment allotments based on donor and recipient fitness levels. In other words, move excess inventory from locations with the most to give to the locations with the most need. Each location has up to two types of items in it's inventory with one taking up twice the space as the other. Each type accomplishes the same thing. However, the larger and less efficient type is more plentiful and cheaper than the more efficient one.
I already have the criteria to judge the fitness of donors and recipients that will result in a numeric score. The higher the score, the more fit the candidate is. Although I do know that I need to come up with a way to encode possible solutions, I'm not sure on how to proceed after I have identified potential donors and recipients along with their respective fitness scores.
Additional Requirements:
Each location has a fixed amount of room. Donors and recipients can exchange one type of equipment for another so the relationship between them can be bi-directional. Once a donor and recipient have "mated" the donor and recipient move on to the next round if and only if they have remaining inventory or need, respectively. Therefore, there needs to be some sort of "memory" to remember the remaining need levels of recipients and the remaining excess inventory levels of donors. Additionally, each pairing that led to the optimized result should be logged in the order that it occurred so that a "family tree" of sorts is generated.
Given the requirements, should I be pursuing a genetic algorithm? If not, what methods should I use? If so, what do I need to do next? When answering, please bear in mind that I haven't had specific training in algorithms or optimization.
Thanks in advance for any assistance you can provide.
This is the article I read that got me started on this idea:
http://www.ai-junkie.com/ga/intro/gat1.html
I already have the criteria to judge the fitness of donors and recipients that will result in a numeric score. The higher the score, the more fit the candidate is. Although I do know that I need to come up with a way to encode possible solutions, I'm not sure on how to proceed after I have identified potential donors and recipients along with their respective fitness scores.
Additional Requirements:
Each location has a fixed amount of room. Donors and recipients can exchange one type of equipment for another so the relationship between them can be bi-directional. Once a donor and recipient have "mated" the donor and recipient move on to the next round if and only if they have remaining inventory or need, respectively. Therefore, there needs to be some sort of "memory" to remember the remaining need levels of recipients and the remaining excess inventory levels of donors. Additionally, each pairing that led to the optimized result should be logged in the order that it occurred so that a "family tree" of sorts is generated.
Given the requirements, should I be pursuing a genetic algorithm? If not, what methods should I use? If so, what do I need to do next? When answering, please bear in mind that I haven't had specific training in algorithms or optimization.
Thanks in advance for any assistance you can provide.
This is the article I read that got me started on this idea:
http://www.ai-junkie.com/ga/intro/gat1.html
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
It's been a while. Does anyone have any additional suggestions?
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thank you for your replies!
"How many locations and how many pieces of equipment?
How far apart are the locations and how big/heavy is the equipment?
How much does it cost to move 1/10/1000 pieces of equipment?
How do the costs vary for different pairs of locations?"
The cost of moving the equipment is a trivial constant compared to the cost of the equipment itself. All I am trying to do is calculate potential inventory allocation scenarios.
Can you point out some online resources where I can learn about greedy algorithms from a beginner's perspective?
Thanks!
"How many locations and how many pieces of equipment?
How far apart are the locations and how big/heavy is the equipment?
How much does it cost to move 1/10/1000 pieces of equipment?
How do the costs vary for different pairs of locations?"
The cost of moving the equipment is a trivial constant compared to the cost of the equipment itself. All I am trying to do is calculate potential inventory allocation scenarios.
Can you point out some online resources where I can learn about greedy algorithms from a beginner's perspective?
Thanks!
ASKER
I'm not trying to optimize the cost of transporting goods or anything like that, but rather reallocating unused inventory stored at one location to one or many other locations that may need it. Transportation costs are not part of the equation.
Some background information:
For example, say I have a chain of bakeries and a central warehouse. Some of the bakeries are busier than others. Some, that used to be very busy, have less business due to increased local competition. Additionally, the output of such bakeries is directly proportional to the amount of ovens that are installed. There are two types of ovens being used: a smaller, more efficient one, and a larger one. Although the space available varies depending on the location, the amount of space at each location is a fixed amount. A bakery can be remodeled, but its extremely expensive and time consuming.
As for the ovens themselves, the smaller oven has the same daily output as the larger one but it comes in pairs. By swapping out a larger oven for a pair of smaller ovens you can double the output produced by that oven. However, the more efficient ovens are very rare, in high-demand, and are more expensive than the larger ones.
The problem and its constraints:
Now, say that our chain just got purchased by another bakery company and we are in the process of phasing out redundant locations. The bakeries that exist overlapping markets are being phased out. Given that our new parent company doesnt want us purchasing new ovens, we need to use whats available from the bakeries being phased out as well as other bakeries that have reduced customer levels before using new ovens from the warehouse. In this situation, we need to optimize the allocation of oven types based on a locations need while minimizing the need for remodeling.
Given that each individual market is to be optimized individually, assume transportation and installation costs are negligible when compared to the cost of the ovens themselves. Locations with large deficits are to be prioritized as recipients. Phased out locations are to be prioritized as donors followed by locations with surplus ovens. Again, no new equipment is available, so once the warehouse is empty of ovens, there are no more. Additionally, assume that the warehouse is prohibited from storing any ovens removed from a bakery and that it can only be treated as a donor. However, some locations with surpluses may need to swap equipment with a recipient because a donor location might not be in an overlapping market and that some recipients may not have room to expand.
I already know the minimum number of ovens needed per bakery. Simply taking the inventory on hand and subtracting the need either gives a surplus or deficit on a per-bakery level. In my fitness function, Ive already given a heavy weight to locations being phased out.
I hope that provides sufficient detail to describe what I need to do. Please post any additional questions you may have.