# Integrated Optimization Strategy for Sustainable Shared Designated Driver Ferry Vehicle Scheduling

Authors: Siqi Wang; Jingbo Yin; Rafi Ullah Khan
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

The focus of this study is on optimizing the schedule adjustment scheme of shared designated driver ferry vehicles to obtain a sustainable and energy-efficient system to pick up and drop off designated drivers to serve drunk customers. A two-stage matching model for driver and customer supply and demand matching and driver ferry vehicle dispatching is designed in order to optimize the total distance travelled and minimize the generalized deviation costs. A maximum residual time adjustment algorithm is designed to reduce the logarithm of new interference demand, and a tabu search algorithm is used to solve the schedule adjustment scheme for ferry vehicles. The validity of the model and the algorithm is verified by a multiperiod example constructed in the Solomon test question bank. The result of numerical experiments shows that the proposed model and algorithm can solve the disruption adjustment scheduling strategy of shared designated driver ferry vehicles. The integrated optimization strategy can effectively improve the utilization rate and the operation efficiency of the shared driver ferry vehicles to reduce operation cost and energy consumption.


---

## Body

## 1. Introduction

Designated drivers are assigned to customers to drive them in the customer’s own cars, for example, if they have been drinking alcohol during an evening meal [1, 2]. Designated driving agency aims at reducing alcohol-related traffic fatalities through prevention, deterrence, and treatment [3]. In recent years, demand for designated drivers specifically for customers with drinking problems has increased rapidly. In 2019《China Social value report of designated driving agency》, the designated driving industry reduced 3.5 million traffic accidents caused by drunk driving, exempted 830 thousand people from criminal law sanctions, and reduced the loss of wealth by 46.2 billion Yuan.Designated drivers may get to the customer’s location on foot or by public transportation. Subject to situations in which the city public transport during rush hours at night gets shut down, some drivers cannot meet the demand by reaching customers’ points in time. The shared designated driver ferry is a transportation tool provided by the designated driving agency to take the designated drivers to the customer’s location and bring them back after serving the customers. The designated driver ferry uses green, energy-saving, and environment protecting electric vehicles to carry out short-distance trips, which can be thought as a subsystem and extension of the city and large-scale public transportation system.However, the dilemma of empty driving of designated driver ferry vehicles is becoming more and more serious. Effective usage of empty vehicles may enhance the efficiency of private transportation and contribute to reducing traffic congestion, fuel consumption, and pollution [4]. As an important part of sustainability strategies, designated driver ferry vehicle dispatching is an important topic that has recently gained significant attention.The demand in designated ferry vehicle dispatching depicts both the pickup point of the designated driver and his drop off at the customer’s location. The designated driver ferry vehicle dispatching problem in this paper is like the Dial-a-Ride Problem (DARP), where users specify requests between origins and destinations, subject to scheduling constraints [5]. In a ride-sharing system, a fleet of vehicles without fixed routes and schedules carries people from their pickup point to their delivery point [6].The research on pickup and delivery problems focused on delivering objects or people in real time, but tight time windows and maximum ride times have not been considered [7, 8]. Dynamic Dial-a-Ride system deals with a dynamic dial-a-ride problem with time window constraints [9]. The design and algorithms of matching and scheduling models act as bottlenecks in related research. Zhang, W. et al. proposed the spatial wide equilibrium model to solve the empty car matching problem [10]. Mark et al. proposed a model on real-time dispatching for a fleet of demand-responsive passenger vehicles such as taxis or variably routed buses [11]. In view of shared taxi dispatching, the dynamic demand of taxi sharing is considered and solved using a genetic algorithm [12]. Andrea Attanasio et al. developed a Tabu search heuristic algorithm for the static DARP, which is able to satisfy a high quantity of user requests [13]. Issam Zidi et al. solved the DRP using the multiobjective simulated annealing algorithm and compared the results with Tabu search algorithm and genetic algorithm [5].As scheduling and rescheduling methods rearrange the whole system strategically, they can achieve the lowest cost [14]. That is to say, the global optimization adjustment of the original plan can get an optimal adjustment scheme, but it may cost a lot of time, space, and human resources, resulting in a large disturbance of the system and even making the new scheme infeasible [15]. At present, many disruption management studies have been conducted in airline industry [16, 17], supply chain and logistics [18], berth schedule [19], and transportation systems [20, 21]. Numerical experiments carried by Qingcheng et al. [19] show that local rescheduling-based tabu search algorithm can improve the computation efficiency comparing to full rescheduling-based algorithm.From the perspective of system optimization and economy effectiveness of ferry vehicle utilization, this paper provides an integrated optimization strategy of supply-demand matching and shared designated driver ferry vehicle dispatching based on disruption management. The objective of this paper is to minimize the disturbance, reduce operating cost, and increase the number of services and their punctuality.The paper is organized as follows. In Section2, problem description and analysis are briefly introduced. In Section 3, the one-stage matching model to optimize total distance travelled is established, and a two-stage disturbance management model is established with the objective of minimizing the generalized deviation cost. Then, in Section 4, a maximum remaining time adjustment algorithm and tabu search algorithm are used to solve the scheduling strategies for designated driver ferry vehicles. Next, in Section 5, a numerical experiment is comparatively analyzed and evaluated, comparing the effectiveness of the proposed two-stage model and algorithm with traditional rescheduling method. Finally, Section 6 summarizes the main findings and highlights issues for future research.


## 2. Problem Description and Analysis

The basic task of the shared designated driver ferry vehicle dispatching is to match the driver and customer demand. Because of the empty driving of designated driver ferry vehicles, there is a large delay in arriving at the customer demand points, which not only affects customer satisfaction, but also indirectly reduces driver efficiency. This paper proposed two-stage models and algorithms based on matching optimization and vehicle scheduling to provide safe and convenient services for designated drivers and customers. Shared designated driver ferry vehicle dispatching can also reduce empty driving and make full use of ferry vehicles, so as to minimize energy consumption and enhance sustainability.


### 2.1. Supply and Demand Matching Optimization

The matching networkFB,C involves driver Bi,ti0,ti,xi,yi,δi and customer needs Cj,tj0,tj,xj,yj. When new customer j is introduced, the designated driving agency makes a real-time decision to match the customer with the nearest driver i who satisfies mindij and ti0≤tj0. In addition, in order to reduce the complexity of vehicle scheduling, the set F¯B¯,C¯ of designated drivers and customers within walking distance must be matched to the best possibility.


