# An Improved Adaptive Large Neighborhood Search Algorithm for the Heterogeneous Customized Bus Service with Multiple Pickup and Delivery Candidate Locations

Authors: Shouqiang Xue; Rui Song; Shiwei He; Jiuyu An; Youmiao Wang
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

In order to tackle the congestion and environmental issues, customized bus services are proposed and deployed in metropolitan areas. As emerging public transportation services, customized bus services bring passengers more convenience and accessibility. Besides, conventional customized bus services generally organize homogeneous fleet and single location selection to passengers. In this paper, to enhance the mobility and flexibility of customized buses and increase companies’ profit, we propose a new form of customized bus service with heterogeneous fleets and multiple candidate locations. First, a mixed-integer programming model (MIP) is developed to describe the customized bus problem. Compared with the conventional model, the proposed MIP is involved in the case of one passenger with multiple candidate pickup or delivery locations and can be solved by GUROBI on small scale, quickly and efficiently. Second, an improved adaptive large neighborhood search algorithm (ALNSip) is utilized to address the large-scale problem more efficiently. Time slack calculation method is then designed to optimize vehicle timetables, which provides stable and excellent performance for searching feasible solutions. In addition, we propose two inserting operators to deal with the problem with multiple candidate locations and analyse its influence on the results. Finally, we test the performance of the proposed model and algorithm on the numerical experiments. And they are verified the effectiveness and implication in a small-scale case on a simplified Sioux waterfall network and a large-scale problem in Beijing, China. The result shows that ALNSip outperforms other algorithms in searching for more satisfying solutions with higher efficiency. However, the GUROBI solver can obtain the solution to small-scale problems within a shorter time than ALNSip. Furthermore, it can be suggested that the heterogeneous fleets service with multiple candidate locations is helpful to facilitate collaboration among vehicles and optimize pickup and delivery routes in consequence.


---

## Body

## 1. Introduction

The increase in the number of private cars has imposed an impact on potential traffic jams and environmental issues, and in the meanwhile, the increasing number of people has grown interest in enjoying personalized travel services. Therefore, many transportation service providers are gradually focusing their attention on seeking new services to attract more public transport users and increase passengers’ accessibility. In recent years, internet-based customized buses service has become more popular in the market due to its higher accessibility and quicker response, especially in congested metropolitan areas. Since Kirby and Bhatt analysed and discussed in detail about subscribing to the bus service in 1974 [1], the customized bus system (CB) has been continuously developed into a demand-responsive transportation service. Nowadays, some transportation companies have constructed mobile application platforms for customized bus services to collect detailed travel information [2, 3]. With the spatial and temporal characteristics of travel requests taken into considerable consideration, the customized bus service platform can aggregate similar requests and design bus routes. To the best of our knowledge, some customized bus services have been deployed in physical road networks of metropolitan areas such as Beijing.According to different characteristics of travel requests, customized bus services can be usually divided into four major categories: “Customized commuter bus,” “Customized school bus,” “Customized business bus,” and “Customized community bus,” and other kinds of customized feeder or shuttle bus systems [2]. This paper focuses on the customized commuter bus, which offers commute shuttle service and takes customers from the residential community to the workplace. This is also the most important CB system. It is noted that there are some unique service features about commuters. They usually book relatively fixed demands and change them in different weeks or months. Therefore, the customized bus services will be updated according to new requests in each optimization time (e.g., one month and one week) [4].The detailed operating procedure of the customized bus service is presented in Figure1. Each passenger needs to input his/her request through the network and platform to complete the service-design process. This paper mainly focuses on the process to plan and deploy new routes based on fail-to-match requests in the requests pool. If requests cannot be matched with the existing routes, these requests will be put into the requests pool. When the number of booked people meets the minimum load requirement, the platform will plan new routes deployed in the physical road network based on the requests in the requests pool.Figure 1
The entire process of the customized bus service.There are several notable features of customized bus problems. As can be seen from the above operating procedure, compared to the traditional bus routing problem, customized bus problems pay more attention to individual passenger request information. Bus route and specific timetables are updated and designed by considering more about companies’ profit and various characteristics of passenger demands, including origin-destination pairs and time windows. In the field of operations research, the problem regarding passengers’ pickup and delivery locations with time windows can be classified as a special vehicle planning problem [5]. With the consideration of all constraints, it is worthwhile but challenging to design reasonable routes and specific timetables. Furthermore, it is also of great significance to enrich the personalized public transportation services and provide highly reliable and accessible trip services for commuters living in congested metropolitan areas.The remainder of this paper is organized as follows. The next section describes an overview of earlier research. Section3 describes the MIP model. In Section 4, we describe ALNSip in detail. Section 5 reports the test of the MIP and ALNSip on numerical experiments. Finally, Section 6 summarizes the research content and future research directions of the paper.


## 2. Literature Review

Customized bus service can be regarded as a request-oriented public transportation service based on its unique service features. In earlier research, on-demand transportation was described as a set of vehicle routing problems with pickup and deliveries (VRPPD). Nagy et al. [6] divided the previous studies about the problem into three main categories: simultaneous pickups and deliveries, mixed pickups and deliveries, and delivery-first, pickup-second. In subsequent research, VRPPD is gradually evolved into different versions due to the specific problems and traffic conditions. When the pickup and delivery locations with time windows are determined, VRPPD can be seen as pickup and delivery problems with time windows (PDPTW). In general, the exact algorithm is a major way to solve multivehicle pickup and delivery problems in most studies [7–9]. Ropke et al. [10] proposed a new branch-and-cut-and-price algorithm to tackle the problem, which dynamically introduced valid inequalities and heuristic algorithm to enhance algorithm performance. Wang et al. [11–14] constructed related optimization models and proposed algorithms based on state-space-time network to effectively solve some pickup and delivery problems.With the development of mobile technology, passengers can book vehicles and pay for trips through smartphones or platforms. In the operations research, this type of transportation service can be classified as dial-a-ride problems (DARP). Compared to VRPPD, DARP offers more unique characteristics, including depots, time window, vehicles capacity, ride time, and route duration. Stein [15] proposed the first DARP model and gave the bounds of both static and dynamic models. For static and dynamic DARP versions, Psaraftis et al. [9] developed a dynamic programming algorithm for the problem with a single vehicle. For the multiobjective problem in DARP, Jorgensen et al. [16] considered the total weight of multiple objects and proposed a Granular Tabu Search algorithm to solve the static DARP. In addition, Garaix et al. [17] and Schilde et al. [18] considered optimizing multiobjective problems by priority. And Paquette et al. [19] used the Pareto boundary to solve it.The original application of DARP was a nonprofit dial-a-ride system service (DAR) for the elderly and the disabled. Relevant constraints include ride and waiting time, pickup or delivery with time windows, vehicles capacity, and fleet systems [20–23]. However, due to market demand and emerging communication technology, DARP has been applied in the field of public transportation. Based on the on-demand transportation system developed in rural France, Garaix et al. [17] designed a free-riding system that maximized customer occupancy and used the column generation way to deal with it. The problem where not all passengers are collected in advance is classified as dynamic on-demand transportation services [5]. Pillac et al. [24] introduced the concept of dynamic problem and reviewed the solution methods about it. Alonso-Mora et al. [25] paid attention to the dynamic ride-sharing problem with high-capacity and proposed a pairwise shareability graph to compute feasible trips. Studies about customized bus service, one type of demand-responsive transport service, are also gradually increasing. Liu et al. [2] introduced the development and application of customized bus services in China. To solve customized bus service-design problems, Tong et al. [4] proposed a multicommodity optimization model and provided a Lagrangian decomposition-based solution algorithm to solve the routing problems.Furthermore, in terms of solving route planning problems, the neighborhood search algorithm always has a high performance [26–31]. To improve the performance of neighborhood search algorithm, Ropke and Pisinger [32] proposed an adaptive large neighborhood search algorithm for the first time (ALNS). In the subsequent studies, it is found that ALNS has an outstanding performance in solving large-scale route planning problems with NP-hard, and it has been applied to different fields. To stack with the pollution routing problem (PRP), Demir et al. [33] improved the ALNS algorithm and updated some mechanisms, applicable to the problem. Polat et al. [34] proposed a mixed-integer mathematical optimization model and design a perturbation-based variable neighborhood search heuristic to solve the vehicle routing problem with simultaneous pickup and delivery with time limit (VRPSPDTL). To study the share-a-ride problem, Li et al. [35] proposed an adaptive large neighborhood search method with time slack. Yu et al. [36] and Yu et al. [37] developed an adaptive large neighborhood search heuristic to solve green vehicle routing problems in large-scale instances. In addition, ALNS is also widely used in the vehicle routing problem with drones, a supply chain, carsharing service, train stop planning, timetabling, and other fields [38–41]. Furthermore, there are also some hybridization and improvement from ALNS and other algorithms [42–44].In the paper, to further improve passengers’ accessibility and increase bus operators’ profits, we consider adding two strategies (Strategy 1 and Strategy 2) into customized bus services.(I)
Strategy 1: the heterogeneous fleets with different operating cost and vehicle capacity can be dispatched to offer customized bus service(II)
Strategy 2: passengers can choose multiple candidate locations as their pickup and delivery locationsThe existing literature still lacks relative research on the heterogeneous customized bus service problem with multiple pickup and delivery candidate locations. With the comprehensive consideration about the new service form, this paper builds a new MIP model based on the classical DARP model proposed by Cordeau [20] to address the practical and theoretical challenges. At the same time, to effectively solve large-scale problems, we introduce and improve ALNS (ALNSip) proposed by Li et al. [35] by designing corresponding operators (MI.1 and MI.2) to address new challenges with multiple candidate locations. In addition, given the complexity of the problem with time window, a time slack calculation method is utilized to adjust vehicle arriving time during searching feasible solutions.In summary, this study has several contributions in theory and application: (1) constructing a new bus service with heterogeneous fleets and multiple candidate locations to improve conventional service quality and facilitate collaboration among different buses, (2) formulating relative optimization model with considering the different time windows, capacities, passenger assignment, and location selection to maximize operator’s profit, (3) designing an improved heuristic algorithm based on ALNS, including a time slack calculation method and two inserting operators to address the large-scale problem with high efficiency.


## 3. Mathematical Model

The PDPTW and the DARP can be modelled using classical formulation (see, e.g., Cordeau [20] and Dumas et al. [7]). It is usually utilized to optimize the problem where each request is represented by a set of unique pickup location and delivery location. In this paper, to further tackle the challenges with multiple depots, heterogeneous fleets and multiple candidate locations, we propose a MIP model to deal with the problem, where the state node concept is utilized to describe the relationship between every passenger and their pickup and delivery locations.


### 3.1. Problem Statement

We define the problem on a direct graphG=S,Λ, where S is the set of all state nodes and Λ is the set of all arcs connecting state nodes. Each state node p,i in S=p,i|p∈P,i∈V means the passenger p is picked up and delivered at the physical location i. P, V, and K mean, respectively, the set of passenger requests, the set of physical locations, and the set of customized buses. For each passenger p0, p0,i∈Sp is the set of state nodes for passenger p0 picked up, and the same for p0,i∈Sd is the set of state nodes for passenger p0 delivered. Λ=p,i,q,j|p,i∈S,q,j∈S indicates one directed arc from one state node p,i to another state node q,j, where bus moves from location i to location j to offer service for passenger p and passenger q. Although one passenger may have multiple pickup and delivery locations, he/she must be picked up or delivered at a unique location.To guarantee bus operators’ profit, the number of passengers the bus serves must meet the minimum load constraint. As a result, if the loading capacity of busk is Capku, the number of passengers on the bus must be more than or equal to Capkl. Given a number of service features from customized buses, some unreasonable passenger requests may be rejected. The rejected passengers in the model are served by the vehicle k∈KV, where KV is the set of virtual vehicles. Expensive cost from virtual vehicles is the penalty cost for unserved customers. The remaining passengers are served by the buses k∈KL∪KS, where KL is the bus set with large capacity.Pretreatment: before solving the model, it is necessary to find all potential state nodesS and construct the arcs Λ among these state nodes.


### 3.2. Related Definitions and Optimization Model

