Home > Software design >  Javascript sorting array by shortest step
Javascript sorting array by shortest step

Time:05-02

This is a warehouse aisle/row/rack issue. Looking down an aisle, I have row 6 on my left and row 5 on my right.

I need to visit a list of racks in the fewest possible steps. Here is an array of rows and racks:

[   
    {"rowIndex": 5, "rowRackIndexActual": 1},
    {"rowIndex": 5, "rowRackIndexActual": 3},
    {"rowIndex": 5, "rowRackIndexActual": 4},
    {"rowIndex": 6, "rowRackIndexActual": 5},
    {"rowIndex": 6, "rowRackIndexActual": 6},
    {"rowIndex": 5, "rowRackIndexActual": 6},
    {"rowIndex": 5, "rowRackIndexActual": 7},
    {"rowIndex": 6, "rowRackIndexActual": 8},
    {"rowIndex": 5, "rowRackIndexActual": 8},
    {"rowIndex": 6, "rowRackIndexActual": 9}
]

The output should look something like this from the bottom up:

(step 9) row 6, rack 9  |  
(step 8) row 6, rack 8    row 5, rack 8 (step 7)
                        | row 5, rack 7 (step 6)
                        / row 5, rack 6 (step 5)
(step 4) row 6, rack 5  \
                        | row 5, rack 4 (step 3)
                        | row 5, rack 3 (step 2)
                        | row 5, rack 1 (step 1)
                        

This issue is with rack 8 which appears in both rows. My sort is choosing the left row first but the shortest step is actually moving up one, since my last rack was in row 5 (the right row) -- step 7, in this case;

I obviously need to keep track of when a row changes -- when we move left or right. Here is my sort statment so far:

        let prevRow = aisleRackArr[0].rowIndex; // the first item in the array
        aisleRackArr.sort(function(a, b) {
            console.log(a.rowIndex, a.rowRackIndexActual, b.rowIndex, b.rowRackIndexActual, prevRow);
            if (a.rowRackIndexActual === b.rowRackIndexActual) {
                console.log(`got the same rowRackIndex`);
                if (a.rowIndex === prevRow) {
                    console.log(`a should come first`);
                    return 0;
                } else {
                    console.log(`a came second`);
                    return 1;
                }
            }
            prevRow = b.rowIndex;
            return 0;
        });

Here is the output from the sort function (a.row, a.rack, b.row, b.rack, prevRow):

5 3 5 1 5
5 4 5 3 5
6 5 5 4 5
5 6 6 5 5
5 7 5 6 6
6 8 5 7 5
5 8 6 8 5 <---------- not returning a even though a.row===prevRow
got the same rowRackIndex
a should come first
6 9 5 8 5

At first blush, it would seem we could simply sort by rackIndex and then rowIndex. However, that would not account for the case when we need to move up in the left row and the next two racks are the same index.

What can I do to fix this?

edit Here is a picture of what it looks like:

What it looks like

CodePudding user response:

Well, regardless of the rack numbers the example below is an agnostic solution -- a reusable function that will take an array of objects and sort the objects by the primary property's ("rack") value and if they happen to be equal they will be compared by the secondary's ("row") value:

a[primary] - b[primary] || a[secondary] - b[secondary]

Which is:

{row: 6 rack: 8} - {row:5, rack: 8} OR {row: 6 rack: 8} - {row:5, rack: 8}
//           ⬆️ This equals out ⬆️ ⏭️      ⬆️  row: 5 first  ⬆️

Details are commented in example below

// Mixed order to really test capability
const rowRack = [   
  {"row": 5, "rack": 1},  
  {"row": 6, "rack": 9},  
  {"row": 5, "rack": 3},
  {"row": 5, "rack": 4},
  {"row": 6, "rack": 5},
  {"row": 5, "rack": 7},
  {"row": 6, "rack": 8},
  {"row": 5, "rack": 8},
  {"row": 5, "rack": 6},
  {"row": 5, "rack": 2}
];
/**
* Given an array of objects (objectArray), it will sort each object by the
* first given property's (primary) value. If there is a value that equals
* another value, the second given property's (secondary) value will be 
* compared to each other.
* @param {array<object>} objectArray - An array of object literals
* @param {string} primary - The property's value to compare with.
* @param {string} secondary - The property's value to compare with if the 
*                             primary values are equal. 
* @return {array<object>}
*/  

