The current public transportation systems predominantly rely on rigid schedules and service patterns, leading to suboptimal resource allocation that impacts both passengers and transit operators. This inefficiency results in the wastage of resources and dissatisfaction among users. The unsatisfactory passenger experience significantly contributes to the declining ridership, thereby diminishing revenue for transit operators. To specifically address these challenges encountered by Lhasa's public transportation system, we propose a multi-objective model for bus departure timetables. The model aims to synchronize the costs of passenger waiting time and bus operation costs concurrently, accounting for diverse constraints such as actual travel times, operational bus numbers, bus capacity limits, and arrival time distributions. In this research, we establish a multi-objective optimization model with the primary goal of maximizing passenger satisfaction while concurrently optimizing the revenue of the transit company. Implemented in Lhasa, China, we use the Non-Dominated Sorting Genetic Algorithm-Ⅱ to derive Pareto fronts relevant for analysis. The research findings demonstrate a reduction in the frequency of departures by one bus within a one-hour timeframe. Additionally, a substantial 37% decrease is observed in both the count of buses not arriving at stations and the number of passengers waiting at these stations compared to previous timetables. These results suggest promising potential for significant benefits to both the transit company and passengers within the public transportation system.
Citation: Gang Cheng, Yijie He. Enhancing passenger comfort and operator efficiency through multi-objective bus timetable optimization[J]. Electronic Research Archive, 2024, 32(1): 565-583. doi: 10.3934/era.2024028
Related Papers:
[1]
Peiqun Lin, Chenxing He, Lingshu Zhong, Mingyang Pei, Chuhao Zhou, Yang Liu .
Bus timetable optimization model in response to the diverse and uncertain requirements of passengers for travel comfort. Electronic Research Archive, 2023, 31(4): 2315-2336.
doi: 10.3934/era.2023118
[2]
Wuhua Jiang, Yuexin Zhang, Jie Liu, Daisheng Zhang, Yajie Yan, Chuanzheng Song .
Multi-objective optimization design for steel-aluminum lightweight body of pure electric bus based on RBF model and genetic algorithm. Electronic Research Archive, 2023, 31(4): 1982-1997.
doi: 10.3934/era.2023102
[3]
Donghyeon Kim, Jinsung Kim .
GPU-accelerated non-dominated sorting genetic algorithm III for maximizing protein production. Electronic Research Archive, 2024, 32(4): 2514-2540.
doi: 10.3934/era.2024116
[4]
Ming Wei, Congxin Yang, Bo Sun, Binbin Jing .
A multi-objective optimization model for green demand responsive airport shuttle scheduling with a stop location problem. Electronic Research Archive, 2023, 31(10): 6363-6383.
doi: 10.3934/era.2023322
[5]
Seongmin Park, Juneyoung Park, Youngkwon Yoon, Jinhee Kim, Jaehyun So .
Operation standards for exclusive bus lane on expressway using simulation and traffic big data. Electronic Research Archive, 2024, 32(4): 2323-2341.
doi: 10.3934/era.2024106
[6]
Gang Cheng, Changliang He .
Analysis of bus travel characteristics and predictions of elderly passenger flow based on smart card data. Electronic Research Archive, 2022, 30(12): 4256-4276.
doi: 10.3934/era.2022217
[7]
Wenjie Wang, Suzhen Wen, Shen Gao, Pengyi Lin .
A multi-objective dynamic vehicle routing optimization for fresh product distribution: A case study of Shenzhen. Electronic Research Archive, 2024, 32(4): 2897-2920.
doi: 10.3934/era.2024132
[8]
Donghyeon Kim, Jinsung Kim .
Optimization of designing multiple genes encoding the same protein based on NSGA-II for efficient execution on GPUs. Electronic Research Archive, 2023, 31(9): 5313-5339.
doi: 10.3934/era.2023270
[9]
Shiqi Zou, Xiaoping Shi, Shenmin Song .
MOEA with adaptive operator based on reinforcement learning for weapon target assignment. Electronic Research Archive, 2024, 32(3): 1498-1532.
doi: 10.3934/era.2024069
[10]
Chao Ma, Hong Fu, Pengcheng Lu, Hongpeng Lu .
Multi-objective crashworthiness design optimization of a rollover protective structure by an improved constraint-handling technique. Electronic Research Archive, 2023, 31(7): 4278-4302.
doi: 10.3934/era.2023218
Abstract
The current public transportation systems predominantly rely on rigid schedules and service patterns, leading to suboptimal resource allocation that impacts both passengers and transit operators. This inefficiency results in the wastage of resources and dissatisfaction among users. The unsatisfactory passenger experience significantly contributes to the declining ridership, thereby diminishing revenue for transit operators. To specifically address these challenges encountered by Lhasa's public transportation system, we propose a multi-objective model for bus departure timetables. The model aims to synchronize the costs of passenger waiting time and bus operation costs concurrently, accounting for diverse constraints such as actual travel times, operational bus numbers, bus capacity limits, and arrival time distributions. In this research, we establish a multi-objective optimization model with the primary goal of maximizing passenger satisfaction while concurrently optimizing the revenue of the transit company. Implemented in Lhasa, China, we use the Non-Dominated Sorting Genetic Algorithm-Ⅱ to derive Pareto fronts relevant for analysis. The research findings demonstrate a reduction in the frequency of departures by one bus within a one-hour timeframe. Additionally, a substantial 37% decrease is observed in both the count of buses not arriving at stations and the number of passengers waiting at these stations compared to previous timetables. These results suggest promising potential for significant benefits to both the transit company and passengers within the public transportation system.
1.
Introduction
Urban transit vehicles play a vital role in urban public transportation, and implementing systematic service standards for bus operations is essential to enhance their attractiveness. Among these, the effectiveness of bus operation services is predominantly dependent upon bus network planning. However, there is considerable complexity in this global planning issue, and it is typically broken down into a series of subproblems to address, including route planning, timetable generation, vehicle scheduling, and crew scheduling [1,2]. These subproblems are often addressed sequentially [3]. Since the generation of timetables for bus departures is a critical phase, its solutions determine the quality of service and subsequent subproblems, such as vehicle and personnel scheduling. The problem of generating the bus departure timetable involves designing departure times for each trip on all routes within the bus network, with the objective of maximizing service quality.
When decision-makers are formulating bus timetables, they must consider passenger needs, including the reduction of waiting times, the increase in service frequency, and the improvement of punctuality. These factors contribute to enhancing the passenger travel experience and increasing their satisfaction with the public transit system. Furthermore, a well-planned timetable can reduce buses' deadheading and waiting times, thereby increasing vehicle utilization. This results in decreased operational costs and increased profits for the transit company. By providing increased service frequency and ensuring punctual arrivals, the public transit system becomes more attractive, encouraging more people to use public transportation and reducing private car usage. One method, for example, is multi-objective optimization involving various vehicle types [4]. This, in turn, helps to mitigate traffic congestion and reduces environmental pollution. An efficient timetable aims to minimize the gap between buses, thereby mitigating traffic congestion and reducing delays on the roadways. This, enhances the overall efficiency of urban transportation.
Appropriate headways between bus departures can assist passengers in reducing their waiting times, enhancing travel efficiency, and effectively planning their journeys, ultimately resulting in enhanced passenger satisfaction. This is crucial for the sustainable development of public transportation systems, as satisfied passengers are more likely to choose buses as their mode of travel. This choice contributes to the reduction of urban traffic congestion and the improvement of environmental quality. Simultaneously, public transit companies and transportation authorities must also take into account the efficiency and sustainability of bus operations. The calculation of appropriate headways plays a significant role in the optimization of bus fleet scheduling and operations, aiming to reduce waste and congestion resulting from excessively long or short intervals between vehicles. However, there are certain drawbacks to traditional bus scheduling systems, including the practice of setting fixed time intervals between two consecutive bus departures, typically adjusted by experienced staff [5]. In practice, the utilization of fixed timetables can lead to instances where buses operate without passengers during periods of low demand or on routes with minimal passenger volume, thereby resulting in the inefficient use of resources and energy. This has adverse effects on both the environment and operating costs. Buses operating on fixed timetables during peak hours may experience traffic congestion, leading to delays and unreliable services. This can impact the passenger travel experience. Moreover, fixed timetables are often challenging in accommodating unforeseen circumstances, such as accidents or adverse weather, potentially resulting in service interruptions or delays.
To address these limitations, some cities and transportation systems are exploring alternative bus service models, such as on-demand bus services, real-time scheduling systems, and shared mobility solutions, to better cater to the ever-changing passenger demands [6]. These methods can enhance efficiency, mitigate congestion, and offer increased flexibility in travel options. Cheng and He [7] employed this method to address the issue by utilizing smart card data in public transit to identify distinct user profiles, thereby facilitating the creation of flexible timetables tailored to their respective needs. Fixed bus timetables often face challenges in accommodating diverse passenger requirements [8]. Therefore, through the employment of non-fixed bus headways, we can enhance our ability to accommodate fluctuations in demand at different times and locations. Buses, during peak and off-peak periods, have the capability to dynamically modify their departure times to meet the specific demands of passengers and maintain a sufficient supply of buses. This system can reduce congestion and waiting times, enhancing the overall efficiency of the public transit system. The implementation of this flexible departure system facilitates the reduction of passenger waiting durations and operational costs within the transit system. Furthermore, it assists in the minimization of resource and fuel waste, while optimizing vehicle utilization. Consequently, this enhances passenger satisfaction as it eliminates the need for extended periods for buses and enables them to easily schedule their travel based on their own schedules. It is worth noting that this optimization model considers the interests of both the transit operator and passengers, as finding a balance between these competing objectives is one of the most challenging aspects of model optimization.
1.1. Literature review
In recent decades, significant progress has been made in the research on bus scheduling optimization, leading to the establishment of a relatively comprehensive research framework. This field has evolved beyond a single-objective focus and has become more diverse, with an emphasis on resolving multi-objective problems. The application of these multi-objective approaches has enhanced the comprehensiveness of bus scheduling solutions, facilitating the simultaneous consideration of multiple crucial factors, such as the reduction of passenger waiting durations, enhancement of efficiency, cost reduction, and mitigation of adverse environmental impacts [9,10]. The primary advantage of these multi-objective methods resides in their ability to enhance the balance of trade-offs among diverse objectives, thereby increasing the adaptability of public transportation systems to the needs and challenges encountered in different cities [11]. Researchers can enhance their ability to meet the travel requirements of urban residents by considering not only temporal efficiency but also factors such as passenger satisfaction and economic viability [12,13]. This approach also facilitates the reduction of traffic congestion, the enhancement of urban sustainability, and the decrease in the consumption of fuel and resources, leading to a reduction in negative environmental impacts [14].
Moreover, the application of multi-objective methods has encouraged the advancement of innovative optimization algorithms, such as genetic algorithms (GAs), particle swarm optimization, simulated annealing, and others. These algorithms are better at handling complex multi-objective optimization problems [15,16]. This advancement further drives research and applications in the field of bus scheduling optimization, contributing to enhanced efficiency and sustainability in urban transportation planning.
In summary, multi-objective bus scheduling optimization methods have become integral to modern urban public transportation planning. They provide urban residents with a more convenient, comfortable, and environmentally friendly mode of travel [17].
An important emphasis and challenge in the investigation of multimodal bus scheduling is the effective integration and coordination of diverse types of public transportation services to provide a more comprehensive, efficient, and convenient public transit system. This includes considering various modes such as traditional public bus services, light rail, subway, trams, taxis, and shared mobility solutions [18]. In a multimodal environment, passengers are required to perform intermodal transfers between different transportation modes. Research should address how to minimize waiting and transfer times to enhance the user experience [19], ensuring that schedules for different modes are coordinated to reduce passenger wait times and improve connectivity. To do so, the comprehensive consideration of multiple schedules and frequencies is needed [20,21,22]. Furthermore, information sharing is critical in multimodal bus scheduling research because the coordination and integration of various public transportation modes necessitates real-time, accurate information flow. Several scholars have investigated the information sharing aspects related to bus scheduling [23,24,25].
Information sharing is critical in research on multi-modal public transit scheduling because the coordination and integration of different modes of public transportation require real-time and accurate information flow. Information sharing can involve multiple levels [26]. First, passengers need to access information about different transportation modes, including schedules, routes, fares, transfer guides, and more [27,28,29]. This can be achieved through mobile applications, websites, signage, and announcements [30]. To plan their journeys more effectively, passengers should be able to easily access and comprehend this information [31]. Second, the real-time monitoring of vehicle locations across various transportation modes is imperative for both passengers and operators. This information can be obtained through GPS and IoT technology and subsequently exhibited on applications and screens at stations and vehicles to provide real-time vehicle location information [32,33,34,35]. Furthermore, operators must share operational data to enhance the coordination of schedules and allocation of resources for various transportation modes. This includes sharing traffic flow data, vehicle dispatch information, site load data, and other relevant data sources [36]. In the event of emergencies or traffic issues, sharing of critical information in real-time is essential among different transportation modes to aid passengers and operators in resolving the issues.
The optimization problem of bus departure scheduling is a multi-objective optimization problem with inherent complexity, characterized by conflicting objectives. Table 1 presents the optimization objectives associated with the multi-objective bus departure scheduling optimization problem and the methods utilized by scholars.
Table 1.
Descriptive summary of the most relevant and recent research on using different algorithms to solve bus timetable problems with different objectives.
Inter-city bus routing and timetable setting under stochastic demands
A stochastic demand scheduling model is established considering the random perturbations of passengers' daily demands in actual operations. Two heuristic algorithms were developed to solve the model by applying simulation techniques and combining link-based and path-based routing strategies.
User perspectives on public transport timetable optimization
An approach was proposed to address timetable optimization with the aim of minimizing passenger waiting times during bus transfers. This problem was solved by applying a Tabu Search algorithm.
Robust timetable optimization for bus lines subject to resource and regulatory constraints
Combining travel time and passenger demand uncertainties to generate robust timetables, a genetic algorithm was used to solve the resulting minimax problem.
Distributed Multiagent Deep Reinforcement Learning for Multiline Dynamic Bus Timetable Optimization
The multi-line dynamic bus timetable optimization problem was treated as a Markov decision process model, and a distributed reinforcement learning algorithm was employed to solve this problem.
Single bus line timetable optimization with big data: A case study in Beijing
A timetable optimization model was developed, considering passenger demand between stations and travel times. A model reduction method was proposed to solve medium-scale problems.
In Table 1, the prevailing approach often involves amalgamating multiple objectives into a singular objective through weighted combinations, followed by employing single-objective optimization methods to solve the problem. However, assigning appropriate weights to each objective is often intricate and lacks a straightforward methodology [37]. Consequently, researchers have increasingly turned to heuristic algorithms as a means of addressing multi-objective problems. Renowned algorithms in this realm include GAs, tabu search, simulated annealing, and particle swarm optimization. Heuristic algorithms, equipped with global search capabilities, have exhibited prowess in achieving a trade-off between solution quality and computation time, particularly in intricate optimization scenarios.
1.2. Objectives and contributions
The literature review suggests a limited number of studies focusing on multi-objective optimization models specifically addressing the optimization challenges associated with bus scheduling. Limited studies delve into the intricacies of scheduling concerning this context, which inherently poses an optimization challenge. Hence, our study aims to address three primary objectives. First, we construct a multi-objective model aimed at synchronizing passenger waiting time costs and bus operational expenses, factoring in various constraints such as actual travel durations, bus route numbers, capacity limitations, and arrival time distributions. This model aims to leverage the Non-Dominated Sorting Genetic Algorithm-Ⅱ (NSGA-Ⅱ) to obtain the Pareto front. Second, we have developed a resolution methodology to filter out, from the Pareto front obtained through the NSGA-Ⅱ algorithm, a solution that simultaneously considers the costs associated with passenger waiting time and bus operational expenses. Subsequently, we execute numerical experiments and perform sensitivity analyses to evaluate both the efficacy and efficiency of the proposed model. This enables us to scrutinize the repercussions of parameter variations. The theoretical and pragmatic contributions stemming from our investigation are delineated hereunder.
Theoretical Contribution: There is a scarcity of multi-objective optimization models for optimizing bus scheduling timetables. Our dual-objective integer programming model minimizes passenger waiting time and bus operation costs simultaneously while considering various constraints such as actual travel times, operational bus numbers, bus capacity limits, and arrival time distributions. We employ the NSGA-Ⅱ algorithm to solve our proposed model. Numerical experiments demonstrate the effectiveness of the proposed model and solution approach in devising an efficient bus departure timetable considering passenger waiting time and bus operation costs while minimizing the number of bus departures.
Practical Contribution: In Lhasa, the current fixed bus departure schedules and service patterns result in inefficiencies, leading to resource wastage and user dissatisfaction. Our research not only minimizes passenger waiting times but also aims to reduce the overall operational costs of the bus company.
The rest of this paper is organized as follows: Section 2 provides a detailed description of the problem. Section 3 presents the model and solution approach to address this issue. Section 4 describes numerical experiments that were conducted to validate the effectiveness and applicability of the proposed methods. The conclusion is presented in Section 5.
2.
Problem description
To facilitate the simulation of the train timetable problem considered in this study, the relevant sets, indices, parameters, and decision variables are outlined in Table 2.
Table 2.
Notations.
Sets
I
Set of bus stations
N
Set of buses
T
Set of time periods
Parameters
i
Bus station index, i∈I
n
Bus index, n∈N
t
Index of times, t∈T
λi
Passenger Arrival Rate at Station i
Din
Departure time of the n th vehicle at station i
tin
Time of arrival of the n th vehicle at station i
dij
Distance from station i to station j
L
The total length of the selected bus route
v
Average speed
β
Boarding and alighting time
μi
Passenger Alighting Rate at Station i
Qin
The number of passengers on board when the n th vehicle departs from station i
C1
Ticket fee for a passenger on a bus
C2
Unit operating costs of buses
C3
Passenger time cost
Dmax
Maximum Departure Interval
Decision variables
xit
Binary variable {0,1}, xit=1, when bus n departs at the end of time t; otherwise, xit=0, where i∈I and t∈T
xn
Binary variable {0,1}, xn=1, when bus n is selected for operation; otherwise, xn=0, where n∈N
Consider an individual bus route with bus stops represented as i∈I. Typically, each bus service operates in two opposing directions. This situation can be regarded as the optimization of two independent bus routes, as the passenger volumes for the two directions are uncorrelated within the same time frame. The optimization objective of this paper is now focused on a single route.
Buses receive service scheduling instructions from the control center and depart from the originating station (i=1) towards the terminating station (i=S). All service details, such as departure times Din and scheduled arrival times tin, can only be confirmed when the bus commences its service.
In the context of a data survey, the manual collection of passenger arrival times at different bus stations for a group of passengers is a significant and complex task. It should be noted that the calculation method for passenger waiting durations varies based on the type of arrival time distribution. To simplify this problem, it is assumed that the arrival times of passengers adhere to an identical distribution across various bus stations. Passenger arrival at bus stations and waiting for buses can be modeled as a queuing problem, and queueing theory can estimate the time distribution of passenger arrivals. In practical applications, the probability distribution of customer arrival times often encompasses a Poisson distribution, exponential distribution, and Erlang distribution [38]. Assuming the events are independent, a Poisson distribution is a widely used model for representing passenger arrival patterns. In our application, it is assumed that passenger arrival times approximately adhere to a Poisson distribution, given the smooth, independent, and general nature of passenger flows to each station.
To facilitate the formalization of the model, the following assumptions are suggested to simplify the modeling procedure:
Assumption 1. All passengers are rational travelers and will board the first available bus that meets their requirements. Furthermore, they will not board more than one bus.
Assumption 2. The bus route is a continuous one-way service, and all buses have the same average speed.
3.
Methodology
3.1. Objective function
In this study, the primary focus is on establishing a framework for bus departure scheduling, encompassing cost models and optimization algorithms, while considering actual travel times, passenger arrival distributions, and vehicle capacity constraints. This section presents an optimization approach for the bus departure schedule problem aimed at minimizing the integrated costs incurred by both the bus company and passengers. The specific steps are enumerated below.
Step 1: Cost Model
Step 1.1: Passenger Income Value
Given that P(t) represents the Poisson distribution probability and D(t) represents the number of people arriving at the i-th station in the t-th minute, Eqs (1) and (2) can be constructed as follows:
P(t)=λti⋅e−λit!
(1)
D(t)=P(t)⋅(Din−t)⋅λi
(2)
Equation (3) can be used to calculate the bus arrival time at the platform after waiting for passengers to board and alight. The departure time is given by the sum of the previous departure time, the travel time between stops, and the waiting time at the platform. It is assumed that the duration of time required for passengers to board and alight at each station remains constant.
Din=∑t∈Txitt+d1i+L(n−1)v+β(i−1+Sm−S)
(3)
Equation (4) calculates the number of passengers alighting at the i-th station, while Eq (5) describes the number of passengers boarding at the i-th station accordingly.
Ain=Q(i−1)n⋅μi
(4)
Bin=min(M+Ain−Q(i−1)n,(Din−Di(n−1))⋅λi)
(5)
Equation (6) calculates the passenger revenue value, which comprises two components: the fare paid by passengers for taking the bus and the cost associated with passenger waiting time.
Equation (7) computes the revenue of the bus company, comprising the aggregate fare collected from passengers utilizing the bus and the operational costs associated with the bus service.
Step 1.3: Multi-Objective Optimization Model
Based on the two cost models, the objective of the problem is to combine the two main factors, namely passenger waiting time cost and bus operational cost, to form a multi-objective optimization problem. A mixed optimization model is then formulated with the objective of minimizing the integrated cost, aiming to formulate a rational scheduling plan as depicted in Eq (8).
maxxit,xnF:=[F1,F2]
(8)
xin(1)=Ef
(9)
xin(S)=El
(10)
3.2. Constraints
Assuming that the departure times for the first and last frequencies correspond to the beginning and end of the time period, we can establish Constraints (9) and (10).
Constraint (11) ensures that buses depart in sequence:
xin(1)≤x(i+1)n(1)
(11)
Constraint (12) represents the departure interval constraint:
0≤xin≤Dmax
(12)
3.3. Coding rules
The problem of double-layer programming is classified as a non-convex optimization problem. Simplest linear double-layer programming problems have been proven to be NP-hard. The challenge in double-layer optimization resides in the nested structure of the problem, wherein the upper and lower problems are influenced by each other's decision variables. Double-layer optimization problems are much more challenging than regular single-level mathematical optimization problems. The NSGA-Ⅱ algorithm can be selected as the elite strategy to solve this model. The algorithm's implementation is carried out in MATLAB, following these specific steps.
Step 1: Initialization. Randomly allocate an initial population xin(t) and n for the departure strategy.
Step 2: Calculate the fitness function. For a given set of xin(t) and n, substitute them into the F1 and F2 functions to obtain fitness values.
Step 3: Non-dominated sorting. For the newly generated population, perform non-dominated sorting based on fitness values. If p dominates q, then, q∈Sq. When applying the selection operator, populations that are ranked lower will be eliminated first.
Step 4: Crowding distance calculation. The crowding distance value of the maximum and minimum fitness values is defined as 0. For the intermediate individuals, the crowding distance is calculated as the absolute value of the difference between the next value and the previous value, divided by the difference between the maximum and minimum values, and then the absolute value is taken. Compute the summation of the crowding distances at the same index to obtain the total crowding distance of the population.
Step 5: Forming the Pareto front: By employing the results obtained in Steps 1 to 4, generate the initial population for the NSGA-Ⅱ algorithm, followed by executing selection, crossover, and mutation operations on the population. When the stopping condition is met (for example, reaching the maximum number of generations or a time limit), the Pareto front is formed.
4.
Case study
4.1. Test case description
The data utilized in this study was obtained from Lhasa City, China. Bus route 34 was selected for the case study. The bus route consists of 22 bus stations, spans a total distance of 10.6 kilometers, and operates from 6:40 to 20:50. The distances between stations are presented in Table 3.
The bus company has seven buses in its fleet. Upon receipt of the departure instructions, a bus departs from the originating station and proceeds in one direction. The case simulation had a total runtime of 60 minutes. The parameter values and their sources utilized in this case are presented in Table 4.
The NSGA-Ⅱ algorithm is a multi-objective optimization algorithm that has been successfully utilized in the domain of public transportation. The optimization method proposed in this work was implemented using MATLAB 2021b. The experiments were conducted on a computer equipped with 4 GB of memory, an Intel i3 3.70 GHz CPU, and the Microsoft Windows 10 operating system.
4.2. Parameter adjustment
As shown in Table 5, four different values are assigned to the best individual factor. The table indicates that when the Pareto score is 0.35, the proportion of credible Pareto optimal solutions obtained as a percentage of total results is the highest. Therefore, the value of 0.35 is selected as the best individual factor.
Table 5.
Mean extremes of the Pareto Front across various Pareto Fractions.
In Table 6, four different crossover rates can be examined. When the crossover rate is set to 0.85 and 0.90, two peaks are observed in the ratio of the number of approximately correct Pareto optimal solutions to the total obtained results. Since the latter is larger and has a shorter runtime, the crossover rate is selected as 0.90.
Table 6.
Mean extremes of the Pareto Front across various Crossover Fractions.
In Table 7, a sensitivity analysis was conducted on five different mutation probabilities with a fixed crossover probability of 0.9. Setting the mutation probability to 0.03 resulted in a limited local search capability. While a mutation probability of 0.07 led to a loss of solutions. Therefore, a mutation probability of 0.05 was chosen as it struck a balance between search capability and computational efficiency, providing an appropriate compromise in terms of both time consumption and solution search ability.
Table 7.
Mean extremes of the Pareto Front across various Mutation Fractions.
In Table 8, a sensitivity analysis was performed concerning the impact of varying iteration counts while maintaining a fixed crossover probability of 0.9. Setting the iteration count to 100 resulted in excessively slow convergence, affecting the model's efficiency. Conversely, at an iteration count of 500, computational demands were noticeably high without a proportional improvement in convergence. After careful analysis, an iteration count of 300 was selected, striking a balance between convergence speed and computational efficiency. This count optimally balances the trade-off between the time required for convergence and the computational resources expended, ensuring a reasonably efficient solution-searching process.
Table 8.
Average boundary values of the Pareto front regarding the mutation ratio.
Based on the provided optimal parameter settings, the program was executed to solve the established model. To mitigate the impact of randomness on the obtained results, due to the stochastic nature of the algorithm, the program was executed in a total of five independent trials. Figure 1 illustrates the six different Pareto fronts obtained from the five independent runs, which comprise a total of 282 non-dominant cases.
Figure 1.
Multi round Pareto optimal solution set.
The results from the five different runs were integrated into a new Pareto front, exclusively comprising solutions that are not dominated in relation to the combined results, as shown in Figure 1. The integrated Pareto front comprises a total of 238 cases.
As shown in Figure 1, there is a negative correlation between the revenue value of the transit operator and the revenue value of passengers. In this scenario, the Pareto frontier is defined as the optimal state in which the operator can achieve maximum revenue by implementing rational pricing strategies that simultaneously satisfy the needs of passengers. This implies that the operator can increase fares to achieve higher revenue as the value to passengers increases. However, achieving this ideal state is often challenging in practice because operators need to balance pricing with passenger satisfaction to maintain sustainable business operations. Therefore, the primary challenge in the Pareto frontier lies in achieving a trade-off that enables the maximization of revenue while maintaining passenger satisfaction. This analysis helps operators optimize fare strategies for the best economic outcomes.
Here we investigated the time period of the morning peak hours spanning from 7:00 to 8:00. The bus headway, as shown in Figure 2(a), initially had a frequency of 6 with a 10-minute headway. After optimization, it transformed into the headway schedule shown in Figure 2(b), with a reduced frequency of 5. Figure 3(a) shows the distribution of passengers who had not yet boarded and those waiting at each bus stop under the condition of a uniform headway of 10 minutes for six trips. The related slopes of the passenger cumulative curve in Figure 3(b) indicate that, following adjustment, there was an increase in passengers yet to board and waiting at the first departure. However, for subsequent departures, owing to the optimized timetable, it is evident that the number of passengers significantly decreased in comparison to the original schedule.
Figure 3.
(a) Initial program three-dimensional view of the number of people not entering the station + waiting. (b) Optimization program three-dimensional view of the number of people not entering the station + waiting.
In this study, we considered multiple crucial factors, such as actual travel times, bus capacity constraints, and passenger arrival time distributions, to address the urban bus scheduling problem with the objective of minimizing the total costs for passengers and the transit company. The NSGA-Ⅱ method was employed to handle complex constraints to explore the Pareto frontier using two objective functions. The objective was to identify bus departure timetables for various scenarios.
1) Given the assumption that passenger arrival times follow a Poisson distribution, this study holds significant value in optimization urban public transit systems. This assumption, based on a comprehensive analysis of actual data, provides a more efficient approach and theoretical foundation for minimizing overall costs. By gaining a comprehensive understanding of the distribution characteristics of passenger arrival times, it is possible to improve the accuracy of bus route planning, schedule adjustments, and resource allocation in order to meet urban transportation demands and enhance operational efficiency. Thus, this study holds potential significance for improving the sustainability and effectiveness of public transportation systems.
2) Calculating passenger waiting times must be more comprehensive and accurate when facing limited bus capacity. This is attributed not solely to the need of considering factors associated with the distribution of passenger arrival times, but also to the requirement of accounting for the carrying capacity of buses, thereby ensuring the prevention of overloading during operations. This integrated approach significantly reduces waiting times and overcrowding, which enhances the efficiency and service quality of urban public transit systems. Specifically, by integrating the passenger arrival time distribution with the bus capacity, the accuracy of determining bus departure intervals and stopping points can be enhanced. This effectively reduces waiting times as passengers are not required to wait excessively long for a bus.
3) Ensuring that buses do not become overloaded during peak hours is essential for enhancing passenger comfort and safety, and has the added benefit of mitigating congestion and discomfort. This comprehensive approach enhances the accessibility of urban public transit systems, attracting a larger number of individuals to utilize public transportation, mitigating urban traffic congestion, and contributing to the city's sustainable development.
Despite the achievements of this study, certain limitations persist. First, relying on a Poisson distribution for passenger arrival times might necessitate more substantial empirical backing from datasets such as GPS trajectories, IC card records, and video data to precisely emulate real-world scenarios. Second, the study's use of travel times does not account for actual road traffic conditions. Future research could focus on advancing scheduling optimization techniques by integrating real-time traffic data to enhance accuracy. Moreover, we focus on buses, lacking an extensive exploration of integration with other forms of public transportation. Incorporating real-time traffic data could significantly enhance the model's adaptability and efficiency in dynamic urban environments.
In conclusion, we present a robust method and insights for optimizing urban public transit systems. However, it also highlights the need for additional actual data and refined modeling to address more complex issues in future investigations. These efforts will help enhance urban transportation systems, improve passenger travel experience, and mitigate operating costs for transit companies.
Use of AI tools declaration
The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.
Acknowledgments
This research was supported by the National Natural Science Foundation of China (Grant No. 51968063), Research on Key Technologies of Traffic Organization in Xizang Plateau (Grant No. XZ202303ZY0005G), Academic development support program for young doctors of Tibet University (No. zdbs202212), Himalayan human activities and regional development collaborative innovation construction center project (No. 00060872) and Zangcai Yuzhi [2023] No.1 Central Support for the Construction of a Comprehensive Discipline Innovation Platform Project Supported by Local Departments and Regions-High Altitude Traffic Incident Assessment and Emergency Exercise Platform Construction Project.
Conflict of interest
The authors declare that there are no conflicts of interest.
References
[1]
A. Ceder, B. Golany, O. Tal, Creating bus timetables with maximal synchronization, Transp. Res. Part A: Policy Pract., 35 (2001), 913–928. https://doi.org/10.1016/S0965-8564(00)00032-X doi: 10.1016/S0965-8564(00)00032-X
[2]
V. Guihaire, J. K. Hao, Transit network design and scheduling: A global review, Transp. Res. Part A: Policy Pract., 42 (2008), 1251–1273. https://doi.org/10.1016/j.tra.2008.03.011 doi: 10.1016/j.tra.2008.03.011
[3]
G. Laporte, Scheduling issues in vehicle routing, Ann. Oper. Res., 236 (2016), 463–474. https://doi.org/10.1007/s10479-013-1423-3 doi: 10.1007/s10479-013-1423-3
[4]
P. Lin, C. He, L. Zhong, M. Pei, C. Zhou, Y. Liu, Bus timetable optimization model in response to the diverse and uncertain requirements of passengers for travel comfort, Electron. Res. Arch., 31 (2023), 2315–2336.. http://dx.doi.org/10.3934/era.2023118 doi: 10.3934/era.2023118
[5]
J. Tang, Y. Yang, W. Hao, F. Liu, Y. Wang, A data-driven timetable optimization of urban bus line based on multi-objective genetic algorithm, IEEE Trans. Intell. Transp. Syst., 22 (2020), 2417–2429. https://doi.org/10.1109/TITS.2020.3025031 doi: 10.1109/TITS.2020.3025031
[6]
M. Pei, P. Lin, R. Liu, Y. Ma, Flexible transit routing model considering passengers' willingness to pay, IET Intell. Transp. Syst., 13 (2019), 841–850. https://doi.org/10.1049/iet-its.2018.5220 doi: 10.1049/iet-its.2018.5220
[7]
G. Cheng, C. He, Analysis of bus travel characteristics and predictions of elderly passenger flow based on smart card data, Electron. Res. Arch., 30 (2022), 4256–4276. https://doi.org/10.3934/era.2022217 doi: 10.3934/era.2022217
[8]
S. Hassold, A. C. Avishai, Public transport vehicle scheduling featuring multiple vehicle types, Transp. Res. Part B: Methodol., 67 (2014), 129–143. https://doi.org/10.1016/j.trb.2014.04.009 doi: 10.1016/j.trb.2014.04.009
[9]
X. Yang, L. Liu, A multi-objective bus rapid transit energy saving dispatching optimization considering multiple types of vehicles, IEEE Access, 8 (2020), 79459–79471. https://doi.org/10.1109/ACCESS.2020.2989334 doi: 10.1109/ACCESS.2020.2989334
[10]
X. Yang, Y. Qi, Research on optimization of multi-objective regional public transportation scheduling, Algorithms, 14 (2021), 108. https://doi.org/10.3390/a14040108 doi: 10.3390/a14040108
[11]
S. B. Jha, K. J. Jitendra, K. T. Manoj, A multi-objective meta-heuristic approach for transit network design and frequency setting problem in a bus transit system, Comput. Ind. Eng., 130 (2019), 166–186. https://doi.org/10.1016/j.cie.2019.02.025 doi: 10.1016/j.cie.2019.02.025
[12]
M. Wei, S. Zhang, B. Sun, Comprehensive operating efficiency measurement of 28 Chinese airports using a two-stage DEA-Tobit method, Electron. Res. Arch., 31 (2023), 1543–1555. https://doi.org/10.3934/era.2023078 doi: 10.3934/era.2023078
[13]
M. Wei, S. Zhang, T. Liu, B. Sun, The adjusted passenger transportation efficiency of nine airports in China with consideration of the impact of high-speed rail network development: A two-step DEA-OLS method, J. Air Transp. Manage., 109 (2023), 102395. https://doi.org/10.1016/j.jairtraman.2023.102395 doi: 10.1016/j.jairtraman.2023.102395
[14]
M. H. Miandoab, G. Vahidreza, M. Davood, Developing a simultaneous scheduling of passenger and freight trains for an inter-city railway considering optimization of carbon emissions and waiting times, J. Cleaner Prod., 248 (2020), 119303. https://doi.org/10.1016/j.jclepro.2019.119303 doi: 10.1016/j.jclepro.2019.119303
[15]
H. Wang, Y. Wen, S. Wang, Facility planning and schedule design in the pandemic: Eliminating contacts at construction workplace, J. Cleaner Prod., 395 (2023), 136394. https://doi.org/10.1016/j.jclepro.2023.136394 doi: 10.1016/j.jclepro.2023.136394
[16]
H. Wang, R. Yan, S. Wang, L. Zhen, Innovative approaches to addressing the tradeoff between interpretability and accuracy in ship fuel consumption prediction, Transp. Res. Part C: Emerging Technol., 157 (2023), 104361. https://doi.org/10.1016/j.trc.2023.104361 doi: 10.1016/j.trc.2023.104361
[17]
C. Wang, Z. Ye, W. Wang, A multi-objective optimization and hybrid heuristic approach for urban bus route network design, IEEE Access, 8 (2020), 12154–12167. https://doi.org/10.1109/ACCESS.2020.2966008 doi: 10.1109/ACCESS.2020.2966008
[18]
Z. Jun, Initial boundary value problem for a inhomogeneous pseudo-parabolic equation, Electron. Res. Arch., 28 (2020), 67–90. https://doi.org/10.3934/era.2020005 doi: 10.3934/era.2020005
[19]
Y. Liu, F. Wu, C. Lyu, S. Li, J. Ye, X. Qu, Deep dispatching: A deep reinforcement learning approach for vehicle dispatching on online ride-hailing platform, Transp. Res. Part E: Logist. Transp. Rev., 161 (2022), 102694. https://doi.org/10.1016/j.tre.2022.102694 doi: 10.1016/j.tre.2022.102694
[20]
Y. Bie, R. Tang, Z. Liu, D. Ma, Mixed scheduling strategy for high frequency bus routes with common stops, IEEE Access, 8 (2020), 34442–34454. https://doi.org/10.1109/ACCESS.2020.2974740 doi: 10.1109/ACCESS.2020.2974740
[21]
Y. Bie, M. Hao, M. Guo, Optimal electric bus scheduling based on the combination of all-stop and short-turning strategies, Sustainability, 13 (2021), 1827. https://doi.org/10.3390/su13041827 doi: 10.3390/su13041827
[22]
B. Hu, X. Wang, W. Chen, Study on combinational scheduling between inter-zone vehicle and regular vehicle for urban public transit, J. Wuhan Univ. Technol. (Transp. Sci. Eng.), 36 (2012), 1192–1195. https://api.semanticscholar.org/CorpusID:112197872
[23]
M. Kim, S. Paul, Conventional, flexible, and variable-type bus services, J. Transp. Eng., 138 (2012), 263–273. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000326 doi: 10.1061/(ASCE)TE.1943-5436.0000326
[24]
Z. Zhou, Z. Ye, Y. Xu, Optimizing combined bus service pattern and frequencies with genetic algorithm, in 18th COTA International Conference of Transportation Professionals. Reston, VA: American Society of Civil Engineers, 2018. https://doi.org/10.1061/9780784481523.088
[25]
Z. Ning, S. Sun, M. C. Zhou, X. Hu, X. Wang, L. Guo, et al., Online scheduling and route planning for shared buses in urban traffic networks, IEEE Trans. Intell. Transp. Syst., 23 (2021), 3430–3444. https://doi.org/10.1109/TITS.2020.3036396 doi: 10.1109/TITS.2020.3036396
[26]
Y. Liu, L. Wang, Z. Zeng, Y. Bie, Optimal charging plan for electric bus considering time-of-day electricity tariff, J. Intell. Connected Veh., 5 (2022), 123–137. https://doi.org/10.1108/JICV-04-2022-0008 doi: 10.1108/JICV-04-2022-0008
[27]
T. Liu, A. C. Avishai, Analysis of a new public-transport-service concept: Customized bus in China, Transp. Policy, 39 (2015), 63–76. https://doi.org/10.1016/j.tranpol.2015.02.004 doi: 10.1016/j.tranpol.2015.02.004
[28]
W. Zhang, H. Zhao, M. Xu, Optimal operating strategy of short turning lines for the battery electric bus system, Commun. Transp. Res., 1 (2021), 100023. https://doi.org/10.1016/j.commtr.2021.100023 doi: 10.1016/j.commtr.2021.100023
[29]
Y. Yang, Z. Z. Yuan, J. Y. Li, Y. H. Wang, W. C. Wang, Multi-mode public transit OD prediction and scheduling model, Adv. Transp. Stud., 2018 (2018). https://doi.org/10.4399/978882552166517 doi: 10.4399/978882552166517
[30]
S. I. Wahjono, A. Marina, M. Y. K. Bachok, M. Mochklas, The Importance of MPIS on RK for further ITS implementation in Malaysia, Int. J. Adv. Appl. Sci. (IJAAS), 4 (2017), 53–60. https://doi.org/10.21833/ijaas.2017.09.007 doi: 10.21833/ijaas.2017.09.007
[31]
J. Ji, Y. Bie, Z. Zeng, L. Wang, Trip energy consumption estimation for electric buses, Commun. Transp. Res., 2 (2022), 100069. https://doi.org/10.1016/j.commtr.2022.100069 doi: 10.1016/j.commtr.2022.100069
[32]
Y. Liu, E. Yao, S. Liu, Energy consumption optimization model of multi-type bus operating organization based on time-space network, Appl. Sci., 9 (2019), 3352. https://doi.org/10.3390/app9163352 doi: 10.3390/app9163352
[33]
G. J. Zhou, D. F. Xie, X. M. Zhao, C. Lu, Collaborative optimization of vehicle and charging scheduling for a bus fleet mixed with electric and traditional buses, IEEE Access, 8 (2020), 8056–8072. https://doi.org/10.1109/ACCESS.2020.2964391 doi: 10.1109/ACCESS.2020.2964391
[34]
X. Kong, M. Li, T. Tang, K. Tian, L. Moreira-Matias, F. Xia, Shared subway shuttle bus route planning based on transport data analytics, IEEE Trans. Autom. Sci. Eng., 15 (2018), 1507–1520. https://doi.org/10.1109/TASE.2018.2865494 doi: 10.1109/TASE.2018.2865494
[35]
X. Kong, F. Xia, J. Li, M. Hou, M. Li, Y. Xiang, A shared bus profiling scheme for smart cities based on heterogeneous mobile crowdsourced data, IEEE Trans. Ind. Inf., 16 (2019), 1436–1444. https://doi.org/10.1109/TII.2019.2947063 doi: 10.1109/TII.2019.2947063
[36]
A. Jahic, M. Plenz, M. Eskander, D. Schulz, Route scheduling for centralized electric bus depots, IEEE Open J. Intell. Transp. Syst., 2 (2021), 149–159. https://doi.org/10.1109/OJITS.2021.3096115 doi: 10.1109/OJITS.2021.3096115
[37]
X. Zuo, C. Chen, W. Tan, M. Zhou, Vehicle scheduling of an urban bus line via an improved multiobjective genetic algorithm, IEEE Trans. Intell. Transp. Syst., 16 (2014), 1030–1041. https://doi: 10.1109/TITS.2014.2352599 doi: 10.1109/TITS.2014.2352599
[38]
S. Yan, C. J. Chi, C. H. Tang, Inter-city bus routing and timetable setting under stochastic demands, Transp. Res. Part A: Policy Pract., 40 (2006), 572–586. https://doi.org/10.1016/j.tra.2005.11.006 doi: 10.1016/j.tra.2005.11.006
[39]
D. J. Sun, Y. Xu, Z. Peng, Timetable optimization for single bus line based on hybrid vehicle size model, J. Traffic Transp. Eng., 2 (2015), 179–186. https://doi.org/10.1016/j.jtte.2015.03.006 doi: 10.1016/j.jtte.2015.03.006
[40]
F. D. Wihartiko, A. Buono, B. P. Silalahi, Integer programming model for optimizing bus timetable using genetic algorithm, in IOP Conference Series: Materials Science and Engineering. Vol. 166. No. 1. IOP Publishing, 2017. https://doi.org/10.1088/1757-899X/166/1/012016
[41]
J. Parbo, O. A. Nielsen, C. G. Prato, User perspectives in public transport timetable optimization, Transp. Res. Part C: Emerging Technol., 48 (2014), 269–284. https://doi.org/10.1016/j.trc.2014.09.005 doi: 10.1016/j.trc.2014.09.005
[42]
K. Gkiotsalitis, F. Alesiani, Robust timetable optimization for bus lines subject to resource and regulatory constraints, Transp. Res. Part E: Logist. Transp. Rev., 128 (2019), 30–51. https://doi.org/10.1016/j.tre.2019.05.016 doi: 10.1016/j.tre.2019.05.016
[43]
H. Yan, Z. Cui, X. Chen, X. Ma, Distributed Multiagent Deep Reinforcement Learning for Multiline Dynamic Bus timetable optimization, IEEE Trans. Ind. Inf., 19 (2022), 469–479. https://doi.org/10.1109/TII.2022.3158651 doi: 10.1109/TII.2022.3158651
[44]
H. Ma, X. Li, H. Yu, Single bus line timetable optimization with big data: A case study in Beijing, Inf. Sci., 536 (2020), 53–66. https://doi.org/10.1016/j.ins.2020.03.108 doi: 10.1016/j.ins.2020.03.108
Gang Cheng, Yijie He. Enhancing passenger comfort and operator efficiency through multi-objective bus timetable optimization[J]. Electronic Research Archive, 2024, 32(1): 565-583. doi: 10.3934/era.2024028
Gang Cheng, Yijie He. Enhancing passenger comfort and operator efficiency through multi-objective bus timetable optimization[J]. Electronic Research Archive, 2024, 32(1): 565-583. doi: 10.3934/era.2024028
Table 1.
Descriptive summary of the most relevant and recent research on using different algorithms to solve bus timetable problems with different objectives.
Inter-city bus routing and timetable setting under stochastic demands
A stochastic demand scheduling model is established considering the random perturbations of passengers' daily demands in actual operations. Two heuristic algorithms were developed to solve the model by applying simulation techniques and combining link-based and path-based routing strategies.
User perspectives on public transport timetable optimization
An approach was proposed to address timetable optimization with the aim of minimizing passenger waiting times during bus transfers. This problem was solved by applying a Tabu Search algorithm.
Robust timetable optimization for bus lines subject to resource and regulatory constraints
Combining travel time and passenger demand uncertainties to generate robust timetables, a genetic algorithm was used to solve the resulting minimax problem.
Distributed Multiagent Deep Reinforcement Learning for Multiline Dynamic Bus Timetable Optimization
The multi-line dynamic bus timetable optimization problem was treated as a Markov decision process model, and a distributed reinforcement learning algorithm was employed to solve this problem.
Single bus line timetable optimization with big data: A case study in Beijing
A timetable optimization model was developed, considering passenger demand between stations and travel times. A model reduction method was proposed to solve medium-scale problems.
Inter-city bus routing and timetable setting under stochastic demands
A stochastic demand scheduling model is established considering the random perturbations of passengers' daily demands in actual operations. Two heuristic algorithms were developed to solve the model by applying simulation techniques and combining link-based and path-based routing strategies.
User perspectives on public transport timetable optimization
An approach was proposed to address timetable optimization with the aim of minimizing passenger waiting times during bus transfers. This problem was solved by applying a Tabu Search algorithm.
Robust timetable optimization for bus lines subject to resource and regulatory constraints
Combining travel time and passenger demand uncertainties to generate robust timetables, a genetic algorithm was used to solve the resulting minimax problem.
Distributed Multiagent Deep Reinforcement Learning for Multiline Dynamic Bus Timetable Optimization
The multi-line dynamic bus timetable optimization problem was treated as a Markov decision process model, and a distributed reinforcement learning algorithm was employed to solve this problem.
Single bus line timetable optimization with big data: A case study in Beijing
A timetable optimization model was developed, considering passenger demand between stations and travel times. A model reduction method was proposed to solve medium-scale problems.
Sets
I
Set of bus stations
N
Set of buses
T
Set of time periods
Parameters
i
Bus station index, i∈I
n
Bus index, n∈N
t
Index of times, t∈T
λi
Passenger Arrival Rate at Station i
Din
Departure time of the n th vehicle at station i
tin
Time of arrival of the n th vehicle at station i
dij
Distance from station i to station j
L
The total length of the selected bus route
v
Average speed
β
Boarding and alighting time
μi
Passenger Alighting Rate at Station i
Qin
The number of passengers on board when the n th vehicle departs from station i
C1
Ticket fee for a passenger on a bus
C2
Unit operating costs of buses
C3
Passenger time cost
Dmax
Maximum Departure Interval
Decision variables
xit
Binary variable {0,1}, xit=1, when bus n departs at the end of time t; otherwise, xit=0, where i∈I and t∈T
xn
Binary variable {0,1}, xn=1, when bus n is selected for operation; otherwise, xn=0, where n∈N
Figure 3. (a) Initial program three-dimensional view of the number of people not entering the station + waiting. (b) Optimization program three-dimensional view of the number of people not entering the station + waiting
DownLoad:
