Lecture: Agent Based Modeling in Transportation Lecturers: Dr. Francesco Ciari Dr. Rashid Waraich Assistant: Patrick Bösch Autumn Semester 2014 Lecture I September 16th 2014 Lecture Structure - Theory - Modeling Transport - Agent Based Modeling - Multi Agent Transport Simulation (MATSim) - Practice - Case studies (individual or in small groups) - Paper - The expected output is a case study report in the form of a proper scientific paper Modeling transport(ation) Modeling transportation Transportation: ??? Model: ??? Modeling transportation Transportation: is the movement of people, animals and goods from one location to another (Wikipedia) Model: ??? Modeling transportation Transportation: is the movement of people, animals and goods from one location to another (Wikipedia) Model: A simplified representation of a part of the real world which concentrates on certain elements considered important for its analysis from a particular point of view (Ortuzar and Wilumsen, 2006) What for? • Planning (i.e. infrastructure, systems) • Policy making Type of model depends on: – – – – Decision making context Accuracy required Data Resources Activity based paradigm Transportation Transportation: is the movement of people, animals and goods from one location to another Transportation Transportation: is the movement of people, animals and goods from one location to another Transportation Transportation: is the movement of people, animals and goods from one location to another What are the reasons of this movement? Activity approaches Activity approaches means «The consideration of revealed travel patterns in the context of a structure of activities, of the individual or household, with a framework emphasizing the importance of time and space constraints. (Goodwin, 1983) Activity approaches Allow looking at important aspects of travel like: • • • • • Activity Generation In home/out of home activities (patterns, substitution) Constraints Scheduling Social Networks (Kitamura, 1988) Modeling with agents What is an agent? • An agent: • • • • • • • Has a set of attributes/characteristics Follows given behavioral rules Has decision making capability Is goal oriented Acts in an environment and interacts with other agents Is autonomous Can learn • Agents are: • Heterogeneous • Attributes can change dynamically (Source: Macal and North, 2005) Agent Attributes Behavioral rules Decision making Memory 22 Agent-based modeling … … … Environment 23 Agent-based modeling … … … … … … … … … … … … 24 Agent-based modeling 25 Agent-based modeling 26 Agent-based modeling 27 Agent-based modeling The actors of the (real) system modeled are represented at indivudual level and implement simple rules. The behavior of the system is not explictly modeled but emerges from the simulation Agent-based modeling The actors of the (real) system that is modeled are represented at indivudual level and implement simple rules. The behavior of the system is not explictly modeled but emerges from the simulation Simple rules implemented at the micro-level (individual) allows modeling complex behavior at the macro-level (system) Pros and cons Pros: – – – – Models Individuals Agents heterogeneity Emergent behavior Can deal with complexity Cons: – Data hungry – Skilled users 30 Why Agent-Based Modeling is becoming popular? • Increasingly complex world • Availability of high resolution level data • Computer power What about transportation? Traditional Modeling Approach • Four steps model 33 Four Step Process • Trip generation – Define number of trips from and to each zone. • Trip distribution – Define for each zone where its trips are coming from and going to. • Mode choice – Define transport mode for each trip. • Route assignment – Assign a path to each route. 34 Four Step Process – Trip Generation 2238 Niederhelfenschwil 757 Hauptwil-Gottshaus 39 Wittenbach 1038 Waldkirch 1996 Niederbüren 1068 Mörschwil 2541 Goldach 1452 Untereggen 335 Andwil (SG) 543 Eggersriet 1861 Gaiserwald 2620 Oberbüren 152 St. Gallen 1282 Gossau (SG) 498 Speicher 861 Degersheim 1428 Teufen (AR) Generation Attraction 2674 Flawil 1980 Schwellbrunn 2332 Herisau 1630 Bühler 220 Stein (AR) 2359 Schlatt-Haslen 1777 Waldstatt 1160 Gais 1138 Hundwil 35 Four Step Process – Trip Distribution 2238 Niederhelfenschwil 757 Hauptwil-Gottshaus 39 Wittenbach 1038 Waldkirch 1996 Niederbüren 1068 Mörschwil 2541 Goldach 1452 Untereggen 335 Andwil (SG) 543 Eggersriet 1861 Gaiserwald 2620 Oberbüren 152 St. Gallen 1282 Gossau (SG) 498 Speicher 861 Degersheim 1428 Teufen (AR) Generation Attraction 2674 Flawil 1980 Schwellbrunn 2332 Herisau 1630 Bühler 220 Stein (AR) 2359 Schlatt-Haslen 1777 Waldstatt 1160 Gais 1138 Hundwil 36 Four Step Process – Mode Choice 2238 Niederhelfenschwil 757 Hauptwil-Gottshaus 39 Wittenbach 1038 Waldkirch 1996 Niederbüren 1068 Mörschwil 2541 Goldach 1452 Untereggen 335 Andwil (SG) 543 Eggersriet 1861 Gaiserwald 2620 Oberbüren ? 1282 Gossau (SG) 152 St. Gallen 498 Speicher 2674 Flawil 1428 Teufen (AR) 2332 Herisau 1630 Bühler 220 Stein (AR) 861 Degersheim 2359 Schlatt-Haslen 1980 Schwellbrunn 1777 Waldstatt 1160 Gais 1138 Hundwil 37 Four Step Process – Route Assignment 2238 Niederhelfenschwil 757 Hauptwil-Gottshaus 1996 Niederbüren 335 Andwil (SG) 2620 Oberbüren 1282 Gossau (SG) 2674 Flawil 543 Eggersriet 1861 Gaiserwald 152 St. Gallen 498 Speicher ? 1428 Teufen (AR) 1630 Bühler 220 Stein (AR) 861 Degersheim 1777 Waldstatt 2541 Goldach 1452 Untereggen ? ? 2332 Herisau 1980 Schwellbrunn 39 Wittenbach 1038 Waldkirch 1068 Mörschwil 2359 Schlatt-Haslen 1160 Gais 1138 Hundwil 38 Four Step Process – Facts • Sequential execution • Feedback not required, but desirable • Aggregated Model • No individual preferences of single travelers • Only single trips, no trip chains Traditional Four Step Process • Traditional approach in transport planning • Simple, well known and understood Trip Generation Trip Distribution Mode Choice Route Assignment • Static, average flows for the selected hour, e.g. peak hour 39 Iterative Four Step Process Trip Generation Trip Distribution Mode Choice Iterations • Still an aggregated model Iterative Four Step Process • Improvement of the traditional approach • Iterations allow feedback to previous process steps Route Assignment 40 Modern Modeling Approaches • Activity-based demand generation • Dynamic traffic assignment 41 Activity-based demand generation • Models the traffic demand on an individual level. • Based on a synthetic population representing the original population. • For each individual a detailed daily schedule is created, including descriptions of performed… – …activities (location, start and end time, type) – …trips (mode, departure and arrival time) • Activity chains instead of unconnected activities and trips. • Represents the first three steps of the 4 step process. 42 Activity-based demand generation • Spatial resolution can be increased from zone to building/coordinate. • High resolution input data is required such as… – …the coordinates of all locations where an activity from type X can be performed. – …the capacity of each of this locations. • Examples of activity-based models – ALBATROSS (A Learning-Based Transportation Oriented Simulation System) – TASHA (Travel Activity Scheduler for Household agents) 43 Dynamic Traffic Assignment • Supports detailed description of the demand (persons/households). • Based on trip chains instead of single trips. • Time dependent link volumes replace static traffic flows. – Spatial and temporal dynamics are supported. • Represents the fourth step of the 4 step process. 44 Dynamic Traffic Assignment • Typical implementations are simulation based. – Iterative simulation and optimization of traffic flows in a network on an individual level. • Examples of DTA implementations – – – – DYNAMIT (Ben-Akiva et.al.) DYNASMART (Mahmassani et.al.) VISSIM (PTV; only small scenarios) TRANSIMS 45 State of the art Fully agent-based approach – Combination of activity-based demand generation and dynamic traffic assignment Fully Agent-based Approach • Combines the benefits of activity-based demand generation and dynamic traffic assignment. Activity-based Demand Generation Dynamic Traffic Assignment • During the whole process, people from the synthetic population are maintained as individuals. Fully Agent-based Approach • Replaces all steps of the four step process. Synthetic Population Generation Agent-based Activity Generation (Trip Generation & Distribution) Agent-based Mode Choice Agent-based Route Assignment Agent-based Traffic Flow Simulation Individual behavior can be modeled! 47 Macro-Simulation vs. Micro-Simulation • Macro-Simulation – Based on aggregated data – Flows instead of individual movement – Often planning networks • Micro-Simulation – Population is modeled as a set of individuals – Traffic flows are based on the movement of single vehicles (or agents) and their interactions – Various traffic flow models, e.g. cellular automata model, queue model or car following model – Often high resolution networks (e.g. in navigation quality) 48 Introduction to MATSim 50 MATSim at a glance • Implementation of a fully agent-based approach as part of a transport modeling tool – Disaggregated – Activity-based – Dynamic – Agent-based • • • • Open source framework written in java (GNU License) Started ~10 years ago, community is still growing Developed by Teams at ETH Zurich, TU Berlin and senozon AG www.matsim.org Working with MATSim… • Users • Black-box use • Super-users • Add new features • Developers • Add new fundamental features Working with MATSim… • Users • Black-box use • Super-users • Add new features • Developers • Add new fundamental features MATSim Optimization Loop • Optimization is based on a co-evoluationary algorithm • Period-to-period replanning (typically day-to-day) • Each agent has total information and acts like homo economicus • Approach is valid for typical day situations initial demand execution (simulation) scoring replanning analyses MATSim – Scenario Creation • A MATSim scenario contains some mandatory as well as some supplementary data structures • Mandatory – Network – Population • Supplementary – Facilities – Transit (Schedule, Vehicles) – Counts 55 Road network High resolution navigation network, including turning rules 56 Day-plan 7:56 17:03 7:50 7:40 17:09 17:13 19:24 19:31 17:25 17:55 17:45 7:30 Resolution Speed vs Resolution physical (VISSIM) CA (TRANSIMS) Q (Cetin) Q event (MATSIM) parallel Q event (MATSIM) meso (METROPOLIS) macro (VISUM) Speed 58 Facilities „Facilities“: • Building location • Activity options • Capacity, Opening time Source: Enterprise register, Building register 59 Performance - Scenario • Transportation system in Switzerland • 24 h of an average Work-day • • • • • • 5.99 Mio Agents 1.6 Mio Facilities for 1.7 Mio Activities (5 Types) Navigation network with 1.0 Mio Links 4 Modes (others optional i.e. shared modes) 22.2 Mio Trips Routes-, Time-, (Subtour-)Mode- und „Location“-Choice One Iteration in ca. 4.5 hours Current research themes (I) • Simulation of public transport – Improved routing, multimodal simulation • Replanning improvement – Reduce the number of iterations, add other choice dimensions • Simulation of traffic lights and lanes – Focus on adaptive signal-control • Queue simulation – Parallelization • Modeling of vehicle fleet – Calculation of emissions • Electric vehicles – Simulation of the use of electric vehicles 60 Current research themes (II) • Agents coordination – Simulation of joint plans • Parking – Improvement of parking choice and search • Introduction of land-use – Integration with UrbanSim • Location choice of retailers – Addition of supply-side agents • Car-sharing – Car-sharing as an additional modal option • Weather impacts – Modeling of weather and climate change effects 61 Current scenarios • Zurich and Switzerland – Switzerland 7,6 Mio Agents – Navigation road network with 1 Mio Links • Berlin, Germany • Singapore • Gauteng, South-Africa • Sioux Falls, USA Tel Aviv, Israel Switzerland • • • • • • • Munich, Germany Germany/Europe – Main road network Padang, Indonesia Tel-Aviv, Israel Kyoto, Japan Toronto, Canada Toronto, Canada Caracas, Venezuela Berlin and Munich, Germany Gauteng, South Africa • MATSim Singapore 60FPS NEW TITLES.mkv (author: Pieter Fourie) Possible Case Study Themes • Carsharing • Electric Vehicles • Weather Questions • Laptop? – Windows – Mac Additional Literature • Bhat, C. R., J. Y. Guo, S. Srinivasan and A. Sivakumar (2004) A comprehensive econometric microsimulator for daily activity-travel patterns, Transportation Research Record, 1894, 57-66. • Kitamura, R. (1988) An evaluation of activity-based travel analysis, Transportation, 15 (1) 9–34. • Macal, C. M. and M. J. North (2005) Tutorial on agent-based modeling and simulation, Proceedings of the 37th Conference on Winter simulation, Orlando, December 2005. • Mahmassani, H. S., T. Hu and R. Jayakrishnan (1992) Dynamic traffic assignment and simulation for advanced network informatics, in N. H. Gartner and G. Improta (eds.) Compendium of the Second International Seminar on Urban Traffic Networks. • Ortuzar, J. D. D. and L. G. Willumsen (2006) Modelling Transport, John Wiley & Sons, Chichester.