# Optimizing Centralized Dispatching of Flexible Feeder Transit considering Transfer Coordination with Regular Public Transit

Authors: Yu-Qiong Wang; Shun-Ping Jia; Run-Bin Wei; Min Wang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Optimizing centralized dispatching of flexible feeder transit to provide transport and transfer services is important and theoretically challenging for real-world applications. Considering transfer coordination with regular public transit, a multiobjective optimization model that can output an operation plan containing vehicle routes and a timetable for a bus fleet is proposed. By establishing constraints for parameters such as maximum acceptable advance or delay time of transfer, rated passenger capacity, and maximum travel time of a single trip, the proposed model attempts to maximize the successful response ratio, minimize the passengers’ average time costs, and minimize the operating costs of a single passenger. A genetic algorithm was designed to solve the optimal solution, and computational experiments were conducted in a residential area in Beijing. Results reveal that the proposed model and algorithm can be applied in the operation of flexible feeder transit. Moreover, compared with the distributed dispatching method, the value of the optimal objective function in the proposed model was improved by 26%. Although the successful response ratio showed a 29.3% increase and the average passenger time cost showed a small drop, the operating costs per passenger were reduced by 30.7%. The different weight coefficients of the subobjective function and maximum acceptable advance or delay time of transfer could result in different optimal operation plans. Essentially, the optimization procedures for the successful response ratio and the operating costs are in the same direction, whereas the one for the passenger’ cost is in the opposite direction. However, operators should select appropriate values to optimize operation plans.


---

## Body

## 1. Introduction

### 1.1. Literature and Background Survey

In the past, providing door-to-door services (referred to as demand-responsive transport (DRT), Dial-a-Ride Transit (DART), and flexible transport service (FTS) [1–3]) has been trialed in many cities around the world. The concept of a flexible bus service system was originally proposed by Flusberg in 1976 [4]. In addition, Koffman [5] classified flexible bus service systems for the first time in terms of line offsets, station offsets, demand response shuttles, demand response stations, section flexible buses, and regional flexible buses services. The dispatching and operation planning of door-to-door services is receiving significant research attention. For example, Parragh et al. [6] established a heuristic algorithm to make vehicle route selections for DART for minimizing total routing costs, and Muelas et al. [7] considered the waiting time constraints of passengers and designed a variable neighborhood search algorithm to find optimal vehicle routes for DART. To solve large-scale problems of dispatching of DART, Muelas et al. [8] proposed a distributed algorithm and proved the effectiveness of this algorithm. Moreover, Molenbruch et al. [9] and Oscar et al. [10] studied DART services for special travel demands, e.g., medical users with wheelchairs. Problems related to actual dispatching and new technology have been analyzed and considered in many studies, e.g., the time-varying speed of vehicles on the road network (Schilde et al. [11], Wei et al. [12]), flexing service schedules for demand-adaptive hybrid transit (Frei et al. [13]), autonomous vehicles (Jager et al. [14]), and roundtrip car-sharing systems (Jorge et al. [15]).Because of the inefficiency of travel with regular public transport, with the development of railway systems, car-hailing services, and other diversified travel modes, the passenger volume of regular public transport in many cities in China has been progressively declining year after year. Taking Beijing as an example, the passenger volume of regular public transport in 2018 was 3.19 billion compared with 5.15 billion in 2012 [16]. To improve the travel efficiency of regular public transport systems, the connection between the lines of different bus-route ranks is an urgent problem to solve. Sivakumaran et al. [17] demonstrated that when the feeder and main buses are coordinated, passenger cost reduction is often greater than the increase in connecting operation cost, which reduces costs for both passengers and bus operators. Yu et al. [18] tailored the FTS for people traveling from a fixed rail station to their final work destinations and from the latter to the former, and a bilevel nonlinear mixed-integer programming model is constructed to tackle the flexible feeder transit service design problem (FFTS). Relative to dispatching and operation plans of FFTS considering connections with traditional bus lines, Li et al. [19] optimized the collection points and vehicle routes to minimize the access cost of passengers and the operation cost. Guo et al. [20] designed an exact ε-constraint method to solve the FFTS design problem and discussed the influence of maximum walk time of passengers and route length constraint. Jaw et al. [21] constructed vehicle routes and schedules with predetermined demand stations and timetables, which impose great restrictions on feeder plans. Pillac et al. [22] defined the concept of dynamic routes, solved the vehicle dynamic path problem, and obtained the optimal route. Lee et al. [23] relaxed the restriction of alighting stations and allowed vehicles to drop passengers off at an alternative transit station. Lu et al. [24] considered double-time window assurance and group travel. Alonso-Mora et al. [25] focused on dynamic high-capacity carpooling and designed many-to-one, flexible bus demand response strategies based on the vehicle-demand analysis. Sun et al. [26] studied multiple flexible sites corresponding to multiple target sites (i.e., the many-to-many pattern).Most recent studies [6–13, 23, 24, 26] have focused on distributed dispatching of door-to-door services, making the vehicle route and timetable of each bus run serial number; however, the optimization of a centralized dispatching model considers the operation plan of a bus fleet, which allows a single feeder vehicle to execute several bus run serial numbers. A literature review has shown that the existing distributed dispatching model assumed that a flexible transit system could provide service to all passengers. Based on this assumption, many studies [6–10, 23] have attempted to minimize the operation costs in terms of operation time and distance, and one study [9] attempted to minimize the total passenger ride time. In addition, some studies [24, 26] considered the objectives of the operating costs and passengers in terms of travel time and disutility of delay. However, in practice, it is not economical to provide service to all passengers because of the spatiotemporal dispersion of passenger travel.In this paper, a multiobjective optimization model is presented to optimize the centralized dispatching schemes for flexible feeder transit systems considering time coordination with regular public transit. The objective of passengers’ interests involves minimizing the average time costs of successfully reserved passengers, and the objective of transit operators involves minimizing the operating costs of a single passenger. In addition, maximization of the successful response ratio is considered an objective of both passengers and operators. Then, a genetic algorithm (GA) is designed to implement the model.


### 1.2. Contributions

A multiobjective optimization model for the centralized dispatching of a flexible feeder transit system is proposed. The centralized dispatching method can reduce fleet size and increase the resource utilization rate compared with distributed dispatching methods.The assumption that flexible transit systems must provide service to all passengers is rejected; at the same time, the objectives of maximizing the successful response ratio are considered.The effect of passenger experience in terms of maximum acceptable advance or delay time of transfer on the model is presented.


### 1.3. Paper Organization

The remainder of this paper is organized as follows. Section2 presents the problem description. The optimization model for the centralized dispatching of flexible feeder transit is proposed in Section 3. Then, the GA is described in Section 4. In Section 5, several experiments performed to prove the rationality and feasibility of the proposed model and algorithm are discussed, followed by sensitivity analyses of the weight coefficient of the subobjective function and maximum acceptable advance or delay time of transfer. Finally, Section 6 concludes the paper and discusses future research directions.


## 1.1. Literature and Background Survey

