PHP Classes

PHP Breadth First Search: Find the shortest path to visit warehouse bins

Recommend this page to a friend!
  Info   View files Example   Screenshots Screenshots   View files View files (9)   DownloadInstall with Composer Download .zip   Reputation   Support forum   Blog    
Ratings Unique User Downloads Download Rankings
Not enough user ratingsTotal: 33 This week: 2All time: 10,970 This week: 96Up
Version License PHP version Categories
sylvane-task 1.0.0The PHP License5Algorithms, PHP 5, Geography
Description 

Author

This package can find the shortest path to visit warehouse bins.

It can generate a graph with a given number of nodes and a list of edges that can have bins in a warehouse.

The package can find the shortest path to traverse all bins from a starting point and return to the same point.

A Python component can render the warehouse bins' path as an image.

Picture of Malik Naik
  Performance   Level  
Name: Malik Naik is available for providing paid consulting. Contact Malik Naik .
Classes: 9 packages by
Country: India India
Age: 25
All time rank: 3536233 in India India
Week rank: 52 Up4 in India India Up
Innovation award
Innovation award
Nominee: 5x

Example

<?php

require_once('params.php');
require_once(
'Graph.php');
require_once(
'PathFinder.php');
require_once(
'Sylvane.php');

/**
 * Returns the unvisited nearest bin.
 *
 * @param string $start
 * The starting point of the bin.
 * @param array $bins
 * The array of subset of the bins.
 * @param array $visited
 * The array of visited bins.
 * @param array $distances
 * The distance between all pairs in the graph.
 * @param array $bin_mapping
 * The associaitve array of mapping bin to the node id.
 */
function getNearestBin($start, $bins, $visited, $distances, $bin_mapping) {

   
// Get the index of the bin in the graph.
   
$start_node_id = $bin_mapping[$start];

   
// Get all the unvisited bins.
   
$unvisited_bins = array_values(array_diff($bins, $visited));

   
// Select the first bin as the nearest.
   
$nearest = $unvisited_bins[0];

   
// Get the index of the nearest bin.
   
$nearest_node_id = $bin_mapping[$nearest];

   
// Get the distance of the bin from the start to the nearest bin.
   
$dist = $distances[$start_node_id][$nearest_node_id];

    for(
$i = 0; $i < count($unvisited_bins); $i++) {

       
// Get the bin at ith index.
       
$bin = $unvisited_bins[$i];

       
// If a shortest distance bin is found then update the nearest bin.
       
if($distances[$start_node_id][$bin_mapping[$bin]] < $dist) {
           
$nearest = $bin;
           
$nearest_node_id = $bin_mapping[$nearest];
           
$dist = $distances[$start_node_id][$nearest_node_id];
        }
    }

    return
$nearest;
}

// Instantiate the graph.
$graph = new Graph ( $num_nodes );

// Setup the graph by adding edges and nodes.
foreach ($edges as $edge) {
   
$graph->addEdge ( $edge[0], $edge[1] );
}

// Get all the bins.
$bins = array_keys( $bin_mapping );
$bins = array_diff( $bins, ['start'] );

// Initialize the Sylvance class object.
$sylvane = new Sylvane( $bins );

// Get 12 random bins.
$random_bins = $sylvane->getRandomBins ( 12 );

// Instantiate the PathFinder class object.
$path_finder = new PathFinder ( $graph );

// Get all distances.
$distances = $path_finder->getDistances();

// Get all paths.
$paths = $path_finder->getPaths();


// Initally no bin is visited.
$visited = [];

// Start from the start position in the warehouse.
$current_node = 'start';

// Store the final path.
$final_path = ['start'];

// Store the path in the graph with node ids.
$exact_path = [14];