To formulate DARP with multiple candidate locations into a mathematical model, all parameters used in the model are defined in Table1.Table 1
Notation and definition in the model.
SetDefinitionPSet of all passengersSSet of all state nodes,S=Sp∪SdΛSet of all arcs connecting state nodes;Λ=p,i,q,j|p,i∈S,q,j∈S indicates one directed state arc from one state node p,i to another state node q,j, where bus moves from location i to location j to offer service for passenger p and passenger qKSet of all customized bus:K=KL∪KS∪KVKLSet of customized bus with large capacityKSSet of customized bus with small capacityKVSet of virtual customized busVSet of all physical locations:V=Vp∪Vd∪VO∪VDVpSet of pickup locations in the transportation networkVdSet of delivery locations in the transportation networkVOSet of start depots of customized bus in the transportation networkVDSet of end depots of customized bus in the transportation networkSpState node means the passenger is picked up at the location:p,i∈Sp,p∈P,i∈VpSdState node means the passenger is delivered at the location,p,i∈Sd,p∈P,i∈VdParametersETotal profitsCdTotal departure costCfTotal fuel costCpTotal penalty costtp0The ticket pricecdkDeparture cost of busk∈KcfkThe fuel cost per unit time of busk∈KCapkuThe maximum load capacity of customized busk∈KCapklThe minimum load capacity of customized busk∈Ke0p,l0pTime window when passengerp is picked up, where e0p and l0p represent the earliest and latest time, respectivelye1p,l1pTime window when passengerp is delivered, where e1p and l1p represent the earliest and latest time, respectivelyp,iState node passengerp is picked up or delivered at location i, p,i∈STp,iThe time of passengerp is picked up or delivered at location iti,jTravel time between locationi and j, i,j∈VMBig numberDecision variableμp,iAn auxiliary variable: it indicates the order of state nodep,i in the routexv,p,ikCustomized busk departs from depots or return depotsyp,i,q,jkThe busk moves from the state node p,i to the state node q,jThe total income mainly refers to the tickets income. The cost includes the following three parts: the fixed cost of each bus dispatched, fuel cost on the arcs, and penalty cost for unserved passengers.(1)MaxE−Cd−Cf−Cp.(2)E=∑k∈KL∪KS∑p,i∈Sp∑q,j∈Stp0⋅yp,i,q,jk.(3)Cd=∑k∈KL∪KS∑v∈VO∑p,i∈Spcdk⋅xv,p,ik.(4)Cp=∑k∈KV∑v∈VO∑p,i∈Spcdk⋅xv,p,ik.(5)Cf=∑k∈KL∪KS∑v∈VO∑p,i∈Vpcfk⋅tv,i⋅xv,p,ik+∑k∈KL∪KS∑p,i∈Sp∑q,j∈Scfk⋅ti,j⋅yp,i,q,jk.(6)∑v∈VO∑p,i∈Spxv,p,ik≤1,fork∈K.(7)∑v∈VO∑p,i∈Spxv,p,ik=∑v∈VD∑q,j∈Sdxv,q,jk,fork∈K.(8)∑k∈K∑v∈Vp,i∑p0,i∈Spxv,p0,ik+∑k∈K∑q,j∈S∑p0,i∈Spyq,j,p0,ik=1,forp0∈P.(9)∑k∈K∑v∈VD∑p0,i∈Sdxv,p0,ik+∑k∈K∑q,j∈S∑p0,i∈Sdyp0,i,q,jk=1,forp0∈P.(10)∑p0,i∈Sp∑q,j∈Syp0,i,q,jk=∑p0,i∈Sd∑q,j∈Syq,j,p0,ik,forp0∈P,fork∈K.(11)∑v∈VOxv,p0,ik+∑q,j∈Syq,j,p0,ik=∑q,j∈Syp0,i,q,jk,fork∈K,forp0,i∈Sp.(12)∑v∈VDxv,q0,jk+∑p,i∈Syq0,j,p,ik=∑p,i∈Syp,i,q0,jk,fork∈K,forq0,j∈Sd.(13)∑q,j∈S∑p,i∈Syp,i,q,jk≤∑v∈VO∑p,i∈Spxv,p,ik⋅2⋅Capku−1,fork∈K.(14)∑q,j∈S∑p,i∈Syp,i,q,jk≥∑v∈VO∑p,i∈Spxv,p,ik⋅2⋅Capkl−1,fork∈K.(15)Tq,j≥Tp,i−M⋅1−∑k∈Kyp,i,q,jk,forp,i,q,j∈S.(16)Tp,i=e0p,l0p,forp,i∈Sp,e1p,l1p,forp,i∈Sd,.(17)μq,j≥μp,i+1−M⋅1−∑k∈Kyp,i,q,jk,forp,i,q,j∈S.(18)xv,p,ik=0,1,fork∈K,forv∈VO∪VD,forp,i∈S.(19)yp,i,q,jk=0,1,fork∈K,forp,i,q,j∈S.The objective function (1) maximizes total profits. Constraints (2)–(5) are ticket income, total departure cost, penalty cost, and fuel cost, respectively. And constraints (3) and (4) can be represented by constraint (20).(20)Cd+Cp=∑k∈KL∪KS∑v∈VO∑p,i∈Spcdk⋅xv,p,ik+∑k∈KV∑v∈VO∑p,i∈Spcdk⋅xv,p,ik=∑k∈K∑v∈VO∑p,i∈Spcdk⋅xv,p,ik.For vehicles, constraints (6) and (7) ensure that each vehicle travels at most once, and each one leaves start depots and enters start depots. For some customers offering multiple locations as their candidate pickup or delivery locations, he/she can only be picked up or delivered at one location in the end, and the platform also will choose one location from their multiple pickup or delivery candidate locations. Therefore, constraints (8) and (9) ensure that all passengers are served and each passenger is picked up or delivered at a unique location. In addition, constraint (10) indicates that one person is just picked up and delivered by the same vehicle. For network flow, constraints (11) and (12) enforce traffic flow balance. If vehicle k arrives in location i to serve one person, it will leave from location i to location j to serve another one. Constraint (13) guarantees that the total number of served passengers cannot exceed the capacity of vehicle. To achieve the profit goal, constraint (14) ensures a minimum number of passengers in the vehicle. Constraints (15) and (16) enforce each passenger to be picked up or delivered within he/her time windows. Constraint (17) is subtour elimination constraint. Finally, constraints (18) and (19) define the binary decision variables. If the vehicle k moves from the state node p,i to the state node q,j, then yp,i,q,jk=1; otherwise, yp,i,q,jk=0. If one vehicle departs from start depots or returns to end depots, then xv,p,ik=1; otherwise, xv,p,ik=0.


## 3.1. Problem Statement

We define the problem on a direct graphG=S,Λ, where S is the set of all state nodes and Λ is the set of all arcs connecting state nodes. Each state node p,i in S=p,i|p∈P,i∈V means the passenger p is picked up and delivered at the physical location i. P, V, and K mean, respectively, the set of passenger requests, the set of physical locations, and the set of customized buses. For each passenger p0, p0,i∈Sp is the set of state nodes for passenger p0 picked up, and the same for p0,i∈Sd is the set of state nodes for passenger p0 delivered. Λ=p,i,q,j|p,i∈S,q,j∈S indicates one directed arc from one state node p,i to another state node q,j, where bus moves from location i to location j to offer service for passenger p and passenger q. Although one passenger may have multiple pickup and delivery locations, he/she must be picked up or delivered at a unique location.To guarantee bus operators’ profit, the number of passengers the bus serves must meet the minimum load constraint. As a result, if the loading capacity of busk is Capku, the number of passengers on the bus must be more than or equal to Capkl. Given a number of service features from customized buses, some unreasonable passenger requests may be rejected. The rejected passengers in the model are served by the vehicle k∈KV, where KV is the set of virtual vehicles. Expensive cost from virtual vehicles is the penalty cost for unserved customers. The remaining passengers are served by the buses k∈KL∪KS, where KL is the bus set with large capacity.Pretreatment: before solving the model, it is necessary to find all potential state nodesS and construct the arcs Λ among these state nodes.


## 3.2. Related Definitions and Optimization Model

To formulate DARP with multiple candidate locations into a mathematical model, all parameters used in the model are defined in Table1.Table 1
Notation and definition in the model.
SetDefinitionPSet of all passengersSSet of all state nodes,S=Sp∪SdΛSet of all arcs connecting state nodes;Λ=p,i,q,j|p,i∈S,q,j∈S indicates one directed state arc from one state node p,i to another state node q,j, where bus moves from location i to location j to offer service for passenger p and passenger qKSet of all customized bus:K=KL∪KS∪KVKLSet of customized bus with large capacityKSSet of customized bus with small capacityKVSet of virtual customized busVSet of all physical locations:V=Vp∪Vd∪VO∪VDVpSet of pickup locations in the transportation networkVdSet of delivery locations in the transportation networkVOSet of start depots of customized bus in the transportation networkVDSet of end depots of customized bus in the transportation networkSpState node means the passenger is picked up at the location:p,i∈Sp,p∈P,i∈VpSdState node means the passenger is delivered at the location,p,i∈Sd,p∈P,i∈VdParametersETotal profitsCdTotal departure costCfTotal fuel costCpTotal penalty costtp0The ticket pricecdkDeparture cost of busk∈KcfkThe fuel cost per unit time of busk∈KCapkuThe maximum load capacity of customized busk∈KCapklThe minimum load capacity of customized busk∈Ke0p,l0pTime window when passengerp is picked up, where e0p and l0p represent the earliest and latest time, respectivelye1p,l1pTime window when passengerp is delivered, where e1p and l1p represent the earliest and latest time, respectivelyp,iState node passengerp is picked up or delivered at location i, p,i∈STp,iThe time of passengerp is picked up or delivered at location iti,jTravel time between locationi and j, i,j∈VMBig numberDecision variableμp,iAn auxiliary variable: it indicates the order of state nodep,i in the routexv,p,ikCustomized busk departs from depots or return depotsyp,i,q,jkThe busk moves from the state node p,i to the state node q,jThe total income mainly refers to the tickets income. The cost includes the following three parts: the fixed cost of each bus dispatched, fuel cost on the arcs, and penalty cost for unserved passengers.(1)MaxE−Cd−Cf−Cp.(2)E=∑k∈KL∪KS∑p,i∈Sp∑q,j∈Stp0⋅yp,i,q,jk.(3)Cd=∑k∈KL∪KS∑v∈VO∑p,i∈Spcdk⋅xv,p,ik.(4)Cp=∑k∈KV∑v∈VO∑p,i∈Spcdk⋅xv,p,ik.(5)Cf=∑k∈KL∪KS∑v∈VO∑p,i∈Vpcfk⋅tv,i⋅xv,p,ik+∑k∈KL∪KS∑p,i∈Sp∑q,j∈Scfk⋅ti,j⋅yp,i,q,jk.(6)∑v∈VO∑p,i∈Spxv,p,ik≤1,fork∈K.(7)∑v∈VO∑p,i∈Spxv,p,ik=∑v∈VD∑q,j∈Sdxv,q,jk,fork∈K.(8)∑k∈K∑v∈Vp,i∑p0,i∈Spxv,p0,ik+∑k∈K∑q,j∈S∑p0,i∈Spyq,j,p0,ik=1,forp0∈P.(9)∑k∈K∑v∈VD∑p0,i∈Sdxv,p0,ik+∑k∈K∑q,j∈S∑p0,i∈Sdyp0,i,q,jk=1,forp0∈P.(10)∑p0,i∈Sp∑q,j∈Syp0,i,q,jk=∑p0,i∈Sd∑q,j∈Syq,j,p0,ik,forp0∈P,fork∈K.(11)∑v∈VOxv,p0,ik+∑q,j∈Syq,j,p0,ik=∑q,j∈Syp0,i,q,jk,fork∈K,forp0,i∈Sp.(12)∑v∈VDxv,q0,jk+∑p,i∈Syq0,j,p,ik=∑p,i∈Syp,i,q0,jk,fork∈K,forq0,j∈Sd.(13)∑q,j∈S∑p,i∈Syp,i,q,jk≤∑v∈VO∑p,i∈Spxv,p,ik⋅2⋅Capku−1,fork∈K.(14)∑q,j∈S∑p,i∈Syp,i,q,jk≥∑v∈VO∑p,i∈Spxv,p,ik⋅2⋅Capkl−1,fork∈K.(15)Tq,j≥Tp,i−M⋅1−∑k∈Kyp,i,q,jk,forp,i,q,j∈S.(16)Tp,i=e0p,l0p,forp,i∈Sp,e1p,l1p,forp,i∈Sd,.(17)μq,j≥μp,i+1−M⋅1−∑k∈Kyp,i,q,jk,forp,i,q,j∈S.(18)xv,p,ik=0,1,fork∈K,forv∈VO∪VD,forp,i∈S.(19)yp,i,q,jk=0,1,fork∈K,forp,i,q,j∈S.The objective function (1) maximizes total profits. Constraints (2)–(5) are ticket income, total departure cost, penalty cost, and fuel cost, respectively. And constraints (3) and (4) can be represented by constraint (20).(20)Cd+Cp=∑k∈KL∪KS∑v∈VO∑p,i∈Spcdk⋅xv,p,ik+∑k∈KV∑v∈VO∑p,i∈Spcdk⋅xv,p,ik=∑k∈K∑v∈VO∑p,i∈Spcdk⋅xv,p,ik.For vehicles, constraints (6) and (7) ensure that each vehicle travels at most once, and each one leaves start depots and enters start depots. For some customers offering multiple locations as their candidate pickup or delivery locations, he/she can only be picked up or delivered at one location in the end, and the platform also will choose one location from their multiple pickup or delivery candidate locations. Therefore, constraints (8) and (9) ensure that all passengers are served and each passenger is picked up or delivered at a unique location. In addition, constraint (10) indicates that one person is just picked up and delivered by the same vehicle. For network flow, constraints (11) and (12) enforce traffic flow balance. If vehicle k arrives in location i to serve one person, it will leave from location i to location j to serve another one. Constraint (13) guarantees that the total number of served passengers cannot exceed the capacity of vehicle. To achieve the profit goal, constraint (14) ensures a minimum number of passengers in the vehicle. Constraints (15) and (16) enforce each passenger to be picked up or delivered within he/her time windows. Constraint (17) is subtour elimination constraint. Finally, constraints (18) and (19) define the binary decision variables. If the vehicle k moves from the state node p,i to the state node q,j, then yp,i,q,jk=1; otherwise, yp,i,q,jk=0. If one vehicle departs from start depots or returns to end depots, then xv,p,ik=1; otherwise, xv,p,ik=0.


