Sage Journals: Discover world-class research

Abstract

Company commuter bus service (CCBS) is a convenient commuting mode provided for employees. which has always been popular because of its flexible route planning and low cost. Some companies offer CCBS to their employees for free. However, there are also some companies that need employees to pay the fare for CCBS. For fee-based CCBS, profit is an important consideration. Appropriate stop setting and route programming can attract more commuters and generate greater profits. This paper studies the stop selection and route planning for CCBS considering uncertain demand and travel time. In the data preparation phase, we propose an improved fuzzy c-means clustering to obtain appropriate clusters of commuters’ addresses. In the solution phase, we designed a collaborative framework for stop selection and route programming with the objective to maximize the profit of CCBS. A novel heuristic stochastic dynamic programming (H-SDP) method is then designed for the stop selection sub-problem considering the uncertainties of both traveling time and commuting demand. Meanwhile, we employ a variable neighborhood search algorithm with a novel shaking operation suitable for the routing problem. Finally, we conduct a series of computational experiments to demonstrate the effectiveness and efficiency of the developed algorithms.

Keywords

public transportation bus transit systems stops innovative public transportation services and technologies complimentary paratransit routing

Daily commuting is an important aspect of urban transportation. The urban spatial layout means that many large enterprises are concentrated in industrial parks along urban fringes, while residential areas are relatively scattered throughout the city. The many commuters and long commuting distances cause heavy traffic pressure on the urban transportation network ( 1 ). Company commuter bus service (CCBS) is a convenient commuting mode provided by a company for employees to improve commuting efficiency ( 2 ). CCBS has always been popular with commuters because typically there are few stops and the service is reliably punctual. Some companies offer CCBS for free to their employees. However, there are also some companies, such as Huawei, that require their employees to pay CCBS fares. For fee-based CCBS, the fare is usually low, similar to that of the bus service, and does not affect the employee’s choice of CCBS. Under the premise of constant fares, increasing the number of customers is an important consideration to ensure that a CCBS operation does not lose money. For fee-based CCBS, profit is an important consideration. Excellent stop setting and route programming can attract more commuters and generate greater profits.

Some uncertain factors are encountered in the process of vehicle service in CCBS, mainly in two aspects: uncertainty in travel time and in passenger demand. Travel time varies as vehicle speeds are affected by morning and evening peak hours and complex traffic conditions. Unexpected conditions, such as traffic congestion or weather, can also lead to uncertain travel times. Additionally, the passenger demand is uncertain. At the planning level, the company usually formulates its transportation routes before CCBS operation by counting employee preferences and car ownership. During the actual operation of CCBS, for employees with certain income and high requirements for convenience, individual factors will affect their choice of CCBS, which will result in frequent changes in the actual demand ( 3 ). Therefore, it is necessary to consider the uncertainty of demand in CCBS operations. According to the survey, the main factors affecting commuters’ willingness to choose CCBS are walking distance and vehicle travel time. However, the CCBS is strictly guaranteed to arrive at the company workplace no later than the working time window. Therefore, the willingness of commuters to choose the CCBS is mainly affected by the walking distance. For vehicle route planning, the location of the bus stop is particularly important for vehicle travel time. Too many stops may lead to longer driving distances and longer travel times, while fewer stops may lead to longer walking distance and fewer commuters choosing to use the service.

This study aims to propose an optimization framework that comprehensively considers the stochastic travel time, the probability of commuters choosing CCBS, the location of stops, and the cost of vehicles to obtain CCBS routes with maximum profit. Figure 1 illustrates an example of this problem. The trip with an origin and destination pair is expressed as $〈 o, d 〉$ . $m_{j}$ is the candidate stop. There are 18 candidate stops and 46 commuters, as shown in Figure 1. Candidate stops are located on the main road or at an intersection. The two commuting buses provide commuting services. We designed two routes $R_{1} 〈 m_{1}, m_{5}, m_{6}, m_{8} 〉$ and $R_{2} 〈 m_{2}, m_{3}, m_{7}, m_{10} 〉$ for bus $k_{1}$ and two other routes $R_{3} 〈 m_{11}, m_{15}, m_{17} 〉$ and $R_{4} 〈 m_{12}, m_{14}, m_{18} 〉$ for bus $k_{2}$ . We can observe that route $R_{2}$ has a shorter distance than route $R_{1}$ , and route $R_{3}$ has a shorter distance than route $R_{4}$ . However, the demand of commuters in route $R_{1}$ may be larger than route $R_{2}$ and that of route $R_{4}$ may be larger than route $R_{3}$ because more commuters are closer to stops in routes $R_{1}$ and $R_{4}$ . Routes with maximum profits are the optimal choice.

Figure 1.

Example of commuter bus stop selection and routing problem.

This study investigates the collaborative optimization framework of CCBS stops, and the routes considering the stochastic travel time and the probability of commuters choosing CCBS. The objective function of the optimization is profit maximization. The main contributions of this study are summarized as follows:

In the data preparation phase, we propose an improved fuzzy c-means (FCM) clustering algorithm to cluster the residences of commuters. Improved coding and increased neighborhood search results in more appropriate clusters for this optimization problem.

In the solution phase, we design a collaborative optimization framework of stop selection and route programming for CCBS considering commuter demand and travel time. A novel heuristic stochastic dynamic programming (H-SDP) algorithm is proposed to solve the bus stop selection sub-problem.

We apply a variable neighborhood search (VNS) algorithm with novel shaking operation to solve the CCBS routing problem. A series of computational experiments were conducted to demonstrate the effectiveness and efficiency of the proposed algorithm.

The remainder of this paper is organized as follows. Related studies are reviewed in the next section and the commuter bus routing problem is described in the third section. In the fourth section, we design optimization algorithms for commuter bus stop selection and routing problems. An experimental simulation is further conducted and analyzed in the fifth section 5. The final section concludes this study.

Literature Review

CCBS is a widely used commuting mode of paratransit. Traditional bus routing has always been a commonly discussed topic in industry and academia. Public bus routing and school bus routing, which are typical applications of traditional bus routing problems, have been widely studied. However, few studies have focused specifically on the CCBS. CCBS has fewer stops and a strict arrival time window compared with traditional bus services. In addition, the key factor of uncertainty in CCBS profit is the probability of employees choosing CCBS. The probability of commuters choosing CCBS and the location of the stops are closely related to route planning.

Bus stop selection and bus routing programming are important sub-problems of bus route planning. The extant literature on the two sub-problems mainly focuses on travel time and service quality ( 4 ). Generally, the first step is to solve the bus stop selection sub-problem because each bus stop’s location is the input to the bus routing problem ( 5 ). The minimization of the maximum walking distance and total walking distance are two methods for selecting commuter bus stops ( 6 ). A dual-objective model was considered by Riera-Ledesma and Salazar-González ( 6 , 7 ) to minimize the total bus route distance and passenger walking distance. Schittekat et al. ( 8 ) established an integer programming model and use walking distance as a constraint to find the route with the shortest total travel distance. Taplin and Sun ( 9 ) designed a traveling salesman genetic algorithm to find the shortest route linking the stops, so that an efficient circuit route is generated for each alternative number of bus stops. However, the influence of walking distance on the probability of passengers’ travel mode selection has not been considered.

Although some studies considered bus stop selection as a standalone problem, researchers also suggested that bus stop selection optimization should be combined with bus route programming ( 10 , 11 ). The bus route programming of CCBS is closely related to the well-known pick-up and delivery problems with time windows (PDPTW). In most PDPTWs, the number of passengers served, operating costs, and service quality are the three major objectives to be optimized separately or simultaneously ( 12 – 14 ). When the service is in an uncertain environment, the uncertain demand and vehicle travel time make PDPTW problems become stochastic PDPTW problems (SPDPTW). Ghilas et al. ( 15 ) proposed a scenario-based sample average approximation approach for the PDPTW with stochastic demands. Mourad et al. ( 16 ) introduced a sample average approximation method along with an adaptive large neighborhood search algorithm to solve the stochastic PDPTW problem. We use the stochastic dynamic programming approach to solve the CCBS routing optimization problem with maximum profit.