while(
count($visited) <= 12) {

    if(
count($visited) < 12) {
       
// Get the nearest bin.
       
$nearest = getNearestBin($current_node, $random_bins, $visited, $distances, $bin_mapping);
    } else {
       
$nearest = 'start';
    }

   
// Mark the nearest bin as visited.
   
$visited[] = $nearest;

   
// Get the path from the current node to the nearest bin.
   
$current_path = $paths[$bin_mapping[$current_node]][$bin_mapping[$nearest]];

   
// Add the path to the exact path.
   
for($i = 1; $i < count($current_path); $i++) {
       
$exact_path[] = $current_path[$i];
    }

   
// Update the current node.
   
$current_node = $nearest;

   
// Add the nearest bin to the final path.
   
$final_path[] = $nearest;
}


echo
"Random Bins selected are:\n---\n";
foreach(
$random_bins as $bin) {
    echo
$bin . "\n";
}

echo
"\n\nThe optimal bin visiting order is as follows:\n---\n";

$i = 0;

foreach(
$final_path as $bin) {
    echo
$bin;

    if(
$i == count($final_path) - 1) {
        echo
"\n";
    } else {
        echo
" -> ";
    }

   
$i++;

}

echo
"\n\nThe exact path in the graph is as follows with a total distance of " . count($exact_path) . " steps:\n---\n";

$i = 0;

foreach(
$exact_path as $node) {
    echo
$node;

    if(
$i == count($exact_path) - 1) {
        echo
"\n";
    } else {
        echo
" -> ";
    }

   
$i++;

}

// Random Bins selected are:
// ---
// B1
// B4
// A6
// A7
// A10
// C1
// C5
// C11
// F2
// F9
// E11
// G5


// The optimal bin visiting order is as follows:
// ---
// start -> C1 -> C5 -> C11 -> E11 -> F9 -> F2 -> B1 -> B4 -> A6 -> A7 -> A10 -> G5 -> start


// The exact path in the graph is as follows with a total distance of 73 steps:
// ---
// 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 60 -> 61 -> 38 -> 37 -> 36 -> 35 -> 34 -> 33 -> 32 -> 31 -> 30 -> 29 -> 28 -> 27 -> 26 -> 55 -> 54 -> 13 -> 53 -> 52 -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 58 -> 59 -> 25 -> 60 -> 61 -> 38 -> 62 -> 63 -> 51 -> 50 -> 49 -> 48 -> 47 -> 46 -> 45 -> 44 -> 43 -> 42 -> 41 -> 40 -> 39 -> 57 -> 56 -> 26 -> 55 -> 54 -> 13 -> 14


Details

Sylvane Task

This is a task to find the shortest path by visiting all the bins in the warehouse and coming back to the start position in an optimal way.

Approach

  1. We are considering the aisle as the nodes in the graph and when we are at a certain aisle we can pick the item from the bin on either side of the aisle.
  2. The Modified Breadth-First Search is used to find the shortest path from all pairs of nodes in the graph.
  3. Starting with the start position this approach greedily picks the nearst node from the start position and then takes the path and then from there picks the next nearsest node until all the bins are visited.
  4. Finally, it returns back to the start position.

The graph of the warehouse is as follows: WareHouse Visualization

In the above graph, the green nodes are the aisles and are paths that can be traversed and the white nodes are the bins from which we can pick the items.

Execution

To test the working of this code. Clone this repository and then run the following command:

php main.php

Make sure you have PHP CLI installed before running the above command.

Visualization

To execute the visualization using Python you need to install the NetworkX and Matplotlib libraries. They can be installed by running the following command:

python -m pip install -r requirements.txt

Then, run the following command to generate the visualization of the Warehouse.

python visualization.py


Screenshots  
  • Warehouse.png
  Files folder image Files  
File Role Description
Accessible without login Plain text file bins.py Data Auxiliary data
Plain text file Graph.php Class Class source
Accessible without login Plain text file main.php Example Example script
Accessible without login Plain text file params.php Aux. Auxiliary script
Plain text file PathFinder.php Class Class source
Accessible without login Plain text file README.md Doc. Documentation
Accessible without login Plain text file requirements.txt Doc. Documentation
Plain text file Sylvane.php Class Class source
Accessible without login Plain text file visualization.py Data Auxiliary data

 Version Control Unique User Downloads Download Rankings  
 100%
Total:33
This week:2
All time:10,970
This week:96Up