Introduction

In the area of activity-based travel demand modeling, designing the activity planning and scheduling components in a way that they can replicate individual’s actual activity scheduling behavior is a critical step to represent daily activity-travel patterns. In this line of research, various operational models have been developed, including SCHEDULER (Gärling et al. 1994), TASHA (Miller and Roorda 2003), ALBATROSS (Arentze and Timmermans 2004), and ADAPTS (Auld and Mohammadian 2012). Although most of these models attempt to undertake activity-scheduling process, they lack the dynamic notion underlay in activity scheduling behavior. Being developed from travel survey data, these rule-based models typically follow presumed activity orders and attributes. However, Doherty and Mohammadian (2011) have shown that there is no fixed priority for planning order of activities. Moreover, Roorda and Miller (2005) showed that in many cases people reschedule or skip mandatory activities, which intuitively have the highest priority, to carry out other activity types. Therefore, the importance of investigating scheduling process has recently been recognized by many scholars.

A core component of activity planning and scheduling models is the conflict resolution procedure; because numerous activity conflicts may occur in individuals’ daily schedule. Activity conflict is defined as a situation when two or more activities of an individual are planned so that they have temporal overlap. In the literature, rule-based or choice-based models have been developed to handle such conflicts. TASHA (Miller and Roorda 2003) employs priority-based rules to resolve scheduling conflict. Priority reflects the importance of the activity in the individual activity schedule. The model also considers the degree to which an activity has been planned earlier than other activity involved in the conflict. For more information on scheduling process of TASHA, readers may refer to Roorda and Miller (2005) and Roorda et al. (2005). Likewise, ALBATROSS (Arentze and Timmermans 2004) uses a set of priori assumptions derived from diary data in the scheduling process. Nonetheless, diary data could not realistically represent the conflict resolution process.

As the necessity for modeling activity scheduling became more evident, more reliable scheduling surveys were conducted including CHASE (Doherty et al. 2004) and REACT (Lee and McNally 2001), as well as the more recent multi-instrumented data collected by Clark and Doherty (2009). Following to the availability of the data, more recent models attempted to capture scheduling behavior from scheduling process data. Joh et al. (2005) investigated the factors affecting individuals scheduling and modifying behavior using data collected from CHASE survey; however, scheduling conflicts were not considered in their study. Ruiz and Timmermans (2006) developed a conflict resolution model just for the case in which a single new activity is going to be inserted between two consecutive pre-planned activities. They resolved the conflict by modifying the timing and/or duration of the previously planned activities without changing their sequence.

Later on, other frameworks such as ADAPTS also tried to promote activity-scheduling models by using actual activity scheduling data (Auld et al. 2009a, b). Based on the observed conflict instances, the scheduler of ADAPTS determines four strategies to resolve the conflicts: modify the original activity, modify the new activity, delete the original activity, and modify both activities. The strategy depends on decision maker’s attributes and characteristics of the conflicting activities and is determined by a series of rules derived from a Decision Tree (DT) model. Although several previous studies have utilized DT in their scheduling process (Arentze et al. 2001; Arentze and Timmermans 2003), none have utilized scheduling process data. Consequently, based on strategy types and conflict situation (i.e. configuration of conflict such as start edge, end edge, insertion conflict, and percentage of overlap), the ADAPTS scheduler considers 52 conflict scenarios and for each case, a set of rules is implemented to resolve the conflict.

In this paper, we continue the study of conflict resolution methods by enhancing ADAPTS activity-scheduling model. That is instead of considering a large number of rules for each conflict type, a general non-linear optimization model is proposed to resolve the conflicts and fit the activities into the schedule. Although some previous studies have formulated various aspects of planning and scheduling process as an optimization problem (e.g. Recker 1995; Chow and Recker 2012), the proposed optimization application is novel in the context of conflict resolution and to the best of the author’s knowledge, has not yet been considered in the literature.

