Genetic Algorithm for Inventory Allocation

Posted on 2009-02-18
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 84

    Accepted Solution

    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

    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

    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.

    Author Comment

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

    Assisted Solution

         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 26

    Assisted Solution

    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

    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?


    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Why You Should Analyze Threat Actor TTPs

    After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

    Suggested Solutions

    Title # Comments Views Activity
    equalIsNot  challenge 43 90
    Simple Random Sample 2 43
    seriesUp challenge 7 81
    scoresClump  challenge 31 85
    Introduction Many of the most common information processing tasks require sorting data sets.  For example, you may want to find the largest or smallest value in a collection.  Or you may want to order the data set in numeric or alphabetical order. …
    Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
    Need more eyes on your posted question? Go ahead and follow the quick steps in this video to learn how to Request Attention to your question. *Log into your Experts Exchange account *Find the question you want to Request Attention for *Go to the e…
    how to add IIS SMTP to handle application/Scanner relays into office 365.

    737 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

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now