### 2.2. Disruption Management of Vehicle Scheduling

In order to facilitate designated drivers travelling to serve the customers, when the matching driver walking time does not meet the customer’s maximum waiting time constraint, the shared designated driver ferry vehicle is considered. Because the matching network is updated in real time, the initial scheduling strategy will be constantly adjusted due to the emergence of new customers and designated drivers. In the dispatching system, the generation of location pointsF˜B˜,C˜ is called twin demand, because every designated driver will be associated with a customer point. Figure 1(a) indicates the initial scheduling strategy at a certain time. At this time, vehicle a has completed the task of dispatching a pair of twin needs (driver 1 and customer 1); vehicle b has completed the task of picking up driver 3. As shown in Figure 1(b), two pairs of twin demand points 5 and 6 are added at this time. Owing to the reversibility of prior vehicle planning, the optimal solution with the lowest cost of the vehicle scheduling can be obtained through rescheduling. However, the adjustment and execution of the plan are extensive and intricate. In this paper, the idea of disruption management is introduced, and a new scheduling strategy is designed to minimize the amount adjustments made to the original schedule in order to make full use of ferry vehicles and reduce operation cost.Figure 1
Vehicle dispatching.The influence of the disturbance (i.e., the new twin demand) on vehicle scheduling is mainly reflected in the deviation of the planning path, the dispatching cost, and the waiting time. There are four forms of deviation of the planning path, as shown in Figure2. The time of disruption is T, the time of arriving at i is Si, the time of arriving at j is Sj, the original route is rij, and the new twin demand points are driver b and customer c. When T≤Si, it is known that the vehicle must change its route before departure fromi. In this scenario, the path may go from b directly to j (Figure 2(a)), or from b to c and then to j (Figure 2(b)). The deviation of the path in (a) can be described as the decrease of rij and the increase of rib and rcj. Similarly, the deviation of the path in (b) is greater than that in (a) due to the additional increase of rbc. When Si<T<Sj, it is known that the vehicle must change its route after departure from i when the vehicle is at p. In this scene, the path may go from b directly to j (Figure 2(c)), or from b to c and then to j (Figure 2(d)). The original path rij is not completely abandoned, because it partially coincides with the new path. Therefore, the deviation of the path in (c) can be expressed as the decrease of rpj and the increase of rpb and rbj.Figure 2
Path migration.There are two forms of deviation of the dispatch cost. One is the start-up cost for a new ferry vehicle, i.e., when a suitable vehicle already in-transit cannot be found, it is necessary to utilize a new ferry vehicle in the dispatching center. If the customer’s maximum waiting time still cannot be met, the service is refused, and the penalty for refusal is accepted. The other form of deviation is the change of vehicle operating cost caused by the path deviation.Waiting time deviation affects customer service satisfaction in two cases: assuming the upper limit of the designated driver expected average waiting time istbE, the upper limit of customer waiting time that does not meet satisfaction is tcE, and the latter service point j is the driver point. The hard time window constraint of waiting time can be transformed into tj<Sj<tj+tbE; if j is the customer point, the hard time window constraint is tj<Sj<tj+tcE.


## 2.1. Supply and Demand Matching Optimization

The matching networkFB,C involves driver Bi,ti0,ti,xi,yi,δi and customer needs Cj,tj0,tj,xj,yj. When new customer j is introduced, the designated driving agency makes a real-time decision to match the customer with the nearest driver i who satisfies mindij and ti0≤tj0. In addition, in order to reduce the complexity of vehicle scheduling, the set F¯B¯,C¯ of designated drivers and customers within walking distance must be matched to the best possibility.


## 2.2. Disruption Management of Vehicle Scheduling

In order to facilitate designated drivers travelling to serve the customers, when the matching driver walking time does not meet the customer’s maximum waiting time constraint, the shared designated driver ferry vehicle is considered. Because the matching network is updated in real time, the initial scheduling strategy will be constantly adjusted due to the emergence of new customers and designated drivers. In the dispatching system, the generation of location pointsF˜B˜,C˜ is called twin demand, because every designated driver will be associated with a customer point. Figure 1(a) indicates the initial scheduling strategy at a certain time. At this time, vehicle a has completed the task of dispatching a pair of twin needs (driver 1 and customer 1); vehicle b has completed the task of picking up driver 3. As shown in Figure 1(b), two pairs of twin demand points 5 and 6 are added at this time. Owing to the reversibility of prior vehicle planning, the optimal solution with the lowest cost of the vehicle scheduling can be obtained through rescheduling. However, the adjustment and execution of the plan are extensive and intricate. In this paper, the idea of disruption management is introduced, and a new scheduling strategy is designed to minimize the amount adjustments made to the original schedule in order to make full use of ferry vehicles and reduce operation cost.Figure 1
Vehicle dispatching.The influence of the disturbance (i.e., the new twin demand) on vehicle scheduling is mainly reflected in the deviation of the planning path, the dispatching cost, and the waiting time. There are four forms of deviation of the planning path, as shown in Figure2. The time of disruption is T, the time of arriving at i is Si, the time of arriving at j is Sj, the original route is rij, and the new twin demand points are driver b and customer c. When T≤Si, it is known that the vehicle must change its route before departure fromi. In this scenario, the path may go from b directly to j (Figure 2(a)), or from b to c and then to j (Figure 2(b)). The deviation of the path in (a) can be described as the decrease of rij and the increase of rib and rcj. Similarly, the deviation of the path in (b) is greater than that in (a) due to the additional increase of rbc. When Si<T<Sj, it is known that the vehicle must change its route after departure from i when the vehicle is at p. In this scene, the path may go from b directly to j (Figure 2(c)), or from b to c and then to j (Figure 2(d)). The original path rij is not completely abandoned, because it partially coincides with the new path. Therefore, the deviation of the path in (c) can be expressed as the decrease of rpj and the increase of rpb and rbj.Figure 2
Path migration.There are two forms of deviation of the dispatch cost. One is the start-up cost for a new ferry vehicle, i.e., when a suitable vehicle already in-transit cannot be found, it is necessary to utilize a new ferry vehicle in the dispatching center. If the customer’s maximum waiting time still cannot be met, the service is refused, and the penalty for refusal is accepted. The other form of deviation is the change of vehicle operating cost caused by the path deviation.Waiting time deviation affects customer service satisfaction in two cases: assuming the upper limit of the designated driver expected average waiting time istbE, the upper limit of customer waiting time that does not meet satisfaction is tcE, and the latter service point j is the driver point. The hard time window constraint of waiting time can be transformed into tj<Sj<tj+tbE; if j is the customer point, the hard time window constraint is tj<Sj<tj+tcE.


