Wednesday, August 16, 2017

Suburban Fulfilment Centre

A few weeks ago I was thinking about online grocery fulfilment and different ways of getting stock to customers faster. I had some ideas about the form factor of the facilities involved and thought I'd write about what I'm calling the Suburban Fulfilment Centre (SFC).

There are many important factors that add up to make a good online shopping experience, but when you strip away everything else, customers want a service that is fast, has a large range of products, and has reasonable fees. An important way to accomplish this is to do something that I call "tightening the loop". The time between a customer buying something and the stock being replenished and available for reorder needs to be as small as possible. It's important to have stock for customers to buy, but if you don't have a stock quickly flowing in to replace it you've failed.

Unlike regular parcel delivery, grocery shipments have some constraints that makes the process more challenging. Parts of the order need to be refrigerated, and some parts have a short shelf life. You can't just put a bottle of milk and some bananas in a box with some bubble wrap and ship it across the country in a cost effective manner. These constraints mean you need to have a supply of stock close to the final destination. If you're astute, you may have noticed that I just described a grocery store. Let's play with that idea.

What's really needed is a supermarket that's able to supply a much larger range, but keeping the online shopping model at the forefront of the planning. Around my local area a lot of 5 storey apartments are being built and I started to wonder if these could fill the roll. If an fulfilment centre with the exact same external appearance was built with a ground level drive-through, the only noticeable difference would be traffic to and from the centre. It would blend into the surrounding area and supplant current facilities that don't fit into the surrounds. To explore the idea, I selected a local set of apartments to study and run some numbers on.

Apartment Building
Apartment Building
To further illustrate the idea, I've included some screenshots from StreetView of a storage company in Brisbane with a McDonald's wedged underneath it. The drive-though runs under the building and is similar to what I pictured for an ideal pick up location.

Drive Through
Ground Level Drive Through
Although I've been talking about a drive through for customers picking up orders, it would also serve as a loading dock for receiving stock and dispatching orders that get delivered directly to customers. Obviously there needs to be separation of different kinds of traffic for safety reasons, but there would be multiple drive-through lanes and when needed, one could be shut down and isolated for a delivery or dispatch.

Drive Through
Ground Level Drive Through
So how much space do we have to play with? The apartment shown above has a gross floor area of 419 m².

Floor Plan
Apartment Floor Plan
The height of the levels 1 to 4 is 11.2 meters. This gives us a volume of 4700 m³. But what does that actually mean? How much range can we fit in that volume?

Apartment Elevation
Apartment Height
Let's look at the floor plan of a supermarket and do some visualisation exercises. It should be immediately obvious that there is a lot of unused floor space, what's not seen is that of the space that is utilised a lot of it is empty space. Next time you go shopping look at the displays and imagine what would happen if all the shelving suddenly vanished. How big would the pile of stock on the floor be? Typically shelves are utilised fully side to side, but vertically they might be only 70% full, and front to back they might be only 70% full on average. Therefore it's not outrageous to suggest that volumetrically, the shelves are only half full.

Floor Plan
Supermarket Floor Plan
How much does a supermarket hold though. Let's do some Fermi approximation.

10 aisles × 2 meters high × 1 meter wide × 15 meters long × half full = 150 m³

Let's say that the grocery department holds two thirds of all the stock in a store.  This means that in total a store holds 225 m³ of product.

Just as a sanity check, that's equivalent to the volume of 92 × 1.8 m high Australian pallets. From my experience that sounds about right to fill a store from empty.

Another important number to remember is that an average supermarket stocks about 15 thousand different items. This would mean that each item on average occupies about 15 L of space. That may seem wrong but some items need much more and some need a lot less, and remember this is the raw volume of the stock, not shelf space.

Let's look at how much space a purpose built fulfilment facility uses. The image below is of a supermarket dark store without customers. This makes it easier to fulfil online orders by staff manually picking individual orders.  As you can see though, not much of the facility is actually occupied. It's a giant waste of space. I can understand why they've done it though. It's a cheap and easy way to get started with online fulfilment without going all in automating the process. I'm still surprised that going all in is questioned. Amazon did it and look at how well it worked out for them.

