# A Green Demand-Responsive Airport Shuttle Service Problem with Time-Varying Speeds

Authors: Ming Wei; Binbin Jing; Jian Yin; Yang Zang
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

This study proposes a multiobjective mixed integer linear programming (MOMILP) model for a demand-responsive airport shuttle service. The approach aims to assign a set of alternative fuel vehicles (AFVs) located at different depots to visit each demand point within the specified time and transport all of them to the airport. The proposed model effectively captures the interactions between path selection and environmental protection. Moreover, users with flexible pick-up time windows, the time-varying speed of vehicles on the road network, and the limited fuel for the route duration are also fully considered in this model. The work aims at simultaneously minimizing the operating cost, vehicle fuel consumption, and CO2 emissions. Since this task is an NP-hard problem, a heuristic-based nondominated sorting genetic algorithm (NSGA-II) is also presented to find Pareto optimal solutions in a reasonable amount of time. Finally, a real-world example is provided to illustrate the proposed methodology. The results demonstrate that the model not only selects an optimal depot for each AFV but also determines its route and timetable plan. A sensitivity analysis is also given to assess the effect of early/late arrival penalty weights and the number of AFVs on the model performance, and the difference in quality between the proposed and traditional models is compared.


---

## Body

## 1. Introduction

Airports are generally located in the suburbs of a city; therefore, passengers living in urban areas need to be transported to the airport by shuttle buses. To increase the flexibility and accessibility of airport services, an increasing number of traffic authorities in different countries have realized airport shuttle services in a regular bus or subway system as one of the most effective strategies to meet passengers’ accessibility needs. Most of the existing shuttle services are fixed-route regular bus or subway systems, which are suitable for high-density residential areas. However, this can often have high operating costs and low service levels in some remote areas with few people. Currently, with the rapid expansion of mobile internet, the demand-responsive airport shuttle services (DRASS) using app-based ride services is a future trend in designing a customized supply-to-demand transit route. Some of the benefits of this may include reduced operational cost and carbon emission and improved mobility [1, 2].A DRASS transit system, in which passengers place their travel orders through a mobile app to obtain a door-to-door-type airport shuttle service and many vehicle routes located at different depots are assigned to visit these demand points and transport them to the airport, is an important component of a demand-responsive transit system (DRT) [3]. As with DRT, the increase in consciousness about environmental impact has made green DRASS a critical issue. In this case, DRASS route decisions determine operating cost, vehicle fuel consumption, and carbon emissions [4, 5]. Therefore, green DRASS is different from traditional systems, and a study considering the environmental impact on AFVs route design is timely.The carbon emissions of airport shuttle buses are mainly related to their travel speed and load [6]. Recent research on minimizing emissions in DRASS models can be divided into two main categories. The first is the set of models where vehicle speed is assumed to be constant [1, 2, 7], and the second set includes models where the vehicle speed is time-varying based on different road conditions [5, 8]. Although the first models are not accurate, they are suitable where there is a lack of traffic data. Recently, remote vehicle tracking techniques have been used to collect detailed traffic data on transit times for different roads by time of day and day of the week, which provides the possibility for the second models to accurately estimate carbon emissions. Therefore, it is important to find the optimal relationship between time-varying networks, DRASS route design, and carbon emissions in order to reduce the negative impact on the environment.The main contribution of this paper is to investigate a multiobjective green DRASS with a time-varying network in order to minimize operating cost, vehicle fuel consumption, and CO2 emissions. The main research tasks are summarized as follows: (1) coordination of a DRASS transit routing and departure time guidance process based on a time-varying network to balance path selection and environmental protection; (2) development of a heuristic-based NSGA-II algorithm to efficiently obtain a set of Pareto optimal solutions. Finally, a numerical simulation example in the real world is provided to illustrate the optimization approach.The remainder of this paper is organized as follows: Section2 reviews the related literature concerning green DRASS; Section 3 details the framework of green DRASS with a time-varying network; Section 4 presents a heuristic method based on NSGA-II for resolving MOMILP; a real-world case study is used to demonstrate the applicability of the proposed approach in Section 5; and some conclusions and possible future work are discussed in Section 6.


## 2. Literature

Both DRT and DRASS are extensions of the vehicle routing problem (VRP) and the pick-up and delivery problem (PDP), which aim at assigning all customers in demand points to vehicles located at different bus depots and designing routes to transport them from their home or workplace to destinations [1, 2, 5, 8]. The only difference between them is that DRT strengthens the connectivity between residential areas and rail stations, while DRASS transports air passengers to airports [1, 7]. They have similar objective functions (i.e., operating cost, carbon emissions, and passenger satisfaction) and constraints (i.e., time windows, vehicle capacity, and mileage). Fortunately, these factors normally do not change the properties of the problem, and thus, their models and algorithms are universal [8–11]. Because rail transit is more popular than civil aviation, the amount of research on DRT is greater than that of DRASS.In general, DRT and DRASS often involve customers being picked up within specific time windows, which is related to the customers’ satisfaction level in the airport shuttle service [9]. A variant of vehicle routing with time windows has been studied by researchers and can be divided into hard time windows [3, 4, 7, 9] and soft time windows [12–14]. In the former, time windows cannot be violated, where the vehicles must arrive at the earliest arrival time and leave the customers before the latest departure time. However, a little tardiness is acceptable to a person if they can still catch their trip. To deal with the latter issues pertaining to a small deviation from time windows, an early or late penalty cost is calculated once a predetermined time window is unmet. Obviously, DRT and DRASS with soft time windows can reduce fleet size and improve operating efficiency, compared to that of hard time windows. Most existing studies only allow the vehicle to visit customers in a single period of time. Sometimes, passengers may provide multiple time windows, and a vehicle can arrive at the pick-up locations within one of the specified periods. DRT and DRASS with multiple time windows can reduce the operating cost compared to the single-time window problem [9, 15, 16].Currently, there is an increasing amount of interest in a new variant of DRT and DRASS with time-varying speeds. Due to road traffic congestion depending on the time of day, the speed is not constant. This differs significantly by the hour of the day, by the day of the week, and by the season of the year [5, 17]. Generally speaking, historical data are used to obtain the hypothetical distribution of fuzzy, grey, and random variables [18–20]. However, a piecewise function can describe time-varying speeds more precisely, in the absence of statistics [21]. When vehicle speeds are replaced by traffic volumes, these models are further expanded to time-dependent DRT and DRASS [22, 23]. Also, the vehicle speed may also be used as an additional decision variable in time-dependent models, which is useful in reducing the waiting time for all customers [24, 25]. To avoid the situation where a vehicle with a later departure time arrives before a vehicle with an earlier departure time, these models are constructed based on the first in first out (FIFO) or queuing approach [26].In recent years, another variant of DRT and DRASS has attracted widespread attention regarding the environment. Here, not only the operational cost is considered but also the energy consumption/CO2 emissions. Compared to the traditional problem, this would save energy consumption and CO2 emissions but increase some operating costs. Most research has only focused on energy minimizing [27] or CO2 emission minimizing vehicle routing [28]. Few have investigated an integrated routing, energy consumption, and CO2 emission model [21, 29]. These studies were also extended by taking driver wages into account [21, 29]. Furthermore, this research can be divided into time-independent and time-dependent models: in the former, the energy consumption and CO2 emissions are only related to routes, not schedules; in the latter, carbon emissions also depend on the departure time of the vehicles. Due to the fuel consumption and CO2 emissions of delivery vehicles being closely related to the driving speed, load and road conditions, and other factors, the result of time-dependent models is more accurate and reliable than that of time-independent models [5, 21].As DRT and DRASS belongs to the class of NP-hard problems, two solution methods, i.e., route-building heuristics and evolutionary algorithms, are often used to resolve large-scale problem instances. For route-building heuristics, a set of feasible solution is quickly found, and better solutions can be obtained by further search based on the fine-tuned initial solutions [30–32]. There are two ways to get the initial solution: (1) all customers are grouped into several vehicles, and then, the order in which the vehicles will visit the customers is determined; (2) each route is gradually constructed to visit some customers until the travel demand is met. Some widely used evolutionary algorithms that are often used include the column generation metaheuristic [12], ant colony algorithms [3, 15, 19], Tabu search [12, 16, 17], particle swarm optimization [20], and genetic algorithms [7, 10, 33–35].To the best of our knowledge, the following important issues deserve further investigation:(1)
Most studies have neglected the integrated operation of depot selection, vehicle scheduling, and routing to transport passengers from home to the airport. Since different depots for each vehicle route influences the time the vehicle arrives and leaves the demand point, the ignorance of assigning optimal depots to the vehicle route often results in increasing the operational costs [36, 37].(2)
Few studies have analyzed the impact of time-varying road conditions and soft time windows on AFV scheduling and routing, which leads to a lack of an integrated solution that balances fuel consumption, CO2 emissions, and operating costs [32].(3)
DRASS is an NP-hard problem. Although some methods have been explicitly used to solve the two relevant objectives between operating costs and fuel consumption/CO2 emissions, a heuristic algorithm should be used to efficiently find a set of Pareto solutions to balance all of the three objectives [34, 35].


