Multi Agent System for Ride Sharing and Carpooling

Abstract

This thesis describes the research done to implement a ridesharing solution in Sri Lanka using a multi-agent system based approach. Particularly this research focuses on implementing a carpooling/ridesharing solution using real geospatial data extracted from a geographic information system. Emphasis is placed on solving the complex problem of user route matching based on journey start, end locations and route overlap.Carpooling is the sharing of car journeys so that more than one person travels in a car. By having more people using one vehicle, carpooling reduces each person's travel costs such as fuel costs, tolls, and the stress of driving. Carpooling is seen as a more environmentally friendly and sustainable way to travel,since sharing journeys reduces carbon emissions, traffic congestion on the roads, and the need for parking spaces. Carpooling/ridesharing however has many challenges such as socio-cultural challenges, which need to be looked into when implementing a solution. A multi agent based solution is proposed due to the complex and dynamic nature of the problem.For this system, users are simulated using the simulation capabilities of a multi agent system. Route data for the simulated users are generated using a list of addresses in the Western Province of Sri Lanka. The list of addresses are then converted to geo location data and randomly paired using a randomized pairing algorithm to generate routes for the users. Agents generated with the simulated routes are allowed to interact with one another to group together and form ride shares or carpools. A Route Match Agent is implemented with a custom route match algorithm in order to find the best pairings for ride shares and carpools. Carpools are identified as an extension of rideshares, established between multiple users who have overlapping journeys with approximately the same route distances. The system also includes a social network module where connections between users are mapped as first and second degree connections.The available rideshares/carpools for user are then ranked based on the social connections. Running tests against the system showed that it is effective in finding the optimal carpools for users. The simulation also showed that for successful carpools to be established, a large user pool from the same area is required.