Methods For Generating Road Networks In Car Parks

This is a project I completed in 2019. The project is about comparing methods for optimal packing of car parking spaces in pre-exisiting car park boundaries.

The full project is available to read here

Summary

I'll highlight excerpts from my project so everyone doesn't have to read 63 pages about car parks unless they really want to.

Motivation

The main motivation behind making the most optimal car parks is money 💸

"

In the example of constructing a new block of flats, this directly affects the amount of potential profit from a planned estate as they will only be able to accommodate as many living spaces as they can the appropriate ratio of carparking spaces. Another example is that the cost of underground parking in the United Kingdom is typically £15,000 per space [12]. In areas that are much more costly to purchase land, such as London, this value could be much higher. These examples provide ample motivation for maximising the number of possible car parking spaces in a car park design.

Problem Statement

After defining specifically how I want to view this problem in detail, the problem is stated as:

"

Given the boundary of a car park, with a defined entrance (which also functions as an exit) on the boundary, find a layout that maximises the number of car parking spaces with as little road as possible

This was then explored from the perspective of growing the car park from the entrance. Inspired by root systems, irrigation etc. the problem was also simplified by requiring rectangular boundaries.

Determinisitic Approach

The first unsuccessful attempt at creating an algorithm for optimising the road network was a determinisitic approach that used a cost function based on attributes of the current road network. The attributes used were:

• The number of road network vertices around a vertex.
• The amount of unfilled space accessed by moving in any given direction from a vertex.
• The distance the vertex is from the entrance of the car park.
• The number of vertices connected to a vertex and its surrounding vertices.
• The amount of area wasted when branching out from a vertex at an angle not at 90 degrees to the vertex’s other connected edges.

Stochastic

Here I instead defined a rule set for how the car park can grow in a valid way. I then allowed it to randomly add new vertices at semi-optimal positions based on a stripped down cost function from the deterministic approach. This process was ran a bunch of times to get the best result. This proved to be a lot more successfull and almost always found the optimal solution (for this simplified scenario)