Optimisation of Car Park Designs

Abstract

The problem presented by ARUP to the UK Study Group 2014 was to investigate methods for maximising the number of car parking spaces that can be placed within a car park. This is particularly important for basement car parks in residential apartment blocks or offices where parking spaces command a high value. Currently the job of allocating spaces is done manually and is very time intensive.

The Study Group working on this problem split into teams examining different aspects of the car park design process There were three approaches taken. These approaches include a so-called "tile-and-trim" method in which an optimal layout of cars from an `infinite car park' are overlaid onto the actual car park domain; adjustments are then made to accommodate access from one lane to the next. A second approach seeks to develop an algorithm for optimising the road within a car park on the assumption that car parking spaces should fill the space and that any space needs to be adjacent to the network. A third similar approach focused on schemes for assessing the potential capacity of a small selection of specified road networks within the car park to assist the architect in selecting the optimal road network(s).

The problem is a variant of the "bin packing" problem, well known in computer science. It is further complicated by the fact that two different classes of item need to be packed (roads and cars), with both local (immediate access to a road) and global (connectivity of the road network) constraints. Bin-packing is known to be NP-hard, and hence the problem at hand has at least this level of computational complexity.

None of the approaches produced a complete solution to the problem posed. Indeed, it was quickly determined by the group that this was a very hard problem (a view reinforced by the many different possible approaches considered) requiring far longer than a week to really make significant progress. All approaches rely to differing degrees on optimisation algorithms which are inherently unreliable unless designed specifically for the intended purpose. It is also not clear whether a relatively simple automated computer algorithm will be able to "beat the eye of the architect"; additional sophistication may be required due to subtle constraints.

Apart from determining that the problem is hard, positive outcomes have included:

Determining that parking perpendicular to the road in long aisles provides the most efficient packing of cars.
Provision of code which "tiles and trims" from an infinite car park onto the given car park with interactive feedback on the number of cars in the packing.
Provision of code for optimal packing in a parallel-walled car park.
Methods for optimising a road within a given domain based on developing cost functions ensuring that cars fill the car park and have access to the road. Provision of code for optimising a single road in a given (square) space.
Description of methods for assessing the capacity of a car park for a set of given road network in order to select optimal road networks.
Some ideas for developing possible solutions further.