Warehouse Simulation

 

Introduction

 

In this simulation you are asked to play the part of a consultant to a warehousing company.  In an interest to lower costs and improve efficiency, the company has chosen to automate the warehouse inventory system and use a robotic crane to store and retrieve parcels.  The company has the hardware in place and has three basic strategies that each use a different algorithm to add and remove parcels.  It is your job to implement an additional strategy for use with the crane.

 

The warehouse

 

The simulated warehouse is two-dimensional, containing m rows by n columns of spaces.  Each space in the warehouse is referred to by its row and column coordinates within the warehouse.  The coordinate system works in the same fashion as computer graphics: the origin – row 0, column 0 – is in the upper left of the warehouse.  The row numbering increases as you move towards the bottom of the warehouse, and the column numbering increases as you move towards the right.  The bottom right space is row m – 1, column n – 1 for a warehouse with m rows and n columns.

 

Each space in the warehouse is either empty, or contains exactly one parcel.  All parcels used in this simulation are exactly the same size.  This simplification makes the warehouse simulation manageable, though not completely realistic.

 

Parcels are stored in and retrieved from the warehouse in groups called “orders”.  Each parcel is color coded and numbered by its order.  In addition, a parcel is displayed with a dashed border if its order is fragmented.  An order is considered fragmented if one or more of the parcels in it is not stored in a space one step away from at least one other parcel in it.  In this simulation, one step is either up one row, down one row, left one column, or right one column.  For instance, the space at (1, 1) is one step away from the four spaces at locations (0, 1), (2, 1), (1, 0), and (1, 2).  In the following picture, the gray squares are all one step away from the black square:

 

     column

row

0

1

2

  0

 

 

 

  1

 

 

 

  2

 

 

 

 

There is a single crane in the warehouse that stores and retrieves parcels.  The crane can move from its current location to a space one step away.  If the crane is at an empty space, it can store a parcel at that empty space instantaneously.  If the crane is at a space containing a parcel, it can replace that parcel with another one or simply remove the parcel from that space, each instantaneously.

 

The crane is simply a piece of movable machinery, and requires a strategy in order to carry out its operations in the warehouse.  Any strategy for use in the crane can be installed at any time except in the middle of a simulation.  There are only a few requirements for a strategy, which will be covered in a later section of this document.

 

In order to compare different strategies, the crane compiles statistics as it performs its operations.  These statistics, and how to compare the efficiency of strategies, are each covered in a later section of this document.

 

The warehouse simulation

 

The following is a screen shot of the warehouse simulation:

 

 

There is a great deal of information available in the user interface for this application.  It is separated into seven sections:

 

The section of the user interface named “Inventory” shows all of the spaces in the warehouse.  Parcels contained in spaces are painted in a color corresponding with their order number, which is displayed on the top of the parcel.  Parcels with a dashed outline are in an order that is fragmented.  The black square shows the current location of the warehouse crane.  The red square shows where the crane is headed when it is moving to another space.  Spaces the crane has visited are painted in a shade of red whose intensity depends on the number of times the crane has been in that space.

 

The section named “Crane” shows all of the relevant information for the warehouse crane.  The name of the strategy is listed, along with the current and destination locations and a brief description of its status.  The crane status describes the general operation being performed by the crane, but does not describe specific details about the strategy used by its device driver.  To print a log of the status lines for a simulation run, press the “Print log” button.

 

The section named “Statistics” shows all of the compiled statistics for the current simulation.  These values are updated in real time, and will change as a simulation progresses.  The statistics themselves are discussed in a later section of this document.  The “Print stats” button prints the current simulation statistics in the text console for the application.  These reports are useful for comparing the performance of several device drivers or successive simulation runs for the same device driver.

 

The section named “Strategies” shows the device drivers available for use in the simulation.  As long as a simulation is not currently running, you can choose the device driver to be installed in the warehouse crane by selecting the desired driver from this list.  See the “Testing and Troubleshooting” section of this document to find out how to add a new device driver to this list.

 

The section named “Simulation” contains buttons to start and stop a simulation.  Pushing the “Start” button will lock in the choice of simulation parameters and install the selected device driver in the warehouse crane.  These choices will remain until the simulation is stopped or the simulation runs to completion.  Pushing the “Stop” button will immediately end a running simulation, enabling you to select a different device driver and change the simulation parameters.

 

The section named “Parameters” shows the current simulation parameters.  As long as a simulation is not currently running, you can change the parameter values by replacing the values in the text fields.  The parameters for the simulation are set when the start button is pressed, and  remain in effect until the simulation completes or the stop button is pressed.  The parameters themselves are described in a later section of this document.

 

The section named “Animation” contains a slider that governs the speed of the animation used in the simulation.  The value for this slider can be changed at any time, whether or not a simulation is in progress.  The speed of the animation affects only the “Time taken” statistic.

 

A simulation and its parameters

 

Before you write new device driver algorithms, you should run at least one simulation for each of the provided device drivers.  This will give you an idea of their behavior, and will help you understand the meaning of the different simulation parameters.  The four simulation parameters are described below:

 