## 3. Mathematical Models

### 3.1. Model Variables and Parameters

Decision variables of the model are explained as follows:(i)
xij=1,new customerjis served by driveri,0,others(ii)
yijk′=1,the route fromitojin original planning is provided by vehiclek,0,others(iii)
yijk=1,the route fromitojin new planning is provided by vehiclek,0,others(iv)
State variables and related parameters in the model are explained as follows:(v)
F: matching network, recorded as FB,C(vi)
B: the set of matching designated drivers(vii)
C: the set of matching customers(viii)
F¯: the matching set of designated drivers and customers within walking distance, recorded as F¯B¯,C¯, B¯⊆B, C¯⊆C, B¯=C¯(ix)
F˜: the matching set of designated drivers and customers driven by the shared designated driver ferry, recorded as c, B˜⊆B, C˜⊆C, B˜=C˜(x)
tiS: the time of appearance of demand ii∈B∪C(xi)
ti: the time of matching supply and demand ii∈B∪C(xii)
dij: Euclidean distance between driver i and customer j, i∈B∪C(xiii)
v˜: average walking speed of designated drivers(xiv)
P˜: the real-time location set of in-transit vehicle when disruption occurs(xv)
P: the real-time location set of non-in-transit vehicle when disruption occurs(xvi)
n: dispatching center number, n=0 and n∈P(xvii)
U¯: set of the driver positions that the shared designated driver ferry vehicle did not arrive when the disruption occurs, U¯⊆B, U¯=u¯(xviii)
U˜: set of the customer positions that the shared designated driver ferry vehicle did not arrive when the disruption occurs, U˜⊆C, U˜=u˜(xix)
U: set of the locations that the shared designated driver ferry vehicle will arrive next when the disruption occurs, U=U˜∪U¯∪P∪P˜(xx)
K: set of all shared designated driver ferry vehicles at the dispatching center; each vehicle number is recorded as i=1,…,k(xxi)
K˜: set of all in-transit designated driver ferry vehicles when the disruption occurs, K˜⊂K; the set of not-in-transit designated driver ferry vehicles is K/K˜(xxii)
Qk: the maximum number of designated drivers that vehicle k can carry(xxiii)
α: the fixed cost of dispatching a new designated driver ferry vehicle from the dispatch center(xxiv)
μ: average penalty cost for rejected service(xxv)
β: average unit cost of urban road transport network(xxvi)
γ: unit penalty cost of path variation(xxvii)
dijreal: real distance between demand i and demand j(xxviii)
v¯: average speed of designated driver ferry(xxix)
Si′: the time of original dispatching plan to arrive at the location point of demand i(xxx)
Si: the time of new dispatching plan to arrive at the location point of demand i(xxxi)
tbE: the upper limit of designated driver’s expected waiting time(xxxii)
tcE: the upper limit of customer’s expected waiting time that does not affect service satisfaction


### 3.2. One-Stage Model Based on Supply and Demand Matching

Two-stage model is an advanced optimization strategy of decision-making, which requires the transition of parameters between stages. A one-stage matching model is established based on the optimal function of the matching system total distance. The model is shown as follows:(1)minDB,C=∑i∈B∑j∈Cxijdij,(2)∑j∈Cxij≤1,∀i∈B,(3)∑i∈Bxij≤1,∀j∈C,(4)Prti≤n≤Prtj≤n,tiS≥tjS,∀i,j∈B,(5)dijv˜≤tcE,xij=1,i∈B¯,j∈C¯,F¯B¯,C¯,(6)dijv˜>tcE,xij=1,i∈B˜,j∈C˜,F˜B˜,C˜,(7)xij=0,1,i∈B,j∈C.Equation (1) is the objective function of the one-stage model, which represents the minimum Euclidean distances between designated drivers and customers in the matching system. Equation (2) indicates that each new driver will only match a maximum of one customer. Equation (3) indicates that each new customer is, at the most, served by one designated driver. Equation (4) represents the FIFO () rule in the matching process; that is, the designated driver that occurs firstly will be the first to match for the customer. Equations (5) and (6) indicate that the successfully matched designated drivers must satisfy the waiting time constraints of the customer. If not, the designated drivers and customers will be distributed into the set of demands, for which it is considered to be accomplished by the shared designated driver ferry vehicle. Equation (7) is the value constraint of decision variables.


### 3.3. Two-Stage Model Based on Scheduling Disruption

Taking one-stage model transmitF˜B˜,C˜ as the twin demand disruption, a two-stage model with minimum generalized deviation cost is constructed as follows:(8)minZB˜,C˜=ZN+ZC,(9)ZN=∑k∈K/K˜∑j∈U¯αynjk+μ2∑i∈B˜∪C˜1−∑j∈B˜∪C˜yijk,(10)ZC=β∑k∈K˜∑i∈U∪B˜∪C˜∑j∈U∪B˜∪C˜dijrealyijk−∑k∈K˜∑i∈U∑j∈Udijrealyijk′+∑k∈K˜∑i∈U∑j∈Uγyijk′−yijk,(11)∑i∈U∪B˜∪C˜∑j∈U˜∪C˜yijk+1≤Qk,Si≥Sb,∀b∈B˜,∀k∈K,(12)∑k∈K/K˜∑j∈U¯ynjk≤KK˜,(13)∑k∈K∑j∈Uyijk≤1,∀i∈B˜∪C˜,∀k∈K,(14)∑j∈U∪B˜yijk=1,∀i∈P˜,∀k∈K˜,(15)∑i∈U∪B˜∪C˜yihk=∑j∈U∪B˜∪C˜yhjk,∀h∈U∪B˜∪C˜,∀k∈K,(16)∑i∈U∪C˜yink=1,∀k∈K,(17)Sj=Si+dijrealv¯,yijk=1,∀i,j∈U∪B˜∪C˜,(18)ti<Si<ti+taE,∀i∈U¯∪B˜,(19)ti<Si<ti+tcE,∀i∈U˜∪C˜,(20)Si≤Sj,xij=1,∀i∈B˜,j∈C˜,(21)yijk′∈0,1,∀i,j∈U∪n,∀k∈K,(22)yijk∈0,1,∀i,j∈U∪B˜∪C˜∪n,∀k∈K.Equation (8) is the two-stage model objective function, which represents the minimum generalized deviation cost of the new dispatching plan, including the path deviation and cost deviation. Equation (9) is the cost of new designated driver ferry vehicle start-up and penalty cost for rejected service. Equation (10) is the travel cost and penalty cost caused by actual path deviation. Equation (11) is the capacity constraint of designated driver ferry vehicle. Equation (12) indicates that the number of newly dispatched designated driver ferry vehicles should not exceed the number of remaining vehicles in the dispatching center. Equation (13) means that each designated driver and customer can only be served by one ferry vehicle or be abandoned due to the dissatisfaction of scheduling conditions. Equation (14) indicates that all in-transit ferry vehicles start from the current location. Equation (15) indicates the balance of the demand points for vehicle service. Equation (16) indicates that the ferry vehicle will be required to return to the dispatching center when the last designated driver is sent to the customer’s point. Equation (17) indicates the time recurrence of customers. Equation (18) indicates that the arrival of the ferry vehicle at each designated driver’s point needs to satisfy the designated driver’s waiting time constraint. Equation (19) indicates the arrival of the ferry vehicle at each customer point needs to meet the customer’s waiting time constraint. Equation (20) indicates that the ferry vehicle needs to first pick up the designated drivers and send them to the customers. Equations (21) and (22) are the value constraints of decision variables.


