Agent-based Simulation Model and Matching Support Framework for Carpooling

Abstract

Carpooling is a specific instance of cooperation between two or more individuals regarding the use of a single vehicle to meet their mutual commuting needs. In actual practice, carpooling and similar concepts can be supported by intelligent advisory systems for individuals: one of these is trip matching. Evaluating the operational fitness of such systems in the testing phase requires an active community of users. Therefore the need for agent-based simulation arises to test the advisory system because (i) on one hand individuals have their own goals and plans and (ii) on the other hand they need to communicate, negotiate, coordinate and adapt their daily schedule to enable cooperation to achieve their goals. The negotiation between individuals requires that they effectively convey and interpret information to enable carpooling. Negotiation is essential to cooperation both on activity and on trip execution. Mutual coordination and matching for carpooling are challenging tasks both for the driver and for all the passengers. This thesis specifies mechanisms to simulate carpooling for commuting in the long term. Firstly an agent-based simulation model for carpooling is presented; the focus is on mechanisms to simulate human behavior that affect the decisions for cooperation. Secondly an employer-based matching framework to support closed-group carpooling is presented. Part I: Agent-based Simulation Model Motivated by the limitations of coordination and negotiation mechanisms, one of the major contributions of this research is to model and simulate the agents’ behavior in the carpooling simulation to investigate the effect of cooperation between individuals with regard to the trip execution. The study of human behavior is important to investigate its effect on the outcome of cooperation decisions. Another major contribution of this research is to develop a mechanism to simulate the outcome of multiple trips based negotiation; this is used to find and evaluate feasible carpool sequences for the participants and to select the optimal one. This research considers autonomous individuals and the similarity relationships between them. At the start of the PhD research project it was observed that no activity-based travel demand research studied coordination and negotiation and the effect of negotiated agenda adaptation required for carpooling. The design of a comprehensive model to simulate the carpooling process is presented. It is mapped to an agent-based simulation which requires the setup of a framework and the establishment of a network of carpooling candidates. It analyzes various effects of individuals’ interaction and behavior adaptation of a set of candidate carpoolers. Agents’ coordination in a multiple-trip negotiation model is investigated. Both home-to-work (HW) and work-to-home (WH) commuting trips are negotiated at once. The carpooling social network of candidates is established starting from results predicted by FEATHERS. The agent-based simulation for carpooling has been implemented using Janus (multi-agent platform) and by several increments: each increment is discussed in a different chapter. Chapter 2 presents an agent based framework and simulation setup to evaluate the evolution of aggregate behavior of the carpooling society under several conditions. The direct interaction between agents is modeled within restricted carpooling social groups (CPSG) and the CPSG are formed by considering their home and work TAZs. A negotiation model for carpooling on the trips departure times and also on driver assignment is presented. In this chapter the evaluation process is not aimed to find the optimal passenger pick-up sequence. The base model presented in this chapter is used to measure the carpool potential on similar trips and without taking into account the pick-up and drop-off orders of the passengers. The negotiation outcome is determined by a deterministic function based on the candidates’ profiles and time windows. Chapter 3 presents an agent-based framework for long term carpooling using the CRIO organizational meta-model. It has been setup to simulate the emergence of carpooling and analyzes various effects of agent interaction and behavior adaptation for sets of candidate carpoolers. It enables the interaction between agents by establishing the CPSGs on the basis of work TAZs. A multiple-trip negotiation model is presented for the departure time decisions, driver and vehicle selection, and pick-up and drop-off orders of the carpoolers. The model is also used to measure the evolution of carpooling potential over time and takes into account the pick-up and drop-off order of the passengers. In order to find the optimal sequence, different options are evaluated by a scoring function based on the degree of flexibility (degree of freedom). Chapter 4 presents an extension of the work described in chapter 2 where cooperating carpoolers were restricted to share the respective home and work areas and in chapter 3 where the constant preferences for the trips start times were used. The presented carpooling model analyzes various effects of multi-zonal individuals’ interaction and behavior adaptation for sets of candidate carpoolers. The multiple trips negotiation model is extended and highly depends on the factors that influence the departure time decision, on the individuals’ profile, route optimization and on the effect of constraining activities. The driver and vehicle selection, pick-up and drop-off order, and the preferred trip start time intervals of the optimal carpool group are evaluated by using scoring functions: (i) time of day, (ii) the time loss and (iii) degree of flexibility. Chapter 5 further extends the agent-based carpooling simulation model by the use of address disaggregation so that all aspects of the complete carpooling problem can be examined. It presents a mechanism to simulate the interactions of autonomous agents which enables communication within CPSGs that coincide with the sets of agents working at a particular company or institution. The street addresses of the individuals are used to extract the actual trip duration information on the road network from the OpenStreetMap (OSM) dataset. A multiple trip negotiation model for work trips (HW and WH) is also presented to enable agent matching. The driver and vehicle selection, pick-up and drop-off order and the preferred trip start times of feasible carpool groups are evaluated by means of scoring functions: (i) degree of flexibility and (ii) the time loss. One of the objectives of the reported research is to investigate the computational performance of the model that contains all features described in this chapter. Part II: Matching Support Framework and Service Large companies may incorporate a variety of means to encourage employees to carpool, including by providing an employees’ matching service to identify colleagues. Motivated by the expected benefits of using the personnel databases of large employers to provide carpooling advice, this research contributes by providing a mechanism to find all the feasible carpool groups for each employee using mutually compatibility indicators along with a scoring mechanism to evaluate solutions in order to propose a limited set of the feasible carpools to each employee for further negotiation. In chapter 6, an innovative carpool matching advisory framework is presented that is to be rolled out by large companies to expand the range of ways that employees can carpool. It was designed to be operated by employers in order to find optimal carpool matching solutions which are to be proposed to the candidate carpoolers. It has the capability to account for dynamic evolution of the extracted personnel database in order to minimize burden on the users. It notifies interested candidate carpoolers about new opportunities to find partners belonging to the closed managed group. The framework is capable to match candidates based on home and target locations as well as on the time windows and maximum excess durations specified by the interested individuals. The innovative advisory framework proposes suitable groups of people (carpools) to the registered users. For a given group, the timely feasible pick-up and drop-off orders are evaluated. Those are scored at the carpool level. The best groups are kept and presented to the group members who in turn evaluate them using their own individual scoring criteria and start negotiation to take the final decision. As a proof-of-concept of the proposed framework, experiments were conducted at the scale of the Doppahuis database.