Abstract: Dynamic ridesharing (DR), as a new approach to help alleviate the traffic congestion and improve travel experience, has gained lots of attentions in recent years. However, how to smartly choose the suitable passengers from the numerous appliers so as to achieve as high service effectiveness and satisfaction as possible challenges the drivers. Apart from the reason that the participants' travel schedule and the number of seats constrain the matching of passengers and drivers, another important problem is the matching scale. In reality DR service often involves thousands of participants who are located randomly in a large road network. Consequently, to accomplish a match in a short time is a very time-consuming task. A multi-objective 0-1 programming model is built whose objective functions are to maximize passengers' utility and meantime to minimize the travel distance. Such consideration can care about the passengers' most interest but at lowest cost of drivers. The constraints of the model comprise the time limitation to passengers and drivers and driver's reserve utility. An intelligent algorithm which incorporates scattered algorithm into the harmony algorithm is developed to help solve the model because the scale of the model is beyond the capability of the traditional algorithms. Based on a 100*100 road network (more complicated than the real road network, actually), the simulation experiments are carried out twice according to the way of how to specify the passengers and driver's utility. The simulation result shows that the model is reasonable and the algorithm is feasible in terms of the derived Pareto solutions. Moreover, compared with the directly assigned utility value, the utility function is more effective to find the suitable the riders. Finally, the comparison with Tabu search algorithm shows that our algorithm outperforms the rival algorithm, which further indicates that our algorithm is effective and applicable to the reality.

Key words: dynamic ridesharing, multi-objective 0-1programming model, harmony scatter search algorithm, utility