# Optimal Route Assignment at the Bus Hub with Multiple Berths for Minimal Passenger Transfer Distance

Authors: Yan-Pei Zhang; Hui Jin; Hai-Ming Hao; Xiao-Guang Yang
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Bus hub is characterized with multiple berths, each serving specific bus routes. When bus routes at different berths share the same stops en route, passengers to the shared stops may rush among these berths to catch the newly arriving bus, causing inconvenience and deteriorating bus service level. Thus, this research attempts to optimize bus route assignment to the berths at a bus hub to minimize passenger transfer distance among the optional berths. The problem is modeled with integer linear programming, with the constraints of bus service capacity. To enhance computation efficiency, exclusive and inclusive constraints based on the count of shared stops among the bus routes are additionally added to the original model, though they may bring gap from the optimal solution. Case study follows to apply the proposed set of models to a bus terminal, where a total of 26 routes are assigned to 11 berths. It is found that the models with additional constraints can greatly reduce calculation time at the cost of small or no gap from the optimal solution. Thus, the models with additional constraints are recommended to obtain ideal solution quickly. This research provides insights into bus route management at the bus terminal with multiple berths, contributing to enhanced passenger waiting experience.


---

## Body

## 1. Introduction

Transit oriented development has long been accepted as a radical remedy to urban congestion under rapidly increasing motorization. Bus hub, a critical facility in the transit system, has attracted tremendous attention to accommodate various trip demands with multiple routes [1, 2]. Considering that these routes may share stops en route, passengers alighting at these shared stops can be faced with multiple route choices at different berths. Without proper route assignment, bus riders may have difficulty in deciding which berth to wait at. That is, they may struggle from the current berth to another to catch the newly arriving bus if it serves their alighting stop, which severely impacts passengers’ route choice decisions [3]. For example, in Figure 1, if the newly arriving bus (in red) at Berth 1 serves the route that shares stops with the lines at other berths, passengers alighting at the shared stops may hurry to Berth 1 as the dotted lines. Such hasty transfer can bring significant inconvenience to passenger waiting, as well as delay to bus service when drivers wait for the catching-up riders to board and buy ticket or swipe smart card. Thus, it is necessary to assign the routes with shared stops to the same or adjacent berths to facilitate passengers’ bus route choice and to secure bus service efficiency.Figure 1
Rider transfer among berths for the newly arriving bus at Berth 1.In the literature, there is increasingly rich and expansive document on facilitating bus passengers’ waiting, but most existing research aims at reducing waiting time [4, 5]. On this problem, early studies generally target bus frequency [6], while the latest research focuses on reliability as it is validated to exert more significant influence on bus service quality [7–10]. Huang et al. [11] proposed data-driven approaches based on functional data analysis and Bayesian support vector regression for short-term bus arrival time prediction under uncertainties for bus service reliability. Based on GPS and smart card databases of all bus routes in Santiago, they find that functional data analysis can adapt to the fast and sharp changes in traffic dynamics after being trained with Bayesian support vector regression. Transit crowding results in excessive waiting time and in-vehicle delay, making travel time less reliable. Paudel [12] quantified the economic cost of crowding on the quality of bus services to investigate the relationship between ridership and bus service reliability. He proposed a multivariate linear programming model in which the variables consist of three components: bus ridership, a vector of controls (e.g., bus speed and operation status), and four coefficients measuring bus service effects, confirming that transit crowding poses a negative effect on bus service reliability.Furthermore, bus real-time information [13] and schedule publishment [14] are emphasized to help passengers better plan trips to avoid undue waiting time. Bus real-time information, such as in-vehicle congestion and waiting time information, helps to mitigate bus bunching with passengers guided to choose the most appropriate bus, instead of the earliest one. Building a simulation model to depict bus operation and passenger service choices, Zhou et al. [15] showed that providing bus real-time information is as effective as the schedule-based and headway-based control methods in reducing passenger waiting time. Zhang et al. [16] studied an automatic bus schedule redesign method based on bus arrival time prediction for real-time bus dispatching to minimize the impact on the initial schedule by finding the minimum adjustment range, which reduces passengers’ average wait time at stops and allows bus operations to be adjusted in time. Updated research resorts to automatic vehicle location data, providing many more details than human-collected ones. Barabino and Di Francesco [17] developed a descriptive model to identify and analyse the regularity of actual arrival (or departure) times at bus stops. Using archived AVL data to derive related sources, this method would benefit transit managers in making accurate regularity analysis and possible service revisions.Targeting the relationship among bus routes, Barabino et al. [18] proposed an offline framework to monitor the reliability of transfers at all the bus stops and time periods by analysing automatic vehicle location data. Liu et al. [19] constructed a joint optimization model of the bus departure time and speed for multiple routes with several shared stops to avoid bus bunching and reduce passenger wait time by approximately 30%. To simplify the transfer coordination model among bus routes, transfer passengers’ wait time is minimized by adjusting bus departure interval and speed [20]. Markevych et al. [21] established the influence of bus dwell time on the inter-route transfer impedance with simulation. New zonal express routes can be added to reduce transit transfers, where similar travel demand is clustered to determine bus stop locations [22]. Motivated by the dynamics of traffic demands, Wu et al. [23] employed autonomous buses to allow passengers to travel on the shortest path smoothly, which is validated to reduce 15% transfers on average.Note that the above research assumes that passengers wait at a predetermined site, which is not changeable. But that is not always true, as riders may transfer among the berths that serve the routes dewlling at the riders' alighting stops. Thus, it is necessary to optimize route assignment to berths especially at the bus hub, the space of which spreads extensively, and transfer among berths can be very inconvenient. Though there are few efforts on the route assignment to bus hub berths, rich literature exists in the similar field of berth assignment at port [24] and gate assignment at airport [25].The studies on ship assignment are basically oriented with maximal port loading, under the consideration of differing berth shore power, crane services, slip depth, and length [26]. Thus, ships can be directed to the optimal berth for maximal utility of the available port service capacity. Developing a multiple linear regression model, Mahpour et al. [27] showed that access channel depths and the number of berths are the most significant contributing factors on the loading efficiency. Research on the airport gate assignment can be classified according to the optimization objective, i.e., to be passenger-oriented or agency-oriented [28]. For example, research on passenger-oriented objectives has started since the 1970s to minimize passenger intra-hub travel [29]. Bi et al. [25] aimed to minimize total passenger walk distance by optimizing the number of aircraft assigned to the apron with a mixed integer nonlinear programming model, which is solved with filtered beam search algorithms for the problems of larger sizes. Subsequently, various studies have accounted for passenger walk distance [30, 31], waiting or transfer time [32, 33], and baggage transport distance [34]. Chow et al. [35] developed a gate assignment model to reduce travellers’ total walk distance by optimizing the utilization of gate resources, which shows an 8.7% reduction for business class travellers and 7.4% for economy one by reducing the usage of the far gates. Wu et al. [36] focused on the impacts of gate assignment on the service to transfer passengers at the hub airport with satellite halls. Considering the transfer time budget, a transfer demand-oriented objective function is formulated to improve the efficient utilization of gate resources. To reduce baggage transportation distance, Jiang et al. [37] improved vehicle routes for baggage collection to minimize total vehicle distance.A major difference of ship berth or airport gate from bus hub berth is that ships and air passengers are seldom temporarily directed to another berth or gate or are always allowed sufficient time to make the transfer in a few cases. In contrast, passengers at bus hubs may freely haste among the optional berths. That is, if there is a newly arriving bus that pulls in at another berth and head to the passengers' alighting stop, passengers may transfer from the current berth to that one.The contributions of this article can be threefold. First, this research aims to optimize bus route assignment to the multiple berths at bus hubs when the routes share stops en route to reduce passengers’ transfer distance among the optional berths and avoid disruptions to the bus hub station. Thus, passengers’ waiting experience at the hub can be improved and bus service quality can be refined. Second, the problem is modeled with mixed integer linear programming (MILP) under the constraint of berth service capacity, based on which the extended models are developed to enhance solution efficiency without significantly degenerating the solution quality. Thus, the routes departing from the same bus hub and serving more shared stops are more likely grouped to the same or the neighboring berths. Third, case study is conducted at a typical bus hub station to demonstrate the performance of the proposed model, validating that the optimal assignment of bus routes to the hub can be rapidly obtained with passenger transfer distance reduced significantly.The remainder of the paper is structured as follows. In Section2, the parameters in the proposed model are summarized. Section 3 establishes the basic assumption and modeling with ILP for the optimal route allocation to bus hub berths. Section 4 conducts the case study, and Section 5 briefly concludes the research with suggestions for future research directions.


