الرياضيات المنفصلة لنظام WMS: خوارزمية لضغط البضائع في الخلايا (الجزء 2)

عنق الزجاجة عملية

فكرة حل مشكلة

• في المرحلة الأولى ، نجد أن مجموعات الأطراف القريبة في التاريخ مضغوطة (هذه هي المقالة الأولى لمهمة التفاني هذه) ؛
• في المرحلة الثانية ، نحسب كل مجموعة من مجموعات الدُفعات أكثر المواضع المدمجة لمخلفات المنتجات في الخلايا.

int computeProblemSolution(int **aCellsData, int **aMatDist, int cellsNumb, int **aMatSolution, int **aMatAssignmentSolution) { //       //  int     .      WMS   3  ( .,    10 ),         // aMatSolutionIteration -    : // [i][0]  , [i][1]     , [i][2]             // [i][3]        int **aMatSolutionIteration = new int*[cellsNumb]; for (int count = 0; count < cellsNumb; count++) aMatSolutionIteration[count] = new int[4]; // aMatAssignmentSolutionIteration -     . [i][j] = 1 -  j   i, 0    int **aMatAssignmentSolutionIteration = new int*[cellsNumb]; for (int count = 0; count < cellsNumb; count++) aMatAssignmentSolutionIteration[count] = new int[cellsNumb]; const int maxIteration = 10; int iter = 0, recordCosts = 1000000; //    ,      int totalDemand = 0; for (int i = 0; i < cellsNumb; i++) totalDemand += aCellsData[i][1]; while (iter < maxIteration) { //     setValueIn2Array(aMatAssignmentSolutionIteration, cellsNumb, cellsNumb, 0); //    setClearSolutionArray(aMatSolutionIteration, cellsNumb, 4); //      int *aFreeContainersFitnessFunction = new int[cellsNumb]; //   ,       findGreedyRandomSolution(aCellsData, aMatDist, cellsNumb, aMatSolutionIteration, aMatAssignmentSolutionIteration, aFreeContainersFitnessFunction, false); //         improveSolutionLocalSearch(aCellsData, aMatDist, cellsNumb, aMatSolutionIteration, aMatAssignmentSolutionIteration, totalDemand); //     (      ) bool feasible = isSolutionFeasible(aMatSolutionIteration, aCellsData, cellsNumb); //    ,    if (feasible == false) { getFeasibleSolution(aCellsData, aMatDist, cellsNumb, aMatSolutionIteration, aMatAssignmentSolutionIteration); } //        ,  ,          int totalCostsIteration = getSolutionTotalCosts(aMatSolutionIteration, cellsNumb); if (totalCostsIteration < recordCosts) { recordCosts = totalCostsIteration; copy2Array(aMatSolution, aMatSolutionIteration, cellsNumb, 3); } iter++; } delete2Array(aMatSolutionIteration, cellsNumb); delete2Array(aMatAssignmentSolutionIteration, cellsNumb); return recordCosts; } 

 void findGreedyRandomSolution(int **aCellsData, int **aMatDist, int cellsNumb, int **aMatSolutionIteration, int **aMatAssignmentSolutionIteration, int *aFreeContainersFitnessFunction, bool isOldSolution) { //     int numCellsInSolution = 0; if (isOldSolution) { //     ,   aFreeContainersFitnessFunction //  numCellsInSolution ,       for (int i = 0; i < cellsNumb; i++) { for (int j = 0; j < cellsNumb; j++) { if (aMatAssignmentSolutionIteration[i][j] == 1) numCellsInSolution++; } } } //  ,        aFreeContainersFitnessFunction,     // [i][j] = 1,   j    i, 0  int **aFreeContainersAssigntCells = new int*[cellsNumb]; for (int count = 0; count < cellsNumb; count++) aFreeContainersAssigntCells[count] = new int[cellsNumb]; while (numCellsInSolution != cellsNumb) { setValueIn2Array(aFreeContainersAssigntCells, cellsNumb, cellsNumb, 0); //    //               setFreeContainersFitnessFunction(aCellsData, aMatDist, cellsNumb, aFreeContainersFitnessFunction, aFreeContainersAssigntCells); //   ,    //       ,          int selectedRandomContainer = selectGoodRandomContainer(aFreeContainersFitnessFunction, cellsNumb); //          aMatSolutionIteration[selectedRandomContainer][0] = selectedRandomContainer; aMatSolutionIteration[selectedRandomContainer][1] = 0; aMatSolutionIteration[selectedRandomContainer][2] = aCellsData[selectedRandomContainer][2]; for (int j = 0; j < cellsNumb; j++) { if (aFreeContainersAssigntCells[selectedRandomContainer][j] == 1) { aMatAssignmentSolutionIteration[selectedRandomContainer][j] = 1; aMatSolutionIteration[selectedRandomContainer][1] += aCellsData[j][1]; aMatSolutionIteration[selectedRandomContainer][2] += aMatDist[selectedRandomContainer][j]; aMatSolutionIteration[selectedRandomContainer][3] = 0; aFreeContainersFitnessFunction[j] = 10000; numCellsInSolution++; } } } delete2Array(aFreeContainersAssigntCells, cellsNumb); delete[] aFreeContainersFitnessFunction; } void setFreeContainersFitnessFunction(int **aCellsData, int **aMatDist, int cellsNumb, int *aFreeContainersFitnessFunction, int **aFreeContainersAssigntCells) { //  ,        i // [0][k] -      , [1][k] -   int **aCurrentDist = new int*[2]; for (int count = 0; count < 2; count++) aCurrentDist[count] = new int[cellsNumb]; for (int i = 0; i < cellsNumb; i++) { // 10000 -      ,        if (aFreeContainersFitnessFunction[i] >= 10000) continue; //       int containerCurrentVolume = aCellsData[i][1]; //      int containerCosts = aCellsData[i][2]; //  -,    i int amountAssignedCell = 0; setCurrentDist(aMatDist, cellsNumb, aCurrentDist, i); for (int j = 0; j < cellsNumb; j++) { int currentCell = aCurrentDist[1][j]; if (currentCell == i) continue; if (aFreeContainersFitnessFunction[currentCell] >= 10000) continue; if (aCellsData[i][0] < containerCurrentVolume + aCellsData[currentCell][1]) continue; aFreeContainersAssigntCells[i][currentCell] = 1; containerCosts += aCurrentDist[0][j]; containerCurrentVolume += aCellsData[currentCell][1]; amountAssignedCell++; } //           (     ) if (aCellsData[i][1] > 0) { aFreeContainersAssigntCells[i][i] = 1; amountAssignedCell++; } //       1 (     ),       //           1. //          .      ,     //     (   )            . //         (     ),        //   ,             . if (amountAssignedCell > 1) amountAssignedCell *= 10; if (amountAssignedCell > 0) aFreeContainersFitnessFunction[i] = containerCosts / amountAssignedCell; else aFreeContainersFitnessFunction[i] = 10000; } delete2Array(aCurrentDist, 2); } int selectGoodRandomContainer(int *aFreeContainersFitnessFunction, int cellsNumb) { int minFit = 10000; for (int i = 0; i < cellsNumb; i++) { if (minFit > aFreeContainersFitnessFunction[i]) minFit = aFreeContainersFitnessFunction[i]; } int threshold = minFit * (1.2); // 20 %      //       int *aFreeContainersThresholdFitnessFunction = new int[cellsNumb]; int containerNumber = 0; for (int i = 0; i < cellsNumb; i++) { if (threshold >= aFreeContainersFitnessFunction[i] && aFreeContainersFitnessFunction[i] < 10000) { aFreeContainersThresholdFitnessFunction[containerNumber] = i; containerNumber++; } } int randomNumber = rand() % containerNumber; int randomContainer = aFreeContainersThresholdFitnessFunction[randomNumber]; delete[] aFreeContainersThresholdFitnessFunction; return randomContainer; } 

 void findBestSolutionInNeighborhoodN1(int **aCellsData, int **aMatDist, int cellsNumb, int **aMatSolutionIteration, int **aMatAssignmentSolutionIteration, int totalDemand, bool stayFeasible) { //        int recordDeltaCosts, recordCell, recordNewContainer, recordNewCosts, recordNewPenalty, recordOldContainer, recordOldCosts, recordOldPenalty; do { recordDeltaCosts = 10000; int totalContainersCapacity = 0; for (int i = 0; i < cellsNumb; i++) if (aMatSolutionIteration[i][1] > 0) totalContainersCapacity += aCellsData[i][0]; //   - for (int j = 0; j < cellsNumb; j++) { //   ,     j int currentContainer; for (int i = 0; i < cellsNumb; i++) { if (aMatAssignmentSolutionIteration[i][j] == 1) { currentContainer = i; break; } } //   ,     j (  ) int numbAssignedCells = 0; if (aMatSolutionIteration[j][0] >= 0) { for (int i = 0; i < cellsNumb; i++) { if (aMatAssignmentSolutionIteration[j][i] == 1) { numbAssignedCells = i; } } } else { numbAssignedCells = 0; } //    j        ,     j,       //     ""           ,     if (j == currentContainer && numbAssignedCells > 1) { continue; } //         int currentTotalContainersCapacity = totalContainersCapacity - aCellsData[currentContainer][0]; //  ,   ,        j    int currentCosts = aMatDist[currentContainer][j]; //        j         ,      if (aMatSolutionIteration[currentContainer][1] - aCellsData[j][1] == 0) currentCosts += aCellsData[currentContainer][2]; //        j        ,      int currentPenelty = getPenaltyValueForSingleCell(aCellsData, aMatSolutionIteration, currentContainer, j, 0); currentCosts += currentPenelty; for (int i = 0; i < cellsNumb; i++) { if (i == currentContainer) continue; if (stayFeasible) { if (max(0, aMatSolutionIteration[i][1]) + aCellsData[j][1] > aCellsData[i][0]) continue; } else { if (currentTotalContainersCapacity + aCellsData[i][0] < totalDemand) continue; } //     int newCosts = aMatDist[i][j]; //      if (aMatSolutionIteration[i][0] == -1) newCosts += aCellsData[i][2]; //        int newPenalty = getPenaltyValueForSingleCell(aCellsData, aMatSolutionIteration, i, j, 1); newCosts += newPenalty; int deltaCosts = newCosts - currentCosts; if (deltaCosts < 0 && deltaCosts < recordDeltaCosts) { recordDeltaCosts = deltaCosts; recordCell = j; recordNewContainer = i; recordNewCosts = newCosts; recordNewPenalty = newPenalty; recordOldContainer = currentContainer; recordOldCosts = currentCosts; recordOldPenalty = currentPenelty; } } } //   ,       if (recordDeltaCosts < 0) { //             aMatSolutionIteration[recordOldContainer][1] -= aCellsData[recordCell][1]; aMatSolutionIteration[recordOldContainer][2] -= recordOldCosts; if (aMatSolutionIteration[recordOldContainer][1] == 0) aMatSolutionIteration[recordOldContainer][0] = -1; aMatSolutionIteration[recordOldContainer][3] -= recordOldPenalty; aMatAssignmentSolutionIteration[recordOldContainer][recordCell] = 0; //             aMatSolutionIteration[recordNewContainer][1] += aCellsData[recordCell][1]; aMatSolutionIteration[recordNewContainer][2] += recordNewCosts; if (aMatSolutionIteration[recordNewContainer][0] == -1) aMatSolutionIteration[recordNewContainer][0] = recordNewContainer; aMatSolutionIteration[recordNewContainer][3] += recordNewPenalty; aMatAssignmentSolutionIteration[recordNewContainer][recordCell] = 1; //checkCorrectnessSolution(aCellsData, aMatDist, aMatAssignmentSolutionIteration, aMatSolutionIteration, cellsNumb); } } while (recordDeltaCosts < 0); }