Carpooling Scheme Selection for Taxi Carpooling Passengers: a Multi-Objective Model and Optimisation Algorithm

Qiang Xiao; Rui-chun He

doi:10.5604/01.3001.0010.0530

Authors

Qiang Xiao School of Traffic and Transportation, Lanzhou Jiao tong University, Lanzhou, China Author
Rui-chun He School of Traffic and Transportation, Lanzhou Jiao tong University, Lanzhou, China Author

DOI:

https://doi.org/10.5604/01.3001.0010.0530

Keywords:

traffic engineering, taxi carpooling, multi-objective optimisation, information entropy

Abstract

Carpooling has been long deemed a promising approach to better utilizing existing transportation infrastructure, the carpooling system can alleviate the problems of traffic congestion and environmental pollution effectively in big cities. However, algorithmic and technical barriers inhibit the development of taxi carpooling, and it is still not the preferred mode of commute. In order to improve carpooling efficiency in urban, a taxi carpooling scheme based on multi-objective model and optimisation algorithm is presented. In this paper, urban traffic road network nodes were constructed from the perspective of passenger carpooling. A multi-objective taxi carpooling scheme selection model was built based on an analysis of the main influences of carpooling schemes on passengers. This model aimed to minimise get-on-and-get-off distance, carpooling waiting time and arriving at the destination. Furthermore, a two-phase algorithm was used to solve this model. A rapid searching algorithm for feasible routes was established, and the weight vector was assigned by introducing information entropy to obtain satisfying routes. The algorithm is applied to the urban road, the Simulation experimental result indicates that the optimisation method presented in this study is effective in taxi carpooling passengers.

References

BALDACCI R., MEMIEZZO V. & MINGOZZI A., 2013. An exact method for the carpooling problem based on lagrangean column generation. Operations Research, 52(3),pp.422-429.

BONARRIGO S., CARCHIOLO V., LONGHEU A., LORIA M., MALGERI M., et all, 2014. A carpooling open application with social oriented reward mechanism. Lecture Notes in Computer Science, 8729, pp.447-456.

BRUGLIERI M., COLORNI A., LIA F. & LUÈ A., 2014. A Multi-objective Time-dependent Route Planner: A Real World Application to Milano City. Transportation Research Procedia, 3, pp.460-469.

CALVO,R.W., LUIGI, F.L., HAASTRUP P. & Maniezzo V., 2004. A distributed geographic information system for the daily carpooling problem. Computers and Operations Research, 31(13),pp. 2263-2278.

CHENG J., TANG,ZH.H., LIU J. & ZHONG L., 2013. Research on dynamic taxipooling model based on genetic algorithm. Journal of Wuhan University of Technology(Transportation Science& Engineering) , 37(1), pp.187-191.

DELHOMME P. & GHEORGHI A., 2016.Comparing French carpoolers and non-carpoolers: Which factors contribute the most to carpooling?. Transportation Research Part D: Transport and Environment, 42(1), pp.1-15.

FAHNENSCHREIBER S., GÜNDLING F., KEYHANI M.H. & SCHNEE M., 2016. A Multi-modal Routing Approach Combining Dynamic Ride-sharing and Public Transport. Transportation Research Procedia, 13,pp. 176-183.

FRIGINAL J., GAMBS S., GUIOCHET J. & KILLIJIAN,M.O., 2014. Towards privacy-driven design of a dynamic carpooling system. Pervasive and Mobile Computing, 14(5),71-82.

GARLING T., GARLING A. & JOHANSSON A., 2000. Household choice of car-use reduction measures. Transportation Research Part A, 34,pp.309-320.

HE W., KAI H. & LI D., 2014. Intelligent carpool routing for urban ridesharing by mining GPS trajectorie. IEEE Transaction on Intelligent Transportation system, 15(5), pp.2286-2296.

HUANG C., ZHANG D., SI,Y.W. & STEPHEN,C. H. LEUNG, 2016. Tabu search for the real-world carpooling problem. Journal of Combinatorial Optimization, 32(2), pp.492-512.

KNAPEN, L., YASAR, A., CHO, S., et all, 2014. Exploiting graph-theoretic tools for matching in carpooling applications. J Ambient Intell Human Comput, 5(3),pp.393-407.

KUMAR A. & PEETA S., 2015. Entropy weighted average method for the determination of a single representative path flow solution for the static user equilibrium traffic assignment problem. Transportation Research Part B: Methodological, 71(1), pp.213-229.

LI B., KRUSHINSKY D.,REIJERS,H.A. & WOENSEL,T.V., 2014. The Share-a-Ride Problem: People and parcels sharing taxis. European Journal of Operational Research, 238(1),pp. 31-40.

MAJKA, A., 2014. Multi-objective optimization applied for planning of regional European airline. Archives of Transport,29(1),pp.37-46.

MALODIA S. & SINGLA H., 2016. A study of carpooling behaviour using a stated preference web survey in selected cities of India. Transportation Planning and Technology, 39(5), pp.538-550.

SHAHEEN,S.A., CHAN N.D. & GAYNOR T., 2016. Casual carpooling in the San Francisco Bay Area: Understanding user characteristics, behaviors, and motivations. Transport Policy, 51,pp.165-173.

SHAO Z.ZH., WANG H.G., LIU H., et al, 2013. Research on service requirement distribution algorithms in carpooling problems. Journal of Tsinghua University (Science and Technology),53(2), pp.252-258.

SUGIHAKIM R. & ALATAS H., 2016.Application of a Boltzmann-entropy-like concept in an agent-based multilane traffic model. Physics Letters A, 380(1-2),pp.147-155.

WAERDEN,P.V.D., LEM A. & SCHAEFER W., 2015. Investigation of factors that stimulate car drivers to change from car to carpooling in city center oriented work trips. Transportation Research Procedia, 10,pp.335-344.

WANG W.L., HUANG H.P., ZHAO Y.W. & ZHANG J.L.,2011. Dynamic customer demand VRP with soft time windows based on vehicle sharing. Computer Integrated Manufacturing Systems, 17(5),pp. 1056-1063.

WOLFENBURG A., 2014. New version of the BBS method and its usage for determining and scheduling vehicle routes. Archives of Transport,31(3),pp.83-91.

XU X., LI K. & LI X., 2016. A multi-objective subway timetable optimization approach with minimum passenger time and energy consumption. Journal of Advanced Transportation, 50(1),pp. 69-95.

YAN S. & CHEN C.Y., 2011. An optimization model and a solution algorithm for the many to many carpooling problem. Annals of Operations Research, 191(1),pp. 37-71.

YUAN CH.W. & WU Q.Q., 2014. Optimal loading rate model of taxi under different objective. Journal of Chang an University (Natural Science Edition),34(2),pp. 88-93.

ZHANG W.Q, ZHANG SH.Y & JIANG L.Q., 1995. A decision assessment model based on entropy and its application. Journal of Systems Engineering, 10(3), pp.69-74.

ZHANG SH.B,YANG Y.J., ZHAO W.Y., ZHANG S.Y. & Jiao H.H. 2014. Hedonic price pricing model based on urban taxi feature. Journal of Chang an University (Natural Science Edition), 34(4), pp.127-133.