Delft University of Technology Faculty of Electrical Engineering, Mathematics and Computer Science Man Machine Interaction Group Dynamic Routing using Ant-Based Control by Adriana Camelia Suson Supervisor: Prof. Dr. Drs. L. J. M. Rothkrantz Delft, August 2010 Dynamic Routing using Ant-Based Control Thesis submitted in partial fulfilment of the requirements for the degree of MASTER OF SCIENCE in MEDIA AND KNOWLEDGE ENGINEERING by Adriana Camelia Suson born in Braşov, Romania Media and Knowledge Engineering Department of Electrical Engineering Faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS) Delft University of Technology Dynamic Routing using Ant-Based Control by Adriana Camelia Suson Department: Man Machine Interaction http://mmi.tudelft.nl/ Student Number: 1391968 Date: 23 August 2010 Committee Members: Member: Prof. Dr. Drs. L. J. M. Rothkrantz, TUDelft Member: Dr. Ir. P. Wiggers, TUDelft Member: Ir. H. Geers, TUDelft Member: Bsc. B.Tatomir, TUDelft Abstract Currentlymostcardriversusestaticroutingalgorithmsbasedontheshortestdistance betweenstartandendposition. Butthe shortestrouteisdifferentfromthe fastestroute intime. Becauseexistingroutingalgorithmslacktheabilitytoreacttodynamicchanges in the road network, drivers are not optimally routed. In this thesis we present a multi-agent approach for routing vehicle drivers using historically-based traffic information. The general workings of our solution bears strong similarities with Ant Based Control (ABC) and AntNet, but an important modification has been made, namely the adaptation of ant-like agents for spatio-temporal routing. Thedynamicroutingalgorithmproposed,routesself-interesteddriversonanintersec- tiontointersectionbasisviathefastestpathbetweenaproposedsourceandadestination. Forthistohappen,atime-expandedgraphencodesvariableroadnetworkcosts. Ant-like agents are launched in this graph. They use a technique of collective learning based on locally dependent pheromone tables. Finally, we report results obtained for part of The Netherlands’ GIS-based road net- work. Intheestablishedexperimentsetting,thenewABCmakesapositivedifferencefor drivers. An importantreductionof the travellingtime was observedin53%of the cases. The experimental results also showed that ABC clearly outperforms Static Dijkstra’s algorithm and Dynamic Dijkstra with updates algorithm. Contents Contents i List of Figures v List of Tables vii List of Symbols xi 1 Introduction 3 1.1 Problem setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Statement of objectives . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Societal relevance of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Research challenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5 Organisationof the thesis document. . . . . . . . . . . . . . . . . . . . . . 12 2 Related work 15 2.1 Taxonomy of routing systems . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Dijkstra’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 A swarm intelligence approach to routing . . . . . . . . . . . . . . . . . . . 20 2.3.1 The class of ant “inspired” algorithms . . . . . . . . . . . . . . . . . 20 2.3.1.1 Features of ant algorithms . . . . . . . . . . . . . . . . . . 22 2.3.1.2 Application of ACO to static problems . . . . . . . . . . . 24 2.3.1.3 Application of ACO to dynamic problems . . . . . . . . . . 26 2.3.2 The class of bee “inspired” routing . . . . . . . . . . . . . . . . . . 30 2.3.2.1 Bee colony’s characteristics . . . . . . . . . . . . . . . . . . 30 2.3.2.2 Applications of bee colonies . . . . . . . . . . . . . . . . . . 30 2.3.3 Hierarchicalnature-inspired routing . . . . . . . . . . . . . . . . . . 32 2.4 Traffic models for simulation of routing . . . . . . . . . . . . . . . . . . . . 33 2.4.1 Simulating traffic flow . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5 Conclusion of literature overview . . . . . . . . . . . . . . . . . . . . . . . 36 3 Model Design 39 3.1 General design aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.1.1 Centralized versus decentralized technical architecture . . . . . . . . 40 3.1.2 Travel time models . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.3 Choosing the algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1.4 Analytical-based model versus simulation-based model . . . . . . . 45 3.1.5 Output representation and update management . . . . . . . . . . . 46 3.2 Resources for the current routing system . . . . . . . . . . . . . . . . . . . 46 i ii CONTENTS 3.2.1 Spatial network formulation . . . . . . . . . . . . . . . . . . . . . . 47 3.2.2 Temporal network formulation . . . . . . . . . . . . . . . . . . . . . 50 3.3 Algorithmic approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3.1 Description of an example . . . . . . . . . . . . . . . . . . . . . . . 52 3.3.2 Routing table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3.3 Solution construction . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3.4 Updates of the routing table . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Travel time estimation methodology for a road segment . . . . . . . . . . . 59 3.5 Vehicular traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.5.1 Modelling vehicular traffic . . . . . . . . . . . . . . . . . . . . . . . 60 3.5.2 Constraints of network loading . . . . . . . . . . . . . . . . . . . . . 60 4 Implementation details 63 4.1 Development tool: Quintiq . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.1.2 Quintiq environment . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.1.3 Quintiq and databases. . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.1.4 Quintiq and PTV . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2 System architectural design . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2.1 Chosen architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2.2 UML diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.3 Algorithm pseudo-code description . . . . . . . . . . . . . . . . . . . . . . 77 4.3.1 ABC algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.3.2 Dynamic travel time estimation . . . . . . . . . . . . . . . . . . . . 78 4.4 Implementation issues. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4.1 Vehicle generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4.2 Modelling the future . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4.3 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.5 System interface description . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5 Evaluation of the routing algorithm 85 5.1 Experimental methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.1.1 General experimental settings . . . . . . . . . . . . . . . . . . . . . 86 5.1.2 Data preprocessing and filtering . . . . . . . . . . . . . . . . . . . . 86 5.1.3 Routing algorithms used for comparison. . . . . . . . . . . . . . . . 90 5.2 Path selection: adaptivity test . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.3 Traveling time: effectiveness analysis . . . . . . . . . . . . . . . . . . . . . 91 5.4 Pheromone evolution: stability test . . . . . . . . . . . . . . . . . . . . . . 93 5.5 Global improvement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.6 Analysis of the algorithm run . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.6.1 Average age of living forwardant. . . . . . . . . . . . . . . . . . . . 97 5.6.2 Number of forward ants . . . . . . . . . . . . . . . . . . . . . . . . . 98 6 Conclusions and Future Work 101 6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.2 Reached goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.3 Description of the findings . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.4 Future work or possible extensions . . . . . . . . . . . . . . . . . . . . . . 103 Bibliography 105 A Class Diagram 113 B Results of the adaptivity test 117 CONTENTS iii C Paper from Proceedings of ANTS 2008 121 D Paper from Proceedings of the 2009 Winter Simulation Conference 125