In the past, providing door-to-door services (referred to as demand-responsive transport (DRT), Dial-a-Ride Transit (DART), and flexible transport service (FTS) [1–3]) has been trialed in many cities around the world. The concept of a flexible bus service system was originally proposed by Flusberg in 1976 [4]. In addition, Koffman [5] classified flexible bus service systems for the first time in terms of line offsets, station offsets, demand response shuttles, demand response stations, section flexible buses, and regional flexible buses services. The dispatching and operation planning of door-to-door services is receiving significant research attention. For example, Parragh et al. [6] established a heuristic algorithm to make vehicle route selections for DART for minimizing total routing costs, and Muelas et al. [7] considered the waiting time constraints of passengers and designed a variable neighborhood search algorithm to find optimal vehicle routes for DART. To solve large-scale problems of dispatching of DART, Muelas et al. [8] proposed a distributed algorithm and proved the effectiveness of this algorithm. Moreover, Molenbruch et al. [9] and Oscar et al. [10] studied DART services for special travel demands, e.g., medical users with wheelchairs. Problems related to actual dispatching and new technology have been analyzed and considered in many studies, e.g., the time-varying speed of vehicles on the road network (Schilde et al. [11], Wei et al. [12]), flexing service schedules for demand-adaptive hybrid transit (Frei et al. [13]), autonomous vehicles (Jager et al. [14]), and roundtrip car-sharing systems (Jorge et al. [15]).Because of the inefficiency of travel with regular public transport, with the development of railway systems, car-hailing services, and other diversified travel modes, the passenger volume of regular public transport in many cities in China has been progressively declining year after year. Taking Beijing as an example, the passenger volume of regular public transport in 2018 was 3.19 billion compared with 5.15 billion in 2012 [16]. To improve the travel efficiency of regular public transport systems, the connection between the lines of different bus-route ranks is an urgent problem to solve. Sivakumaran et al. [17] demonstrated that when the feeder and main buses are coordinated, passenger cost reduction is often greater than the increase in connecting operation cost, which reduces costs for both passengers and bus operators. Yu et al. [18] tailored the FTS for people traveling from a fixed rail station to their final work destinations and from the latter to the former, and a bilevel nonlinear mixed-integer programming model is constructed to tackle the flexible feeder transit service design problem (FFTS). Relative to dispatching and operation plans of FFTS considering connections with traditional bus lines, Li et al. [19] optimized the collection points and vehicle routes to minimize the access cost of passengers and the operation cost. Guo et al. [20] designed an exact ε-constraint method to solve the FFTS design problem and discussed the influence of maximum walk time of passengers and route length constraint. Jaw et al. [21] constructed vehicle routes and schedules with predetermined demand stations and timetables, which impose great restrictions on feeder plans. Pillac et al. [22] defined the concept of dynamic routes, solved the vehicle dynamic path problem, and obtained the optimal route. Lee et al. [23] relaxed the restriction of alighting stations and allowed vehicles to drop passengers off at an alternative transit station. Lu et al. [24] considered double-time window assurance and group travel. Alonso-Mora et al. [25] focused on dynamic high-capacity carpooling and designed many-to-one, flexible bus demand response strategies based on the vehicle-demand analysis. Sun et al. [26] studied multiple flexible sites corresponding to multiple target sites (i.e., the many-to-many pattern).Most recent studies [6–13, 23, 24, 26] have focused on distributed dispatching of door-to-door services, making the vehicle route and timetable of each bus run serial number; however, the optimization of a centralized dispatching model considers the operation plan of a bus fleet, which allows a single feeder vehicle to execute several bus run serial numbers. A literature review has shown that the existing distributed dispatching model assumed that a flexible transit system could provide service to all passengers. Based on this assumption, many studies [6–10, 23] have attempted to minimize the operation costs in terms of operation time and distance, and one study [9] attempted to minimize the total passenger ride time. In addition, some studies [24, 26] considered the objectives of the operating costs and passengers in terms of travel time and disutility of delay. However, in practice, it is not economical to provide service to all passengers because of the spatiotemporal dispersion of passenger travel.In this paper, a multiobjective optimization model is presented to optimize the centralized dispatching schemes for flexible feeder transit systems considering time coordination with regular public transit. The objective of passengers’ interests involves minimizing the average time costs of successfully reserved passengers, and the objective of transit operators involves minimizing the operating costs of a single passenger. In addition, maximization of the successful response ratio is considered an objective of both passengers and operators. Then, a genetic algorithm (GA) is designed to implement the model.


## 1.2. Contributions

A multiobjective optimization model for the centralized dispatching of a flexible feeder transit system is proposed. The centralized dispatching method can reduce fleet size and increase the resource utilization rate compared with distributed dispatching methods.The assumption that flexible transit systems must provide service to all passengers is rejected; at the same time, the objectives of maximizing the successful response ratio are considered.The effect of passenger experience in terms of maximum acceptable advance or delay time of transfer on the model is presented.


## 1.3. Paper Organization

The remainder of this paper is organized as follows. Section2 presents the problem description. The optimization model for the centralized dispatching of flexible feeder transit is proposed in Section 3. Then, the GA is described in Section 4. In Section 5, several experiments performed to prove the rationality and feasibility of the proposed model and algorithm are discussed, followed by sensitivity analyses of the weight coefficient of the subobjective function and maximum acceptable advance or delay time of transfer. Finally, Section 6 concludes the paper and discusses future research directions.


## 2. Problem Description

This study focused on the optimization of centralized dispatching of demand-responsive flexible feeder transit. One such FFTS has been discussed widely, where commuters are transported from residential addresses to transit stations, from where they continue their journey via a traditional timetabled service (Figure1). FFTS is a complement to traditional transit services in medium-sized residential areas. Before service time, a dispatch center receives the requirements for a given area. Each requirement includes the demand locations, the number of passengers, desired transfer station, and desired time of transfer to an express line. After collecting demand information, the dispatching system determines the routes and timetables of vehicles and provides feedback to passengers about whether a reservation is successful and trip information.Figure 1
Flexible feeder transit service.The proposed optimization model is based on the following assumptions:Assumption 1.
The passengers’ demand locations and the number of passengers are known before service time, and the approximate desired time of the transfer is also known.Assumption 2.
Each demand location of a reservation is a call-responsive stop. If the demand location of a reservation cannot be a call-responsive stop, the dispatch center recommends the nearest call-responsive stop as a boarding spot.Assumption 3.
The travel time and distance between any two demand locations are known.Assumption 4.
The arrival time of a bus run serial number of an express line at a transfer station is known and is a predetermined value.Assumption 5.
The feeder transit vehicle departs from and returns to transfer stations.Assumption 6.
The passenger capacity of the feeder transit vehicle is known, and overload is not permitted.Assumption 7.
After arriving at the transfer station, passengers always select the bus that arrives first, and the passenger queue and delay time are ignored.
Here, a simple example is demonstrated. Suppose that there are several passenger requirements from nine call-responsive stops. The distributed dispatching of the FFTS generates the vehicle route and timetable for each bus run serial number (Figure2), and four vehicles are allocated to transfer passengers. Meanwhile, the optimizing centralized dispatching model allows a single vehicle to execute several bus run serial numbers, and two vehicles are allocated to follow the operation planning of four bus run serial numbers (Figure 3). This simple example proves that the centralized dispatching method can reduce fleet size and operating costs.Figure 2
Operation planning of distributed dispatching.Figure 3
Operation planning of centralized dispatching.


## 3. Proposed Optimization Model for Centralized Dispatching of Flexible Feeder Transit

### 3.1. Definitions and Notations

The model parameters are as follows.N: the set of passenger demand locationsP: the set of transfer stationsK: the set of feeder transit bus run serial numberV: the set of feeder transit vehiclesR: the set of express line bus run serial numberQ: the set of demandsQi: the set of demands for location iThe model’s input variables are as follows:QMAX: the passenger capacity of each feeder transit vehicletMAX: the maximum length of time (min) for each feeder transit bus run serial numberΔtMAX: the maximum acceptable advance or delay time (min) of transferc0: the fixed cost of the feeder vehicle (yuan)c1: the variable cost of the feeder vehicle (yuan/km).lij: distance between locations i and j (km).tij: the travel time between locations i and j (min).ts: the delay time for the feeder transit vehicle at each demand location (min)th: the transfer time between a feeder transit vehicle and an express line (min)Tr: the arrival time of bus run serial number r of an express line at a transfer stationNumq: the number of passengers of demand qTq: the desired transfer time of demand qαm: the weight coefficient of subobjective functionfm, ∑13αm=1fmmin: the minimum value of fm as the only goalfmmax: the maximum value of fm as the only goalThe decision variables of the model are as follows:xijk: the route decision of bus run serial number k (if bus run serial number k of the feeder transit traverses arc(i, j),xijk=1; otherwise, xijk=0)yqkr: service decision of demand q (if bus run serial number k of the feeder transit serves demand q to bus run serial number r of the express line, yqkr=1; otherwise, yqkr=0)zvk: dispatching decision of vehicle v (if vehicle v executes bus run serial number k of the feeder transit, zvk=1; otherwise, zvk=0)T0k: the departure time of bus run serial number k of the feeder transit at the transfer stationT1k: the arrival time of bus run serial number k of the feeder transit at the transfer stationTik: the arrival time of bus run serial number k of the feeder transit at location i


