documentclass[a4paper,10pt,oneside,onecolumn,titlepage,final]article usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]geometry usepackagetimes usepackagehelvet usepackagetabularx usepackagefancyhdr makeatletter letKEEPheadruleheadrule letheadruleundefined letKEEPfootrulefootrule letfootruleundefined makeatother usepackagegraphicx usepackageamssymb usepackage[nooneline]caption par usepackagetitlesec titleformatsectionLargesffamilybfseriesthesection.1em titleformatsubsectionlargesffamilybfseriesthesubsection1em titleformatsubsubsectionnormalfontsffamilybfseriesthesubsubsection1em par titleformatparagraph[hang]normalfontsffamilybfseriesitshape0pt par titleformatsubparagraph[hang]smallsffamilybfseriesitshape0pt par usepackagenatbib par usepackagegerman selectlanguageUSenglish par letheadruleKEEPheadrule letfootruleKEEPfootrule par pagestylefancy lheadtextitInternational Conference on Travel Behaviour Research
rheadtextitAugust 10-14, 2003 par setlengthparindent0in setlengthparskip10pt par newedcommandmytitleAgent-Based Activities Planning for an Iterative Traffic Simulation of Switzerland par usepackagesubfigure par begindocument par begintitlepage par hrule begincenter includegraphics[width=0.5hsize]plans-server-design-gz.eps endcenter hrule par sffamily par vspace0.5in centerLARGEtextbfmytitle par vspace0.5in Large noindent textbfBryan Raney, Institute for Computational Science, ETH Zürich
noindent textbfMichael Balmer, Institute for Computational Science, ETH Zürich
noindent textbfKay Axhausen, Institute for Transport Planning and Systems (IVT), ETH Zürich
noindent textbfKai Nagel, Institute for Computational Science, ETH Zürich par par vspace0.25in noindent textbflarge Conference paper
textbflarge Session XXX par sffamily vspace0.25in par begintabular[b]cp5in par includegraphics[width=1.15in]iatbr_logo.eps.gzhspace0.1in& large vspace-0.75in textbfMoving through nets:newline textbfThe physical and social dimensions of travelnewline 10 International Conference on Travel Behaviour Researchnewline Lucerne, 10-14. August 2003 par endtabular par par vfilleject par setcounterpage1 par vspace0.25in noindent textbfsffamilyLarge mytitle par noindent Bryan Raney
Institute for Computational Science
ETH Zürich
CH-8092 Zürich, Switzerland par noindent parbox[t]0.5inPhone: +41 (0)1 632 08 92
parbox[t]0.5inFax: +41 (0)1 632 13 74
parbox[t]0.5ineMail: braney@inf.ethz.ch par noindent Michael Balmer
Institute for Computational Science
ETH Zürich
CH-8092 Zürich, Switzerland par noindent parbox[t]0.5inPhone: +41 (0)1 632 03 64
parbox[t]0.5inFax: +41 (0)1 632 13 74
parbox[t]0.5ineMail: balmermi@inf.ethz.ch par noindent Kay Axhausen
Institute for Transport Planning and Systems (IVT)
ETH Hönggerberg
CH-8093 Zürich, Switzerland par noindent parbox[t]0.5inPhone: +41 (0)1 633 39 43
parbox[t]0.5inFax: +41 (0)1 633 10 57
parbox[t]0.5ineMail: axhausen@ivt.baug.ethz.ch par noindent Kai Nagel
Institute for Computational Science
ETH Zürich
CH-8092 Zürich, Switzerland par noindent parbox[t]0.5inPhone: +41 (0)1 632 27 54
parbox[t]0.5inFax: +41 (0)1 632 13 74
parbox[t]0.5ineMail: nagel@inf.ethz.ch par vspace0.25in noindent textbfsffamilyLarge Abstract par noindent In a multi-agent transportation simulation, travelers are represented as individual ``agents'' who make independent decisions about their actions. We are implementing a large-scale version of such a simulation in order to model the traveler behavior in all of Switzerland. par Our simulation is composed of separate modules. Each module models a different set of decisions made by an agent, and calculates those decisions independently for each agent. The modules we use are listed below. par The textbfactivities generator module generates a complete 24-hour day-plan for a given agent, including each major activity (sleep, eat, work, shop, drink beer) the agent wishes to accomplish during the day, their times, and their locations. Activity times may be flexible, and can be specified by some combination of starting time, duration, and/or ending time. par The textbfroute planner module determines the mode of transportation, as well as the actual route plan taken, for each leg of the agent's chosen activity plan. Each leg simply connects one activity to another. At present our router generates routes only for automobile travel. par The textbfmicro-simulation module executes all the agents' plans simultaneously and in consequence computes the interaction between different travelers, leading e.g. to congestion. The micro-simulation provides data to the other modules about what happened during the simulated day, including the travel-time information described above, as well as the time and location of significant events to happen to agents while they are being simulated (such as arriving at their first activity destination, etc.). par There is an interdependence between the above modules. For example, plans depend on congestion (via travel-times) but congestion is a result of the execution of plans. The textbffeedback and learning module resolves the interdependence via an iterative method, where an initial plans set is slowly adapted until it is consistent with the resulting travel conditions, or until some other stopping criterion is fulfilled. In this technique, each iteration of the simulation can been seen as a separate ``day'' in the life of the agents. Each day the agents' view of the traffic network is updated, and they learn about which plans work well and which do not. par We implement the feedback mechanism with a so-called textbfagent database that allows agents to have a ``memory'' of the plans they have used during past days in the current iteration sequence. The agents also use the events data from the micro-simulation to determine performance ``scores'' for each plan. Each day of the iteration, every agent chooses a plan from its memory based on their scores, or decides to generate a brand-new plan (either a new set of route plans for a given activity-set or a new activity-set and associated route plans) based on information from the past. par This paper goes beyond what we have done in the past by investigating for the first time the effects of time choice inside the feedback loop. That is, travel time results are fed back to the time selection module, which reacts by constructing time schedules that avoid, for example, congestion. This paper contains preliminary verification results; a real-world case study is planned soon. par vfill par vspace0.25in noindent textbfsffamilyLarge Keywords par noindent Traffic Simulation, Transportation Planning, Route Planning, Activities Planning, International Conference on Travel Behaviour Research, IATBR par vspace0.25in noindent textbfsffamilyLarge Suggested citation par noindent Raney, Bryan, Michael Balmer, Kay Axhausen, and Kai Nagel (2003) mytitle, paper presented at the 10th International Conference on Travel Behaviour Research, Lucerne, August 2003. par endtitlepage par yy TODO: Make a high-resolution (300 ppi) digital file for each image, in JPEG or TIFF file. par sectionIntroduction par There is widespread agreement that, at least from a theoretical perspective, the traditional 4-step process has reached its limits. Demand generation in the traditional 4-step process is decoupled both from time-of-day and from demographics. This means that important sensitivities and effects, such as peak spreading, time-dependent tolls, or income-dependent behavior, cannot be modeled. par It is possible to include both of these aspects via the widely discussed activity-based demand generation. However, the representation of traffic in the 4-step process in independent from time. It is difficult to see how a time-dependent demand structure can be mapped on a time-independent traffic system and how results for time-dependent questions can still be meaningful. par In consequence, there are many attempts to make traffic assignment dynamic. This starts with incremental changes to the static assignment citep[e.g.][]Kaufman:etc:91,VISUM:dynamic,METROPOLIS. yy metropolis paper is published, should have complete reference However, all of these approaches need to sacrifice the nice uniqueness feature of static assignment, and it is unlikely that something similarly nice exists at all citepDaganzo:assign-w-queues. This indicates that, once one has to give up time-independence, then a completely new start might be a better option. Such new starts, called Dynamic Traffic Assignment (DTA) and being entirely simulation-based, have been pursued by a considerable number of groups. At this point, one can maybe, despite many overlaps, distinguish the following different directions: beginitemize par item Some groups are driven by requirements from the Intelligent Transportation Systems (ITS) initiatives. The ITS technology of adaptive route guidance demands that models are time-dependent, and that they can model time-dependent reactions of drivers (e.g. DYNASMART citepDYNASMART, DYNAMIT citepDYNAMIT). par item Some groups have an interest in a rather complete representation of the complete traffic dynamics while still having acceptable computing speeds. This is in general achieved by using advanced parallel computing concepts citep[e.g.][]TRANSIMS. par item Some other groups have instead concentrated on using a rather minimal representation of the traffic dynamics. The advantages of this are larger computational speed, and better conceptual clarity citep[e.g.][]Gawron:queue,ch. par item Finally, there are attempts to understand the theoretical aspects of this new approach citep[e.g.][]Cascetta:Cantarella:day2day,Bottom:thesis,Watling:stochastic,Bliemer:personal. par yy replace bliemer:personal by better reference in later versions par enditemize par Now once traffic assignment is dynamic, it is conceptually straightforward to couple it to time-dependent demand. For historical reasons, however, at this point the method to couple time-dependent demand generation and time-dependent traffic assignment is via time-dependent origin-destination (OD) matrices. That is, the system generates for each time slice, say for each hour, the typical matrix of trips going from each zone to each other zone. The traffic assignment reads all these matrices, and computes the resulting equilibrium routes. par When thinking about this, it is quickly clear that this method is giving up some of the potential advantages of the activity-based approach. For example, delays along the time axis (delays in the morning will cause delays in the evening) are completely lost in the OD-matrix approach since activity chains are decomposed into trips which are treated completely independent. Also, using the OD matrix once more decouples the route assignment completely from any demographic information that may be there. par A possible alternative is to maintain the identity of the traveler throughout the system. That is, instead of having the demand generation write OD matrices, it could write individual activity chains for each traveler, which the route assignment part of the code would then read and then via DTA find routes for those activity chains. One could even go further and include the activity generation into the feedback process (adapting activity time, activity location, or even activity participation to the delay structure in the transportation system). par The maybe only operational approach at that level is TRANSIMS citepTRANSIMS. The TRANSIMS is essentially finished and has been run on a Portland case study, but despite much documentation, we are unable to find results of this study with respect to real world behavior citepTRANSIMS:Portland. par The approach of TRANSIMS would now probably be called ``agent-based'' or ``multi-agent'', since it tracks each individual traveler agent through its day. The TRANSIMS design, however, is somewhat contrary to an agent-based design, since it does not keep consolidated person information in one place, but has, say, demographic data, activity plans, route plans, performance information, or information about past plans all in different files. Nevertheless, the agent-based information can be reconstructed if needed. par Our own research has been oriented to extend TRANSIMS to make it entirely agent-based (which means to have consolidated agent information, and also to actually use it, for example by explicitly using several plans per agent), and then to move away from the day-to-day logic that is inherently included in the existing TRANSIMS design. This paper is an intermediate result along the way to that eventual goal. We have already in the past achieved a completely agent-based dynamic traffic assignment citepch. The behavior of that system was similar to other existing DTA systems, but it had the following differences: beginitemize par item The traffic microsimulation was, because of parallel computing technique, considerably faster than any other approach we are aware of - it is capable to compute a complete car traffic of a 24-hour day for a population of several millions in several minutes citepqueue. par item The whole approach was, via an agent database, completely agent-based. That is, each agent ``remembers'' all plans that it ever executes during the simulation process, together with scores that measure the performance of each plan. In general, the agent selects between the ``known'' plans with a multinomial logit model, but from time to time, a random plan is tested or new plans are added. par enditemize par This paper now goes beyond DTA and for the first time includes activity feedback into the process. Although in the long run it is intended to include the complete activity planning process, consisting of activity pattern choice, activity location choice, and activity time choice, into the process, at this point only a time choice module was available. This paper in consequence refers to activity time choice only; for information regarding other dimensions of activity replanning, please see citepga4acts. par Time choice for whole activities means that we assume activities plus their locations are given, but the traveler-agent still needs to decide how much time to allocate to each activity, and when to start the whole chain. This problem is related to departure time choice citep[e.g.][]Arnott:etc:bottleneck,METROPOLIS, but it is more complicated: The task is to position the whole activity chain optimally into the complete day. This means that, in contrast to conventional departure time modeling, a traveler that has a lot of activities planned after work is more apt to start early than one without this. In addition, the system picks up travel time information at the time choice level. That is, it will include knowledge about travel times from one activity to the next, as a function of time-of-day, into the decision-making process. par This paper will be structured as follows: After an explanation of the overall simulation structure (Sec. refsec:structure), where all the different modules are explained, it will discuss the utility function that is used for scoring different plans (Sec. refsec:util-fcns). This is then followed by a section discussing results which are obtained with a testing scenario, which is used to establish the functionality of the code (Sec. refsec:test-case). Sec. refsec:discussion will discuss some of the artifacts of our preliminary results, from which assumptions they derive, and how we intend to improve the system. This section will also contain some outlook on our future plans regarding real-world activity-based simulations. The paper is concluded by a summary. par sectionSimulation Structure labelsec:structure par Traffic simulations for transportation planning typically consist of the following modules (Fig. reffig:bubbles):beginitemize par item textbfPopulation generation. Demographic data is disaggregated so that one obtains individual households and individual household members, with certain characteristics, such as a street address, car ownership, or household income citepBeckman:pops. - This module is not used for our current investigations but will be used in future. par item textbfActivities generation. For each individual, a set of activities (home, going shopping, going to work, etc.) and activity locations for a day is generated citepVaughn:etc:HATPs,Bowman:thesis. - This module is introduced in this paper. par item textbfModal and route choice. For each individual, the modes are selected and routes are generated that connect activities at different locations (see Sec. refsec:router). The routing should be dynamic in order to adequately model time-dependent congestion effects. par item textbfMobility simulation. Up to here, all individuals have made emphplans (or emphstrategies) about their behavior. The mobility simulation executes all those plans simultaneously (see Sec. refsec:mobsim). In particular, we now obtain the result of emphinteractions between the plans - for example congestion. par item textbfFeedback. In addition, such an approach needs to make the modules consistent with each other (Sec. refsec:learning). For example, plans depend on congestion, but congestion depends on plans. A widely accepted method to resolve this is systematic relaxation citepKaufman:etc:91,Nagel:thesis,Bottom:thesis - that is, make preliminary plans, run the traffic micro-simulation, adapt the plans, run the traffic micro-simulation again, etc., until consistency between modules is reached. The method is somewhat similar to the Frank-Wolfe-algorithm in static assignment, or in more general terms to a standard relaxation technique in numerical analysis. par enditemize This modularization has in fact been used for a long time; the main difference to earlier implementations is that it is now feasible to make all modules completely microscopic, i.e. each traveler is individually represented in all modules. par As of now, not all of the above modules are currently implemented. This paper discusses results obtained with a version of the simulation system that consists of car-only versions of the activity generator, the router, the mobility simulation, and the feedback. par These modules will be described in more detail in the following sub-sections. It should be noted that in particular the feedback system is unique in that it explicitly keeps track of many strategies of each individual traveler. Most simulation systems assume either only one strategy per traveler, or they group travelers together according to their characteristics, for example by common destination. par beginfigure begincenter captionSimulation modules. labelfig:bubbles vspace1em hrule vspace1em includegraphics[width=0.7hsize]transims-bubbles-fig.eps endcenter hrule endfigure par subsectionThe Day Plan with Activities par The activities generator (Sec. refsec:acts-gen) and router (Sec. refsec:router) modules are used by the agents in the simulation system to make decisions and fill in parts of their plan (or emphstrategy) for each day. par That plan is a list of activities to be executed throughout the entire day (24 hours), and the trips connecting the activities. Activities describe what the agent wants to do or where it wants to be during the day, and trips describe how the agent moves from one activity to the next. Trips are handled by the router, described in Sec. refsec:router. par Each activity in the day's plan is described by a type (e.g. home, work, shopping, leisure), a location, and timing information. Timing information usually consists of just the activity's duration, but might also include an absolute ending time (i.e. closing time for shops). par note three parts to activities feedback par The process an agent can use to generate an activity plan can be divided into three parts: pattern choice, location choice, and timing choice. par The emphpattern choice determines which activities to perform during the day, and in what order. For example, and agent might decide whether or not to go shopping, and if so, before or after work. par The emphlocation choice determines where the agent will perform each activity. For some activities, such as home/sleeping, and work, this decision is made very infrequently, while for other activities, such as shopping, the agent might choose a different location each time it wants to perform the activity. (E.g., bakery close to home, grocery store near work) par The emphtime choice determines the specific timing of when to start the day, and how much time to allocate to each activity. par These decisions can be made all at once by a single module, or separate modules can be used to handle each one individually. For this paper we have only implemented the time choice decision module, and keep the activity pattern and locations fixed. This module is described in the next section. par subsectionActivities Generation Module labelsec:acts-gen par Given the current traffic situation and an activity pattern with specified locations, the activities generation module calculates the optimal durations to apply to each activity. par note Connections par The activities generator is aware of the traffic situation because it reads the events information provided by the mobility simulation (see Sec. refsec:mobsim). From this information it builds a representation of the travel times that were encountered by agents traveling from one location in the network to another starting at various times of day. The data is stored by geographic coordinates and by time of day, which for speed is aggregated into 15-minute time bins. From this model the module can estimate the time it would take to make any arbitrary trip within the network by matching nearby coordinates and/or travel-times and interpolating the desired data from them. par note GA par This module uses a genetic algorithm approach to generate plans. Each activity type (work, shop, etc.) has a specific emphutility function that tells the module how much ``good'' an activity does for its agent. The specific utility functions are described below in Sec. refsec:util-fcns. The utility of an activity is determined by comparing the specific time of day that the agent starts performing that activity, the time when the agent stops, and how long the agent on that activity spent in total with the activities ``preferred'' start time, end time and duration. par The genetic algorithm essentially compares the utilities of many different potential plans and chooses the best one. A potential plan is just a proposed set of durations for the activities. The first activity in the plan (typically ``home'') always begins at midnight (00:00) and the last activity (also ``home'') ends at midnight (24:00). Coupling this information with the proposed durations and the estimates of the trip times from the connection data, the module can compute a score for any potential plan. par The genetic algorithm searches for an optimal (or near-optimal) plan using the standard operations of genetic algorithms, mutation and crossover. Mutation causes a random alteration of a plan, while crossover combines the information from two plans into a new plan. For reasons of speed this process is cut off after 250 ``generations'' of plans (using a population size of 25), and the best plan is returned to the agent. par One important consequence is that the algorithm returns only one solution. That solution is the best one that the GA has found within the time allocated to it. This is in stark difference to standard random utility models that chose between different options with exponentially weighted probabilities. As one will see later, this causes many travelers to concentrate on the same options, rather than spreading out through time. par yy above may need modif once rnd seed is changed every time when time ch module is called par subsectionRouting Module labelsec:router par Successive activities at different locations are connected by trips that use the transportation network. Trips are described by their mode and mode-specific information. For example, a car-mode trip contains a description of the vehicle's route through the network from the location of the previous activity to the location of the next activity. In principle trips can be selected from different mode types, but at present we only model car trips. par The routing module generates those paths that guide agents through the network, as part of the description for the trips that connect their activities. The trips have (expected) starting times, and the router needs to be sensitive to congestion so that it tends to avoid congested links. par The router we use for the present study is based on Dijkstra's shortest-path algorithm, but ``shortness'' is measured by the time it takes an agent to travel down a link (road segment) in the network. These times depend on how congested the links are, and so they change throughout the day. This is implemented in the following way: The way a Dijkstra algorithm searches a shortest path can be interpreted as expanding, from the starting point of the trip, a network-oriented version of a wave front. In order to make the algorithm time-dependent, the speed of this wave front along a link is made to depend on when this wave front enters the link citep[e.g.][]Jacob:etc:comp. par That is, for each link $l$ we need a function $c_l(t)$ which returns the link ``cost'' ($=$ link travel time) for a vehicle entering at time $t$. This information is taken from a run of the traffic simulation. In order to make the look-up of $c_l(t)$ reasonably fast, we aggregate over 15-min bins, during which the cost function is kept constant. That is, all vehicles entering a link between e.g. 9am and 9:15am will contribute to the average link travel time during that time period. par subsectionMobility Simulation labelsec:mobsim par As a traffic micro-simulation we use an improved version of a so-called ``queue simulation'' citepGawron:queue. The improvements are an implementation on parallel computers, and an improved intersection dynamics, which ensures a fair sharing of the intersection capacity among incoming traffic streams citepqueue,queue-trb03. The details of the traffic simulation are not particularly important for this paper; we expect many traffic simulations to reproduce similar results. The important features of our simulation are:beginitemize par item Plans following. The feedback framework generates individual day plans for each individual vehicle, and the traffic simulation needs to have travelers/vehicles which follow those plans. This implies that the traffic simulation needs to be microscopic, that is, all individual travelers/vehicles are resolved. Beyond that, however, it does not prescribe the dynamics; everything is possible from smooth particle hydrodynamics (e.g. DYNAMIT, DYNASMART) to virtual reality micro-simulations (e.g. TRANSIMS). par item Trip chaining. As described in Sec. refsec:acts-gen, the day plan of an agent consists of a list of activities (with associated durations) and the trips needed to connect the activities. The trips are not independent, but ``chained'' together throughout the day. The simulation should be implemented so that a late arrival (due to traffic congestion) of one trip shifts the rest of the day's schedule accordingly. par item Computational speed. We need to run many simulations of 24-hour days -- usually about 50 emphfor a single scenario. This means that a computational speed of 100 times faster than real time on a road network with several thousands of links (road segments) and several millions of travelers is desirable. Our queue simulation demonstrates that this is feasible. par item Congestion build-up and queue spillback. Although this is not a requirement for the framework in general, the results of the present paper depend on the fact that congestion normally starts at bottlenecks (i.e. where demand is higher than capacity), but then spills backwards into the system and across intersections. Once such congestion is there, it takes a long time to dissolve. The model should reflect this, emphand it should reflect the physical space that the queued vehicles occupy in the system. enditemize par We keep the simulation as simple as we can, which means we do not perform any data aggregation within the simulation. It simply dumps out raw data, in the form of ``events,'' which tell the time and location where something interesting happens to an agent. These events can be parsed and aggregated, if necessary, by the other modules to obtain any information they may need about what happened in the simulation. At present the simulation only outputs events for agents entering or exiting a link, but other interesting events might be when agents encounter congestion, change speed, etc. par A major advantage of the queue simulation, besides its simplicity, is that it can run directly off the data typically available for transportation planning purposes. This is no longer true for more realistic simulations, which need, for example, the number of lanes including pocket and weaving lanes, turn connectivities across intersections, or signal schedules. par subsectionLearning and Feedback via the Agent Database labelsec:learning par As mentioned above, plans (such as routes) and congestion need to be made consistent. This is achieved via a relaxation technique citepKaufman:etc:91,Nagel:thesis,Bottom:thesis: beginenumerate par item The system begins with an initial set of strategies, one per agent. The initial strategy is the fully specified activity plan connected by trips with routes based on free speed travel times, which represent a network with no congestion. par item For each agent, the new strategy is stored in the agent database citepRaney:Nagel:strc2002,agdb, which represents its memory of previously tried strategies. Since the agents have only one strategy apiece, they automatically select this as their next strategy to execute. par item labelit:sim The traffic simulation is executed with the set of selected strategies. par item Each agent measures the performance of its strategy based on the outcome of the simulation. ``Performance'' is measured by the same utility functions as used by the activities generator, described in Sec. refsec:util-fcns. This information is stored for all the agents in the agent database, associated with the strategy that was used. par item labelit:frac If less than 100 iterations have been performed so far in the cycle, then 20% of the population chooses to obtain a new plan they have never tried before. (After 100 iterations, plans are only chosen from memory.) Each agent picks a strategy at random from its memory and sends it to either the activities generator or route planner (with equal probability) to update it based on the newest travel-time data from the last traffic simulation. The returned plan is added to the agent database as a new strategy and, being new, is mandatorialy selected by the agent for the next simulation run. Note that plans coming from the activities generator are also sent to the router for updated routes. par Since the router needs trip start times to create a route, these are estimated from the durations of the activities preceding the trip, and from the travel times most recently encountered by an agent for the trips preceding the current trip. Durations are always known, but if travel-time for a trip is missing, it is assumed to be 0. par item labelit:select 70% of the agents (or 90% if past iteration 100) choose a previously tried strategy from the agent database, by comparing the performance values for the different strategies, without looking at any other information about them. Specifically, they use a multinomial logit model citepBen-Akiva:book