## 3. Methodology

### 3.1. Research Framework

In the DRASS model, passengers will be transported by several AFVs from their workplaces or home addresses to the airport. The location, maximum expected riding time, preferred pick-up time windows, and number of persons on board for each demand point is easily obtained using the mobile app in advance. If an AFV arrives at the passenger’s location early or late, there will be a penalty charge. Each AFV, initially located at a depot, has its own limited fuel for the duration of the route. The fuel consumption of an AFV is only related to its speed, vehicle load weight, and mileage [6]. It is obvious that the change in traffic volume in different periods determines the time-varying speed of vehicles on the road, and its rules can be depicted by a piecewise function. The main aim of this study is to assign all demand points to several AFVs, route each AFV starting from a selected depot, visit the points and end at the airport, and determine the time this vehicle arrives and leaves each demand point. A MOMILP model for DRASS is presented to simultaneously minimize operational cost, vehicle fuel consumption, and CO2 emissions. The key inputs of the model are the travel information of each demand point, endurance and energy consumption of AFVs, and the real travel speed/distance matrix between these vehicle nodes.To better understand the underlying principles of the DRASS model, a small example consisting of one airport (M), eight demand points (C1–C8), and two depots (D1-D2) is shown in Figure 1. The change curves of the average speeds on different roads are shown in Figure 2. The numbers in brackets around each demand point denotes time windows and maximum expected riding time. The red numbers on top of each demand point denotes the number of passengers to be picked up. The number in-line linking two adjacent demand points is the travel distance. All customers in each demand point spend one minute getting on the bus. There are three generated AFV routes in the optimization process, i.e., (D1 (7 : 20)–C5 (7 : 35, 7 : 36)–C4 (7 : 56, 7 : 57)–M (8 : 12)), (D2 (7 : 15)–C2 (7 : 35, 7 : 36)–C6 (8 : 01, 8 : 02)–M (8 : 17)), and (D2 (7 : 25)–C3 (7 : 40, 7 : 41)–C1 (8 : 01, 8 : 02)–M (8 : 12)). For example, vehicle 3 departs from D2 at 7 : 25. Due to the speed of the vehicle on road section D2–C3 during this period being 20 km/h, this vehicle arrives and leaves at C3 at 7 : 40 and 7 : 41 with a speed of 15 km/h and loads three persons. Obviously, the vehicle does not arrive at the location within the time window and is about five minutes late. Similarly, the arrival and departure time for the vehicle at C1 are (8 : 01, 8 : 02) (nine minutes early), and the vehicle picks up four passengers. Finally, it returns back to M at 8 : 12, and a total of seven passengers are unloaded. In this case, each objective function of all AFV routes can be calculated easily.Figure 1
Graphical representation of the DRASS problem.Figure 2
Vehicle average speed change curve on roads in small example.To deal with real-life situations, this DRASS model will be based on the following assumptions:(1)
All demand points must be visited by AFVs, and each of them can only be covered once by one AFV.(2)
The unit cost of fuel, the unit cost of carbon emissions, and the per-unit-time reward of vehicles arriving at the demand point normally, early, or late can be estimated.(3)
Biggest continue voyage course of each AFV can be predicted using an intelligent car-carried terminal in advance.(4)
The travel distance matrix between these vehicle nodes as well as time-varying speed on the road can be obtained from an Open GIS tool.


### 3.2. Model Formulation

#### 3.2.1. Notation

To facilitate model presentation, all definitions and notations used hereafter are summarized in Table1.Table 1
Parameters and variables in the mathematical model.
Indicesi,jVehicular node (demand point, depot, and airport) indexkAFV index0Airport indexSetsISet of demand pointsKSet of AFVsDSet of depotsParametersβThe boarding time per passengerγThe average weight of each personai,liPick-up time window of demand pointi; ∀i∈ILtiThe maximum expected ride time of the demand pointi; ∀i∈IpiNumber of persons to be picked up at demand pointi; ∀i∈ITiPick-up time of the demand pointi, i.e., Ti=pi⋅β; ∀i∈IQkMaximum capacity of the AFVDmaxkBiggest continue voyage course of each AFVk; ∀k∈KTminMinimum total travel time of the AFV routedijTravel distance between the vehicular nodei and j; ∀i,j∈I∪D∪0vijtikThe piecewise function of travel speed between the vehicular nodei and j, related to the time of the AFV k visiting demand point i; ∀k∈K∀i,j∈I∪D∪0t0kThe time of the AFVk arriving the airport;∀k∈KwkThe weight of the AFVk;∀k∈KckFixed use cost of the AFVk;∀k∈KcePenalty fee for early arrivalclPenalty fee for late arrivalcfUnit cost of the fuelcpUnit CO2 emission costfpCO2 emission factorHA very large fixed valueDecision variablesxijkWhether the vehicular nodei precedes vehicular node j on the AFV k or not; ∀k∈K∀i,j∈I∪D∪0yikWhether the vehicular nodei is visited by the AFV k or not; ∀k∈K∀i∈I∪D∪0tikThe time of the AFVk arriving at demand point i; ∀k∈K∀i∈IqikNumber of passengers at demand pointi assigned to the AFV k; ∀k∈K∀i∈IUikAn auxiliary (real) variable for subtour elimination constraint in the AFVk; ∀k∈K


#### 3.2.2. Formulation

The proposed problem can be formulated as the following mixed integer program (MIP), which requires minimization:(1)minf1=∑∀i∈I∑∀k∈Kyik⋅pi⋅ce⋅maxai−tik,0+cl⋅maxtik−li,0,(2)minf2=∑∀i∈I∑∀k∈Kxi0k⋅ck+cf⋅∑∀i,j∈I∪D∪0∑∀k∈Kxijk⋅Fwk+qik,vijtik,dij,(3)minf3=cp⋅fp⋅∑∀i,j∈I∪D∪0∑∀k∈Kxijk⋅Fwk+qik,vijtik,dij,which is subject to(4)∑∀i∈Iyik≥1,∀k∈K,(5)∑∀i∈Dyik=1,∀k∈K,(6)∑∀k∈Kyik=1,∀i∈I,(7)∑∀j∈Ixjik=0,∀k∈K,∀i∈D,(8)∑∀j∈Ixijk≤yik,∀k∈K,∀i∈D,(9)∑∀i∈Ix0ik=0,∀k∈K,(10)∑∀i∈Ixi0k=1,∀k∈K,(11)∑∀j∈I∪0xijk=∑∀j∈I∪Dxjik=yik,∀k∈K,∀i∈I,(12)Uik−Ujk+I∪D∪M⋅xijk≥I∪D∪M−1,∀k∈K,∀i∈I∪D∪0,(13)tik+Ti+dijvijtik−1−xijk⋅H≤tjk,∀k∈K,∀i∈I∪D∪0,(14)tik+Ti+dijvijtik+1−xijk⋅H≥tjk,∀k∈K,∀i∈I∪D∪0,(15)t0k−tik≤Lti,∀k∈K,∀i∈I,(16)qik+pi−1−xijk⋅H≤qjk,∀k∈K,∀i∈I∪D∪0,(17)qik+pi+1−xijk⋅H≥qjk,∀k∈K,∀i∈I∪D∪0,(18)qik≤Qk,∀k∈K,∀i∈I,(19)∑∀i,j∈I∪D∪0xijkdij≤Dmaxk,∀k∈K,(20)∑∀i,j∈I∪D∪0xijktij≥Tmin,∀k∈K,where Fwk+qik,vijtik,dij is a function used to calculate the fuel consumption of vehicles passing through a given arci,j when considering time-varying speeds. The speed vijtik is a piecewise function.vijtik and its value depend on tik. wk+qik denotes the total weight, including the vehicle weight wk and the load weight for the vehicle leaving the demand point i. Using the formulation proposed by Demir et al. [6, 34, 35, 38], this can be expressed as follows:(21)Fwk+qik,vijtik,dij=0.0308dij33vijtik+0.8175+0.2725wk+qik⋅γ+0.0035vijtik2.In this formulation, the objective function (1) aims at minimizing the penalty cost of time-window violation. The objective functions (2) and (3) simultaneously aim at minimizing the operating cost, including the fixed cost and cost of fuel consumption and cost of CO2 emissions. Constraint (4) guarantees that each AFV visits at least one demand point. Constraint (5) is used to assign one depot to each AFV. Constraint (6) guarantees that all demand points are visited by AFVs. Constraints (7) and (8) guarantee that each AFV starts at the selected bus depot. Constraints (9) and (10) guarantee that each AFV eventually ends at the airport. Constraint (11) sets all demand points (except the airport and bus depot) being served by each AFV to have the same incoming and outgoing arcs. Constraint (12) is used for the subtour elimination in the vehicle routing. Constraints (13) and (14) are used for calculating the time for each AFV passing through adjacent vehicular points i and j. Constraint (15) guarantees that the riding time of each demand point must be less than the expected value. Constraints (16) and (17) are used for calculating the load weight for each AFV passing through adjacent vehicular points i and j. Constraint (18) guarantees that the number of passengers in each AFV must be less than the vehicle capacity. Constraint (19) guarantees that the total mileage of each AFV should not exceed its maximum range. Constraint (20) guarantees that the travel time of each AFV must meet its lower limits.