## 3.1. Model Variables and Parameters

Decision variables of the model are explained as follows:(i)
xij=1,new customerjis served by driveri,0,others(ii)
yijk′=1,the route fromitojin original planning is provided by vehiclek,0,others(iii)
yijk=1,the route fromitojin new planning is provided by vehiclek,0,others(iv)
State variables and related parameters in the model are explained as follows:(v)
F: matching network, recorded as FB,C(vi)
B: the set of matching designated drivers(vii)
C: the set of matching customers(viii)
F¯: the matching set of designated drivers and customers within walking distance, recorded as F¯B¯,C¯, B¯⊆B, C¯⊆C, B¯=C¯(ix)
F˜: the matching set of designated drivers and customers driven by the shared designated driver ferry, recorded as c, B˜⊆B, C˜⊆C, B˜=C˜(x)
tiS: the time of appearance of demand ii∈B∪C(xi)
ti: the time of matching supply and demand ii∈B∪C(xii)
dij: Euclidean distance between driver i and customer j, i∈B∪C(xiii)
v˜: average walking speed of designated drivers(xiv)
P˜: the real-time location set of in-transit vehicle when disruption occurs(xv)
P: the real-time location set of non-in-transit vehicle when disruption occurs(xvi)
n: dispatching center number, n=0 and n∈P(xvii)
U¯: set of the driver positions that the shared designated driver ferry vehicle did not arrive when the disruption occurs, U¯⊆B, U¯=u¯(xviii)
U˜: set of the customer positions that the shared designated driver ferry vehicle did not arrive when the disruption occurs, U˜⊆C, U˜=u˜(xix)
U: set of the locations that the shared designated driver ferry vehicle will arrive next when the disruption occurs, U=U˜∪U¯∪P∪P˜(xx)
K: set of all shared designated driver ferry vehicles at the dispatching center; each vehicle number is recorded as i=1,…,k(xxi)
K˜: set of all in-transit designated driver ferry vehicles when the disruption occurs, K˜⊂K; the set of not-in-transit designated driver ferry vehicles is K/K˜(xxii)
Qk: the maximum number of designated drivers that vehicle k can carry(xxiii)
α: the fixed cost of dispatching a new designated driver ferry vehicle from the dispatch center(xxiv)
μ: average penalty cost for rejected service(xxv)
β: average unit cost of urban road transport network(xxvi)
γ: unit penalty cost of path variation(xxvii)
dijreal: real distance between demand i and demand j(xxviii)
v¯: average speed of designated driver ferry(xxix)
Si′: the time of original dispatching plan to arrive at the location point of demand i(xxx)
Si: the time of new dispatching plan to arrive at the location point of demand i(xxxi)
tbE: the upper limit of designated driver’s expected waiting time(xxxii)
tcE: the upper limit of customer’s expected waiting time that does not affect service satisfaction


## 3.2. One-Stage Model Based on Supply and Demand Matching

Two-stage model is an advanced optimization strategy of decision-making, which requires the transition of parameters between stages. A one-stage matching model is established based on the optimal function of the matching system total distance. The model is shown as follows:(1)minDB,C=∑i∈B∑j∈Cxijdij,(2)∑j∈Cxij≤1,∀i∈B,(3)∑i∈Bxij≤1,∀j∈C,(4)Prti≤n≤Prtj≤n,tiS≥tjS,∀i,j∈B,(5)dijv˜≤tcE,xij=1,i∈B¯,j∈C¯,F¯B¯,C¯,(6)dijv˜>tcE,xij=1,i∈B˜,j∈C˜,F˜B˜,C˜,(7)xij=0,1,i∈B,j∈C.Equation (1) is the objective function of the one-stage model, which represents the minimum Euclidean distances between designated drivers and customers in the matching system. Equation (2) indicates that each new driver will only match a maximum of one customer. Equation (3) indicates that each new customer is, at the most, served by one designated driver. Equation (4) represents the FIFO () rule in the matching process; that is, the designated driver that occurs firstly will be the first to match for the customer. Equations (5) and (6) indicate that the successfully matched designated drivers must satisfy the waiting time constraints of the customer. If not, the designated drivers and customers will be distributed into the set of demands, for which it is considered to be accomplished by the shared designated driver ferry vehicle. Equation (7) is the value constraint of decision variables.


## 3.3. Two-Stage Model Based on Scheduling Disruption

Taking one-stage model transmitF˜B˜,C˜ as the twin demand disruption, a two-stage model with minimum generalized deviation cost is constructed as follows:(8)minZB˜,C˜=ZN+ZC,(9)ZN=∑k∈K/K˜∑j∈U¯αynjk+μ2∑i∈B˜∪C˜1−∑j∈B˜∪C˜yijk,(10)ZC=β∑k∈K˜∑i∈U∪B˜∪C˜∑j∈U∪B˜∪C˜dijrealyijk−∑k∈K˜∑i∈U∑j∈Udijrealyijk′+∑k∈K˜∑i∈U∑j∈Uγyijk′−yijk,(11)∑i∈U∪B˜∪C˜∑j∈U˜∪C˜yijk+1≤Qk,Si≥Sb,∀b∈B˜,∀k∈K,(12)∑k∈K/K˜∑j∈U¯ynjk≤KK˜,(13)∑k∈K∑j∈Uyijk≤1,∀i∈B˜∪C˜,∀k∈K,(14)∑j∈U∪B˜yijk=1,∀i∈P˜,∀k∈K˜,(15)∑i∈U∪B˜∪C˜yihk=∑j∈U∪B˜∪C˜yhjk,∀h∈U∪B˜∪C˜,∀k∈K,(16)∑i∈U∪C˜yink=1,∀k∈K,(17)Sj=Si+dijrealv¯,yijk=1,∀i,j∈U∪B˜∪C˜,(18)ti<Si<ti+taE,∀i∈U¯∪B˜,(19)ti<Si<ti+tcE,∀i∈U˜∪C˜,(20)Si≤Sj,xij=1,∀i∈B˜,j∈C˜,(21)yijk′∈0,1,∀i,j∈U∪n,∀k∈K,(22)yijk∈0,1,∀i,j∈U∪B˜∪C˜∪n,∀k∈K.Equation (8) is the two-stage model objective function, which represents the minimum generalized deviation cost of the new dispatching plan, including the path deviation and cost deviation. Equation (9) is the cost of new designated driver ferry vehicle start-up and penalty cost for rejected service. Equation (10) is the travel cost and penalty cost caused by actual path deviation. Equation (11) is the capacity constraint of designated driver ferry vehicle. Equation (12) indicates that the number of newly dispatched designated driver ferry vehicles should not exceed the number of remaining vehicles in the dispatching center. Equation (13) means that each designated driver and customer can only be served by one ferry vehicle or be abandoned due to the dissatisfaction of scheduling conditions. Equation (14) indicates that all in-transit ferry vehicles start from the current location. Equation (15) indicates the balance of the demand points for vehicle service. Equation (16) indicates that the ferry vehicle will be required to return to the dispatching center when the last designated driver is sent to the customer’s point. Equation (17) indicates the time recurrence of customers. Equation (18) indicates that the arrival of the ferry vehicle at each designated driver’s point needs to satisfy the designated driver’s waiting time constraint. Equation (19) indicates the arrival of the ferry vehicle at each customer point needs to meet the customer’s waiting time constraint. Equation (20) indicates that the ferry vehicle needs to first pick up the designated drivers and send them to the customers. Equations (21) and (22) are the value constraints of decision variables.


## 4. Algorithm Design

The integrated optimization problem of designated driver supply-demand matching and vehicle scheduling is a complex decision-making problem of “supply-demand matching-disruption management.” Although the one-stage model can achieve the optimal solution under the infinite delay strategy, it may not be able to obtain the equilibrium solution after adding the waiting time constraint. The two-stage model is an extension of the Dial-a-Ride Problem, which is a NP-hard problem, as it generalizes the pickup and delivery problem with the time windows [6]. It is difficult to design an exact solution algorithm. In order to meet the demand of dynamic real-time decision-making, it is necessary to find a solution strategy with high efficiency and better calculation results. In this study, the one-stage model is solved based on the nearest location matching principle. The maximum remaining time adjustment algorithm is used to reduce the number of F˜ elements, and the disruption scale of the two-stage vehicle scheduling to the possible extent. The tabu search algorithm is designed to solve two-stage model, because the tabu search algorithm can carry out fast global optimization step by step [22]. The detailed steps of the algorithm are shown in Figure 3.Figure 3
A flowchart of the algorithm.


### 4.1. Maximum Remaining Time Adjustment Algorithm

The optimal solution of the one-stage model can be solved based on the nearest location matching principle to obtain the minimum Euclidean distances between designated drivers and customers in the matching system. The nearest location matching principle first obtainsB¯i,C¯i by matching customer set Ci with driver set Bi, which meet the constraints of mindBi,Ci and dB¯i,C¯i<tcE. Similarly, B˜j,C˜j can be obtained if dB˜j,C˜j>tcE. However, there may be conditions such as dB¯i,C˜j<tcE or dB˜j,C¯i<tcE. In order to reduce the number of F˜ elements and the disruption scale of the two-stage vehicle scheduling, it is necessary to calculate the remaining amount of each element and the maximum walking time. The steps of maximum remaining time adjustment algorithm are shown as follows:Step 1: find the designated driverBi for customer Cj to meet mindBi,Cj as the initial matching set Bi,Cj.Step 2: estimate walking arrival timetijB and calculate the maximum remaining time ΔtijB=tcE−tijB. If ΔtijB<0, Bi,Cj will be arranged into F˜. If not, Bi,Cj will be arranged into F¯ in descending order.Step 3: extractB¯i in F¯i, i=i+1.Step 4: findC˜j in F˜ to match with B¯i and obtain B¯i,C˜j and B˜j,C¯i.Step 5: ifΔtjiB<0 or ΔtijB<0, there will not be adjustments for F˜ and F¯, j=j+1, go to Step 7. Otherwise, go to the next step.Step 6:B˜j,C˜j and B¯i,C¯i are removed from F˜ and F¯ and recorded into F¯, j=j+1.Step 7: Ifj<F¯, go back to Step 4 to find new C˜j. Otherwise, go to the next step.Step 8: Ifj<F¯, go back to Step 3 to extract new B˜i. Otherwise, the algorithm ends.


### 4.2. Tabu Search Algorithm

For the two-stage model, the design of tabu search algorithm is shown as follows.


#### 4.2.1. Initial Solution Generation

Taking the initial timeti of each decision period i as the moment of occurrence of the disruption, the result of the decision period i−1 is taken as the initial solution of the designated driver vehicle dispatching of the decision period i. This represents the core idea that disruption management for partial adjustment is based on the original plan.


#### 4.2.2. Neighborhood Transformation Rule

Rule 1: nearer ferry vehicle priority insertion: the nearest in-transit ferry vehicle is chosen after the designated driver’s location is inserted into the algorithm. As shown in Figure4(a), the ferry vehicle 1 is selected to adjust its path to pick up designated driver b7 because db7,c1<db7,c8. On the premise of meeting the designated driver’s waiting time window constraint ti,ti+tbE and the capacity constraint of designated driver ferry vehicle, the route c1c2 is chosen as the insertion path. If all points meet the time window constraint after insertion, consider inserting client point c7; otherwise, search neighborhood c2b4 and b4c3. The insertion of customer point c7 is shown in Figure 4(b), and its neighborhood is modelled with reference to ferry vehicle 1’s path after insertion of designated driver b7.Figure 4
Neighborhood transformation.Rule 2: vehicle replacement rules: if there is no feasible solution in Rule 1, the planned path of Vehicle 2, which is far from the designated driver’s point at the time of disruption, will be considered, and Rule 1 is used to identify a feasible solution. If there is no feasible solution, further vehicles will be tried.


