Small test system

Every Pod Reposition Problem consists of warehouse properties, the initial state of the warehouse and pods departures. In this tutorial we will create a small test system to test different solvers.

This small system has 10 places, 10 pods and two pick stations with queue length three as in the picture below:

Warehouse layout.

NPLACES = 10  # Number of places
NPODS = 10  # Number of pods.
NQ = 3  # Queue length.

Then we will generate 1000 random departures of the pods from the storage area to the pick stations.

We save this information in JSON file.

LAYOUT_FILE = "../data/10-layout.json"
INITIAL_STATE_FILE = "../data/10-initial-state.json"
COSTS_FILE = "../data/10-costs.json"
DEPARTURES_FILE = "../data/10-departures.json"

Before we start we import all the necessary modules

import sys
sys.path.append('../')  # noqa: E402
import numpy.random
import prp.core.departure_generators as departure_generators
import prp.solvers.simple as simple_solvers
import prp.recorder as recorder
import prp.xy as xy
import prp.utils as utils

Layout

First we generate the layout of the system. We start with the storage area. It is one-dimensional and consists of multiple square places ordered from right to left. The size of each place is 1x1. Thus length of the storage area is the number of places in the system.

layout = xy.Layout()
storage_length = NPLACES

Initial positions of the pod.

The places has an unique ID and x-y-coordinates. We order the places by their IDs from right to left, as it shown on the picture above. The highest ID has coordinates (0,0).

for place in range(1, NPLACES + 1):
    xy_place = xy.XYPlace(place, xy.Coord(NPLACES - place, 0))
    layout.add_place(xy_place)

We symmetrically add two pick stations right from storage area [1]. One above and one below. See layout picture. Every pick station, is a queue where pods wait to be processed. In the both queues, the heads of the queue are o the right side.

station1 = xy.XYStation(1, hcoord=xy.Coord(storage_length + NQ - 1, 2),
                        tcoord=xy.Coord(storage_length, 2))
station2 = xy.XYStation(2, hcoord=xy.Coord(storage_length + NQ - 1, -2),
                        tcoord=xy.Coord(storage_length, -2))
layout.add_station(station1)
layout.add_station(station2)

Pods, costs and the initial state

From our layout we can already derive some important parameters: the set of places, the set of stations, and the queue station:

warehouse = layout.get_empty_warehouse()

As the costs, we use manhattan distances between the places and the heads of the stations. That is \(|x_\text{place}-x_\text{station head}| + |y_\text{place}-y_\text{station head}|\).

It is possible to enter these costs separately for every place and every station, but instead, we use Manhattan distances calculated by Layout.get_costs().

warehouse.set_costs(layout.get_costs())

We add 10 pods to storage area, such that pod 10 is on place 10, pod 9 is on place 9, and so on.

warehouse.set_num_pods(NPODS)
for place in warehouse.places:
    warehouse.assign_pod_to_place(place, place)

Departures

Before we start to optimize the system, we need to know, which pods will go to which picking stations. This information is stored as departures. It is a sequence of destinations tuples (pod, station) from time \(0\) to maximal time

MAX_TIME = 1000  # Number of steps the system is running.

For each departure we randomly select a pod in storage area and a station according to their weights. For our example, we want to have pods which we use very frequently and pods which we use very seldom. For the frequent ones we use larger weights, for the rare ones we use smaller weights. There are many select the pod weights, for simplicity we use the truncated geometric distribution. That means

\(weight(ID) = q^{(ID-1)}\cdot weight(1)\)

with some parameter \(q\). We calculate the parameter \(q\) in such a way, that the quotient of the most frequent pod 1 is 20 times larger than the weight of the less frequent pod 10.

\(\frac{weight(10)} {weight(1)}=20\)

As for the pick stations in our example, we choose them with equal probabilities.

STATION_WEIGHTS = {1: 0.5, 2: 0.5}  # Probability for a pod to departure to a particular station.

Now we use both pod and station weights to create a random generator of 1000 pod departures.

pod_w = departure_generators.get_geometric_weights(npods=NPODS, max_weight_ratio=MAX_WEIGHT_RATIO)
generator = departure_generators.MarkovianGenerator(warehouse,

Finally, we add a departure generator to the warehouse. We can add the departure generator directly to the warehouse with:

warehouse.set_departure_generator(generator)

but instead, we put a special recorder generator between the actual departures and the warehouse. We use this recorder to store departures and store them to a JSON file.

departure_recorder = recorder.DepartureRecorder(generator)
warehouse.set_departure_generator(departure_recorder)

Generate and store data

Before we will generate data, we store the layout and costs. If we also want to store initial state, we need to need to store it before running the warehouse.

If the distination directories do not exists, we can create them create_missing_directories_of_file from utils module. For example:

utils.create_missing_directories_of_file(LAYOUT_FILE)
utils.create_missing_directories_of_file(COSTS_FILE)
utils.create_missing_directories_of_file(INITIAL_STATE_FILE)

Then we can save the data to files:

with open(LAYOUT_FILE, 'w') as outfile:
    layout.store_to_json(outfile)
with open(COSTS_FILE, 'w') as outfile:
    recorder.store_costs_to_json(costs, outfile)
with open(INITIAL_STATE_FILE, 'w') as outfile:
    recorder.store_initial_state_to_json(warehouse, outfile)

To create departures we must run the system until the departure generator is empty. In order to be able to run a system, we need a solver. It does not matter which solver we will use, because every solver generates the same departure stream. We select some simple solver, because it is very fast.

solver = simple_solvers.SomePlaceSolver(warehouse)
while not warehouse.finished():
    place_id = solver.decide_new_place()
    warehouse.next(place_id)

After the system have run for MAX_TIME time steps, the departures are stored in departure_recorder. We can now store them to a JSON file.

utils.create_missing_directories_of_file(DEPARTURES_FILE)
with open(DEPARTURES_FILE, 'w') as outfile:
    departure_recorder.store_to_json(outfile)

Now we have all data to run our first experiments.

Footnotes

[1]	We add the station in such a way that for any place the distance to the first and to the second station is the same. And the distances from a place with lower ID is smaller than the distances from a place with higher IDs.

For a mathematical model of the Pod Reposition Problem we need a set of pods, a set of places, a set of pick stations, lengths of the queues at the pick stations, costs, the initial state and the sequence of departures.