## 3.1. Research Framework

In the DRASS model, passengers will be transported by several AFVs from their workplaces or home addresses to the airport. The location, maximum expected riding time, preferred pick-up time windows, and number of persons on board for each demand point is easily obtained using the mobile app in advance. If an AFV arrives at the passenger’s location early or late, there will be a penalty charge. Each AFV, initially located at a depot, has its own limited fuel for the duration of the route. The fuel consumption of an AFV is only related to its speed, vehicle load weight, and mileage [6]. It is obvious that the change in traffic volume in different periods determines the time-varying speed of vehicles on the road, and its rules can be depicted by a piecewise function. The main aim of this study is to assign all demand points to several AFVs, route each AFV starting from a selected depot, visit the points and end at the airport, and determine the time this vehicle arrives and leaves each demand point. A MOMILP model for DRASS is presented to simultaneously minimize operational cost, vehicle fuel consumption, and CO2 emissions. The key inputs of the model are the travel information of each demand point, endurance and energy consumption of AFVs, and the real travel speed/distance matrix between these vehicle nodes.To better understand the underlying principles of the DRASS model, a small example consisting of one airport (M), eight demand points (C1–C8), and two depots (D1-D2) is shown in Figure 1. The change curves of the average speeds on different roads are shown in Figure 2. The numbers in brackets around each demand point denotes time windows and maximum expected riding time. The red numbers on top of each demand point denotes the number of passengers to be picked up. The number in-line linking two adjacent demand points is the travel distance. All customers in each demand point spend one minute getting on the bus. There are three generated AFV routes in the optimization process, i.e., (D1 (7 : 20)–C5 (7 : 35, 7 : 36)–C4 (7 : 56, 7 : 57)–M (8 : 12)), (D2 (7 : 15)–C2 (7 : 35, 7 : 36)–C6 (8 : 01, 8 : 02)–M (8 : 17)), and (D2 (7 : 25)–C3 (7 : 40, 7 : 41)–C1 (8 : 01, 8 : 02)–M (8 : 12)). For example, vehicle 3 departs from D2 at 7 : 25. Due to the speed of the vehicle on road section D2–C3 during this period being 20 km/h, this vehicle arrives and leaves at C3 at 7 : 40 and 7 : 41 with a speed of 15 km/h and loads three persons. Obviously, the vehicle does not arrive at the location within the time window and is about five minutes late. Similarly, the arrival and departure time for the vehicle at C1 are (8 : 01, 8 : 02) (nine minutes early), and the vehicle picks up four passengers. Finally, it returns back to M at 8 : 12, and a total of seven passengers are unloaded. In this case, each objective function of all AFV routes can be calculated easily.Figure 1
Graphical representation of the DRASS problem.Figure 2
Vehicle average speed change curve on roads in small example.To deal with real-life situations, this DRASS model will be based on the following assumptions:(1)
All demand points must be visited by AFVs, and each of them can only be covered once by one AFV.(2)
The unit cost of fuel, the unit cost of carbon emissions, and the per-unit-time reward of vehicles arriving at the demand point normally, early, or late can be estimated.(3)
Biggest continue voyage course of each AFV can be predicted using an intelligent car-carried terminal in advance.(4)
The travel distance matrix between these vehicle nodes as well as time-varying speed on the road can be obtained from an Open GIS tool.


## 3.2. Model Formulation

### 3.2.1. Notation

To facilitate model presentation, all definitions and notations used hereafter are summarized in Table1.Table 1
Parameters and variables in the mathematical model.
Indicesi,jVehicular node (demand point, depot, and airport) indexkAFV index0Airport indexSetsISet of demand pointsKSet of AFVsDSet of depotsParametersβThe boarding time per passengerγThe average weight of each personai,liPick-up time window of demand pointi; ∀i∈ILtiThe maximum expected ride time of the demand pointi; ∀i∈IpiNumber of persons to be picked up at demand pointi; ∀i∈ITiPick-up time of the demand pointi, i.e., Ti=pi⋅β; ∀i∈IQkMaximum capacity of the AFVDmaxkBiggest continue voyage course of each AFVk; ∀k∈KTminMinimum total travel time of the AFV routedijTravel distance between the vehicular nodei and j; ∀i,j∈I∪D∪0vijtikThe piecewise function of travel speed between the vehicular nodei and j, related to the time of the AFV k visiting demand point i; ∀k∈K∀i,j∈I∪D∪0t0kThe time of the AFVk arriving the airport;∀k∈KwkThe weight of the AFVk;∀k∈KckFixed use cost of the AFVk;∀k∈KcePenalty fee for early arrivalclPenalty fee for late arrivalcfUnit cost of the fuelcpUnit CO2 emission costfpCO2 emission factorHA very large fixed valueDecision variablesxijkWhether the vehicular nodei precedes vehicular node j on the AFV k or not; ∀k∈K∀i,j∈I∪D∪0yikWhether the vehicular nodei is visited by the AFV k or not; ∀k∈K∀i∈I∪D∪0tikThe time of the AFVk arriving at demand point i; ∀k∈K∀i∈IqikNumber of passengers at demand pointi assigned to the AFV k; ∀k∈K∀i∈IUikAn auxiliary (real) variable for subtour elimination constraint in the AFVk; ∀k∈K


### 3.2.2. Formulation