## 2. Notation

For the convenience and consistency of presenting the proposed model, parameters used hereafter are listed in Table1.Table 1
List of parameters.
NotationExplanationIndicesi,jIndex of routesbIndex of berthsParameterski,kjBerth index that routesi and j are assigned toCbMaximum count of bus routes that can be accommodated by berthbN,MBerth count and route count at the hubSl,SuLower and upper bounds of shared bus stops for exclusive and inclusive constraintsDecision variablesBib,BjbBinary variables indicating whether routesi and j are assigned to berth bAuxiliary variablessijTotal number of shared stops between routesi and jdijDistance between the berths that routesi and j are assigned to


## 3. Assumptions and Methodology

The following assumptions are made before developing the proposed model. (1) Route assignment to hub berths is static to avoid disruption to passengers. Moreover, their initial walk distance to any berth is not specifically addressed as they always have abundant time to do so. (2) All bus passengers can be accommodated, and they are equally attracted to the routes as long as they dwell at the alighting stop. Also, passengers always ride the earliest arriving bus. (3) Berth service capacity is reflected with route count, without specifying bus frequency and dwell time of each route for simplicity.The objective function of the proposed model is structured with(1)minz=∑i∑j≠isij⋅dij2.to minimize the total transfer distance that passengers walk among the berths serving the routes dewlling at the riders' alighting stops. The reason why the minimal transfer distance is adopted as the objective rather than transfer time among the routes at the hub is as follows. The transfer time includes two parts: (1) the walking time from the current berth to the berth where the newly arriving bus dwells and (2) the waiting time at the berth before the target bus arrives [18]. The second part of waiting time can be zero because the passengers may rush from the current berth to another one when there comes the newly arriving bus. Therefore, the transfer time can be equal to the walk time between the current and the target berth, i.e., the transfer distance divided by walk speed, where walk speed can vary significantly. Thus transfer impedance can be reflected with the distance between the berths serving the bus routes that dwell at the same stops en route, which is minimized as the objective of the proposed model.It is noted that the walk distance of passengers not alighting at the shared stops is not included in (1), as they have only one optional berth and have no need to transfer to other berths. Parameter sij refers to the total number of shared stops between routes i and j, and dij represents the distance between the berths that routes i and j are assigned to. Parameter dij is given by(2)dij=ki−kj,∀i≠j,where ki and kj mean the berth number that routes i and j are assigned to. Route assignment is constrained with(3)∑bBib=1,∀i,(4)∑iBib≤Cb,∀b,(5)ki=∑bb⋅Bib,∀i,where Bib is binary variable indicating whether route i is assigned to berth b. That is, when b=ki, variable Bib is tightened to take the value of 1; otherwise, it is equal to 0. Parameter Cb means the maximum count of bus routes that can be accommodated by berth b, due to the berth’s limited service capacity.Thus, the proposed model can be summarized with objective of (1) and constraints of equations (2)–(5). To linearize the programming model, the nonlinear relationship from (2) is replaced with the following equations:(6)dij≥ki−kj,dij≥−ki−kj,∀i≠j.To reduce solution time of the proposed programming, exclusive and inclusive constraints can be added to the model as follows:(7)ifsij≤Sl,thenBib+Bjb≤1,∀i≠j,(8)ifsij≥Su,thenki=kj,∀i≠j.(7) means that when the number of shared stops between routes i and j is no more than the lower bound Sl, they are regarded as the least related routes and cannot be assigned to the same berths. This relationship can remove N∗fM−2 schemes from the feasible domain, where fM−2 represents the solution count of assigning (M−2) routes to N berths. In contrast, (8) sets the routes with close relations, i.e., sharing stops no fewer than Su, to the same berth. As a result, the passengers patronating these routes can wait at one berth, without the need to transfer to other berths. This relationship can remove N2−N∗fM−2 schemes from the feasible domain. Note that the constraints of equations (7) and (8) may also remove the model’s optimal solution from feasible domain, though they help to reduce the search space and to enhance solution efficiency. In the following, to explore the effect of exclusive and inclusive constraints on the accuracy and efficiency of model solving, we test the original model and the extended ones as follows:(i)
Model 1 adopts the constraints of equations (3)–(6) without the exclusive and inclusive constraints. Thus, the model is capable of returning the optimal route assignment to the hub station, though it may take a relatively long computation time.(ii)
Model 2 adopts the constraints of equations (3)–(7) with an exclusive constraint, which helps to separate the bus routes with few shared stops to different berths.(iii)
Model 3 adopts the constraints of equations (3)–(6) as well as the inclusive constraint of equation (8), which combines the bus routes with sufficient shared stops at the same berth.(iv)
Model 4 adopts the constraints of equations (3)–(8) with both exclusive and inclusive constraints, which is more likely to return sub-optimal result for the benefit of reduced computation time.