Random seed

 

This value is used to determine the order of the random numbers used by the simulation to choose what will happen next.  Each random number seed will produce a different set of random numbers, and will consequently produce a different simulation.  Choosing the same random seed for two successive simulations, however, will produce the same set of random numbers.  The other parameters for the simulation, including the device driver that is chosen, will determine whether or not two successive simulations are exactly the same, but the same random seed must be chosen in order to even have a hope of producing the same simulation twice.

 

Number of orders

 

This value represents the number of orders that will be added to the warehouse over the course of the simulation.  Depending on other factors, including the random seed and the remove bias, the number of orders that are removed from the warehouse can vary from zero to this value.  Increasing this value will produce a longer simulation.  Decreasing this value will produce a shorter simulation.

 

Maximum order size

 

This value represents the largest number of parcels that could be in an order of a randomly generated size.  Increasing this value will reduce the average number of orders that can fit in the warehouse.  Decreasing this value will increase the average number of orders that can fit in the warehouse.

 

Remove bias

 

This value represents the percentage chance that an order currently contained in the warehouse will be removed.  Increasing this value will increase the number of orders that are removed over the course of a simulation, leaving more room for orders to be added.  Decreasing this value will decrease the number of orders that are removed over the course of a simulation, leaving less empty space for orders to be added.

 

You should experiment with different values for each parameter, to gain an understanding of their influence on the simulation.

 

Strategies

 

To put it simply, a strategy tells the crane where to go when an order of parcels is to be added to or removed from the warehouse.  There are three strategies provided to you with the simulation.

 

There are two basic operations that are required of a device driver: add an order of parcels and remove an order of parcels.  The abstract class ACraneStrategy encapsulates this basic structure in a way that leaves the details up to the different strategies.  Only code that is common to all device drivers is included in the ACraneStrategy class.

 

Adding parcels

 

The common code to add an order of parcels is provided in the addOrder method in the  ACraneStrategy class.  This method takes an order of parcels to be added as its single parameter and is to return true if it was added correctly, or false if not.  The following methods are called at appropriate times in the addOrder method.

 

protected Point getAddLocation(Parcel aParcel)

 

This method must return a Point representing the row and column coordinates where the given parcel should be added to the warehouse, or null if no such point can be found.  The point to be returned should have its x component set to the appropriate row, and y component set to the appropriate column in the warehouse.  At the very least, a device driver must define this method in order for the simulation to work.

 

protected void parcelAdded(Parcel aParcel, Point aLocation)

 

This method is called immediately after the given parcel was added to the warehouse at the given location.  The given Point will have its x component set to the row, and its y component set to the column, where the given parcel was added.  A strategy should define this method if it wishes to keep track of parcels that have been added to the warehouse.  For example, the provided strategies all use this method to keep track of what parcels are in the warehouse during the course of a simulation.

 

protected void beginAdd(Order anOrder)

 

This method is called once before any parcels are actually added to the warehouse.  A strategy should override this method to if it needs to do any work before adding an order of parcels.  For example, the provided RowsStrategy uses this method to find good locations for each of the parcels in an order before any of the parcels are actually added.

 

Removing parcels

 

The common code to remove a lot of parcels is provided in the removeOrder method in the  ACraneStrategy class.  This method takes the order to be removed as its single parameter and is to return true if all of the parcels in it were removed, or false if not.  The following methods are called at appropriate times in the removeOrder method.

 

protected Point getRemoveLocation(Order anOrder)

 

This method should return a Point representing the row and column coordinates where a parcel from the given order is stored in the warehouse, or null if no such point can be found.  The point to be returned should have its x component set to the appropriate row, and y component set to the appropriate column in the warehouse.  As with the getAddLocation method, a strategy must define this method in order for the simulation to work.

 

protected void parcelRemoved(Parcel aParcel, Point aLocation)

 

This method is called immediately after the given parcel was removed from the warehouse at the given location.  The given Point will have its x component set to the row, and its y component set to the column, where the given parcel was removed.  A strategy should override this method if it wishes to keep track of what parcels have been removed from the warehouse.  For example, the provided strategies all override this method to keep track of what parcels are in the warehouse during the course of a simulation.

 

protected void beginRemove(Order anOrder)

 

This method is called once before any parcels are actually removed from the warehouse.  A strategy should override this method to if it needs to do any work before removing an order of parcels.

 

The provided strategies

 

Three example strategies are provided with the simulation.  Each represents a specific algorithm governing the adding and removing of parcels.  Each strategy, and the kind of strategy it represents, is described below:

 

Randomosity v1.0: the RandomStrategy class

 

This class uses a bare minimum of strategy.  Whenever a parcel is to be added to or removed from the warehouse, this driver randomly selects a Point at which to add or remove a parcel.  Since this driver does not keep track of the parcels in the warehouse, it is impossible for this driver to make an educated choice of a Point for either an add or remove operation.

 

Centrifugal v1.1: the CenterStrategy class

 