The proposed problem can be formulated as the following mixed integer program (MIP), which requires minimization:(1)minf1=∑∀i∈I∑∀k∈Kyik⋅pi⋅ce⋅maxai−tik,0+cl⋅maxtik−li,0,(2)minf2=∑∀i∈I∑∀k∈Kxi0k⋅ck+cf⋅∑∀i,j∈I∪D∪0∑∀k∈Kxijk⋅Fwk+qik,vijtik,dij,(3)minf3=cp⋅fp⋅∑∀i,j∈I∪D∪0∑∀k∈Kxijk⋅Fwk+qik,vijtik,dij,which is subject to(4)∑∀i∈Iyik≥1,∀k∈K,(5)∑∀i∈Dyik=1,∀k∈K,(6)∑∀k∈Kyik=1,∀i∈I,(7)∑∀j∈Ixjik=0,∀k∈K,∀i∈D,(8)∑∀j∈Ixijk≤yik,∀k∈K,∀i∈D,(9)∑∀i∈Ix0ik=0,∀k∈K,(10)∑∀i∈Ixi0k=1,∀k∈K,(11)∑∀j∈I∪0xijk=∑∀j∈I∪Dxjik=yik,∀k∈K,∀i∈I,(12)Uik−Ujk+I∪D∪M⋅xijk≥I∪D∪M−1,∀k∈K,∀i∈I∪D∪0,(13)tik+Ti+dijvijtik−1−xijk⋅H≤tjk,∀k∈K,∀i∈I∪D∪0,(14)tik+Ti+dijvijtik+1−xijk⋅H≥tjk,∀k∈K,∀i∈I∪D∪0,(15)t0k−tik≤Lti,∀k∈K,∀i∈I,(16)qik+pi−1−xijk⋅H≤qjk,∀k∈K,∀i∈I∪D∪0,(17)qik+pi+1−xijk⋅H≥qjk,∀k∈K,∀i∈I∪D∪0,(18)qik≤Qk,∀k∈K,∀i∈I,(19)∑∀i,j∈I∪D∪0xijkdij≤Dmaxk,∀k∈K,(20)∑∀i,j∈I∪D∪0xijktij≥Tmin,∀k∈K,where Fwk+qik,vijtik,dij is a function used to calculate the fuel consumption of vehicles passing through a given arci,j when considering time-varying speeds. The speed vijtik is a piecewise function.vijtik and its value depend on tik. wk+qik denotes the total weight, including the vehicle weight wk and the load weight for the vehicle leaving the demand point i. Using the formulation proposed by Demir et al. [6, 34, 35, 38], this can be expressed as follows:(21)Fwk+qik,vijtik,dij=0.0308dij33vijtik+0.8175+0.2725wk+qik⋅γ+0.0035vijtik2.In this formulation, the objective function (1) aims at minimizing the penalty cost of time-window violation. The objective functions (2) and (3) simultaneously aim at minimizing the operating cost, including the fixed cost and cost of fuel consumption and cost of CO2 emissions. Constraint (4) guarantees that each AFV visits at least one demand point. Constraint (5) is used to assign one depot to each AFV. Constraint (6) guarantees that all demand points are visited by AFVs. Constraints (7) and (8) guarantee that each AFV starts at the selected bus depot. Constraints (9) and (10) guarantee that each AFV eventually ends at the airport. Constraint (11) sets all demand points (except the airport and bus depot) being served by each AFV to have the same incoming and outgoing arcs. Constraint (12) is used for the subtour elimination in the vehicle routing. Constraints (13) and (14) are used for calculating the time for each AFV passing through adjacent vehicular points i and j. Constraint (15) guarantees that the riding time of each demand point must be less than the expected value. Constraints (16) and (17) are used for calculating the load weight for each AFV passing through adjacent vehicular points i and j. Constraint (18) guarantees that the number of passengers in each AFV must be less than the vehicle capacity. Constraint (19) guarantees that the total mileage of each AFV should not exceed its maximum range. Constraint (20) guarantees that the travel time of each AFV must meet its lower limits.


## 3.2.1. Notation

To facilitate model presentation, all definitions and notations used hereafter are summarized in Table1.Table 1
Parameters and variables in the mathematical model.
Indicesi,jVehicular node (demand point, depot, and airport) indexkAFV index0Airport indexSetsISet of demand pointsKSet of AFVsDSet of depotsParametersβThe boarding time per passengerγThe average weight of each personai,liPick-up time window of demand pointi; ∀i∈ILtiThe maximum expected ride time of the demand pointi; ∀i∈IpiNumber of persons to be picked up at demand pointi; ∀i∈ITiPick-up time of the demand pointi, i.e., Ti=pi⋅β; ∀i∈IQkMaximum capacity of the AFVDmaxkBiggest continue voyage course of each AFVk; ∀k∈KTminMinimum total travel time of the AFV routedijTravel distance between the vehicular nodei and j; ∀i,j∈I∪D∪0vijtikThe piecewise function of travel speed between the vehicular nodei and j, related to the time of the AFV k visiting demand point i; ∀k∈K∀i,j∈I∪D∪0t0kThe time of the AFVk arriving the airport;∀k∈KwkThe weight of the AFVk;∀k∈KckFixed use cost of the AFVk;∀k∈KcePenalty fee for early arrivalclPenalty fee for late arrivalcfUnit cost of the fuelcpUnit CO2 emission costfpCO2 emission factorHA very large fixed valueDecision variablesxijkWhether the vehicular nodei precedes vehicular node j on the AFV k or not; ∀k∈K∀i,j∈I∪D∪0yikWhether the vehicular nodei is visited by the AFV k or not; ∀k∈K∀i∈I∪D∪0tikThe time of the AFVk arriving at demand point i; ∀k∈K∀i∈IqikNumber of passengers at demand pointi assigned to the AFV k; ∀k∈K∀i∈IUikAn auxiliary (real) variable for subtour elimination constraint in the AFVk; ∀k∈K


## 3.2.2. Formulation

The proposed problem can be formulated as the following mixed integer program (MIP), which requires minimization:(1)minf1=∑∀i∈I∑∀k∈Kyik⋅pi⋅ce⋅maxai−tik,0+cl⋅maxtik−li,0,(2)minf2=∑∀i∈I∑∀k∈Kxi0k⋅ck+cf⋅∑∀i,j∈I∪D∪0∑∀k∈Kxijk⋅Fwk+qik,vijtik,dij,(3)minf3=cp⋅fp⋅∑∀i,j∈I∪D∪0∑∀k∈Kxijk⋅Fwk+qik,vijtik,dij,which is subject to(4)∑∀i∈Iyik≥1,∀k∈K,(5)∑∀i∈Dyik=1,∀k∈K,(6)∑∀k∈Kyik=1,∀i∈I,(7)∑∀j∈Ixjik=0,∀k∈K,∀i∈D,(8)∑∀j∈Ixijk≤yik,∀k∈K,∀i∈D,(9)∑∀i∈Ix0ik=0,∀k∈K,(10)∑∀i∈Ixi0k=1,∀k∈K,(11)∑∀j∈I∪0xijk=∑∀j∈I∪Dxjik=yik,∀k∈K,∀i∈I,(12)Uik−Ujk+I∪D∪M⋅xijk≥I∪D∪M−1,∀k∈K,∀i∈I∪D∪0,(13)tik+Ti+dijvijtik−1−xijk⋅H≤tjk,∀k∈K,∀i∈I∪D∪0,(14)tik+Ti+dijvijtik+1−xijk⋅H≥tjk,∀k∈K,∀i∈I∪D∪0,(15)t0k−tik≤Lti,∀k∈K,∀i∈I,(16)qik+pi−1−xijk⋅H≤qjk,∀k∈K,∀i∈I∪D∪0,(17)qik+pi+1−xijk⋅H≥qjk,∀k∈K,∀i∈I∪D∪0,(18)qik≤Qk,∀k∈K,∀i∈I,(19)∑∀i,j∈I∪D∪0xijkdij≤Dmaxk,∀k∈K,(20)∑∀i,j∈I∪D∪0xijktij≥Tmin,∀k∈K,where Fwk+qik,vijtik,dij is a function used to calculate the fuel consumption of vehicles passing through a given arci,j when considering time-varying speeds. The speed vijtik is a piecewise function.vijtik and its value depend on tik. wk+qik denotes the total weight, including the vehicle weight wk and the load weight for the vehicle leaving the demand point i. Using the formulation proposed by Demir et al. [6, 34, 35, 38], this can be expressed as follows:(21)Fwk+qik,vijtik,dij=0.0308dij33vijtik+0.8175+0.2725wk+qik⋅γ+0.0035vijtik2.In this formulation, the objective function (1) aims at minimizing the penalty cost of time-window violation. The objective functions (2) and (3) simultaneously aim at minimizing the operating cost, including the fixed cost and cost of fuel consumption and cost of CO2 emissions. Constraint (4) guarantees that each AFV visits at least one demand point. Constraint (5) is used to assign one depot to each AFV. Constraint (6) guarantees that all demand points are visited by AFVs. Constraints (7) and (8) guarantee that each AFV starts at the selected bus depot. Constraints (9) and (10) guarantee that each AFV eventually ends at the airport. Constraint (11) sets all demand points (except the airport and bus depot) being served by each AFV to have the same incoming and outgoing arcs. Constraint (12) is used for the subtour elimination in the vehicle routing. Constraints (13) and (14) are used for calculating the time for each AFV passing through adjacent vehicular points i and j. Constraint (15) guarantees that the riding time of each demand point must be less than the expected value. Constraints (16) and (17) are used for calculating the load weight for each AFV passing through adjacent vehicular points i and j. Constraint (18) guarantees that the number of passengers in each AFV must be less than the vehicle capacity. Constraint (19) guarantees that the total mileage of each AFV should not exceed its maximum range. Constraint (20) guarantees that the travel time of each AFV must meet its lower limits.


