Mathematical modelling, simulation and optimisation of dynamic transportation networks : with applications in production and traffic

摘要

In this work we provide a general classification of dynamic transportation networks (DTNs), which represent macroscopic PDE/ODE-based descriptions of network flow problems. There is a broad variety of versions depending on the application; for example it is possible to model buffers, where particles can be stored. Furthermore, we can describe the evolution of density by conservation laws and model different kinds of coupling conditions. Afterwards we consider optimisation techniques. We discuss the advantages of mixed integer optimisation and presented a general strategy how DTNs can be transformed into linear mixed-integer optimization Problems (short MIPs). Furthermore, we show how the knowledge of the problem structure can be used to introduce bounding heuristics which are extremely efficient to speed up the optimisation procedure. Within this frame, we present specific models with application in production and traffic. The first is a novel production model for the time-changing repair worker assignment. The main idea is to keep the system performance optimal whenever machines have failed and must be repaired. In general, available workers are limited and therefore a decision has to be made on which machines are repaired first. The resulting optimisation question is how the optimal worker schedule looks like to maximise the production flow. This issue is intensively analysed and numerical case studies comparing fixed and time-changing schedules are presented. The numerical results show the different opportunities of our modelling approach. With respect to the second application, we consider the LWR-based traffic flow network model. We show how coupling conditions of several junction types can be transformed into easily linearisable min-terms. We introduce a numerical framework for the Hamilton-Jacobi formulation of traffic flow and show how this correctly resolves the dynamics at the junction. We present simulations for a roundabout and compare them with existing results and computed travel times for certain routes through the network depending on the starting time of the travel. Moreover, we model traffic light settings for LWR-based traffic flow networks that can easily be adapted to arbitrary junction types and network topologies and discuss requirements for secure traffic light settings. We show the necessity of additional requirements on the switching time rate to avoid inapplicably frequent fluctuations which appear when mixed integer optimisation techniques are used, and solve this problem with previously derived techniques. Furthermore, we use the knowledge of the problem structure to develop bounding heuristics to speed up the optimisation process by providing feasible solutions for the subproblems within the Branch&Bound procedure. The resulting improvements for the optimisation procedure are remarkable and indicate the potential of combining simulation techniques with Branch & Bound procedures.