"An Effective Tabu Search Method with a Limited Search Space for Carpooling Optimization Problems"
Kosei Takahashi, Toshichika Aoki, Takayuki Kimura and Tohru Ikeguchi

Carpooling systems are one of the effective means of reducing traffic congestion. Recently, many carpool matching services, such as Carpool Global and Share Your Ride, have arisen to match passengers as carpool members. Such carpool matching services require high-speed matching of carpool groups, while considering the distances between drivers and the pick-up and drop-off points of passengers. Constructing an efficient route in a carpooling system is called the carpooling optimization problem (COP). To solve the COP, an approximate solution method has been proposed using tabu search. However, this method fully searches all routes between the passengers and drivers in possible carpooling groups in each iteration, and this procedure requires considerable computational costs. In this study, we improve this grouping procedure by employing an evaluation function that automatically determines the carpooling groups of drivers and passengers. Numerical experiments demonstrate that the tabu search method using our proposed procedure efficiently determines better carpooling groups, and also drastically reduces the calculation time by approximately 300 seconds compared to the conventional method.