## 4. Heuristic-Based NSGA-II to Resolve Green DRASS

In this study, three possibly conflicting objectives require optimization. To avoid the disadvantages of the weighted sum approach to set weights to characterize the decision-makers preferences, NSGA-II is used to find a set of Pareto optimal solutions. As mentioned above, our model involves three core variables, includingyik,xijk, and tik，where yik decides xijk. Obviously, once several demand points and one depot can be assigned to an AFV (i.e., yik), its route (i.e., xijk) is also easily obtained according to the shortest distance principle. Hence, a two-stage NSGA-II-based heuristic approach is developed to solve this problem [39–41]. In the first stage, NSGA-II is used to determine the assignment of demand points and depots to different AFVs as well as departure time of each AFV. In the second stage, the A∗ algorithm is embedded in NSGA-II to construct the route of each AFV: leaving the depot, visiting the selected demand points, and returning to the airport. Through these two operations, the speed, weight, and time for an AFV arriving and leaving the location of demand points in the objective function are also determined.


### 4.1. NSGA-II in the First Stage

A three-dimensional vectorU=U1,U2,U3 represents the chromosome of a feasible solution in green DRASS, where each element ui in U1=u1,u2,…,uI, being a natural number in 1, 2, ... ,K, denotes an AFV ui visiting demand point ii=1,2,…,I. Each element ui in U2=uI+1,u2,…,uI+K, being a real number, denotes the departure time of the AFV kk=1,2,…,K. Each element ui in U3=uI+K+1,u2,…,uI+2K, being a natural number in 1, 2, ..., D, denotes the departure depot of the AFV kk=1,2,…,K. For example, a chromosome vector U  = {1 1 2 2 1 2 6 : 00 6 : 10 3 4 } of two AFVs, four depots, and six demand points can be understood as follows: vehicle 1 leaves depot 3 at 6 : 00 and visits demand points 1, 2, and 5; vehicle 2 leaves depot 4 at 6 : 10 and visits demand points 3, 4, and 6.Figure3 describes the optimization procedure of NSGA-II. An initial population consisting of individuals is randomly generated. At each iteration, each individual is firstly decoded as an assignment of demand points and depots to vehicles as well as the determination of departure time for the vehicle, and the A∗ algorithm is used to search for the shortest distance route of each vehicle. After this, all objective functions are calculated for fitness evaluation. The selected individuals in the parent population exchange genes to generate new individuals by using crossover and mutation operators. The current population with older and new individuals is sorted and selected again based on nondomination to obtain offspring. The selection depends on rank and crowding distance for an individual. The crowding distance, related to averaging the distances between individuals in a front, is used to find a consistent spread of solutions along the Pareto front. If the solutions are in the same nondominated front, those with a higher crowding distance are chosen first; otherwise, those with the lowest rank are chosen first. The algorithm continues until the maximum number of iterations is reached.Figure 3
Flow chart of the NSGA-II-based two-stage algorithm.


### 4.2.A∗ Algorithm in the Second Stage

In the first stage, all demand points, the depots, and the airport are assigned to different AFVs. Based on the output of the first stage algorithm, a route for each AFV would be found based on the shortest distance principle. TheA∗ algorithm is one of the most efficient algorithms for finding the shortest path [42]. The detailed process for this algorithm in solving the problem is given as follows:(i)
Step 1: define three sets,close_list, open_list, and parent_node, where close_list and open_list are used to record visited and unvisited demand points and parent_node is used to record the route.(ii)
Step 2: put the depot intoopen_list and set lose_list=∅ and parent_node=∅.(iii)
Step 3: inopen_list, select a demand point with the minimum travel distance as the current node. Remove the current node fromopen_list, and put it into close_list.(iv)
Step 4: if the current node is the airport, the search ends; otherwise, search the adjacent nodes of the current node. Put these adjacent nodes intoopen_list, and the current node is set as a node in parent_node.(v)
Step 5: if the current node is inopen_list, its total travel distance is recalculated and updated when the result is less than the previous one; parent_node is also updated. If the current node is in close_list, go to step 3.


## 4.1. NSGA-II in the First Stage

A three-dimensional vectorU=U1,U2,U3 represents the chromosome of a feasible solution in green DRASS, where each element ui in U1=u1,u2,…,uI, being a natural number in 1, 2, ... ,K, denotes an AFV ui visiting demand point ii=1,2,…,I. Each element ui in U2=uI+1,u2,…,uI+K, being a real number, denotes the departure time of the AFV kk=1,2,…,K. Each element ui in U3=uI+K+1,u2,…,uI+2K, being a natural number in 1, 2, ..., D, denotes the departure depot of the AFV kk=1,2,…,K. For example, a chromosome vector U  = {1 1 2 2 1 2 6 : 00 6 : 10 3 4 } of two AFVs, four depots, and six demand points can be understood as follows: vehicle 1 leaves depot 3 at 6 : 00 and visits demand points 1, 2, and 5; vehicle 2 leaves depot 4 at 6 : 10 and visits demand points 3, 4, and 6.Figure3 describes the optimization procedure of NSGA-II. An initial population consisting of individuals is randomly generated. At each iteration, each individual is firstly decoded as an assignment of demand points and depots to vehicles as well as the determination of departure time for the vehicle, and the A∗ algorithm is used to search for the shortest distance route of each vehicle. After this, all objective functions are calculated for fitness evaluation. The selected individuals in the parent population exchange genes to generate new individuals by using crossover and mutation operators. The current population with older and new individuals is sorted and selected again based on nondomination to obtain offspring. The selection depends on rank and crowding distance for an individual. The crowding distance, related to averaging the distances between individuals in a front, is used to find a consistent spread of solutions along the Pareto front. If the solutions are in the same nondominated front, those with a higher crowding distance are chosen first; otherwise, those with the lowest rank are chosen first. The algorithm continues until the maximum number of iterations is reached.Figure 3
Flow chart of the NSGA-II-based two-stage algorithm.


## 4.2.A∗ Algorithm in the Second Stage

In the first stage, all demand points, the depots, and the airport are assigned to different AFVs. Based on the output of the first stage algorithm, a route for each AFV would be found based on the shortest distance principle. TheA∗ algorithm is one of the most efficient algorithms for finding the shortest path [42]. The detailed process for this algorithm in solving the problem is given as follows:(i)
Step 1: define three sets,close_list, open_list, and parent_node, where close_list and open_list are used to record visited and unvisited demand points and parent_node is used to record the route.(ii)
Step 2: put the depot intoopen_list and set lose_list=∅ and parent_node=∅.(iii)
Step 3: inopen_list, select a demand point with the minimum travel distance as the current node. Remove the current node fromopen_list, and put it into close_list.(iv)
Step 4: if the current node is the airport, the search ends; otherwise, search the adjacent nodes of the current node. Put these adjacent nodes intoopen_list, and the current node is set as a node in parent_node.(v)
Step 5: if the current node is inopen_list, its total travel distance is recalculated and updated when the result is less than the previous one; parent_node is also updated. If the current node is in close_list, go to step 3.


## 5. Numerical Example

### 5.1. Example Description