$$p_i propto e^{beta U_i}$$

for the probability $p_i$ to select route $i$, where $U_i (le 0)$is the corresponding memorized total utility and $beta$ is an empirical constant. This process is explained in detail in citetRaney:Nagel:strc2002,fgcs,agdb. We differ from these by setting $beta$ to 0.01 in this work. par item labelit:random The rest of the agents (10%) choose a plan emphat random from their memory, using a uniform probability for each plan, and ignoring plan performance. The value of $beta$ in step refit:select effects how likely agents choose ``non-best'' plans. Higher values of $beta$ lead toward the best plan being chosen more often, while smaller values provide a more randomized choice. This random choice ensures that no matter what the value of $beta$ is, no plan is left out of consideration. Some agents will be sure to use even the worst plans in their memory (which may or may not improve their performance with successive tries). par item labelit:relax This cycle (i.e. steps refit:sim through refit:select) is run for 150 times. Note that in the last 50 cycles no new plans are created by the agents. par endenumerate par sectionUtility Functions for the Day Plan labelsec:util-fcns par note Explain the problem par When the activities generator module generates the timing for the activity schedule, it optimizes over the emphentire day all at once, not piece-by-piece. This is to allow trade-offs between the different parts of the day. For example, if the day has a large number of activities that need to be accomplished, the activities generator module should be able to do something like shorten the first activity (i.e. leave home earlier) in order to fit the extra activities at the end of the day. It should consider the travel-times of the trips between the activities when scheduling them as well, so as not to waste more time than necessary driving around. This might mean temporally grouping activities that are geographically near one another to avoid driving across town more times than necessary. par The module must solve a problem similar to, but not the same as, departure time choice. One difference is that departure time choice makes decisions for each trip independently from one another citepMETROPOLIS, rather than allowing trade-offs between them. Also, while the activity durations chosen by the activities generation module directly effect the departure times of the agents' trips, those departure times are not fixed. If, for example, an agent arrives late to one activity, the agent will stay at the activity for the chosen duration, rather than leaving early to stick to the departure time of the next trip. In essence, priority is given to the timing of activities over timing of trips, since the activities motivate the trips, and not the other way around. par yy in a future version of this paper, this needs to be explained better. we should explain what is the output of the time choice module, and how the usim deals with it. par We were unable to find a single reference where we could look up a meaningful set of utility functions to implement. As a result our group has implemented two prototypes of activities generators with their inclusive utility functions. The more ``diligent'' module of the two, by D. Charypar, was not completed in time to use for this study, but it will be presented at IATBR citepga4acts. Instead, this work uses the simpler module by A. Schneider, which is described here and elsewhere in this paper citepSchneider:act-times. par note Utility par In order for the activities generation module to calculate the optimal day plan for an agent, it must have some way to evaluate the plan. The utility function provides a way to do this by describing the utility, or usefulness, the plan has to the agent (if the plan is not useful, why would the agent execute it?). The utility function translates the layout of the plan into a numerical value, which can be thought of as a score or an actual value in monetary terms. par The utility of the day plan must incorporate the utilities for each component of the plan. Those seperate utilities must be set relative to one another so that they can be compared appropriately when making trade-offs. In other words, changing a parameter of a more important activity by a certain amount should effect the total utility more than more than the same change on a less important activity. par Since location choice is currently not implemented, the different activity types are differentiated only by their timing information. In the utility function used for this paper, each activity type has a preferred duration, and preferred time windows for when agents should begin and end activities of that type. Different agents could have different preferences for a given activity type, but in the current implementation we give identical preferences to all agents. par Not all preferences of all activities in a day's plan can necessarily be met, so the activity generator's job is to find the best compromise between the specifications of each activity in order to make the whole day as useful as possible to the agent. par The utility of the day plan measures the usefulness of that plan, or how well it meets the needs of the agent. It is just the sum of the utilities of each activity, plus the utilities of each trip. These calculations are explained next. par subsectionUtility of a Single Activity par The utility function for a single activity measures how closely an activity of a certain type (e.g. home or work) matches the preferences set for that type. par An ``ideal'' instance of an activity would achieve the maximum utility, which we set to 0. As an activity instance moves away from the ideal, its utility decreases into negative values. The more negative the utility (or more positive the ``disutility''), the less useful the activity is for the agent. par This disutility can be thought of as a monetary cost incurred from not achieving all of the preferred timing goals for the activity. For example, being late for work may result in a cut in pay, or an angry boss, neither of which is good for the agent. par An activity's utility function is composed of three parts, according to: beginequation utl_act = utl^T_b(t_b) + utl^T_e(t_e) + utl^T_d(t_d), labeleq:act-util-total endequation where $utl_{act}$ is the total utility for the activity; $utl^T_b$ is the utility of the beginning time ($t_b$) for an activity of type $T$; $utl^T_e$ is the utility of the ending time ($t_e$) for an activity of type $T$; and $utl^T_d$ is the utility of the duration ($t_d$) for an activity of type $T$. par note modeling strategy par The next question is how to model the separate contributions. In this early version of our utility model, we use piecewise linear functions for mismatches at the activity starting and ending times, and a quadratic function for deviations from the optimal activity duration. Piecewise linear functions for the starting/ending times make sense because (1) they allow direct modeling of the Vickrey model citepArnott:etc:bottleneck, and because (2) piecewise linear functions with enough pieces allow the modeling of nearly any functional form. However, for the duration it was decided to use a quadratic function because the piecewise linear approach causes too many artifacts when competing with the piecewise linear contributions of the starting/ending times mismatches. In the future, we intend to use logarithmic utilities of duration instead citega4acts. par note Begin Time par The begin time utility, $utl^T_b$, is a piecewise linear function incorporating a preferred window of time to begin the activity, and penalties for starting too early or too late. The function looks like: beginequation utl^T_b(t_b) = left{ beginarrayll -a^T(t^a_b - t_b) & textrmif $t_b < t^{T,a}_b$,
-b^T(t_b - t^a_b) & textrmif $t_b > t^{T,b}_b$,
0 & textrmelse. endarray right., labeleq:util-begin-end endequation where $t^{T,a}_b$, $t^{T,b}_b$, $a^T$ and $b^T$ are the paramters that describe the function for the given activity type $T$. The values of $t^{T,a}_b$ and $t^{T,b}_b$ define the left and right boundaries, respectively, of the preferred window of time for starting the activity. If the starting time is within this window, there is no penalty, so this part of the utility is 0, the ``ideal'' value. The values of $a^T$ and $b^T$ are the penalty rates for starting early or late, respectively. The higher $a^T$ or $b^T$, the worse it is to be early or late. par note End Time par The utility of the ending time for an activity looks just like the utility for beginning the activity. par note Duration par The utility for the activity duration is calculated in a different way. We use a quadratic formula, like so: beginequation utl^T_d(t_d) = -10 left( alpha^T ( t_d / t^T_d - 1 )right)^2, labeleq:util-duration endequation where $t^T_d$ is a parameter describing the preferred duration for an activity of type $T$, and $alpha^T$ is a parameter that adjusts the steepness of activity type $T$'s parabola: higher values of $alpha^T$ mean a faster penalty increase penalty for spending too much or not enough time at the activity. par In this study we only use home and work activities. Their utility functions are illustrated in Figures reffig:home-util-fcns and reffig:work-util-fcns, respectively. par beginfigurebegincentercaptionHome activity utility functions. Higher values are better (the highest possible value is 0). pThe home (or essentially ``sleep'') activity starts at night, after work, and continues through the night until morning. This makes it appear as if the times of the begin and end functions are reversed. The preferred time to arrive (start) home is before midnight. There is no penalty for getting home early, but arriving after midnight causes the agent lose sleep, so the utility goes down. The preferred time to leave (end) home is after 7:00 AM. It's okay to leave anytime after that, but before then the agent loses sleep so the score gets lower. The preferred duration of home time is 16 hours. Since this activity overlaps the day boundary, the start and end are reversed. For this activity, the duration really means the agent prefers to stay home $24 - 16 = 8$ hours, corresponding to 8 hours of sleep. Less sleep than this becomes quadratically worse. labelfig:home-util-fcns vspace1em hrule vspace1em subfigure[Home begin time]includegraphics[width=0.3hsize]utl_h-begin-gz.epslabelfig:utl_h-beginsubfigure[Home end time]includegraphics[width=0.3hsize]utl_h-end-gz.epslabelfig:utl_h-endsubfigure[Home duration]includegraphics[width=0.3hsize]utl_h-dur-gz.epslabelfig:utl_h-durendcenter hrule endfigure par beginfigurebegincentercaptionWork activity utility functions. Higher values are better (the highest possible value is 0). Slope of 99 means that time must be adhered to; slope of 10 means it's not preferred, but possible. Slope of 0 means anything goes. The preferred time to begin work is between 7:00 AM and 9:00 AM. Arriving earlier than 7 means some sleep was lost, so it has disutility of 10 utility units per hour. Arriving to work after 9 is very bad (99 units per hour) because the boss gets angry. The preferred time to end work is between 4:00 PM and 6:00 PM; it's very bad to leave early (boss), and it's not preferred by the agent to leave late. The preferred duration of work time is 8 hours; near 8 hours is okay; the farther the duration is from 8 hours, the worse the utility becomes, quadratically. labelfig:work-util-fcns vspace1em hrule vspace1em subfigure[Work begin time]includegraphics[width=0.3hsize]utl_w-begin-gz.epslabelfig:utl_w-beginsubfigure[Work end time]includegraphics[width=0.3hsize]utl_w-end-gz.epslabelfig:utl_w-endsubfigure[Work duration]includegraphics[width=0.3hsize]utl_w-dur-gz.epslabelfig:utl_w-durendcenter hrule endfigure par subsectionUtility of the day plan par The total utility of the day plan is computed as the sum of all individual utility contributions emphplus a disutility for the time spent moving from one activity to another. This is to make sure there is a trade-off between driving duration and activity durations. For example, a worker might stay at work longer to avoid getting into rush-hour traffic on its his way home. To achieve this trade-off, time must also be translated into utility. We use linear transformation, known as the value of time. Since no effort was made to calibrate the utilities of the single activities, at this point the value of time is just an arbitrary free parameter. The next section will show some parametric studies as to the effect of changing this parameter. Again, future versions of the time choice module will contain more diligent values for all the free parameters. par sectionValidation Scenario labelsec:test-case par To test the activities planning module with the feedback/learning system, we implemented a simple scenario with plans containing only a few parameters that are changeable by the agents, so we might be able to follow the agents' decision-making. par subsectionThe Equil-Test Network par The scenario uses a simple network as shown in fig. reffig:equil-test-net. In this network, there is just one ``home'' location and one ``work'' location. There are nine different but identically long routes from home to work, and just one route from work to home. With no network congestion, the free-speed travel-time from home to work is 15 min (for all routes), and the travel-time from work back to home is 39 min. par beginfigure begincenter captionThe equil-test network. Nodes (intersections) are the numbered circles. Links (roads) are unidirectional; arrows show direction and line width indicates link capacity. All links have a free speed of 100 km/h. Most links are the same length (10 km), except the nine leading into node 12 (5 km), and the long link connecting node 14 to 15 at the bottom (35 km). For clarity the different routes from home to work are drawn with links of different lengths, but to the simulation the routes are all identical in length. Home and work locations are effectively at the end of their respective link, but are still behind the capacity barrier of the link. labelfig:equil-test-net vspace1em hrule vspace1em includegraphics[width=0.9hsize]equil-test.net-fig.eps endcenter hrule endfigure par For this scenario, we generate 2,000 agents with ``home-work-home'' day plans utilizing the above network. Initially, all agents have the same plan: leave home at 6:00 AM and drive to work via node 7, then stay at work for 8 hours and return home (via the only possible route). Note that 6:00 AM, even with travel time added, is earlier than the preferred time to start work, which is between 7:00 AM and 9:00 AM, as described Sec. refsec:util-fcns (Fig. reffig:utl_w-begin). Using the activities replanning module and the routing module, an agent can alter exactly three parts of its plan: the departure time from home, the route used to get to work, and the duration of the work activity. par The purpose of this scenario is to test the feedback system to make sure the agents will improve their plans until the system has relaxed into an approximate Nash Equilibrium. We expect the agents to adjust their activity plans to leave home later, so they do not arrive to work too early. We also expect the agents to adjust their routes to avoid congestion as much as possible, as they did with the previous version of the feedback system. Since all routes from home to work are equivalent, equal numbers of agents should use each of the nine routes. par The initial plans file is given to the simulation system described above, and run for 150 iterations. Recall that the first 100 iterations follow the usual relaxation scheme, but during the last 50 iterations the agents are not allowed to create new plans; they can only choose between the plans they have already tried. par As mentioned in Sec. refsec:util-fcns, the optimal value (or disutility rate) of travel time is not known relative to the other utility function parameters. So, the scenario is executed several times with different values of time (0, 50, 500, 1500). As a control, each version of the scenario is also run in a ``route-only'' mode, where activities replanning is disabled. This leads to 8 versions of the scenario. par subsectionRelaxation par In previous work, we looked at the sum of travel times as a measure of the relaxation of the system. At that time, when the system performed only route-replanning, the travel time of a trip was effectively the score of the strategy. Now we want to include activity scheduling in the measurement, so we look at the sum of the scores of the plans as the measure of relaxation. par Figure reffig:relaxation shows the total score of all agents in the system as a function of iteration (note: higher is better). One can see that most of the relaxation happens quickly, in the first 20-30 iterations, then improvement slows down toward iteration 100. The last 50 iterations do not change very much, except for fluctuations; this is expected since no new plans are created, so improvement can only come from plan selection. If the system is in an approximate Nash Equilibrium, changing one agent's plan should not improve that agent's score significantly. The figure seems to support this. par beginfigure begincenter captionRelaxation of runs with different values of time. Top left: Value of time = 0. Top right: Value of time = 50. Bottom left: Value of time = 500. Bottom right: Value of time = 1500. labelfig:relaxation vspace1em hrule vspace1em includegraphics[width=0.4hsize]relaxation_vot0-gpl.eps includegraphics[width=0.4hsize]relaxation_vot50-gpl.eps includegraphics[width=0.4hsize]relaxation_vot500-gpl.eps includegraphics[width=0.4hsize]relaxation_vot1500-gpl.eps endcenter hrule endfigure par One also sees that with the activities replanning disabled (``route-only''), the system always has a worse total score than with activities replaning. This makes sense, since the initial activities timing was not a very good one, and agents can not alter it. Their only choice is which route to take to work. For lower values of time the relaxation occurs in the direction of a worse total score! This means that the initial plans (which all used the same route) were better than the more distributed plans from later iterations. This happens because the penalty for arriving to work so early (and thus leaving work early) outweighs the advantage of having a faster route. Since 10% of the agents are always replanned and the router always generates the fastest route possible, the travel-times get shorter with more iterations, making the arrival to work even earlier, which makes the scores worse! Once the value of time is high enough, the agents do benefit from shorter travel times, and are able to relax toward better scores. par subsectionActivity Timing par If the scenario contained only one agent, that agent would never encounter congestion and would have completely predictable travel times. It is thus possible to analytically compute the best-scoring plan possible for a single agent in the system. The best plan, to the nearest second is: departure from home between 07:55:48 (hh:mm:ss) AM and 08:45:00 AM, and work duration of exactly 07:49:12 hours. par For 2000 agents, they cannot all follow the single best solution because they would get in each others' way while implementing it. The feedback system and agent database help the agents explore until they find a good set of solutions to try out, which take into account the usage of the network by the other agents. par All agents use the same utility functions. All have access to the same information. The activity generation module supplies plans based on complete information about network congestion obtained from the previous simulation run. This means that within the decision phase of a given iteration, every agent that requests a new activity plan will receive the emphsame exact plan from the module. This is caused by the property of the time choice module to always return the best solution it has found so far, rather than, say, employing a discrete choice model. par The result is that the agents leave home for work in several ``waves'' of home-to-work trips, and then leave work for home in a different set of ``waves.'' One departure from home wave is of course the initial 06:00 AM departure, which some agents will always try out. These all have 8 hour work durations, so including the home-to-work trip, they lead to departures from work at about 2:15 PM. par Figure reffig:waves depicts these waves, showing how many agents leave home or work during various 15-minute intervals throughout the day. Most departures from home occur around 8:00 in the morning. Since the agents have seperate routes from home to work, they are able to spread out along these routes. For the departure from work, there is only one route home, so the agents spread out so they are on the road at different times by varying the duration of their work activity. This effect is especially prominent at higher values of time; in fact at higher values of time the travel time becomes so significant that some agents choose to leave home emphbefore 6:00 AM. par beginfigure begincenter captionDeparture waves at various iterations for the scenarios with activities planning enabled. Morning times are departure times from home to work. Afternoon times are departure times from work to home. There are more departure waves leaving from work than from home. As the value of time increases, the travel-times becomes more important than the timing, so the departure times (esp. for leaving work) spread out more to lower the time spent driving. labelfig:waves vspace1em hrule vspace1em includegraphics[width=0.4hsize]histo_vot0-gpl.eps includegraphics[width=0.4hsize]histo_vot50-gpl.eps includegraphics[width=0.4hsize]histo_vot500-gpl.eps includegraphics[width=0.4hsize]histo_vot1500-gpl.eps endcenter hrule endfigure par The basic proportions between the times seems to be pretty consistent between the different iterations. par subsectionRoute Equilibration par We expect that within a given ``wave'' of trips from home to work, the agents will distribute themselves onto the nine identical routes available to them. However, since the agents do not coordinate with one another about who will take which route, they are not likely to be perfectly balanced between the routes. par Figure reffig:route_histogram shows how the different routes contribute to the departure waves seen in Fig. reffig:waves. The routes appear to be used roughly equally, though there are some over- and under-used routes. This seems to be caused by random fluctuations. par beginfigure begincenter captionRoute equilibration for activities-replanned scenarios. A break-down of the routes used in the home-to-work departures from Fig. reffig:waves. The ``boxes'' are emphstacked on top of one another. That is, the visible portion of each ``box'' indicates the relative number of agents using that route who departed within that 15-minute time-bin; height of the individual boxes above the x-axis axes is not relevant. labelfig:route_histogram vspace1em hrule vspace1em includegraphics[width=0.4hsize]histo.route_vot0-gpl.eps includegraphics[width=0.4hsize]histo.route_vot50-gpl.eps includegraphics[width=0.4hsize]histo.route_vot500-gpl.eps includegraphics[width=0.4hsize]histo.route_vot1500-gpl.eps endcenter hrule endfigure par sectionDiscussion and Future Work labelsec:discussion par One wonders why the departure ``waves'' are so prominent and distinct, rather than spread out about the ideal plan. Further investigation reveals that this is caused by a low ``free-speed'' setting of the time choice module, causing it to estimate 50 km/h ``free-speed'' for trips to unknown locations or starting at unsampled times. In contrast, the free speed for all links in the test network is 100 km/h, so sampling certain trips at certain times leads to speeds faster than the ``free'' speed, thus causing the module to prefer to use time-bins that have already been used, and to not try new time bins. This will be improved in future versions. par yy use different rnd seeds each time time chooser is called par In addition, the time choice module, being a Genetic Algorithm (GA), always returns the best solution that it knows, rather than selecting according to an exponentially weighted probability as would be done in discrete choice theory. On the other hand, just returning the optimum rather than making a random choice is computationally considerably more tractable. And a Genetic Algorithm, stopped after a short time, will in general not even return the optimum, but some intermediate result. It is an open question of future research how the distribution of results returned from such a GA compares to the distribution of results generated by a (computationally much more expensive) random utility model. par yy dave Charypar: distributions of intermed solutions in GA?? par note eventual goal of Switzerland/big-Zurich. par The goal of our work is to be able to run a scenario of a full 24-hour simulation of all of Switzerland, including transit traffic, freight traffic, and all modes of transportation. This will involve about 7.5 million travelers, and more than 20 million trips (including short pedestrian trips, etc.). par A more short-term goal is a full 24-hour simulation of all of car traffic in Switzerland. For this, we will have about 4.5 million car trips. However, we have not yet met this goal; while we have been able to run route-replanning on the morning peak time-period for all of Switzerland, as of this writing we have not succeeded in running the activities feedback on this large scenario. We hope to be able to have results from this scenario by the time of the IATBR conference. par sectionSummary labelsec:summary par The limitations of the 4-step process are well known. One alternative is a completely agent-based simulation approach to travel forecasting. In an agent-based approach, each traveler is represented individually throughout the whole simulation system. The necessary modules for such an approach are: synthetic population generation module, activity generation module(s), mode choice/route module(s), traffic simulation module, and finally a feedback/learning mechanism. To our knowledge, no agent-based system is available that successfully and consistently implements all these modules; TRANSIMS is maybe the closest existing implementation. par In this paper, we investigate the integration of activity time choice, route planner, traffic simulation, and feedback. The last three together form an agent-based version of Dynamic Traffic Assignment (DTA), which has been investigated in earlier papers. Activity time choice now for the first time goes beyond DTA in our work and integrates the first aspect of activity feedback. Activity time choice is related to departure time choice, but it is more complicated since it attempts to find times for a complete 24-hour day plan, instead of just for a single activity. par The problem is solved by attaching a separate time choice module to the DTA process. In each iteration, not only can agents select new and supposedly better routes, but they also obtain new activity times. These times are generated by a Genetic Algorithm (GA) that uses the following information as input: For each agent, the activity pattern and their locations; a utility function that is (at this point) the same for every agent; and a global view of the travel times between network locations as a function of the time-of-day. par The paper shows verification runs with a testing scenario. The system behaves essentially as expected, but an artifact was discovered with respect to the model's assumption about travel times for areas in space-time for which no feedback information was available. Essentially, the model very much over-estimated travel times where it had no other information, leading to the effect that travelers clustered in space-time regions instead of spreading out. This will be improved in future versions. In addition, different values of time for travel were tried out. While a zero value of time for travel leads to artifacts in the sense that agents attempt to prolong travel time in order not to be early at the work location, a too high value of time for travel puts such a high weight on travel times that schedule delay plays no longer a role and all agents spread out so much that everybody is driving at free speed. par As said before, the results presented here are preliminary. The ultimate goal is a real-world case study. par section*Acknowledgments par Special thanks go to Adrian Schneider for the activities generation module, which was his semester project during the winter 2003/03 semester. par bibliographystyleiatbr bibliographyref,kai,projects,xref par enddocument