3
$\begingroup$

Let's assume a warehouse with multiple areas, each including either ground or shelf bins. I want to zone bins in this warehouse such that all bins in a zone are as close as possible. Considering that I need to use a preset value for the number of zones in each area, I have explored two options so far:

  • Mathematical programming: For each area, suppose $i$ and $j$ refer to the indices of zones and bins, respectively. If binary variable $x_{ij}$ determines the allocation of bins to zones, and integer variable $z_j$ specifies the distance of other bines from bin $j$, I can formulate a model as follows.

\begin{equation} min \sum_{j} z_j \end{equation}

subjected to:

\begin{equation} \sum_{i} x_{ij} = 1 \hspace{1cm} \forall j \end{equation}

\begin{equation} z_j \geq \sum_{j'} x_{ij'} \times D_{jj'} - (1-x_{ij}) \times \Omega \hspace{1cm} \forall i,j \end{equation}

where $D_{jj'}$ specifies the distance between bins $j$ and $j'$, and $\Omega$ is a sufficiently large number. Based on my experimental observations, this model is not computationally efficient (no feasible solution was found after a couple of hours).

  • Data mining: I have tried different data mining methods, out of which k-means works the best. The following figure illustrates the zoning of bins for a warehouse with 3,000 bins and 50 zones in each area.

enter image description here

Please let me know your opinion on whether you suggest other methods worth exploring for this question.

$\endgroup$
10
  • 1
    $\begingroup$ I think your final sum should be over $j'$ instead of $i$. What solver are you using? Have you considered a quadratic objective instead of the big-M constraints? $\endgroup$
    – RobPratt
    Mar 31, 2023 at 3:18
  • $\begingroup$ You are correct. It is just a type (will edit the question). I tried both Gurobi and CPLEX (default). Can you please elaborate more on the use of quadratic objective (any reference is appreciated)? $\endgroup$
    – mdslt
    Mar 31, 2023 at 3:23
  • 1
    $\begingroup$ Have you tried a simple greedy approach? for example, while not all bins have been assigned, for each bin, try to pack a zone containing this bin and all its closest bins and select the one with the lowest cost $\endgroup$
    – fontanf
    Mar 31, 2023 at 6:25
  • 1
    $\begingroup$ @mdslt try applying an upper bound to $z_j$ $\endgroup$ Mar 31, 2023 at 17:26
  • 1
    $\begingroup$ @mdslt using your constraints & objective, make $z_j$ a non-negative variable. It may speed up. $\endgroup$ Apr 1, 2023 at 2:51

3 Answers 3

6
$\begingroup$

Here is a reformulation as MIQP. Minimize $$\sum_{i,j,j'} D_{jj'} x_{ij} x_{ij'}$$ subject to $$\sum_i x_{ij} = 1 \quad \text{for all $j$} \tag1\label1$$ If both $j$ and $j'$ are assigned to the same bin $i$, then $x_{ij}=x_{ij'}=1$, so the objective penalty $D_{jj'}$ is accrued.


Here is an alternative linearization that does not use big-M constraints. Let binary decision variable $y_{jj’}$ indicate whether $j$ and $j’$ are assigned to the same bin. Define linear constraints $$x_{ij} + x_{ij’} - 1 \le y_{jj’} \quad \text{for all $i,j,j’$} \tag2\label2$$ Now minimize $$\sum_{j,j’} D_{jj’} y_{jj’}$$ subject to \eqref{1} and \eqref{2}. Note that this linearization differs from the usual one that would instead use triply-indexed variables $y_{ijj’}$.

$\endgroup$
3
  • $\begingroup$ I've tried the quadratic objective function but it does not work well! Note that I have 3,000 bins and around 100-300 zones which makes the problem large. I will try the other formulation coupled with a set of restrictive constraints. Thanks anyway! $\endgroup$
    – mdslt
    Mar 31, 2023 at 16:30
  • 1
    $\begingroup$ If I understand correctly, if $y_{jj'}$ is meant to be $= x_{ij} & x_{ij'}$, then adding the constraints $x_{ij} >= y_{jj'}$ and $x_{ij'} >= y_{jj'}$ will further strengthen the formulation. This is called Fortet's linearization. $\endgroup$
    – batwing
    Mar 31, 2023 at 18:06
  • 2
    $\begingroup$ @batwing If you use the usual triply-indexed $y_{ijj'}$ variables, the constraints $x_{ij} \ge y_{ijj'}$ and $x_{ij'} \ge y_{ijj'}$ would be valid but probably unhelpful because they are naturally satisfied at optimality. But my formulation uses instead $y_{jj'}$, so the constraints you proposed are not valid. The interpretation of $y_{jj'}$ is $\sum_i x_{ij} x_{ij'}$. $\endgroup$
    – RobPratt
    Mar 31, 2023 at 20:02
1
$\begingroup$

Rather than summing all the distances, another possible objective function is to minimize the sum of the "diameters" of the zones, where the diameter is the maximum distance between any two bins assigned to the zone. Using your variables $x_{i,j}$ and letting $z_i$ now represent the diameter of zone $i,$ your second constraint is replaced by $$z_i \ge D_{j,j'} (x_{i,j} + x_{i,j'} - 1)\quad \forall i,j,j' > j.$$

Addendum: Another common choice for this type of problem is to minimize the largest zone diameter, rather than the sum of the diameters. To do this, minimize a new variable $y$ subject to the constraints $y\ge z_i \, \forall i.$

$\endgroup$
1
$\begingroup$

As you understood, your zoning problem can be modeled as a clustering problem: discrete decision variables related to assigning items to sets, possible additional constraints on how the items can or cannot be assigned to the sets, and an objective function related to a distance to minimize. The distance is generally of a quadratic nature. Paul, above, suggests different distance functions to reach the most appropriate business solutions.

Due to the quadratic nature of the problem, traditional solvers like Gurobi and Cplex cannot scale. Given the number of items you mentioned (3,000 bins), MILP or MIQP solvers don't deliver meaningful solutions, even after hours of running times.

Thanks to its higher-lever modeling APIs involving set variables and nonlinear mathematical operators, coupled with exact and heuristic methods under the hood, Hexaly can provide high-quality solutions to such problems in minutes. You can find ready-to-use templates for this problem here. Benchmarks related to these problems, like Quadratic Assignment Problem (QAP) or K-Means Clustering Problem (MSSC), are also available here.

Disclaimer: Hexaly is commercial software. Nevertheless, it is free for faculty and students.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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