In this section, a case study of designing green DRASS for Nantong City in China is given to demonstrate the applicability of the proposed model. There is one airport (M), five depot centers (D1–D5), and 33 demand points (P1–P33). Figure 4 is used to map the spatial distribution of these vehicular nodes, in which time-varying speeds on the road are obtained from a Baidu Open GIS tool using http://api.map.baidu.com. Moreover, the number of passengers and their preferred time windows and expected ride time in demand points are shown in Table 2. The parameters of NSGA-II are given in [34]. The proposed algorithm is run on Matlab 2017 B using a Dell Inspiron N5040 laptop with Core i3 processor and 4 GB memory. The key parameters used in the case study are as follows:(i)
Number of AFVs:6.(ii)
Maximum capacity of each AFV:Qk = 12 per.(iii)
Biggest continue voyage course of each AFV:Dmaxk = 100 km.(iv)
Weight of each AFV:wk = 2300 kg.(v)
Fixed use cost of each AFV:ck = 120 CNY.(vi)
Minimum travel time of vehicle route:Tmin = 3 min.(vii)
Boarding time of per passenger:β = 0.5 min.(viii)
Average weight of each person:γ = 60 kg.(ix)
Penalty fee for early arrival:ce = 1 CNY/min.(x)
Penalty fee for late arrival:cl = 3 CNY/min.(xi)
Unit cost of the fuel:cf = 7.59 CNY/liter.(xii)
Unit CO2 emission cost: cp = 80 CNY/ton.(xiii)
CO2 emission factor: fp = 0.785 kg/liter.Figure 4
Spatial distribution of vehicles visiting points in Nantong City in China.Table 2
Basic information of demand points.
No.ai,lipiLtihNo.ai,lipiLtihNo.ai,lipiLtihP18 : 30–8 : 4022.5P127 : 30–8 : 0014P238 : 10–8 : 3023.5P28 : 20–8 : 3012.5P136 : 20–6 : 4022.5P248 : 00–8 : 3023P38 : 00–8 : 1022.5P146 : 20–6 : 5022P257 : 10–7 : 3021P46 : 40–7 : 1024P156 : 20–6 : 4022P267 : 40–7 : 5020.5P510 : 00–10 : 1021.5P166 : 40–7 : 0022P276 : 40–7 : 1015P68 : 00–8 : 2021P178 : 00–8 : 3013.5P2810 : 00–10 : 1021P76 : 40–7 : 1011.5P186 : 30–7 : 0022.5P297 : 50–8 : 0021.5P86 : 40–7 : 1021.5P197 : 00–7 : 1022.5P307 : 50–8 : 1021P96 : 10–6 : 3022.5P206 : 50–7 : 1024.5P316 : 40–7 : 1015P107 : 40–8 : 0021.5P216 : 30–7 : 0022P328 : 00–8 : 2011P116 : 30–7 : 0024.5P228 : 00–8 : 2013.5P338 : 00–8 : 1020.5


### 5.2. Results

The CPU time for finding a set of Pareto optimal solutions is usually less than 1 minute. As explained previously, the proposed model could yield 10 feasible metaoptimal solutions in three dimensions, including the assignment of each demand point to an AFV, its route, and timetable. The upper and lower bounds of objective function 1 are 1305.8 RMB and 693.7 RMB, that of objective function 2 are 1187.2 RMB and 1156.7 RMB, and that of objective function 3 are 3.9 RMB and 3.7 RMB, respectively. Figures5 and 6 reveal the changing relationship between any two goals. As the value of objective function 1 becomes larger, that of objective function 2 becomes smaller. This is because the reduction in the total penalty charges for violating the passenger’s time window leads to the need for more mileage for vehicles covering all demand points, thus increasing energy consumption costs. Objective 2 and objective 3 are positively linearly correlated, which determines that the change in trend of objective 1 and objective 2 is consistent with the change in trend of objective 1 and objective 3. This is because energy consumption determines carbon emissions.Figure 5
Negative nonlinear relationship between objective 1 and objective 2.Figure 6
Positive linear relationship between objective 2 and objective 3.Tables3 and 4 are used to provide the routing and scheduling results related to the metaoptimal solution (693.7, 1187.2, 3.9). The pick-up time, riding time, and early/late arrival time of the AFV at each pick-up location are detailed in Table 3, in which zero, positive, and negative numbers in the fourth column of the table represent normal, early, and late arrival, respectively. The arrival and departure time for all AFVs visiting their demand points as well as fuel consumption and CO2 emissions of each AFV are detailed in Table 4. Taking the AFV of V1 as an example, the vehicle leaves the depot D5 at 06 : 28 and arrives at the demand point P29 at 7 : 36. Since the client’s time window is (7 : 50, 8 : 00), the early arrival time is 13.9 minutes. After 1 minute to pick up 2 persons, it leaves this location at 7 : 37. Similarly, the arrival and departure time of P30 and P33 are (7 : 53, 7 : 54) and (8 : 07, 8 : 08), and their early or late arrival times are 0 minutes and 0 minutes. Finally, this vehicle reaches its airport of M at 8 : 37 to unload 6 persons. As above mentioned, the riding times of P29, P30, and P33 for V4 are calculated as 61.1 minutes, 44.2 minutes, and 29.6 minutes. The vehicle travels a total of 52.6 km, consuming 9 liters of petrol and emitting 7.1 kg of CO2. The costs in terms of energy consumption and carbon emissions are 68.3 CNY and 0.5 CNY, and the penalty for violating the time window is 27.8 CNY.Table 3
Assignment results of passengers picked up by each AFV.
No.Pick-up time (min)Ride time (min)Early/late time (min)VehicleP8178.80V1P70.568.3−4.2P25138.2−14.3P26120.4−12.1P181138.40V2P191131.815.0P211110.1−6.7P10162.30P6148.10P270.5287.50V3P311265.7−14.7P201243.2−17.2P120.5232.40P221204.50P231195.60P241187.60P5183.80P29161.113.9V4P30144.20P33129.60P111253.30V5P41234.5−7.7P170.5207.535.3P31148.3−14P20.5141.3−1P11134.30P28143.60P91135.10V6P131122.10P141116.90P1611120P151100.2−17.5P32141.94.3—————Table 4
Routing and scheduling plan of each AFV.
VehicleSequence of demand points visited by each AFVMileage (km)Fuel consumption (liter)CO2 emissions (kg)Number of passengersV1D4 (6 : 45)–P8 (7 : 03–7:04)–P7 (7 : 14, 7 : 14)–P25 (7 : 44, 7 : 45)–P26 (8 : 02, 8 : 03)–M (8 : 22)48.49.17.17V2D3 (6 : 35)–P18 (6 : 38, 6 : 39)–P19 (6 : 44, 6 : 45)–P21 (7 : 06, 7 : 07)–P10 (7 : 54, 7 : 55)–P6 (8 : 08, 8 : 09)– M (9 : 56)44.46.85.310V3D1 (6 : 36)–P27 (6 : 42, 6 : 43)–P31 (7 : 04, 7 : 05)–P20 (7 : 27, 7 : 28)–P12 (7 : 37, 7 : 38)–P22 (8 : 05, 8 : 06)–P23 (8 : 14, 8 : 15)– P24 (8 : 22, 8 : 23)– P5 (10 : 06, 10 : 07)–M (11 : 30)94.515.011.812V4D5 (6 : 28)–P29 (7 : 36, 7 : 37)–P30 (7 : 53, 7 : 54)–P33 (8 : 07, 8 : 08)–M (8 : 37)52.69.07.16V5D4 (6 : 21)–P11 (6 : 39, 6 : 40)–P4 (6 : 57, 6 : 58)–P17 (7 : 24, 7 : 25)–P3 (8 : 24, 8 : 25)–P2 (8 : 31, 8 : 31)– P1 (8 : 37, 8 : 38)–P28 (10 : 08, 10 : 09)–M (10 : 52)90.514.211.112V6D4 (6 : 17)–P9 (8 : 22, 8 : 23)–P13 (6 : 35, 6 : 36)–P14 (6 : 40, 6 : 41)–P16 (6 : 45, 6 : 46)–P15 (6 : 57, 6 : 58)–P32 (7 : 55, 7 : 56)–M (8 : 37)47.47.25.811Furthermore, the proposed model has unique features compared to traditional DRASS with fixed speed. As shown in Figure7, mileage of the proposed model is 0.36% more than for the traditional one, but the carbon emissions and fuel consumption of the proposed model are 0.87% and 0.66% less than those of the traditional one. In traditional DRASS with fixed speed, the more the mileage, the more the carbon emissions and fuel consumption. However, the flexible departure time of each AFV in time-varying traffic conditions can avoid vehicles driving on congested roads, thus increasing energy consumption costs.Figure 7
Comparison of the results between proposed and traditional model.


### 5.3. Comparative Analysis and Parameter Sensitivity

