On Pre-Processing For Least-Cost Carpooling Routing In A Transportation Network

Within a location based social network, carpooling is becoming more and more preferable among workers both living and working near each other due to the continuous increase in gasoline price and air pollution, and is more desirable when working places are far away from homes. To find the least-cost path for carpooling means to find the optimal order to traverse the homes and workplaces to pick up passengers and to drop off them. However, before the order searching is performed, in a large transportation network, it is prevalent to first obtain the least-cost path between any two locations, with one as a work place and the other as a home, to reduce computation time. In fact, for carpool, since only a few people can stay within a vehicle, it is fast to obtain the best pickup and drop-off order. Therefore, the bottleneck to obtain the least-cost route is indeed the calculation of the least-cost paths between any such two locations. The two existing dominant approaches to pre-compute these least-cost paths are Dijkstra's algorithm and A*, where Dijkstra's algorithm is used to compute single-origin multiple-destination least-cost paths while A* is used to compute the least-cost path between an origin-destination pair. In this paper, LU, a best first search algorithm and framework recently proposed to compute single-origin multiple-destination least-cost routes, is adopted in this pre-processingstep to retrieve the optimal path to traverse the carpool-based pickup and drop-off locations. Its performance is compared with A* and Dijkstra's algorithm through a set of experiments in a large transportation network. The results demonstrate that LU is significantly faster than Dijkstra's algorithm and much better than A*.