Demand-responsive customized bus (CB) services, an emerging mode of public transportation, offer flexible routing for passengers with similar travel preferences. However, existing route planning algorithms for CB services do not fully utilize the extensive route data generated during daily operations. Owing to the large data size and variability in passenger travel demands, directly using all historical route planning results makes it difficult to extract effective information, which reduces algorithm efficiency. Common similarity analysis methods include the Jaccard and mean squared error (MSE) algorithms. The Jaccard algorithm measures similarity by calculating the ratio of the intersection to the union of two sets of stops, but it considers only the presence of bus stops and overlooks differences in passenger demand, potentially resulting in routes that risk vehicle overload. The common MSE algorithm calculates the squared differences in passenger numbers at each stop between historical and current data, offering a highly accurate reflection of data discrepancies. However, these methods do not consider the practical feasibility of historical routes, such as vehicle capacity and passenger waiting times.

To address these issues, this study proposes a modified MSE algorithm based on Lagrangian relaxation that incorporates penalty terms for vehicle capacity and time window constraints into the objective function. By comparing historical data with current passenger demand, the modified MSE identifies similar and feasible historical routes for route planning. This approach comprehensively accounts for operational constraints to ensure that the selected routes are similar and feasible. Lagrangian relaxation is also applied in the iterative process of the adaptive large neighborhood search (ALNS) algorithm to ensure that the generated route plans meet the capacity and time requirements. In addition, a mathematical model based on historical route similarity is established using a sequence similarity matching algorithm to evaluate the similarity between historical and current routes. Stops are treated as elements in sequences, with similarity measured by the longest common subsequence of stops appearing in the same order. For multiple historical routes, the similarity between a current route and the historical set is defined as the maximum sequence similarity across all historical routes. To accelerate the model's solution process, a modified ALNS is developed, which constructs initial solutions based on historical data and integrates novel removal and insertion operators that consider route similarity to achieve better solutions. To prevent premature convergence, ALNS incorporates simulated annealing, accepts inferior solutions in the early stages and gradually limits its acceptance as iterations progress. ALNS terminates after a fixed number of iterations or when no improvement is observed. Additionally, a path-relinking process improves efficiency by fixing routes that exactly match historical results and carry equal or more passengers, thereby excluding them from further iterations.

The proposed approach leveraged high-quality historical data to generate highly competitive results. Case studies using real travel data from Nanjing demonstrated that the modified ALNS algorithm, incorporating route similarity, outperformed the common ALNS in terms of effectiveness, convergence speed, and route similarity. By using the modified MSE algorithm that accounted for historical scenarios, the proposed algorithm improved route feasibility, stability, and quality compared with common similarity analysis methods. Moreover, selecting historical data from scenarios that closely matched the current situation helped ensure high-quality routing. Increasing the time window length reduced the total travel cost while maintaining a consistent level of route similarity. As the weight of the similarity cost parameter increased, the similarity between current and historical routes steadily rose until reaching a maximum value of one, whereas the total travel cost gradually decreased, highlighting the algorithm's ability to balance cost efficiency and route consistency effectively.

Using historical route data that are similar to those used in current scenarios improves the quality of CB route planning solutions. This study not only advances research on CB route planning but also identifies gaps that serve as potential directions for future research. Exploring heterogeneous fleets, accounting for uncertain travel times, and incorporating additional heuristic techniques may further enhance the operational efficiency and practical applicability of the results.The research results of this paper can provide a reference for solving the CB line planning problem by using historical information.