An uncertain environment is considered in many studies for the optimization problem of public transportation routes. There are two types of bus operations in uncertain environments: stochastic travel time and stochastic demand ( 17 – 19 ). Many studies have established stochastic models for different types of buses to solve sub-problems such as routing, scheduling, and stop selection in bus operation optimization. Li et al. ( 20 ) studied the optimal multiple headways determination for a single public bus route with stochastic travel time. They proposed a hybrid intelligent algorithm of stochastic simulation and genetic algorithm (GA) to treat uncertain functions. Wu et al. ( 21 ) proposed a novel stochastic bus schedule coordination design with demand assignment and passenger rerouting in the case of transfer failure. They developed a bi-level programming model in which the schedule design and passenger route choice were determined simultaneously via two travel strategies: non-adaptive and adaptive routings. Zhang et al. ( 22 ) proposed a real-time control method for public bus routes considering stochastic demand and stochastic travel time. Buses skip some stations and return at appropriate stations to balance passenger demand along the bus route and improve the overall transit service.

Some researchers have studied several forms of auxiliary bus operations in uncertain environments. Bouyahia et al. ( 23 ) proposed a simulated annealing (SA) algorithm for the probabilistic vehicle routing problem that considers both uncertain transport demand and travel time. Caceres et al. ( 3 ) studied school bus routing problem with stochastic demand and travel time and proposed a mathematical formulation that responds to the overbooking policies applied at a real-world school district. Babaei and Rajabi-Bahaabadi ( 24 ) presented a simultaneous approach to the school bus routing and scheduling problem with stochastic time-dependent travel times that guarantee on-time arrival at a single school for all buses with a required reliability level. Lee et al. ( 25 ) investigated flexible bus. The volume stochasticity of demand, detour time stochasticity, and service price and quality are captured in the formulation. Ben Abdelaziz et al. ( 27 ) proposed a multi-objective stochastic program (MSP) to model the airport bus routing problem. They solved the MSP problem using a goal programming approach. Ng and Mahmassani ( 28 ) investigated the potential of autonomous minibuses which take on-demand directional routes for pick-up and drop-off in suburban areas, followed by fixed routes in downtown with greater demand. The key relevant papers delineating the bus types, sub-problems, stochastic model, and solution methods used are compared in Table 1.

Table 1.

Comparison of Relevant Literature with Present Work

Study	Bus type	Sub-problem	Stochastic travel time	Stochastic demand	Approach
Li et al. ( 20 )	Public bus	Scheduling	√	×	Genetic algorithm
Wu et al. ( 21 )	Public bus	Scheduling, routing	√	×	Heuristic
Zhang et al. ( 22 )	Public bus	Stop selection	√	×	Monte Carlo
Bouyahia et al. ( 23 )	Chartered bus	Routing	√	√	Simulated annealing
Chao et al. ( 26 )	Customized bus	Routing	×	√	NSGA-II
Lee et al. ( 25 )	Flexible bus	Routing	√	√	Gradient-based approach with a GS
Caceres et al. ( 3 )	School bus	Routing, scheduling	√	√	Column generation
Babaei and Rajabi-Bahaabadi ( 24 )	School bus	Scheduling, routing	√	×	Ant colony and heuristic
Ben Abdelaziz et al. ( 27 )	Airport bus	Routing	×	√	Stochastic program
Ng and Mahmassani ( 28 )	Autonomous Minibus	Routing	×	√	Monte Carlo
Our study	Company commuter bus service	Stop selection, routing	√	√	Heuristic dynamic programming and improved variable neighborhood search

Aiming at CCBS, this study comprehensively considers commuter demand, stop location, uncertain link time, and total vehicle profit, and establishes a collaborative optimization algorithm framework. In the optimization process, a new H-SDP algorithm and an improved VNS algorithm are developed considering the selection of location of stops and the optimization of vehicle routing.

Problem Statement

This study solves the problem of routing optimization of CCBS. In the case study, the employer company is located in an industrial park of the urban fringe, while the employees reside throughout the city, which makes it difficult for urban employees to commute. CCBS is a commuting service provided by the employer company and is paid for by the employees who use it. As a business arm of the company, CCBS has the goal of making profits, so it needs to plan advantageous commuter bus routing to improve the utilization rate of employees. Owing to many uncertain factors such as weather and traffic during peak hours, the travel time of the shuttle bus is uncertain. Simultaneously, the convenience of the bus stop plays an important role in the choice of commuting for employees, and unreasonable stops will affect the user demand for CCBS. This study mainly designs the stop selection and routing scheme of CCBS by considering commuters’ demand and stochastic travel time. The profitability of the CCBS is an objective function of our problem.

This study considers a case in which an enterprise has multiple commuter buses. The following assumptions are made:

a. The bus fare is the same for each commuter.

b. Each commuter bus runs at the same speed.

c. All commuter buses are homogeneous.

Figure 2 depicts the framework of this problem. The input data included the commuters’ residence coordinates, the enterprises’ location coordinates, and a predefined road network. The steps are as follows:

Step 1. The starting points of commuters are clustered.

Step 2. For each cluster center, $m$ candidate stops are obtained at the main roads and road intersections.

Step 3. The initial solution of vehicle allocation and vehicle routing is given.

Step 4. The optimal solution for stop selection is obtained by the SDP algorithm for each path according to the vehicle allocation and vehicle routing scheme.

Step 5. Obtain a new vehicle allocation and vehicle routing scheme by using the VNS algorithm and turn to Step 4.

Step 6. If the iteration does not meet the conditions, output the optimized stop selection and routing scheme.

Figure 2.

Framework for commuter bus stop selection and routing problem.

Solution Algorithm

The optimization of stop selection and vehicle routing in CCBS is a NP (non-deterministic polynomial)-hard problem. Moreover, when there are many commuter location records, the computational load can be large. Therefore, we solve this problem in the data preparation and solution phase. Figure 2 describes the framework for solving this problem:

Phase 1 (Commuter clustering procedure): In this phase, we propose an improved FCM clustering to obtain appropriate clusters of commuters’ addresses.

Phase 2 (Collaborative optimization of stop selection and vehicle routing): In this phase, a novel H-SDP algorithm is proposed to solve the bus stop selection sub-problem. Meanwhile, we apply a VNS algorithm with two novel sharking operations to solve the CCBS routing problem.

Commuter Clustering Procedure

FCM Method

The FCM clustering method is widely used because it can solve the uncertainty of the data clustering problem ( 29 ). As an important basis for data clustering, the membership degree is iteratively optimized. Assume $x_{i}$ represents the commuter $i$ . $x_{i} \in X$ , $X = {x_{1}, x_{2}, \dots, x_{n}}$ , where $n$ is the number of commuters. The commuter set $X$ is classified into $c$ clusters. The cluster centroid set is $S = {s_{1}, s_{2}, \dots, s_{c}}$ , where $s_{j}$ represents the cluster $j$ centroid. The objective function of the FCM is given as follows.

J (U, S) = \sum_{i = 1}^{n} \sum_{j = 1}^{c} U {(x_{i}, s_{j})}^{α} \cdot d {(x_{i}, s_{j})}^{2}

(1)

$U$ represents the membership degree of $x_{i}$ belonging to $s_{j}$ , as shown in Equation 2

U (x_{i}, s_{j}) = \frac{1}{\sum_{l = 1}^{c} {(\frac{d (x_{i}, s_{j})}{d (x_{i}, s_{l})})}^{\frac{2}{α - 1}}}

(2)

where the parameter $α$ is the weighting coefficient of the degree of fuzziness, and $α > 1$ . For any commuter $x_{i}$ , $\sum_{j = 1}^{c} U (x_{i}, s_{j}) = 1$ , which means that the sum of membership degree in all clusters is one. The Euclidean distance $d (x_{i}, s_{j})$ is given by Equation 3.

