Author:

Abstract:

The study of pedestrian walking behaviour and crowd dynamics is an important topic with many applications. Many computationally efficient but less accurate macroscopic models (where the crowd is described as a whole using average quantities such as density and velocity at a certain location and time) and computationally less efficient but more accurate microscopic models (where each pedestrian is described as a separate entity) have been developed to describe the walking behaviour of individual pedestrians and large crowds. Moreover, many optimisation models have been proposed to solve problems involving pedestrians. Most of these models have hitherto focused on evacuation problems, where for a given building and an initial distribution of pedestrians, the optimal evacuation plan for each pedestrian is computed. A few researchers have also focused on design problems to find the optimal layout of a pedestrian facility or bottleneck passages. In this thesis, we consider the link between timetabling problems and crowd flow optimisation. Indeed, the assignment of events to timeslots and rooms in a timetable has an impact on the resulting people flows. For example, in a university course timetable, at the end of each timeslot, students have to switch rooms to go to their next class. This can cause congestion problems in the halls and stairwells in universities where the class rooms are concentrated in one or a few buildings. Furthermore, if the building needs to be evacuated at a certain time, this evacuation process is also influenced by the university course timetable. After all, the timetable determines how many people are present in the building in each timeslot and in which rooms. University course timetables are not the only example. The timetable at large conferences, music festivals, cultural events, or sports events also determines the people flows during the event. This thesis consists of four main parts. Chapter 2 presents a review of optimisation models for pedestrian evacuation and design problems. Relevant empirical research and descriptive (mathematical) models of pedestrian walking behaviour are also discussed. This review shows that most models include the inverse relationship between density and walking speed, but that calibration and implementation of the proposed models are lacking. Chapter 3 focuses on the university course timetabling problem (UCTP) at KU Leuven Campus Brussels. A two-stage mixed-integer programming (MIP) approach is developed to build a timetable that maximises the scheduling preferences and minimises the travel times of students between lectures in consecutive timeslots. Pedestrians are modelled using a macroscopic network model with a density-dependent arc traverse time. The model is extended to optimise evacuations time of students in the event of an emergency. Computational results show that the model succeeds in constructing timetables with reduced travel or egress times. However, the model fails to solve large real-life instances, such as the KU Leuven instance. Therefore, a heuristic approach is developed to solve the problem. In contrast to the two-stage MIP approach, the heuristic is able to find good quality solutions for the KU Leuven instance. Moreover, it succeeds in improving upon the solutions found by the two-stage MIP approach for all other test instances. In Chapter 4, we develop a generic, flexible model for timetabling incorporating resulting people flows. To keep the model generic and tractable, only the assignment of events to rooms is optimised, while the assignment of events to timeslots is considered given. The pedestrian walking behaviour and crowd dynamics are described using the microscopic pedestrian simulator Menge developed by Curtis et al. (2016). A surrogate-based tabu search heuristic is proposed to solve the problem. The surrogate model is used to speed up the search by filtering the number of candidate solutions that are evaluated using the expensive Menge simulator. The performance of different surrogate models is evaluated. The model is used to solve two applications, one where we minimise evacuation times and one where we minimise travel times between events in consecutive timeslots. The results show that for both applications the model succeeds in building timetables with significantly reduced travel or egress times. Finally, the model is implemented in a scheduling tool with graphical user interface and applied to the room assignment problem at KU Leuven Campus Brussels. It shows that our model is able to tackle real-life problem instances with large numbers of pedestrians. Finally, Chapter 5 compares the network model of Chapter 3 and the microscopic Menge simulator of Chapter 4. Using exhaustive search on small problem instances, the quality assigned to each solution in the solution space by the different models is compared in detail. Moreover, the modelling power and the robustness of the models with respect to the calibration of their parameters is discussed.