### 3.2. Optimization Model

#### 3.2.1. Objective

Flexible feeder transit is one of the most effective dispatching measures to satisfy diverse demands; however, it increases operating costs compared with fixed bus routes. Thus, a balance must be found among operation benefits, passenger costs, and operating costs.(1) Operation Benefit. Improving the successful response ratio is a common goal of operators and passengers. Therefore, the proposed model structures the objective function of operation benefit as maximization of the successful response ratio, expressed as formula (1). For unified optimization, the minimization of the unsuccessful response ratio is given by formula (2).(1)maxf1∗=∑q∈Q∑k∈K∑r∈RyqkrNumq∑q∈QNumq,(2)minf1=1−f1∗.(2) Passenger Time Costs. The passenger costs of successfully reserved passengers should be guaranteed. Passenger costs comprise accounting and time costs. Accounting costs depend on the fare for flexible feeder transit, as time costs are reflected in travel time f21 and the advanced or delay time of transfer compared with reservation f22. Because of the public welfare part involved in public transport, the fare is subject to several restrictions; this is beyond the scope of this study. Thus, the proposed model structures the objective function of passenger costs as minimization of the passengers’ average time costs f2. This objective function is expressed as follows:(3)minf21=∑q∈Q∑k∈K∑r∈RyqkrNumqTr−T0k∑q∈Q∑k∈K∑r∈RyqkrNumq,minf22=∑q∈Q∑k∈K∑r∈RyqkrNumqTr−Tq∑q∈Q∑k∈K∑r∈RyqkrNumq,minf2=f21+f22.(3) Operating Costs. The proposed model formulates the objectives as the minimization of the operating costs of a single passenger. The operating costs consist of fixed operating costs and variable operating costs. At the level of distributed dispatching, the objective function can be formulated as formula (4). And the improved objective function considering the centralized dispatching is given by equation (5). The difference between the distributed dispatching and centralized dispatching is the number of configured vehicles in the fixed operating costs accounting.(4)minf3∗=c0∑v∈V∑k∈Kzvk+c1∑k∈K∑i∈P∪N∑j∈P∪Nxijklij∑q∈Q∑k∈K∑r∈RyqkrNumq,(5)minf3=c0∑v∈Vmin1,∑k∈Kzvk+c1∑k∈K∑i∈P∪N∑j∈P∪Nxijklij∑q∈Q∑k∈K∑r∈RyqkrNumq.Then, normalization of the objective function of the proposed model is performed as follows:(6)minF=∑13αmfm−fmminfmmax−fmmin.


#### 3.2.2. Constraints

Constraint (7) specifies that the origin and destination station of each bus run serial number must be the transfer station.(7)∑i∈Nxjik=∑i∈Nxijk=1,∀k∈K,j∈P.Constraint (8) guarantees that each demand location can be served by the same bus run serial number at most once.(8)∑j∈N∪Pxjik≤1,∀i∈N,∀k∈K.Constraint (9) guarantees that the passenger-carrying capacity of each bus run serial number of the feeder transit is not violated.(9)∑q∈Q∑r∈RyqkrNumq≤QMAX,∀k∈K.Constraint (10) guarantees that the maximum time of a single trip of the feeder transit is not violated.(10)∑i∈N∪P∑j∈N∪Pxijktij+ts≤tMAX,∀k∈K.Constraint (11) defines the mathematical relationship between the departure and arrival times of each bus run serial number of the feeder transit. Constraint (12) defines the mathematical relationship between the arrival time of a bus run serial number of the feeder transit and the express line, which guarantees that the passenger waiting time is zero.(11)T1k=T0k+∑,i∈N∪P∑j∈N∪Pxijktij+ts,∀k∈K,(12)T1k+th=∑r∈RTrmaxyqkr|q∈Q,∀k∈K.Constraint (13) guarantees that each demand is satisfied by a single bus run serial number of the feeder transit to transfer to one bus run serial number of an express line. Constraint (14) guarantees that each bus run serial number of the feeder transit corresponds to a single bus run serial number of an express line (M is a large positive number). Constraint (15) guarantees that the difference value between the actual transfer time and expected transfer time is within a limit.(13)∑r∈R∑k∈Kyqikr≤1,∀qi∈Qi,∀i∈N,(14)∑m∈R/ryskm−1−yqkrM≤0,∀s,q∈Q,∀r∈R,∀k∈K,(15)ΔtMAX−Tr−Tq∑k∈Kyqkr≥0,∀q∈Q,∀r∈R.Constraint (16) specifies the mathematical relationship between x and y.(16)∑r∈Ryqikr≤∑j∈N∪Pxijk,∀qi∈Qi,∀i∈N,∀k∈K.Constraint (17) guarantees that each bus run serial number k can only be executed by a single vehicle.(17)∑v∈Vzvk=1,∀k∈K.Constraint (18) guarantees that no time conflict exists for each bus run serial number k executed by the same vehicle.(18)zvk∗zvh=0,∀k,h∈K,T0k,T1k∩T0h,T1h≠∅,∀v∈V.


## 3.1. Definitions and Notations

The model parameters are as follows.N: the set of passenger demand locationsP: the set of transfer stationsK: the set of feeder transit bus run serial numberV: the set of feeder transit vehiclesR: the set of express line bus run serial numberQ: the set of demandsQi: the set of demands for location iThe model’s input variables are as follows:QMAX: the passenger capacity of each feeder transit vehicletMAX: the maximum length of time (min) for each feeder transit bus run serial numberΔtMAX: the maximum acceptable advance or delay time (min) of transferc0: the fixed cost of the feeder vehicle (yuan)c1: the variable cost of the feeder vehicle (yuan/km).lij: distance between locations i and j (km).tij: the travel time between locations i and j (min).ts: the delay time for the feeder transit vehicle at each demand location (min)th: the transfer time between a feeder transit vehicle and an express line (min)Tr: the arrival time of bus run serial number r of an express line at a transfer stationNumq: the number of passengers of demand qTq: the desired transfer time of demand qαm: the weight coefficient of subobjective functionfm, ∑13αm=1fmmin: the minimum value of fm as the only goalfmmax: the maximum value of fm as the only goalThe decision variables of the model are as follows:xijk: the route decision of bus run serial number k (if bus run serial number k of the feeder transit traverses arc(i, j),xijk=1; otherwise, xijk=0)yqkr: service decision of demand q (if bus run serial number k of the feeder transit serves demand q to bus run serial number r of the express line, yqkr=1; otherwise, yqkr=0)zvk: dispatching decision of vehicle v (if vehicle v executes bus run serial number k of the feeder transit, zvk=1; otherwise, zvk=0)T0k: the departure time of bus run serial number k of the feeder transit at the transfer stationT1k: the arrival time of bus run serial number k of the feeder transit at the transfer stationTik: the arrival time of bus run serial number k of the feeder transit at location i


## 3.2. Optimization Model

### 3.2.1. Objective