This class attempts to store each parcel as close to the center of the warehouse as possible.  In order to do so, it keeps track of the order numbers of parcels stored at each location in the warehouse.  Since this strategy stores this information about the state of the warehouse, it is always able to return a sensible location to add or remove a parcel.

 

Row-tastic v2.0: the RowsStrategy class

 

This class attempts to store each of the parcels in an order next to each other in the same row.  In order to do so, it keeps track of the warehouse contents in the same fashion as the CenterStrategy.  This class, however, uses the stored information to a greater extent.  Before an order of parcels is to be added, this strategy searches through its representation of the warehouse contents to find a row with enough contiguous empty space to hold all of the parcels in the order.

 

Writing your device drivers

 

To write a strategy, you will need to create a new file, write the code that defines the class, save the file with the same name as the class, and add that file to the CodeWarrior project.  You may name the class whatever you like, as long as its name contains the word “Strategy”.

 

There are additional methods in the ACraneStrategy class you need to be aware of when creating a strategy.  The HTML documentation describes all of the methods, but two require specific details.

 

The getName method must return a short name for the strategy.  You will need to override this method, and return a unique name for the strategy. 

 

The reset method is called whenever a strategy is chosen for use in the simulation, and should set all of the member data for the strategy back to their initial values.  The first thing that should be done in the reset method for any strategy is to call super.reset().  This will enable the base ACraneStrategy class to do the work it needs to do to reset itself, before your strategy does the work it needs to do to reset itself.  Consult the reset methods in the given strategies as a guide.

 

Any class that extends ACraneStrategy has access to the warehouse crane and the warehouse itself.  The data members crane and warehouse in the ACraneStrategy class are protected member data, meaning that they are accessible to classes that extend ACraneStrategy.  Depending on your strategy, you may want to call methods on those two objects.  The HTML documentation describes what methods are available in the Crane and Warehouse classes.

 

See the “Testing and Troubleshooting” section that comes later in this document for instructions on how to add your strategy to the simulation and test its performance. 

 

Statistics and comparing strategies

 

Several statistics are compiled while a simulation is running.  These statistics can be used to compare the effectiveness of different strategies.  The statistics you should use to compare strategies are described below:

 

Crane moves

 

This is the number of times the crane has moved from one space to an adjacent space, and the average number of movements made to add or remove an order.  In a real warehouse crane movements would take time, so this statistic measures the efficiency of a strategy.

 

Fragmented orders

 

This is the total number of orders that were fragmented when they were added, and the percentage of added orders that were fragmented.  Usually a high fragmentation rate leads to a greater number of crane moves, but that is not a rule.  It is more important for a strategy to use fewer crane moves than to fragment fewer orders.

 

Failed adds and failed removes

 

This is the total number of orders that could not be added or removed, and the percentage of overall add and remove attempts that failed.  A strategy should not fail to add an order unless there is not enough empty space in the warehouse to fit all of the parcels.  A device driver should never fail to remove an order.  A strategy that occasionally fails to add or remove parcels is poor.

 

Time taken

 

This is the amount of time spent to add and remove parcels in a simulation.  As graphical output and animation delay are included in this calculation, the amount of time taken will depend on several factors that have nothing to do with your algorithm.  When a simulation is run outside of a graphical environment, however, this is a reasonably accurate measure of the time taken by a device driver to do its work.

 

Testing and troubleshooting

 

When you are ready to test an ACraneStrategy, you must make that implementation available for use in the application.  In MapFactory.java, there is a method named addStrategies that adds each of the strategies to the application.  Using the existing code as a guide, add your strategy to the application.  Once it has been added to the application, it should be available for selection within the user interface.

 

In order to test your strategy, you must select it by its unique name, and run one or more simulations using it.  Reduce the animation speed to see exactly where your strategy moves the crane in different situations.  Increase the animation speed to quickly run a simulation to completion, in order to gather meaningful statistics about the performance of your strategy.  If you are unable to easily follow the behavior of your strategy, you may want to have it print feedback in the console window while a simulation is running.

 

The following are problems you may encounter when running the warehouse simulation:

 

The simulation appears to not run at all.

The selected strategy most likely does not have a call to super.reset() as the first step in its reset method.  If the selected strategy is the one you wrote, add a call to super.reset() as the first line in the reset method, and try to run the simulation again.  This error should not occur when any of the provided strategies are selected.

The simulation runs for a while, and then stops before the correct number of orders have been added.

The selected strategy failed to add two straight orders of parcels.  This is either because the warehouse is too full to add an order of parcels, or because the selected strategy returned null in the getAddLocation or getRemoveLocation methods.

The crane seems to jump around wildly in the warehouse, and parcels seem to appear and disappear.

The simulation is running too quickly for the user interface.  This is not really an error, but will make it difficult to see what is happening in the simulation.  Reduce the animation speed until the behavior is clear.

You receive a Java Exception: ArrayIndexOutOfBounds

The selected strategy may have attempted to move the crane out of the row and/or column bounds of the warehouse.  Alternately, the selected strategy may have attempted to access stored information about a location in the warehouse that is out of the row and/or column bounds of the warehouse.  This should not occur when any of the provided strategies are selected.