In this section, sensitivity analyses are also given to investigate the impact of the number of AFVs and the changes in weight coefficientcl/ce on the model performance. Comparison of the results is shown in Tables 5 and 6, from which the following holds:(1)
As the weight coefficient gradually increases, early arrival time will be increased while late arrival time will be reduced. Besides, total mileage, fuel consumption, and CO2 emissions remain the same, except for the boundary conditions being met. When it happens, DRASS plan with an increase in mileage would lead to more fuel consumption and CO2 emissions. This is because increased weight coefficient cl/ce may cause an increase in early arrival time and a reduction in late arrival time, which leads to more mileage.Table 5
Comparison of the results of different weight coefficientscl/ce
ScenarioMileage (km)Fuel consumption (liter)CO2 emissions (kg)Early arrival time (min)Late arrival time (min)1 : 3377.861.548.368.4119.32 : 337460.047.177.1111.33 : 337460.047.177.1109.34 : 3366.159.246.586.078.0(2)
As the number of AFVs increases, total mileages slightly increase. This can be attributed to an increase in invalid mileage from vehicles starting from the depot and ending at the airport. Similarly, a reduced number of demand points visited by those AFVs may causes vehicles to reach the pick-up locations faster, thus increasing total early and late arrival time. When mileage of two DRASS plans varies widely, DRASS plan with greater mileage means more energy consumption and emissions. However, DRASS plan with small mileage in congested road conditions may consume more energy and emit more emissions, as the mileage difference in them is small.Table 6
Comparison of the results of different numbers of AFVs.
ScenarioMileage (km)Fuel consumption (liter)CO2 emissions (kg)Early and late arrival time (min)6 AFVs353.457.545.2363.47 AFVs444.774.358.3891.18 AFVs45173.857.91000.6


### 5.4. Validation of Algorithm

In order to verify the validity of proposed algorithm, the multiobjective DRASS could be transformed into a single objective function with minimization of the weighted sum of two objective functions (1), (2), and (3). Several instances with different problem scales are randomly generated. Globally optimal solutions are gained by using CPLEX 12.6 to solve small size instances. We also implement the ACO-based heuristic algorithm to solve large-scale instances. Table 7 shows their difference in terms of computation efficiency and solution quality. As more demand points are covered by all routes, more solved time is required to obtain the solutions, where the computation time of CPLEX increases geometrically, while that of heuristic algorithm increases gently. We can observe that CPLEX takes more than 1 h to solve optimal solutions in case of more than 30 demand points, while the heuristic spends 5.1 seconds to obtain locally optimal solutions. The difference of best solutions is controlled under 10%, but that of solved time will grow at a geometric rate as well.Table 7
Comparison of CPLEX solution and heuristic solution.
CPLEX resultsHeuristic resultsDifferenceScenarioISolved timeBest (CNY)Solved timeAverage (CNY)Best (CNY)Solved timeBest (CNY)10389 s2496.22.3 s2693.12496.20.59%0%303912 s6794.95.1 s7651.66885.50.13%1.3%60>24 h10214.69.6 s12268.411003.90.01%7.7%120——21.8 s29663.228088.5——180——35.6 s52069.650149.7——


## 5.1. Example Description

In this section, a case study of designing green DRASS for Nantong City in China is given to demonstrate the applicability of the proposed model. There is one airport (M), five depot centers (D1–D5), and 33 demand points (P1–P33). Figure 4 is used to map the spatial distribution of these vehicular nodes, in which time-varying speeds on the road are obtained from a Baidu Open GIS tool using http://api.map.baidu.com. Moreover, the number of passengers and their preferred time windows and expected ride time in demand points are shown in Table 2. The parameters of NSGA-II are given in [34]. The proposed algorithm is run on Matlab 2017 B using a Dell Inspiron N5040 laptop with Core i3 processor and 4 GB memory. The key parameters used in the case study are as follows:(i)
Number of AFVs:6.(ii)
Maximum capacity of each AFV:Qk = 12 per.(iii)
Biggest continue voyage course of each AFV:Dmaxk = 100 km.(iv)
Weight of each AFV:wk = 2300 kg.(v)
Fixed use cost of each AFV:ck = 120 CNY.(vi)
Minimum travel time of vehicle route:Tmin = 3 min.(vii)
Boarding time of per passenger:β = 0.5 min.(viii)
Average weight of each person:γ = 60 kg.(ix)
Penalty fee for early arrival:ce = 1 CNY/min.(x)
Penalty fee for late arrival:cl = 3 CNY/min.(xi)
Unit cost of the fuel:cf = 7.59 CNY/liter.(xii)
Unit CO2 emission cost: cp = 80 CNY/ton.(xiii)
CO2 emission factor: fp = 0.785 kg/liter.Figure 4
Spatial distribution of vehicles visiting points in Nantong City in China.Table 2
Basic information of demand points.
No.ai,lipiLtihNo.ai,lipiLtihNo.ai,lipiLtihP18 : 30–8 : 4022.5P127 : 30–8 : 0014P238 : 10–8 : 3023.5P28 : 20–8 : 3012.5P136 : 20–6 : 4022.5P248 : 00–8 : 3023P38 : 00–8 : 1022.5P146 : 20–6 : 5022P257 : 10–7 : 3021P46 : 40–7 : 1024P156 : 20–6 : 4022P267 : 40–7 : 5020.5P510 : 00–10 : 1021.5P166 : 40–7 : 0022P276 : 40–7 : 1015P68 : 00–8 : 2021P178 : 00–8 : 3013.5P2810 : 00–10 : 1021P76 : 40–7 : 1011.5P186 : 30–7 : 0022.5P297 : 50–8 : 0021.5P86 : 40–7 : 1021.5P197 : 00–7 : 1022.5P307 : 50–8 : 1021P96 : 10–6 : 3022.5P206 : 50–7 : 1024.5P316 : 40–7 : 1015P107 : 40–8 : 0021.5P216 : 30–7 : 0022P328 : 00–8 : 2011P116 : 30–7 : 0024.5P228 : 00–8 : 2013.5P338 : 00–8 : 1020.5


## 5.2. Results