## 4. An Adaptive Large Neighborhood Search Algorithm for Customized Bus Service System

In this section, we describeALNSip and its application to the problem in great detail. The ALNSip constructs the initial feasible solution using the greedy algorithm represented in Section 4.1. It uses several competing removal and insertion algorithms and chooses a reasonable set of operators by the score of each operator during the search. The removal algorithms are described in Section 4.3, and the insertion algorithms are described in Section 4.4. Furthermore, we propose a time slack calculation strategy to adjust timetables for searching more feasible solutions.


### 4.1. Initial Solution Construction

A greedy insertion algorithm is used to search for a feasible initial solution. Requests in the setP are inserted one by one in a random order into routes. The entire process can be shown in the pseudocode of Algorithm 1.Algorithm 1: Initial solution.
(1)
Construct the set of passengersP;(2)
Repeat(3)
Construct a new route;(4)
Insert one passenger into the route, suitable for all constraints;(5)
Remove the passenger from P;(6)
If the number of passengers in the current bus exceeds its capacity then(7)
Return to step 3;(8)
Else(9)
Return to step 4;(10)
End if(11)
Until there is no new route can be constructed, remain passengers in P cannot be served and be refused;(12)
Get all routes and passengers refused as initial solutionS;


### 4.2.ALNSip Process

To diversify the search, theALNSip selects suitable removal and insertion operators by a roulette wheel mechanism at every iteration. We define every UpI times as a cycle. The probabilities of choosing operator i in the kth cycle, pik, is updated as formulation pik=wik/∑wik, where wik is the weight of the operator i in the kth cycle. For every UpI iteration, weights are recalculated using the scores obtained as formulation wik=wik−11−γ+γσik−1/mik−1, where γ is the weight coefficient and σik−1 and mik−1 are the overall score and selected times of the operator i in k−1th cycle. If the operator i is chosen, its score is increased by λqq=1,2,3or4, as shown in Table 2, according to its performance at the current iteration. For every UpI iteration, all scores are reset to zero. Finally, the entire process of ALNSip is completed under U iterations, as shown in Algorithm 2.Algorithm 2:ALNSip algorithm procedure.
(1)
Input initial solutionS, the objective values of initial solution S as initial values of fcurrentbestS and fglobalbestS;(2)
i⟵1(3)
Whilei<=U(4)
Select a couple of removal and insertion operators using a roulette wheel mechanism to generate new feasible solution S′;(5)
Iff′S′ > fglobalbestSthen(6)
Score of removal and insertion operators is increased by λ1; fglobalbestS⟵f′S′; fcurrentbestS⟵f′S′; S⟵S′;(7)
Else iff′S′≥fcurrentbestS and the solution has not been accepted before then(8)
Score of removal and insertion operators is increased by λ2; fcurrentbestS⟵f′S′; S←S′;(9)
Else iff′S′≥fcurrentbestS and the solution has been accepted before then(10)
Score of removal and insertion operators is increased by λ3; fcurrentbestS⟵f′S′; S←S′;(11)
Else if random value ρ′≤ρthen(12)
Score of removal and insertion operators is increased by λ4; fcurrentbestS⟵f′S′; S←S′;(13)
End if(14)
ifmodi,UpI=0then(15)
Update weight of each operator;(16)
End if(17)
i⟵i+1;(18)
Get the efficient feasible solutionS;Some parameters are shown in Table2 by using the tuning strategy proposed by Ropke and Pisinger [32] and Li et al. [35] to obtain values. When just one parameter is adjusted, the rest will be fixed. Finally, the setting with the best average behaviour is chosen.The acceptance criterion adopts the simulated annealing criterion shown as Algorithm2, where f′S′ is the objective value of the new solution, fcurrentbestS is the objective value of the current solution, and fglobalbestS is the objective value of the global optimal solution. The probability that we accept new solution is ρ=e−f′S′−fcurrentbestS/T, where T=T0ε is the current temperature, ε is the cooling rate, and T0 is the initial temperature.Table 2
Parameters used inALNSip.
ParametersDefinitionValueUTotal iterations5000UpICycle500λ1A new global optimal solution17λ2A new and better than the current solution13λ3Accepted before and better than the current solution5λ4A worse solution4T0Initial temperature100εThe cooling rate0.99927γThe weight coefficient0.3ϕ1The Shaw coefficients3ϕ2The Shaw coefficients2ϕ3The Shaw coefficients2uDelete parameter0.15∼0.3


### 4.3. Removal Algorithms (RA)

In each iteration, a removal operator is selected from RA and removes the total number of passenger requestsnp=u⋅P in the solution to break the current solution, where u is the random removal parameter. These requests removed are added to the perturbation set RP. The section has designed five operators, the first three are chosen from Ropke and Pisinger [32], the fourth operator is adapted from Demir et al. [33], and the last one is motivated by Cordeau and Laporte [5].R1-Random Removal: the operator randomly removesnp requests from the current solution put them into the set P.R2-Worst-Removal: the operator calculates theΔfp value of all passengers, where Δfp denotes the change in objective value incurred by removing passenger request p from current position. Then, np requests with the greatest value Δfp are removed and put into the set RP.R3-Shaw Removal: to diversify the search, the operate measures the similarity levelRij between passenger i and passenger j through the correlation function Rij=ϕ1⋅dijp+dijd+ϕ2⋅tip−tjp+tid−tjd+ϕ3⋅lij, where ϕ1−ϕ3 are the Shaw coefficients, dijp is the distance between pickup locations of passengers i and j, dijd is the distance between delivery locations, tip is the boarding time, tid is the alighting time, lij indicates whether passengers i and j are in the same vehicle (lij=−1) or not (lij=1). The operator randomly chooses one customer and calculates all Rij between the passenger and other ones. Then, it removes np requests with the smallest similarity level.R4-Random Route Removal: This operator randomly removes all passenger requests of one route and puts them into the setRP.R5-Tabu Removal: the operator is spired by tabu search. It keeps a track of the times passengeri has been removed and then removes np requests with the smallest removed times and puts them to the set RP.


### 4.4. Insertion Algorithms (IA)

After a number of passenger requests are removed from the vehicle routing solution, insertion operators are used to repair and generate new solution. The first three operators are adapted from Ropke and Pisinger [32], the fourth one is motivated by Cordeau and Laporte [5], the fifth is inspired by Demir et al. [33], while the last two are the insertion operators designed for the problem with multiple pickup and delivery locations in the paper.I1-Greedy Insertion: the requests in the setRP are sequentially removed from RP set and inserted into the best location.I2-Regret-2-Insertion: to avoid the myopia of local optimization from greedy algorithm, the operator calculates the regret-k value, where k=2. And then it sequentially inserts the request with the greatest regret value.I3-Regret-3-Insertion: this operator is similar toI2 and makes k=3.I4-One by one Insertion: the operator is similar toI1. The difference is that I4 inserts one request into the best location after removing it, rather than reinserting one by one after removing all requests.I5-TimeWindows Insertion: to tackle with the impact of the time feature from the problem,I5 gets the similarity level of all removed passengers in terms of time window, that is, the value of time window difference, l0p−e0p+l1p−e1p. And then, it sequentially inserts the request with the greatest value.For the passenger with multiple locations, we need to combine one ofI1–I5 and one of the last two operators to complete the insertion of the passenger. For this, one of the following two operators is randomly selected:MI.1-Random insertion based on multiple locations:MI.1 principle randomly selects a candidate location as the current pickup or delivery location of the passenger and then inserts the passenger using I1–I5.MI.2-One-by-one insertion based on multiple locations:MI.2 principle compares the performance of all candidate locations using I1–I5 separately and selects the candidate location with the best performance as the current pickup or delivery location of the passenger and inserts it.


### 4.5. Time Slack Calculation Strategy

As seen in Figure2, if we break and repair the solution using RA and IA operators without adjusting timetables, it is possible to fail to search more feasible insertion solutions. Therefore, we design the instance to simulate the issue, where the maximum ride time of each passenger is 40 and the service time is 0. Time window, pickup, and delivery locations of two passengers are presented in Figure 2.Figure 2
The instance without time slack calculation strategy.If we just use Algorithm3 without any ways to adjust timetables, it can be found that the ride time of passenger 1 is more than 40 and passenger 2 cannot be inserted into the route as shown in Figure 2. After using Algorithm 4 to change the timetables, passenger 2 can be inserted in the position and the insertion solution is feasible, as shown in Figure 3. Therefore, it is very essential to adjust timetables to further improve the solution during the search. The time slack calculation strategy we proposed can test the feasibility of any insertion cases in time constraints. The symbols that may be used in Section 4.5 are shown in Table 3.Figure 3
The instance with time slack calculation strategy.Algorithm 3:Greedy time calculate strategy.
(1)
Input initial informationAT1=Eal1, DT1=AT1+ST and WT1=0;(2)
u⟵2;(3)
Whileu≤nATu=maxDTu−1+tu−1,u,Ealu;DTu=ATu+ST;WTu=min0,Ealu−ATu;u⟵u+1;(4)
EndTable 3
Notations and definitions of symbols used in Section4.5.
SymbolDefinitionMrdThe maximum ride time of one passengernThe total number of locations in the routeSTService timeATiArrival time of vehicle at locationiDTiDeparture time of vehicle at locationiWTiWaiting time of vehicle at locationiRDiActual ride time of passenger on the routeEali,LaTiTime window of passenger at locationiti,jThe travel time between locationi and location jTitwOne type of time slack based on time window of the passenger on locationiTirdOne type of time slack based on the maximum ride time of the passenger on locationiMTSiA maximum time slack of locationiMTSi′One time slack of locationiMTSi″One time slack of locationiAs shown in Figure2, the greedy algorithm just guarantees time window constraint but cannot consider the impact of the maximum ride time. In addition, it may also cause more waiting time.Titw is the adjustable time bus can delay its arrival at the location i according to the timetable and time window:(21)Titw=LaTi−ATi.Tird is the adjustable time bus can delay its arrival at the location i within the maximum ride time constraint:(22)Tird=Mrd−RDi.MTSi'′ means the adjustable time vehicle can delay its arrival at the location i, where its value may affect time constraints at other locations.(23)MTSi′′=minTitw,Tird.Note:(1)
If both boarding and alighting locations of one passenger are behind the locationu, MTSi'′ on pickup location or delivery location of the passenger is Titw(2)
If only delivery locationi of one passenger is behind the location u and Tird<0, MTSi'′ of the location i is TitwMTSi′ means the adjustable time of the vehicle at location i based on waiting time, where its value may affect time constraints of other locations.MTSi means the maximum adjustable time of the vehicle at the location i, where its value cannot affect time constraints at other locations.The relationship amongMTSi″, MTSi′, and MTSi and the entire process of time slack calculation strategy is shown as Algorithm 4.


### 4.6. Stopping Criteria

There are two types of stopping criteria used to avoid local optimization:(i)
When the current iteration exceeds the maximum iteration, the algorithm operation ends and the result is output(ii)
When the temperatureT=T0ε is less than 0.5, the algorithm operation ends and the result is output


## 4.1. Initial Solution Construction

A greedy insertion algorithm is used to search for a feasible initial solution. Requests in the setP are inserted one by one in a random order into routes. The entire process can be shown in the pseudocode of Algorithm 1.Algorithm 1: Initial solution.
(1)
Construct the set of passengersP;(2)
Repeat(3)
Construct a new route;(4)
Insert one passenger into the route, suitable for all constraints;(5)
Remove the passenger from P;(6)
If the number of passengers in the current bus exceeds its capacity then(7)
Return to step 3;(8)
Else(9)
Return to step 4;(10)
End if(11)
Until there is no new route can be constructed, remain passengers in P cannot be served and be refused;(12)
Get all routes and passengers refused as initial solutionS;


## 4.2.ALNSip Process

