A Ride-Sharing Problem with Meeting Points and Return Restrictions

Wenyi Chen, Martijn Mes, Johannes M.J. Schutten, J. Quint

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Ride sharing has been widely acknowledged as an effective solution for reducing travel costs, congestion, and pollution. This paper considers the ride-sharing problem of the scheduled commuter and business traffic within a closed community of companies that agree to share the calendars of their employees. We propose a formulation in the form of a general integer linear program (ILP) for the aforementioned ride-sharing problem,which incorporates return restrictions to satisfy the business needs, as well as meeting points and the option for riders to transfer between drivers. All the instances with 40 and 60 participants and most of the instances with 80 participants can be solved to optimality within a time limit of two hours. Using instances of up to 100 participants, the ILP can be solved with a gap of no more than 1.8% within the time limit. Because of the high computational complexity, we develop a constructive heuristic that is based on the savings concept. This heuristic is also able to combine ride sharing with the use of an external mobility service provider. Our numerical study shows that ride sharing can be an effective way of reducing the number of trips and vehicle miles. Particularly, ride sharing creates more benefits when the participation is high and when the origins and the destinations of the trips are more spatially concentrated. The results show that ride sharing can create up to 31.3% mileage savings and up to 28.7% reduction in the number of cars needed to fulfill employees’ travel schedules. We also illustrate our model using a real-life ride-sharing problem of a Dutch consultancy and research firm.
LanguageEnglish
Number of pages26
JournalTransportation science
DOIs
Publication statusE-pub ahead of print - 30 Jan 2019

Fingerprint

savings
heuristics
travel
employee
Personnel
Industry
commuter
service provider
Computational complexity
Pollution
Railroad cars
driver
traffic
firm
participation
costs
community
Costs
time

Cite this

@article{f4e562213d1140469399f84ae38ff02c,
title = "A Ride-Sharing Problem with Meeting Points and Return Restrictions",
abstract = "Ride sharing has been widely acknowledged as an effective solution for reducing travel costs, congestion, and pollution. This paper considers the ride-sharing problem of the scheduled commuter and business traffic within a closed community of companies that agree to share the calendars of their employees. We propose a formulation in the form of a general integer linear program (ILP) for the aforementioned ride-sharing problem,which incorporates return restrictions to satisfy the business needs, as well as meeting points and the option for riders to transfer between drivers. All the instances with 40 and 60 participants and most of the instances with 80 participants can be solved to optimality within a time limit of two hours. Using instances of up to 100 participants, the ILP can be solved with a gap of no more than 1.8{\%} within the time limit. Because of the high computational complexity, we develop a constructive heuristic that is based on the savings concept. This heuristic is also able to combine ride sharing with the use of an external mobility service provider. Our numerical study shows that ride sharing can be an effective way of reducing the number of trips and vehicle miles. Particularly, ride sharing creates more benefits when the participation is high and when the origins and the destinations of the trips are more spatially concentrated. The results show that ride sharing can create up to 31.3{\%} mileage savings and up to 28.7{\%} reduction in the number of cars needed to fulfill employees’ travel schedules. We also illustrate our model using a real-life ride-sharing problem of a Dutch consultancy and research firm.",
author = "Wenyi Chen and Martijn Mes and Schutten, {Johannes M.J.} and J. Quint",
year = "2019",
month = "1",
day = "30",
doi = "10.1287/trsc.2018.0832",
language = "English",
journal = "Transportation science",
issn = "0041-1655",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

A Ride-Sharing Problem with Meeting Points and Return Restrictions. / Chen, Wenyi; Mes, Martijn; Schutten, Johannes M.J.; Quint, J.

In: Transportation science, 30.01.2019.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A Ride-Sharing Problem with Meeting Points and Return Restrictions

AU - Chen, Wenyi

AU - Mes, Martijn

AU - Schutten, Johannes M.J.

AU - Quint, J.

PY - 2019/1/30

Y1 - 2019/1/30

N2 - Ride sharing has been widely acknowledged as an effective solution for reducing travel costs, congestion, and pollution. This paper considers the ride-sharing problem of the scheduled commuter and business traffic within a closed community of companies that agree to share the calendars of their employees. We propose a formulation in the form of a general integer linear program (ILP) for the aforementioned ride-sharing problem,which incorporates return restrictions to satisfy the business needs, as well as meeting points and the option for riders to transfer between drivers. All the instances with 40 and 60 participants and most of the instances with 80 participants can be solved to optimality within a time limit of two hours. Using instances of up to 100 participants, the ILP can be solved with a gap of no more than 1.8% within the time limit. Because of the high computational complexity, we develop a constructive heuristic that is based on the savings concept. This heuristic is also able to combine ride sharing with the use of an external mobility service provider. Our numerical study shows that ride sharing can be an effective way of reducing the number of trips and vehicle miles. Particularly, ride sharing creates more benefits when the participation is high and when the origins and the destinations of the trips are more spatially concentrated. The results show that ride sharing can create up to 31.3% mileage savings and up to 28.7% reduction in the number of cars needed to fulfill employees’ travel schedules. We also illustrate our model using a real-life ride-sharing problem of a Dutch consultancy and research firm.

AB - Ride sharing has been widely acknowledged as an effective solution for reducing travel costs, congestion, and pollution. This paper considers the ride-sharing problem of the scheduled commuter and business traffic within a closed community of companies that agree to share the calendars of their employees. We propose a formulation in the form of a general integer linear program (ILP) for the aforementioned ride-sharing problem,which incorporates return restrictions to satisfy the business needs, as well as meeting points and the option for riders to transfer between drivers. All the instances with 40 and 60 participants and most of the instances with 80 participants can be solved to optimality within a time limit of two hours. Using instances of up to 100 participants, the ILP can be solved with a gap of no more than 1.8% within the time limit. Because of the high computational complexity, we develop a constructive heuristic that is based on the savings concept. This heuristic is also able to combine ride sharing with the use of an external mobility service provider. Our numerical study shows that ride sharing can be an effective way of reducing the number of trips and vehicle miles. Particularly, ride sharing creates more benefits when the participation is high and when the origins and the destinations of the trips are more spatially concentrated. The results show that ride sharing can create up to 31.3% mileage savings and up to 28.7% reduction in the number of cars needed to fulfill employees’ travel schedules. We also illustrate our model using a real-life ride-sharing problem of a Dutch consultancy and research firm.

U2 - 10.1287/trsc.2018.0832

DO - 10.1287/trsc.2018.0832

M3 - Article

JO - Transportation science

T2 - Transportation science

JF - Transportation science

SN - 0041-1655

ER -