## 4. Case Study and Sensitivity Analyses

The proposed method is tested at a bus hub close to the railway and coach station in Ningbo, Zhejiang Province, China. Figure2 shows the siting of the hub and its geographical layout with 11 berths, which are numbered anti-clockwise and spaced evenly. To avoid disorder in the waiting area, passengers are required to walk along the pedestrian path of blue line. Thus, walk distance between different berths can be represented with the gap in their berth indices. This hub serves a total of 26 routes, and the count of stops shared by each pair of bus routes (i.e., sij) is summarized in Figure 3. Parameters of the proposed model are set as follows. Capacity of bus berths (i.e., Cb) is set as 2, 2, 3, 1, 2, 3, 3, 2, 3, 3, and 2, respectively, considering their actual service space. The lower and upper bounds of shared stops between bus routes are 0 and 7 for the adoption of the exclusive and inclusive constraints, respectively. The algorithm is coded with Matlab 2021a in the environment of Windows 10, characterized with i-7-7700K CPU, 4.2 GHz processor, and 16 GB RAM.Figure 2
Siting and geographical layout of the selected bus hub. (a) Bus hub siting. (b) Hub geographical layout.Figure 3
The demonstration of the count of shared stops of each pair of bus routes.Results of Models 1 to 4 are summarized in Table2. It is observed that Model 1 takes 360 min (i.e., 6 hours) to obtain the optimal solution. In comparison, Model 2 incorporating the exclusive relationship manages to reduce calculation time to 50 min, though it brings 2.46% gap from the optimal value. Model 3 with inclusive constraints is capable of locating the optimal solution and reducing calculation time to 30 min. Model 4 corresponds to the shortest calculation time of 12 min by combining the exclusive and inclusive constraints, with 2.46% gap from the optimal solution.Table 2
Results of proposed models.
ModelObjectiveOptimalityGapSolution time (min)1244Yes—3602250No2.46%503244Yes—304250No2.46%12Figure4 shows the proposed scheme from the developed model. It is observed that the optimal solution from Models 1 and 3 (Figure 4(a)) assigns the route pairs (2, 4), (7, 11), (4, 21), and (6, 23) to the same berth, though they have no shared stops. That can be explained with their complex relationship to the routes at the neighboring berths under the tight constraints from berth capacity. Moreover, referring to the results from Models 2 and 4 (Figure 4(b)), the exclusive constraint removes the optimal solution from the feasible domain and brings moderate gap from the optimal solution, which is acceptable in the transportation engineering field that works well with the nearly optimal solution. Therefore, it is recommended to adopt the extended model to greatly reduce calculation time (V.S. Model 1) without significantly deteriorating the optimal solution.Figure 4
Schemes of route assignment to the hub berths from the proposed models. (a) Model 1/3 result. (b) Model 2/4 result.Due to the berth not being able to serve more routes than its capacity, bus routes must be assigned to many berths to avoid bus queues. In addition, adding some routes to one berth may increase the total transfer distance because the passengers, who may ride the route, possiblely transfer from the berth they currently wait at to this berth. That may increase the total transfer distance at the bus hub. Thus, the proposed programming may assign fewer routes to one berth than its service capacity for minimal transfer distance.Sensitivity analyses test the impact of problem scale on solution time and examine the difference in solution efficiency and accuracy among different models. Specifically, route count at a bus hub increases from 10 to 20, which is common in practice and could avoid undue calculation time. To overcome the effect of the specific characteristics in the shared stops among bus routes, the routes given in the previous section are randomly selected 10 times. The proposed 4 models are then employed to solve each set of the selected routes, respectively. Figure5 shows the box plot of CPU time from the calculation, where Model 3 tends to be the most efficient one, while the efficiency of Models 2 and 4 are less stable. Figure 6 shows the distribution of the objective value, where no significant gap is observed among the four proposed models. Thus, it is recommended to incorporate the inclusive constraint, which combines the bus routes sharing many stops en route at the same berth.Figure 5
CPU time from the four proposed models with varying bus routes. (a) Model 1’s CPU time. (b) Model 2’s CPU time. (c) Model 3’s CPU time. (d) Model 4’s CPU time.
(a)(b)(c)(d)Figure 6
Objective value from the four proposed models with varying bus routes. (a) Model 1’s objective value. (b) Model 2’s objective value. (c) Model 3’s objective value. (d) Model 4’s objective value.
(a)(b)(c)(d)The integer linear programming model proposed in this paper can provide a theoretical basis for transit agencies to assign bus routes to the multiple berths at bus hubs, thereby reducing transfer distances, improving bus service efficiency, and attracting more transit riders. In terms of modeling selection, adding inclusive constraints can be further applied to the situations of large model scale, which may take a long time for the optimal solution.


