Maximizing pedestrian flow in shopping center layout

A problem frequently faced by shopping center planners is how to locate the shops in relation to one another. A natural objective is to achieve a suitable level of pedestrian movement throughout the center and a good layout will increase overall profitability. This requires the knowledge of pedestrian flows between pairs of shops, by itself a difficult problem. Given the relevant data is available, the optimal layout problem is a hard combinatorial optimization problem. If the shopping center is linear, it is akin to a large scale seriation problem. The authors present a dynamic programming algorithm for this case, as well as a greedy heuristic. This heuristic is adapted to the case of tree-shaped shopping centers. It is illustrated on a numerical example.