The flex-route transit planning problem with meeting points
研究了带会合点的灵活路线公交规划问题，乘客可在指定点或替代会合点上下车，通过优化车辆路线和节点选择来最小化车辆行驶成本和乘客步行成本，并设计了精确求解算法。
As an innovative alternative to ridesharing, flex-route transit (FRT) is widely acknowledged as a promising solution, especially in scenarios in which transportation demand is low or dispersed. This paper addresses the FRT planning problem with meeting points (FRTPP-MP), which conceptualizes each passenger’s pick-up/drop-off request as a set of points (i.e., a cluster) containing the designated pick-up/drop-off point and alternative points (i.e., meeting points), stipulating that only one point in each cluster needs to be visited to fulfill the request. The aim is to minimize both the travel cost of vehicles and the walking cost of passengers by simultaneously optimizing the routes of vehicles and the selection of nodes within their respective clusters. We formulate the FRTPP-MP as a mixed-integer programming (MIP) model and develop an exact branch-and-price (BAP) algorithm to solve it. To tackle the specific challenges of cluster visit restrictions in the pricing problem, we design a tailored bidirectional label correction algorithm (TBLCA), which is further enhanced by a novel acceleration strategy. Extensive computational experiments are conducted based on benchmark instances generated from a real-life FRT system. The numerical results highlight our solution algorithm’s satisfactory performance. Furthermore, managerial insights from a sensitivity analysis suggest that introducing meeting points can substantially reduce the costs associated with FRT.