Flexible feeder transit is one of the most effective dispatching measures to satisfy diverse demands; however, it increases operating costs compared with fixed bus routes. Thus, a balance must be found among operation benefits, passenger costs, and operating costs.(1) Operation Benefit. Improving the successful response ratio is a common goal of operators and passengers. Therefore, the proposed model structures the objective function of operation benefit as maximization of the successful response ratio, expressed as formula (1). For unified optimization, the minimization of the unsuccessful response ratio is given by formula (2).(1)maxf1∗=∑q∈Q∑k∈K∑r∈RyqkrNumq∑q∈QNumq,(2)minf1=1−f1∗.(2) Passenger Time Costs. The passenger costs of successfully reserved passengers should be guaranteed. Passenger costs comprise accounting and time costs. Accounting costs depend on the fare for flexible feeder transit, as time costs are reflected in travel time f21 and the advanced or delay time of transfer compared with reservation f22. Because of the public welfare part involved in public transport, the fare is subject to several restrictions; this is beyond the scope of this study. Thus, the proposed model structures the objective function of passenger costs as minimization of the passengers’ average time costs f2. This objective function is expressed as follows:(3)minf21=∑q∈Q∑k∈K∑r∈RyqkrNumqTr−T0k∑q∈Q∑k∈K∑r∈RyqkrNumq,minf22=∑q∈Q∑k∈K∑r∈RyqkrNumqTr−Tq∑q∈Q∑k∈K∑r∈RyqkrNumq,minf2=f21+f22.(3) Operating Costs. The proposed model formulates the objectives as the minimization of the operating costs of a single passenger. The operating costs consist of fixed operating costs and variable operating costs. At the level of distributed dispatching, the objective function can be formulated as formula (4). And the improved objective function considering the centralized dispatching is given by equation (5). The difference between the distributed dispatching and centralized dispatching is the number of configured vehicles in the fixed operating costs accounting.(4)minf3∗=c0∑v∈V∑k∈Kzvk+c1∑k∈K∑i∈P∪N∑j∈P∪Nxijklij∑q∈Q∑k∈K∑r∈RyqkrNumq,(5)minf3=c0∑v∈Vmin1,∑k∈Kzvk+c1∑k∈K∑i∈P∪N∑j∈P∪Nxijklij∑q∈Q∑k∈K∑r∈RyqkrNumq.Then, normalization of the objective function of the proposed model is performed as follows:(6)minF=∑13αmfm−fmminfmmax−fmmin.


### 3.2.2. Constraints

Constraint (7) specifies that the origin and destination station of each bus run serial number must be the transfer station.(7)∑i∈Nxjik=∑i∈Nxijk=1,∀k∈K,j∈P.Constraint (8) guarantees that each demand location can be served by the same bus run serial number at most once.(8)∑j∈N∪Pxjik≤1,∀i∈N,∀k∈K.Constraint (9) guarantees that the passenger-carrying capacity of each bus run serial number of the feeder transit is not violated.(9)∑q∈Q∑r∈RyqkrNumq≤QMAX,∀k∈K.Constraint (10) guarantees that the maximum time of a single trip of the feeder transit is not violated.(10)∑i∈N∪P∑j∈N∪Pxijktij+ts≤tMAX,∀k∈K.Constraint (11) defines the mathematical relationship between the departure and arrival times of each bus run serial number of the feeder transit. Constraint (12) defines the mathematical relationship between the arrival time of a bus run serial number of the feeder transit and the express line, which guarantees that the passenger waiting time is zero.(11)T1k=T0k+∑,i∈N∪P∑j∈N∪Pxijktij+ts,∀k∈K,(12)T1k+th=∑r∈RTrmaxyqkr|q∈Q,∀k∈K.Constraint (13) guarantees that each demand is satisfied by a single bus run serial number of the feeder transit to transfer to one bus run serial number of an express line. Constraint (14) guarantees that each bus run serial number of the feeder transit corresponds to a single bus run serial number of an express line (M is a large positive number). Constraint (15) guarantees that the difference value between the actual transfer time and expected transfer time is within a limit.(13)∑r∈R∑k∈Kyqikr≤1,∀qi∈Qi,∀i∈N,(14)∑m∈R/ryskm−1−yqkrM≤0,∀s,q∈Q,∀r∈R,∀k∈K,(15)ΔtMAX−Tr−Tq∑k∈Kyqkr≥0,∀q∈Q,∀r∈R.Constraint (16) specifies the mathematical relationship between x and y.(16)∑r∈Ryqikr≤∑j∈N∪Pxijk,∀qi∈Qi,∀i∈N,∀k∈K.Constraint (17) guarantees that each bus run serial number k can only be executed by a single vehicle.(17)∑v∈Vzvk=1,∀k∈K.Constraint (18) guarantees that no time conflict exists for each bus run serial number k executed by the same vehicle.(18)zvk∗zvh=0,∀k,h∈K,T0k,T1k∩T0h,T1h≠∅,∀v∈V.


## 3.2.1. Objective

Flexible feeder transit is one of the most effective dispatching measures to satisfy diverse demands; however, it increases operating costs compared with fixed bus routes. Thus, a balance must be found among operation benefits, passenger costs, and operating costs.(1) Operation Benefit. Improving the successful response ratio is a common goal of operators and passengers. Therefore, the proposed model structures the objective function of operation benefit as maximization of the successful response ratio, expressed as formula (1). For unified optimization, the minimization of the unsuccessful response ratio is given by formula (2).(1)maxf1∗=∑q∈Q∑k∈K∑r∈RyqkrNumq∑q∈QNumq,(2)minf1=1−f1∗.(2) Passenger Time Costs. The passenger costs of successfully reserved passengers should be guaranteed. Passenger costs comprise accounting and time costs. Accounting costs depend on the fare for flexible feeder transit, as time costs are reflected in travel time f21 and the advanced or delay time of transfer compared with reservation f22. Because of the public welfare part involved in public transport, the fare is subject to several restrictions; this is beyond the scope of this study. Thus, the proposed model structures the objective function of passenger costs as minimization of the passengers’ average time costs f2. This objective function is expressed as follows:(3)minf21=∑q∈Q∑k∈K∑r∈RyqkrNumqTr−T0k∑q∈Q∑k∈K∑r∈RyqkrNumq,minf22=∑q∈Q∑k∈K∑r∈RyqkrNumqTr−Tq∑q∈Q∑k∈K∑r∈RyqkrNumq,minf2=f21+f22.(3) Operating Costs. The proposed model formulates the objectives as the minimization of the operating costs of a single passenger. The operating costs consist of fixed operating costs and variable operating costs. At the level of distributed dispatching, the objective function can be formulated as formula (4). And the improved objective function considering the centralized dispatching is given by equation (5). The difference between the distributed dispatching and centralized dispatching is the number of configured vehicles in the fixed operating costs accounting.(4)minf3∗=c0∑v∈V∑k∈Kzvk+c1∑k∈K∑i∈P∪N∑j∈P∪Nxijklij∑q∈Q∑k∈K∑r∈RyqkrNumq,(5)minf3=c0∑v∈Vmin1,∑k∈Kzvk+c1∑k∈K∑i∈P∪N∑j∈P∪Nxijklij∑q∈Q∑k∈K∑r∈RyqkrNumq.Then, normalization of the objective function of the proposed model is performed as follows:(6)minF=∑13αmfm−fmminfmmax−fmmin.


## 3.2.2. Constraints

