A priori approach of real-time ridesharing problem with intermediate meeting locations

• Autorzy: Aissat C. , Oulamara A.

Identyfikatory

DOI

10.1515/jaiscr-2015-0015

• Języki publikacji: EN

Abstrakty

EN

Ridesharing is a mobility concept in which a trip is shared by a vehicle’s driver and one or more passengers called riders. Ridesharing is considered as a more environmentally friendly alternative to single driver commutes in pollution-creating vehicles on overcrowded streets. In this paper, we present the core of a new strategy of the ridesharing system, making it more flexible and competitive than the recurring system. More precisely, we allow the driver and the rider to meet each other at an intermediate starting location and to separate at another intermediate ending location not necessarily their origins and destinations, respectively. This allows to reduce both the driver’s detour and the total travel cost. The term “A priori approach” means that the driver sets the sharing cost rate on the common path with rider in advance. An exact and heuristic approaches to identify meeting locations, while minimizing the total travel cost of both driver and rider are proposed. Finally, we analyze their empirical performance on a set of real road networks consisting of up to 3,5 million nodes and 8,7 million edges. Our experimental results show that our heuristics provide efficient performances within short CPU times and improves the recurring ridesharing approach in terms of cost-savings.

Słowa kluczowe

EN

ridesharing; a priori approach; cost rate; heuristic approaches; travel cost; driver; rider; cost savings

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2014
• Tom: Vol. 4, No. 4
• Strony: 287--299
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Aissat C.

• Loria laboratory, University of Lorraine, Nancy, France

autor

Oulamara A.

• University of Lorraine, Ile de Saulcy, Metz, France

Bibliografia

• [1] Agatz, N.A.H., Erera, A., Savelsbergh, M., Wang, X.: Optimization for dynamic ridesharing: A review. European Journal of Operational Research, 223, pp. 295-303 (2012)
• [2] Furuhata, M., Dessouky, M., Ordonez, F., Brunet, M.E.,Wang, X., Koenig, S.: Ridesharing: The stateof-the-art and future directions. Transportation Research Part B: Methodological, 57, pp. 28-46 (2013)
• [3] Agatz, N.A.H., Erera, A., Savelsbergh, M.W.P., Wang, X.: Dynamic ridesharing: a simulation study in metro atlanta. Transportation Research Part B, Methodological, 45, pp. 1450-1464 (2011)
• [4] Baldacci, R., Maniezzo, V., Mingozzi, A.: An exact method for the car pooling problem based on lagrangean column generation. Operations Research, 52, pp. 422-439 (2004)
• [5] Herbawi, W., and Weber, M. 2012b. Modeling the multihop ridematching problem with time windows and solving it using genetic algorithms. In Proceedings of the 2011 IEEE 24th International Conference on Tools with Artificial Intelligence, ICTAI ’12, IEEE Computer Society. (Athens, Greece, 2012)
• [6] Ghoseiri, K., Haghani, A., Hamedi, M.: Real-time rideshare matching problem. University of Maryland, Department of Civil and Environmental Engineering, UMD-2009-05 (2011)
• [7] Amey, A.: Proposed Methodology for Estimating Rideshare Viability Within an Organization: Application to the MIT Community, Transportation Research Board Annual Meeting 2011, pp. 11-2585 (2011)
• [8] Winter, S., Nittel, S: Ad-hoc shared-ride trip planning by mobile geosensor networks. International Journal of Geographic Information Science, 00, pp. 1-21 (2006)
• [9] Xing, X., Warden, T., Nicolai, T., Herzog, O.: Smize: a spontaneous ridesharing system for individual urban transit. In: Proceedings of the 7th German Conference on Multiagent System Technologies, MATES’09. Springer-Verlag, Berlin Heidelberg, pp. 165-176 (2009)
• [10] Geisberger, R., Luxen, D., Neubauer, S., Sanders, P., Volker, L.: Fast Detour Computation for Ride Sharing. In: 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - ATMOS’10. Editors: Th. Erlebach, M. Lubbecke, pp. 88-99 (2010)
• [11] Calvo, R.W., de Luigi, F., Haastrup, P., Maniezzo, V.: A distributed geographic information system for the daily car pooling problem. Computers & Operations Research, 31, 2263-2278 (2004)
• [12] Herbawi, W., Weber, M.: The ridematching problem with time windows in dynamic ridesharing: a model and a genetic algorithm In: Proceedings ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 1-8 (2012)
• [13] Herbawi,W.,Weber, M.: Evolutionary multiobjective route planning in dynamic multi-hop ridesharing. In: EvoCOP’11, pp. 84-95 (2011)
• [14] Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient Models for Timetable Information in Public Transportation Systems. ACM Journal of Experimental Algorithmics, 12 (2.4) (2007)
• [15] Drews, F., Luxen, D.: Multi-hop ride sharing. In: Proceedings of the Sixth Annual Symposium on Combinatorial Search, pp. 71-79 (2013)
• [16] Bit-Monnot, A., Artigues, C., Huguet, M.-J., Killijian, M.-O.: Carpooling: the 2 Synchronization Points Shortest Paths Problem. In: 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Vol. 33, pp. 150-163 (2013)
• [17] Dijkstra, E.W.: A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, pp. 269-271 (1959)
• [18] Hart. P.E., Nilsson, N., Raphael, B.:A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Trans. on Sys. Sci. and Cyb. 4, pp. 100-107 (1968)
• [19] Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact Routing in Large Road Networks Using Contraction Hierarchies. Transp. Sci. 46, pp. 388-404 (2012)
• [20] Arz, J., Luxen, D., Sanders, P.: Transit Node Routing Reconsidered. In: International Symposium on Experimental Algorithms (SEA13). LNCS, volume 7933, pp. 55-66. Springer, Rome (2013)