#### 4.2.3. Tabu Rule

The tabu object is the insertion position of the disruption point of customers and designated drivers when the disruption occurs. When the disruption point is inserted in a certain position, the insertion of the disruption point in that position is not permitted withinl searches of the tabu length.


#### 4.2.4. Aspiration Principle

If the objective function value of a neighborhood solution is less than that of the current optimal solution, the solution is not restricted by tabu rules, and the current optimal solution will be replaced.


## 4.1. Maximum Remaining Time Adjustment Algorithm

The optimal solution of the one-stage model can be solved based on the nearest location matching principle to obtain the minimum Euclidean distances between designated drivers and customers in the matching system. The nearest location matching principle first obtainsB¯i,C¯i by matching customer set Ci with driver set Bi, which meet the constraints of mindBi,Ci and dB¯i,C¯i<tcE. Similarly, B˜j,C˜j can be obtained if dB˜j,C˜j>tcE. However, there may be conditions such as dB¯i,C˜j<tcE or dB˜j,C¯i<tcE. In order to reduce the number of F˜ elements and the disruption scale of the two-stage vehicle scheduling, it is necessary to calculate the remaining amount of each element and the maximum walking time. The steps of maximum remaining time adjustment algorithm are shown as follows:Step 1: find the designated driverBi for customer Cj to meet mindBi,Cj as the initial matching set Bi,Cj.Step 2: estimate walking arrival timetijB and calculate the maximum remaining time ΔtijB=tcE−tijB. If ΔtijB<0, Bi,Cj will be arranged into F˜. If not, Bi,Cj will be arranged into F¯ in descending order.Step 3: extractB¯i in F¯i, i=i+1.Step 4: findC˜j in F˜ to match with B¯i and obtain B¯i,C˜j and B˜j,C¯i.Step 5: ifΔtjiB<0 or ΔtijB<0, there will not be adjustments for F˜ and F¯, j=j+1, go to Step 7. Otherwise, go to the next step.Step 6:B˜j,C˜j and B¯i,C¯i are removed from F˜ and F¯ and recorded into F¯, j=j+1.Step 7: Ifj<F¯, go back to Step 4 to find new C˜j. Otherwise, go to the next step.Step 8: Ifj<F¯, go back to Step 3 to extract new B˜i. Otherwise, the algorithm ends.


## 4.2. Tabu Search Algorithm

For the two-stage model, the design of tabu search algorithm is shown as follows.


### 4.2.1. Initial Solution Generation

Taking the initial timeti of each decision period i as the moment of occurrence of the disruption, the result of the decision period i−1 is taken as the initial solution of the designated driver vehicle dispatching of the decision period i. This represents the core idea that disruption management for partial adjustment is based on the original plan.


### 4.2.2. Neighborhood Transformation Rule

Rule 1: nearer ferry vehicle priority insertion: the nearest in-transit ferry vehicle is chosen after the designated driver’s location is inserted into the algorithm. As shown in Figure4(a), the ferry vehicle 1 is selected to adjust its path to pick up designated driver b7 because db7,c1<db7,c8. On the premise of meeting the designated driver’s waiting time window constraint ti,ti+tbE and the capacity constraint of designated driver ferry vehicle, the route c1c2 is chosen as the insertion path. If all points meet the time window constraint after insertion, consider inserting client point c7; otherwise, search neighborhood c2b4 and b4c3. The insertion of customer point c7 is shown in Figure 4(b), and its neighborhood is modelled with reference to ferry vehicle 1’s path after insertion of designated driver b7.Figure 4
Neighborhood transformation.Rule 2: vehicle replacement rules: if there is no feasible solution in Rule 1, the planned path of Vehicle 2, which is far from the designated driver’s point at the time of disruption, will be considered, and Rule 1 is used to identify a feasible solution. If there is no feasible solution, further vehicles will be tried.


### 4.2.3. Tabu Rule

The tabu object is the insertion position of the disruption point of customers and designated drivers when the disruption occurs. When the disruption point is inserted in a certain position, the insertion of the disruption point in that position is not permitted withinl searches of the tabu length.


### 4.2.4. Aspiration Principle

If the objective function value of a neighborhood solution is less than that of the current optimal solution, the solution is not restricted by tabu rules, and the current optimal solution will be replaced.


## 4.2.1. Initial Solution Generation

Taking the initial timeti of each decision period i as the moment of occurrence of the disruption, the result of the decision period i−1 is taken as the initial solution of the designated driver vehicle dispatching of the decision period i. This represents the core idea that disruption management for partial adjustment is based on the original plan.


## 4.2.2. Neighborhood Transformation Rule

Rule 1: nearer ferry vehicle priority insertion: the nearest in-transit ferry vehicle is chosen after the designated driver’s location is inserted into the algorithm. As shown in Figure4(a), the ferry vehicle 1 is selected to adjust its path to pick up designated driver b7 because db7,c1<db7,c8. On the premise of meeting the designated driver’s waiting time window constraint ti,ti+tbE and the capacity constraint of designated driver ferry vehicle, the route c1c2 is chosen as the insertion path. If all points meet the time window constraint after insertion, consider inserting client point c7; otherwise, search neighborhood c2b4 and b4c3. The insertion of customer point c7 is shown in Figure 4(b), and its neighborhood is modelled with reference to ferry vehicle 1’s path after insertion of designated driver b7.Figure 4
Neighborhood transformation.Rule 2: vehicle replacement rules: if there is no feasible solution in Rule 1, the planned path of Vehicle 2, which is far from the designated driver’s point at the time of disruption, will be considered, and Rule 1 is used to identify a feasible solution. If there is no feasible solution, further vehicles will be tried.


## 4.2.3. Tabu Rule

The tabu object is the insertion position of the disruption point of customers and designated drivers when the disruption occurs. When the disruption point is inserted in a certain position, the insertion of the disruption point in that position is not permitted withinl searches of the tabu length.


## 4.2.4. Aspiration Principle

If the objective function value of a neighborhood solution is less than that of the current optimal solution, the solution is not restricted by tabu rules, and the current optimal solution will be replaced.


## 5. Numerical Experiment Analysis

### 5.1. Validity Analysis

