We help IT Professionals succeed at work.

# Genetic Algorithm for Inventory Allocation

on
Medium Priority
864 Views
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.

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
Comment
Watch Question

## View Solutions Only

CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015
Commented:
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.

Not the solution you were looking for? Getting a personalized solution is easy.

Commented:
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.

Commented:

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 its 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 doesnt want us purchasing new ovens, we need to use whats 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 locations 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, Ive 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.

Commented:
It's been a while.  Does anyone have any additional suggestions?
Commented:
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.
CERTIFIED EXPERT
Commented:

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.

Commented:

"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!
##### Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile