Novel model for integrated demand-responsive transit service considering rail transit schedule

1.   Introduction

In DRT systems, vehicles are assigned to reach all boarding locations and transport passengers to train stations ^[1,2]. In comparison to fixed-route transit services (FRTs), it allows travel instructions involving boarding or alighting locations and service time windows to be given in sparsely populated residential areas using mobile applications, capturing the individual needs of each passenger, while predetermined subway schedules facilitate lower operating costs but higher service levels ^[3,4,5]. Thus, DRT has raised widespread interest among scholars worldwide.

Travel orders of passengers serve as an input to design DRT systems. Generally, passengers prefer to select their metro schedules by themselves, except for boarding or alighting locations, boarding time windows, etc. Thus, individual subway schedules of passengers will affect the route building process. Without loss of generality, these are only related to passenger wait time during transfer travels and are a critical component of the total travel time. They affect the design process of feeder bus routes, thus causing changes to the ride time. Clearly, the total travel time of all passengers could be reduced due to synchronous transfers between shuttle and feeder buses. Thus, it is significant to identify the optimal relationship of synchronous rail transit coordination and feeder bus routes, and then wait time and ride time can be traded off.

Another important observation is that in most studies, locations of demand points are assumed as pickup locations. In reality, at the demand point, passengers may choose a nearby stop to board or alight the bus, and their behavior is determined by routes that have more available seats and shorter ride times. In the case of demand points being assigned, it is also critical to select optimal stops as pick-up locations along candidate routes for the DRT system design ^[6,7]. Thus, incorporating stop selection into the DRT route design is currently considered to be an efficient method to enhance the operation levels of transportation providers.

The aim of this paper is to propose a mixed integer mathematical programming model that considers the DRT route design with stop selection and railway transit schedules to promote service levels. Its seamless integration offers the best potential for transit authorities to trade off between them to design and refine a globally optimal DRT network. This research focused on the following aspects: 1) coordinating the DRT route design process and stop selection, while incorporating synchronous transfers between shuttle and feeder buses; 2) developing a new and efficient two-stage ant colony algorithm (ACO) to achieve meta-optimal solutions of the presented model, since the mixed-integer linear programming (MILP) belongs to an NP-hard problem. In addition, in order to verify the application and feasibility of the developed methodology, a case study was conducted.

This paper has the following structure: Following the introduction, Section 2 presents the relevant literature of DRT; Section 3 details the problem of the proposed DRT and its mathematical model; Section 4 demonstrates a new two-stage ACO; Section 5 demonstrates a case analysis to further verify our study; remarks and future study recommendations are summarized in Section 6.

2.   Related work

DRT integrates vehicle routing problems (VRPs) and pickup and delivery problems (PDPs) ^[7,8], and vehicles are allocated to pick up or drop off passengers at various locations ^[9,10,11]. However, significant differences amongst them commonly lead to more problems and difficulty in DRT than in VRPs and PDPs. Obviously, DRT has a better performance than FRTs in areas of low population size ^[11,12]. In recent years, multiple studies have taken place on DRT and are generally grouped into two types: analytical and network approaches ^[13,14].

The optimal relationship amongst route design, departure frequencies and stop locations in service areas has been studied using the analytic approach, and street shape geometry and the demand distribution of these areas are also incorporated. Wirasinghe ^[15] initially proposed an analytical approach for the peak demand design of the Calgary DRT system. Then, stop location influences the DRT route design, which was studied by Kuah and Perl ^[16,17]. The DRT model was further extended by Chowdhury with multiple coordinated routes at transfer stops ^[18]. However, due to the significant limitations of two parameters (i.e., road network structure and spatial-temporal distribution of demand points), this analytic approach has rarely been employed to address DRT ^[14].

The service of assigning bus routes to reach boarding locations is demonstrated using the network approach, with each location concentrated at a node, and the connections between these nodes are used to denote the segments of various bus routes. For the DRT model, two conventional network approaches are available: (ⅰ) the design optimization model of the route network developed by Kuah et al. ^[17], which was further extended by Kuan et al. ^[14], Chang et al. ^[19], Wei et al. ^[20] and Mohaymany et al. ^[21]; and (ⅱ) the heuristic generation algorithm of the route network developed by Shrivastava et al. ^[22], which was further extended by Shrivastava et al. ^[23,24,25]. Chen et al. ^[26] established a two-stage model in order to deal with the DRT. Another model, by Deng et al. ^[27], was developed to address the multi-objective M-to-M DRT. A bi-level model by Pan et al. ^[28] could deal with the largest passenger number in the DRT system and the optimal operational expenditure for transit operators. A bi-level model was introduced by Yu et al. ^[29] to improve flexible feeder-dedicated transit between train stations and bus stops. A multi-objective model was constructed by Sun et al. ^[30] in order to establish coordination between rail and bus lines. Based on a robust MIP model, Yan et al. ^[31] minimized the overall sum of operator costs as well as their variability through a weighting process of different cost components. Multiple time windows of passengers and their satisfaction were included in the MIP model for DRT by Sun et al. ^[32].

Even though various DRT models have been studied in the existing literature, two critical issues still need further study:

1) Stop selection and rail transit schedule have rarely been studied. In this case, the integrated operation of stop selection, DRT routes and schedules that consider synchronous transfers between the shuttle and feeder buses are ignored in order to optimize the total vehicle ride time and passenger wait time ^[34,35,36].

2) DRT, as an extension of VRPs and PDPs, ought to be solved by an effective heuristic ^[32,35,36].

3.   Methodology

3.1.   Problem description

This study aims to develop a DRT model that considers stop selection and rail transit schedule. DRT routes were designed, which started at bus depots and ended at rail transit stations, and vehicles were assigned to selected stops with assignment of all demand points. Passengers used a mobile application to place some travel orders regarding boarding or alighting locations, boarding time windows and predetermined subway schedules. Based on the open source GIS tool, actual travel distances and time matrices between these depots, stations, demand points and railway stations were calculated. With respect to the DRT model design, a MILP model was developed to investigate the optimal correlation of design efficiency with stop selection, feeder bus routes and schedules, which also took synchronous transfers between the shuttle and feeder buses into account.

Figure 1 illustrates the research framework of the suggested methodology. In terms of the objective, a feeder bus routing and schedule was achieved which optimizes weighted passenger walking distance, vehicle ride time from the pickup site to the train station and passenger wait time during a transfer ride.

3.2.   Model development

3.2.1.   Notation

Table 1 shows notations involved in the model in order to simplify and clarify the model.

3.2.2.   Mathematical model

The objective of this model, given by Eq (1), is to minimize weighted passenger walking distance, vehicle ride time and the wait time.

Through Constraints (2)–(4), each passenger location must be only covered by a vehicle. Through Constraints (5)–(8), eventually, each vehicle leaves from a depot at first and finally arrives at the rail transit station. Through Constraint (9), each demand point cannot be attended by different vehicles simultaneously. Constraint (10) is used to eliminate sub-tours along vehicle routes. Through Constraints (11) and (12), the time required for the vehicle to arrive from the last node to the next node is calculated. Through Constraint (13), a feeder bus is guaranteed to arrive at the demand point within the boarding window of time. Through Constraints (14) and (15), the number of passengers who have boarded feeder buses is determined after the vehicle reaches demand points. Through Constraint (16), the number of passengers boarding a vehicle at each pickup location cannot exceed the vehicle capacity. Through Constraints (17) and (18), each vehicle can have the overall distance of travel and ride time that meet its limits. Through Constraint (19), the same subway timetable at the rail transit station was selected by the passengers who were loaded by a vehicle at the various demand points.

4.   A two-stage ACO-based heuristic algorithm

A two-stage ACO-based heuristic algorithm ^[33,34,36] was established to compare with the presented model. The algorithm framework is given in Figure 2. In Stage I, the ACO was used to generate DRT routes visiting demand points based on their pre-defined time windows of service. In Stage II, a dynamic programming (DP) algorithm was used to select optimal stops for each demand point in each route.

4.1.   ACO of first stage

In Stage I, passenger locations were assigned to DRT routes considering spatial and pre-defined time window constraints. Thus, an ACO was used wherein the ants were positioned at the demand point with the earliest service time window, and then they visited the entire demand set in order to allocate demand points to bus routes. The process of the ACO algorithm was divided into the following steps:

Step 1: Algorithm initialization, including ① number of ants (i.e., L), NCmax and ② $\tau_{i, i'}(0) = \mathrm{C}$ and $\Delta \tau_{i \ i^{\prime}}(0) = 0$. Let t = 0.

Step 2: In the t^th iteration, an ant l = 1: L randomly generates K DRT routes that visit all demand points according to a random rule of probability.

Step 2.1: First, an ant l is randomly placed at the vertex of a demand point i.

Step 2.2: When the ant l generates a feasible solution for the DRT route k for visiting the demand point i, if the next set allowed of the visited demand point should be found to satisfy $allowed = \left\{\left.i\right| \mathop \cap \limits_{\forall i \in I} \left[l_{i}, e_{i}\right] \neq \varnothing\right. \ and \ \left.\sum\limits_{\forall i \in I} z_{i j}^{k} \cdot q_{i} \leq Q\right\}$ , the ant prepares to construct a new DRT route k = k + 1 to cover these unvisited demand points; otherwise, go to Step 2.4.

Step 2.3: If a random q ranging within [0, 1] is less than $q_{0} \in(0, 1]$, the pseudo-random proportion rule of Eq (20) is used to obtain the next demand point visited by the DRT route after leaving the current location; otherwise, the probability distribution of Eq (21) is used to find an ant path.

where α and β denote the importance of pheromones and heuristic information, and heuristic information $\eta_{i, i'} = 1 /\left(d_{i, i'}+0.01\right)$ denotes the cost of DRT route k visiting adjacent demand points i and i'.

Step 2.4: When all demand points have been visited by ants, output feasible solutions; otherwise, return to Step 2.2.

Step 3: According to the DP algorithm in Step 2, assignment of all passenger locations to the assigned stops is obtained to calculate the objective function.

Step 4: Based on Eqs (21) and (22), the information on all routes is updated globally and locally.

where $\rho \in(0, 1)$ denotes the pheromone volatility coefficient, $\xi \in(0, 1)$ and Q are normal parameters, and $f^{n n}$ and $f^{b s}$ denote the optimal solution value currently found by the nearest neighbor method and the ACO.

Step 5: Let t = t + 1; if t < = NC_max, return to Step 2; otherwise, the algorithm is terminated.

4.2.   DP algorithm of the second stage

In the first stage, the order in which the DRT route visits the demand points can be determined. If the stops assigned for each demand point can be determined, the order in which the DRT route visits the stops can be confirmed. Obviously, this problem involves a multi-stage decision-making process of the shortest route problem. For the sequence of demand points visited by a certain connecting line K, the starting and arrival points of the line and the step-by-step determination of the candidate location of the next demand point can be directly solved using the backward DP algorithm. The calculation process of the sequence of $n_{k}$ demand points $\left(i_{1}, i_{2}, \ldots, i_{n_{k}}\right)$ visited by the DRT route k can be described as follows: The DRT route starts from the depot $\forall m \in D$ at first and finally arrives at the rail transit station $\forall m \in M_{s}$. After the candidate locations of the previous demand point $i_{i}$, the candidate stop of the next demand point $i_{i+1}$ is determined step by step. The process of solving this problem by the DP algorithm can be described as follows.

Step 1: In the stage 0, let l = 0 and $f_{0}^{1}(m) = 0$.

Step 2: In the stage l, the set of feasible candidate stops $J_{i_{l}}$ of demand point i_l is calculated based on the maximum walking distance of passengers. According to $f_l^1\left({{i_l}} \right) = \mathop {\min }\limits_{\forall j \in {J_{{i_l}}}} \left[{f_{l + 1}^1\left({{i_{l + 1}}} \right) + {t_{j{u_{l + 1}}\left({{i_{l + 1}}} \right)}}} \right]$, the optimal stop selection strategy $u_{l}\left(i_{l}\right)$ is determined for the demand point $i_{l}$ by considering its time window, i.e., $x_{l, u_{l}\left(i_{l}\right)} = 1$.

Step 3: Let $l = l+1$. If $l = =n_{k}$, the algorithm is terminated; otherwise, return to Step 2.

5.   Case study

5.1.   Example description

Based on the geospatial distribution of five bus depots (D1–D5), 42 candidate stops, 25 demand points (S1–S42) and one rail transit station (M), a case study was conducted using the model. It aims to develop a design for the feeder bus system in Chongqing, China. Through the mobile application data exploration, the demand data were acquired, including the passenger number, preferred boarding time windows of passengers and the selected subway schedule at the demand points, as listed in Table 2. In the case study, the selected main model input parameters are presented as follows.

• Number of vehicles: 3;

• Vehicle capacity (Q, people): 35;

• Maximum (${D_{\min }}$, km) and minimum (${D_{\max }}$, km) mileage of each vehicle: 4 and 30;

• Maximum travel time of each vehicle (${T_{\max }}$, min): 30;

• Passenger walking time (${T_w}$, min) from alighting locations at the rail transit station to the metro station: 3;

• Parameters of algorithm are as follows: NCmax = 500, $L = 40, Q = 200, q_{0} = 0.9,$ $\alpha = 1, \beta = 2$ and $\rho = \xi = 0.1$.

5.2.   Results

The proposed model can solve the problem in three dimensions, i.e., assigning all demand points to selected stops, considering user-preferred windows for bus routing and service time. Table 3 summarizes the assignment results, including scheduling stop selection and service time window at every demand point. Table 4 presents DRT routes and their preferred service time windows. By taking DRT route 1 as an example, P7 and P12 are assigned to S3, P13 and P14 are assigned to S4, and P24 and P25 are assigned to S34 and S22 respectively. Due to the uncertainty of the expected subway schedule of six demand points, the vehicle must arrive at the rail transit station during time period (6:30, 6:40). Therefore, feasible time windows for this vehicle to depart, visit stops and arrive at the rail transit station were (6:5, 6:15), (6:13, 6:23), (6:18, 6:28), (6:23, 6:33), (6:26, 6:36) and (6:30, 6:40). Figure 3 shows the routing and scheduling plans of all DRT vehicles.

In addition, the presented DRT model has distinctive characteristics in comparison to the conventional ones. Figure 4 shows differences between our model and a conventional rail transit model without synchronous coordination (DRTNSCRT). Compared with the DRTNSCRT, the DRT had a slight increase of 0.4% in total travel time in the case of passengers' soft railway schedule constraints, while it also was increased by 4.9% in their hard constraints. This can be explained by the fact that the expected arrival time of passengers at rail transit stations may result in vehicles failing to access all demand points based on the shortest route or minimum travel time, thus causing an increase in the total travel time. The tighter the time window, the more restrictions are placed on route construction, thus increasing the total travel time. Although the objective function value of this model was larger than that of the traditional model, it is in line with the individual travel needs of passengers, and the result and intuitive analysis agree well with each other.

5.3.   Sensitivity analysis

Table 5 shows a performance comparison of the model depending on a differing number of feeder buses. With the increasing number, the number of demand points decreased, which are to be covered by each vehicle leaving from the depot at first and arriving at the rail transit station at last, while invalid travel distance and time increased. However, the vehicle ride time also decreased. This shows that the deviation of the proposed algorithm solution from Cplex was within 7%, but the calculation time was significantly lowered, indicating that the proposed algorithm was effective and achievable in terms of solving problems. Figure 5 shows the variations in total travel time of the presented model from the DRTNSCRT models by considering three scenarios of 3, 4 and 5 vehicles, respectively, and the results were in good agreement with those of Table 5.

6.   Conclusions

In this study, a novel optimization method was developed for DRT considering stop selection and rail transit schedule. The relationship between passenger walking distance, vehicle ride time from pickup locations to rail transit stations and passenger wait time at transfer points was analyzed. In comparison with existing studies, the proposed method 1) considered synchronous transfers between the shuttle and feeder buses in the DRT route design process and stop selection and 2) included a two-stage ACO for efficient model solutions. The results show that the developed model was an effective method to generate passenger, route and operation plans.

It should be noted that two key assumptions were made in this study, i.e., (i) passenger boarding locations (demand points) are taken as bus stops, and (ii) the origin-destination table remains stable. The integrated allocation of demand points was ignored for selected passenger boarding locations and time-varying demand. Thus, it is a worthwhile topic for further research to extend the model by simultaneously selecting optimal stops along candidate routes and assigning passengers to them with time-dependent origin-destination.

Acknowledgments

We acknowledge all the people who have contributed to this paper in some manner. This paper is funded by the Fundamental Research Funds for the Central Universities of the Civil Aviation University of China (3122020079).

Conflicts of interest

The authors declare that they have no conflicts of interest to report regarding the present study.