const route = (objectArray, primary, secondary) => {
  return objectArray.sort((a, b) => 
    a[primary] - b[primary] || a[secondary] - b[secondary]);
};
  
console.log(route(rowRack, "rack", "row"));
.as-console-row::after { width: 0; font-size: 0; }
.as-console-row-code { width: 100%; word-break: break-word; }
.as-console-wrapper { min-height: 100% !important; max-width: 30%; margin-left: 70%; }
<pre>
(step 9) row 6, rack 9  |  
(step 8) row 6, rack 8    row 5, rack 8 (step 7)
                        | row 5, rack 7 (step 6)
                        / row 5, rack 6 (step 5)
(step 4) row 6, rack 5  \
                        | row 5, rack 4 (step 3)
                        | row 5, rack 3 (step 2)
                        | row 5, rack 2 (step 1)
                        | row 5, rack 1 (step 0)
</pre>

CodePudding user response:

As I suspected, I needed to keep track of the current row. Since we can move up a row or down a row, each rack in each row has been given two indexes which represent the optimal route through an aisle if every rack in the aisle were selected. The "down" index is not the converse of the "up" index. When moving down a row, the first rack will be on your left. When moving up a row, the first rack will be on your right. Then, the index is assigned by over/up/over when moving up the row and over/down/over when moving down.

We take our pick list -- an array of all the items being filled for an order which also contains the row and rack in which a product can be found -- and extract out the unique aisles.

Here is a sample record in a pick list:

{
    "idorder": 527261,
    "orderIndex": 3,
    "sku": "WZH76-4-W-YRS-PKP-XL",
    "upc": "195041059206",
    "quantity": 1,
    "warehouse": 10,
    "zone": 10,
    "row": "20",
    "rack": 20,
    "tier": 1,
    "shelf": 2,
    "bin": 5,
    "rowNorm": "000020",
    "aisleNum": 1,
    "rowIndex": 2,
    "rowRackIndex": 2,
    "rowRackIndexActual": 2,
    "revRowRackIndexActual": -2,
    "ecFactor": 0,
    "aisleMaxRackIndex": 10,
    "aisleRackIndex": 3,
    "reverseAisleRackIndex": 16,
    "rackCode": "10-10-20-20"
  }

From the entire pick list we get the unique aisles:

uniqueAisles = [...new Set(pickListArr.map((a) => a.aisleNum))].keySort({aisleNum: `asc`});

Then, we loop through the aisles, selecting every product from the pick list that matches the current aisle:

sarr = [];
aisleRackArr = pickListArr.filter((r) => r.aisleNum === aa);

and then refine our aisleRackArray again by getting the unique racks for that aisle:

aisleRackArr = [...new Map(aisleRackArr.map((item) => [item.aisleRackIndex, item])).values()];

Then we figure out which direction in the aisle we're going: up or down. That isn't pertinent to this discussion so we'll skip it.

Once we know which way we're heading, we do a gross sort of every selected rack in the row -- from the order pick list -- based on it's up or down index:

if (curDir === `up`) {
    aisleRackArr.keySort({rowRackIndexActual: `asc`, rowindex: `desc`});
} else {
    aisleRackArr.keySort({revRowRackIndexActual: `asc`, rowIndex: `asc`});
}

We know our first rack based on the above sort and we know what direction we're going.

const dirFactor = curDir === `up`?1 : -1;
curRack = aisleRackArr[0];

Let's take our first record and push it into a temporary sorting array (sarr)