Constraint (7) specifies that the origin and destination station of each bus run serial number must be the transfer station.(7)∑i∈Nxjik=∑i∈Nxijk=1,∀k∈K,j∈P.Constraint (8) guarantees that each demand location can be served by the same bus run serial number at most once.(8)∑j∈N∪Pxjik≤1,∀i∈N,∀k∈K.Constraint (9) guarantees that the passenger-carrying capacity of each bus run serial number of the feeder transit is not violated.(9)∑q∈Q∑r∈RyqkrNumq≤QMAX,∀k∈K.Constraint (10) guarantees that the maximum time of a single trip of the feeder transit is not violated.(10)∑i∈N∪P∑j∈N∪Pxijktij+ts≤tMAX,∀k∈K.Constraint (11) defines the mathematical relationship between the departure and arrival times of each bus run serial number of the feeder transit. Constraint (12) defines the mathematical relationship between the arrival time of a bus run serial number of the feeder transit and the express line, which guarantees that the passenger waiting time is zero.(11)T1k=T0k+∑,i∈N∪P∑j∈N∪Pxijktij+ts,∀k∈K,(12)T1k+th=∑r∈RTrmaxyqkr|q∈Q,∀k∈K.Constraint (13) guarantees that each demand is satisfied by a single bus run serial number of the feeder transit to transfer to one bus run serial number of an express line. Constraint (14) guarantees that each bus run serial number of the feeder transit corresponds to a single bus run serial number of an express line (M is a large positive number). Constraint (15) guarantees that the difference value between the actual transfer time and expected transfer time is within a limit.(13)∑r∈R∑k∈Kyqikr≤1,∀qi∈Qi,∀i∈N,(14)∑m∈R/ryskm−1−yqkrM≤0,∀s,q∈Q,∀r∈R,∀k∈K,(15)ΔtMAX−Tr−Tq∑k∈Kyqkr≥0,∀q∈Q,∀r∈R.Constraint (16) specifies the mathematical relationship between x and y.(16)∑r∈Ryqikr≤∑j∈N∪Pxijk,∀qi∈Qi,∀i∈N,∀k∈K.Constraint (17) guarantees that each bus run serial number k can only be executed by a single vehicle.(17)∑v∈Vzvk=1,∀k∈K.Constraint (18) guarantees that no time conflict exists for each bus run serial number k executed by the same vehicle.(18)zvk∗zvh=0,∀k,h∈K,T0k,T1k∩T0h,T1h≠∅,∀v∈V.


## 4. Solution Algorithm

Some studies have proposed machine learning [27], hybrid evolutionary [28], and Tabu search [29, 30] methods for the dial-a-ride problem; GA [12, 31] and heuristic algorithm [11, 24] are among the most successful approximate approaches for solving the dial-a-ride problem. GA was tested on a set of medium-scale problem scenarios, and it was found to be accessible and efficient. Generally, GA is the most suitable for a flexible feeder transit model for residential communities. The main steps of GA are as follows:(1)
Chromosome Encoding. In this paper, each chromosome comprises three parts. For the first part, genes are the travel sequence of the demand locations of demand q. The length of this part is Q+K, with serial number 1,2,3,…,Q representing the demand and serial number Q+1,Q+2,…,Q+K representing the beginning of another bus run serial number. For the second part, the genes are the transfer connection between an express line and a feeder bus run serial number. The length of this part is K, with the 1−2−3−⋯−R−1−R encoding bus run serial number of the express line. For the third part, the feeder bus run serial number must match the feeder vehicle by genes. The length of this part is K, with the 1−2−3−⋯−V−1−V encoding the serial number of a feeder vehicle.(2)
Chromosome Adjustment and Screening. The chromosomes are decoded into the route, the bus run serial number of the express line, and the serial number of the feeder vehicle. Then, it is necessary to adjust and select chromosomes as follows: (1) calculate the timetable of each bus run serial number according to constraints (11) and (12); (2) determine whether the timetable satisfies the arrival time window requirements of each demand on the route according to constraint (15); (3) eliminate the demand of the route for which arrival time window requirements are not satisfied and adjust the vehicle and timetable route; and (4) determine whether the chromosome satisfies other constraints, dismiss chromosomes that violate any constraints, and generate a new chromosome for the process of adjustment and screening.(3)
Fitness Calculation. Fitness is defined as follows:(19)fitness=1F.(4)
Crossover and Mutation Operations. The detailed steps of the crossover and mutation operations are similar to those of the standard GA.The steps of the algorithm are shown as follows:Step 1.
Generate the initial population and determine parameters such as population size, maximum evolution algebra, cross probability, and mutation probability.Step 2.
Ensure by chromosome adjustment and screening that each chromosome is feasible.Step 3.
Perform fitness function calculation, and record the maximum fitness value and its corresponding chromosome.Step 4.
Terminate the decision. If the evolutionary algebra reaches the maximum evolution algebra, stop the algorithm and output the optimal solution; otherwise, perform Step5.Step 5.
Perform genetic manipulation. Perform selection, crossover, and mutation and return to Step2.


## 5. Case Study

### 5.1. Model Parameters

#### 5.1.1. Network and Simulated Requirements

Here, a road network in a residential area in Beijing is taken as an example. As shown in Figure4, there are 15 demand locations and one transfer station in the express line. The value of travel time of the feeder vehicle between any two locations is given in Table 1. Simulated requirement data during morning peak were used to test the proposed model in a real-world network, and detailed information about the demands of 100 passengers is given in Table 2.Figure 4
Case study area.Table 1
Travel time between any two locations.
Travel time (min)p0123456789101112131415p005753561010101013111715141506589118912151316161317276047896411141215131016355405464571081112912438750539109712917141355984502455677129966119632067649614111071086494602576885108109451057207981095129101211795657033475510101514107647930621076111313128127968360342412111615119768104230854131716131217121489710480441415131091491155572540615141716121391010125644460Table 2
Simulated demands.
IDDemand locationNumber of passengersExpected transfer time1136:452117:153138:154226:305248:306327:007318:008347:309418:0010437:4511536:3012528:1513637:3014748:0015746:4516817:0017837:4518818:3019936:3020948:15211027:30221038:30231017:15241116:15251146:45261227:30271247:00281248:15291336:30301337:00311426:30321446:45331428:15341537:15351546:30361537:45


#### 5.1.2. Parameters

The parameter values were set as follows:tMAX=40min [32]; ts=0.5min [33], th=3min [33]; QMAX=10 [34];c0=50 yuan [34]; c1=3 yuan/km [34]; Tr=6:15am,6:30am,…,8:15am,8:30am with a 15-minute departure headway; ΔtMAX=15min; and α1=1/3,α2=1/3,α3=1/3, i.e., α1:α2:α3=1:1:1.


### 5.2. Model Optimization Results

The MATLAB solver version R2014a was adopted to solve the model. All experiments were performed on an Intel(R) Core(TM) i5-6300 CPU @ 2.30 GHz with 4 GB RAM. The population size was 100, the maximum evolution algebra was 500, the cross probability was 0.9, and mutation probability was 0.2. Here, two sets of scenarios were designed to verify the optimization effect of the improved model: Scenario A is the proposed centralized dispatching model, and Scenario B is the distributed dispatching model for comparison with the centralized dispatching model.The optimal objective function value of each generation in Scenario A is shown in Figure5, which indicates that the algorithm converges in preconceived evolution algebra. Table 3 demonstrates that compared with Scenario B, the optimal objective function value of the proposed model was improved by 26%. Although the successful response ratio showed a 29.3% increase and the average passenger time cost was slightly reduced, the operating costs of a single passenger were reduced by 30.7%. In particular, the proposed centralized dispatching model improves service coverage and service quality on the basis of economies of scale. Results also indicate that the proposed centralized dispatching model demonstrates both rationality and feasibility.Figure 5
Optimization procedure.Table 3
Comparison of optimal results between centralized dispatching and route planning.
ScenarioFNumber of vehiclesNumber of bus run serial numbersf1f2 (h)f3 (yuan)f21 (h)f22 (h)A0.37480.250.284.990.220.06B0.50660.420.297.200.230.06In Scenario A, the four vehicles were arranged to complete eight bus run serial numbers serving 75 passengers. The total travel distance of all bus run serial numbers was 58.2 km (an average of 7.3 km per bus run serial number), and the operating cost of a single passenger was 4.99 yuan with a 0.94 average loading rate of the vehicle. In addition, the average passenger travel time was 0.22 h (13.2 min), and the average advanced or delay time of transfer was 0.06 h (3.6 min). The operation plan of Scenario A is given in Table4.Table 4
Operation plan of the centralized dispatching model of Scenario A.
Vehicle IDBus run IDBusloadTravel distance (km)RouteDeparture timeArrival time11107.6p0-12-14-9-p05 : 406 : 123109.6p0-13-7-1-p06 : 166 : 57885.0p0-1-2-3-p08 : 058 : 2722107.5p0-15-12-10-p05 : 406 : 124108.7p0-13-15-5-p06 : 206 : 5735106.0p0-8-7-4-p06 : 316 : 574687.5p0-14-11-p06 : 557 : 27796.3p0-10-6-3-p07 : 478 : 12Total7558.2———