To diversify the search, theALNSip selects suitable removal and insertion operators by a roulette wheel mechanism at every iteration. We define every UpI times as a cycle. The probabilities of choosing operator i in the kth cycle, pik, is updated as formulation pik=wik/∑wik, where wik is the weight of the operator i in the kth cycle. For every UpI iteration, weights are recalculated using the scores obtained as formulation wik=wik−11−γ+γσik−1/mik−1, where γ is the weight coefficient and σik−1 and mik−1 are the overall score and selected times of the operator i in k−1th cycle. If the operator i is chosen, its score is increased by λqq=1,2,3or4, as shown in Table 2, according to its performance at the current iteration. For every UpI iteration, all scores are reset to zero. Finally, the entire process of ALNSip is completed under U iterations, as shown in Algorithm 2.Algorithm 2:ALNSip algorithm procedure.
(1)
Input initial solutionS, the objective values of initial solution S as initial values of fcurrentbestS and fglobalbestS;(2)
i⟵1(3)
Whilei<=U(4)
Select a couple of removal and insertion operators using a roulette wheel mechanism to generate new feasible solution S′;(5)
Iff′S′ > fglobalbestSthen(6)
Score of removal and insertion operators is increased by λ1; fglobalbestS⟵f′S′; fcurrentbestS⟵f′S′; S⟵S′;(7)
Else iff′S′≥fcurrentbestS and the solution has not been accepted before then(8)
Score of removal and insertion operators is increased by λ2; fcurrentbestS⟵f′S′; S←S′;(9)
Else iff′S′≥fcurrentbestS and the solution has been accepted before then(10)
Score of removal and insertion operators is increased by λ3; fcurrentbestS⟵f′S′; S←S′;(11)
Else if random value ρ′≤ρthen(12)
Score of removal and insertion operators is increased by λ4; fcurrentbestS⟵f′S′; S←S′;(13)
End if(14)
ifmodi,UpI=0then(15)
Update weight of each operator;(16)
End if(17)
i⟵i+1;(18)
Get the efficient feasible solutionS;Some parameters are shown in Table2 by using the tuning strategy proposed by Ropke and Pisinger [32] and Li et al. [35] to obtain values. When just one parameter is adjusted, the rest will be fixed. Finally, the setting with the best average behaviour is chosen.The acceptance criterion adopts the simulated annealing criterion shown as Algorithm2, where f′S′ is the objective value of the new solution, fcurrentbestS is the objective value of the current solution, and fglobalbestS is the objective value of the global optimal solution. The probability that we accept new solution is ρ=e−f′S′−fcurrentbestS/T, where T=T0ε is the current temperature, ε is the cooling rate, and T0 is the initial temperature.Table 2
Parameters used inALNSip.
ParametersDefinitionValueUTotal iterations5000UpICycle500λ1A new global optimal solution17λ2A new and better than the current solution13λ3Accepted before and better than the current solution5λ4A worse solution4T0Initial temperature100εThe cooling rate0.99927γThe weight coefficient0.3ϕ1The Shaw coefficients3ϕ2The Shaw coefficients2ϕ3The Shaw coefficients2uDelete parameter0.15∼0.3


## 4.3. Removal Algorithms (RA)

In each iteration, a removal operator is selected from RA and removes the total number of passenger requestsnp=u⋅P in the solution to break the current solution, where u is the random removal parameter. These requests removed are added to the perturbation set RP. The section has designed five operators, the first three are chosen from Ropke and Pisinger [32], the fourth operator is adapted from Demir et al. [33], and the last one is motivated by Cordeau and Laporte [5].R1-Random Removal: the operator randomly removesnp requests from the current solution put them into the set P.R2-Worst-Removal: the operator calculates theΔfp value of all passengers, where Δfp denotes the change in objective value incurred by removing passenger request p from current position. Then, np requests with the greatest value Δfp are removed and put into the set RP.R3-Shaw Removal: to diversify the search, the operate measures the similarity levelRij between passenger i and passenger j through the correlation function Rij=ϕ1⋅dijp+dijd+ϕ2⋅tip−tjp+tid−tjd+ϕ3⋅lij, where ϕ1−ϕ3 are the Shaw coefficients, dijp is the distance between pickup locations of passengers i and j, dijd is the distance between delivery locations, tip is the boarding time, tid is the alighting time, lij indicates whether passengers i and j are in the same vehicle (lij=−1) or not (lij=1). The operator randomly chooses one customer and calculates all Rij between the passenger and other ones. Then, it removes np requests with the smallest similarity level.R4-Random Route Removal: This operator randomly removes all passenger requests of one route and puts them into the setRP.R5-Tabu Removal: the operator is spired by tabu search. It keeps a track of the times passengeri has been removed and then removes np requests with the smallest removed times and puts them to the set RP.


## 4.4. Insertion Algorithms (IA)

After a number of passenger requests are removed from the vehicle routing solution, insertion operators are used to repair and generate new solution. The first three operators are adapted from Ropke and Pisinger [32], the fourth one is motivated by Cordeau and Laporte [5], the fifth is inspired by Demir et al. [33], while the last two are the insertion operators designed for the problem with multiple pickup and delivery locations in the paper.I1-Greedy Insertion: the requests in the setRP are sequentially removed from RP set and inserted into the best location.I2-Regret-2-Insertion: to avoid the myopia of local optimization from greedy algorithm, the operator calculates the regret-k value, where k=2. And then it sequentially inserts the request with the greatest regret value.I3-Regret-3-Insertion: this operator is similar toI2 and makes k=3.I4-One by one Insertion: the operator is similar toI1. The difference is that I4 inserts one request into the best location after removing it, rather than reinserting one by one after removing all requests.I5-TimeWindows Insertion: to tackle with the impact of the time feature from the problem,I5 gets the similarity level of all removed passengers in terms of time window, that is, the value of time window difference, l0p−e0p+l1p−e1p. And then, it sequentially inserts the request with the greatest value.For the passenger with multiple locations, we need to combine one ofI1–I5 and one of the last two operators to complete the insertion of the passenger. For this, one of the following two operators is randomly selected:MI.1-Random insertion based on multiple locations:MI.1 principle randomly selects a candidate location as the current pickup or delivery location of the passenger and then inserts the passenger using I1–I5.MI.2-One-by-one insertion based on multiple locations:MI.2 principle compares the performance of all candidate locations using I1–I5 separately and selects the candidate location with the best performance as the current pickup or delivery location of the passenger and inserts it.


## 4.5. Time Slack Calculation Strategy

As seen in Figure2, if we break and repair the solution using RA and IA operators without adjusting timetables, it is possible to fail to search more feasible insertion solutions. Therefore, we design the instance to simulate the issue, where the maximum ride time of each passenger is 40 and the service time is 0. Time window, pickup, and delivery locations of two passengers are presented in Figure 2.Figure 2
The instance without time slack calculation strategy.If we just use Algorithm3 without any ways to adjust timetables, it can be found that the ride time of passenger 1 is more than 40 and passenger 2 cannot be inserted into the route as shown in Figure 2. After using Algorithm 4 to change the timetables, passenger 2 can be inserted in the position and the insertion solution is feasible, as shown in Figure 3. Therefore, it is very essential to adjust timetables to further improve the solution during the search. The time slack calculation strategy we proposed can test the feasibility of any insertion cases in time constraints. The symbols that may be used in Section 4.5 are shown in Table 3.Figure 3
The instance with time slack calculation strategy.Algorithm 3:Greedy time calculate strategy.
(1)
Input initial informationAT1=Eal1, DT1=AT1+ST and WT1=0;(2)
u⟵2;(3)
Whileu≤nATu=maxDTu−1+tu−1,u,Ealu;DTu=ATu+ST;WTu=min0,Ealu−ATu;u⟵u+1;(4)
EndTable 3
Notations and definitions of symbols used in Section4.5.
SymbolDefinitionMrdThe maximum ride time of one passengernThe total number of locations in the routeSTService timeATiArrival time of vehicle at locationiDTiDeparture time of vehicle at locationiWTiWaiting time of vehicle at locationiRDiActual ride time of passenger on the routeEali,LaTiTime window of passenger at locationiti,jThe travel time between locationi and location jTitwOne type of time slack based on time window of the passenger on locationiTirdOne type of time slack based on the maximum ride time of the passenger on locationiMTSiA maximum time slack of locationiMTSi′One time slack of locationiMTSi″One time slack of locationiAs shown in Figure2, the greedy algorithm just guarantees time window constraint but cannot consider the impact of the maximum ride time. In addition, it may also cause more waiting time.Titw is the adjustable time bus can delay its arrival at the location i according to the timetable and time window:(21)Titw=LaTi−ATi.Tird is the adjustable time bus can delay its arrival at the location i within the maximum ride time constraint:(22)Tird=Mrd−RDi.MTSi'′ means the adjustable time vehicle can delay its arrival at the location i, where its value may affect time constraints at other locations.(23)MTSi′′=minTitw,Tird.Note:(1)
If both boarding and alighting locations of one passenger are behind the locationu, MTSi'′ on pickup location or delivery location of the passenger is Titw(2)
If only delivery locationi of one passenger is behind the location u and Tird<0, MTSi'′ of the location i is TitwMTSi′ means the adjustable time of the vehicle at location i based on waiting time, where its value may affect time constraints of other locations.MTSi means the maximum adjustable time of the vehicle at the location i, where its value cannot affect time constraints at other locations.The relationship amongMTSi″, MTSi′, and MTSi and the entire process of time slack calculation strategy is shown as Algorithm 4.


## 4.6. Stopping Criteria

There are two types of stopping criteria used to avoid local optimization:(i)
When the current iteration exceeds the maximum iteration, the algorithm operation ends and the result is output(ii)
When the temperatureT=T0ε is less than 0.5, the algorithm operation ends and the result is output


## 5. Numerical Experiments

We first verify the accuracy of the above proposed MIP model by solving an instance with small-scale requests in the simplified Sioux waterfall network proposed by Tong et al. [3]. The experiments in the paper were performed on the Inter(R) Core(TM) i5-7300HQ CPU @ 2.50 GHz 8G RAM computer. The MIP model was solved by the commercial software GUROBI.


### 5.1. Small Numerical Experiments on a Simplified Sioux Waterfall Network

To verify the proposed model, we test and compare it with the proposed algorithm by one example with 20 passenger requests on the simplified Sioux Falls network proposed by Tong et al. [4]. Some nodes meaning candidate stop locations (denoted by the blue and green dots), other nodes (denoted by the white dots), and transportation links are shown in Figure 4(a). The number on links means travel time.Figure 4
The simplifying Sioux Waterfall Network. (a) The basic information of the road network and customers. (b) The final solution and commuting routes.
(a)(b)Two kinds of buses can be originally located at depot nodes, namely, nodes 1, 2, and 13 (denoted by the yellow dots), which have different load capacity, departure costs, and fuel costs. The maximum and minimum load capacity,Capku and Capkl, of one with large capacity is 10 and 7, and the other with small capacity is 6 and 3. The departure cost cdk of is, respectively, 22 and 17, and the fuel cost per unit time cfk is 1 and 0.7. The ticket price is set to 10, and the penalty cost for each unserved passenger is half of the ticket price in this example. Note that, in this case, we assume that the end depot of the customized bus is virtual depots, of which distance to any point is zero.Table4 lists related information of all passenger requests. Take passenger 1 as an example. Passenger 1 can be picked up at node 3 between time 11 and 15 and be delivered at node 7 between time 26 and 30. In addition, there are some passengers (passengers 4, 15, and 19) with more than one candidate pickup location in requests information. For passenger 4, he/she can select only one node as the final pickup location, namely, 4 or 5.Algorithm 4:Time slack calculation strategy to one route.
(1)
Calculate and remark arrival time, departure time, and waiting time of all locations on one route by Algorithm3;(2)
Begin with first location ofthe route and set u⟵1;(3)
Whileu<=nv⟵u.Whilev<=n(4)
Calculate Tvtw, Tvrd and MTSv'′ at the location v behind u;(5)
MTSv′=MTSv'′+∑w∈u+1,v+1WTw(6)
v⟵v+1(7)
End(8)
MTSu=minv∈u,nMTSv′ and obtain v^, v^ is the location where MTSv′ is the minimum value;(9)
ATu=ATu+MTSu(10)
Update arrival time, departure time, and waiting time of locations from the location u to n based on Algorithm 3;(11)
u⟵v^(12)
EndThe commercial software GUROBI andALNSip are used to solve this instance. Finally, the route is generated as shown in Figure 4(b).


#### 5.1.1. Optimal Solution for the Example

