Coloured-edge graph approach for the modelling of multimodal networks

Abstract

Many networked systems involve multiple modes of transport. Such systems are called multimodal, and examples include logistic and telecommunication networks, biomedical phenomena, conflict resolution models and manufacturing processes. Existing techniques for determining minimal paths in multimodal networks have required either heuristics or else application-specific constraints to obtain tractable problems, removing the multimodal traits of the network during analysis. In this thesis weighted coloured--edge graphs are introduced to model multimodal networks, where colours represent the modes of transportation. Optimal paths are selected using a partial order that compares the total weights in each colour, resulting in a Pareto optimal set of shortest paths. The cardinality of this set is at the core of the model's tractability. Tractability and applicability of the coloured--edge graph are addressed in this work. The tractability is firstly studied experimentally by using random as well as pathological instances of the colored--edge graph. Next, upper bounds on the cardinality of the Pareto set are established. An upper bound which is exponential in k (number of colours) is first presented. Subsequently, a probabilistic bound is developed for bicoloured--edge graphs whose weights are randomly drawn according to a bounded probability density function. An O(n^3) bound on the expected number of minimal paths (where $n$ is the number vertices) is established. The applicability of the approach is studied by means of data obtained from real multimodal transportation networks. Three cases are studied. Case (1) is a comparative analysis based on the multimodal transportation systems of New Zealand and Europe. The data used in the construction of the networks consist of digitized maps obtained from official GIS libraries. Case (2) is a large multimodal network that reproduces transport options in France. This instance is mainly focused on assessing the performance of the coloured--edge graph for very large networks. Finally, Case (3) utilizes air traffic information to build a multimodal network with a large number of modes. Modes in this case correspond to different international airlines. An important aspect of this practical study is that the multimodal networks are larger than most of those previously analyzed in the literature. The coloured--edge graph is shown in this research to be typically tractable without the need to apply any application--specific heuristic or constraints. This provides a new perspective in the analysis and optimization of systems that can be modelled as multimodal networks.