Genetic Algorithm for Inventory Allocation

Posted on 2009-02-18
Medium Priority
Last Modified: 2013-11-13
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:
Question by:rderveloy
LVL 85

Accepted Solution

ozo earned 500 total points
ID: 23676382
from your description, I see no reason a genetic algorithm could not work,
but I also see no reason that a greedy algorithm would not work.

if I had a cleared understanding of what is being optimized under what constraints, I might
have a better idea of what algorithms could work best.
LVL 22

Assisted Solution

NovaDenizen earned 500 total points
ID: 23684651
Like ozo said, a greedy algorithm would probably work well.

Instead of calculating a fitness value for every individual donor/recipient, you should be measuring the overall fitness of a plan.

The plan is just a list of equipment locations:
     * Item X in location A
     * item Y in location B
     * and so on, one line for each item

The overall fitness of a plan is calculated from two parts.  The first part is the cost of moving all the items from their current location to the location specified in the plan.

The second part is measured by the ability of each location to adequately get things done.  Look at the need of each location and the number of items available there according to the plan, and check to see how well each location can do its job.  When a location can't do it's job adequately, there should be a big cost.  When it can barely do it's job, there should be a smaller cost.  When it can do its job very well, there should be no cost.

Add all the costs up, and that is the cost of a plan.

To do a greedy algorithm, first make a starting plan which leaves everything as it is.  Evaluate the cost.  Then copy it, make 1 to 3 or so random changes, then evaluate the cost of this slightly different plan.  If the new plan is better, keep it.  Else throw it away.  Keep making new plans with random changes, keeping the ones that improve.


Author Comment

ID: 23694684
Thank you for the comments.
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.
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.


Author Comment

ID: 23888278
It's been a while.  Does anyone have any additional suggestions?
LVL 31

Assisted Solution

GwynforWeb earned 500 total points
ID: 23894664
     Genetic algorithms should generally be used as a last resort, they are easily described but can be hard to get decent results out of. They often require a massive number per generation,  gazillions of generations and a fair bit of fine tuning.

    More often or not a linear programming, greedy or dynamic programming type of algorithm will give decent results/guesses for the type of problem you are describing. Your problem is complex with many constraints, I could not be bothered to wade through the whole thing.   I am guessing this is the case with others.

   Presenting a simplified version succinctly might get more response.
LVL 27

Assisted Solution

d-glitch earned 500 total points
ID: 23915054
More data would be helpful.

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?

What is the benefit of an optimum allocation (which will cost time and money)
versus just leaving things where they are (which is presumably free)?

What is your scoring criteria?  Show us a few sample score calculations.
It is unlikely that a genetic algorithm will be useful.

I would think you could get by with a simple auction procedure.

Plants with excess capacity can offer equipment.
Plants that need equipment can offer cash/credit.

An arbitrator can look at how to satisfy the greatest need at the smallest cost.
And then look at the second greatest need.

This is the essence of a greedy algorithm.  It is pretty straight forward.

Author Comment

ID: 23953145
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?


Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
"Disruption" is the most feared word for C-level executives these days. They agonize over their industry being disturbed by another player - most likely by startups.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

862 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question