### 5.3. Stability Test

To further verify the reliability of the algorithm, we expanded the number of demand locations and the total number of demands on a practical scale. Keeping the existing parameter values and road network unchanged, we tested 400 travel demands in 30 sets of randomly generated 30 demand locations (the group test was denoted as GroupA+). The maximum evolution algebra of the GA algorithm is 2000 for the distensible network size.The algorithm of 30 sets all converges in preconceived evolution algebra. The results obtained for Group A+ demonstrate that the number of service vehicles was 12–14, the mean of passengers’ average travel time was 15.1 min, and the mean of average advanced or delay time of transfer was 11.1 min. The flexible feeder transit provided on-demand service as the average successful response ratio was 0.73 and the mean of the operating costs of a single passenger was 4.72 yuan. The test results are shown in Figures 6–9.Figure 6
Successful response ratio of GroupA+.Figure 7
Average passenger travel time of GroupA+.Figure 8
Average advanced or delay time of transfer of GroupA+.Figure 9
Operating costs of the single passenger of GroupA+.As shown in Figures6–9, the subobjectives of the model, such as the successful response ratio f1, the passengers’ average travel time f21, the average advanced or delay time of transfer f22, and the operating costs of a single passenger f3 solved by the GA algorithm were stable. Even with more demands, owing to the robustness of the proposed model and algorithm, the final results are considered reliable.


### 5.4. Sensitivity Analysis

The values of important parameters are crucial to the results of the model. Although most of the parameter values could be confirmed according to existing research results, some important parameters were confirmed according to a reasonable hypothesis and analysis. Here, we discuss several experiments and the effect of the values of parameters using the same network and demands used in Scenario A.


#### 5.4.1. Weight Coefficients of the Subobjective Function

The weight coefficients of the subobjective function were set to balance the relationships among operation benefit, passenger costs, and operating costs. Here,α1, α2, and α3 denote the weight of the operation benefit, weight of the passenger costs, and weight of the operating costs, respectively. We performed several sets of experiments with different αi values (Table 5); we analyze the following results:(1)
When the value ofα1:α2:α3 is confirmed in Scenarios C, D, and E, the degree of importance of the three subobjectives differs, and the values of the subobjective will change compared with Scenario A. Here, f1 was optimized in Scenario C, f3 was reduced, and f2 increased. When f2 became more important in Scenario D, the values of f1 and f3 increased and f2 was optimized. In Scenario E, f3 and f1 were optimized, and f2 increased.(2)
By using greater weight coefficients forf1 or f3, this model could optimize both f1 and f3. In other words, when operators attempt to serve more passengers or reduce single passenger costs, the greater number of passengers ensures the scale effect and service quality is reduced within acceptable limits. In addition, when operators attach importance to service quality, the value of the average passenger time cost decreases, whereas the unsuccessful response ratio and the operating costs of a single passenger increase.(3)
The different values ofαi resulted in different optimal operation plans. One more bus run serial number was arranged in Scenario C, and fewer vehicles were arranged in Scenario D. Although the number of vehicles in Scenario E was unchanged compared with Scenario A, the routes and timetables of bus run serial numbers were changed.Table 5
Results of differentαi values.
Scenarioα1:α2:α2Number of vehiclesNumber of bus run serial numbersf1f2 (h)f3 (yuan)A1 : 1 : 1480.250.284.99C2 : 1 : 1490.170.344.89D1 : 2 : 1360.450.215.18E1 : 1 : 2480.210.304.81Essentially, the optimization procedures for the successful response ratio and the operating costs are in the same direction, whereas the one for the passenger’ cost is in the opposite direction. In practice, operators should select appropriate values for the weight coefficients according to actual requirements to optimize the operation plans.


#### 5.4.2. Maximum Acceptable Advance or Delay Time of Transfer

According to the departure headway of the express line of the regular public transport system, several sets of experiments were performed at different intervalsΔtMAX. The results are given in Table 6, and the analysis of the results is as follows:(1)
The larger the value ofΔtMAXis, the more flexible is the matching relationship between passengers and bus run serial numbers, which reduces the unsuccessful response ratio and the operating costs of a single passenger.(2)
However, passengers’ average advanced or delay time of transferf22 increase with increasing ΔtMAX, and the passengers’ average travel time f21 is basically steady. Here, the values of f22 were 3.6, 7.8, and 9.0 min for Scenarios A, F, and G, respectively.(3)
The different values ofΔtMAX result in different optimal operation plans. The successful response ratio of Scenario F is 0.79, and the successful response ratio of Scenario A is 0.75. The operation plan of Scenario F is given in Table 7, although the number of vehicles and the total number of bus run serial numbers in Scenario F were unchanged compared with Scenario A, the routes and timetables of the bus run serial numbers were changed to serve more passengers. In addition, two additional bus run serial numbers were arranged in Scenario G.Table 6
Results of differentΔtMAX values.
ScenarioΔtMAX/minNumber of vehiclesNumber of bus run serial numbersf1f2 (h)f3 (yuan)f21 (h)f22 (h)A15,30480.250.284.990.220.06F30,45480.210.354.690.220.13G45,+∞4100.060.384.470.230.15Table 7
Operation plan of the centralized dispatching model of Scenario F.
Vehicle IDBus run IDBusloadTravel distance (km)RouteDeparture timeArrival time11108.7p0-13-15-5- p05 : 526 : 27495.4p0-4-7-5- p06 : 356 : 577105.7p0-12-10-6-p07 : 347 : 5722107.8p0-9-11-1- p06 : 106 : 425108.5p0-10-14-2- p06 : 537 : 278106.4p0-9-12-4-p08 : 018 : 2733107.3p0-14-7-3-p06 : 266 : 5746107.9p0-15-3-p06 : 557 : 27Total7957.7———From the part of sensitivity analysis ofΔtMAX, the conclusion is also presented showing that the optimization procedures for the successful response ratio and the operating costs are in the same direction, whereas the one for the passenger’ cost is in the opposite direction. In practice, operators should select an appropriate value for the maximum acceptable advance or delay time of transfer by preference survey of the passenger.


## 5.1. Model Parameters

### 5.1.1. Network and Simulated Requirements

Here, a road network in a residential area in Beijing is taken as an example. As shown in Figure4, there are 15 demand locations and one transfer station in the express line. The value of travel time of the feeder vehicle between any two locations is given in Table 1. Simulated requirement data during morning peak were used to test the proposed model in a real-world network, and detailed information about the demands of 100 passengers is given in Table 2.Figure 4
Case study area.Table 1
Travel time between any two locations.
Travel time (min)p0123456789101112131415p005753561010101013111715141506589118912151316161317276047896411141215131016355405464571081112912438750539109712917141355984502455677129966119632067649614111071086494602576885108109451057207981095129101211795657033475510101514107647930621076111313128127968360342412111615119768104230854131716131217121489710480441415131091491155572540615141716121391010125644460Table 2
Simulated demands.
IDDemand locationNumber of passengersExpected transfer time1136:452117:153138:154226:305248:306327:007318:008347:309418:0010437:4511536:3012528:1513637:3014748:0015746:4516817:0017837:4518818:3019936:3020948:15211027:30221038:30231017:15241116:15251146:45261227:30271247:00281248:15291336:30301337:00311426:30321446:45331428:15341537:15351546:30361537:45


### 5.1.2. Parameters

The parameter values were set as follows:tMAX=40min [32]; ts=0.5min [33], th=3min [33]; QMAX=10 [34];c0=50 yuan [34]; c1=3 yuan/km [34]; Tr=6:15am,6:30am,…,8:15am,8:30am with a 15-minute departure headway; ΔtMAX=15min; and α1=1/3,α2=1/3,α3=1/3, i.e., α1:α2:α3=1:1:1.


