Guarda cosa hai scritto:

They request 20 pieces.

And the distribution is as follows '4'=>5, '1'=>5, '2'=>1, '10'=>8, '9'=>10. So ideally the warehouses will be assigned something like this: WID:4=5, WID:1=5, WID:9=10.

Perché non c'è WID: 2 = 1, o del resto no WID: 10 = 8? Qui devi utilizzare una logica, che ti fa dire "Ottenere 1 prodotto dal magazzino 2 costa di più di ...". Questa è la tua funzione di costo .

Un approccio a forza bruta avrebbe una funzione che, dato il layout del magazzino e l'allocazione del magazzino, determina il costo dell'ordine:

function costEstimate(array $wh, array $order) {
    // assert('count($wh) == count($order)');

    $cost = 0;

    // If we proceeded with $order, $wh levels would become
    $whAfter = array_map(function($whStock, $whOrdered) {
        // assert this is not negative
        return $whStock - $whOrdered;
    }, $wh, $order);

    // Number of shipments is number of non-zero requisitions
    $cost += count(array_filter($order)) * COST_PER_SHIPMENT;

    // We do not want to leave a magazine with less than low reorder threshold
    $isBelowThreshold = function($stock) { return $stock < REORDER_THRESHOLD; };
    $reorder_before = count(array_filter($wh, $isBelowThreshold));
    $reorder_after  = count(array_filter($whAfter), $isBelowThreshold));

    $cost += ($reorder_after - $reorder_before) * COST_PER_REORDER;

    // But if we manage to completely empty a warehouse that's good

    $empty_before = count(array_filter($wh));
    $empty_after  = count(array_filter($whAfter));

    $cost -= ($empty_after - $empty_before) * GAIN_PER_EMPTYING;

    // Now add costs per distance
    $idx = 0;
    foreach ($order as $whId => $whNum) {
         $cost += $whNum * $idx * COST_PER_UNIT_PER_DISTANCE;
         $idx++;
    }

    return $cost;
}

Puoi aggiungere ancora più criteri al costo o più dettagliati (ad esempio la distanza effettiva del magazzino o i costi di spedizione effettivi anziché la classifica). Oppure puoi aggiungere una funzione gamma a $ idx nel ciclo precedente per privilegiare i magazzini più vicini piuttosto che quelli più lontani.

