Members of the defense committee:
 Prof. Dr. Ulrich Sorger, University of Luxembourg, Chairman
 AProf. Dr. Kittichai Lavagnananda, King Mongkut’s University of Technology Thonburi (KMUTT), Vicechairman
 Prof. Dr. Pascal Bouvry, University of Luxembourg, Supervisor
 Prof. Dr. Frederic Guinand, Université du Havre, Member
 Dr. Gregoire Danoy, University of Luxembourg, Member
 Dr. Dzmitry Kliazovich, ExaMotive S.A., Expert
Abstract:
Graph theory has become a hot topic in the past two decades as evidenced by the increasing number of citations in research. Its applications are found in many fields, e.g. database, clustering, routing, etc. In this thesis, two novel graphbased algorithms are presented. The first algorithm finds itself in the thriving carsharing service, while the second algorithm is about large graph discovery to unearth the unknown graph before any analyses can be performed.
In the first scenario, the automatisation of the fleet planning process in car sharing is proposed. The proposed work enhances the accuracy of the planning to the next level by taking advantage of the open data movement such as street networks, building footprints, and demographic data. By using the street network (based on graph), it solves the questionable aspect in many previous works, feasibility as they tended to use rasterisation to simplify the map, but that comes with the price of accuracy and feasibility. A benchmark suite for further research in this problem is also provided. Along with it, two optimisation models with different sets of objectives and contexts are proposed. Through a series of experiment, a novel hybrid metaheuristic algorithm is proposed. The algorithm is called NGAP, which is based on Reference Point based Nondominated Sorting genetic Algorithm (NSGAIII) and Pareto Local Search (PLS) and a novel problemspecific local search operator designed for the fleet placement problem in carsharing called Extensible Neighbourhood Search (ENS). The designed local search operator exploits the graph structure of the street network and utilises the local knowledge to improve the exploration capability. The results show that the proposed hybrid algorithm outperforms the original NSGAIII in convergence under the same execution time.
The work in smart mobility is done on city scale graphs which are considered to be medium size. However, the scale of the graphs in other fields in the realworld can be much larger than that which is why the large graph discovery algorithm is proposed as the second algorithm. To elaborate on the definition of large, some examples are required. The internet graph has over 30 billion nodes. Another one is a human brain network contains around 1011 nodes. Apart from the size, there is another aspect in realworld graph and that is the unknown. With the dynamic nature of the realworld graphs, it is almost impossible to have complete knowledge of the graph to perform an analysis that is why graph traversal is crucial as the preparation process. I propose a novel memoryless chaosbased graph traversal algorithm called Chaotic Traversal (CHAT). CHAT is the first graph traversal algorithm that utilises the chaotic attractor directly. An experiment with two wellknown chaotic attractors, Lozi map and Rössler system is conducted. The proposed algorithm is compared against the memoryless stateoftheart algorithm, Random Walk. The results demonstrate the superior performance in coverage rate over Random Walk on five tested topologies: ring, small world, random, grid and powerlaw.
In summary, the contribution of this research is twofold. Firstly, it contributes to the research society by introducing new study problems and novel approaches to propel the advance of the current stateoftheart. And secondly, it demonstrates a strong case for the conversion of research to the industrial sector to solve realworld problem scenarios.
