An Organizational-Based Model and Agent-Based Simulation for Co-Traveling at an Aggregate Level

Abstract

Carpooling is an environmentally friendly and sustainable emerging traveling mode that enables commuters to save travel time and travel expenses. In order to co-travel, individuals or agents need to communicate, interpret information, and negotiate to achieve co-operation to find matching partners. This paper offers the scheme of a carpooling model for a set of candidate carpoolers. The model is interpreted using an agent-based simulation to analyze several effects of agents’ interaction and behavior adaptations. Through communication and negotiation processes, agents can reach dynamic contracts in an iterative manner. The start of the negotiation process relies on the agents’ intention to emit an invitation for carpooling. The realization of the negotiation process depends significantly on the departure time choice, on the agents’ profile, and on route optimization. The schedule or agenda adaptation relies on the preferences among the realistic schedules of the agents and usually depends on both the participation of the trip and on the time of day. From the considerations, it is possible to reveal the actual representation of the possible carpoolers during the simulated period. Experiments demonstrate the nearly-polynomial relationship between computation time and the number of agents.

1. Introduction

At present, various research fields including transport behavior require investigations and simulations of the dynamic behavior of travelers. In recent studies, it has become increasingly important to establish the interaction between agents. Traditional modeling applications have encountered difficulties in dealing with the complication of the interaction and negotiation of individuals (agents) that are essential to simulating the carpool travel demand [1]. The method that is more suitable for autonomous entity interaction is based on agent-based modeling (ABM). ABM is a distributed and personal-centric approach that allows agents to recognize the interaction of physical elements and describes many issues arising in research fields such as astronomy, biology, ecology, and social sciences. It has also been used in a wide range of topics within the field of transportation science, including vehicle or pedestrian flow simulations, route selection modeling, vehicle tracking and lane change models, and traffic simulations.

Carpooling is an environmentally friendly and sustainable emerging traveling mode that aids travelers (carpoolers) to save travel time and travel expenses (fuel, charges, and parking fees). It also cuts emissions and reduces traffic jams. Change in some factors such as the rise in fuel prices, charged parking, or the introduction of new traffic policies may lead to a carpool initiative for an individual. In addition, the social economic characteristics (SEC) such as gender, age, relationships, income, education, job, and vehicle and driving license ownership, may play a dynamic role in finding the right persons to co-travel. In order to co-travel, individuals need to negotiate, coordinate, and in most cases, can adapt their daily schedules to enable co-operation [2,3]. The agent’s daily schedule or agenda is a group of sequential trips and activities. Each activity and trip of the daily schedule is specified by the start time and duration. Each negotiation consists of a small number of agents and their daily schedule can be interrelated through co-operation [2,3].

This research presents an organizational-based model and agent-based simulation for long-term commuting at an aggregate level (Travel Analysis Zones (TAZ)) based on work trips (home-to-work HW and work-to-home WH) that is designed to establish a framework and a carpooling social network of the candidates. The purpose of this research is to examine the effects of time limitations and models on how people adjust their own schedule to co-operate. Carpooling is a concrete example of co-operation between people. The focus is on the mechanisms that simulate human behavior when making collaborative decisions. The agent-based simulations can analyze the aggregation consequences of individual behavioral changes to enable carpooling. The model shall support research on both topics in the arena of large scale agent-based modeling and in the field of co-operation and rescheduling in activity-based models.