In the proposed scheduling model, fitting the new activity in the schedule is conducted in a way that the defined objective function is minimized while satisfying a set of constraints, which are determined by the resolution strategy types. The main advantages of the proposed model are flexibility, ease of implementation and maintenance, less error prone, and potentials for adopting more behavioral objective functions. These advantages become evident when developing large-scale microsimulation models. Usually as models become complicated, they become more computationally intensive that prevents their adoption by practitioners. Moreover, the model takes into account the travel time between locations of involved activities in conflict while fitting them in the schedule. In other words, while the scheduler tries to fit activities in the schedule, it reserves required time to travel to the activity location from the last scheduled activity. This task can be done by means of the newly implemented dynamic traffic assignment (DTA) model in ADAPTS, which is able to calculate prevailing travel times.

This paper is structured as follows. The next section briefly overviews the ADAPTS microsimulation framework focusing on the conflict resolution component. The third section describes the modeling approaches used in the study and explains minimization models corresponding to different conflict situations. The results of the proposed model and comparison of its performance with other ABM schedulers are presented in fourth section. The final section discusses conclusions drawn from the model and potential avenues for future studies.

ADAPTS overview

Agent-based Dynamic Activity Planning and Travel Scheduling (ADAPTS) is an activity-based framework developed to simulate activity travel decisions through a dynamic process as observed in real data. This framework includes an integrated mesoscopic DTA that allows individuals to access network dynamics during the simulation and update their plans and schedules accordingly. The activity planning and scheduling process of ADAPTS is composed of three phases including: (1) activity generation, (2) activity planning, and (3) activity scheduling.

The first phase is activity generation that determines whether to generate an activity of a specific type in the current simulation time step or not. This phase utilizes a hazard-based model for each activity type to generate the list of activities that individuals intend to carry out. The list of activities is a dynamic list and activities may be added to the list or removed from it during the simulation. It also sets the planning horizon of activities to specify how soon the activity needs to be planned once it is generated. Moreover, ADAPTS extends the concept of planning horizon to the attributes of the activity. That is in this model, the time and order that various attributes of an activity are set could be different, and once an attribute is set, it could affect the value of undetermined attributes. Therefore, once an activity is generated, the planning horizons of the activity itself and its attributes are determined. In the second phase, activity planning, the actual values of the attributes such as start time, duration, mode of travel, location, and other participants are set as the attributes planning times arrive. Eventually, activity scheduling is the last phase of the process. Activity scheduling, which is also the focus of this paper, attempts to fit the newly planned activities in the schedule. It is run once all attributes of the activity are determined. If there is any temporal conflict between the new activity and scheduled activities, a conflict resolution model is run to resolve the conflict. The model tries to fit the new activity in the schedule by shortening, shifting, and/or splitting the conflicted activities. If none of these methods could resolve the conflict, it is not feasible to perform the new activity and it will be deleted from the individual’s activity list. For more detailed information on ADAPTS simulation process, readers may refer to Auld et al. (2009a, b), Auld and Mohammadian (2012), Fasihozaman et al. (2016) and Shabanpour et al. (2016).

ADAPTS uses a rule-based decision tree model to determine conflict resolution strategies. Table 1 presents this model, originally developed by Auld et al. (2008). Based on individual’s characteristics as well as the conflicting activities attributes, the model decides whether to modify any of the conflicting activities’ start times and/or durations. Conflict resolution strategies consist of four categories: (1) modify original activity, (2) modify conflicting (new) activity, (3) modify both activities, and (4) delete the original one. These general categories are the main resolution types observed from the CHASE database.

Table 1 ADAPTS decision rules for conflict resolution strategy (Auld et al. 2008)
Full size table

Once the conflict resolution strategies are determined, they need to be implemented in the individuals’ schedules. Current conflict resolution module implemented in ADAPTS is an updated version of rule-based scheduler model of TASHA framework. Based on strategy type and conflict situation (i.e. configuration of conflict such as start edge, end edge, insertion conflict, and percentage of overlap), 52 scenarios are considered and for each case, a set of rules to resolve the conflict is implemented. The development of the scheduling model in ADAPTS simulation framework proved to be very difficult as the number of scenarios grows. The code becomes very large, inflexible, and error prone. This becomes more important in development of large-scale models where the number of components and level of details are substantial. Therefore, in this paper, instead of using these rules, a non-linear programming model is proposed to fit new activities in the schedule with minimizing defined objective functions. The resolution strategy types are obtained from ADAPTS decision tree approach.

