A column generation approach for a dynamic ridesharing problem

ABSTRACT

Recent advances in GPS and telecommunications technologies have made ridesharing a widespread practice around the world. By matching drivers and passengers with near-distance destinations and similar time schedules, ridesharing saves individuals travel costs by enabling them to share vehicles. It is also an effective way to reduce traffic congestion and greenhouse gas emissions. A ridesharing problem can be modeled as a dial-a-ride problem with time windows. This study looks at a solution to the dynamic ridesharing problem in which passengers share travel costs at the same ratio. We formulate the problem as a mixed-integer programming model and suggest a column generation approach. As the system’s status is updated in real time, riders and drivers are matched, and new paths are created via column generation. Computational experiments show that our approach is superior to an existing algorithm when it is tested on instances of various sizes.

KEYWORDS:

• Ridesharing
• dynamic dial-a-ride problems
• mixed-integer programming
• column generation

Acknowledgement

The authors are grateful for the valuable comments from the editor and anonymous reviewers. This research was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (grant number NRF-2019R1A2C2084616).

Disclosure statement

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

Notes

1. https://www.fico.com/en/products/fico-xpress-optimization

2. https://its.go.kr/itsinfo/snl.do

Additional information

Funding

This research was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning [grant number NRF-2019R1A2C2084616].