## 5. Conclusions

There has been rich literature about where to build a bus hub and which routes to serve it at specified service frequency. However, assigning the multiple bus routes with shared stops among the berths at a bus hub has not been fully studied. That may facilitate passengers’ bus route choice and waiting experience by avoiding their hasty transfer among distant optional berths that serve the bus routes dwelling at the alighting stops.To this end, bus route assignment to the multiple berths at a bus hub is modeled with the objective to minimize passengers’ transfer cost among the berths serving the bus routes to their destination stop, which is weighted with the shared stops between each route pair. Then, the constraints for the route assignment under berth service capacity are established. Thus, integer nonlinear programming is proposed and is then converted to integer linear programming. Further, to improve solution efficiency, additional constraints are developed. The exclusive and inclusive constraints assign the least (i.e., with few or no shared stops) and the most related (i.e., with many shared stops) bus routes to different and the same berths, respectively. Thus, four models are developed for the problem, i.e., the original model (Model 1), the model with exclusive constraint (Model 2), the model with inclusive constraint (Model 3), and the model with both exclusive and inclusive constraints (Model 4). Case study follows to validate that the extended models are capable of finding the optimal or near-optimal solution at the advantage of CPU time.Admittedly, this research simplifies the actual process of passengers riding a bus, which just focuses on the optimal bus route allocation to the multiple berths at one bus hub to facilitate passengers waiting. For example, loading factor of buses is not considered or balanced, where passengers can actually be directed to wait for the soon-coming and less-crowded or faster bus with real-time arrival information. Refined berth assignment considering the stochasticity of bus dwell time to avoid bus queues at the berths is another fruitful avenue for future extension.



---

*Source: 1590504-2022-10-20.xml*