Modelling approach

This section presents the modeling approach used in this study and elaborates the optimization models corresponding to different conflict situations. Here, in the process of activity conflict resolution, the activity that intends to fit in the schedule while overlaps already scheduled activities, is referred to as new activity. Those already scheduled activities involved in the conflict situation are called the original activities. Subsequently, the activity which is scheduled to be executed before the original and new activities and has no temporal overlap with them is called the previous activity. Next activity is similarly defined as the activity that occurs after the original and new activities. End time of previous activity and start time of next activity are boundaries of conflict area. That is start time and duration of original and new activities can be modified such that they do not exceed these boundaries. This terminology is frequently used in the following discussions.

Common types of activity conflicts embrace two general cases. Case I includes those conditions when the new activity overlaps only one original activity. Case II consists of conflict cases in which the new activity overlaps two original activities. In this case, the original activity which is about to happen first is noted as original 1, versus original 2 that happens later. These 2 cases are illustrated in Fig. 1. Although this terminology can be extended to encompass the situations in which more than two original activities are involved in the conflict, those cases are not considered in this paper due to their rarity in observed databases.

Fig. 1
figure 1

General conflict cases: conflicting with 1 (case I) or 2 (case II) scheduled activities

Full size image

Each case consists of multiple conflict instances according to the start time and end time of the original and new activities. For example, case 1 consists of conflict instances as shown in Fig. 2. In this case, the conflicts can be either insertion conflicts, for which a new activity is inserted within a previously scheduled (original) activity; overlap conflicts, for which a conflicting activity completely overlapped an original activity; and edge conflicts, for which either the start or end of an original activity is overlapped.

Fig. 2
figure 2

Conflict instances of case I

Full size image

It is worth mentioning that the activity conflict definition is extended in a way that it captures the travel times between activity locations. In other words, even if the new activity does not overlap the original activity, but travel time between their locations cannot be fit in the schedule, this methodology behaves this situation as a conflict, as well. This required travel time between locations of involved activities in conflict situation is depicted in Fig. 3.

Fig. 3
figure 3

Example of resolving a case I conflict and its parameters

Full size image

In this paper, the objective function is defined to minimize the shifts and duration changes of conflicting activities. This objective function requires a non-linear solver. However, since solving a non-linear problem is much more complicated and time consuming than a linear problem, the problem is converted to a series of linear sub-problems. This keeps the model runtime performance high while removes the need to develop a complex non-linear solver or adopting an external solver, which makes the runtime much longer.

This method of resolving the conflicts while minimizing shifts and duration changes relies on the intuitive sense that people try to fit the conflicting activities in their schedule with minimum changes to the preplanned schedule. In some instances, people are more flexible to change the activity start time rather than the activity duration, while in some other cases they keep the start time fixed but shorten the activity duration. These variations are also considered in the methodology with corresponding parameters. Considering the concept of minimizing the changes to the activity start time and duration, the objective function of resolving the conflicts for case I conflicts, where there is only one original activity would be written as:

$${\text{Minimize}}\,{\text{f}} = \left[ {\upalpha *\left( {\left| {{\text{S}}_{{ {\text{NEW}}}}^{\text{A}} - {\text{S}}_{\text{NEW}}^{\text{B}} } \right| + \left| {{\text{S}}_{{ {\text{ORG}}}}^{\text{A}} - {\text{S}}_{\text{ORG}}^{\text{B}} } \right|} \right)} \right] + \left[ {\upbeta *\left( {\left| {\left( {{\text{E}}_{\text{NEW}}^{\text{A}} - {\text{S}}_{\text{NEW}}^{\text{A}} } \right) - \left( {{\text{E}}_{\text{NEW}}^{\text{B}} - {\text{S}}_{\text{NEW}}^{\text{B}} } \right)} \right| + \left| {\left( {{\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{\text{ORG}}^{\text{A}} } \right) - \left( {{\text{E}}_{\text{ORG}}^{\text{B}} - {\text{S}}_{\text{ORG}}^{\text{B}} } \right)} \right|} \right)} \right]$$
(1)

All variables used in this approach are defined in Table 2. The first part of Eq. (1) denotes the value of absolute shifts in the start times while the second part represents the absolute value of changes in the duration of the original and new activities before and after conflict resolution.

Table 2 Model variables description
Full size table

Figure 3 graphically represents the parameters of the objective function. Start time and end time of original and new activities before conflict resolution are the known parameters in the objective function. They are determined in the planning stage of activity-based model. The goal is to achieve the optimal values for activity start and end times after resolving the conflict so that the changes to the preliminary schedule would be minimized. Therefore, \(S_{i}^{A}\) and \(E_{i}^{A}\) are unknown variables to be determined by the optimization approach. The alpha and beta parameters adjust the importance of start time shifts and duration changes, respectively. For simplification purposes in this study, alpha and beta are assumed one to show equal weight for start time shift and duration changes.

As it was mentioned before, the objective function (1) includes absolute value functions, which make the problem non-linear. In order to turn the problem into a regular linear one, the absolute value functions should be removed by redefining the problem into multiple sub-problems with the use of appropriate constraints. Then, the optimum values of these sub-problems are compared to achieve the best resolving decision. Additionally, an assumption is made that in case of conflict, activity durations are not increased in conflict resolution process. This assumption is in line with the intuitive sense that people attempt to squeeze the conflicting activities into their free time slots in case of schedule conflicts. All possible sub-problems for case I (conflicting with one scheduled activity) and case II (conflicting with two scheduled activities) are respectively presented in Tables 3 and 4, as well as their objective functions and graphical representation. For each conflict case, four sub-problems are defined according to the corresponding resolution strategies and configuration of conflicting activities. The arrows in the figures indicate the direction of shifting the activities, which is based on the specific assumptions in each conflict case.

Table 3 Linear sub-problems for case I conflict configurations
Full size table
Table 4 Linear sub-problems for case II conflict configurations
Full size table

The strategy types determined by decision tree model impose a set of constraints to the optimization problem. For example if the decision tree model based on individual’s characteristics and the conflicting activities attributes returns “modify new activity” as the strategy type, the start time and duration of original activity must remain unchanged. In any of these problems, there are additional constraints other than the ones imposed by the type of resolution strategy including consideration of the minimum activities’ durations, maximum shift of activity start times, travel time between activities, end time of the previous activity, and start time of the next activity. In order to clarify the methodology, the linear problem for the conflict type I-1 is presented here along with the constraints, assuming the strategy type as “modify both activities”. All variables used in this model have been defined in Table 2.

Conflict Type I-1

Unknown Variables: \({\text{S}}_{{ {\text{NEW }}}}^{\text{A}} , {\text{S}}_{\text{ORG}}^{\text{A}} , {\text{E}}_{\text{NEW}}^{\text{A}} , {\text{E}}_{\text{ORG}}^{\text{A}}\)

Objective function:

$${\text{Min f}} = \left[ {\upalpha *\left( {{\text{S}}_{{ {\text{NEW}}}}^{\text{A}} - {\text{S}}_{\text{NEW}}^{\text{B}} + {\text{S}}_{{ {\text{ORG}}}}^{\text{B}} - {\text{S}}_{\text{ORG}}^{\text{A}} } \right)} \right] + \left[ {\upbeta *\left( {\left( {{\text{E}}_{\text{NEW}}^{\text{B}} - {\text{S}}_{\text{NEW}}^{\text{B}} } \right) - \left( {{\text{E}}_{\text{NEW}}^{\text{A}} - {\text{S}}_{\text{NEW}}^{\text{A}} } \right) + \left( {{\text{E}}_{\text{ORG}}^{\text{B}} - {\text{S}}_{\text{ORG}}^{\text{B}} } \right) - \left( {{\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{\text{ORG}}^{\text{A}} } \right)} \right)} \right]$$
(2)

Subject to:

  1. 1.

    \({\text{S}}_{\text{ORG}}^{\text{A}} \le {\text{S}}_{\text{ORG}}^{\text{B}}\)

  2. 2.

    \({\text{S}}_{{ {\text{NEW }}}}^{\text{A}} \ge {\text{S}}_{\text{NEW}}^{\text{B}}\)

  3. 3.

    \({\text{S}}_{{ {\text{NEW}}}}^{\text{A}} = {\text{E}}_{\text{ORG}}^{\text{A}} + {\text{TT}}_{\text{OrgToNew}}\)

  4. 4.

    \({\text{E}}_{\text{NEW}}^{\text{A}} \le {\text{S}}_{\text{NEXT}} - {\text{TT}}_{\text{NewToNext}}\)

  5. 5.

    \({\text{S}}_{\text{ORG}}^{\text{A}} \ge {\text{E}}_{\text{PREV}} + {\text{TT}}_{\text{PrevToOrg}}\)

  6. 6.

    \({\text{E}}_{\text{NEW}}^{\text{A}} - {\text{S}}_{\text{NEW}}^{\text{A}} \ge {\text{L}}_{\text{MinNew}}\)

  7. 7.

    \({\text{L}}_{\text{MaxNew}} = {\text{E}}_{\text{NEW}}^{\text{B}} - {\text{S}}_{\text{NEW}}^{\text{B}}\)

  8. 8.

    \({\text{E}}_{\text{NEW}}^{\text{A}} - {\text{S}}_{\text{NEW}}^{\text{A}} \le {\text{L}}_{\text{MaxNew}}\)

  9. 9.

    \({\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{\text{ORG}}^{\text{A}} \ge {\text{L}}_{\text{MinOrg}}\)

  10. 10.

    \({\text{L}}_{\text{MaxOrg}} = {\text{E}}_{\text{ORG}}^{\text{B}} - {\text{S}}_{\text{ORG}}^{\text{B}}\)

  11. 11.

    \({\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{\text{ORG}}^{\text{A}}\,\le {\text{L}}_{\text{MaxOrg}}\)

  12. 12.

    \({\text{S}}_{\text{ORG}}^{\text{B}} - {\text{S}}_{\text{ORG}}^{\text{A}}\,\le {\text{MaxShift}}_{\text{Org}}\)

  13. 13.

    \({\text{S}}_{\text{NEW}}^{\text{A}} - {\text{S}}_{\text{NEW}}^{\text{B}}\,\le {\text{MaxShift}}_{\text{New}}\)

  14. 14.

    \({\text{S}}_{{ {\text{NEW }}}}^{\text{A}} \ge 0\)

  15. 15.

    \({\text{S}}_{\text{ORG }}^{\text{A}} \ge 0\)

  16. 16.

    \({\text{E}}_{\text{NEW}}^{\text{A}} \ge 0\)

  17. 17.

    \({\text{E}}_{\text{ORG}}^{\text{A}} \ge 0\)

However, this linear optimization problem is not consistent with the simplex standard form due to the type of constraints. In the standard simplex, all variables and right-hand sides (RHS) of constraints must be non-negative and the constraints must be in equality form. Therefore, required modifications are made in the problem. In addition, slack variables of \(S_{1} , S_{3} ,S_{6} ,S_{8} ,S_{10}\) and surplus variables of \(S_{2} , S_{4} ,S_{5} ,S_{7} ,S_{9}\) are added to change the inequality signs into equality. All these auxiliary variables must be non-negative, as well. The objective function is also converted to a maximization problem. Executing all these steps, the optimization problem transforms to the standard format as follows:

Conflict Type I-1

Unknown Variables: \({\text{S}}_{\text{ORG}}^{\text{A}} , {\text{E}}_{\text{NEW}}^{\text{A}} , {\text{E}}_{\text{ORG}}^{\text{A}}\)

Objective function:

$${\text{Max Z}} = \left[ { - \upalpha *\left( {{\text{E}}_{{ {\text{Org}}}}^{\text{A}} + {\text{TT}}_{\text{OrgTONew}} - {\text{S}}_{\text{NEW}}^{\text{B}} + {\text{S}}_{{ {\text{ORG}}}}^{\text{B}} - {\text{S}}_{\text{ORG}}^{\text{A}} } \right)} \right] + \left[ { - \upbeta *\left( {\left( {{\text{E}}_{\text{NEW}}^{\text{B}} - {\text{S}}_{\text{NEW}}^{\text{B}} } \right) - \left( {{\text{E}}_{\text{NEW}}^{\text{A}} - {\text{E}}_{{ {\text{Org}}}}^{\text{A}} - {\text{TT}}_{\text{OrgTONew}} } \right) + \left( {{\text{E}}_{\text{ORG}}^{\text{B}} - {\text{S}}_{\text{ORG}}^{\text{B}} } \right) - \left( {{\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{\text{ORG}}^{\text{A}} } \right)} \right)} \right]$$
(3)

Subject to:

  1. 1.

    \({\text{S}}_{\text{ORG}}^{\text{A}} + {\text{S}}_{1} = {\text{S}}_{\text{ORG}}^{\text{B}}\)

  2. 2.

    \({\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{2} = {\text{S}}_{\text{NEW}}^{\text{B}} - {\text{TT}}_{\text{OrgToNew}}\)

  3. 3.

    \({\text{E}}_{\text{NEW}}^{\text{A}} + {\text{S}}_{3} = {\text{S}}_{\text{NEXT}} - {\text{TT}}_{\text{NewToNext}}\)

  4. 4.

    \({\text{S}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{4} = {\text{E}}_{\text{PREV}} + {\text{TT}}_{\text{PrevToOrg}}\)

  5. 5.

    \({\text{E}}_{\text{NEW}}^{\text{A}} - {\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{5} = {\text{L}}_{\text{MinNew}} + {\text{TT}}_{\text{OrgToNew}}\)

  6. 6.

    \({\text{E}}_{\text{NEW}}^{\text{A}} - {\text{E}}_{\text{ORG}}^{\text{A}} + {\text{S}}_{6} = {\text{E}}_{\text{New}}^{\text{B}} - {\text{S}}_{\text{New}}^{\text{B}} + {\text{TT}}_{\text{OrgToNew}}\)

  7. 7.

    \({\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{7} = {\text{L}}_{\text{MinOrg}}\)

  8. 8.

    \({\text{E}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{\text{ORG}}^{\text{A}} + {\text{S}}_{8} = {\text{E}}_{\text{ORG}}^{\text{B}} - {\text{S}}_{\text{ORG}}^{\text{B}}\)

  9. 9.

    \({\text{S}}_{\text{ORG}}^{\text{A}} - {\text{S}}_{9} = {\text{S}}_{\text{ORG}}^{\text{B}} - {\text{MaxShift}}_{\text{Org}}\)

  10. 10.

    \({\text{E}}_{\text{ORG}}^{\text{A}} + {\text{S}}_{10} = {\text{MaxShift}}_{\text{New}} + {\text{S}}_{\text{NEW}}^{\text{B}} - {\text{TT}}_{\text{OrgToNew}}\)

  11. 11.

    \({\text{S}}_{\text{ORG }}^{\text{A}} \ge 0\)

  12. 12.

    \({\text{E}}_{\text{NEW}}^{\text{A}} \ge 0\)

  13. 13.

    \({\text{E}}_{\text{ORG}}^{\text{A}} \ge 0\)

  14. 14.

    \({\text{S}}_{\text{i}} \ge 0\,,\quad {\text{i}} = 1, \ldots , 10\)

This problem is now in line with the simplex standard format. Therefore, it can be used in the conflict resolution component of activity scheduling in microsimulation ABM framework. All 7 other conflict types are similarly transformed to simplex standard format. For the sake of brevity, the expansion of other cases is eliminated from the paper. Solving this linear optimization leads to finding values of start and end times of activities after resolving conflicts. If the algorithm cannot find a solution, it is not feasible to perform the new activity and it will be deleted from the individual’s schedule.

In summary, when a conflict arises in an individual’s schedule, depending on conflict configuration as well as individual’s characteristics and conflicting activities attributes, a decision tree model determines the resolution strategy, which imposes some constraints to the optimization problem. Then the conflict case is determined by the number of original activities involved in the conflict. For each case, four linear optimization problems will be solved. Comparing their objective values, the best resolving decision with the minimum changes in start times and durations of activities for the conflict situation will be determined.

Model results

This section discusses the results of implementing the proposed approach, and compares them with TASHA and ADAPTS former conflict resolvers. Moreover, some implications of implementing the proposed method in ADAPTS framework are presented.

Implementation of the proposed model in ADAPTS

The proposed model has been implemented in ADAPTS framework and applied on a synthetic population of the Chicago Six-County Region. The population synthesizer of ADAPTS utilizes the iterative proportional fitting (IPF) method with multiple household and person-level controls (Auld and Mohammadian 2010) and generates about 7,972,000 persons for that area. In order for the activity generator model to work best, ADAPTS preplans activities for 21 days and then generates the final set of activities for at least one complete day. During the 24-h simulation period, almost 63,844,000 conflict situations occurred in individuals’ daily schedules and Table 5 presents an explanatory analysis of observed conflict instances as well as total number of each strategy type for the statistically significant variables.

Table 5 Analysis of conflict resolution strategies implemented in ADAPTS
Full size table

As shown in this table, the cases in which preplanned or routine activities are involved in the conflict as the original activity are less frequent than same-day and impulsive activities. It is intuitive since when a person is planning for his far future (e.g. next weeks), it is much more probable that he can place the activity in his schedule without any arisen conflict, since the schedule at that time is not still fully occupied. In contrast, in case of the impulsive activities, the person promptly decides to create, plan, and execute an activity. Therefore, it is more likely that the new activity has conflict with an already planned one.

Comparison of scheduling results with TASHA and ADAPTS former scheduler

In order to compare ADAPTS’ new scheduler with the former one and with TASHA, their ability in representing actual scheduling is evaluated, i.e. how closely each system can replicate the observed activity patterns when the initially planned activities from the data set are scheduled.

To determine the accuracy of each conflict resolution system in replicating the result of the scheduling process, a data set that contains both the initial plans and the realized results of the scheduling process was needed. Additionally, for the sake of comparing these three approaches it is compulsory to implement them on the same data source. Therefore, the CHASE data set (Doherty et al. 2004), which is used in TASHA and ADAPTS former scheduling modules, as one of the few sources of scheduling process data, is selected for the first part of our analysis. CHASE is a 7-day computerized activity diary survey conducted in Toronto, Canada, in 2002–2003 with 271 households, including 426 adults. People were interviewed and participants’ activities and travel patterns were recorded. CHASE traces detailed planning process and scheduling behavior of respondents by recording users’ actions of adding, modifying, or deletion of activities on their schedule.

Therefore, the two sets of activity data that Auld et al. (2009a, b) derived from CHASE survey to evaluate performance of their scheduler are utilized: the originally planned schedule and the executed schedule. The planned activities are used as input to conflict resolvers, instead of output of the activity generation and planning stages of ABM, and the results are compared with the executed patterns. The planned activity data are all activities that were added to the schedule without any modifications and deletions, including the conflicting activities. To generate the executed schedules, they used a different filter to get the activities that were in the actual travel pattern. Here, the same activity data sets are generated to be able to compare the results of conflict resolvers.

To compare the results of each scheduling system with the actual executed pattern, the time sequence-alignment routine proposed by Auld et al. (2009a, b) is employed. This method finds the cost of modifying the activities for each individual by aligning the set of planned activities to the executed activities for each activity type. The total cost is defined as the sum of the weighted insertion, deletion, and movement costs of activities as given in Eq. 4.

$${\text{C}} = \mathop \sum \limits_{{{\text{k}}\,=\,1}}^{\text{K}} {\text{w}}_{\text{D}} {\text{C}}_{\text{D}}^{\text{k}} + {\text{w}}_{\text{I}} {\text{C}}_{\text{I}}^{\text{k}} + {\text{w}}_{\text{M}} {\text{C}}_{\text{M}}^{\text{k}}$$
(4)

In this equation,\(\varvec{ }w_{D}\),\(w_{I }\), and \(w_{M}\) are weights for deletion, insertion and movement operations and \(C_{D}^{k}\), \(C_{I}^{k}\), and \(C_{M}^{k}\) are cost of those operations for each activity type \(k\), respectively. The cost of insertion and deletion are the sum of the durations of all deleted and inserted activities and the cost of movement is the cost to align the set of shifted activities calculated as the sum of differences between start times and end times of the activity in planned list and its counterpart in actual executed list. More details of this comparison approach can be found in the study by Auld et al. (2009a, b).

The alignment routine was applied to results of the proposed scheduling methodology presented in this paper. This analysis was done with the same weighting factors for the alignment operations used by Auld et al. (2009a, b) and their results as well as the proposed model outcomes are summarized in Table 6. In this analysis, the movement cost weight was set to 0.5 and the deletion and insertion weights were tested at values of 1, 2, and 3. The results indicate that for all cases the new scheduler has significantly better performance than the TASHA rules and slightly outperforms the ADAPTS scheduler. For the case in which the insertion and deletion weight parameters are 1 and movement weight is 0.5, the proposed model expresses 19.3 and 2.8 % improvement in fit over TASHA and ADAPTS former rule-based schedulers. This holds for other values of the weighting factor tested, which represent a likely realistic range. The proposed model outperforms TASHA and ADAPTS’ former rule-based schedulers for 13.8 and 2.5 % in second scenario and for 8.1 and 1.2 % in third scenario, respectively. Therefore, for reasonable ranges of the weighting factors, the new scheduling results show marked improvement to the fit of the modeled schedules.

Table 6 Scheduling alignment results of TASHA, ADAPTS’ former scheduler, and ADAPTS’ new scheduler
Full size table

Conclusions and direction for future research

This study investigates the process of activity scheduling and fitting the newly planned activities in individuals’ daily activity schedules, when there is temporal conflict between them. The former activity scheduling model of ADAPTS activity-based model consists two components: (1) a decision tree that determines the conflict resolution strategy types to identify which activities should be modified or deleted, (2) a set of rules to fit activities in the schedule according to the information and constraints determined by the first component. Since the complicated and inflexible code of implementation of the resolution strategies proved to be very inefficient and error prone, this study proposes a non-linear optimization model trying to minimize the amount of changes in start times and durations of involved activities in the conflict situation. This new model is very flexible and much less complicated in terms of implementation and coding.

Since non-linear problems (NP) are computationally intensive and in most cases, there is no general solution for them, the problem is converted into a number of linear problems (LP) which together accomplish the same task. The proposed NP and LP models as well as their objective functions are discussed in detail. The new scheduler demonstrates 19.3 and 2.8 % improvement in fit over the TASHA and ADAPTS original schedulers, respectively, when the magnitude of insertion and deletion weights were twice of the movement weight. The model also is applied to a synthetic population for the Chicago region and a descriptive analysis of the results is presented.

However, future work still remains in validation of this model. As the conflict resolution model is developed by means of the same data set that is used to test the model performance, it would be helpful to validate the results found here with additional scheduling process data sets. Along with validating the model results, the transferability of the model needs to be evaluated using scheduling process data from other regions and populations. Employing other techniques to compare the proposed model with other scheduling models in terms of the accuracy of their results, flexibility, and implementation difficulties would be very informative. Moreover, investigating the effect of more comprehensive objective functions (e.g. applying variable weights to different activity types) could add values to the literature of the subject.