Warehouse
Current Dark Store Layout
I keep talking about wasted space but what's the alternative? The system in the animation below is an automated tote storage and retrieval system by Dematic. There's wasted space in this example but the design can be optimised to use a lot more space of a building. It transfers the stock to a picking station where an operator assembles orders. This configuration is referred to as a goods to person solution, which means operators don't have to walk to assemble orders. It also reduces bending, reaching, and lifting.

The other important advantage of this is that each tote is traceable and for perishable food, its use by date is also known and action can be taken to clear the stock before it's wasted.

Tote storage system
Dematic Multi-Shuttle System
Some items are so small that they may only fill part of a tote, in these cases a divider is used. In some cases items are too large to fit and will need to be stored in a bulk handling area. Over time a manufacturer may also alter their products to be tote friendly as it may offer a cost saving.

Tote storage system
Dematic Multi-Shuttle System
Let's circle back to the concept of the suburban fulfilment centre with a 4700 m³ volume. Let's say only one third of it is used for a stock management system like the one by Dematic above, and of that third only one half of it is full. That's a raw stock volume of  783 m³. If each item takes up 15 L of space that means the building can hold about 52 thousand items. There's a lot of assumptions in my calculations and the number could be much higher or lower but I think it's worth investigating further. Especially when you take into consideration that extra items above what would normally be stocked in a supermarket would most likely take less space due to lower demand.

Each SFC doesn't need to hold the full range a service offers either. It may only need to hold 30 thousand core items and 20 thousand supplemental items. There may be multiple facilities reasonably close to each other that may hold different supplemental items and a few times a day small vans move stock between them.

The SFC would also be used to supply nearby retail spaces of the company with low demand items. that are a bit esoteric. Ask yourself if a supermarket really needs that many packets of black dye on the shelf or are they only there because that's how many come in a box. It's a waste of space and it's money sitting on the shelf.

Another consideration is the capacity of the drive through. If two lanes are open for 14 hours a day and a pick up take 2 minutes, that's 840 customers per day at capacity.  If they each take a 200 L trolley load that's 168 m³ of stock per day which the facility can easily hold.

I do actually have a serious reason for thinking about this problem. The less interaction staff have with stock the better. At the moment it's common practice for stock to arrive in store on a pallet like the one seen below. Think about that for a moment, at the warehouse people manually assemble these pallets and at the store people manually disassemble them. The only outcome of this process is people with injuries from a lifetime of manual labour. Finding meaningful replacement work for these people is important but I believe that a company has a moral obligation to minimise injuries where possible.

Pallet
Pallet of stock

Finally to give you an idea of what the inside of what one of these facilities look like, the animation below is of a warehouse that does basically the same thing, only with pallets. Nothing I'm talking about is new, it's just a scaled down version of what's currently happening.

Warehouse
44m High, 12000 pallet, Jungheinrich High Rack Warehouse
I should point out that all ideas are my own and not those of my employer.  I've also purposefully used images publicly available online instead of using my own.

Saturday, August 5, 2017

Riveting Plywood to Metal

Today I'll give you a quick rundown of my experiment riveting aluminium to plywood.

Rivet
2.8 mm Plywood Riveted to 1.4 mm Aluminium
If you've read my blog before you may know I like boxes and storage solutions.  I made some prototype storage boxes last year out of 19 mm pine and plywood, and since then they have been used quiet a lot.  The main problem I have with them is they are heavy, use more material than is really needed, and are complicated to make.  I wanted to simplify things and for inspiration I turned to an ammunition case that I have from 1958.  It's made from ply and is riveted together with metal edges.  All the components themselves are not specifically strong, but when assembled the case is rather sturdy.

Ammunition Box
Ammunition Box
I happened to find some brass rivets on AliExpress that are used for material, you may be wearing some now. Have a look at your jeans.  The type I purchased are called double capped, meaning they have flat rivets on both sides.  They consist of a cap and post that are pressed together.

Rivet
Brass Rivet Cap
I ordered these because they were listed as 10 mm long.  I thought that this would mean I could join materials up to 10 mm (leaving room for compression of course).  Unfortunately I was mistaken. The length of the post is 10 mm but this only leaves 8.5 mm space for materials, and after compression of the rivets only about 5-6 mm are feasible.

