An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization
研究了一种新的静态拨号乘车问题，目标是同时最小化乘客的乘车时间和等待时间，并提出了自适应大邻域搜索算法和动态规划算法，测试表明该算法能有效解决大规模实例，有助于平衡个人交通、盈利能力和交通污染。
Abstract The paper investigates the static dial-a-ride problem with ride and waiting time minimization. This is a new problem setting of significant practical relevance because several ride-sharing providers launched in recent years in large European cities. In contrast to the standard dial-a-ride problem, these providers focus on the general public. Therefore, they are amongst others in competition with taxis and private cars, which makes a more customer-oriented objective necessary. We present an adaptive large neighbourhood search (ALNS) as well as a dynamic programming algorithm (DP), which are tested in comprehensive computational studies. Although the DP can only be used for a single tour and, due to the computational effort, as a restricted version or for small instances, the ALNS also works efficiently for larger instances. The results indicate that ride-sharing proposals may help to solve the trade-off between individual transport, profitability of the provider, and reduction of traffic and pollution.