Computational results of the example are found using, respectively, the commercial software GUROBI and algorithmALNSip to assess their respective performance. The computational results show that the total income is 62.6. Four passengers cannot be served, namely, passengers 5, 6, 9, and 16. Other passengers are assigned to two buses. The computational result is the optimal solution (Gap value is 0), as shown in Table 5. Although the optimal solution from the solver and ALNSip are the same, shorter CPU time indicates the MIP solver has better performance in terms of the small-scale problems.Table 4
Passenger trip requests on the simplifying Sioux Waterfall Network.
Customers idCandidate pickup locationCandidate delivery locationPickup informationDelivery information1373:[11, 15]7:[26, 30]2383:[14, 18]8:[26, 30]3474:[15, 19]7:[26, 30]44, 584:[20, 24]; 5:[20, 24]8:[26, 30]55185:[15, 19]18:[26, 30]611811:[12, 16]8:[26, 30]712712:[7, 11]7:[26, 30]812812:[10, 14]8:[26, 30]912712:[37, 41]7:[56, 60]1020720:[50, 54]7:[56, 60]1120720:[50, 54]7:[56, 60]12201820:[52, 56]18:[56, 60]13201820:[52, 56]18:[56, 60]1421721:[44, 48]7:[56, 60]1521, 22721:[45, 49]; 22:[45, 49]7:[56, 60]1622822:[39, 43]8:[56, 60]1723723:[41, 45]7:[56, 60]18231823:[43, 47]18:[56, 60]1923, 24723:[41, 45]; 24:[41, 45]7:[56, 60]20241824:[43, 47]18:[56, 60]Table6 lists detailed vehicle routes and passenger assignments. Ten passengers are assigned to the bus with large capacity, and the rest six passengers to the bus with small one. Their routes are presented by red and orange lines in Figure 4(b).Table 5
Computational results of the example.
AlgorithmCarsProfitUnserved customerGap (%)CPU (s)MIP262.6[5, 6, 9, 16]0.011.94ALNSip262.6[5, 6, 9, 16]0.023.63


#### 5.1.2. Sensitive Analysis for Strategy 1

By the example on Sioux Waterfall Network, we further analyse the impact of Strategy 1 on the result. The computational results are shown in Table7.Table 6
Solution results of the example.
No.NumberTypeSolutionRouteRoute110LargeVO ⟶19⟶17⟶18⟶20⟶14⟶15⟶13⟶10⟶11⟶12⟶20⟶12⟶13⟶18⟶10⟶14⟶15⟶19⟶11⟶17⟶ VD13⟶23⟶23⟶23⟶24⟶21⟶21⟶20⟶20⟶20⟶20⟶18⟶18⟶18⟶18⟶7⟶7⟶7⟶7⟶7⟶726SmallVO ⟶7⟶8⟶2⟶1⟶3⟶4⟶4⟶2⟶8⟶7⟶3⟶1⟶ VD13⟶12⟶12⟶3⟶3⟶4⟶5⟶8⟶8⟶8⟶7⟶7⟶7Note that the number in Solution is customer’s id.As can be seen from Table7, the heterogeneous fleet achieves better profit in both experiments. Furthermore, the result shows that the heterogeneous fleet serves more passengers than homogeneous fleets in the second experiment. It means more passengers can be served by a flexible solution from heterogeneous fleets. Homogeneous fleets cannot make flexible dispatch based on various passenger requests, which may increase cost or make more passengers unserviceable.


### 5.2. Benchmark Test Results

#### 5.2.1. Benchmark Test with Unique Pickup or Delivery Locations

Because there is no benchmark instance applied to customized bus problem, we choose DARP benchmark instances proposed by Cordeau and Laporte [5] as test instances to evaluate the performance of the ALNSip proposed, which has similar properties as customized bus problems. Assuming all requests are serviced, the total distance is minimized as the objective function.Li et al. [35] tested, respectively, two solution evaluation approaches for ALNS (ALNSF is to allow only feasible solutions, ALNSI is to allow infeasible solutions) and found that although the results of ALNSI are better than ALNSF, ALNSI takes more time than ALNSF. Table 8 shows the calculation results of ALNSI, ALNSF, and ALNSip on DARP instances. The first column in Table 8 represents the instance number, and the Gap% refers to the percentage deviation of the ALNSI, ALNSF, and ALNSip compared to the best results from [5, 45]. We test the ALNSip on DARP benchmark instances and find it provides good results within 5000 iterations. The best result of ALNSip is selected based on 10 runs. All results are shown in Table 8 and compared with the best results of ALNSI, ALNSF from Li et al. [35].Table 7
Impact of various parameters.
ExperimentsVehicle typeCapacityDeparture costFuel costsCarsProfitUnservedNo. 1Heterogeneous vehicle(7, 10);22; 171.0;262.64(3, 6)0.7Homogeneous vehicle(6, 10)221.0251.04No. 2Heterogeneous vehicle(7, 10);22; 170.40;386.753(3, 6)0.25Homogeneous vehicle(6, 10)220.40278.04Table8 shows that compared to ALNSF, the proposed ALNSip can obtain better solutions in most instances where the results have on an average 84.16% decreased gap values with only 23.03% longer CPU time on average. In these instances, the ALNSip generally gives better results but consumes longer time than ALNSF. But the exception is that for instances R2a, R10a, R8b, R9b, and R10b, ALNSip searches better solutions but faster than ALNSF. Furthermore, ALNSip generally gives similar (for instances, R1a, R2a, R4a, R7a, and R7b) or even worse results but consumes less time than ALNSI in these instances. Table 8 shows that the proposed ALNSip searches solutions 60.71% higher gap values but 42.75% shorter CPU time on average than ALNSI. While the exception is that for instances R2a, R4a and R9a, ALNSip obtains better solutions than ALNSI within a shorter time. As a result, it turned out that ALNSip could get efficient and high-quality results in a reasonable time. In addition, ALNSip ensures the feasible solutions at each iteration. It is of great significance to solve the large-scale routing problems with multiple locations and time windows.


#### 5.2.2. Benchmark Test with Multiple Pickup or Delivery Locations

In the section, we improve DARP benchmark instances to further analyse the impact of Strategy 2 and test the performance of theALNSip in terms of multiple pickup or delivery locations problem. Some passengers are randomly appended pickup or delivery candidate locations, where new pickup or delivery locations are some locations closest to the passenger's original pickup or delivery location. Considering different scales, we choose R1a (small-scale problem), R2a (medium-scale problem), and R5a (large-scale problems) as tested instances to illustrate the following analysis.(i)
Analysis for Strategy 2: Table9 compares the impacts of Strategy 2 or not. It can be seen that, compared with the strategy that does not consider multiple candidate locations, Strategy 2 provides more flexible and higher solution quality for the final solution. The results also show that compared with classic ALNS, ALNSip can effectively solve the problem with multiple candidate locations in a reasonable time.(ii)
Analysis for the number of candidate locations: to perform a sensitive analysis of the number of candidate locations, we test it from two perspectives, that is, the number of candidate locations of each passenger (2, 3, or 4 candidate locations) and the total number of people chosen to append candidate locations (5%, 10%, and 20% of passengers randomly). Overall,Strategy 2 with more than one location gives more applicable solutions than cases without multiple locations in terms of two perspectives. Table 10 shows that with the increase of candidate locations, it can obtain the better solution in small-scale problems. But for larger-scale instances, the results in Table 10 may be worse if one passenger has more candidate locations. Possibly, the reason is that multiple candidate locations cause more feasible solutions during the search, which expands the search area and need more iterations and time to search optimized solutions. Therefore, given that passengers generally do not have too many candidate locations near their destination in practice, 2 or 3 candidate locations are more appropriate in practical issues.Table 8
Compared results ofALNSip on the benchmark DARP instances.
InstanceRequestsBest profitGap (%)CPU (min)ALNSipALNSIALNSFALNSIALNSFGap (%)CPU (min)R1a24190.02−1.151.351.630.490.001.67R2a48301.3360.559.599.1212.110.328.01R3a72531.9962.0118.1417.6712.110.7420.40R4a96570.2464.9525.2156.1418.074.7339.97R5a120628.1145.3826.7965.4637.377.3049.11R6a144794.0630.9229.53153.5749.845.2768.94R7a36291.710.006.054.011.120.002.64R8a72487.8431.4521.2744.3220.933.4722.40R9a108658.3123.6657.32148.4139.782.3442.79R10a144857.1092.5329.62242.52128.307.0172.30R1b24164.46−0.052.703.590.413.603.74R2b48295.6640.1815.0512.353.761.0615.41R3b72486.5692.1924.2129.9428.884.5632.04R4b96530.6974.1029.6648.7623.856.4162.58R5b120578.6073.1133.12124.1233.556.1194.23R6b144740.3543.4941.94145.3348.906.17109.70R7b36248.210.018.633.654.430.005.28R8b72461.3893.6810.9531.4951.792.1141.42R9b108597.7463.2825.40134.2775.874.5172.57R10b144795.1574.4838.08242.64115.176.28104.47Average——2.2422.7375.9535.343.6043.48Table 9
Results of Strategy 2 or not.
InstanceRequestsWithout strategy 2With strategy 2CPU (min)R1a24190.02183.051.71R2a48302.31298.758.14R5a120673.95664.8050.17


#### 5.2.3. Comparison of Heuristic Algorithms

To evaluate the effectiveness of theALNSip in searching the problem with multiple candidate locations, we compare and analyse its performance with other heuristic algorithms, namely, Genetic Algorithm (GA) [46], Particle Swarm Optimization (PSO) [47], and Artificial Bee Colony Algorithm (ABC) [48]. We randomly choose 10% customers with 2 candidate locations based on the benchmark instances R1b∼R3b. These heuristic algorithms continuously find feasible solutions and use the data preprocessing techniques [49] to avoid infeasible results. For multiple candidate locations, one location from multiple candidate locations will be chosen during the iteration. The parameter settings are set as follows: the number of populations Psize = 20 and the number of generations Gmax = 5000, and crossover ratio of GA PcGA = 0.8, crossover ratio of PSO PcPSO = 0.6, and mutation ratio Pm = 0.2. The comparisons of four heuristic algorithms’ performances, including mean value and the best value, are shown in Table 11.Table 10
Influence of the number of candidate locations.
(%)InstanceBest profit without strategy2 candidate locations3 candidate locations4 candidate locations5R1a190.02183.96183.96183.95R2a302.31300.94297.80296.79R5a673.95668.26667.06657.1510R1a190.02183.05183.03182.81R2a302.31298.75297.28292.10R5a673.95664.80666.23667.6320R1a190.02178.70177.86174.40R2a302.31296.38285.02286.45R5a673.95667.28644.85651.82Table11 shows the best value and mean value computed by each algorithm for each instance. The results of the four algorithms show a significant difference. We can observe in comparison with other heuristic algorithms the results obtained ALNSip are optimal in terms of the best value and mean value. And with an increase in the number of customers, the ability to find the best optimization solution is higher. In addition, the convergence plot (Figure 5) shows us the convergence of the different algorithms. On observing the plot of them, we can see that ALNSip performs better than other algorithms in convergence and has a strong ability to jump out of the local optimum to avoid premature convergence. As a result, ALNSip can obtain better optimization solutions and effectively search the solution space in terms of solution quality and stability.Figure 5
Convergence graph obtained forALNSip, GA, PSO, and ABC algorithms. (a) R1b. (b) R2b. (c) R3b.
(a)(b)(c)


### 5.3. Customized Buses Instances

