Heuristic Optimization Algorithms of Multi-Carpooling Problem Based on Two-Stage Clustering

In logistics engineering, transportation system and some other domains, the effect of carpooling is enormously significant. Excellent carpooling strategy may not only economize logistics costs, reduce the traffic jam, but be especially favorable for reducing noise and improving the environment. Thus, a two-stage clustering heuristic strategy is introduced to solve deterministic multi-carpooling problem. In the first stage of the strategy, the conception of matching degree is proposed to guide to assign service requirements to specific vehicle, hence the original problem can be split into several single-vehicle problems. And in the second stage of the strategy, based on priori clustering idea, the number of insertion operations in one single-vehicle matching progress is reduced greatly so as to improve the efficiency of the algorithm. To improve the success rate of matching and reduce total costs, the assignment schema of vehicles is not fixed but adjustable. Heuristic emigration and immigration operators are used in a new distribution when some requirements fail to be assigned or probably lead to long arcs in the last distribution. To verify the validity and practicability of the method, some actual samples are generated based on real map information. Experimental results show the algorithm may not only improve ride success rate greatly, reduce total vehicle costs, but also demonstrate strong practicality.