Signals and Telecommunications Journal

DLINE Journals portal

Home

New Journals

Browse Journals

Journal Prices

For Authors

Print ISSN:
Online ISSN:

About STJ
	DLINE Portal Home Home Aims & Scope Editorial Board Current Issue Next Issue Previous Issue Sample Issue Upcoming Conferences Self-archiving policy Alert Services Be a Reviewer Publisher Paper Submission Subscription Contact us

How To Order
	Order Online Price Information Request for Complimentary Print Copy

For Authors
	Guidelines for Contributors Online Submission Call for Papers Author Rights

RELATED JOURNALS

Journal of Digital Information Management (JDIM)

Journal of Multimedia Processing and Technologies (JMPT)

International Journal of Web Application (IJWA)

Signals and Telecommunications Journal

Calculating the Shortest DriversÃ¢â‚¬â„¢ and PassengersÃ¢â‚¬â„¢ Paths

Arthur Bit-Monnot, Christian Artigues, Marie-JosÃƒÂ© Huguet, and Marc-Olivier Killijian
CNRS, LAAS, 7 avenue du colonel Roche, FÃ¢â‚¬â€œ31400 Toulouse, France., UniversitÃƒÂ© de Toulouse, LAAS, FÃ¢â‚¬â€œ31400 Toulouse, France., UniversitÃƒÂ© de Toulouse, INSA, FÃ¢â‚¬â€œ31400 Toulouse, France

Abstract: Carpooling can reduce traffic congestion and the environmental impact of car use. This paper addresses an important problem for dynamic carpooling: calculating the shortest driversÃ¢â‚¬â„¢ and passengersÃ¢â‚¬â„¢ paths. These paths are synchronized in that they have a common sub-path between 2 points: the point where the driver picks up the passenger and the point where the passenger drops off the car. A passenger path may include time-dependent public transportation elements before or after this common sub-path. This defines the 2SynchronizationPointShortestPath Problem (2SSPPP). We demonstrate that 2SPSPP is a polynomial problem with a worst-case solution. However, efficient algorithms must solve this problem in realistic transportation networks. This paper focuses on efficiently calculating optimal itineraries to solve this 2SPSPP problem, i.e., determining (optimal) pick-up/drop-off points and two synchronized paths that minimize total travelling time. Restriction areas are defined for reasonable pickup/drop-off points and are used to guide the algorithms using landmarks-based heuristics. Experiments are performed on real transportation networks. The results demonstrate the performance of the suggested algorithms and the CPU time and application interest of the restriction areas for pick-up and drop-off points.

Keywords: Dynamic Carpooling, Shortest Path Problem, Synchronized Paths Calculating the Shortest DriversÃ¢â‚¬â„¢ and PassengersÃ¢â‚¬â„¢ Paths

DOI:https://doi.org/10.6025/stj/2024/13/1/14-27

Full_Text PDF 559 KB Download: 15 times

References:

[1] Arnould, G., Khadraoui, D., Armendáriz, M., Burguillo, J. C., Peleteiro, A. (2011). A transport based clearing system for dynamic carpooling business services. In: 11th International IEEE Conference on ITS Telecommunications (ITST) (pp. 527–533).

[2] Artigues, C., Deswarte, Y., Guiochet, J., Huguet, M.-J., Killijian, M.-O., Powell, D., Schettini, F. (2012). Amores: an architecture for mobiquitous resilient systems. In: Proceedings of AppRoaches to MObiquitous Resilience (ARMOR’12), a EDCC workshop.

[3] Barrett, C. L., Jacob, R., Marathe, M. (2000). Formal-Language-Constrained Path Problems. SIAM Journal on Computing, 30(3), 809–837.

[4] Delling, D., Sanders, P., Schultes, D., Wagner, D. (2009). Engineering route planning algorithms. In Algorithmics of Large and Complex Networks (Vol. 5515, pp. 117–139).

[5] Goldberg, A. V., Werneck, R. F. (2005). Computing point-to-point shortest paths from external memory. In: ALENEX/ANALCO (pp. 26–40). SIAM.

[6] Huguet, M.-J., Kirchler, D., Parent, P., Wolfler Calvo, R. (2013). Efficient algorithms for the 2-Way Multi-Modal Shortest Path Problems. In: International Network Optimization Conference (INOC).

[7] Kaufman, E., Smith, R. L. (1993). Fastest paths in time-dependent networks for intelligent vehicle-highway systems applications. IVHS Journal, 1(1), 1–11.

[8] Martins, E. (1984). On a multicriteria shortest path problem. European Journal of Operational Research, 16(2), 236–245.

[9] Nannicini, G., Delling, D., Schultes, D., Liberti, L. (2012). Bidirectional A* search on time-dependent road networks. Networks, 59(2), 240–251.

[10] Sghaier, M., Zgaya, H., Hammadi, S., Tahon, C. (2011). A novel approach based on a distributed dynamic graph modeling set up over a subdivision process to deal with distributed optimized real time carpooling requests. In 14th International IEEE Conference on Intelligent Transportation Systems (ITSC) (pp. 1311–1316).

DLINE Journals portal