In order to test the performance ofALNSip in solving practical problems with large scale, we are inspired by Tong et al. [4] and consider the real commuting issue in Beijing. Finally, we design three customized bus service instances containing small-scale problems and large-scale problems, where commuters leave for their workplaces from their houses and two main business areas, namely, Jingrongjie (destination 1) and Guomao (destination 2), as shown in Figure 6.Figure 6
The distribution of candidate locations. Red and green, respectively, represent the pickup and delivery locations of passengers. (a) Destination: Jinrongjie and (b) Destinantion: Guomao.
(a)(b)The maximum and minimum load capacity,Capku and Capkl, of one with large capacity is 16 and 10, and the other with small capacity range is 9 and 6. We obtain the passengers' preferred time windows with the information processing proposed by Tong et al. [4]. The fixed cost of bus dispatched with large capacity is 30, 25 for the small one. The fuel cost per unit time is 0.4 for those buses with large capacity and 0.25 for the small. The maximum route duration of buses is determined according to the shortest path of the home-to-work. If it is more than 60 minutes, the ticket will be set to 14, and the penalty cost of unserved passengers is 7. If it is less than or equal to 60 minutes, the ticket is set to 10, and the penalty cost is 5. With respect to their proximity in time and space, the requests are divided into 3 groups, and the results of the actual case are finally obtained as follows.Tables12 and 13 show the passengers’ information and routing time between some locations (measured by map software) of Group 1. Similarly, Tables 14 and 15 are for Group 2, and Tables 16 and 17 are for Group 3.Table 11
Comparison ofALNSip with the GA-SA, PSO, and ABC on the benchmark instances.
NoGAPSOABCALNSipMeanBestMeanBestMeanBestMeanBestR1b185.9181.7183.3174.9190.7184.6163.8160.4R2b370.9350.7343.9340.1341.9337.3304.7300.9R3b664.6638.8611.6580.8627.1600.4505.3502.2Table 12
Passenger demands information of Group 1.
Passenger idPick up location with candidate locationDelivery locatione0pl0pe1pl1p11090104760213901047603201001545604209010455552410012476063010515476073095154555830104165060940910204555104010720475711401082050601250101020506013501082047581460101020505815609820475516609102045551770102032476018701020304560198792233476020801025335060Table 13
The routing time between locations of Group 1.
min1234567891011121310840280630346074043705754507677067605850253092504102950110012001300Table 14
Passenger demands information of Group 2.
Passenger idPick up location with candidate locationDelivery locatione0pl0pe1pl1p110110570752189054555310110555604101005657052095104555620115105560720105105560823115105560930971560651030117157075113810715657012301171570751340111015707514439121560651540111015707516431110157075175091520606518501115207075196010101555602065111015556021601110155560226091015455523659101545552460111015556025701012205560267011102055602770101215556028701112205560298010210657030811121070753180921060653280112107075Table 15
The routing time between locations of Group 2.
min12345678910111210540250435525534054343504454044468450274203752843095244370710703115552301200Table 16
Passenger demands information of Group 3.
Passenger idPick up location with candidate locationDelivery locatione0pl0pe1pl1p11014010455521516010455031014515455541815515455552014010455562015010455572014515455582015515405092016010405010301401040501130145154055123016515405013301651540501440140104555154614015455516401472045551750145204555185614517455519501652040502050167204550216015515455522601471745552360165154050246016215405025701651540502675145154555277015515455528712142174555298016010405030801451545553180145204555329015102045553391215520455534901452045553590167204050361001410204555371001472045553810147204555391514102040504010161225405041181412254555422016122540504320145204555442016102040504520141020455546201610204050473015152545554830141020455549301412254555Given the data information in Tables12-15, the results using MIP solver and ALNSip are shown in Table 18.Table 17
The routing time between locations of Group 3.
min12345678910111213141516171819105340250550304204404730530362a24732033845049540410443033117302712330313430281403153071630272870170018001900We set 1000s as the termination condition of the MIP solver. In the first two cases, GROUBI returns feasible solutions with 2.33% and 0% of gap value in the allowed time. In the last large-scale case, there are no feasible solutions in the allowed time for MIP solver. But forALNSip, as shown in Table 18, it can efficiently solve routing problems with different scales. Multiple experiments in Sections 5.2 and 5.3 also demonstrate that it is effective for the proposed ALNSip to solve practice problems with large scale. Additionally, to further verify the effectiveness and advancement of heterogeneous customized bus service with multiple candidate locations, we compare the performance among the two strategies, the homogeneous fleet, as well as the result without candidate locations in Table 19. It can be compared with other cases that the heterogeneous fleets and candidate locations strengthen the cooperation among vehicles and flexibility of routes planning. Therefore, both strategies provide the highest profits (relative increase of 12.3%, 6.2%, and 13.7% in total profits, respectively), no unserved requests, and fewer vehicles to reduce lane occupation. It is of great practical significance for increasing operators’ profit and improving service quality.Table 18
Results for 3 Group instances.
Group No.Number of requestsALNSipMIP solverGap (%)Number of served requestsNumber of unserved requestsBig carsSmall cars120111.25111.252.3320011232336.4336.40.0032020349291.75——49014Total101739.4——101045Table 19
Results comparison in different cases.
Group No.Without candidate locationsHomogeneous fleet with big capacityHomogeneous fleet with small capacityHeterogeneous fleets and candidate locationsProfitsNUNCProfitsNUNCProfitsNUNCProfitsNUNC1111.250298.00294.7522111.25022269.923336.402287.7504336.4023277.315261.453268.006291.7505Total658.45310695.857650.5212739.409NU: number of unserved requests; NC: number of customized buses.


### 5.4. Implications

The customized bus service based on heterogeneous fleets and multiple candidate locations provides a good organizational form and service framework. The proposed mathematical model and algorithm also verify its effectiveness and offer a theoretical basis for further research and implications in practice. The bus operators can improve fleets management and route planning by introducing the new mechanism and strategy. The detailed managerial implications of the proposed methodology can be summarized as follows:(1)
The design of heterogeneous fleets can make customized bus companies construct the fleets more flexibly, save costs, and increase the occupancy rate. Heterogeneous fleets have different load capacities and different transportation costs. The selection of customized buses with different capacities improves scheduling and collaboration among buses and enhances the operational efficiency of bus system. Therefore, effective collaboration among heterogeneous vehicles can contribute to avoiding empty seats and increasing operator profitability.(2)
More candidate locations chosen by passengers in the platform make a breakthrough in the limitations of a single candidate location. From the passengers’ perspective, it increases the probability for the passengers to be served. From the operators’ perspective, it means more flexible route planning. Consequently, multiple candidate locations can be utilized to optimize pickup and delivery routes and serve as many passengers as possible to improve service quality.


## 5.1. Small Numerical Experiments on a Simplified Sioux Waterfall Network

To verify the proposed model, we test and compare it with the proposed algorithm by one example with 20 passenger requests on the simplified Sioux Falls network proposed by Tong et al. [4]. Some nodes meaning candidate stop locations (denoted by the blue and green dots), other nodes (denoted by the white dots), and transportation links are shown in Figure 4(a). The number on links means travel time.Figure 4
The simplifying Sioux Waterfall Network. (a) The basic information of the road network and customers. (b) The final solution and commuting routes.
(a)(b)Two kinds of buses can be originally located at depot nodes, namely, nodes 1, 2, and 13 (denoted by the yellow dots), which have different load capacity, departure costs, and fuel costs. The maximum and minimum load capacity,Capku and Capkl, of one with large capacity is 10 and 7, and the other with small capacity is 6 and 3. The departure cost cdk of is, respectively, 22 and 17, and the fuel cost per unit time cfk is 1 and 0.7. The ticket price is set to 10, and the penalty cost for each unserved passenger is half of the ticket price in this example. Note that, in this case, we assume that the end depot of the customized bus is virtual depots, of which distance to any point is zero.Table4 lists related information of all passenger requests. Take passenger 1 as an example. Passenger 1 can be picked up at node 3 between time 11 and 15 and be delivered at node 7 between time 26 and 30. In addition, there are some passengers (passengers 4, 15, and 19) with more than one candidate pickup location in requests information. For passenger 4, he/she can select only one node as the final pickup location, namely, 4 or 5.Algorithm 4:Time slack calculation strategy to one route.
(1)
Calculate and remark arrival time, departure time, and waiting time of all locations on one route by Algorithm3;(2)
Begin with first location ofthe route and set u⟵1;(3)
Whileu<=nv⟵u.Whilev<=n(4)
Calculate Tvtw, Tvrd and MTSv'′ at the location v behind u;(5)
MTSv′=MTSv'′+∑w∈u+1,v+1WTw(6)
v⟵v+1(7)
End(8)
MTSu=minv∈u,nMTSv′ and obtain v^, v^ is the location where MTSv′ is the minimum value;(9)
ATu=ATu+MTSu(10)
Update arrival time, departure time, and waiting time of locations from the location u to n based on Algorithm 3;(11)
u⟵v^(12)
EndThe commercial software GUROBI andALNSip are used to solve this instance. Finally, the route is generated as shown in Figure 4(b).


### 5.1.1. Optimal Solution for the Example

Computational results of the example are found using, respectively, the commercial software GUROBI and algorithmALNSip to assess their respective performance. The computational results show that the total income is 62.6. Four passengers cannot be served, namely, passengers 5, 6, 9, and 16. Other passengers are assigned to two buses. The computational result is the optimal solution (Gap value is 0), as shown in Table 5. Although the optimal solution from the solver and ALNSip are the same, shorter CPU time indicates the MIP solver has better performance in terms of the small-scale problems.Table 4
Passenger trip requests on the simplifying Sioux Waterfall Network.
Customers idCandidate pickup locationCandidate delivery locationPickup informationDelivery information1373:[11, 15]7:[26, 30]2383:[14, 18]8:[26, 30]3474:[15, 19]7:[26, 30]44, 584:[20, 24]; 5:[20, 24]8:[26, 30]55185:[15, 19]18:[26, 30]611811:[12, 16]8:[26, 30]712712:[7, 11]7:[26, 30]812812:[10, 14]8:[26, 30]912712:[37, 41]7:[56, 60]1020720:[50, 54]7:[56, 60]1120720:[50, 54]7:[56, 60]12201820:[52, 56]18:[56, 60]13201820:[52, 56]18:[56, 60]1421721:[44, 48]7:[56, 60]1521, 22721:[45, 49]; 22:[45, 49]7:[56, 60]1622822:[39, 43]8:[56, 60]1723723:[41, 45]7:[56, 60]18231823:[43, 47]18:[56, 60]1923, 24723:[41, 45]; 24:[41, 45]7:[56, 60]20241824:[43, 47]18:[56, 60]Table6 lists detailed vehicle routes and passenger assignments. Ten passengers are assigned to the bus with large capacity, and the rest six passengers to the bus with small one. Their routes are presented by red and orange lines in Figure 4(b).Table 5
Computational results of the example.
AlgorithmCarsProfitUnserved customerGap (%)CPU (s)MIP262.6[5, 6, 9, 16]0.011.94ALNSip262.6[5, 6, 9, 16]0.023.63


### 5.1.2. Sensitive Analysis for Strategy 1

By the example on Sioux Waterfall Network, we further analyse the impact of Strategy 1 on the result. The computational results are shown in Table7.Table 6
Solution results of the example.
No.NumberTypeSolutionRouteRoute110LargeVO ⟶19⟶17⟶18⟶20⟶14⟶15⟶13⟶10⟶11⟶12⟶20⟶12⟶13⟶18⟶10⟶14⟶15⟶19⟶11⟶17⟶ VD13⟶23⟶23⟶23⟶24⟶21⟶21⟶20⟶20⟶20⟶20⟶18⟶18⟶18⟶18⟶7⟶7⟶7⟶7⟶7⟶726SmallVO ⟶7⟶8⟶2⟶1⟶3⟶4⟶4⟶2⟶8⟶7⟶3⟶1⟶ VD13⟶12⟶12⟶3⟶3⟶4⟶5⟶8⟶8⟶8⟶7⟶7⟶7Note that the number in Solution is customer’s id.As can be seen from Table7, the heterogeneous fleet achieves better profit in both experiments. Furthermore, the result shows that the heterogeneous fleet serves more passengers than homogeneous fleets in the second experiment. It means more passengers can be served by a flexible solution from heterogeneous fleets. Homogeneous fleets cannot make flexible dispatch based on various passenger requests, which may increase cost or make more passengers unserviceable.


## 5.1.1. Optimal Solution for the Example

Computational results of the example are found using, respectively, the commercial software GUROBI and algorithmALNSip to assess their respective performance. The computational results show that the total income is 62.6. Four passengers cannot be served, namely, passengers 5, 6, 9, and 16. Other passengers are assigned to two buses. The computational result is the optimal solution (Gap value is 0), as shown in Table 5. Although the optimal solution from the solver and ALNSip are the same, shorter CPU time indicates the MIP solver has better performance in terms of the small-scale problems.Table 4
Passenger trip requests on the simplifying Sioux Waterfall Network.
Customers idCandidate pickup locationCandidate delivery locationPickup informationDelivery information1373:[11, 15]7:[26, 30]2383:[14, 18]8:[26, 30]3474:[15, 19]7:[26, 30]44, 584:[20, 24]; 5:[20, 24]8:[26, 30]55185:[15, 19]18:[26, 30]611811:[12, 16]8:[26, 30]712712:[7, 11]7:[26, 30]812812:[10, 14]8:[26, 30]912712:[37, 41]7:[56, 60]1020720:[50, 54]7:[56, 60]1120720:[50, 54]7:[56, 60]12201820:[52, 56]18:[56, 60]13201820:[52, 56]18:[56, 60]1421721:[44, 48]7:[56, 60]1521, 22721:[45, 49]; 22:[45, 49]7:[56, 60]1622822:[39, 43]8:[56, 60]1723723:[41, 45]7:[56, 60]18231823:[43, 47]18:[56, 60]1923, 24723:[41, 45]; 24:[41, 45]7:[56, 60]20241824:[43, 47]18:[56, 60]Table6 lists detailed vehicle routes and passenger assignments. Ten passengers are assigned to the bus with large capacity, and the rest six passengers to the bus with small one. Their routes are presented by red and orange lines in Figure 4(b).Table 5
Computational results of the example.
AlgorithmCarsProfitUnserved customerGap (%)CPU (s)MIP262.6[5, 6, 9, 16]0.011.94ALNSip262.6[5, 6, 9, 16]0.023.63


## 5.1.2. Sensitive Analysis for Strategy 1