Based on the background of the problem description of the shared designated driver ferry vehicle dispatching, the driver and customer demand are generated and allocated to the ferry vehicles randomly. In the system, when the walking time of the matching designate driver does not meet the maximum waiting time constraint of the customer, the shared designated driver ferry vehicle is considered to dispatch the driver. Due to the real-time update of the matching network, the initial scheduling strategy will be constantly adjusted due to the new matching results.In order to verify the validity of the model and algorithm, this study took the C106 coordinate points of the Solomon test question bank as a reference. The first 40 coordinates are randomly and evenly allocated between the driver set and the customer set as the initial example at decision period 0. The next 60 points are averagely allocated to three groups (decision periods 1–3 with an interval of 120 seconds). Suppose that the dispatching center has 10 ferry vehicles with a maximum capacity of 7 passengers (excluding vehicles’ drivers), running at a speed of 1 unit per minute and a driver walk at a speed of 0.2 units per minute.After constructing the two-stage algorithm in MATLAB, the results of dispatching strategy are shown in Figure5. At decision period 0, the initial route of vehicle 1 is 0-b5-c5-0; the initial route of vehicle 2 is 0-b15-c15-0; that of vehicle 3 is 0-b13-b4-c4-c13-0; and that of vehicle 4 is 0-b20-c20-0. At decision-making period 1 (0–120s), the new matching pairs 22 and 29 are abandoned, because the time constraints cannot be met. At decision-making period 2 (120–240s), the new matching pairs 31 and 39 are abandoned, and the new vehicle 5 has the route 0-b35-c35-0. At decision-making period 3 (240–360s), a new pair 45 is inserted into vehicle 4’s route, creating the adjustment path of V3-b20-b45-c45-c20-0, and new vehicle 6 has the route 0-b44-c44-0. In the dispatching process, 5 pairs of designated drivers were abandoned, 8 pairs were serviced, and 17 pairs could arrive on foot.Figure 5
Two-stage algorithm results in MATLAB. (a) Initial path. (b) Decision-making period 1. (c) Decision-making period 2. (d) Decision-making period 3.
(a)(b)(c)(d)The results of the optimized matching and dispatching of the three periods of C106 are compared for disruption management and rescheduling. The following three points can be seen from the results of the deviations shown in Table1.Table 1
Comparison of optimization results and rescheduling scheme.
SchemeDistance deviation ZC1Service deviation ZNPath deviation ZC2Generalized deviating cost ZThe average operation time of algorithm (s)Rescheduling2654.233600.00108781.8315.35Disruption management1829.304800.0027134.827.131. For distance deviation, disruption management can yield lower total travel distance than the rescheduling plan. 2. For service deviation, rescheduling can lower the cost of new vehicle startup and penalty for denial of service. 3. For path deviation, the rescheduling deviation is 10, and the vehicle route needs to be adjusted to a large scale in real time. The deviation of the disruption management adjustment is lower, and only the adjustment of specific vehicles is needed.Compared with the rescheduling algorithm, the model and algorithm of disruption management have lower average operation time, lower generalized deviation cost, and higher algorithm efficiency. Also, it can provide decision support for new demand disturbance for the vehicle service after matching.


### 5.2. Sensitivity Analysis

In order to explore the general effect of driver and customer position distribution on the supply-demand matching and disruption adjustment model in each decision-making period, sensitivity analysis was carried out with the Solomon test question bank C106, C206, R106, and RC106 data sets. The matching pairs of demand points and the matching total distance at different decision-making periods of algorithm optimization are shown in Tables2 and 3.Table 2
Comparison of the number of pairs of demand points.
Number of pairs of demand pointsDecision-making periodOriginal matching pairsMax △t adjustmentReduced numberC1060642122023213220C2060862153224403871R1060151231109129903770RC106012111199029903880Table 3
Total matching distance.
Total matching distanceDecision-making periodOriginal matchingMax △t adjustmentTotal distance variationC10609799−217676—26057334141—C2060114105916164−329494—31251214R106011110110114614512103103—37878—RC1060144138518282—2116116—3111111—Tables2 and 3 show that the greater the discrete degree of driver and customer position distribution (R106 > RC106 > C206 > C106), the more the number of pairs of demand points reduced by a maximum remaining time adjustment algorithm. For the total distance of the system F˜ and F¯, the maximum remaining time adjustment algorithm may result in the increase of the total distance. This shows that the matching customer is not necessarily the nearest customer for the driver, and the solution produced is not necessarily the optimal solution for the system, but it effectively reduces the number of new disruptions in two-stage decision-making. It is an optimal solution to integrate one-stage and two-stage decision coordination.The generalized deviation cost for each decision-making period and the matching pairs of abandonment of service where the time window constraint cannot be satisfied are shown in Figure6.Figure 6
Comparison of two-stage disruption adjustment results. (a) Generalized deviation cost comparison. (b) Abandonment of service comparison.
(a)(b)As the locations of the example become more discrete, the generalized deviation cost increases, and the difference between the adjustment scheme and the vehicle’s original plan increases. From the relatively discrete degree of R106, the generalized deviation cost is always at a high level, and the probability of requiring a new vehicle or abandoning an additional pair of customer and driver is higher. Hence, the abandonment of service logarithm shown in Figure6(b) will also decrease. As the samples C106 and RC106 are relatively concentrated, the matching number of demand points also increases, and the abandonment of service number of designated drivers shows a certain degree of decline.


## 5.1. Validity Analysis