Rivet
Brass Rivet Post
.
Rivet
Rivet Test Compression
For my test I planned to join some 6 mm ply to a piece of aluminium angle, but because the rivets are smaller than I planned I used 3 mm plywood.  Two 3 mm holes were drilled into the aluminium and the posts were inserted. A hole slightly larger (about 3.75 mm) was drilled in the ply, the caps inserted and the the rivets clipped together. For the final compression step no fancy tools were used. They were placed in a vice and I squashed the hell out of them.

The results speak for themselves. I think they look awesome and they will not budge.
Rivet
Aluminium Side
The dark wood and brass look nice together gives the strength I need. I think I'm on to something.
Rivet
Plywood Side
I'm not actually building a box in this post. This is just a test, and besides I don't think the size of box I want to make will work with 3 mm ply. I need slightly bigger rivets. So now we wait the standard 2 or 3 weeks for a shipment from China. :-(

There are plenty of designs for storage boxes that may be better than mine, but what I'm aiming for is a good strength to weight ratio box that can be easily assembled by people at home without exotic materials and tools.  The idea is that if you want a box you go and buy some ply and metal and use rivets you've purchased.

Friday, June 16, 2017

Merge A Data Set With A Template File To Generate Output Files

For something I'm working on I need to be able to create a large number of files by filling in fields in a template file with entries from a data set. You'd think that would be easy with Linux but I couldn't find a way to do it. (This will be where people tell me a thousand different ways to do it) I didn't think what I wanted was complicated so I wrote SimpleMerge to take care of it. It is a basic Python script that takes data from a tab delimited data file and fills in data fields in a template file.

The first row of the data file are the field identifiers to find and replace and the other rows are just data. This file can be easily generated from a spreadsheet program. The template file contains the structure of the file you intend to create, just with field identifiers in the place of real data.

I haven't done extensive testing on the program but it seems to work fine.  It handles UTF-8 file encoding and maintains the line endings of the template file for both UNIX and Windows systems. The following command generates the two files File1.txt and File2.txt as seen in the block diagram below.

SimpleMerge.py template.txt Data.txt


Block Diagram
Simple Merge Block Diagram
You can use this method on any file really, even SVG files.  Hint hint wink wink.  You can go from this template file.....

Periodic Table Symbols
SVG Template

to this in a matter of minutes. Just by replacing colour and three text fields.

Periodic Table Symbols
Generated Images

I make no guarantee as to how well this works. So my advice is to back things up before using it. Have fun.
Get The Code!
.

Saturday, June 3, 2017

Generating Stippled Images with Stiptacular

A few weeks ago I posted about how to generate stippled images from regular input images. The code was garbage at the time so I've improved it and posted it for people to use or learn from.  I only just remembered why I started this project. I found the StippleGen program from EvilMadScientist (EMS) but it was written in the processing development environment which I didn't have much luck with. I thought it'd be great to have a Python version out there as well and along the way added my own tweaks.

  • Better initial distribution of seed points via a PseudoHilbert Curve
  • Dithering to make points distribute more evenly
  • A term that sets how much points are attracted to darker areas

Since I'm using trying to replicate the work of EMS It thought I'd use their test image of Grace Kelly. Their interface is beautiful and has a few bells and whistles that mine doesn't because I figured that I could do any pre-processing in something like GIMP.

Grace Kelly
Grace Kelly test image 943x834
For an initial test I'll use 2000 points with 5 rounds of dithering and 5 rounds without dithering.  The simplest way to think of the adjustment parameter is like a contrast setting.  In this case it is three. This will cube the value of each pixel and re-scale all the data to a 0-255 range.

number_of_points = 2000
dot_radius = 2.5
non_dithering_iterations = 5
dithering_iterations = 5
adjustment_parameter = 3

Processing the image with the above settings took about 90 seconds and produces the following SVG file.

Grace Kelly
Large Grace Kelly test image - 2000 points

To demonstrate another quirk I noticed, take a look at the smaller image below.  It contains the same number of dots as the image above.  As a matter of fact, it's the exact same image just scaled down. However the dots start to look more like a face. So scale is important.  If I were to do an 8 foot print of this for a wall in my house it wouldn't look that good because I couldn't get far enough away from it for the image to emerge. I would need to use more points.
Grace Kelly
Small Grace Kelly test image - 2000 points
The image below uses 30000 points and takes about 25 minutes to generate. Writing this in something like C would help a lot..  Calculating the centroids of the Voronoi regions can be done in parallel to speed things up as well.
Grace Kelly
Grace Kelly test image - 30000 points
You may notice that some of the darker regions look a little strange. This is caused by points aligning, as can be seen in the close up below. This can be solved by reducing the number of points, dropping the adjustment parameter so the area isn't so crowded, performing more dithering steps, or just enlarging the source image before processing.

Stipple Error
Alignment artefacts
.
Get the Code!
You'll also need to install the PseudoHilbert Curve Module for Stiptacular to work.  It's a dependency that I'd like to eventually remove, but for now it's needed.

The posts below are my train of thought while developing this script.  It may help if you get a bit lost.

Voronoi Stippling
Entry and Exit Points for Space Filling Paths on a Grid
Hilbert Curve Generation With Lookup Tables
Converting Binary to Gray Code with XOR
Calculating Hilbert Curve Coordinates
Pseudo Hilbert Curve for Arbitrary Rectangular Regions - Part 1
Pseudo Hilbert Curve for Arbitrary Rectangular Regions - Part 2
Efficient Centroid Calculation for Discrete Areas
Generating Seed Points For Voronoi Stippling
Generating Stippled Images with Stiptacular

Here's a picture of a Atlantis during the STS-132 shuttle launch made of 30000 points. To infinity and beyond!
STS-132
STS-132
I wish I had the time to do an even deeper dive on this type of problem.

Saturday, May 20, 2017

Linux Text To Speech with Saved Audio

In my last blog post I described a procedure to find a forgotton PIN for 10 digit mechanical lock boxes where you enter a specific sequence of button presses to efficiently test all the combinations. The generated sequence was supplied in the form of a text file, and although this works, it's a little cumbersome moving your eyes between the buttons and paper all the time. It occurred to me that this would be a lot easier if the numbers were read to me. I then imagined how easy it would be if I had a pair of headphones and the instruction in an audio file on my phone. This seemed like the perfect application for a text to speech application and Linux.

After a little bit of research I decided to use the eSpeak speech synthesizer. It has many options for different voices for different languages and countries and allows quite a bit of customisation of the the way the text is read.

The command below that converts the text in "lockbox.txt" to audio in "lockbox.wav" uses the english voice (-ven), pronounces capital letters in a certain way (-k20), leaves a certain gap between words (-g4), reads back at a certain words per minutes (-s90), and  has a certain pitch (-p29). It's that easy!

espeak -ven -k20 -g4 -s90 -p20 -f lockbox.txt -w lockbox.wav

Before processing the file I made some slight alterations to it by replacing some of the commands in the lock box opening sequence. Originally the commands were zero thought nine, open, and clear. I replaced open with test as it was only one syllable and easier to hear.  It's also important to leave spaces between numbers otherwise it will read 11 as "eleven" instead of "one one".

Here is the instructional WAV file converted to an MP3.  It goes for 30 minutes or so and with a little bit of practice you should be able to follow along at that speed.  If you can't, that's fine, just slow the speed down in your music player.  If you screw up just go back 15 or twenty seconds to catch up.

For the YouTube fans out there, here is another version. It might possibly be the most boring and monotonous video on YouTube. That's my speciality though :-)


To be serious though I'd like to try eSpeak on a Raspberry Pi.  I think it'd be great to read out status updates and events.  Compared to some of the other synthesized voices I've heard it's actually pretty good.

Friday, May 19, 2017

Testing All The PINs On A Lock Box With A Forgotten Code

A long time ago I did a blog post on PIN coded lock boxes that you put on your house to hold a spare set of keys. Their main function is to give easy access for emergency services in case they need keys to get in if an elderly relative has a fall and can't get up. The point of my post was to demonstrate that although they have 10 buttons, look secure, and you can choose how many digits are in the PIN, they only really have 1024 PIN combinations. This is because the numbers can only be used once in each PIN.

Lock
PIN coded key lock box
The math is explained in my initial blog post but the results are below. I opined it would take about 4 hours to try all the combinations, and in this case it would require pressing the open button 1024 times, the clear button 1024 times, and pressing digits (0*1 + 1*10 + 2*45 + 3*120 + 4*210 + 5*252 + 6*210 + 7*120 + 8*45 + 9*10 + 10*1) = 5120 times.  In total there are 7168 button presses. That works out at about one button press every 2 seconds.
Table
Number of PINs vs PIN length
At some point in the 5 years since I first wrote about these locks (the time flies doesn't it) it occurred to me that I was being inefficient. Testing if the box opens doesn't clear the current code. So I  can test multiple PINs at once by just chaining them together. It's similar to the De Bruijn sequence, a mathematical tool that can be used to brute force another type of PIN. In this case however you have to reset the lock after a few buttons are pressed. To illustrate the process I'm trying to explain, imagine that the clear button has been pressed and I then enter the numbers 0 through 9, testing if the lock will open in between numbers. I've actually just tested the codes (Null) (0) (01) (012) (0123) (01234) (012345) (0123456) (01234567) (012345678) (0123456789). I've tested 11 codes with one press of the clear button, 11 presses of the open button, and just 10 digit presses. The whole process won't be this efficient but it'll be better than nothing.

But where do we start? In a perfect world, you may see by looking at the chart below and table above, that the best we can do is 1 sequence testing PINs of length 0-10,  followed by 9 sequences testing PINs of length 1-9, 35 sequences testing PINs of length 2-8, 75 sequences testing PINs of length 3-7, 90 sequences testing PINs of length 4-6, and 42 sequences testing PINs of length 5.

This will still result in 1024 presses of the test button, only 252 presses of the clear button, and (1*10)+(9*9)+(35*8)+(75*7)+(90*6)+(42*5) = 1646 presses of the number buttons. For a new total of 2922 button presses, or about 41% of the original estimate.
Graph
Distribution of PIN lengths
There's no guarantee that these sequences exist though and I had no deep understanding of how to create them, so I tried the first thing that came to mind and got lucky.

First, generate all possible combinations for each PIN length and then sort the numbers in each PIN. Then sort the PINs for each length comparing them element by element.  Start in the middle with the PINs of length 5 as there are more of these than the others. Then take the PINs of length 4 and go through them one by one from the start and place them to the left of first 5 digit PIN that could follow it. For instance (1, 5, 6, 7) might go to the left of (1, 2, 5, 6, 7) as only a 2 would have to be pressed to get to the 5 digit PIN. Do the same for the 6 digit PINs and place them on the right of the 5 digits. In this case (1, 2, 3, 5, 6, 7) might go to the right of (1, 2, 5, 6, 7) as only a 3 needs to be pressed. Repeat this left right procedure until all PINs are processed. It will look like a mess, but if you sort the sequences by length you will get a spreadsheet that looks like the one below (zoomed and rotated to fit). Look familiar? It's reflects the distribution graph above, and it shows that the sequences can be generated.

Spreadsheet
Rotated spreadsheet of the sequences
I've placed my code in a Github Gist for you to generate your own sequences in case there are a different number of buttons on your lock. If you have a lock with 10 buttons I've already generated the file for you. It looks a little different from the output of the Python file because I've done some some find and replace operations in Notepad++. I've used the word test instead of unlock as well.

Update1 There is a MP3 file of the instructions in this blog post, Linux Text To Speech With Saved Audio.

Update2 I've sorted the sequences by how often the 4 digit PINs appear in the 2009 Rock You data breach. There are two new files that cover the all the PINs. One of them has the sequences sorted by the 4 digit PIN popularity but still groups the sequences lengths, while the other sorts by PIN popularity only. An Excel file with all this data is also included so you can sort the data however you want. The associated files are in this Google drive folder. It could be argued that Rock You users and the users of lock boxes are a completely different demographic, and it's true. However, their users will exhibit similar behaviours like using birthdays and years that make the effort worthwhile. Although the instructions for the lock suggest selecting a PIN between 4 and 7 digits long, 4 digit PINs have been targeted as they are what people tend to think of when you mention PINs, even though 5 digit PINS are more secure.

So what about those locks you see in banks and other offices that have 14 buttons.  I've done the maths so you don't have to, but they can be broken with 50316 button presses. So 4 extra buttons buys you an increase in security by a factor of about 17. Not that it matters, whenever I've seen these used, people aren't too discreet about entering the PIN.

Door Lock
PIN Door Lock