The constantly increasing number of cars on Maltese roads has given rise to the need for an alternative solution for persons whose requirements are not satisfied by conventional public transport such as buses. One possible approach would be to provide a cab carpooling solution, which would provide the same comfort and convenience of private vehicles, while also reducing the overall environmental impact of having one person per car ‒ possibly even eliminating the need of owning a private car.
The proposed system has taken into account the start (pick-up) and end (drop-off) coordinates for each of each upcoming trip, the vehicles available, their position and maximum time detour. The goal was to calculate the best route for each vehicle to fulfil all trips, while minimising some cost function. A dashboard with this information using an in-built dynamic map would then display the computed routes, to be used by the users managing the service.
The developed software makes use of two algorithms: tabu search and ant colony optimization (ACO). The program runs all the predetermined criteria (the coordinates, number of vehicles and detour time) through both algorithms, and presents the user with the best solution. The overall cost of a route would be determined by several criteria, some of these being: distance travelled by the vehicle; amount of time taken to carry out the route; and the amount of time a passenger would be left waiting.
Another aspect of the system is its ability to add new trips dynamically. Each of the algorithms takes into account the existent routes, generating a new solution that would incorporate the new trip by either utilising an idle vehicle or including the trip in an existent route.
Overall, the algorithms performed equally well, each one finding the optimal route for the coordinates within a matter of seconds. It was found that, in some cases where a new pair of coordinates were added in later on, the algorithms tended to behave differently. The tabu search algorithm tended to attempt to add the new coordinates to the existing routes, whereas the ACO algorithm generally preferred creating a new route when there was a car available.
Student: Francesca Maria Mizzi
Course: B.Sc. IT (Hons.) Artificial Intelligence
Supervisor: Dr Josef Bajada