Una volta che hai questo, il tuo obiettivo è trovare la combinazione (il vettore $ ordine) che minimizza il tuo costo. Puoi (ricorda - questo è l'approccio forza bruta .Per ordini di grandi dimensioni o ordini molto frequenti dovrai cercare ricerca delle operazioni , o almeno i vari aspetti del problema dello zaino) prova tutte le possibili combinazioni di ordini. Questo va rapidamente fuori controllo:

foreach ($combinations as $comb) {
    $test = costEstimate($wh, $comb);
    if ($test < $testSoFar) {
        $best = $comb;
        $test = $testSoFar;
    }
}

A seconda della funzione di costo, potresti essere in grado di migliorare l'algoritmo "sfoltendo" le opzioni poco promettenti.

Un'altra regola

Ad esempio, vuoi svuotare tutti i primi magazzini, a meno che non ci sia un magazzino che soddisfi completamente l'ordine rimanente. In tal caso non hai bisogno di una funzione di costo esplicita:

while ($totalOrder) {
    // Test 1. Can we satisfy this entirely?
    foreach ($warehouses as $id => $quantity) {
        if ($quantity >= $totalOrder) {
            $assignment[$id] = $totalOrder;
            $totalOrder = 0;
            break;
        }
    }
    // Test 2. Do we still need to requisition items?
    if ($totalOrder > 0) {
        // Use the first suitable warehouse.
        foreach ($warehouses as $id => $quantity) {
            if ($quantity > 0) {
                $assignment[$id] = $quantity;
                $totalOrder -= $quantity;
                // Stop this cycle and repeat.
                break;
            }
        }
    }
}

La funzione sopra descritta, nel tuo esempio, cercherà di inviare 20 pezzi. Nessun magazzino ha 20 pezzi, quindi il primo test fallisce. Il primo WH non vuoto è quindi 4, che viene assegnato 5. Il ciclo continua e tenta di inviare 15 e non può, quindi i magazzini sono esaminati di nuovo (array_shift e array_filters qui potrebbero essere i tuoi amici), e il magazzino 1 è selezionato per ottenere 5 pz. Il resto è ora 10 e l'ultimo magazzino può soddisfarlo.

L'assegnazione finale con questo algoritmo sarà WID: 4 = 5, WID: 1 = 5, WID: 9 = 10 e l'operazione è O (N ² ) nel numero di magazzini. Puoi ottenere O (N log N) mantenendo un array ruotato in ordine di dimensioni, ma per valori realistici di N non devi preoccuparti.

ingresso

• Lascia che q sia la quantità richiesta.
• Lascia che c_i sia la quantità disponibile (capacità) al magazzino i .
• Lascia che d_i sia la distanza del magazzino i .

Output

• Lascia che x_i sia la quantità allocata al magazzino i .

Il seguente approccio dovrebbe darti un risultato abbastanza buono.

Puoi prima ordinare i tuoi magazzini per distanza (il più vicino al più lontano). In questo ordine, allocare il maggior quantitativo possibile dal magazzino in questione fino al raggiungimento della quantità richiesta q .

Con questo approccio ridurrai al minimo la distanza totale. In termini matematici, ridurrai al minimo Sum(x_i * d_i) . Questo sarebbe ciò a cui l'utente LSerni si riferisce come funzione di costo .

Tuttavia, dai tuoi commenti precedenti ho l'impressione che tu voglia ridurre al minimo la distanza totale tra i magazzini che devono essere visitati. Temo che sia un po 'più difficile trovare una soluzione ottimale per quel tipo di funzione di costo.

Quello che segue è un approccio che usa le tecniche di Programmazione intera , che sono frequentemente usate nel dominio della ricerca delle operazioni (vedi la risposta di LSerni). Capisco che quanto segue potrebbe richiedere una certa conoscenza di base nell'ottimizzazione matematica, ma potrebbe comunque essere utile per alcune persone.

Possiamo formulare l'approccio di cui sopra come un programma lineare (LP). I vincoli sono che la quantità allocata totale deve essere uguale a q e che l'allocazione di ciascun magazzino può essere al massimo c_i .

min Sum(x_i * d_i)

s.t. Sum(x_i) = q
     x_i <= c_i

Per ridurre al minimo la distanza totale tra i magazzini che devono essere visitati , dovremo introdurre alcune variabili helper binarie:

• Lascia che y_i denoti che una certa quantità ( y_i = 1 ) o non ( y_i = 0 ) sarà allocata al magazzino i .

In tal caso, sarà necessario aggiungere alcuni vincoli "big M"

x_i <= M * y_i

dove M è una certa costante di grandi dimensioni. Ciò assicurerà che x_i possa essere solo 0 ogni volta che y_i = 0 e che x_i possa essere qualsiasi quantità positiva quando y_i = 1 . Suggerimento: lascia che M sia uguale a c_i .

Il problema diventa quindi un problema binario (dove y_i è binario).

min Sum(y_i * d_i)

s.t. Sum(x_i) = q
     x_i <= c_i 
     x_i <= M * y_i

Quindi questo è il modo in cui ho tentato di risolverlo. Riempirà i magazzini, ottenendo il 100% della quantità richiesta da allocare.

Ma non va bene perché questo è solo un modo per completare l'ordine. Se l'ordine dei magazzini è stato spostato, potremmo potenzialmente ottenere un risultato diverso più efficiente.

    $order_draft1 = array();
    $quantity_process = $quantity_requested;

        foreach($breakdown as $whse_id => $quantity){ 

            for($x = $quantity_process; $x >= 0; $x--) {

                if($quantity >= $x AND $quantity_process > 0) { 
                    $quantity_process = $quantity_process - $x;
                        if($quantity==0){ $allocation_percent = 0; } 
                        else { $allocation_percent = ($x / $quantity) * 100;}
                    array_push($order_draft1, array('whse_id'=>$whse_id, 'quantity'=>$x, 'percent'=>$allocation_percent)); 
                    break;
                }


            }

        }

Se dovessi aggiungere arsort($breakdown_process); prima di foreach , eseguirà un ordine a partire dal magazzino che ha il maggior numero di azioni.

In questo caso avrò bisogno di molti diversi ordini di "bozza", ad esempio $order_draft2 = array(); , $order_draft3 = array(); e quindi di scegliere tra loro, cosa che ho fatto.

Tuttavia, in realtà non è efficiente e non funziona bene quando aumenta il numero di magazzini.