d (x_{i}, s_{j}) = \sqrt{{\sum_{a = 1}^{r} (x_{ia} - s_{ja})}^{2}}

(3)

where the parameter $r$ is the characteristic number. In this study, $r = 2$ denotes the x- and the y-coordinates. The cluster centroid $S = {s_{1}, s_{2}, \dots, s_{c}}$ is calculated using Equation 4.

s_{j} = \frac{\sum_{i = 1}^{n} U {(x_{i}, s_{j})}^{α} \cdot x_{i}}{\sum_{i = 1}^{n} U {(x_{i}, s_{j})}^{α}}

(4)

In the FCM method, parameters $S$ and $U$ are updated. Equations 2 and 4 were repeatedly calculated. If the termination condition is met, then we can obtain the minimal objective function and the optimal values of $U$ and $S$ .

FCM is an iterative optimization approach. Convergence depends on the initial solution. Although the FCM has a high search speed, it quickly falls into a local optimal ( 30 ). Next, we propose an improved FCM algorithm to solve this problem.

Improved FCM Algorithm

Encoding

We designed the encoding for the solution of the improved FCM, as shown in Figure 3. The first part of the solution is the number of clusters $C$ . The second part of the solution is the cluster centroid $S = {s_{1}, s_{2}, \dots, s_{c}}$ . The encoding is binary.

Figure 3.

Encoding of the improved fuzzy c-means (FCM) algorithm.

Framework of the Improved FCM Algorithm

In the FCM algorithm, the number of clusters $C$ is particularly important. In our improved FCM algorithm, the initial value of $C$ is a random number, which is a part of $sol$ , as shown in Figure 3. With the optimization of $sol$ solution, the $C$ will be optimized accordingly, and finally the self-adaptation results in the optimal clustering number. The initial value of $sol$ is random. The second part of $sol$ is the randomly generated cluster centroid. We defined the neighborhood structure $F_{e}$ for the FCM-based local search operation. $F_{e}$ adopts two neighborhood structures, 2-opt and 3-opt ( 31 ), and $e_{\max} = 2$ . The optimization process transforms between the two neighborhood structures, eventually finding the optimal $sol$ .

The details of the improved FCM algorithm are as follows:

Improved FCM Algorithm
Step 1:	Initialize the cluster number $C$ and the cluster centroid $S$ . The initial solution is $sol$ . Calculate the membership degree $U$ for each sample $x_{i}$ and the fitness function $J (U, S)$ .
Step 2:	Define neighborhood structures $F_{e} (e = 1, \dots, e_{\max})$ .
Step 3:	Execute the $e$ th local search for each individual $sol \in F_{e} (sol)$ to obtain a solution $sol'$ .
Step 4:	Calculate the membership $U'$ for each sample $x_{i}$ and the fitness function $J (U', S')$ of $sol'$ .
Step 5:	If the solution $sol'$ is better than $sol$ , then set $sol = sol'$ and $e = 1$ and return Step 3. Otherwise, set $e = e + 1$ , and go to Step 6.
Step 6:	If $e \leq e_{\max}$ , then go to Step 3. Otherwise, stop the iteration.

Optimization of Stop Selection and Route Programming

The commuter bus routing problem with stop selection is a collaborative optimization problem. We design a cooperative optimization algorithm framework, in which the results of the stop selection sub-problem are the input of bus routing problems, and we optimize stop selection and routing simultaneously by repeated iterations. In our study, the objective function is to maximize the profit of the CCBS, and the decision variables are the selection of stops and routing scheme.

Commuter Bus Stop Selection Sub-Problem

Generally, each commuter bus stop is selected from a set of candidate bus stops. These candidate stops are located on main roads or road intersections. This section proposes a novel H-SDP approach for solving the bus stop selection problem. In addition, the structural properties are analyzed to obtain the candidate bus stops effectively based on the road network.

Problem Formulation

A commuter bus starts from a fixed parking lot and terminates at the company location, defined as the origin and destination pair $〈 o, d 〉$ . The candidate bus stop selection process for each cluster follows a stage set $B = {b | b = 0, 1, 2, \dots, C}$ . We denote $b = 0$ when the commuter bus starts from the parking lot. The candidate bus stop is defined as a set $m_{b, i} \in M_{b}$ , where $M_{b}$ is the set of candidate stops for stage $b$ . $m_{b, i}$ is the $i$ th candidate stop in the $b$ stage. $A (b)$ is the set of possible actions in state $b \in B$ , and we set $a_{b, i} \in A (b)$ . If the candidate bus stop $i$ of stage $b + 1$ is selected, then $a_{b, i} = m_{b + 1, i}$ . In state $b$ , the commuter bus travel time and the number of passengers have been determined, and we need to determine the best stop for the next stage $b + 1$ . The successive stage-by-stage decision process is not affected by previous stages. The optimal strategy for the entire decision-making process can be solved using a discrete dynamic programming approach shown in Figure 4.

Figure 4.

Discrete dynamic programming for bus stop selection.

However, it is usually difficult to estimate commuter demand and travel time accurately because of uncertain traffic conditions. Scholars generally transform the stochastic optimization problem (SDP) into a deterministic optimization problem and perform dynamic optimization statistically ( 17 ). Here, we model the SDP process and propose an H-SDP algorithm to solve the commuter bus stop selection problem. We define $R (b, a_{b, i})$ as the reward model for performing action $a_{b, i} \in A (b)$ in state $b \in B$ . We formulate the maximum reward problem with a V value $V^{*}$ and an optimal policy $π^{*}$ . Bellman equation is given by Equation 5.

V^{*} (b + 1) = ma x_{a_{b, i} \in A (b)} E {R (b, a_{b, i}) + γ V^{*} (b)}

(5)

where $γ \in (0, 1)$ is the discount rate for analyzing the present values of future rewards. For each $b \in B$ , vector $V^{*} (b + 1)$ is known as the value function Equation 5 can be converted into Equation 6 as