## 5.1.1. Network and Simulated Requirements

Here, a road network in a residential area in Beijing is taken as an example. As shown in Figure4, there are 15 demand locations and one transfer station in the express line. The value of travel time of the feeder vehicle between any two locations is given in Table 1. Simulated requirement data during morning peak were used to test the proposed model in a real-world network, and detailed information about the demands of 100 passengers is given in Table 2.Figure 4
Case study area.Table 1
Travel time between any two locations.
Travel time (min)p0123456789101112131415p005753561010101013111715141506589118912151316161317276047896411141215131016355405464571081112912438750539109712917141355984502455677129966119632067649614111071086494602576885108109451057207981095129101211795657033475510101514107647930621076111313128127968360342412111615119768104230854131716131217121489710480441415131091491155572540615141716121391010125644460Table 2
Simulated demands.
IDDemand locationNumber of passengersExpected transfer time1136:452117:153138:154226:305248:306327:007318:008347:309418:0010437:4511536:3012528:1513637:3014748:0015746:4516817:0017837:4518818:3019936:3020948:15211027:30221038:30231017:15241116:15251146:45261227:30271247:00281248:15291336:30301337:00311426:30321446:45331428:15341537:15351546:30361537:45


## 5.1.2. Parameters

The parameter values were set as follows:tMAX=40min [32]; ts=0.5min [33], th=3min [33]; QMAX=10 [34];c0=50 yuan [34]; c1=3 yuan/km [34]; Tr=6:15am,6:30am,…,8:15am,8:30am with a 15-minute departure headway; ΔtMAX=15min; and α1=1/3,α2=1/3,α3=1/3, i.e., α1:α2:α3=1:1:1.


## 5.2. Model Optimization Results

The MATLAB solver version R2014a was adopted to solve the model. All experiments were performed on an Intel(R) Core(TM) i5-6300 CPU @ 2.30 GHz with 4 GB RAM. The population size was 100, the maximum evolution algebra was 500, the cross probability was 0.9, and mutation probability was 0.2. Here, two sets of scenarios were designed to verify the optimization effect of the improved model: Scenario A is the proposed centralized dispatching model, and Scenario B is the distributed dispatching model for comparison with the centralized dispatching model.The optimal objective function value of each generation in Scenario A is shown in Figure5, which indicates that the algorithm converges in preconceived evolution algebra. Table 3 demonstrates that compared with Scenario B, the optimal objective function value of the proposed model was improved by 26%. Although the successful response ratio showed a 29.3% increase and the average passenger time cost was slightly reduced, the operating costs of a single passenger were reduced by 30.7%. In particular, the proposed centralized dispatching model improves service coverage and service quality on the basis of economies of scale. Results also indicate that the proposed centralized dispatching model demonstrates both rationality and feasibility.Figure 5
Optimization procedure.Table 3
Comparison of optimal results between centralized dispatching and route planning.
ScenarioFNumber of vehiclesNumber of bus run serial numbersf1f2 (h)f3 (yuan)f21 (h)f22 (h)A0.37480.250.284.990.220.06B0.50660.420.297.200.230.06In Scenario A, the four vehicles were arranged to complete eight bus run serial numbers serving 75 passengers. The total travel distance of all bus run serial numbers was 58.2 km (an average of 7.3 km per bus run serial number), and the operating cost of a single passenger was 4.99 yuan with a 0.94 average loading rate of the vehicle. In addition, the average passenger travel time was 0.22 h (13.2 min), and the average advanced or delay time of transfer was 0.06 h (3.6 min). The operation plan of Scenario A is given in Table4.Table 4
Operation plan of the centralized dispatching model of Scenario A.
Vehicle IDBus run IDBusloadTravel distance (km)RouteDeparture timeArrival time11107.6p0-12-14-9-p05 : 406 : 123109.6p0-13-7-1-p06 : 166 : 57885.0p0-1-2-3-p08 : 058 : 2722107.5p0-15-12-10-p05 : 406 : 124108.7p0-13-15-5-p06 : 206 : 5735106.0p0-8-7-4-p06 : 316 : 574687.5p0-14-11-p06 : 557 : 27796.3p0-10-6-3-p07 : 478 : 12Total7558.2———


## 5.3. Stability Test

To further verify the reliability of the algorithm, we expanded the number of demand locations and the total number of demands on a practical scale. Keeping the existing parameter values and road network unchanged, we tested 400 travel demands in 30 sets of randomly generated 30 demand locations (the group test was denoted as GroupA+). The maximum evolution algebra of the GA algorithm is 2000 for the distensible network size.The algorithm of 30 sets all converges in preconceived evolution algebra. The results obtained for Group A+ demonstrate that the number of service vehicles was 12–14, the mean of passengers’ average travel time was 15.1 min, and the mean of average advanced or delay time of transfer was 11.1 min. The flexible feeder transit provided on-demand service as the average successful response ratio was 0.73 and the mean of the operating costs of a single passenger was 4.72 yuan. The test results are shown in Figures 6–9.Figure 6
Successful response ratio of GroupA+.Figure 7
Average passenger travel time of GroupA+.Figure 8
Average advanced or delay time of transfer of GroupA+.Figure 9
Operating costs of the single passenger of GroupA+.As shown in Figures6–9, the subobjectives of the model, such as the successful response ratio f1, the passengers’ average travel time f21, the average advanced or delay time of transfer f22, and the operating costs of a single passenger f3 solved by the GA algorithm were stable. Even with more demands, owing to the robustness of the proposed model and algorithm, the final results are considered reliable.


## 5.4. Sensitivity Analysis

The values of important parameters are crucial to the results of the model. Although most of the parameter values could be confirmed according to existing research results, some important parameters were confirmed according to a reasonable hypothesis and analysis. Here, we discuss several experiments and the effect of the values of parameters using the same network and demands used in Scenario A.


### 5.4.1. Weight Coefficients of the Subobjective Function

The weight coefficients of the subobjective function were set to balance the relationships among operation benefit, passenger costs, and operating costs. Here,α1, α2, and α3 denote the weight of the operation benefit, weight of the passenger costs, and weight of the operating costs, respectively. We performed several sets of experiments with different αi values (Table 5); we analyze the following results:(1)
When the value ofα1:α2:α3 is confirmed in Scenarios C, D, and E, the degree of importance of the three subobjectives differs, and the values of the subobjective will change compared with Scenario A. Here, f1 was optimized in Scenario C, f3 was reduced, and f2 increased. When f2 became more important in Scenario D, the values of f1 and f3 increased and f2 was optimized. In Scenario E, f3 and f1 were optimized, and f2 increased.(2)
By using greater weight coefficients forf1 or f3, this model could optimize both f1 and f3. In other words, when operators attempt to serve more passengers or reduce single passenger costs, the greater number of passengers ensures the scale effect and service quality is reduced within acceptable limits. In addition, when operators attach importance to service quality, the value of the average passenger time cost decreases, whereas the unsuccessful response ratio and the operating costs of a single passenger increase.(3)
The different values ofαi resulted in different optimal operation plans. One more bus run serial number was arranged in Scenario C, and fewer vehicles were arranged in Scenario D. Although the number of vehicles in Scenario E was unchanged compared with Scenario A, the routes and timetables of bus run serial numbers were changed.Table 5
Results of differentαi values.
Scenarioα1:α2:α2Number of vehiclesNumber of bus run serial numbersf1f2 (h)f3 (yuan)A1 : 1 : 1480.250.284.99C2 : 1 : 1490.170.344.89D1 : 2 : 1360.450.215.18E1 : 1 : 2480.210.304.81Essentially, the optimization procedures for the successful response ratio and the operating costs are in the same direction, whereas the one for the passenger’ cost is in the opposite direction. In practice, operators should select appropriate values for the weight coefficients according to actual requirements to optimize the operation plans.


### 5.4.2. Maximum Acceptable Advance or Delay Time of Transfer