The CPU time for finding a set of Pareto optimal solutions is usually less than 1 minute. As explained previously, the proposed model could yield 10 feasible metaoptimal solutions in three dimensions, including the assignment of each demand point to an AFV, its route, and timetable. The upper and lower bounds of objective function 1 are 1305.8 RMB and 693.7 RMB, that of objective function 2 are 1187.2 RMB and 1156.7 RMB, and that of objective function 3 are 3.9 RMB and 3.7 RMB, respectively. Figures5 and 6 reveal the changing relationship between any two goals. As the value of objective function 1 becomes larger, that of objective function 2 becomes smaller. This is because the reduction in the total penalty charges for violating the passenger’s time window leads to the need for more mileage for vehicles covering all demand points, thus increasing energy consumption costs. Objective 2 and objective 3 are positively linearly correlated, which determines that the change in trend of objective 1 and objective 2 is consistent with the change in trend of objective 1 and objective 3. This is because energy consumption determines carbon emissions.Figure 5
Negative nonlinear relationship between objective 1 and objective 2.Figure 6
Positive linear relationship between objective 2 and objective 3.Tables3 and 4 are used to provide the routing and scheduling results related to the metaoptimal solution (693.7, 1187.2, 3.9). The pick-up time, riding time, and early/late arrival time of the AFV at each pick-up location are detailed in Table 3, in which zero, positive, and negative numbers in the fourth column of the table represent normal, early, and late arrival, respectively. The arrival and departure time for all AFVs visiting their demand points as well as fuel consumption and CO2 emissions of each AFV are detailed in Table 4. Taking the AFV of V1 as an example, the vehicle leaves the depot D5 at 06 : 28 and arrives at the demand point P29 at 7 : 36. Since the client’s time window is (7 : 50, 8 : 00), the early arrival time is 13.9 minutes. After 1 minute to pick up 2 persons, it leaves this location at 7 : 37. Similarly, the arrival and departure time of P30 and P33 are (7 : 53, 7 : 54) and (8 : 07, 8 : 08), and their early or late arrival times are 0 minutes and 0 minutes. Finally, this vehicle reaches its airport of M at 8 : 37 to unload 6 persons. As above mentioned, the riding times of P29, P30, and P33 for V4 are calculated as 61.1 minutes, 44.2 minutes, and 29.6 minutes. The vehicle travels a total of 52.6 km, consuming 9 liters of petrol and emitting 7.1 kg of CO2. The costs in terms of energy consumption and carbon emissions are 68.3 CNY and 0.5 CNY, and the penalty for violating the time window is 27.8 CNY.Table 3
Assignment results of passengers picked up by each AFV.
No.Pick-up time (min)Ride time (min)Early/late time (min)VehicleP8178.80V1P70.568.3−4.2P25138.2−14.3P26120.4−12.1P181138.40V2P191131.815.0P211110.1−6.7P10162.30P6148.10P270.5287.50V3P311265.7−14.7P201243.2−17.2P120.5232.40P221204.50P231195.60P241187.60P5183.80P29161.113.9V4P30144.20P33129.60P111253.30V5P41234.5−7.7P170.5207.535.3P31148.3−14P20.5141.3−1P11134.30P28143.60P91135.10V6P131122.10P141116.90P1611120P151100.2−17.5P32141.94.3—————Table 4
Routing and scheduling plan of each AFV.
VehicleSequence of demand points visited by each AFVMileage (km)Fuel consumption (liter)CO2 emissions (kg)Number of passengersV1D4 (6 : 45)–P8 (7 : 03–7:04)–P7 (7 : 14, 7 : 14)–P25 (7 : 44, 7 : 45)–P26 (8 : 02, 8 : 03)–M (8 : 22)48.49.17.17V2D3 (6 : 35)–P18 (6 : 38, 6 : 39)–P19 (6 : 44, 6 : 45)–P21 (7 : 06, 7 : 07)–P10 (7 : 54, 7 : 55)–P6 (8 : 08, 8 : 09)– M (9 : 56)44.46.85.310V3D1 (6 : 36)–P27 (6 : 42, 6 : 43)–P31 (7 : 04, 7 : 05)–P20 (7 : 27, 7 : 28)–P12 (7 : 37, 7 : 38)–P22 (8 : 05, 8 : 06)–P23 (8 : 14, 8 : 15)– P24 (8 : 22, 8 : 23)– P5 (10 : 06, 10 : 07)–M (11 : 30)94.515.011.812V4D5 (6 : 28)–P29 (7 : 36, 7 : 37)–P30 (7 : 53, 7 : 54)–P33 (8 : 07, 8 : 08)–M (8 : 37)52.69.07.16V5D4 (6 : 21)–P11 (6 : 39, 6 : 40)–P4 (6 : 57, 6 : 58)–P17 (7 : 24, 7 : 25)–P3 (8 : 24, 8 : 25)–P2 (8 : 31, 8 : 31)– P1 (8 : 37, 8 : 38)–P28 (10 : 08, 10 : 09)–M (10 : 52)90.514.211.112V6D4 (6 : 17)–P9 (8 : 22, 8 : 23)–P13 (6 : 35, 6 : 36)–P14 (6 : 40, 6 : 41)–P16 (6 : 45, 6 : 46)–P15 (6 : 57, 6 : 58)–P32 (7 : 55, 7 : 56)–M (8 : 37)47.47.25.811Furthermore, the proposed model has unique features compared to traditional DRASS with fixed speed. As shown in Figure7, mileage of the proposed model is 0.36% more than for the traditional one, but the carbon emissions and fuel consumption of the proposed model are 0.87% and 0.66% less than those of the traditional one. In traditional DRASS with fixed speed, the more the mileage, the more the carbon emissions and fuel consumption. However, the flexible departure time of each AFV in time-varying traffic conditions can avoid vehicles driving on congested roads, thus increasing energy consumption costs.Figure 7
Comparison of the results between proposed and traditional model.


## 5.3. Comparative Analysis and Parameter Sensitivity

In this section, sensitivity analyses are also given to investigate the impact of the number of AFVs and the changes in weight coefficientcl/ce on the model performance. Comparison of the results is shown in Tables 5 and 6, from which the following holds:(1)
As the weight coefficient gradually increases, early arrival time will be increased while late arrival time will be reduced. Besides, total mileage, fuel consumption, and CO2 emissions remain the same, except for the boundary conditions being met. When it happens, DRASS plan with an increase in mileage would lead to more fuel consumption and CO2 emissions. This is because increased weight coefficient cl/ce may cause an increase in early arrival time and a reduction in late arrival time, which leads to more mileage.Table 5
Comparison of the results of different weight coefficientscl/ce
ScenarioMileage (km)Fuel consumption (liter)CO2 emissions (kg)Early arrival time (min)Late arrival time (min)1 : 3377.861.548.368.4119.32 : 337460.047.177.1111.33 : 337460.047.177.1109.34 : 3366.159.246.586.078.0(2)
As the number of AFVs increases, total mileages slightly increase. This can be attributed to an increase in invalid mileage from vehicles starting from the depot and ending at the airport. Similarly, a reduced number of demand points visited by those AFVs may causes vehicles to reach the pick-up locations faster, thus increasing total early and late arrival time. When mileage of two DRASS plans varies widely, DRASS plan with greater mileage means more energy consumption and emissions. However, DRASS plan with small mileage in congested road conditions may consume more energy and emit more emissions, as the mileage difference in them is small.Table 6
Comparison of the results of different numbers of AFVs.
ScenarioMileage (km)Fuel consumption (liter)CO2 emissions (kg)Early and late arrival time (min)6 AFVs353.457.545.2363.47 AFVs444.774.358.3891.18 AFVs45173.857.91000.6


## 5.4. Validation of Algorithm

In order to verify the validity of proposed algorithm, the multiobjective DRASS could be transformed into a single objective function with minimization of the weighted sum of two objective functions (1), (2), and (3). Several instances with different problem scales are randomly generated. Globally optimal solutions are gained by using CPLEX 12.6 to solve small size instances. We also implement the ACO-based heuristic algorithm to solve large-scale instances. Table 7 shows their difference in terms of computation efficiency and solution quality. As more demand points are covered by all routes, more solved time is required to obtain the solutions, where the computation time of CPLEX increases geometrically, while that of heuristic algorithm increases gently. We can observe that CPLEX takes more than 1 h to solve optimal solutions in case of more than 30 demand points, while the heuristic spends 5.1 seconds to obtain locally optimal solutions. The difference of best solutions is controlled under 10%, but that of solved time will grow at a geometric rate as well.Table 7
Comparison of CPLEX solution and heuristic solution.
CPLEX resultsHeuristic resultsDifferenceScenarioISolved timeBest (CNY)Solved timeAverage (CNY)Best (CNY)Solved timeBest (CNY)10389 s2496.22.3 s2693.12496.20.59%0%303912 s6794.95.1 s7651.66885.50.13%1.3%60>24 h10214.69.6 s12268.411003.90.01%7.7%120——21.8 s29663.228088.5——180——35.6 s52069.650149.7——


## 6. Conclusions

In this paper, a novel MOMILP model was proposed for green DRASS with time-varying speeds to balance the operating cost, vehicle fuel consumption, and CO2 emissions. Furthermore, customer’s soft time windows and limited fuel capacity for an AFV are incorporated into the proposed model in order to represent real-world conditions. The metaoptimal solutions are obtained using NSGA-II. The main findings can be summarized as follows:(1)
Carbon emissions cost and fuel consumption cost of the proposed model are positively linearly correlated, and both these and the total penalty charges for violating the passenger’s time window are negatively nonlinearly correlated.(2)
When mileage of two DRASS plans varies widely, DRASS plan with a greater mileage means more energy consumption and emissions. However, DRASS plan with small mileage in congested road conditions may consume more energy and emit more emissions than DRASS plan with big mileage in good road conditions, as the mileage difference in them is small.(3)
The carbon emissions and fuel consumption of the proposed model are less than those of DRASS with fixed speeds. This is because the flexible departure time of each AFV in time-varying traffic conditions can avoid vehicles driving on congested roads, thus increasing energy consumption costs.Note that the vehicle in this DRASS model is an AFV, not an electric bus (EC). An EC emits almost no carbon, but it can be recharged at any of the available stations during the workday. In this sense, the collaborative design of DRASS routes and recharging station locations should consider the interactions between construction and operating expenses of charging piles and operation costs of these ECs. As a result, extending the DRASS model to simultaneously select the optimal locations of charging piles, design ECs routes, and assign ECs to recharging stations is worth further studying.



---

*Source: 9853164-2020-09-02.xml*