By the example on Sioux Waterfall Network, we further analyse the impact of Strategy 1 on the result. The computational results are shown in Table7.Table 6
Solution results of the example.
No.NumberTypeSolutionRouteRoute110LargeVO ⟶19⟶17⟶18⟶20⟶14⟶15⟶13⟶10⟶11⟶12⟶20⟶12⟶13⟶18⟶10⟶14⟶15⟶19⟶11⟶17⟶ VD13⟶23⟶23⟶23⟶24⟶21⟶21⟶20⟶20⟶20⟶20⟶18⟶18⟶18⟶18⟶7⟶7⟶7⟶7⟶7⟶726SmallVO ⟶7⟶8⟶2⟶1⟶3⟶4⟶4⟶2⟶8⟶7⟶3⟶1⟶ VD13⟶12⟶12⟶3⟶3⟶4⟶5⟶8⟶8⟶8⟶7⟶7⟶7Note that the number in Solution is customer’s id.As can be seen from Table7, the heterogeneous fleet achieves better profit in both experiments. Furthermore, the result shows that the heterogeneous fleet serves more passengers than homogeneous fleets in the second experiment. It means more passengers can be served by a flexible solution from heterogeneous fleets. Homogeneous fleets cannot make flexible dispatch based on various passenger requests, which may increase cost or make more passengers unserviceable.


## 5.2. Benchmark Test Results

### 5.2.1. Benchmark Test with Unique Pickup or Delivery Locations

Because there is no benchmark instance applied to customized bus problem, we choose DARP benchmark instances proposed by Cordeau and Laporte [5] as test instances to evaluate the performance of the ALNSip proposed, which has similar properties as customized bus problems. Assuming all requests are serviced, the total distance is minimized as the objective function.Li et al. [35] tested, respectively, two solution evaluation approaches for ALNS (ALNSF is to allow only feasible solutions, ALNSI is to allow infeasible solutions) and found that although the results of ALNSI are better than ALNSF, ALNSI takes more time than ALNSF. Table 8 shows the calculation results of ALNSI, ALNSF, and ALNSip on DARP instances. The first column in Table 8 represents the instance number, and the Gap% refers to the percentage deviation of the ALNSI, ALNSF, and ALNSip compared to the best results from [5, 45]. We test the ALNSip on DARP benchmark instances and find it provides good results within 5000 iterations. The best result of ALNSip is selected based on 10 runs. All results are shown in Table 8 and compared with the best results of ALNSI, ALNSF from Li et al. [35].Table 7
Impact of various parameters.
ExperimentsVehicle typeCapacityDeparture costFuel costsCarsProfitUnservedNo. 1Heterogeneous vehicle(7, 10);22; 171.0;262.64(3, 6)0.7Homogeneous vehicle(6, 10)221.0251.04No. 2Heterogeneous vehicle(7, 10);22; 170.40;386.753(3, 6)0.25Homogeneous vehicle(6, 10)220.40278.04Table8 shows that compared to ALNSF, the proposed ALNSip can obtain better solutions in most instances where the results have on an average 84.16% decreased gap values with only 23.03% longer CPU time on average. In these instances, the ALNSip generally gives better results but consumes longer time than ALNSF. But the exception is that for instances R2a, R10a, R8b, R9b, and R10b, ALNSip searches better solutions but faster than ALNSF. Furthermore, ALNSip generally gives similar (for instances, R1a, R2a, R4a, R7a, and R7b) or even worse results but consumes less time than ALNSI in these instances. Table 8 shows that the proposed ALNSip searches solutions 60.71% higher gap values but 42.75% shorter CPU time on average than ALNSI. While the exception is that for instances R2a, R4a and R9a, ALNSip obtains better solutions than ALNSI within a shorter time. As a result, it turned out that ALNSip could get efficient and high-quality results in a reasonable time. In addition, ALNSip ensures the feasible solutions at each iteration. It is of great significance to solve the large-scale routing problems with multiple locations and time windows.


### 5.2.2. Benchmark Test with Multiple Pickup or Delivery Locations

In the section, we improve DARP benchmark instances to further analyse the impact of Strategy 2 and test the performance of theALNSip in terms of multiple pickup or delivery locations problem. Some passengers are randomly appended pickup or delivery candidate locations, where new pickup or delivery locations are some locations closest to the passenger's original pickup or delivery location. Considering different scales, we choose R1a (small-scale problem), R2a (medium-scale problem), and R5a (large-scale problems) as tested instances to illustrate the following analysis.(i)
Analysis for Strategy 2: Table9 compares the impacts of Strategy 2 or not. It can be seen that, compared with the strategy that does not consider multiple candidate locations, Strategy 2 provides more flexible and higher solution quality for the final solution. The results also show that compared with classic ALNS, ALNSip can effectively solve the problem with multiple candidate locations in a reasonable time.(ii)
Analysis for the number of candidate locations: to perform a sensitive analysis of the number of candidate locations, we test it from two perspectives, that is, the number of candidate locations of each passenger (2, 3, or 4 candidate locations) and the total number of people chosen to append candidate locations (5%, 10%, and 20% of passengers randomly). Overall,Strategy 2 with more than one location gives more applicable solutions than cases without multiple locations in terms of two perspectives. Table 10 shows that with the increase of candidate locations, it can obtain the better solution in small-scale problems. But for larger-scale instances, the results in Table 10 may be worse if one passenger has more candidate locations. Possibly, the reason is that multiple candidate locations cause more feasible solutions during the search, which expands the search area and need more iterations and time to search optimized solutions. Therefore, given that passengers generally do not have too many candidate locations near their destination in practice, 2 or 3 candidate locations are more appropriate in practical issues.Table 8
Compared results ofALNSip on the benchmark DARP instances.
InstanceRequestsBest profitGap (%)CPU (min)ALNSipALNSIALNSFALNSIALNSFGap (%)CPU (min)R1a24190.02−1.151.351.630.490.001.67R2a48301.3360.559.599.1212.110.328.01R3a72531.9962.0118.1417.6712.110.7420.40R4a96570.2464.9525.2156.1418.074.7339.97R5a120628.1145.3826.7965.4637.377.3049.11R6a144794.0630.9229.53153.5749.845.2768.94R7a36291.710.006.054.011.120.002.64R8a72487.8431.4521.2744.3220.933.4722.40R9a108658.3123.6657.32148.4139.782.3442.79R10a144857.1092.5329.62242.52128.307.0172.30R1b24164.46−0.052.703.590.413.603.74R2b48295.6640.1815.0512.353.761.0615.41R3b72486.5692.1924.2129.9428.884.5632.04R4b96530.6974.1029.6648.7623.856.4162.58R5b120578.6073.1133.12124.1233.556.1194.23R6b144740.3543.4941.94145.3348.906.17109.70R7b36248.210.018.633.654.430.005.28R8b72461.3893.6810.9531.4951.792.1141.42R9b108597.7463.2825.40134.2775.874.5172.57R10b144795.1574.4838.08242.64115.176.28104.47Average——2.2422.7375.9535.343.6043.48Table 9
Results of Strategy 2 or not.
InstanceRequestsWithout strategy 2With strategy 2CPU (min)R1a24190.02183.051.71R2a48302.31298.758.14R5a120673.95664.8050.17


### 5.2.3. Comparison of Heuristic Algorithms

To evaluate the effectiveness of theALNSip in searching the problem with multiple candidate locations, we compare and analyse its performance with other heuristic algorithms, namely, Genetic Algorithm (GA) [46], Particle Swarm Optimization (PSO) [47], and Artificial Bee Colony Algorithm (ABC) [48]. We randomly choose 10% customers with 2 candidate locations based on the benchmark instances R1b∼R3b. These heuristic algorithms continuously find feasible solutions and use the data preprocessing techniques [49] to avoid infeasible results. For multiple candidate locations, one location from multiple candidate locations will be chosen during the iteration. The parameter settings are set as follows: the number of populations Psize = 20 and the number of generations Gmax = 5000, and crossover ratio of GA PcGA = 0.8, crossover ratio of PSO PcPSO = 0.6, and mutation ratio Pm = 0.2. The comparisons of four heuristic algorithms’ performances, including mean value and the best value, are shown in Table 11.Table 10
Influence of the number of candidate locations.
(%)InstanceBest profit without strategy2 candidate locations3 candidate locations4 candidate locations5R1a190.02183.96183.96183.95R2a302.31300.94297.80296.79R5a673.95668.26667.06657.1510R1a190.02183.05183.03182.81R2a302.31298.75297.28292.10R5a673.95664.80666.23667.6320R1a190.02178.70177.86174.40R2a302.31296.38285.02286.45R5a673.95667.28644.85651.82Table11 shows the best value and mean value computed by each algorithm for each instance. The results of the four algorithms show a significant difference. We can observe in comparison with other heuristic algorithms the results obtained ALNSip are optimal in terms of the best value and mean value. And with an increase in the number of customers, the ability to find the best optimization solution is higher. In addition, the convergence plot (Figure 5) shows us the convergence of the different algorithms. On observing the plot of them, we can see that ALNSip performs better than other algorithms in convergence and has a strong ability to jump out of the local optimum to avoid premature convergence. As a result, ALNSip can obtain better optimization solutions and effectively search the solution space in terms of solution quality and stability.Figure 5
Convergence graph obtained forALNSip, GA, PSO, and ABC algorithms. (a) R1b. (b) R2b. (c) R3b.
(a)(b)(c)


## 5.2.1. Benchmark Test with Unique Pickup or Delivery Locations

Because there is no benchmark instance applied to customized bus problem, we choose DARP benchmark instances proposed by Cordeau and Laporte [5] as test instances to evaluate the performance of the ALNSip proposed, which has similar properties as customized bus problems. Assuming all requests are serviced, the total distance is minimized as the objective function.Li et al. [35] tested, respectively, two solution evaluation approaches for ALNS (ALNSF is to allow only feasible solutions, ALNSI is to allow infeasible solutions) and found that although the results of ALNSI are better than ALNSF, ALNSI takes more time than ALNSF. Table 8 shows the calculation results of ALNSI, ALNSF, and ALNSip on DARP instances. The first column in Table 8 represents the instance number, and the Gap% refers to the percentage deviation of the ALNSI, ALNSF, and ALNSip compared to the best results from [5, 45]. We test the ALNSip on DARP benchmark instances and find it provides good results within 5000 iterations. The best result of ALNSip is selected based on 10 runs. All results are shown in Table 8 and compared with the best results of ALNSI, ALNSF from Li et al. [35].Table 7
Impact of various parameters.
ExperimentsVehicle typeCapacityDeparture costFuel costsCarsProfitUnservedNo. 1Heterogeneous vehicle(7, 10);22; 171.0;262.64(3, 6)0.7Homogeneous vehicle(6, 10)221.0251.04No. 2Heterogeneous vehicle(7, 10);22; 170.40;386.753(3, 6)0.25Homogeneous vehicle(6, 10)220.40278.04Table8 shows that compared to ALNSF, the proposed ALNSip can obtain better solutions in most instances where the results have on an average 84.16% decreased gap values with only 23.03% longer CPU time on average. In these instances, the ALNSip generally gives better results but consumes longer time than ALNSF. But the exception is that for instances R2a, R10a, R8b, R9b, and R10b, ALNSip searches better solutions but faster than ALNSF. Furthermore, ALNSip generally gives similar (for instances, R1a, R2a, R4a, R7a, and R7b) or even worse results but consumes less time than ALNSI in these instances. Table 8 shows that the proposed ALNSip searches solutions 60.71% higher gap values but 42.75% shorter CPU time on average than ALNSI. While the exception is that for instances R2a, R4a and R9a, ALNSip obtains better solutions than ALNSI within a shorter time. As a result, it turned out that ALNSip could get efficient and high-quality results in a reasonable time. In addition, ALNSip ensures the feasible solutions at each iteration. It is of great significance to solve the large-scale routing problems with multiple locations and time windows.


## 5.2.2. Benchmark Test with Multiple Pickup or Delivery Locations

