Publication Cover
Transportation Letters
The International Journal of Transportation Research
Volume 15, 2023 - Issue 8
207
Views
0
CrossRef citations to date
0
Altmetric
Research Article

The ridesharing problem without predetermined drivers and riders: formulation and heuristic

, ORCID Icon, &
 

ABSTRACT

We consider a ridesharing service in which no driver and rider’s roles are pre-determined, but left to decide by the system to further reduce costs compared to the typical version with preassigned roles. Travelers are motivated to participate in the service by saving individual transportation costs and accept its rules. We first formally define it as a generalized ridesharing optimization problem (RSP), propose its transformation into a single-depot multiple traveling salesman problem with pickup and delivery constraints (SDMTSP-PD) and provide its mixed-integer program (MIP) formulation. We then develop a polynomial-time solution method based on optimal pair matching among participants, improved by a construction insertion-based heuristic to obtain approximate solutions to the SDMTSP-PD. Experiments show that this approach could solve the problem very fast and provide near-optimal solutions and that the proposed RSP model provides substantial system-wide travel cost saving (25%+) and vehicle-trip saving (50%) compared to the non-ridesharing system and perform better than companion services with preassigned roles (P-RSP).

Acknowledgments

The research reported in this paper was partially supported by a Dissertation Fellowship of Texas A&M University.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. The data sets can be downloaded from http://www.diku.dk/~sropke/

Additional information

Funding

The author(s) reported there is no funding associated with the work featured in this article.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.