2
$\begingroup$

A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators, trays and slots are identified by unique IDs and slot also have access to the ID of their own article. In the same tray there can be multiple slots with the same article.

Example:

tray A contains

  • slot SA1 with 5 items of article X;
  • slot SA2 with 10 items of article Y;
  • slot SA3 with 3 items of article Z

tray B contains

  • slot SB1 with 12 items of article Y

tray C contains

  • slot SC1 with 4 items of article X;
  • slot SC2 with 15 items of article Z;
  • slot SC3 with 8 items of article W

trays A, B and C belong to the same elevator.

——————————————————

I have to design an algorithm which, given an order list (we can model it as a dictionary with articles' IDs as key and quantity needed as values), returns the minimum list of trays needed to satisfy the order. That is, find the smallest (in terms of cardinality) set of tray whom slots contain a sufficient quantity of each articles listed in the order.

This is quite different from a standard warehouse optimization problem because we are not considering the physical distances between each tray, since the elevators are automatic and they give us the tray, while in the classical problem is the human who moves toward the tray to pick the item from it.

After reading through articles about warehouse optimization, I've decided to take an heuristic approach.
I've modeled a sort of euclidean space, with an axes for each article contained in the order. Then we can consider a tray as a point on that space, with coordinates for each axes equal to the quantity that tray has of the article corresponding to that axes. In the same way we can imagine our order as a point.
Then I've create a heuristic function, $f(order\ o, tray\ t)$, which returns the "euclidean distance" from point-tray $t$ to the point-order $o$. The idea is that the more a tray is "near" the order, the more article we can pick out of it.

So, to satisfy the order, I simply compute $f(order\ o, tray\ t)$ for each tray in every elevator. Then I order it by descending value and finally I greedily take a tray with the minimum distance from the order. This will be repeated until we collect enough articles to satisfy the order.

I've tried to build a graph in which each node is a tray and is connected to each of the others by a directed edge. The weights of the edge from node $i$ to node $j$ will be equal to the heuristic function computed on tray $j$.

$w[i, j] = f(order, j)$

This results in a fully-connected, bidirectional graph (each node linked with each other node by both an incoming and an outgoing edge). I want to apply some algorithm of shortest path (or any other useful algorithm) taken from graph theory on this graph but I couldn't find anything really helpful.

Is there any algorithm I can apply on such a graph? Or maybe the graph is not the right structure to represent my problem. I'm open to new solutions.

$\endgroup$
3
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. Please use ' for apostrophe. $\endgroup$ – greybeard Jan 20 at 22:02
  • $\begingroup$ Let's get rid of the distance function. The goal is just to find out the minimum number of trays I need to call to collect articles from their slots according to the order. I hope the example will clarify. $\endgroup$ – dc_Bita98 Jan 21 at 13:58
  • $\begingroup$ Good, thank you. So it sounds like elevators or which elevator each tray is in doesn't matter? So it seems like some parts of the question can be deleted as irrelevant, given the current problem statement. $\endgroup$ – D.W. Jan 21 at 18:29
2
$\begingroup$

This is the special case of the multidimensional knapsack problem where each item (tray) has the same value (consider the set of trays you don't select). It presumably remains NP-hard, but can be solved by a number of methods. Probably the easiest to try first is to formulate this as an instance of integer linear programming and then apply an ILP solver to it.

$\endgroup$
2
  • $\begingroup$ That's interesting. I was definitely focused on graph theory so I haven't even thought about knapsack. There's a thing I don't get though: when you say "each item (tray) has the same value"... Actually I think the value of a tray depends on items it contains. Maybe I'm misunderstanding you $\endgroup$ – dc_Bita98 Jan 21 at 20:23
  • 1
    $\begingroup$ @dc_Bita98, your objective function is to minimize the number of trays, so in the language of the knapsack each tray counts equally (it has the same value, i.e., same profit). There are separate constraints regarding what subsets of trays are allowable (they have to provide enough of the items needed in the orders). $\endgroup$ – D.W. Jan 21 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.