In the section, we improve DARP benchmark instances to further analyse the impact of Strategy 2 and test the performance of theALNSip in terms of multiple pickup or delivery locations problem. Some passengers are randomly appended pickup or delivery candidate locations, where new pickup or delivery locations are some locations closest to the passenger's original pickup or delivery location. Considering different scales, we choose R1a (small-scale problem), R2a (medium-scale problem), and R5a (large-scale problems) as tested instances to illustrate the following analysis.(i)
Analysis for Strategy 2: Table9 compares the impacts of Strategy 2 or not. It can be seen that, compared with the strategy that does not consider multiple candidate locations, Strategy 2 provides more flexible and higher solution quality for the final solution. The results also show that compared with classic ALNS, ALNSip can effectively solve the problem with multiple candidate locations in a reasonable time.(ii)
Analysis for the number of candidate locations: to perform a sensitive analysis of the number of candidate locations, we test it from two perspectives, that is, the number of candidate locations of each passenger (2, 3, or 4 candidate locations) and the total number of people chosen to append candidate locations (5%, 10%, and 20% of passengers randomly). Overall,Strategy 2 with more than one location gives more applicable solutions than cases without multiple locations in terms of two perspectives. Table 10 shows that with the increase of candidate locations, it can obtain the better solution in small-scale problems. But for larger-scale instances, the results in Table 10 may be worse if one passenger has more candidate locations. Possibly, the reason is that multiple candidate locations cause more feasible solutions during the search, which expands the search area and need more iterations and time to search optimized solutions. Therefore, given that passengers generally do not have too many candidate locations near their destination in practice, 2 or 3 candidate locations are more appropriate in practical issues.Table 8
Compared results ofALNSip on the benchmark DARP instances.
InstanceRequestsBest profitGap (%)CPU (min)ALNSipALNSIALNSFALNSIALNSFGap (%)CPU (min)R1a24190.02−1.151.351.630.490.001.67R2a48301.3360.559.599.1212.110.328.01R3a72531.9962.0118.1417.6712.110.7420.40R4a96570.2464.9525.2156.1418.074.7339.97R5a120628.1145.3826.7965.4637.377.3049.11R6a144794.0630.9229.53153.5749.845.2768.94R7a36291.710.006.054.011.120.002.64R8a72487.8431.4521.2744.3220.933.4722.40R9a108658.3123.6657.32148.4139.782.3442.79R10a144857.1092.5329.62242.52128.307.0172.30R1b24164.46−0.052.703.590.413.603.74R2b48295.6640.1815.0512.353.761.0615.41R3b72486.5692.1924.2129.9428.884.5632.04R4b96530.6974.1029.6648.7623.856.4162.58R5b120578.6073.1133.12124.1233.556.1194.23R6b144740.3543.4941.94145.3348.906.17109.70R7b36248.210.018.633.654.430.005.28R8b72461.3893.6810.9531.4951.792.1141.42R9b108597.7463.2825.40134.2775.874.5172.57R10b144795.1574.4838.08242.64115.176.28104.47Average——2.2422.7375.9535.343.6043.48Table 9
Results of Strategy 2 or not.
InstanceRequestsWithout strategy 2With strategy 2CPU (min)R1a24190.02183.051.71R2a48302.31298.758.14R5a120673.95664.8050.17


## 5.2.3. Comparison of Heuristic Algorithms

To evaluate the effectiveness of theALNSip in searching the problem with multiple candidate locations, we compare and analyse its performance with other heuristic algorithms, namely, Genetic Algorithm (GA) [46], Particle Swarm Optimization (PSO) [47], and Artificial Bee Colony Algorithm (ABC) [48]. We randomly choose 10% customers with 2 candidate locations based on the benchmark instances R1b∼R3b. These heuristic algorithms continuously find feasible solutions and use the data preprocessing techniques [49] to avoid infeasible results. For multiple candidate locations, one location from multiple candidate locations will be chosen during the iteration. The parameter settings are set as follows: the number of populations Psize = 20 and the number of generations Gmax = 5000, and crossover ratio of GA PcGA = 0.8, crossover ratio of PSO PcPSO = 0.6, and mutation ratio Pm = 0.2. The comparisons of four heuristic algorithms’ performances, including mean value and the best value, are shown in Table 11.Table 10
Influence of the number of candidate locations.
(%)InstanceBest profit without strategy2 candidate locations3 candidate locations4 candidate locations5R1a190.02183.96183.96183.95R2a302.31300.94297.80296.79R5a673.95668.26667.06657.1510R1a190.02183.05183.03182.81R2a302.31298.75297.28292.10R5a673.95664.80666.23667.6320R1a190.02178.70177.86174.40R2a302.31296.38285.02286.45R5a673.95667.28644.85651.82Table11 shows the best value and mean value computed by each algorithm for each instance. The results of the four algorithms show a significant difference. We can observe in comparison with other heuristic algorithms the results obtained ALNSip are optimal in terms of the best value and mean value. And with an increase in the number of customers, the ability to find the best optimization solution is higher. In addition, the convergence plot (Figure 5) shows us the convergence of the different algorithms. On observing the plot of them, we can see that ALNSip performs better than other algorithms in convergence and has a strong ability to jump out of the local optimum to avoid premature convergence. As a result, ALNSip can obtain better optimization solutions and effectively search the solution space in terms of solution quality and stability.Figure 5
Convergence graph obtained forALNSip, GA, PSO, and ABC algorithms. (a) R1b. (b) R2b. (c) R3b.
(a)(b)(c)


## 5.3. Customized Buses Instances

In order to test the performance ofALNSip in solving practical problems with large scale, we are inspired by Tong et al. [4] and consider the real commuting issue in Beijing. Finally, we design three customized bus service instances containing small-scale problems and large-scale problems, where commuters leave for their workplaces from their houses and two main business areas, namely, Jingrongjie (destination 1) and Guomao (destination 2), as shown in Figure 6.Figure 6
The distribution of candidate locations. Red and green, respectively, represent the pickup and delivery locations of passengers. (a) Destination: Jinrongjie and (b) Destinantion: Guomao.
(a)(b)The maximum and minimum load capacity,Capku and Capkl, of one with large capacity is 16 and 10, and the other with small capacity range is 9 and 6. We obtain the passengers' preferred time windows with the information processing proposed by Tong et al. [4]. The fixed cost of bus dispatched with large capacity is 30, 25 for the small one. The fuel cost per unit time is 0.4 for those buses with large capacity and 0.25 for the small. The maximum route duration of buses is determined according to the shortest path of the home-to-work. If it is more than 60 minutes, the ticket will be set to 14, and the penalty cost of unserved passengers is 7. If it is less than or equal to 60 minutes, the ticket is set to 10, and the penalty cost is 5. With respect to their proximity in time and space, the requests are divided into 3 groups, and the results of the actual case are finally obtained as follows.Tables12 and 13 show the passengers’ information and routing time between some locations (measured by map software) of Group 1. Similarly, Tables 14 and 15 are for Group 2, and Tables 16 and 17 are for Group 3.Table 11
Comparison ofALNSip with the GA-SA, PSO, and ABC on the benchmark instances.
NoGAPSOABCALNSipMeanBestMeanBestMeanBestMeanBestR1b185.9181.7183.3174.9190.7184.6163.8160.4R2b370.9350.7343.9340.1341.9337.3304.7300.9R3b664.6638.8611.6580.8627.1600.4505.3502.2Table 12
Passenger demands information of Group 1.
Passenger idPick up location with candidate locationDelivery locatione0pl0pe1pl1p11090104760213901047603201001545604209010455552410012476063010515476073095154555830104165060940910204555104010720475711401082050601250101020506013501082047581460101020505815609820475516609102045551770102032476018701020304560198792233476020801025335060Table 13
The routing time between locations of Group 1.
min1234567891011121310840280630346074043705754507677067605850253092504102950110012001300Table 14
Passenger demands information of Group 2.
Passenger idPick up location with candidate locationDelivery locatione0pl0pe1pl1p110110570752189054555310110555604101005657052095104555620115105560720105105560823115105560930971560651030117157075113810715657012301171570751340111015707514439121560651540111015707516431110157075175091520606518501115207075196010101555602065111015556021601110155560226091015455523659101545552460111015556025701012205560267011102055602770101215556028701112205560298010210657030811121070753180921060653280112107075Table 15
The routing time between locations of Group 2.
min12345678910111210540250435525534054343504454044468450274203752843095244370710703115552301200Table 16
Passenger demands information of Group 3.
Passenger idPick up location with candidate locationDelivery locatione0pl0pe1pl1p11014010455521516010455031014515455541815515455552014010455562015010455572014515455582015515405092016010405010301401040501130145154055123016515405013301651540501440140104555154614015455516401472045551750145204555185614517455519501652040502050167204550216015515455522601471745552360165154050246016215405025701651540502675145154555277015515455528712142174555298016010405030801451545553180145204555329015102045553391215520455534901452045553590167204050361001410204555371001472045553810147204555391514102040504010161225405041181412254555422016122540504320145204555442016102040504520141020455546201610204050473015152545554830141020455549301412254555Given the data information in Tables12-15, the results using MIP solver and ALNSip are shown in Table 18.Table 17
The routing time between locations of Group 3.
min12345678910111213141516171819105340250550304204404730530362a24732033845049540410443033117302712330313430281403153071630272870170018001900We set 1000s as the termination condition of the MIP solver. In the first two cases, GROUBI returns feasible solutions with 2.33% and 0% of gap value in the allowed time. In the last large-scale case, there are no feasible solutions in the allowed time for MIP solver. But forALNSip, as shown in Table 18, it can efficiently solve routing problems with different scales. Multiple experiments in Sections 5.2 and 5.3 also demonstrate that it is effective for the proposed ALNSip to solve practice problems with large scale. Additionally, to further verify the effectiveness and advancement of heterogeneous customized bus service with multiple candidate locations, we compare the performance among the two strategies, the homogeneous fleet, as well as the result without candidate locations in Table 19. It can be compared with other cases that the heterogeneous fleets and candidate locations strengthen the cooperation among vehicles and flexibility of routes planning. Therefore, both strategies provide the highest profits (relative increase of 12.3%, 6.2%, and 13.7% in total profits, respectively), no unserved requests, and fewer vehicles to reduce lane occupation. It is of great practical significance for increasing operators’ profit and improving service quality.Table 18
Results for 3 Group instances.
Group No.Number of requestsALNSipMIP solverGap (%)Number of served requestsNumber of unserved requestsBig carsSmall cars120111.25111.252.3320011232336.4336.40.0032020349291.75——49014Total101739.4——101045Table 19
Results comparison in different cases.
Group No.Without candidate locationsHomogeneous fleet with big capacityHomogeneous fleet with small capacityHeterogeneous fleets and candidate locationsProfitsNUNCProfitsNUNCProfitsNUNCProfitsNUNC1111.250298.00294.7522111.25022269.923336.402287.7504336.4023277.315261.453268.006291.7505Total658.45310695.857650.5212739.409NU: number of unserved requests; NC: number of customized buses.


## 5.4. Implications

The customized bus service based on heterogeneous fleets and multiple candidate locations provides a good organizational form and service framework. The proposed mathematical model and algorithm also verify its effectiveness and offer a theoretical basis for further research and implications in practice. The bus operators can improve fleets management and route planning by introducing the new mechanism and strategy. The detailed managerial implications of the proposed methodology can be summarized as follows:(1)
The design of heterogeneous fleets can make customized bus companies construct the fleets more flexibly, save costs, and increase the occupancy rate. Heterogeneous fleets have different load capacities and different transportation costs. The selection of customized buses with different capacities improves scheduling and collaboration among buses and enhances the operational efficiency of bus system. Therefore, effective collaboration among heterogeneous vehicles can contribute to avoiding empty seats and increasing operator profitability.(2)
More candidate locations chosen by passengers in the platform make a breakthrough in the limitations of a single candidate location. From the passengers’ perspective, it increases the probability for the passengers to be served. From the operators’ perspective, it means more flexible route planning. Consequently, multiple candidate locations can be utilized to optimize pickup and delivery routes and serve as many passengers as possible to improve service quality.


## 6. Conclusion

For passengers living in congested metropolitan areas, the customized bus system offers flexible and high-accessibility bus service in the existing transportation network services. Compared with the general customized bus problem, this study constructs a new service form with heterogeneous fleets and multiple candidate locations to deal with practical issues. The two strategies are then analysed and evaluated their effects. To optimize the operator’s profits based on the new service form proposed, a mixed-integer programming model is developed to describe the problem. It is not only suitable for solving small-scale problems but also simple to operate by GUROBI, a commercial solver. An improvedALNSip is then designed to address a large-scale challenge. The initial ALNS algorithm has good performance in terms of routing problem. The time slack calculation method is employed to intelligently adjust vehicle timetables to optimize the wait and duration time. Two inserting operators are utilized to enhance the ability to search solution space, considering some passengers with multiple candidate locations.Numerical experiments are constructed to evaluate the effectiveness of the proposed model and algorithm. The sensitive analysis on small-scale instances indicates that the mechanism with heterogeneous fleets and multiple candidate locations can serve more passengers and obtain more profits. A comparison amongALNSI and ALNSF indicates ALNSip can be efficient in searching for better solutions within a reasonable time. In addition, ALNSip also outperform other heuristic algorithms, like GA, PSO, and ABC, in search ability and avoiding premature. Finally, this study tests the customized bus service in real life to verify its theoretical research and practical implication.This study aims to propose a new form of customized bus service based on heterogeneous fleets and multiple candidate locations. And the designed model and algorithm can offer robust solutions in different scales. In future research, our work can be conducted in the following three directions: (1) researching other models for passengers with random characteristics, who usually offer information in real time and hope to obtain dynamic service, (2) considering the cooperation mechanism between customized bus service and the other transportation systems, and (3) improving the solution algorithm through introducing distributed parallel computing to shorten computing time.



---

*Source: 1679469-2022-05-27.xml*