Based on the background of the problem description of the shared designated driver ferry vehicle dispatching, the driver and customer demand are generated and allocated to the ferry vehicles randomly. In the system, when the walking time of the matching designate driver does not meet the maximum waiting time constraint of the customer, the shared designated driver ferry vehicle is considered to dispatch the driver. Due to the real-time update of the matching network, the initial scheduling strategy will be constantly adjusted due to the new matching results.In order to verify the validity of the model and algorithm, this study took the C106 coordinate points of the Solomon test question bank as a reference. The first 40 coordinates are randomly and evenly allocated between the driver set and the customer set as the initial example at decision period 0. The next 60 points are averagely allocated to three groups (decision periods 1–3 with an interval of 120 seconds). Suppose that the dispatching center has 10 ferry vehicles with a maximum capacity of 7 passengers (excluding vehicles’ drivers), running at a speed of 1 unit per minute and a driver walk at a speed of 0.2 units per minute.After constructing the two-stage algorithm in MATLAB, the results of dispatching strategy are shown in Figure5. At decision period 0, the initial route of vehicle 1 is 0-b5-c5-0; the initial route of vehicle 2 is 0-b15-c15-0; that of vehicle 3 is 0-b13-b4-c4-c13-0; and that of vehicle 4 is 0-b20-c20-0. At decision-making period 1 (0–120s), the new matching pairs 22 and 29 are abandoned, because the time constraints cannot be met. At decision-making period 2 (120–240s), the new matching pairs 31 and 39 are abandoned, and the new vehicle 5 has the route 0-b35-c35-0. At decision-making period 3 (240–360s), a new pair 45 is inserted into vehicle 4’s route, creating the adjustment path of V3-b20-b45-c45-c20-0, and new vehicle 6 has the route 0-b44-c44-0. In the dispatching process, 5 pairs of designated drivers were abandoned, 8 pairs were serviced, and 17 pairs could arrive on foot.Figure 5
Two-stage algorithm results in MATLAB. (a) Initial path. (b) Decision-making period 1. (c) Decision-making period 2. (d) Decision-making period 3.
(a)(b)(c)(d)The results of the optimized matching and dispatching of the three periods of C106 are compared for disruption management and rescheduling. The following three points can be seen from the results of the deviations shown in Table1.Table 1
Comparison of optimization results and rescheduling scheme.
SchemeDistance deviation ZC1Service deviation ZNPath deviation ZC2Generalized deviating cost ZThe average operation time of algorithm (s)Rescheduling2654.233600.00108781.8315.35Disruption management1829.304800.0027134.827.131. For distance deviation, disruption management can yield lower total travel distance than the rescheduling plan. 2. For service deviation, rescheduling can lower the cost of new vehicle startup and penalty for denial of service. 3. For path deviation, the rescheduling deviation is 10, and the vehicle route needs to be adjusted to a large scale in real time. The deviation of the disruption management adjustment is lower, and only the adjustment of specific vehicles is needed.Compared with the rescheduling algorithm, the model and algorithm of disruption management have lower average operation time, lower generalized deviation cost, and higher algorithm efficiency. Also, it can provide decision support for new demand disturbance for the vehicle service after matching.


## 5.2. Sensitivity Analysis

In order to explore the general effect of driver and customer position distribution on the supply-demand matching and disruption adjustment model in each decision-making period, sensitivity analysis was carried out with the Solomon test question bank C106, C206, R106, and RC106 data sets. The matching pairs of demand points and the matching total distance at different decision-making periods of algorithm optimization are shown in Tables2 and 3.Table 2
Comparison of the number of pairs of demand points.
Number of pairs of demand pointsDecision-making periodOriginal matching pairsMax △t adjustmentReduced numberC1060642122023213220C2060862153224403871R1060151231109129903770RC106012111199029903880Table 3
Total matching distance.
Total matching distanceDecision-making periodOriginal matchingMax △t adjustmentTotal distance variationC10609799−217676—26057334141—C2060114105916164−329494—31251214R106011110110114614512103103—37878—RC1060144138518282—2116116—3111111—Tables2 and 3 show that the greater the discrete degree of driver and customer position distribution (R106 > RC106 > C206 > C106), the more the number of pairs of demand points reduced by a maximum remaining time adjustment algorithm. For the total distance of the system F˜ and F¯, the maximum remaining time adjustment algorithm may result in the increase of the total distance. This shows that the matching customer is not necessarily the nearest customer for the driver, and the solution produced is not necessarily the optimal solution for the system, but it effectively reduces the number of new disruptions in two-stage decision-making. It is an optimal solution to integrate one-stage and two-stage decision coordination.The generalized deviation cost for each decision-making period and the matching pairs of abandonment of service where the time window constraint cannot be satisfied are shown in Figure6.Figure 6
Comparison of two-stage disruption adjustment results. (a) Generalized deviation cost comparison. (b) Abandonment of service comparison.
(a)(b)As the locations of the example become more discrete, the generalized deviation cost increases, and the difference between the adjustment scheme and the vehicle’s original plan increases. From the relatively discrete degree of R106, the generalized deviation cost is always at a high level, and the probability of requiring a new vehicle or abandoning an additional pair of customer and driver is higher. Hence, the abandonment of service logarithm shown in Figure6(b) will also decrease. As the samples C106 and RC106 are relatively concentrated, the matching number of demand points also increases, and the abandonment of service number of designated drivers shows a certain degree of decline.


## 6. Conclusions

This paper studies the integrated optimization of supply and demand matching and shared designated driver ferry vehicle dispatching. A two-stage model is established based on the matching setF˜B˜,C˜ as a parameter, which cannot be reached by walking. The one-stage model is modelled by system distance optimization, and the pair number of F˜ is optimized. The two-stage model is aimed to minimize the generalized deviation cost of the vehicle route caused by additional demand disturbances and optimizes the adjustment scheme accordingly. The algorithm proposes the optimal remaining time adjustment strategy to improve the matching results and uses the tabu search method to solve the disruption adjustment scheduling strategy of shared designated driver ferry vehicles in each decision period. Numerical experiments show that the proposed model and algorithm can effectively solve small-scale numerical examples, and the computational speed and results are superior to the rescheduling method. Sensitivity analysis shows that the location distribution characteristics of drivers and customers can affect the solution’s results to a certain degree, and location concentration should be considered further in matching and scheduling adjustments.Since sustainable development has attracted many scholars’ attention, the model and algorithm in this study have reference value for reducing empty driving and energy usage of shared designated driver ferry vehicles. In order to improve the comprehensive driving experience of the designated driver and the customer, the shared ferry platform can be provided between the designated drivers and the customer. In addition, a new generation platform based on real-time interference scheduling strategy is highly recommended on account of the reasonable matches of the needs of designated drivers and customers. The new platform can provide safe and convenient services for drivers and customers, which not only increases customer satisfaction, but also indirectly promotes the work efficiency of drivers.The solution of dispatching and scheduling problem provided in this paper will effectively improve the utilization rate and the operation efficiency of the shared driver ferry vehicles to reduce energy consumption and operation cost. Meanwhile, the dynamic vehicle scheduling and interference management can realize the empty vehicle sharing. Shared mobility can promote sustainable transportation and improves air quality by reducing congestion and greenhouse gas emissions.Furthermore, the model and algorithm can be applied to more fields, such as vehicle scheduling problems between warehouses and distribution center, reducing the empty vehicle operation problem and improving the vehicle use efficiency. The future research will focus on increasing the efficiency of transportation to reduce the impact of global warming.



---

*Source: 9950834-2021-06-08.xml*