Ride Matching Using -means Method: Case Study of Gazela Bridge in Belgrade, Serbia
Publication: Journal of Transportation Engineering
Volume 138, Issue 1
Abstract
Transport networks in many cities are generally very seriously congested. Consequently, travel time, number of stops, unexpected delays, transport costs, level of air pollution, noise, and traffic accidents are increased. In addition to daily congestion, there may be congestion and traffic jams as a consequence of reconstruction of the roads’ lanes. During the past decade, different strategies for transport demand management have been developed, with the aim to decrease existing traffic congestion. One of the available strategies is a ride matching (sharing) concept. This strategy means that several participants share only one private car when traveling from origin to destination. A model for grouping drivers into cars for ride matching, according to similarities of a place of living and working, working hours, and type of car license plate, is developed in this paper. The writers apply the ride matching concept on congested traffic during the reconstruction of the main bridge in Belgrade, Serbia, which is the Gazela Bridge. The basis of the proposed model is the -means method and even-odd concept. To solve the ride matching problem, the writers present improvement of the traditional -means algorithm, in which the numbers of centers is unknown in advance and the number of clusters may not be the same as the number of centers. This modification of the traditional -means algorithm, called advanced -means, for solving a specific ride matching problem is the main contribution of the paper.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This work was supported by Serbian Ministry of Science and Technological Development Grants No. MSTPRCTR36022 and MSTPRCTR36002.
The writers would like to thank the anonymous referees for the valuable suggestions that helped to significantly improve the presentation of the results described in this paper.
References
Anderberg, M. R. (1973). Cluster analysis for applications, Academic, London.
Blumenberg, E., and Smart, M. (2010). “Getting by with a little help from my friends and family: Immigrants and carpooling.” Transportation, 37(3), 429–446.
Brownstone, D., and Golob, T. F. (1992). “The effectivness of ridesharing incentives. Discrete choice models of commuting in Southern California.” Reg. Sci. Urban Econ., 22(1), 5–24.
Coello Coello, C., Van Veldhuizen, D., and Lamont, G. (2002). Evolutionary algorithms for solving multi-objective problems, Kluwer Academic, New York.
Cordeau, J. F., and Laporte, G. (2003a). “The dial-a-ride problem: Variants, modeling issues and algorithms.” Q. J. Belg. French Ital. Oper. Res. Soc., 1(2), 89–101.
Cordeau, J. F., and Laporte, G. (2003b). “A tabu search heuristic for the static multi-vehicle dial-a-ride problem.” Trans. Res. Part B: Methodol., 37(6), 579–594.
Correia, G., Viegas, J. M. (2010). “Carpooling and carpool clubs: Clarifying concepts and assessing value enhancement possibilities through a stated preference web survey in Lisbon, Portugal.” Transp. Res. Part A: Policy Pract., 45(2), 81–90.
Do, H., Nam, P. E., Donald, R., and Drew, P. E. (1998). “Analyzing freeway traffic under congestion: Traffic dynamics approach.” J. Transp. Eng., 124(3), 208–212.
Guo, X., and Lu, H. (2007). “Traffic congestion analysis in complex networks based on various routing strategies.” Mod. Phys. Lett. B, 21(15), 929–939.
Han, D., and Yang, H. (2008). “The multi-class, multi-criterion traffic equilibrium and the efficiency of congestion pricing.” Trans. Res. Part E: Logistics Trans. Rev., 44, 753–773.
Hartigan, J. A. (1975). Clustering algorithms, Wiley, Hoboken, NJ.
Hartigan, J. A., and Wong, M. A. (1979). “Algorithm AS 136: A -means clustering algorithm.” J. R. Stat. Soc. Ser. C (Appl. Stat.), 28(1), 100–108.
Jain, A. K., and Dubes, R. C. (1988). Algorithms for clustering data, Prentice Hall, Upper Saddle River, NJ.
Jungme, P., et al. (2009). “Intelligent vehicle power control based on machine learning of optimal control parameters and prediction of road type and traffic congestion.” IEEE Trans. Veh. Technol., 58(9), 4741–4756.
Kaufman, L., and Rousseeuw, P. J. (1990). Finding groups in data—An introduction to cluster analysis, Wiley, Hoboken, NJ.
Koppelman, F. S., Bhat, C. R., and Schafer, J. L. (1993). “Market research evaluation of actions to reduce suburban traffic congestion: Commuter travel behavior and response to demand reduction actions.” Transp. Res. Part A: Policy Pract., 27A(5), 383–393.
MacQueen, J. B. (1967). “Some methods for classification and analysis of multivariate observations.” Proc., 5th Berkeley Symp. on Mathematical Statistics and Probability, University of California Press, Berkeley, CA, 281–297.
Parragh, S., Doernera, K., and Richard, F. (2010). “Variable neighborhood search for the dial-a-ride problem.” Comp. Oper. Res., 37(6), 1129–1138.
“Press conference on Beijing municipality giving priority to the development of public transportation, accelerating the construction of intelligent traffic, and easing traffic congestion.” (2008). Chin. Law Gov., 41(6), 67–82.
Quddus, M., Wang, C., and Ison, S. (2010). “Road traffic congestion and crash severity: Econometric analysis using ordered response models.” J. Transp. Eng., 136(5), 424–435.
Rajagopalan, S., and Hung-Liang, Y. (2001). “Capacity planning with congestion effects.” Eur. J. Oper. Res., 134(2), 365–377.
Roberg, P., and Abbess, C. R. (1998). “Diagnosis and treatment of congestion in central urban areas.” Eur. J. Oper. Res., 104(1), 218–230.
Rousseeuw, P. (1987). “Silhouettes: A graphical aid to the interpretation and validation of cluster analysis.” Comp. Appl. Math., 20(1), 53–65.
Tao, C. C., and Chen, C. Y. (2007a). “Dynamic rideshare matching algorithms for the taxipooling service based on intelligent transportation system technologies.” Proc., 14th Int. Conf. on Management Science and Engineering, Vol. 1–3, Curran Associates, Red Hook, NY, 399–404.
Tao, C. C., and Chen, C. Y. (2007b). “Heuristic algorithms for the dynamic taxipooling problem based on intelligent transportation system technologies.” Proc., 4th Int. Conf. on Fuzzy Systems and Knowledge Discovery, Vol. 3, 590–595.
Teodorović, D., and Dell’ Orco, M. (2008). “Mitigating traffic congestion: Solving the ride-matching problem by bee colony optimization.” Transp. Plann. Technol., 31(2), 135–152.
Teodorović, D., and Edara, P. (2005). “Highway space unventory control system.” Transportation and traffic theory: Flow, dynamics and human interaction, H. Mahmassani, ed., Elsevier, Amsterdam, Netherlands, 43–62.
Uesugi, K., Mukai, N., and Watanabe, T. (2007). “Optimization of vehicle assignment for car sharing system.” Proc., 11th Int. Conf. on Knowledge-Based Intelligent Information and Engineering Systems (KES) and the XVII Italian Workshop on Neural Networks, Springer, Berlin.
Wu, Y. H. (2007). “Agent behavior in peer-to-peer shared ride systems.” Master’s thesis, Dept. of Geomatics, Univ. of Melbourne, Melbourne, Australia.
Zhihai, X., Chengbin, C., and Haoxun, C. (2006). “A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints.” Eur. J. Oper. Res., 174(2), 1117–1139.
Zhihai, X., Chengbin, C., and Haoxun, C. (2008). “The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments.” Eur. J. Oper. Res., 185(2), 534–551.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 138 • Issue 1 • January 2012
Pages: 132 - 140
Copyright
© 2012 American Society of Civil Engineers.
History
Received: Oct 5, 2010
Accepted: Apr 27, 2011
Published online: Apr 29, 2011
Published in print: Jan 1, 2012
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.