sarr.push({rowIndex: curRack.rowIndex, rackIndex: curRack.rowRackIndexActual, aisleNum: curAisleNum, aisleSort:  ( ( curRack.rowRackIndex * 10)) * ( dirFactor), rackCode: curRack.rackCode});

and then remove it from our aisle Rack Array:

aisleRackArr.splice(0, 1);

Now, we will loop through the remaining records in the aisle Rack Array, looking for the next rack we should move to:

while (aisleRackArr.length > 0) {
    curRack = getNextRack(aisleRackArr, dirFactor, curRack.rowIndex);

once we know our next rack, push it into the temp array and then remove it from our rack array:

    sarr.push({rowIndex: curRack.rowIndex, rackIndex: curRack.rowRackIndexActual, aisleNum: curAisleNum, aisleSort: curRack.sorter, rackCode: curRack.rackCode});
    const curIndex=aisleRackArr.indexOf(curRack);
    aisleRackArr.splice(curIndex, 1);

and continue with the loop;

}

Once we are finished with the loop, push the entire temp array into our master route array:

mapRouteArr.push(...sarr);

The code to determine the next rack:

We need to get the next three records in the array because those records will encompass every possible step we can make next: move left, move right or move up. Once we have those three record, we assign a new sort order based on the rack index (how far up or down the row we are) and if one or more of those records is in the same row (left or right) we're currently on. We'll sort those three records based on that criteria. If two of the racks are on the same level, give the rack that is in our current row precedence.

We then return that row, and the while loop stores it in the temp sort array and then removes it from the mix.

We continue on until the Rack Array is empty.

function getNextRack(rackArray, dirFactor, curRow) {
    next3Arr = rackArray.slice(0, 4);

    if (dirFactor === 1) { // going up!
        next3Arr.forEach((a) => {
            a.sorter =  ( ( a.rowRackIndexActual * 10)   ( curRow ===  a.rowIndex ? 0 : 1));
            a.currentRow = curRow;
        });
        return next3Arr.sort((a, b)=> a.sorter-b.sorter)[0];
    } else { // going down!
        next3Arr.forEach((a) => {
            a.sorter =  (( a.rowRackIndexActual) * -10) - ( curRow ===  a.rowIndex ? 1 : 0);
            a.currentRow = curRow;
        });
        return next3Arr.sort((a, b) => a.sorter - b.sorter)[0];
    }
}

My test case uses 10 orders resulting in 47 different racks that need to be visited. The result of the sort looks like this. This array accounts for all possible left/right,up/down and different row length scenarios and is exactly the way it should be:

[
    {
        "rowIndex": 2,
        "rackIndex": 2,
        "aisleNum": 1,
        "aisleSort": 20,
        "rackCode": "10-10-20-20"
    },
    {
        "rowIndex": 1,
        "rackIndex": 6,
        "aisleNum": 1,
        "aisleSort": 61,
        "rackCode": "10-10-10-70"
    },
    {
        "rowIndex": 1,
        "rackIndex": 8,
        "aisleNum": 1,
        "aisleSort": 80,
        "rackCode": "10-10-10-90"
    },
    {
        "rowIndex": 2,
        "rackIndex": 9,
        "aisleNum": 1,
        "aisleSort": 91,
        "rackCode": "10-10-20-90"
    },
    {
        "rowIndex": 3,
        "rackIndex": 9,
        "aisleNum": 2,
        "aisleSort": -100,
        "rackCode": "10-10-30-90"
    },
    {
        "rowIndex": 3,
        "rackIndex": 8,
        "aisleNum": 2,
        "aisleSort": -81,
        "rackCode": "10-10-30-80"
    },
    {
        "rowIndex": 4,
        "rackIndex": 8,
        "aisleNum": 2,
        "aisleSort": -80,
        "rackCode": "10-10-40-80"
    },
    {
        "rowIndex": 4,
        "rackIndex": 7,
        "aisleNum": 2,
        "aisleSort": -71,
        "rackCode": "10-10-40-70"
    },
    {
        "rowIndex": 4,
        "rackIndex": 4,
        "aisleNum": 2,
        "aisleSort": -41,
        "rackCode": "10-10-40-40"
    },
    {
        "rowIndex": 3,
        "rackIndex": 0,
        "aisleNum": 2,
        "aisleSort": 0,
        "rackCode": "10-10-e4-10"
    },
    {
        "rowIndex": 5,
        "rackIndex": 1,
        "aisleNum": 3,
        "aisleSort": 20,
        "rackCode": "10-10-50-10"
    },
    {
        "rowIndex": 5,
        "rackIndex": 3,
        "aisleNum": 3,
        "aisleSort": 30,
        "rackCode": "10-10-50-30"
    },
    {
        "rowIndex": 5,
        "rackIndex": 4,
        "aisleNum": 3,
        "aisleSort": 40,
        "rackCode": "10-10-50-40"
    },
    {
        "rowIndex": 6,
        "rackIndex": 5,
        "aisleNum": 3,
        "aisleSort": 51,
        "rackCode": "10-10-60-50"
    },
    {
        "rowIndex": 6,
        "rackIndex": 6,
        "aisleNum": 3,
        "aisleSort": 60,
        "rackCode": "10-10-60-60"
    },
    {
        "rowIndex": 5,
        "rackIndex": 6,
        "aisleNum": 3,
        "aisleSort": 61,
        "rackCode": "10-10-50-60"
    },
    {
        "rowIndex": 5,
        "rackIndex": 7,
        "aisleNum": 3,
        "aisleSort": 70,
        "rackCode": "10-10-50-70"
    },
    {
        "rowIndex": 5,
        "rackIndex": 8,
        "aisleNum": 3,
        "aisleSort": 80,
        "rackCode": "10-10-50-80"
    },
    {
        "rowIndex": 6,
        "rackIndex": 8,
        "aisleNum": 3,
        "aisleSort": 81,
        "rackCode": "10-10-60-80"
    },
    {
        "rowIndex": 6,
        "rackIndex": 9,
        "aisleNum": 3,
        "aisleSort": 90,
        "rackCode": "10-10-60-90"
    },
    {
        "rowIndex": 7,
        "rackIndex": 9,
        "aisleNum": 4,
        "aisleSort": -100,
        "rackCode": "10-10-70-90"
    },
    {
        "rowIndex": 8,
        "rackIndex": 8,
        "aisleNum": 4,
        "aisleSort": -80,
        "rackCode": "10-10-80-80"
    },
    {
        "rowIndex": 7,
        "rackIndex": 4,
        "aisleNum": 4,
        "aisleSort": -40,
        "rackCode": "10-10-70-40"
    },
    {
        "rowIndex": 9,
        "rackIndex": 2,
        "aisleNum": 5,
        "aisleSort": 30,
        "rackCode": "10-10-90-20"
    },
    {
        "rowIndex": 10,
        "rackIndex": 3,
        "aisleNum": 5,
        "aisleSort": 31,
        "rackCode": "10-10-100-30"
    },
    {
        "rowIndex": 10,
        "rackIndex": 7,
        "aisleNum": 5,
        "aisleSort": 70,
        "rackCode": "10-10-100-70"
    },
    {
        "rowIndex": 11,
        "rackIndex": 8,
        "aisleNum": 6,
        "aisleSort": -90,
        "rackCode": "10-10-110-80"
    },
    {
        "rowIndex": 11,
        "rackIndex": 7,
        "aisleNum": 6,
        "aisleSort": -71,
        "rackCode": "10-10-110-70"
    },
    {
        "rowIndex": 12,
        "rackIndex": 7,
        "aisleNum": 6,
        "aisleSort": -70,
        "rackCode": "10-10-120-70"
    },
    {
        "rowIndex": 12,
        "rackIndex": 5,
        "aisleNum": 6,
        "aisleSort": -51,
        "rackCode": "10-10-120-50"
    },
    {
        "rowIndex": 11,
        "rackIndex": 4,
        "aisleNum": 6,
        "aisleSort": -40,
        "rackCode": "10-10-110-40"
    },
    {
        "rowIndex": 12,
        "rackIndex": 3,
        "aisleNum": 6,
        "aisleSort": -30,
        "rackCode": "10-10-120-30"
    },
    {
        "rowIndex": 11,
        "rackIndex": 2,
        "aisleNum": 6,
        "aisleSort": -20,
        "rackCode": "10-10-110-20"
    },
    {
        "rowIndex": 11,
        "rackIndex": 1,
        "aisleNum": 6,
        "aisleSort": -11,
        "rackCode": "10-10-110-10"
    },
    {
        "rowIndex": 12,
        "rackIndex": 1,
        "aisleNum": 6,
        "aisleSort": -10,
        "rackCode": "10-10-120-10"
    },
    {
        "rowIndex": 13,
        "rackIndex": 2,
        "aisleNum": 7,
        "aisleSort": 30,
        "rackCode": "10-10-130-20"
    },
    {
        "rowIndex": 13,
        "rackIndex": 4,
        "aisleNum": 7,
        "aisleSort": 40,
        "rackCode": "10-10-130-40"
    },
    {
        "rowIndex": 13,
        "rackIndex": 6,
        "aisleNum": 7,
        "aisleSort": 60,
        "rackCode": "10-10-130-60"
    },
    {
        "rowIndex": 15,
        "rackIndex": 6,
        "aisleNum": 8,
        "aisleSort": -70,
        "rackCode": "10-10-150-60"
    },
    {
        "rowIndex": 16,
        "rackIndex": 6,
        "aisleNum": 8,
        "aisleSort": -60,
        "rackCode": "10-10-160-60"
    },
    {
        "rowIndex": 15,
        "rackIndex": 5,
        "aisleNum": 8,
        "aisleSort": -50,
        "rackCode": "10-10-150-50"
    },
    {
        "rowIndex": 15,
        "rackIndex": 4,
        "aisleNum": 8,
        "aisleSort": -41,
        "rackCode": "10-10-150-40"
    },
    {
        "rowIndex": 15,
        "rackIndex": 3,
        "aisleNum": 8,
        "aisleSort": -31,
        "rackCode": "10-10-150-30"
    },
    {
        "rowIndex": 16,
        "rackIndex": 2,
        "aisleNum": 8,
        "aisleSort": -20,
        "rackCode": "10-10-160-20"
    },
    {
        "rowIndex": 15,
        "rackIndex": 1,
        "aisleNum": 8,
        "aisleSort": -10,
        "rackCode": "10-10-150-10"
    },
    {
        "rowIndex": 17,
        "rackIndex": 2,
        "aisleNum": 9,
        "aisleSort": 20,
        "rackCode": "10-10-170-20"
    },
    {
        "rowIndex": 17,
        "rackIndex": 3,
        "aisleNum": 9,
        "aisleSort": 30,
        "rackCode": "10-10-170-30"
    }
]

enter image description here

The EC racks are end caps and they belong to the odd rows -- the rows on the right looking up the aisle. The first rack in the entire sort is colored red. Using that starting point and following the above array, we now have the shortest path possible to pick a set of orders.

As a note: when we are finished with an aisle, sometimes the closest rack in the next aisle will be behind us. Here is the calculation to determine the closest rack in the next aisle, which factors in having to turn around in the current aisle to move to the next closest rack:

if (curDir === `up`) {
    x = reverseMinRack.reverseAisleRackIndex   previousReverseAisleRackIndex   curDir === `up` ? 0 : 1;//  1 accounts for having to turn around
    y = minRack.aisleRackIndex   previousAisleRackIndex   curDir === `down` ? 0 : 1; //  1 accounts for having to turn around
}
if (x === y) {
    curDir = curDir === `up` ? `down` : `up`;
}
if (x < y) {
    curDir = `down`;
}
if (x > y) {
    curDir = `up`;
}
  • Related