This paper presents the model and simulation for co-traveling which generalize the conception of interaction, negotiation, and co-ordination of a multi-trips negotiation model. It takes the option of flexible activity planning into account. The model is based on an agent-based and organizational meta-model [4]. The role and organization are the foremost entities in the organizational meta-model. In order to co-travel, agents search for other participants to cooperate with while performing their periodic trips and explore the carpooling social network (CPSN) by emitting carpool invitations and sharing their agendas within a carpooling social group (CPSG). During negotiation, agents may reach complex contracts depending on the “negotiation model” (used to match with the carpooling participants) and also on the travel behavior of the individuals. The agents negotiate about trip timings, and on the driver and vehicle selection, and may adjust their daily agenda to enable co-operation. After finding matching partners during the negotiation procedure, agents may decide to carpool for a specified time period. Carpoolers may re-negotiate and/or re-schedule their daily schedule when someone joins the carpool group or leave it permanently. For implementation, the Janus (http://www.janus-project.org/Home) [5], multi-agent based platform is used which offers an efficient implementation of agent-based and organizational-based concepts.

This paper is organized as follows. After the detailed related work presented in Section 2, an organizational-based model for carpooling is described in Section 3. It is based on three layers (from bottom to top): (1) problem layer; (2) organizational layer; and (3) the agent layer. In depth results and the discussion are presented in Section 4. Finally, the conclusion and ideas for future work are presented in Section 5.

2. Related Work

The related work on carpooling negotiation models, negotiation, and co-operation on multi-agent environments, agent-based studies in other fields (i.e., tourism), and activity rescheduling is presented in this section.

It starts by explaining some of the agent-based models covering coordination and negotiation in carpooling. Hussain et al. [6] present a negotiation model for carpooling based on multiple trips (HW and WH) that is derived from the existing departure time studies presented in [7]. The authors designated the direct communication between agents using a state-transition machine. It also restricted the interaction to within the small groups and the formation of groups is based on the home and Work Travel Analysis Zones (TAZs). The same authors in [8] offer the agents’ interaction mechanism by making an independent group of individuals living in different areas but having the same work TAZ. Only the individuals within a group are permitted to negotiate with each other. The negotiation model on trip departure times and on driver selection is also presented in literature. For instance, Garland et al. [9] propose the conceptual design of an ABM for carpooling applications by simulating autonomous agents and by analyzing the impact of changes in infrastructure, individuals’ behavior, and cost factors. The model uses agent information and social networks to start communications, and then uses routing algorithms and utility functions to trigger negotiation processes. This study is based on [10], which presents the conceptual design of ABM for carpool applications.

Bellemans et al. [11] introduce an agent-based simulation model to support the carpooling of large manufacturing plants. The authors describe the following services: (a) agent-based simulations are used to study the opportunities and inhibitors; and (b) online matching can be used to match the commuter profile. They claim that the complex consultations between agents is necessary for fruitful carpooling because of re-routing and re-scheduling parameters. In [12], an adaptive genetic algorithm based on multi-agent approach is proposed, which can effectively solve the problem of long-term carpooling with a limited search space. The system is a combination of a multi-agent system and genetic paradigm, and by the collective learning process dynamically modified super-heuristic guidance. In [13], the authors used NetLogo to design and present a multi-agent based Dynamic Carpooling System (DCS). The DCS optimizes the use of transportation by sharing the same route. The authors claim that their system provides intelligent matching services and intelligent routing engines that can use real-time information (i.e., weather and traffic conditions).

In terms of travel requirements, co-operation is appropriate for the implementation of supportive activity and trip accomplishment. Ronald et al. [14] presents an agent-based model that emphases the negotiation scheme of cooperative activities. The proposed scheme comprises a precise and structured interactive protocol: a combination of transport and social dimensions. A utility method based on personal and composite attributes is presented. Agents negotiate on the type of activity, destination location, and the departure time of their communal activities. Chun and Wong [15] presented a generalized model to schedule events dynamically that uses a negotiation mechanism. It is based on an agent-based approach. The authors define a group and a negotiating protocol to establish agreements on agendas. Each agent is supposed to state its most preferred choices first. It also identified new proposals in a non-increasing order of preference.

The authors in [16] applied game theory in environments where the agents are autonomous, but may follow some agreed-upon protocols. This revealed that classical mechanic models are valuable for task distribution in large sets of co-operative agents. The queueing networks for task distribution among a comparatively small set of co-operative agents are also applied. The authors also used the less formal social science models of co-operation when there were no strict protocols. Furthermore, they verified that concepts drawn from philosophy can be the basis for the development of shared plans among agents. The authors in [17] present the first complete-implementation of a multi-agent based Delphi process for the document relevance domain. The Delphi method is a procedure that promises a new way of dealing with the co-ordination of agents. Intuitively, the specialists should engage in dialogue, interchange ideas, and change their mind as the discussion progresses. The authors solve the document relevance evaluation problem with a case study where a community of specialists decide whether a document is relevant or not. The domain-specific portion is summarized in certain objects and external modules.

In the research presented in [18], the authors established the Jiuzhaigou tourist shunt model based on the multi-agent simulation platform of NetLogo. It determines the allocation probability according to the space-time load based on the Logit model. The performance is evaluated using two indexes of tourist balanced distribution including the variance model and the Gini–Simpson model. The research study of tourist route selection during the peak travel period illustrates further exploration based on previous studies. The authors in [19] presented an Agent-based Simulator for Tourist Urban Routes (ABSTUR) that provides the number of tourist people signed up for each route. The simulation considered both the characteristics of routes and the types of tourists with their preferences. ABSTUR has been experienced by assisting a group of tourism experts in designing a set of tourist routes in the historic center of Madrid. In this manner, they were able to avoid both overcrowded tourist and non-profitable routes.

A large body of literature (e.g., Nijland, et al. [20] and Guo [12]) has been published about the idea of rescheduling activities. In the context of negotiation to co-operate, this considered agenda adaptation to surprising events which are opposite to the rescheduling activities. Knapen et al. [21] present a framework at a large scale to investigate algorithms for rescheduling. The exchange of information between traffic information applications and commuters is aided by explicit modeling. It chains macroscopic traffic assignment with the microscopic simulation of the agents. The Aurora model developed by Joh et al. [22] provides agenda generation and the decisions of the dynamic activity travel rescheduling. Arentze et al. [23] present a complete description of the Aurora activity-based model for schedule generation and adaptation. A comprehensive model has been indicated by describing the following operations: insertion, shifting, deletion, and replacement of activities, as well as changing locations, trip chaining options, and transportation modes. Prototypes of this level of detail are a prerequisite to incorporate co-operation concepts in carpooling. Gupta and Vovsha [24] describe a hybrid discrete choice-duration framework for work activity by modeling interactions between workers in a multiple-worker household. The important feature is to introduce the intra-household interactions through the worker’s agenda synchronization techniques.

Xia et al. [25] present matching services for carpooling by applying both optimal and heuristic approaches to test and find solutions. It is verified that a new formulation and related solution processes can authorize the purpose of the optimal carpool teams and their routes. Martinez et al. [26] present an agent-based simulation for shared taxis to identify a set of rules for matching in terms of space and time. The authors considered that the client is only eager to agree a maximum deviation from his or her straight path. Knapen et al. [2] present an automated advisory service to match travelling trips for carpooling. The probability for fruitful negotiation is measured by means of a learning mechanism. The matching tool needs to deal with dynamically changing the graph with regards to the topology and edge weights. The problem of finding an optimal tree structured route for carpooling is studied by the same authors in [27], in case some participants leave their car at a carpool parking area. In this research, the authors proposed an algorithm to find the optimal solution for the join tree.

None of the reported research effectively analyses the effect of agents’ behavior and the negotiated schedule adaptation of a set of candidate carpoolers required for co-traveling. In this paper, we propose and present a model to examine the problem.

3. Agent-Based Model for Co-Traveling

An agent-based framework for cooperative travelling is presented to investigate the behavior of carpooling participants. The aim is to simulate how individuals decide to carpool by adjusting their daily agendas, and how actual trip execution activity is performed in the carpooling process. Agents can communicate autonomously to find matching partners in order to co-travel. Agents will carpool for numerous days with the same carpool-group. They can also carpool for several consecutive carpooling periods in different CPSG, one at a time. The negotiation procedure integrates a constant preference scheme for the trip departure times. The travelling trips, HW and WH, in the daily agendas are specifically comprehensive and discussed in the long-term perspective. The negotiation model is used to find the matching partners: by adapting the trip departure times and by selecting the vehicle (car) and the driver of the carpool-group. The driver and vehicle selection is achieved by inspecting the individual’s profiles during the negotiation process. The presented carpooling model is established on the movement of vehicles between traffic analysis zones (TAZ). It is anticipated that people board at home, alight at work TAZ, and vice versa; participants with similar trips can carpool with each other.

3.1. Agent-Based Modeling

An agent-based approach is used for evaluating the effects of an agent’s behavior and for simulating the communications of autonomous entities. It is individual-centric and essentially distributed, and suitable for systems that display complex behavior. The proposed carpooling model is based on the Capacity, Role, Interaction, and Organization (CRIO) meta-model [4]. It provides organizational views for demonstrating dynamic structures in terms of their role and relations. This meta-model offers the transformation from organizational views to ones that are processed for generating an agent-based simulation. Accepting an organizational approach permits agents to dynamically adapt their actions without altering their core structure.

According to the CRIO meta-model, the definition of an organization is “a cluster of roles that participate in structured logical institutionalized designs of interactions with the other roles in a collective perspective. This perspective involves common knowledge, common rules or standards and common feelings, etc. and is considered as an ontology. The goal of an organization is to accomplish some requirements”. A group is used for splitting organizations. The group is an organizational object in which all associates are able to cooperate according to pre-defined interaction designations and rules. A role is defined as “a predictable behavior where a set of role jobs are well-ordered by a strategy, and a set of privileges and responsibilities in the organization context.” Each role contributes to the completion of the necessities of the organization within which it is defined.

According to [28,29], the CRIO meta-model is suitable because the carpoolers are dynamically altering their roles in the carpooling social network. For implementation, the Janus [5] multi-agent based platform is used which offers the well-organized application of agent-based and organizational-based models. Janus is built upon the CRIO organizational meta-model in which the concepts of organization and role are special entities. Each agent has the ability to play its role inside an instance (CPSG) of the organization. The organizational-based modeling permits the situations to be defined in an organized way. It provides the capability to determine where the associations between agents occur and how these associations influence the outcomes [4,30].

3.2. Framework Structure

This section presents the setup of an organizational-based framework and the associated agent-based simulation model for the carpooling problem. The presented framework is based on three layers (see Figure 1 from bottom to top): (1) the problem layer; (2) organizational layer; and (3) agent layer. In the problem layer of the framework, different activities of the carpooling process performed by the agents (carpooling and non-carpooling) are described. The negotiation model on trip departure times and on the selection of the driver for multiple trips is presented. The organizational layer of the proposed model emphases the organizations of the carpooling scheme. It also focuses on the activities in terms of role behaviors of the agents. Subsequently, the design of the day-switching mechanism is revealed by the use of organizational concepts. The agent layer section presents the agent model of the framework where the agent’s behavior is demonstrated and discussed using state-machines.

The agent or individual (carpooler and non-carpooler) is someone who belongs to the region where (s)he executes a daily agenda to fulfil personal needs. The agent’s personal daily schedule is a group of sequential trips and activities. Each activity and trip of the daily schedule is specified by the start time and duration. The demonstrating construction claims that the agents perform their daily activities and also spend their time on traveling between those activities. The schedule adjustments of the participants depends on personal preferences of their feasible schedule. Agents who belong to the same carpooling social group may cooperate while performing their periodic trips by exploring the carpooling social network.

Different layers of the agent-based framework for co-traveling are illustrated in Figure 1. In what follows, each of these layers from bottom to top are described in more detail.

3.3. Problem Layer

This section presents the problem domain of the carpooling model. It is based on three main activities which are iterative and performed by the agents: (1) exploration; (2) negotiation; and (3) carpooling, and each of these activity is described in more detail.

3.3.1. Exploration

Each non-carpooling agent explores the carpooling social network for carpool partners to cooperate with while performing their daily trips. The presented framework is established on the movement of vehicles between Traffic Analysis Zones (TAZ) as different to agents’ street or home addresses. The model considers that people board at home and alight at work TAZ locations. People agree to choose carpool companions from the group of individuals segmented on the basis of similar home and work TAZ locations.

The agents, once they decide to carpool, may start searching for carpool partners from the carpooling social network. In case they do not want to carpool, they continue traveling solo by using their own car. The agents who reside in the same carpooling social group (grouped on the basis of same home and work TAZs) may interact by exchanging text messages. Through the interaction process, the agents may search for the ideal candidate for carpooling and may reach a coordinated solution by negotiating on the departure times of both the trips, on the selection of the driver, and hence on the choice of vehicle. Agents may continue looking for participants in the exploration process throughout the simulated period (in case they are unable to find a carpool partner).

For a carpooling agent, the time intervals, path, and personal profile are considered as the relationship information to compare with other agents. In general, every agent has a basic set of properties for interaction such as mutual interests and requirements. The common interest (intention to invite someone for carpooling) and requirements (the similarity values: path, route, time intervals, and some personal attributes) for the corresponding individuals need to match satisfactorily well for the interaction process.

Each agent (the sender) may look for a carpooling partner by sending him a carpool invitation message. This emission of a carpool invitation depends on the personal intension to invite someone with similar attributes i.e., the similar home and work TAZ. Some people do not like to carpool so they will not emit any carpool invitation. Within a day, an individual can search for carpool partners multiple times in the carpooling social network. The receiver agent may accept the sender or inviter as a carpooling partner when the negotiation succeeds. The negotiation process is described in the following section.

3.3.2. Negotiation

The final decision to form a carpool group is taken in the negotiation process where the actual matching is applied using similarity constraints. The negotiation among agents is taken into account for the selection of departure times of the multiple trips (morning and evening) and also to select the driver of the carpool group. The schedule is adapted based on the preferences amongst the feasible schedules of the agents. The negotiation will become successful only when the driver is available and the preferred trip departure times for both the trips are commonly well-matched within the carpool group. Compatible indicators (described in more detail below) are used in the negotiation process.

Driver and Vehicle Selection

During the negotiation process, the agent’s personal profile is used for the driver and vehicle selection. The agent having the car and the driving-license ownership may be selected as a driver when carpooling. The driver in the carpool is responsible for picking other carpool participants from their home-locations. Hence the first agent of the candidate sequence shall be the driver. The candidate sequence can be considered infeasible and dropped immediately, where the first agent cannot act as the driver.

Time Intervals Similarity

In this study, every moment or interval between the earliest and latest possible trip departure time in the time windows as indicated by the candidate carpoolers is supposed to be equal. The time preference function is the same for each participant over the time and supposed to be constant. For matching agents, time windows equipped with a constant preference function, i.e., $\forall t\in I:P\left(t\right)=1$ are used. For each trip (either $HW$ or $WH$) of an agent, two time windows (departure and arrival) are used.

Let $A$ be a set of all individuals or agents. For an agent $a_i$, the earliest and latest departure time intervals for the trip are $T_{a_i}^b$, $T_{a_i}^e$ and the preferred trip start time of $a_i$ is $t_{a_i}$. The time windows of carpooling participants at the specific TAZ-location $l_i$ are represented by $T_{carpool,l_i}$. The departure and arrival time windows for the carpool trips are the intersection of the departure and arrival time windows of the particular participants. The earliest $T_{carpool,l_i}^b$ and latest $T_{carpool,l_i}^e$ intervals of the intersection of the time windows can be calculated as specified in Equation (1); the indices used for the maximum and minimum range are max() and min() functions, respectively, over the set of carpooling candidates. The available departure and arrival time intervals of trips for the carpool group are given by Equation (1), where $j$ recognizes the candidate carpooler.

$$\begin{array}{c}\hfill T_{carpool, l_i}^b=\underset{j=1\dots N}{max}\left(T_{a_j}^b\right)\\ \hfill T_{carpool, l_i}^e=\underset{j=1\dots N}{min}\left(T_{a_j}^e\right)\end{array}={\displaystyle \bigcap }_{j=1}^N{T}_{a_j l_i}$$

(1)

For some $l_i$, when the time windows $T_{carpool,l_i}$ of the individuals participating in the negotiation process are empty (the $T_{carpool,l_i}$ do not intersect), the case is considered as infeasible (given by the Equation (2)). Similarly when the time windows of the trip departure times intersect, then the case is feasible (given by the Equation (2)) and the negotiation among participants on the trip departure time succeeds.

$${\forall }_h:\begin{array}{c}{T}_{carpool, l_i}=0\mathrm{infeasible}\mathrm{case}\\ T_{carpool, l_i}\ne 0\mathrm{feasible}\mathrm{case}\end{array}$$

(2)

Hence, a carpooling participant may join the carpool group if and only if the desired trip departure times are within the suitable intervals and can be achieved by Equation (3).

$${\displaystyle \bigcap }_{j=1}^N{T}_{HW, a_j l_i} · {\displaystyle \bigcap }_{j=1}^N{T}_{WH, a_j l_i} \ne 0$$

(3)

Path Similarity

Detour or maximum excess time duration integrates the path similarity concepts which are assigned to each individual of the ordered pair that specifies the OD (Origin-Destination) pairs are involved in the particular trips. An individual with a solo trip duration $d_{solo, a_i}$ has an upper limit $d_{detour, a_i}$ for the detour delay in the trip: from home-to-work and from work-to-home TAZs. The maximum excess duration depends on the personal preference of the agent and it may be specified by the individuals.

For negotiation success, the carpool duration for an $a_i$ must be less than or equal to the individual’s detour travel or maximum excess duration $d_{detour, a_i}$.

The negotiation becomes successful when the above described constraints are satisfied and the carpooling participants adapt their daily schedules according to the output of the negotiation. During the schedule adaptation process, the carpoolers agree on pickup and drop-off times, pickup and drop-off orders, and also how long (number of days/months) everyone may carpool with this carpooling group.

When the negotiation succeeds and everyone agrees on the negotiated agendas then the actual trips are executed. The invited agent (the first agent in the sequence of the participants) who is able to drive starts playing his role as driver in the carpooling group. The rest of the participants continue carpooling by playing the passenger role in the carpooling group.

3.3.3. Carpooling

The actual trips (HW and WH) execution activity of the carpoolers is operational for multiple days (for long-term). The presented carpooling model considers that the travel times are oblivious to the actual carpooling trips. The carpooling trips do not expressively decrease jamming on the roads. The pre-computed travel times between TAZs are expected to be time independent. Travel times in the presented model are to be advanced by making it time dependent (by the use of real-time travel times). Since the carpooling model is presented for the long-term, it is considered that the day-to-day schedule of individuals remains the same for all the simulated working days.

During the carpooling trips, the carpoolers may receive carpool invitations from the non-carpooling agents and will reply with either accept or reject messages. The actual negotiation process presented in Section 3.3.2 will be repeated again by considering the car capacity. New trip departure times for both the trips and the pick-up and drop-off orders of the carpoolers must be assigned before a new carpooling candidate can be accepted.

The potential carpoolers may terminate carpooling when their agreed carpool participation period expires. When the driver leaves the carpool group and the carpool group exceeds one, the remaining passengers will re-negotiate the driver selection and decide the pick-up, drop-off order of the carpool group. In this case, the driver first transfers the driver-charge to the newly selected driver from the rest of passengers of the same carpool group and then leaves the carpool group. An agent who once left the group can immediately start exploring the carpooling social networks again and be part of the same or any other active carpool group at a later instance. The same agent can also establish a new carpool group with the carpool participants of his or her interest group. The destruction of the carpool group occurs when only one agent is left in the group or if no persons with a car and a driving license are available.

3.4. Organizational Layer

In an organization layer, organizational concepts are used solely to divide organizations into groups. A group is an organizational body in which all the participants are capable of interacting according to pre-defined interaction definitions and protocols. In groups, sets of roles are stated jointly and specify the communal norms for the roles. Within a group of an organization, every agent has the capability to play a role. Organizational-based modeling permits the situations to be well-defined in an organized way. It offers the aptitude to determine where the associations exist between the agents and how it influences the outcomes [4,30].

In this model, the following organizations are introduced in the carpooling simulation: (1) Social Organization; and (2) the Carpool Organization.

3.4.1. Carpooling Social Organization

In the above presented organizational model, Carpooling social organization is used to divide the social network into segments, namely carpooling social groups (CPSG). This limits the communication requirements to individuals with similar characteristics (see Figure 2a) as the negotiators for carpooling are members of the same CPSG. In this model, agents are segmented on the basis of the same origin and destination TAZs. Within the CPSG, the agents play their respective Carpooling social role. The agents (who are playing the respective roles) may communicate with each other by exchanging text messages within their communal CPSG. To achieve the required tasks, agents should remain in their own CPSG throughout the simulation period.

3.4.2. Carpool Organization

The carpool organization contains the carpooling agents. When the negotiation succeeds, the receiver agent creates a Carpool group of the Carpool organization and starts his/her role either as Driver role or Passenger role depending on the negotiation outcome. Figure 2b shows the Carpool organization that supports the trip execution or co-traveling of the carpoolers. All carpooling agents must play a role (driver or passenger) in the carpool group of this Carpool organization. The driver of the carpool group will play the Driver role, while the passenger will play the Passenger role in the Carpool group throughout the carpooling period. When the driver’s carpool period expires, he or she will allocate the driving tasks to one of the passengers who owns the vehicle and driving-license and has been playing the passenger role for the longest period. He or she will immediately leave the Carpool group by leaving the Driver role. On the other hand, the passenger who is selected as the driver will start playing the Driver role and will leave the Passenger role immediately. During the lifetime of the carpool group, agents can also interact with the other agents who have the intention to join. An agent can be part of one or more carpool groups throughout the simulation period, but only one at a time. When the carpool period of the particular agent expires, the agent will simply leave the respective role of the carpool group which they belong to. The same agent can later be part of it again or may join or create a new Carpool group.

3.4.3. Day-Switching Organization

In the presented simulation, the synchronization of a day using a time resolution is sufficient and it is a complex task. The day switching mechanism is compulsory to familiarize the concept of synchronized time for each day among agents as the organizational-based concept that is used exclusively for simulated time synchronization. The Day-switching organization is used to create instances for each simulated day. As soon as the agent has completed their daily actions, they need to join a Day-switching group (instance of Day-switching organization). For each day, the first agent will create the day-switching group and joins it by playing the day-switching role. The following agents, after finishing their daily activities, will join the same day-switching group. Every agent joining such a group instantly starts playing the day-switching role. They will wait for other agents to finish their daily actions and to join the Day-switching group by playing their particular role.

The joining of the last individual to the Day-switching group triggers the start of the next-day activities. Different day-switching groups will be created for each day. The day-switching process is repeated over and over until the termination of the simulation.

3.5. Agent Layer

The agent layer is committed to an agent-oriented model (see class-diagram in Figure 3) that is a solution to the problem defined in the problem layer. Agents denote people in the population whose particular properties and communal associations are modeled at the discrete level. Each agent acts independently and therefore is considered an autonomous entity.

In this simulation model, the agents live and execute their own daily agenda in the carpooling social network, and the agent environment is therefore established. The simulation starts the execution by loading personal profiles of the agents and the network information (OD-based travel time matrix). The carpooling social network is segmented and each agent becomes a member of a CPSG as determined by its home and work TAZs. Each agent once in its lifetime becomes part of such a social group (CPSG). The simulator comprises at most one carpool social group for each home-work TAZ combination. As soon as the agent becomes a member of the CPSG, it starts playing the role (social role).

A finite state-transition machine is used to model the behavior of the agent. It is composed of four states: “Exploring”, “Waiting-for”, “Driving”, and “As-passenger” (see Figure 4). The transition of the agents between different states depends on the interaction mechanism. The interaction between agents is modeled by the use of the text messages. The agents can exchange text messages with the other agents who belong to the same CPSG. The Carpool invitation, Accept, and Reject messages are used for interaction.

The state-machine is described in more detail in the following sub-sections.

3.5.1. Exploring

Exploration in the carpooling social network is the action of searching for people involved in co-operation. In the Exploring state, the sender agent may search for a partner by sending a Carpool invitation message to a randomly chosen agent, of the same CPSG. An invitation can be emitted on the basis of an agent’s properties and interests. A variable probToInvite is used to model these properties and interests. If the value of probToInvite for someone is set to 30%, it implies that on a given day an agent has a probability of 0.3 to invite someone for carpooling. Once an invitation has been released, the sender enters into the WAIT state, and waits for the receiver’s reply.

An agent can receive a Carpool invitation message from another agent in the Exploring state and will take the cooperative decision based on the negotiation model, discussed in Section 3.3.2. In case there is a feasible invitation for the receiver agent, he or she will reply with the Accept message and will change his or her state to either Driving or As-passenger. When the invitation is not decent, then he or she will reply with the Reject message and will continue the exploration process to find the ideal carpool partners in the same state.

When the negotiation succeeds between agents, the receiver agent creates a carpool group which is an instance of the Carpool organization. The receiver agent registers himself and starts playing the suitable role, either Driver role or Passenger role. Within a day, an agent can search CPSG for the participants multiple times sequentially. During the interaction process, the agents can switch multiple times between Exploring and Waiting-for states.

3.5.2. Waiting-For

In the Waiting-for state, the sender agent is waiting for the receiver’s reply. If the sender receives an Accept message then the sender agent joins the same Carpool group that the receiver belongs to. The sender agent changes its state to either Driving or As-passenger depending on the receiver’s reply. If a driver exists in the carpool group, then the sender agent will join as a passenger and in the case where the sender agent is selected as the driver then he or she will join the carpool group as the driver. When the receiver agent’s reply is a Reject message, the sender agent changes its state to Exploring and again starts to find other carpool partners. In the Waiting-for state, if the sender agent receives an invalid (Carpool invitation or other irrelevant) message, then he or she simply replies with a Reject message and remains in the same state.

The Accept message specifies the role (Driver role or Passenger role) to play in the carpool group. The agent (1) leaves the Waiting-for state; (2) joins the Carpool group; and (3) starts playing the coordinated role of either Driver or Passenger. If the response is a Reject message, the sender agent changes its state to Exploring and tries to find a carpool partner again.

While in the Waiting-for state, the agent rejects any incoming invitation (simply by replying with a Reject message).

3.5.3. Driving

In the Driving state, the driver agent plays the Driver role in the Carpool group and remains in this state throughout his or her carpooling period. In this state, the driver agent can receive Carpool invitation messages and negotiate and coordinate with the sender agent. The driver agent can reply with either Accept or Reject messages on the basis of a sender’s profile and the remaining seats in the vehicle. The driver leaves this carpool group when his or her carpooling period expires by leaving the Driver role. In this case, if the carpool group size still exceeds one, the remaining passengers will renegotiate for the driver and vehicle selection, and pick-up and drop-off orders of the participants. The driver agent who leaves the carpool group will change its state to Exploring. The driver agent destroys the carpool group when he or she is the only one left in the group after all passengers have quit.

3.5.4. As-Passenger

The passenger agent’s behavior with regard to carpool association and co-operation while present in the As-passenger state is identical to the driver agent in the Driving state. Except, when the driver agent’s carpooling period deceases and the remaining passengers re-negotiate to choose a driver. The selected driver agent will continue carpooling by starting the Driver role and by leaving the Passenger role of the same Carpool group.

The agents, once they finish their daily activities, will move to the following day immediately. Because of the combination of subsequent reasons: (1) agents will carpool on a long-term basis, for a specified time period; (2) agents are associated with carpool groups sequentially; (3) a carpool calendar is not followed by the agents; and (4) the newly accepted carpooling agents can join a carpool group on any day.

4. Results

For the experimentations, a carpooling social network was recognized by generating a population. FEATHERS [31], an operative activity-based traffic demand model for Flanders (Belgium region), is used to establish the social network for carpooling. There are about six million inhabitants living in the Flanders region. The area is subdivided into 2386 TAZs and on average a TAZ covers 5 [km²] only. The daily schedule for each participant of the synthetic population is generated. The individuals allocate the day taking part in activities and traveling between them. The detailed commuting trips (HW and WH) for co-traveling are taken and discussed relative to the long term. The set of constraining activities, i.e., pick-up and drop-off, shopping, etc., is considered because the induced timing constraints can also have an effect on the commuting trips. Note that only individuals with the same home and work TAZs can carpool together.

To examine the behavior of the carpoolers, the presented framework is simulated for 150 working days and the constraints shown in

Table 1. Important constraints and their values for the experiments.

Constraints	Values
No. of persons invited	At most 5 people/simulated day.
No. of agents	18,000 individuals whose transportation mode is car.
Destination TAZs	Twenty two TAZs from the Brussels region of Belgium.
Time windows’ length	5 min, 10 min, 15 min, 20 min, 25 min, and 30 min.
Maximum car capacity	5 persons (driver included).
Carpool period	[30 to 60 days] by sampling from a uniform distribution.
Constraining activities	Enabled: pick-up and drop-off, shopping.

are applied to accomplish the simulation results.

As a proof-of-concept, some experiments were conducted and are explained as follows:

Figure 5 demonstrates the development of the number of active carpool groups over the simulated period. The horizontal axis indicates the simulated working days and the vertical axis specifies the number of active carpool groups for each day. The graph in Figure 5 is based on six curves. Each curve indicates the length of the time windows. As shown in Table 1, the experiments were conducted by taking different time window lengths ranging from 5 min to 30 min with an interval of 5 min (i.e., 5 min, 10 min, 15 min, etc.). As per intuition, a larger time acceptance window allows for more carpooling. During the initial period of the simulation, also known as the warm-up period, the number of active carpool groups monotonically increase with the passage of time since the shortest possible carpooling period lasts for 30 days only. In the warm-up period, the active carpool groups are placed in a realistic condition and this means that the initial transient has passed and the simulation output is in a steady state. Figure 5 shows a visual representation of active carpool groups over the simulated period. After the warm-up period, each curve shows a decline because the destruction rate of carpool groups is higher than creating the new carpool groups. The new carpoolers give the impression of joining existing carpool groups more frequently than creating new ones and joining them. It appears to be convenient to join an existing carpool group rather than to create a new one. In this case, the number of active carpool groups decreases, but the number of active carpoolers does not decrease. The curves become stable with a linear decrease after 60 days because the possibility to join existing carpool groups becomes lower due to the car saturation effect.

The graph in Figure 6 expresses the number of active carpoolers over the simulated period of 150 days. The x-axis displays the working days while the y-axis shows the number of active carpoolers. It is perceived that, on average, a larger time acceptance window permits more carpooling. The curves represent the active carpoolers for each length of the time window ranging from 5 min to 30 min with an interval of 5 min (i.e., 5 min, 10 min, 15 min, etc.). The number of active carpoolers quickly rises during the warm-up period of the simulation and the shortest carpooling period continues up to 30 days. Note that the warm-up period is 30 days where the individuals are only joining the carpool groups. After the warm-up period, the increase rate is lower because of the joining and leaving the carpool groups, respectively. The curves show the decrease of the number of active carpoolers after the warm-up period because the rate of joining by the new carpoolers is lower compared to the rate of leaving the carpool periods by the existing carpoolers. The share of carpooling individuals appears to have become saturated after 100 simulated working days. The results show that when the length of the time window is larger, the chances for negotiation success are greater than when using the smaller one and the behavior of the carpoolers evolves over time due to their carpooling periods and the car capacity parameters.

The graph in the Figure 7 illustrates the average carpool group size as a function of time. The carpool size gradually increases during the warm-up period up to 30 days of the simulation. After the warm-up period, the carpool group size curve almost shows spikes. This is enlightened as follows: when the carpooling period of the carpoolers expires and they leave the existing carpool group, there is an enhanced likelihood that they will join another (existing or the same) carpool group instead of creating a new one. After a few days (nearly 80-days), the carpool group size increases at an aggregate level because the rate of the passengers joining groups is higher than the new drivers joined. During this period, the passengers join the existing carpool groups rather than create new ones.

The measurement of the computation time of the agent-based simulation is also one of the goals of this study. This is done to analyze the effect of the interaction between individuals. In addition, it aims to determine whether optimization is required to iterate reality and precisely predict carpooling negotiation consequences for the whole population of the study area. The graph in Figure 8 indicates the average computation time of the presented simulation. The experiment was conducted on an Intel^® Xeon^® CPU E5-2643 [email protected] 3.50GHz (2-processors) machine, with 128 GB of RAM and 64-bits operating system. The population scale is achieved by taking 1000 to 10,000 agents (i.e., 1000, 2000, 3000, up to 10,000) for various simulation runs. Each time, the simulation is executed for 150 work-days. To perform this experiment, a constant time window of 30 min is used for each run. The rest of the constraints are the same as shown in the Table 1 except the number of agents. The curve in the graph shows that the processing time increases in a nearly polynomial way with different numbers of agents. It happens due a greater execution of the interaction and the negotiation mechanisms.

The model presented in this paper requires that all carpooling individuals share the source travel analysis zone, as well as the destination travel analysis zone. This constraint will be considered in future research, which will allow the route of one participant to be a subpath of the route of another participant. The car trip depends on the selection of the driver and the pick-up and drop-off orders of the passengers. This information is used to select the optimal driver.

5. Conclusions and Future Work

An agent-based simulation for long-term carpooling has been developed and presented to simulate human behavior when decisions for co-operation are to be made. It setups the framework and also the social network of the carpooling candidates. The model covers the co-operation of individuals’ matching for commuting trips. The negotiation model is based on the constant preference function of the trip start times and the personal profile of the driver and the vehicle selection. The implementation also applies constraining activities by considering the personal daily schedule of each individual. Sensitivity analysis of the simulation model was also conducted during this research. Experiments showed that when the time window was larger, the chances for a successful negotiation were greater. The computation time of the simulation increased in a nearly polynomial manner with the increase of the number of agents. The simulation model requires a large amount of accurate input data, and has scalability issues that are still to be solved. Apart from scalability issues, future research will mainly focus on the effect of schedule adaptation and enhancing the mechanisms for communication and negotiation between agents. To make this simulation operational, multi-zonal interaction and negotiation will be taken into account. In addition, other features, including feasible pick-up and drop-off orders of the carpooling agents of the same carpool groups, will be added to increase the volume of the potential carpoolers.