\begin{matrix} V^{*} (b + 1) \\ = ma x_{a_{b, i} \in A (b)} {\sum_{m_{b, j} ϵ M_{b}} P (T_{m_{b, j}, m_{b + 1, i}}) (R (b, a_{b, i}) + γ V^{*} (b)) \end{matrix}

(6)

where $P (T_{m_{b, j}, m_{b + 1, i}})$ is the probability that the bus moves from a stop $m_{b, j}$ to stop $m_{b + 1, i}$ in the time window of stage $b + 1$ . The time window demand for each stage $b + 1$ is expressed as $e_{b + 1}, l_{b + 1}$ . The probability of travel time $T_{m_{b, i}, m_{b + 1, j}}$ in the time window is given in Equation 7.

P (T_{m_{b, i}, m_{b + 1, j}}) = \int_{e_{b + 1}}^{l_{b + 1}} \frac{1}{\sqrt{2 π} σ} e^{- \frac{{(T_{m_{b, i}, m_{b + 1, j}} - μ)}^{2}}{2 σ^{2}}} d T_{m_{b, i}, m_{b + 1, j}}

(7)

The travel time $T_{m_{b, i}, m_{b + 1, j}}$ is uncertain. The total travel time consists of the bus stop time $t_{m_{b + 1, j}}$ and the link travel time $t_{m_{b, i}, m_{b + 1, j}}$ . We assumed that the bus stop time is a linear function of the number of commuters waiting at the bus stops and the link travel time follows a normal distribution ( 3 ). Let $f t_{m_{b + 1, j}}$ and $v t_{m_{b + 1, j}}$ represent the fixed and variable times when picking up commuters at each stop such that it would take time $f t_{m_{b + 1, j}} + v t_{m_{b + 1, j}} W_{m_{b + 1, j}}$ for $W_{m_{b + 1, j}}$ commuters. The expected value and variance of the travel time $T_{m_{b - 1, i}, m_{b, j}}$ are given by Equations 8 and 9, respectively.

μ T_{m_{b, i}, m_{b + 1, j}} = μ t_{m_{b, i}, m_{b + 1, j}} + μ t_{m_{b + 1, j}}

(8)

σ^{2} T_{m_{b, i}, m_{b + 1, j}} = σ^{2} t_{m_{b, i}, m_{b + 1, j}} + σ^{2} t_{m_{b + 1, j}}

(9)

An estimation of the link travel time and bus stop time for picking up commuters can be found in Caceres et al. ( 3 ). The reward function $R (b, a_{b, i})$ is the profit of selecting $a_{b, i} = m_{b + 1, i}$ in state $b$ , as shown in Equation 10.

R (b, a_{b, i}) = Inc (b, a_{b, i}) - Cost (b, a_{b, i})

(10)

where $Inc (b, a_{b, i})$ denotes the fare revenue that performs action $a_{b, i} = m_{b + 1, i}$ at state $b \in B$ for the commuter bus. $Inc (b, a_{b, i})$ is related to the probability of commuters choosing CCBS, as shown in Equation 11.

Inc (b, a_{b, i}) = z \sum_{x_{i} \in X_{b + 1}} w (a_{b, i}, x_{i})

(11)

where $z$ denotes the fare of each commuter, and $X_{b + 1}$ denotes the set of commuters in state $b + 1$ . $w (a_{b, i}, x_{i})$ denotes the probability of commuter $x_{i}$ choosing CCBS when the commuter bus performs action $a_{b, i} \in A (b)$ at state $b \in B$ . Walking distance is an important factor affecting commuters’ choice of travel mode. In many studies, a logistic regression model is used to study the factors of commuters’ travel mode choice, and it is found that walking distance has a significant impact on commuters’ willingness to choose public transport ( 32 – 34 ). In our study of the stop location of CCBS, the effect of walking distance on the willingness to choose CCBS needs to be considered, and the logistic regression model can estimate the probability of passengers choosing CCBS accordingly. In logistic regression, the sigmoid function is used as a constructor. The relationship between walking distance and probability of commuters choosing CCBS is formulated as a variation on the sigmoid function, which is shown in Equation 12.

w (a_{b, i}, x_{i}) = \frac{1}{1 + e^{- (θ - d (a_{b, i}, x_{i}))}}

(12)

where $θ$ denotes a fixed coefficient. $d (a_{b, i}, x_{i})$ denotes the distance of commuter $x_{i}$ to a stop $m_{b + 1, i}$ . If $a_{b, i} = m_{b + 1, j}$ , the number of commuters choosing CCBS is $W_{m_{b + 1, j}} = \sum_{x_{i} \in X_{b + 1}} w (m_{b + 1, j}, x_{i})$ .

$Cost (b, a_{b, i})$ is the travel cost of performing action $a \in A (b)$ at state $b \in B$ for the commuter bus, as shown in Equation 13.

Cost (b, a_{b, i}) = ε t (b, a_{b, i}) = ε d (m_{b, j}, m_{b + 1, i}) / h

(13)

where $t (b, a_{b, i})$ denotes the travel time that performing action $a_{b, i} \in A (b)$ at state $b \in B$ for the commuter bus. $ε$ is the fuel cost per minute. $d (m_{b, j}, m_{b + 1, i})$ is the travel distance of the bus from the stop $m_{b, j}$ to $m_{b + 1, i}$ . $h$ is the speed of the commuter bus.

Structural Properties

Determining the candidate bus stops for each cluster is essential to obtain the optimal stop strategy. Several properties of the model were investigated.

The maximum expected reward criterion is utilized to maximize the total revenue, as shown in Equation 14.

R (b, a_{b, i}) = z \sum_{x_{i} \in X_{b}} \frac{1}{1 + e^{- (θ - d (a_{b, i}, x_{i}))}} - ε d (m_{b, j}, m_{b + 1, i}) / h

(14)

where $a_{b, i}$ denotes the location of the candidate stop. We set $d (a_{b, i}, x_{i}) = ax$ , $θ - ax = u$ , $d (m_{b, j}, m_{b + 1, i}) = ma$ , $d (m_{b, j}, x_{i}) = d$ , and $ma = d - ax = d - θ + u$ .

Property 1: $X_{b}$ is the set of commuters in the $b$ stage. Let $R_{b} (u) = z \sum_{x_{i} \in X_{b}} w (u) - ε / h \cdot (d - θ + u)$ . There is a threshold $u^{*}$ that maximizes $R_{b} (u^{*})$ .

Proof: We take $a$ as a variable of $R_{b} (a)$ , and take the derivative of $R_{b} (a)$ .

\frac{dR}{du} = z \sum_{x_{i} \in X_{b}} w w (u)' - ε / h = z \sum_{x_{i} \in X_{b}} w_{b} (u) (1 - w_{b} (u)) - ε / h

(15)

If $\sum_{x_{i} \in X_{b}} w_{b} (u) (1 - w_{b} (u)) = ε / hz$ , then $\frac{dR}{da} = 0$ and $\frac{d^{2} R}{d u^{2}} \neq 0$ . A threshold $u^{*}$ exists that optimizes $R_{b} (u^{*})$ . That is, there exists an optimal $a^{*}$ that maximizes $R (b, a^{*})$ .

Property 2: We set action $a^{*}$ to optimize $R_{b} (a^{*})$ . There exist commuter bus stops ${m_{b + 1, i}}^{*} \in M_{b + 1}$ on the main road, and the reward function of the stop $R_{b} ({m_{b + 1, i}}^{*})$ with the minimum difference from $R_{b} (a^{*})$ is the optimal strategy in $b$ stage.

Proof: We set $Δ_{b, i} = R_{b} (a^{*}) - R_{b} (m_{b + 1, i})$ and $m_{b + 1, i}, m_{b + 1, j} ϵ M_{b + 1}$ . Then, $R_{b} (m_{b + 1, i}) = z W_{m_{b + 1, j}} - δ t (b, m_{b + 1, i})$ . In dynamic programming, we can derive the value function as shown in Equation 16.

V (b + 1, m_{b + 1, i}) = R_{b} (m_{b + 1, i}) + γ V^{*} (b)

(16)

Then, we have $V (b + 1, m_{b + 1, i}) - V (b + 1, m_{b + 1, j}) = Δ_{b, j} - Δ_{b, i}$ . If $Δ_{b, i} < Δ_{b, j}$ , then $V (b + 1, m_{b + 1, i}) > V (b + 1, m_{b + 1, j})$ and $V^{*} (b + 1) = V (b + 1, m_{b + 1, i})$ .

There exist commuter bus stops ${m_{b + 1, i}}^{*} \in M_{b + 1}$ on the main road, which is the optimal strategy in $b$ stage.

In the road network, each region is surrounded by one or more available main roads. An optimal candidate stop can be obtained for each available main road according to Properties 1 and 2. We use the dynamic programming method to obtain the optimal strategy according to candidate stops on several main roads. Furthermore, the stochastic travel time should be considered. Combined with the above properties, we designed an H-SDP algorithm to obtain the optimal strategy.

Solution Approach

Combining the above properties with the SDP algorithm, we propose the H-SDP algorithm for the commuter bus stop selection problem to obtain the optimal strategy. The H-SDP algorithm proceeds as follows:

H-SDP Algorithm
Step 1:	Initialize the parameters: the stage $B$ of the commuter bus; the transition probability $P$ , the set of commuters $N,$ the initial set of candidate bus stop $M^{'},$ the cluster number $C$ .
Step 2:	Set $b = 0$ , $v_{π *} (b) = 0$ .
Step 3:	If $P (M_{b} \| M_{b + 1}) \neq 0$ , we solve the optimal $R_{b} (a^{})$ and $R_{b} ({m_{b + 1, i}}^{})$ of each main road based on Property 1 and Property 2, determine the candidate stops set $M$ .
Step 4:	Calculate the transition probability $P (M_{b} \| M_{b + 1})$ and optimal value $v_{π } (b + 1)$ . Set $π^{} (b) = π (b)$ .
Step 5:	If $b = C$ , stop the iteration. Otherwise, set $b = b + 1$ and go to Step 3.
Step 6:	Generate an optimal value $v_{π } (b + 1)$ and optimal solution $π^{}$ .

Commuter Bus Route Programming

The commuter bus routing problem is closely related to a multiple vehicle routing problem, which is an NP-hard problem. The objective function of the commuter bus routing problem is to maximize the profit of CCBS as shown in Equation 17.

Q = \sum_{k = 1}^{K} {V^{*}}_{k}

(17)

where ${V^{*}}_{k}$ is optimal profit of the CCBS route for the vehicle $k$ .

We use the VNS algorithm with a novel shaking operation to solve the problem. The VNS algorithm has a powerful search capability and flexibility in solving the optimization problem ( 35 ). The most suitable solution can be found by switching between different neighborhood spaces and implementing a local search strategy. We design the encoding, initial solution, sharking, and neighborhood structures of the VNS algorithm for this commuter bus problem.

Encoding and Decoding Strategy

To encode the solution vector, we consider the following two stages: (i) assign the commuter bus for each commuter cluster; (ii) assign the service order for each commuter cluster. An example of a VNS-based coding strategy is presented in Figure 5.

Figure 5.

Encoding and decoding strategy of the algorithm.

The encoding of the solution $g_{i}$ is a set of random decimals. We set $g_{i} = {b_{1}, b_{2}, \dots, b_{n}}, b_{i} < K$ . $K$ is the number of buses. The decoding of the solution is the service bus and service order of each stop $b_{i}$ . We arrange stops to commuter buses according to the $b_{i}$ maximum close bus number $k$ . In addition, the service order of the stops of each bus is in the order of the $b_{i}$ . For example, $b_{4}, b_{1}, b_{7}$ are serviced by bus $k = 1$ owing ${b_{4}, b_{1}, b_{7}} < 1,$ $b_{3}, b_{5}$ are serviced by bus $k = 2$ , and stops $b_{6}, b_{2}, b_{8}$ are serviced by bus $k = 3$ in Figure 5. The service order of bus $k = 1$ is $b_{4}, b_{1}, b_{7}$ , the order of bus $k = 2$ is $b_{3}, b_{5}$ , and the order of bus $k = 3$ is $b_{6}, b_{2}, b_{8}$ .

Initial Solution

The initial solution is an essential factor that affects the optimization efficiency. In general, commuter service orders are based on the distance from their residence to the company. We set the initial solution for service order. The initial solution is based on the distance from the stop location to the company address. Setting the distance order as the initial solution can accelerate the optimization speed of the algorithm.

Shaking

In the shaking phase, we generate new solutions by changing the allocation and service sequences of different vehicles, which can speed up the convergence of the algorithm. We design two shaking operations. (i) Swapping any two clusters $b_{i}$ , $b_{j}$ belonging to different vehicle routes. Find two groups $b_{i}$ and $b_{j}$ belonging to two different vehicle paths randomly. Add and subtract values of $b_{i}$ and $b_{j}$ with the difference between the two vehicle numbers. Reorder the new solution for each route. Figure 6a shows the first shaking operation. (ii) Swapping two groups of service sequences belonging to two routes. Randomly find two groups of service sequences of two different routes, exchange them, and reorder the $b_{i}$ values of the two routes. Figure 6b shows the second shaking operation. After shaking of the solution, we recalculate the total profit and then search for the local optimum.

Figure 6.

Diagrams of first (a) and second (b) shaking operation.

Neighborhood Structures

The neighborhood structures commonly applied to assignment problems are swap operation and insert operation ( 36 ). The swap neighborhood structure is randomly swapping two elements of the given solution. The insertion neighborhood structure is the insertion of one randomly selected element before or after another randomly selected element. In our study, classical swap neighborhood is applied, 2-opt and 3-opt are local search operations $L_{e}, e_{\max} = 2$ . The main framework of the VNS algorithm is shown in Figure 7.

Figure 7.

Flowchart of the variable neighborhood search (VNS) algorithm.

Experiments and Results

In this section, we evaluate the effectiveness and performance of the proposed algorithm through a series of computational experiments. First, to verify the validity of the improved FCM on our problem, we compared it with the original FCM ( 37 ). Second, the applied VNS algorithm with the novel shaking operation was compared with the other three metaheuristic algorithms to demonstrate the performance improvement of the proposed algorithm. Finally, the experiment on uncertain travel time parameters was performed, and the experimental results show the effect of the uncertain parameter on the profit of the commuter bus service.

Data and Parameter Setting

Different scenarios were created to investigate the solution quality and computational efficiency of the algorithms. Data on employee residences collected from a company in Beijing were used. All the data were preprocessed. After cleaning, the data were reformatted for the experiment inputs. According to the study of Caceres et al. ( 3 ), the link travel time and stop time of commuter bus were estimated. The pick-up fixed time was $f t_{m_{s, j}} = 19$ s and the variable time was set to $v t_{m_{s, j}} = 2.6$ s. The standard deviation of the link time was $σ t_{m_{s - 1, i}, m_{s, j}} = 0.1$ s. The fuel cost per minute per vehicle was set to $ε = 2.0$ (RMB/L). The average speed of vehicle $k$ is set as $h = 1.0$ km/min. The commuter fare was set to $z = 10$ RMB.

Effects of Proposed Improved FCM

In this section, we compare the improved FCM algorithm with the original FCM algorithm for its performance of our CCBS model. The problem parameters are shown in Table 2.

Table 2.

Parameter Settings

Notation	Definition	Value
$K$	Number of commuter buses	2, 3, 4, 5, 6, 8
$N$	Number of commuters	50, 70, 85, 100, 120, 150, 180, 200, 250, 300, 350
$r$	Number of characteristics	2
$μ$	Weighting coefficient of the degree of fuzziness	3
$e_{\max}$	Maximum iteration number	200

For each instance, the proposed algorithm and the comparison algorithm were run 30 times. Table 3 shows the maximum, median, minimum, and average values of the algorithm results for each instance. To increase the readability of the tables, the best metric values are marked in bold.

Table 3.

Experimental Results of Profit for Improved FCM and Original FCM

Instances	Improved FCM				Original FCM
$(K, N)$	Minimum	Median	Maximum	Average	Minimum	Median	Maximum	Average
(2, 50)	95.21	100.15	106.33	101.57	94.49	98.63	103.56	99.12
(2, 70)	149.44	154.35	162.77	155.73	144.21	150.11	156.37	152.15
(2, 85)	174.85	182.76	191.31	182.52	168.23	175.75	181.91	176.83
(3, 70)	130.58	137.54	142.14	136.79	125.29	130.46	138.21	132.22
(3, 85)	165.69	171.93	179.51	173.34	161.13	165.32	172.42	165.88
(3, 100)	195.55	198.21	208.85	199.84	187.28	193.55	199.86	190.38
(3, 120)	266.70	275.69	289.40	277.05	261.28	269.32	277.21	264.19
(4, 100)	193.25	201.19	210.03	201.44	187.26	196.77	204.25	195.32
(4, 120)	236.46	244.32	256.22	245.14	229.62	237.78	247.23	238.51
(4, 150)	318.25	331.32	339.12	332.14	311.25	320.72	332.49	321.57
(4, 180)	389.12	405.59	417.23	402.19	367.21	389.25	408.12	381.47
(5, 120)	223.14	231.66	342.98	232.18	218.35	226.11	231.14	224.23
(5, 150)	267.00	274.94	283.30	275.16	261.21	271.76	280.40	271.46
(5, 180)	376.16	381.35	394.35	380.23	353.91	362.76	375.42	363.92
(5, 200)	428.15	442.13	451.51	440.77	415.36	427.18	439.82	425.56
(6, 150)	289.52	301.42	318.31	300.78	271.39	288.19	297.45	188.62
(6, 180)	332.79	344.92	357.24	346.12	312.56	325.25	334.83	326.66
(6, 200)	352.06	368.14	378.85	365.75	331.15	342.21	354.36	344.32
(6, 250)	469.33	481.21	498.87	485.47	442.62	458.32	472.31	456.23
(7, 180)	323.77	337.90	352.12	338.95	308.14	320.11	335.19	319.53
(7, 200)	391.12	402.17	415.86	404.76	370.28	383.17	404.72	381.44
(7, 250)	466.05	474.26	488.61	475.28	428.85	442.55	467.55	443.73
(7, 300)	588.33	610.42	622.17	608.34	551.21	564.03	584.36	564.55
(8, 200)	358.66	374.03	389.79	373.41	338.05	355.12	372.43	354.85
(8, 250)	494.12	516.08	531.29	513.77	462.18	476.21	489.93	478.44
(8, 300)	578.91	585.23	608.17	586.46	538.76	553.89	570.56	552.41
(8, 350)	719.33	738.28	754.94	736.52	681.59	696.63	714.23	694.57

Note: FCM = fuzzy c-means algorithm; K = number of commuter buses; N = number of commuters. Unit of measurement is RMB.

The best metric values are marked in bold.

As shown by the results in Table 3, the experimental results of various metrics obtained by the improved FCM are superior to the experimental results of the original FCM in all instances. The average value for each instance is shown in Figure 8.

Figure 8.

The average profit of each instance.

We compared the average values of all instances for the improved FCM and original FCM. As shown in Figure 8, the proposed improved FCM has more positive effects on improving the algorithm solution quality than the original FCM for all instances. In particular, the proposed algorithm has a more prominent effect in solving large-scale instances.

Comparison of VNS with Other Baseline Algorithms

In this subsection, we compare the VNS algorithm with the other three population-based algorithms, genetic algorithm (GA), simulated annealing (SA), and ant colony (ACO), to demonstrate its effectiveness and efficiency. The GA, SA, and ACO parameters were suggested by Ünsal and Yiğit ( 38 ), Afifi et al. ( 39 ), and Yiğit and Ünsal ( 40 ), respectively. The parameter settings are shown in Table 4.

Table 4.

Parameter Settings for Three Population-Based Algorithms

Type of Parameters	Parameters	Values
Parameters of genetic algorithm: Ünsal and Yiğit ( 38 )	Crossover probability	0.9
	Mutation probability	0.1
	Population size	200
Parameters of simulated annealing: Afifi et al. ( 39 )	Cooling coefficient	0.95
	Initial temperature	200
	Termination of the temperature	1
Parameters of ant colony: Yiğit and Ünsal ( 40 )	Relative importance of pheromone trace	1
Parameters of ant colony: Yiğit and Ünsal ( 40 )	Importance of visibility value	1

We compared the algorithms’ performance in different instances. For each instance, all algorithms were run 30 times. The maximum, minimum, and average values of the algorithm results for each instance were recorded. In addition, to evaluate the performance of the VNS algorithm in different instances, the relative percentage deviation (RPD) values were applied as the measurement metric. The RPD is defined by Equation 18.

RPD = \frac{alg - opt}{opt}

(18)

where $alg$ is the algorithm, and $opt$ is the best-known solution for a single instance. A comparison of the metric values of the algorithms for all instances is shown in Table 5. It is clear that the VNS algorithm is the most competitive algorithm for maximum, minimum, and average values and RPD, as it has the best value in 18, 18, 17, and 12 instances, respectively. The GA algorithm and ACO have similar performance for the maximum, minimum, and average values, as they have the best value in 2, 2, and 3 instances, respectively. The SA algorithm displayed a considerably worse performance than the VNS, GA, and ACO algorithms. After analyzing the performance of algorithms in different instances, we can conclude that the performance of the VNS algorithm is the best for this problem. The GA and ACO algorithms performed better than the SA algorithm.

Table 5.

Comparison of the Performances of Algorithms for Different Instances

Instances	Variable neighborhood search				Genetic algorithm				Simulated annealing				Ant colony
Instances	Minimum	Avg.	Maximum	RPD	Minimum	Avg.	Maximum	RPD	Minimum	Avg.	Maximum	RPD	Minimum	Avg.	Maximum	RPD
(3, 100)	185.47	197.51	201.37	0.019	188.54	193.21	198.33	0.026	172.76	183.32	190.27	0.037	176.84	188.58	195.22	0.034
(3, 120)	266.7	273.69	289.4	0.054	260.05	275.19	285.25	0.035	257.66	272.12	283.38	0.040	252.83	269.45	276.15	0.024
(4, 100)	190.25	203.19	210.03	0.033	187.34	195.22	202.13	0.034	182.17	191.58	198.93	0.037	193.76	196.45	205.62	0.045
(4, 120)	236.46	242.32	253.22	0.043	232.29	244.18	250.36	0.025	228.83	236.46	245.19	0.036	234.82	240.47	251.15	0.043
(4, 150)	318.25	331.32	339.12	0.023	314.77	324.45	332.28	0.024	310.25	317.76	325.35	0.023	316.04	320.43	328.89	0.026
(4, 180)	389.12	405.59	412.23	0.016	383.62	398.23	417.88	0.047	371.25	385.48	392.74	0.018	385.42	402.11	408.92	0.017
(5, 120)	221.14	231.66	342.98	0.325	223.78	225.15	337.22	0.332	217.64	226.33	328.49	0.311	219.51	227.48	335.12	0.321
(5, 150)	271.36	280.41	294.22	0.047	258.93	262.33	278.17	0.057	254.39	263.25	277.42	0.051	260.14	268.82	282.69	0.049
(5, 180)	376.16	379.35	392.35	0.033	372.81	375.23	385.59	0.027	369.33	375.15	382.72	0.020	372.15	381.23	389.66	0.022
(5, 200)	428.15	442.13	451.51	0.021	414.32	428.59	437.63	0.021	412.11	420.13	428.86	0.020	415.19	429.52	439.16	0.022
(6, 150)	289.57	301.42	315.31	0.044	284.94	296.78	318.27	0.068	276.45	289.21	307.11	0.058	278.68	293.24	311.59	0.059
(6, 180)	332.79	344.92	357.24	0.034	328.53	339.75	348.17	0.024	325.19	334.77	345.49	0.031	328.76	338.28	350.96	0.036
(6, 200)	338.61	352.78	368.17	0.042	325.45	338.71	353.83	0.043	321.15	340.43	355.78	0.043	338.74	343.95	356.21	0.034
(6, 250)	469.33	481.21	498.87	0.035	454.92	462.17	482.57	0.042	451.33	460.62	476.94	0.034	455.23	464.32	483.27	0.039
(7, 180)	323.77	334.9	352.12	0.049	320.04	332.19	343.35	0.033	316.16	328.63	340.75	0.036	318.25	337.09	347.82	0.031
(7, 200)	391.12	402.17	411.86	0.024	386.62	394.47	410.03	0.038	382.83	389.71	403.59	0.034	388.12	392.45	415.61	0.056
(7, 250)	440.7	448.33	457.21	0.019	438.32	444.21	459.61	0.034	428.62	437.75	448.94	0.025	434.22	442.35	451.23	0.020
(7, 300)	588.33	610.42	622.17	0.019	576.54	603.65	612.82	0.015	561.63	577.88	586.49	0.015	578.04	591.75	607.31	0.026
(8, 200)	358.66	370.03	389.79	0.051	341.37	365.22	380.04	0.039	335.29	358.76	377.13	0.049	346.82	374.91	385.01	0.026
(8, 250)	464.12	486.08	501.29	0.030	457.28	472.53	492.16	0.040	449.88	463.92	482.27	0.038	459.03	481.24	496.62	0.031
(8, 300)	543.22	552.43	754.94	0.268	532.66	542.88	558.71	0.028	526.84	538.27	553.15	0.027	533.78	541.51	557.84	0.029
(8, 350)	719.33	738.28	754.94	0.022	689.19	714.84	736.92	0.030	685.35	710.62	728.28	0.024	692.27	723.14	741.69	0.025

Note: Avg. = average; RPD = relative percentage deviation. Unit of measurement is RMB. The best metric values are marked in bold.

The four algorithms are compared by t tests. Table 6 shows the t-test results. Compared with GA, SA, and ACO, VNS achieved significantly better results in almost all instances of the problem we studied, except for one instance with ACO, which had no significant effect. The VNS algorithm designed by us is proved to be an improvement on this problem.

Table 6.

T-Test Results for VNS with the Compared Algorithms

Instances	(VNS, genetic algorithm)		(VNS, simulated annealing)		(VNS, ant colony)
Instances	p	h	p	h	p	h
(3, 100)	1.2758e-07	1	3.8854e-08	1	1.1983e-07	1
(4, 120)	2.3225e-05	1	1.5329e-06	1	2.5036e-05	1
(4, 150)	2.9756e-05	1	3.1477e-05	1	2.3228e-05	1
(5, 150)	3.1478e-05	1	4.5893e-07	1	2.7817e-06	1
(5, 180)	1.1835e-04	1	1.3728e-08	1	1.3856e-04	1
(6, 180)	2.1777e-04	1	2.6285e-06	1	0.054817	0
(6, 250)	3.8388e-10	1	1.4592e-11	1	4.8257e-011	1
(7, 250)	1.8455e-13	1	2.4383e-14	1	1.5961e-13	1
(7, 300)	1.5229e-16	1	2.5765e-17	1	6.1282e-17	1
(8, 300)	2.1377e-18	1	5.3266e-19	1	5.5871e-19	1
(8, 350)	1.8498e-18	1	1.6892e-21	1	2.7369e-19	1

Note: VNS = variable neighborhood search; p = p-value, is the probability that the results difference is not significant under the premise that the results have significant difference is true (h = 1); For p<0.05, h = 1; For p> = 0.05, h = 0. An instance with no significant difference is marked in bold.

We compared the convergence performance of the algorithms for five different instances and the results are presented in Figure 9.

Figure 9.

Convergence performance of the algorithms: (a) instance (3, 100), (b) instance (5, 150), (c) instance (6, 200), (d) instance (7, 250), (e) instance (8, 300).

The VNS algorithm exhibited the best convergence performance among the five instances. The graph in Figure 9a reports the fitness of instance (3, 100), show that the convergence performance using the VNS is better than that of the other algorithms. The same trend was observed in instance (5, 150) (Figure 9b). The solutions of the VNS performed better than the others. In Figure 9c, the VNS algorithm is much better than the other three algorithms in instance (6, 200). However, in Figure 9d, the VNS, GA, and ACO algorithms perform equally well, and they are better than the SA algorithm in instance (7, 250). Figure 9e reports the fitness of instance (8, 300). The solutions of the VNS are better than those of the other algorithms. Therefore, the convergence performance of the designed VNS algorithm was better than that of the other algorithms.

Next, we study the impact of travel time uncertainty on the commuter bus problem. The stochastic model depends on the uncertainty of the CCBS system. We regenerate the stochastic travel time for 10 different instances with different standard deviations of the travel time. The solutions under varying levels of uncertainty for the instances are shown in Figure 10. As presented in Figure 10, the value of the objective function in all instances decreases as the uncertainty (the standard deviation) increases. More specifically, the business profits of CCBS decrease as the uncertainty of the vehicle travel time increases.

Figure 10.

Solutions under different levels of uncertainty.

Conclusion

This study investigates the collaborative optimization of the CCBS stop selection and routing problem. We model the CCBS routing problem based on CCBS characteristics (maximize profits and commuter satisfaction), and an optimization framework is designed to solve the problem. In addition, our solution considers both uncertain bus travel time and commuter demands, which are of practical significance for CCBS.

The main findings of this study can be summarized as follows. First, we developed an improved FCM algorithm to obtain more appropriate clusters for this problem. Then, a collaborative optimization framework is proposed to optimize both stop selection and routing problems. We propose a novel H-SDP algorithm to solve the CCBS stop selection problem with uncertain travel time and demand. In addition, we apply a VNS algorithm with a novel shaking operation to obtain the CCBS routing scheme. The results show that the designed VNS performs better than the other three metaheuristic algorithms in the quality of solutions for different scenarios. Furthermore, we analyze the impact of travel time uncertainty on the commuter bus problem. The results show that the business profits of CCBS decrease as the uncertainty of vehicle travel time increases.

Future research may include the following: other factors that affect commuters’ willingness to choose travel modes, such as the bus’s indoor environment and the fare. Additionally, the model can be modified to reflect commuters’ heterogeneity because people’s attitudes toward time and cost risks are different, which will significantly improve commuters’ perceived value. Finally, the real-time dynamic bus service is a new development in the mobile internet era that should be further considered.

Footnotes

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: L. Guan, W. Wang; data collection: L. Guan; analysis and interpretation of results: L. Guan; draft manuscript preparation: L. Guan, W. Wang. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the Introducing Talents for Ningxia Provincial Social Science Foundation of China (Nos. 20NXRCC17), the Ningxia Provincial Natural Science Foundation of China (Nos. 2022AAC05038).

ORCID iD

Lei Guan

References

Long

Thill

J. C.

Combining Smart Card Data and Household Travel Survey to Analyze Jobs-Housing Relationships in Beijing. Computers, Environment and Urban Systems, Vol. 53, 2015, pp. 19–35.

Qiu

Song

Jiang

Clustering Passenger Trip Data for the Potential Passenger Investigation and Line Design of Customized Commuter Bus. IEEE Transactions on Intelligent Transportation Systems, Vol. 20, No. 9, 2019, pp. 3351–3360.

Caceres

Batta

School Bus Routing with Stochastic Demand and Duration Constraints. Transportation Science, Vol. 51, No. 4, 2017, pp. 1031–1386.

Song

S. M.

Kim

Customer-Oriented School Bus Operations for Childcare Centers in Korea. Computers & Industrial Engineering, Vol. 66, No. 1, 2013, pp. 116–124.

Parvasi

S. P.

Mahmoodjanloo

Setak

A Bi-Level School Bus Routing Problem with Bus Stops Selection and Possibility of Demand Outsourcing. Applied Soft Computing, Vol. 61, 2017, pp. 222–238.

Riera-Ledesma

Salazar-González

J. J.

Solving School Bus Routing Using the Multiple Vehicle Traveling Purchaser Problem: A Branch-and-Cut Approach. Computers & Operations Research, Vol. 39, No. 2, 2012, pp. 391–404.

Riera-Ledesma

Salazar-González

J. J.

A Column Generation Approach for a School Bus Routing Problem with Resource Constraints. Computers & Operations Research, Vol. 40, No. 2, 2013, pp. 566–583.

Schittekat

Kinable

Sörensen

Sevaux

Spieksma

Springael

A Metaheuristic for the School Bus Routing Problem with Bus Stop Selection. European Journal of Operational Research, Vol. 229, No. 2, 2013, pp. 518–528.

Taplin

J. H. E.

Sun

Optimizing Bus Stop Locations for Walking Access: Stops-First Design of a Feeder Route to Enhance a Residential Plan. Environment and Planning B: Urban Analytics and City Science, Vol. 47, No. 7, 2020, pp. 1237–1259. https://doi.org/10.1177/2399808318824108.

10.

Galdi

Thebpanya

Optimizing School Bus Stop Placement in Howard County, Maryland: A GIS-Based Heuristic Approach. International Journal of Applied Geospatial Research, Vol. 7, No. 1, 2016, pp. 30–44.

11.

Mokhtari

N. A.

Ghezavati

Integration of Efficient Multi-Objective Ant-Colony and a Heuristic Method to Solve a Novel Multi-Objective Mixed Load School Bus Routing Model. Applied Soft Computing, Vol. 68, 2018, pp. 92–109.

12.

Song

Han

Liu

Sun

Metaheuristics for Solving the Vehicle Routing Problem with the Time Windows and Energy Consumption in Cold Chain Logistics. Applied Soft Computing, Vol. 95, 2020, p. 106561.

13.

Ouertani

Ben-Romdhane

Krichen

A Decision Support System for the Dynamic Hazardous Materials Vehicle Routing Problem. Operational Research, Vol. 22, 2022, pp. 551–576. https://doi.org/10.1007/s12351-020-00562-w.

14.

Foroutan

R. A.

Rezaeian

Mahdavi

Green Vehicle Routing and Scheduling Problem with Heterogeneous Fleet Including Reverse Logistics in the Form of Collecting Returned Goods. Applied Soft Computing, Vol. 94, 2020, p. 106462.

15.

Ghilas

Demir

Woensel

T. V.

A Scenario-Based Planning for the Pickup and Delivery Problem with Time Windows, Scheduled Lines and Stochastic Demands. Transportation Research Part B: Methodological, Vol. 91, 2016, pp. 34–51.

16.

Mourad

Puchinger

Woensel

T. V.

Integrating Autonomous Delivery Service into a Passenger Transportation System. International Journal of Production Research, Vol. 59, No. 7, 2021, pp. 2116–2139.

17.

Xia

Liao

Zhang

Peng

A Discrete Spider Monkey Optimization for the Vehicle Routing Problem with Stochastic Demands. Applied Soft Computing, Vol. 111, 2021, p. 107676.

18.

Huang

Wang

Liu

Zhang

A Two-Phase Optimization Model for the Demand-Responsive Customized Bus Network Design. Transportation Research Part C: Emerging Technologies, Vol. 111, 2020, pp. 1–21.

19.

Chow

J. Y. J.

School Bus Routing Problem with a Mixed Ride, Mixed Load, and Heterogeneous Fleet. Transportation Research Record: Journal of the Transportation Research Board, 2021. 2675: 467–479.

20.

Expected Value Model for Optimizing the Multiple Bus Headway. Applied Mathematics and Computation, Vol. 11, No. 1, 2013, pp. 5849–5861.

21.

Liu

Jin

Stochastic Bus Schedule Coordination Considering Demand Assignment and Rerouting of Passengers. Transportation Research Part B: Methodological, Vol. 121, 2019, pp. 275–303.

22.

Zhang

Zhao

Cao

Liu

Liang

Real-Time Integrated Limited-Stop and Short-Turning Bus Control with Stochastic Travel Time. Journal of Advanced Transportation, Vol. 2017, 2017. https://doi.org/10.1155/2017/2960728.

23.

Bouyahia

Haddad

Jabeur

Moh

A. N. S.

Optimization of Chartered Buses Routes Under Uncertainties Using Probabilistic Vehicle Routing Problem Modeling. Procedia Computer Science, Vol. 130, 2018, pp. 644–651.

24.

Babaei

Rajabi-Bahaabadi

School Bus Routing and Scheduling with Stochastic Time-Dependent Travel Times Considering On-Time Arrival Reliability. Computers & Industrial Engineering, Vol. 138, 2019, p. 106125.

25.

Lee

Cen

H. K.

Zonal-Based Flexible Bus Service Under Elastic Stochastic Demand. Transportation Research Part E: Logistics and Transportation Review, Vol. 152, 2021, p. 102367.

26.

Chao

Multi-Objective Optimization of Real-Time Customized Bus Routes Based on Two-Stage Method. Physica A: Statistical Mechanics and its Applications, Vol. 537, 2020, p. 122774.

27.

Ben Abdelaziz

Masri

Alaya

A Recourse Goal Programming Approach for Airport Bus Routing Problem. Annals of Operations Research, Vol. 251, 2017, pp. 383–396.

28.

M. T. M.

Mahmassani

H. S.

Autonomous Minibus Service with Semi-on-Demand Routes in Grid Networks. Transportation Research Record: Journal of the Transportation Research Board, 2023. 2677: 178–200.

29.

Zhou

Yang

Exploring the Uniform Effect of FCM Clustering: A Data Distribution Perspective. Knowledge-Based Systems, Vol. 96, 2016, pp. 76–83.

30.

Gao

Lee

G. M.

Moment-Based Rental Prediction for Bicycle-Sharing Transportation Systems Using a Hybrid Genetic Algorithm and Machine Learning. Computers & Industrial Engineering, Vol. 128, 2019, pp. 60–69.

31.

Rocki

Suda

Accelerating 2-opt and 3-opt Local Search Using GPU in the Travelling Salesman Problem. Proc., IEEE: ACM International Symposium on Cluster, IEEE,New York, 2012.

32.

Hoback

Anderson

Dutta

True Walking Distance to Transit. Transportation Planning & Technology, Vol. 31, No. 6, 2008, pp. 681–692.

33.

Zhao

Chow

L. F.

M. T.

Ubaka

Gan

Forecasting Transit Walk Accessibility: Regression Model Alternative to Buffer Method. Transportation Research Record: Journal of the Transportation Research Board, 2003. 1835: 34–41.

34.

Stanesby

Morse

Magill

Ball

Blizzard

Harpur

Jose

, et al. Characteristics Associated with Willingness to Walk Further than Necessary to the Bus Stop: Insights for Public Transport-Related Physical Activity. Journal of Transport & Health, Vol. 22, 2021, p. 101139.

35.

Wassan

Nagy

Salhi

The Multiple Trip Vehicle Routing Problem with Backhauls: Formulation and a Two-Level Variable Neighborhood Search. Computers & Operations Research, Vol. 78, 2017, pp. 454–467.

36.

Pei

Cheng

Liu

Pardalos

P. M.

Kong

Single-Machine and Parallel-Machine Serial-Batching Scheduling Problems with Position-Based Learning Effect and Linear Setup Time. Annals of Operations Research, Vol. 272, 2019, pp. 217–241.

37.

Sun

Zhang

Shen

Analyzing Spatiotemporal Traffic Line Source Emissions Based on Massive DIDI Online Car-Hailing Service Data. Transportation Research Part D: Transport & Environment, Vol. 62, 2018, pp. 699–714.

38.

Ünsal

Yiğit

Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem. BRAIN. Broad Research in Artificial Intelligence Neuroscience, Vol. 9, No. 2, 2018, pp. 6–21.

39.

Afifi

Dang

D. C.

Moukrim

Heuristic Solutions for the Vehicle Routing Problem with Time Windows and Synchronized Visits. Optimization Letters, Vol. 10, No. 3, 2015, pp. 511–525.

40.

Yiğit

Ünsal

. Using the Ant Colony Algorithm for Real-Time Automatic Route of School Buses. The International Arab Journal of Information Technology, Vol. 13, No. 5, 2016, pp. 559–565.

Collaborative Optimization of Company Commuter Bus Stop Selection and Route Programming Considering Stochastic Travel Time and Demand

Abstract

Keywords

Literature Review

Problem Statement

Solution Algorithm

Commuter Clustering Procedure

FCM Method

Improved FCM Algorithm

Encoding

Framework of the Improved FCM Algorithm

Optimization of Stop Selection and Route Programming

Commuter Bus Stop Selection Sub-Problem

Problem Formulation

Structural Properties

Solution Approach

Commuter Bus Route Programming

Encoding and Decoding Strategy

Initial Solution

Shaking

Neighborhood Structures

Experiments and Results

Data and Parameter Setting

Effects of Proposed Improved FCM

Comparison of VNS with Other Baseline Algorithms

Conclusion

Footnotes

Author Contributions

Declaration of Conflicting Interests

Funding

ORCID iD

References