According to the departure headway of the express line of the regular public transport system, several sets of experiments were performed at different intervalsΔtMAX. The results are given in Table 6, and the analysis of the results is as follows:(1)
The larger the value ofΔtMAXis, the more flexible is the matching relationship between passengers and bus run serial numbers, which reduces the unsuccessful response ratio and the operating costs of a single passenger.(2)
However, passengers’ average advanced or delay time of transferf22 increase with increasing ΔtMAX, and the passengers’ average travel time f21 is basically steady. Here, the values of f22 were 3.6, 7.8, and 9.0 min for Scenarios A, F, and G, respectively.(3)
The different values ofΔtMAX result in different optimal operation plans. The successful response ratio of Scenario F is 0.79, and the successful response ratio of Scenario A is 0.75. The operation plan of Scenario F is given in Table 7, although the number of vehicles and the total number of bus run serial numbers in Scenario F were unchanged compared with Scenario A, the routes and timetables of the bus run serial numbers were changed to serve more passengers. In addition, two additional bus run serial numbers were arranged in Scenario G.Table 6
Results of differentΔtMAX values.
ScenarioΔtMAX/minNumber of vehiclesNumber of bus run serial numbersf1f2 (h)f3 (yuan)f21 (h)f22 (h)A15,30480.250.284.990.220.06F30,45480.210.354.690.220.13G45,+∞4100.060.384.470.230.15Table 7
Operation plan of the centralized dispatching model of Scenario F.
Vehicle IDBus run IDBusloadTravel distance (km)RouteDeparture timeArrival time11108.7p0-13-15-5- p05 : 526 : 27495.4p0-4-7-5- p06 : 356 : 577105.7p0-12-10-6-p07 : 347 : 5722107.8p0-9-11-1- p06 : 106 : 425108.5p0-10-14-2- p06 : 537 : 278106.4p0-9-12-4-p08 : 018 : 2733107.3p0-14-7-3-p06 : 266 : 5746107.9p0-15-3-p06 : 557 : 27Total7957.7———From the part of sensitivity analysis ofΔtMAX, the conclusion is also presented showing that the optimization procedures for the successful response ratio and the operating costs are in the same direction, whereas the one for the passenger’ cost is in the opposite direction. In practice, operators should select an appropriate value for the maximum acceptable advance or delay time of transfer by preference survey of the passenger.


## 5.4.1. Weight Coefficients of the Subobjective Function

The weight coefficients of the subobjective function were set to balance the relationships among operation benefit, passenger costs, and operating costs. Here,α1, α2, and α3 denote the weight of the operation benefit, weight of the passenger costs, and weight of the operating costs, respectively. We performed several sets of experiments with different αi values (Table 5); we analyze the following results:(1)
When the value ofα1:α2:α3 is confirmed in Scenarios C, D, and E, the degree of importance of the three subobjectives differs, and the values of the subobjective will change compared with Scenario A. Here, f1 was optimized in Scenario C, f3 was reduced, and f2 increased. When f2 became more important in Scenario D, the values of f1 and f3 increased and f2 was optimized. In Scenario E, f3 and f1 were optimized, and f2 increased.(2)
By using greater weight coefficients forf1 or f3, this model could optimize both f1 and f3. In other words, when operators attempt to serve more passengers or reduce single passenger costs, the greater number of passengers ensures the scale effect and service quality is reduced within acceptable limits. In addition, when operators attach importance to service quality, the value of the average passenger time cost decreases, whereas the unsuccessful response ratio and the operating costs of a single passenger increase.(3)
The different values ofαi resulted in different optimal operation plans. One more bus run serial number was arranged in Scenario C, and fewer vehicles were arranged in Scenario D. Although the number of vehicles in Scenario E was unchanged compared with Scenario A, the routes and timetables of bus run serial numbers were changed.Table 5
Results of differentαi values.
Scenarioα1:α2:α2Number of vehiclesNumber of bus run serial numbersf1f2 (h)f3 (yuan)A1 : 1 : 1480.250.284.99C2 : 1 : 1490.170.344.89D1 : 2 : 1360.450.215.18E1 : 1 : 2480.210.304.81Essentially, the optimization procedures for the successful response ratio and the operating costs are in the same direction, whereas the one for the passenger’ cost is in the opposite direction. In practice, operators should select appropriate values for the weight coefficients according to actual requirements to optimize the operation plans.


## 5.4.2. Maximum Acceptable Advance or Delay Time of Transfer

According to the departure headway of the express line of the regular public transport system, several sets of experiments were performed at different intervalsΔtMAX. The results are given in Table 6, and the analysis of the results is as follows:(1)
The larger the value ofΔtMAXis, the more flexible is the matching relationship between passengers and bus run serial numbers, which reduces the unsuccessful response ratio and the operating costs of a single passenger.(2)
However, passengers’ average advanced or delay time of transferf22 increase with increasing ΔtMAX, and the passengers’ average travel time f21 is basically steady. Here, the values of f22 were 3.6, 7.8, and 9.0 min for Scenarios A, F, and G, respectively.(3)
The different values ofΔtMAX result in different optimal operation plans. The successful response ratio of Scenario F is 0.79, and the successful response ratio of Scenario A is 0.75. The operation plan of Scenario F is given in Table 7, although the number of vehicles and the total number of bus run serial numbers in Scenario F were unchanged compared with Scenario A, the routes and timetables of the bus run serial numbers were changed to serve more passengers. In addition, two additional bus run serial numbers were arranged in Scenario G.Table 6
Results of differentΔtMAX values.
ScenarioΔtMAX/minNumber of vehiclesNumber of bus run serial numbersf1f2 (h)f3 (yuan)f21 (h)f22 (h)A15,30480.250.284.990.220.06F30,45480.210.354.690.220.13G45,+∞4100.060.384.470.230.15Table 7
Operation plan of the centralized dispatching model of Scenario F.
Vehicle IDBus run IDBusloadTravel distance (km)RouteDeparture timeArrival time11108.7p0-13-15-5- p05 : 526 : 27495.4p0-4-7-5- p06 : 356 : 577105.7p0-12-10-6-p07 : 347 : 5722107.8p0-9-11-1- p06 : 106 : 425108.5p0-10-14-2- p06 : 537 : 278106.4p0-9-12-4-p08 : 018 : 2733107.3p0-14-7-3-p06 : 266 : 5746107.9p0-15-3-p06 : 557 : 27Total7957.7———From the part of sensitivity analysis ofΔtMAX, the conclusion is also presented showing that the optimization procedures for the successful response ratio and the operating costs are in the same direction, whereas the one for the passenger’ cost is in the opposite direction. In practice, operators should select an appropriate value for the maximum acceptable advance or delay time of transfer by preference survey of the passenger.


## 6. Conclusions

In this paper, we have proposed a multiobjective optimizing centralized dispatching model for flexible feeder transit considering the transfer coordination with regular public transit. The objectives of this model are to maximize the successful response ratio, minimize the average passenger time cost, and minimize the operating costs of a single passenger. In addition, the proposed model defines several constraints such as maximum acceptable advance or delay time of transfer, rated passenger capacity, and maximum travel time of a single trip. A GA was designed to solve the proposed multiobjective model.The experimental results of real-world experiments based on a residential area in Beijing reveal that the proposed model and algorithm can be applied to real-world applications. In addition, the proposed model could output an operation plan with rigorous computation and optimization, which increases the successful response ratio and decreases both the average passenger time cost and the operating costs of a single passenger compared with a distributed dispatching model. The different weight coefficients of the subobjective function and maximum acceptable advance or delay time of transfer resulted in different optimal operation plans.Future research will focus on the following aspects:(1)
In this study, we did not consider the account costs of the passenger; thus, the fares of flexible feeder transit services should be considered.(2)
Only a single vehicle type was considered in this study; thus, in the future, multiple vehicle types should be considered.(3)
Finally, new energy vehicle technology should be analyzed and considered relative to flexible feeder transit systems.



---

*Source: 6160321-2021-03-05.xml*