In major metropolitan areas, ride-sharing systems can help reduce traffic congestion and increase the transportation system’s efficiency. In this paper, we propose a Branch-and-Price based approach for solving the ride-share routing problem with flexible pickup and drop-off points. We assume a ride-sharing system where drivers have their own origins and destinations, where all the drivers’ and passengers’ information is known beforehand, and all the problem data information is static and deterministic. We assume that drivers can pick up or drop off passengers from or to flexible meeting points that are within a passenger’s walking time limit from their origin or destination and are determined on a continuous plane. We formulate a mixed integer nonlinear model for routing and selecting pickup and drop-off points. Our solution approach decomposes this problem in two: selecting pickup and drop-off points and a rideshare routing problem. We develop an efficient algorithm to select the best pickup and drop-off points and show computationally that it is more efficient at finding pickup and drop-off points than considering a fixed set of discrete meeting points. To evaluate the performance of our approach, we perform numerical experiments on a San Francisco Taxicab dataset. Results show that our approach is efficient, solving instances with up to 600 points within 31 CPU minutes. For these datasets, incorporating flexible pickup and drop-off points can reduce the total vehicle travel time of the rideshare system by 4% on average.

中文翻译：

---

灵活的上车和下车点的拼车路线问题

在主要大都市地区，拼车系统可以帮助减少交通拥堵并提高交通系统的效率。在本文中，我们提出了一种基于 Branch-and-Price 的方法，用于解决具有灵活上下车点的拼车路线问题。我们假设一个拼车系统，其中驾驶员有自己的出发地和目的地，所有驾驶员和乘客的信息都是事先知道的，并且所有问题数据信息都是静态和确定性的。我们假设驾驶员可以在乘客从出发地或目的地出发的步行时间限制内，并在连续的飞机上确定灵活的集合点接送乘客。我们制定了一个混合整数非线性模型，用于路由和选择接送点。我们的解决方案将这个问题分为两部分：选择上车和下车点以及拼车路线问题。我们开发了一种有效的算法来选择最佳的接送点，并通过计算表明，与考虑一组固定的离散交汇点相比，它在寻找接送点方面更有效。为了评估我们方法的性能，我们在 San Francisco Taxicab 数据集上进行了数值实验。结果表明，我们的方法非常高效，可以在 31 个 CPU 分钟内解决多达 600 个点的实例。对于这些数据集，结合灵活的上车和下车点可以将拼车系统的总车辆行驶时间平均减少 4%。