# Time-Dependent Vehicle Routing of Free Pickup and Delivery Service in Flight Ticket Sales Companies Based on Carbon Emissions

Authors: Jingmei Guo; Chao Liu
Journal: Journal of Advanced Transportation
 (2017)

---

## Abstract

The time-dependent pollution-routing problem of free pickup and delivery of passengers to the airport service (TDFPDS) is an extension of the time-dependent pollution-routing problems, arising in flight ticket sales companies for the service of free pickup and delivery of airline passengers to the airport. The problem consists of routing a fleet of vehicles in order to deliver a set of customers to the airport considering the traffic congestion, time window constraints, and maximum ride time constraints. The cost function includes fuel consumption and driver costs. We provide an analytical characterization of the optimal solutions for a fixed route and propose a novel heuristic for a given route based on the analysis of the illustrative examples. The heuristic algorithm is embedded into a set-partitioning model to produce high-quality routing plans. Finally, using wide variety of random instances, we present results on the computational performance of the heuristic and also on the impact of the congestion and the maximum ride time constraints.


---

## Body

## 1. Introduction

Green Logistics has recently received closed attention from governments and business organizations. The importance of Green Logistics is motivated by the fact that current production and distribution logistics strategies are not sustainable development in the long term due to the negative impacts on the environment and the ecology. It is no doubt that transportation accounts for the major part of logistics. The trend is that more and more countries will start to adopt emission-reducing actions, build green intelligent transportation systems, and exploit other strategies to obtain Green Logistics, which enhances the importance of vehicle routing problems with environmental considerations.The studies of routing problems concerning the change of transportation systems are mainly divided into two topics. One aspect makes use of new energy sources, named alternative fuel vehicles, such as electric cars and liquid natural gas, to complete the transportation of the goods, which is denoted as Green Vehicle Routing Problems (GVRP). The main issue of GVRP is that it contains not only the algorithms of routing and scheduling but also the key procedures of recharge due to the limited energy capacity, as described in Felipe et al. [1] and Montoya et al. [2]. Another topic is committed to the reasonable arrangement of paths and selection of speeds to reduce carbon emissions or fuel consumption, since better utilization of vehicles and a cost effective vehicle routing solution would more directly achieve sustainable transportation schemes (Lin et al. [3]). A formulation of fuel consumption is provided in Xiao et al. [4]. They proposed a Fuel Consumption Rate (FCR) to denote the fuel consumption per unit distance as a linear function associated with the vehicle’s load, which extends to Capacitated Vehicle Routing Problems (CVRP) with the objective of minimizing fuel consumption. Besides the transportation distance and the loading weight, Kuo [5] adds the transportation speed to the fuel consumption calculation model in time-dependent Vehicle Routing Problems (VRP). Pollution-routing problem (PRP) introduced by Bektaş and Laporte [6] converts the traditional objective function of distance or duration to carbon emissions and driver costs. PRP consists of routing a number of vehicles to serve a set of customers within preset time windows and determining their speed on each arc of the route to minimize the total cost. This problem seeks optimal travel routes and speeds subject to time constraints, the combination of two intricate sets of decision variables making it more complicated than VRP with time windows (VRPTW). PRP is solved mainly by metaheuristic for medium and large cases (Demir et al. [7]; Kramer et al. [8]). Franceschetti et al. [9] integrate the PRP with time-dependent VRP (TDPRP) as a more realistic approach to deal with the minimization of emissions considering the impact of congestion. More details about research of the Green Transportation can be seen in the survey of Lin et al. [3].Free pickup and delivery to the airport is a personalized service from flight ticket sales companies for passengers to buy tickets from the company firstly introduced by Dong et al. [10] and denoted as free pickup and delivery of passengers to the airport service (FPDS). The FPDS consists of routing a number of vehicles to serve customers with their desired delivery time so as to balance the trade-off between the company’s cost and the passenger satisfaction degree. The FPDS is an extension of VRPTW and has typical characteristics such as small vehicle capacity and time windows restricted in the unified destination (airport). Flight ticket sales companies supply the service in order to compete in the market on the premise of cost savings. The pollution-routing problem (Bektaş and Laporte [6]) converts the carbon emissions to the fuel consumption, which considers the environmental impact but also the fuel cost. As a result, the fuel cost association with the driver wages cost as the ticket companies’ cost is an appropriate measurement compared with the total distance traveled, especially in the congestion case.We introduce the time-dependent routing problem of free pickup and delivery of passengers to the airport service (TDFPDS), which extends the FPDS by explicitly taking into account traffic congestion, the environmental implication, and the reasonable cost measurement. A set-partitioning model is introduced as the basic routing algorithm and the main contribution is focused on the feasibility check and schedule of a fixed route with the vehicle’s departure time and speeds. We describe a mixed integer linear programming formulation for a given route where the vehicle speed of each leg of the route is optimized among a set of discrete values. Through the numerical analysis solved by the formulation, we also propose a heuristic algorithm to solve medium- and large-sized problems with near-optimal schedule for fixed route. Finally, we report computational experiments with the formulation and the heuristic algorithm on simulation instances.The contribution of this paper can be stated as follows: (i) we introduce time-dependent travel time, which is the first time that such constraint is addressed in FPDS, to our knowledge, (ii) we also consider the maximum ride time constraints in the FPDS, which are not considered in the VRPTW, as the main difference between the TDPRP and TDFPDS, (iii) we demonstrate that in the optimal schedule speeds on each leg of the route are the same, and hence an effective heuristic algorithm is proposed to schedule the route with complex maximum ride time constraints and traffic congestion.The remainder of the paper is structured as follows. The next section presents a formal description of each composition of the TDFPDS and the general model of it. Section3 provides departure time and speed optimization procedure on a fixed route by integer linear programming formulation, illustrative examples to motivate the problem, and a heuristic to solve the fixed route schedule in the last. Section 4 describes the set-partitioning model routing the TDFPDS. Computational results with the proposed exact and heuristic formulation are presented in Section 5. Conclusions follow in Section 6. For the sake of conciseness, proofs and the optimal departure time results of the heuristic are provided in Appendices A and B.


## 2. Problem Description

The TDFPDS is defined on a complete graphG={N,A}, where N is the set of nodes, 0 is the depot, V is the airport, N0=N∖{0,V} is the set of orders, and A is the set of arcs between each pair of nodes. The distance between two nodes i and j is denoted by dij. A homogeneous fleet of K vehicles, each with a capacity of Q customers, is available to serve all orders. Each node is visited exactly once by one vehicle. Each order i∈N0 is associated with a number of passengers qi, a desired delivery time window [Ei,Li], and a maximum ride time MRTi which represent the service quality. Without loss of generality the service time of each order is set equal to zero as the boarding time is short enough compared with the travel time. The following sections present the way in which time-dependency and congestion are modeled and how CO2 emissions are calculated and elaborate the complete model of the TDFPDS in the last.


### 2.1. Congestion and Time-Dependency

In the case of time-dependent travel time, the speed model is based on the key elements of peak hour traffic congestion. The travel time of a vehicle mainly depends on distance and the departure time of the vehicle because the speed is constrained by periods of traffic congestion. Without loss of generality we assume that the vehicles depart from the depot at time zero. Here, we model traffic congestion using a two-level speed function as in Jabali et al. [11] and Franceschetti et al. [9]. It is assumed that there is an initial period of congestion, lasting a units of time, followed by a period of free-flow. In the peak-period, the vehicle travels at a limited speed vc whereas in the free-flow period that follows it is only constrained by the speed limits vmin and vmax; that is, the vehicle drives at free-flow speed vf∈[vmin,vmax]. The speed vc and the time a are constants which can be extracted from archived travel data and we assume that the same values hold between each pair of locations. Let T(w,vf) denote the travel time of a vehicle between two locations of distance d as a function of its departure time w from the first location and the chosen free-flow speed vf. It can be computed using the following formulation proposed by Jabali et al. [11]:(1)Tw,vf=dvc,ifw≤a-dvc+,a+d-vca-wvf,ifa-dvc+<w<a,dvf,ifw≥a,where (x)+=max{x,0}.


### 2.2. Calculating Emissions

Our modeling of emissions follows the same approach as in Bektaş and Laporte [6] and Franceschetti et al. [9], where the fuel use rate is used as a proxy to estimate the amount of CO2 emissions and the fuel consumption is calculated to model the emissions.Given the departure timew and the free-flow speed vf on a road of distance d, in the time-dependent setting, the travel time T(w,vf) is split into two terms: the time spent by the vehicle in congestion, denoted as Tc(w), and the time spent in the free-flow speed, denoted as Tf(w,vf). The total amount of fuel consumption TC(w,vf) can be written as (2)TCw,vf=k1Tw,vf+k2Tcwvc3+Tfw,vfvf3+k3μ+fd,where k1, k2, and k3 are parameters based on fuel properties, vehicle, and the road network characteristics (Demir et al. [7]) and μ and f are the curb weight and the weight of the persons in the vehicle.


### 2.3. Description of the TDFPDS

In this section, we briefly describe the objective and constraints of the TDFPDS, which could help us to understand the problem better and work out an effective method to solve it. We follow the precious work of pollution routing which shows that the total travel cost function is composed of the cost of the vehicle emissions and the driver cost for each trip instead of the traditional total distance multiplying unit cost. As theCO2 emissions cost is not easy to be quantified, we assume that the CO2 emissions cost is equal to the fuel cost similar to Franceschetti et al. [9], denoted as fe. The vehicle’s fuel consumption is related to the emissions [11]; thus, a conversion factor h is used to calculate the vehicle’s fuel consumption. Then, the unit cost of the fuel consumption and the emissions is calculated as fc=fe(1+h) per liter. Thus, the cost is especially suitable for the FPDS, since it adopts fuel cost and driver wage cost which satisfy the cost saving requirements of the company but also decrease the carbon emissions for environmental considerations. The driver cost is calculated from the beginning of the trip until arriving at the airport. Let fd denote the wage rate for the drivers.The aim of the TDFPDS is to determine a set of routes, starting at the depot, ending at the airport, with free speeds on each road of the routes and departure times from each node to minimize the total travel cost, under the constraints of vehicle capacity, time window, and the maximum ride time.


## 2.1. Congestion and Time-Dependency

In the case of time-dependent travel time, the speed model is based on the key elements of peak hour traffic congestion. The travel time of a vehicle mainly depends on distance and the departure time of the vehicle because the speed is constrained by periods of traffic congestion. Without loss of generality we assume that the vehicles depart from the depot at time zero. Here, we model traffic congestion using a two-level speed function as in Jabali et al. [11] and Franceschetti et al. [9]. It is assumed that there is an initial period of congestion, lasting a units of time, followed by a period of free-flow. In the peak-period, the vehicle travels at a limited speed vc whereas in the free-flow period that follows it is only constrained by the speed limits vmin and vmax; that is, the vehicle drives at free-flow speed vf∈[vmin,vmax]. The speed vc and the time a are constants which can be extracted from archived travel data and we assume that the same values hold between each pair of locations. Let T(w,vf) denote the travel time of a vehicle between two locations of distance d as a function of its departure time w from the first location and the chosen free-flow speed vf. It can be computed using the following formulation proposed by Jabali et al. [11]:(1)Tw,vf=dvc,ifw≤a-dvc+,a+d-vca-wvf,ifa-dvc+<w<a,dvf,ifw≥a,where (x)+=max{x,0}.


## 2.2. Calculating Emissions

Our modeling of emissions follows the same approach as in Bektaş and Laporte [6] and Franceschetti et al. [9], where the fuel use rate is used as a proxy to estimate the amount of CO2 emissions and the fuel consumption is calculated to model the emissions.Given the departure timew and the free-flow speed vf on a road of distance d, in the time-dependent setting, the travel time T(w,vf) is split into two terms: the time spent by the vehicle in congestion, denoted as Tc(w), and the time spent in the free-flow speed, denoted as Tf(w,vf). The total amount of fuel consumption TC(w,vf) can be written as (2)TCw,vf=k1Tw,vf+k2Tcwvc3+Tfw,vfvf3+k3μ+fd,where k1, k2, and k3 are parameters based on fuel properties, vehicle, and the road network characteristics (Demir et al. [7]) and μ and f are the curb weight and the weight of the persons in the vehicle.


## 2.3. Description of the TDFPDS

In this section, we briefly describe the objective and constraints of the TDFPDS, which could help us to understand the problem better and work out an effective method to solve it. We follow the precious work of pollution routing which shows that the total travel cost function is composed of the cost of the vehicle emissions and the driver cost for each trip instead of the traditional total distance multiplying unit cost. As theCO2 emissions cost is not easy to be quantified, we assume that the CO2 emissions cost is equal to the fuel cost similar to Franceschetti et al. [9], denoted as fe. The vehicle’s fuel consumption is related to the emissions [11]; thus, a conversion factor h is used to calculate the vehicle’s fuel consumption. Then, the unit cost of the fuel consumption and the emissions is calculated as fc=fe(1+h) per liter. Thus, the cost is especially suitable for the FPDS, since it adopts fuel cost and driver wage cost which satisfy the cost saving requirements of the company but also decrease the carbon emissions for environmental considerations. The driver cost is calculated from the beginning of the trip until arriving at the airport. Let fd denote the wage rate for the drivers.The aim of the TDFPDS is to determine a set of routes, starting at the depot, ending at the airport, with free speeds on each road of the routes and departure times from each node to minimize the total travel cost, under the constraints of vehicle capacity, time window, and the maximum ride time.


## 3. Departure Time and Speed Optimization on Fixed Route

In this section, we consider a given route in which the customer nodes and sequence to be visited are fixed. Let(0,1,…,n,n+1) be the fixed sequence of nodes. Node 0 is the depot and node n+1 is the airport. Let di denote the distance on arc (i,i+1) with 0≤i≤n. The main job of this section is to determine departure time and free-flow speed of each arc in the route so as to minimize the total travel cost, denoted as DSP.The following sections will present a mixed linear integer programming for DSP, extensive examples to illustrate the characteristics of the solutions, and a heuristic algorithm to solve the DSP.


### 3.1. A Mixed Linear Integer Programming for DSP

This section presents a mathematical formulation for DSP. Firstly, we simplify the time window constraints. Since customers in a route arrive at the airport at the same time, the vehicle should arrive at the airport in[l,u], where l=max{Ei∣i=1,…,n} and u=min{Li∣i=1,…,n}. Obviously, if l>u, the route is infeasible. In order to clarify the effect of waiting time to the solution, waiting time is allowed in the model. As the free-flow speed is continuous, the objective function and the constraints are not linear. To linearize it, we discretize the free-flow speed following the approach used by Bektaş and Laporte [6] and Franceschetti et al. [9]. Here we provide a brief exposition for the sake of well understanding. Let v1,…,vk denote the different free-flow speeds where vmin=v1≤⋯≤vk=vmax. To rewrite the travel time as a linear equation, the following definitions are given. Let bi0=0, bi1=(a-di/vc)+, bi2=a, and bi3=∞. Then [bi,m-1,bi,m) denotes the mth time interval of arc (i,i+1), where m={1,2,3}. Let Vmr denote the vehicle speed in time region m given free-flow speed vr; that is, V1,r=vc, V2,r=vc, and V3,r=vr. These definitions allow us to rewrite (1) for arc (i,i+1) as T(w,vr)=θmrw+ηimr if w∈[bi,m-1,bim) with free-flow speed vr, where (3)
θ
m
r
=
0
,
i
f
m
=
1,3
,
V
2
r
-
V
3
r
V
3
r
,
i
f
m
=
2
,
η
i
m
r
=
d
i
V
1
r
,
i
f
m
=
1
,
d
i
V
3
r
+
θ
m
r
a
,
i
f
m
=
2
,
d
i
V
3
r
,
i
f
m
=
3
.The model uses the following decision variables:zimr is binary variable equal to 1 if the vehicle leaves node i to node i+1 within time interval [bi,m-1,bi,m) with free-flow speed vr,wimr is equal to the time instant at which the vehicle leaves node i to node i+1 within time interval [bi,m-1,bi,m) with free-flow speed vr, where i=0,1,…,n,m=1,2,3, and r=1,…,k. wn+1 is equal to the time instant at which the vehicle arrives at the airport.A mixed integer linear programming formulation for the DSP is given below. The first three parts of the objective function represent the total cost of the fixed route. In particular, (4)-(5) compute the cost induced by the engine module and the speed module. Term (6) measures the cost induced by the driver wage and the weight module, where F=∑i=0nfck3(μ+iν)di is the cost induced by the weight module, which is constant when the route is determined. Constraints (7)-(8) are used to express the temporal relationship between arrival time and departure time, with inequality constraints indicating that wait is allowed in the trip. Constraints (9) and (10) guarantee that the departure time of node i belongs to exactly one of the three intervals. The time window restriction at the airport is imposed by constraint (11). The maximum ride time restriction at each node is imposed by constraint (12). Finally, constraint (13) enforces the integrality and nonnegativity restrictions on the variables. We provide a numerical analysis of the performance of this formulation in the following section and Section 5. (4)
m
i
n
i
m
i
z
e
f
c
k
1
∑
i
=
0
n
∑
m
=
1
3
∑
r
=
1
k
θ
m
r
w
i
m
r
+
η
i
m
r
z
i
m
r
+
∑
i
=
0
n
∑
m
=
1
3
∑
r
=
1
k
f
c
k
2
v
m
r
3
θ
m
r
w
i
m
r
+
η
i
m
r
z
i
m
r
(5)
+
∑
i
=
0
n
∑
r
=
1
k
f
c
k
2
v
2
r
3
a
z
i
2
r
-
w
i
2
r
+
∑
i
=
0
n
∑
r
=
1
k
f
c
k
2
v
3
r
3
w
i
2
r
+
θ
2
r
w
i
2
r
+
η
i
2
r
z
i
2
r
-
a
z
i
2
r
(6)
+
f
d
w
n
+
1
-
∑
m
=
1
3
∑
r
=
1
k
w
0
m
r
+
F
(7)
s
u
b
j
e
c
t
t
o
∑
m
=
1
3
∑
r
=
1
k
w
i
+
1
,
m
r
≥
∑
m
=
1
3
∑
r
=
1
k
w
i
m
r
+
θ
m
r
w
i
m
r
+
η
i
m
r
z
i
m
r
,
i
=
0,1
,
…
,
n
-
1
(8)
w
n
+
1
≥
∑
m
=
1
3
∑
r
=
1
k
w
n
m
r
+
θ
m
r
w
n
m
r
+
η
n
m
r
z
n
m
r
(9)
∑
m
=
1
3
∑
r
=
1
k
z
i
m
r
=
1
,
i
=
0,1
,
…
,
n
(10)
b
i
,
m
-
1
z
i
m
r
≤
w
i
m
r
≤
b
i
m
z
i
m
r
,
i
=
0,1
,
…
,
n
,
m
=
1,2
,
3
,
r
=
1
,
…
,
k
(11)
l
≤
w
n
+
1
≤
u
(12)
w
n
+
1
-
∑
m
=
1
3
∑
r
=
1
k
w
i
m
r
≤
M
R
T
i
,
i
=
1,2
,
…
,
n
(13)
z
i
m
r
∈
0,1
,
w
i
m
r
≥
0
,
i
=
0,1
,
…
,
n
,
m
=
1,2
,
3
,
r
=
1
,
…
,
k
.


### 3.2. Case Study of the Mixed Linear Integer Programming for DSP

In this section, we give three types of examples to investigate the impact of considering traffic congestion on the routing and scheduling planning activities. We then enable a heuristic for DSP through the test results.In both cases, we analyze a four-node network where node0 is the depot, {1,2} is the set of customers, and 3 is the airport, with routing (0,1,2,3). The congestion speed vc is set to 19 km/h, the minimum speed limit vmin to 40 km/h, and the maximum speed limit vmax to 110 km/h. The congestion period is set to 3600 seconds. We uniformly discretize the free-flow speed within vmin and vmax. The examples differ with respect to the time window at the airport, the distance of the nodes, and the maximum ride time to guarantee feasibility. We assume that the capacity constraint is always satisfied given that the scheduling does not depend on the customer number. The parameters used to calculate the total cost function are the same as reported in Demir et al. [7]. Let SI and SD denote the solution of the time-independent approach and the time-dependent approach. For the computational results, the table reports cases in the first column. Then for each solution, the table reports (i) the set of traversed arcs, (ii) the distance of the arc, (iii) the speed at which each arc is traversed (for an arc traversed during the transient region, both the congestion speed and free-flow speed are reported), (iv) the departure time from the origin node, and (v) the total cost TC. The last row of Dep denotes the arrival time at the airport. All the mixed integer problems are solved by CPLEX 12.0 and all the time parameters given below are measured in seconds.Example 1 (u≤a).
In this example, the vehicle is in the all congestion period. The parameters are as follows:l=1084, u=2489, MRT1=657, and MRT2=541. The solutions to the time-independent and time-dependent approaches are displayed in Table 1.Table 1
Results in Example1.
Arc Dis S D S I Speed (m/s) Dep (s) TC (£) Speed (m/s) Dep (s) TC (£) (0,1) 6370 5.28 0 4.4925 21.91 648 1.7637 (1,2) 580 5.28 1207 0.4095 21.91 939 0.1610 (2,3) 2600 5.28 1317 1.8377 21.91 965 0.7238  Total   1810 6.7397  1084 2.6485Example 2 (l≤a≤u).
In this example, the vehicle is in the transient region; the vehicle leaving within this region traverses a distance of congestion period and then the vehicle travels the remaining (if exists) distance with the free-flow speed. The parameters are as follows:l=2929, u=4179, MRT1=2738, and MRT2=2814. The solutions are displayed in Table 2.Table 2
Results in Example2.
Arc Dis S D S I Speed (m/s) Dep (s) TC (£) Speed (m/s) Dep (s) TC (£) (0,1) 5117 5.28 2582 3.61 21.91 1877 1.42 (1,2) 5294 5.28, 30.56 3551 0.94 21.91 2110 1.47 (2,3) 12653 30.56 3765 4.07 21.91 2352 3.52  Total   4179 8.62  2929 6.41Example 3 (a≤l).
In this example, the vehicle arrives at the airport after the congestion period. The vehicle may firstly traverse a distance of congestion period and then the vehicle travels the remaining (if exists) distance with the free-flow speed. The parameters are as follows:l=4013, u=4179, MRT1=2738, and MRT2=251. The solutions are displayed in Table 3. We do not consider the case of all free-flow region as it is actually the time-independent approach.Table 3
Results in Example3.
Arc Dis S D S I Speed (m/s) Dep (s) TC (£) Speed (m/s) Dep (s) TC (£) (0,1) 5117 5.28, 30.56 2746 2.03 21.91 3160 1.42 (1,2) 8440 30.56 3677 2.72 21.91 3393 2.35 (2,3) 5104 30.56 3734 1.64 21.91 3780 1.42  Total   4179 6.39  4013 5.19From Tables1–3, we can see that the time-dependent approach yields a higher cost than the time-independent approach. The best speeds of the time-independent approach all exceed the congestion speed vc, which is not feasible in the congestion period. We conclude that congestion is likely to increase costs or even leads to an infeasible solution. Thus, the congestion should be considered in the study of the pollution routing of FPDS.From the last column of Tables2 and 3, we see that the vehicle arrives at the airport at the maximum of the time window in order to avoid the congestion. The vehicle will never wait even if the wait time is allowed, which is not compatible with the results of Franceschetti et al. [9]. The reason is that the time window is limited to the final destination airport instead of the pickup node and the maximum ride time of each order is constrained in our problem, which makes the optimal schedule delay the departure time and decrease the wait time so as to avoid the congestion and reduce the customers ride time.From the tables, we can see that the free-flow speeds in the time-dependent and time-independent approaches are the same in all the arcs. As a consequence, in the next section, we assume that the free-flow speed of a vehicle is the same even if it travels the different arc and provide a heuristic for the scheduling of a fixed route.


### 3.3. A Heuristic for DSP

In this section, we propose a heuristic for solving DSP. From Section3.2, we can see that the DSP can be solved by a mixed integer programming. However, solving the MIP in Section 3.1 requires considerable computational effort due to the large number of binary decision variables and the accuracy of the solution depends on the level of discretization of the free-flow speeds. To overcome these limitations, we propose a heuristic algorithm which, in our numerical experiments, has been observed to solve the problem at least as well as the MIP solutions in most cases we have considered.From the case study in Section3.2, we can see that the free-flow speeds do not change in the route. Accordingly, we assume that the free-flow speed is unchanged during the route (0,1,2,…,n,n+1). Then the DSP converts to scheduling the departure time and free-flow speed on a single arc with two nodes, the depot and the airport. This special case of a single arc network has been studied by Franceschetti et al. [9]. Our problem differs with the case of Franceschetti et al. [9] as there are maximum ride time constraints in the TDFPDS. We introduce a new speed function as the maximum ride speed together with the speed functions considered in Franceschetti et al. [9] to solve the DSP.In order to ensure the consistency and readability of the paper, we firstly give the speed functions used in Franceschetti et al. [9]. We convert route (0,1,2,…,n,n+1) to a new single arc (0,n+1), with the distance of d=∑i=0ndi and time window [l,u] denoting the time in which the vehicle should arrive at the airport.Letvwt be the free-flow speed required for the driver to arrive at node n+1 exactly at time t when leaving the depot at time w. Then (14)vwt=d-a-w+vct-max⁡a,w,ifw∈0,t,t>a,∞,otherwise.Thenvwu is the free-flow speed required for the driver to arrive at node n+1 exactly at time u when leaving the depot at time w. In other words, vwu is the minimum speed required to arrive at the airport which is less than or equal to u when u>a. vwl is the free-flow speed required for the driver to arrive at node n+1 exactly at time l when leaving the depot at time w and meanwhile is the maximum speed required to arrive at the airport which is greater than or equal to l when l>a.Letwmaxu denote the time at which the vehicle needs to depart from the depot to reach the node n+1 at exactly time u, with free-flow speed vmax. wmaxu is an upper bound on the departure time since the free-flow speed is no greater than vmax. If wmaxu<0, then the route is infeasible. Without loss of generality, we assume that wmaxu≥0 hereinafter.Lemma 4.
Consider a single arc instance to minimize the emission cost and driver wage cost in the absence of time window with fixed departure timew. The optimal free-flow speed is v¯=((fck1+fd)/(2fck2))1/3.Using Lemma4, we can reduce DSP to one-dimensional optimization problem; that is, we set w as the unique decision variable. Proof of Lemma 4 is given in Appendix A.We then consider the maximum ride time constraints. For each orderi(1≤i≤n) of route (0,1,2,…,n,n+1), the minimum speed without congestion to satisfy its maximum ride time constraint is vfreei=(∑j=indj)/MRTi. The minimum speed of the route is vfree=max1≤i≤n{vfreei}. If vfree>vmax, the route is infeasible and the algorithm is stopped. If vfree≤vc, which makes the maximum ride time constraints always feasible, the maximum ride time constraints are trivial and the results are given in Franceschetti et al. [9]. We set that vfree=vmin if vfree<vmin in Cases 2 and 3. We integrate the congestion period into computation. For each node i, let wridei denote the departure time from node 0 with free-flow speed vmax so that the vehicle travels from order i to the airport exactly for time MRTi, written as (15)wridei=a-∑j=indj-MRTivmaxvc-vmax-∑j=0i-1djvc.If wridei<0, we can see that the maximum ride time of order i is always feasible with free-flow speed vmax, in which case we set wridei=0. If wridei>wmaxu, the route is infeasible. The minimum departure time to meet the maximum ride time constraints is denoted as wride=max1≤i≤n{wridei}.Letvridei denote the free-flow speed required for the driver to travel from node i to node n+1 exactly for time MRTi when leaving the depot at time w. In other words, vridei is the minimum speed to meet the maximum ride time constraint of order i, which is written as follows: (16)vridei=∑j=indj-vca-w-∑j=0i-1dj/vc+MRTi-a-w-∑j=0i-1dj/vc+.Then the minimum free-flow speed to meet the maximum ride time constraints when leaving the depot at timew is denoted as vride=max1≤i≤nvridei. Figure 1(a) shows the minimum free-flow speed vride of a vehicle as a function of departure time w.Figure 1
Speed functions as a function ofw.
(a)
v r i d e (b)
v r i d e and vwu (c)
Three speed curvesThe calculation ofvride suggests that the planning horizon can be divided into two consecutive time regions in terms of the departure time w as follows. The first one wride≤w≤wfree is called the all decrease region: the vehicle leaving the depot within this region makes vride decrease all the time. The second one w>wfree is called the stable region: the vehicle leaving the depot within this region makes vride remain a constant.Lemma 5.
When the vehicle is leaving the depot within the all decrease region with free-flow speedvride, the emission cost and driver wage cost are monotonically decreasing with respect to the departure time w.Using Lemma5, the optimal departure time in the decrease region can be easily solved. Proof of Lemma 5 is given in Appendix A.We consider three cases: (1)l≤u≤a, (2) l≤a≤u, and (3) a<l<u.Case 1 (l≤u≤a).
In this case, the vehicle travels in the all congestion period. Ifvfree>vc, the maximum ride time constraint is infeasible. Otherwise, the vehicle travels with speed vc in the trip at any time w in [(l-d/vc)+,wmaxu]. The results of optimal departure time and the total cost are given in Appendix B.1.Case 2 (l≤a≤u).
In this case, the earliest time to arrive at the airport is less thana, which means that the vehicle travels with speed vc when arriving at the airport exactly at l. We conclude that wride≥(l-d/vc)+ since the vehicle arrives at the airport after a if leaving the depot at time wride. The feasible departure time belongs to [wride,wmaxu]. Figure 1(b) shows the minimum free-flow speed as a function of departure time w. Let wunion denote the intersection point of the speed curves vwu and vride. Then the calculation of the free-flow speed can be divided into two consecutive time regions in terms of the departure time w. In the first one wride≤w≤wunion, the feasible free-flow speed belongs to [vride,vmax]. In the second one wunion≤w≤wmaxu, the feasible free-flow speed belongs to [vwu,vmax].
The results of optimal departure time and the total cost are given in AppendixB.2.Case 3 (a<l<u).
In this case, the earliest time to arrive at the airport is greater thana, which makes the choice of the free-flow speed more complicated. vwl, as the maximum speed to arrive at the airport greater than or equal to l, also needs to be considered. Let wmaxl denote the time at which the vehicle needs to depart from the depot to reach the node n+1 at exactly time l, with free-flow speed vmax. If the condition wmaxl≤wride holds, which means that the maximum speed already reaches vmax, then vwl does not work and the feasible departure time belongs to [wride,wmaxu] which converts to Case 2. Otherwise, let wini denote the intersection point of the speed curves vwl and vride. Figure 1(c) shows the minimum free-flow speed and the maximum free-flow speed as functions of departure time w. The calculation of the minimum free-flow speed can be divided into two consecutive time regions in terms of the departure time w. In the first one wini≤w≤wunion, the feasible free-flow speed belongs to [vride,min{vwl,vmax}]. In the second one wunion≤w≤wmaxu, the feasible free-flow speed belongs to [vwu,min{vwl,vmax}].
The result of optimal departure time and the total cost is given in AppendixB.3.


## 3.1. A Mixed Linear Integer Programming for DSP

This section presents a mathematical formulation for DSP. Firstly, we simplify the time window constraints. Since customers in a route arrive at the airport at the same time, the vehicle should arrive at the airport in[l,u], where l=max{Ei∣i=1,…,n} and u=min{Li∣i=1,…,n}. Obviously, if l>u, the route is infeasible. In order to clarify the effect of waiting time to the solution, waiting time is allowed in the model. As the free-flow speed is continuous, the objective function and the constraints are not linear. To linearize it, we discretize the free-flow speed following the approach used by Bektaş and Laporte [6] and Franceschetti et al. [9]. Here we provide a brief exposition for the sake of well understanding. Let v1,…,vk denote the different free-flow speeds where vmin=v1≤⋯≤vk=vmax. To rewrite the travel time as a linear equation, the following definitions are given. Let bi0=0, bi1=(a-di/vc)+, bi2=a, and bi3=∞. Then [bi,m-1,bi,m) denotes the mth time interval of arc (i,i+1), where m={1,2,3}. Let Vmr denote the vehicle speed in time region m given free-flow speed vr; that is, V1,r=vc, V2,r=vc, and V3,r=vr. These definitions allow us to rewrite (1) for arc (i,i+1) as T(w,vr)=θmrw+ηimr if w∈[bi,m-1,bim) with free-flow speed vr, where (3)
θ
m
r
=
0
,
i
f
m
=
1,3
,
V
2
r
-
V
3
r
V
3
r
,
i
f
m
=
2
,
η
i
m
r
=
d
i
V
1
r
,
i
f
m
=
1
,
d
i
V
3
r
+
θ
m
r
a
,
i
f
m
=
2
,
d
i
V
3
r
,
i
f
m
=
3
.The model uses the following decision variables:zimr is binary variable equal to 1 if the vehicle leaves node i to node i+1 within time interval [bi,m-1,bi,m) with free-flow speed vr,wimr is equal to the time instant at which the vehicle leaves node i to node i+1 within time interval [bi,m-1,bi,m) with free-flow speed vr, where i=0,1,…,n,m=1,2,3, and r=1,…,k. wn+1 is equal to the time instant at which the vehicle arrives at the airport.A mixed integer linear programming formulation for the DSP is given below. The first three parts of the objective function represent the total cost of the fixed route. In particular, (4)-(5) compute the cost induced by the engine module and the speed module. Term (6) measures the cost induced by the driver wage and the weight module, where F=∑i=0nfck3(μ+iν)di is the cost induced by the weight module, which is constant when the route is determined. Constraints (7)-(8) are used to express the temporal relationship between arrival time and departure time, with inequality constraints indicating that wait is allowed in the trip. Constraints (9) and (10) guarantee that the departure time of node i belongs to exactly one of the three intervals. The time window restriction at the airport is imposed by constraint (11). The maximum ride time restriction at each node is imposed by constraint (12). Finally, constraint (13) enforces the integrality and nonnegativity restrictions on the variables. We provide a numerical analysis of the performance of this formulation in the following section and Section 5. (4)
m
i
n
i
m
i
z
e
f
c
k
1
∑
i
=
0
n
∑
m
=
1
3
∑
r
=
1
k
θ
m
r
w
i
m
r
+
η
i
m
r
z
i
m
r
+
∑
i
=
0
n
∑
m
=
1
3
∑
r
=
1
k
f
c
k
2
v
m
r
3
θ
m
r
w
i
m
r
+
η
i
m
r
z
i
m
r
(5)
+
∑
i
=
0
n
∑
r
=
1
k
f
c
k
2
v
2
r
3
a
z
i
2
r
-
w
i
2
r
+
∑
i
=
0
n
∑
r
=
1
k
f
c
k
2
v
3
r
3
w
i
2
r
+
θ
2
r
w
i
2
r
+
η
i
2
r
z
i
2
r
-
a
z
i
2
r
(6)
+
f
d
w
n
+
1
-
∑
m
=
1
3
∑
r
=
1
k
w
0
m
r
+
F
(7)
s
u
b
j
e
c
t
t
o
∑
m
=
1
3
∑
r
=
1
k
w
i
+
1
,
m
r
≥
∑
m
=
1
3
∑
r
=
1
k
w
i
m
r
+
θ
m
r
w
i
m
r
+
η
i
m
r
z
i
m
r
,
i
=
0,1
,
…
,
n
-
1
(8)
w
n
+
1
≥
∑
m
=
1
3
∑
r
=
1
k
w
n
m
r
+
θ
m
r
w
n
m
r
+
η
n
m
r
z
n
m
r
(9)
∑
m
=
1
3
∑
r
=
1
k
z
i
m
r
=
1
,
i
=
0,1
,
…
,
n
(10)
b
i
,
m
-
1
z
i
m
r
≤
w
i
m
r
≤
b
i
m
z
i
m
r
,
i
=
0,1
,
…
,
n
,
m
=
1,2
,
3
,
r
=
1
,
…
,
k
(11)
l
≤
w
n
+
1
≤
u
(12)
w
n
+
1
-
∑
m
=
1
3
∑
r
=
1
k
w
i
m
r
≤
M
R
T
i
,
i
=
1,2
,
…
,
n
(13)
z
i
m
r
∈
0,1
,
w
i
m
r
≥
0
,
i
=
0,1
,
…
,
n
,
m
=
1,2
,
3
,
r
=
1
,
…
,
k
.


## 3.2. Case Study of the Mixed Linear Integer Programming for DSP

In this section, we give three types of examples to investigate the impact of considering traffic congestion on the routing and scheduling planning activities. We then enable a heuristic for DSP through the test results.In both cases, we analyze a four-node network where node0 is the depot, {1,2} is the set of customers, and 3 is the airport, with routing (0,1,2,3). The congestion speed vc is set to 19 km/h, the minimum speed limit vmin to 40 km/h, and the maximum speed limit vmax to 110 km/h. The congestion period is set to 3600 seconds. We uniformly discretize the free-flow speed within vmin and vmax. The examples differ with respect to the time window at the airport, the distance of the nodes, and the maximum ride time to guarantee feasibility. We assume that the capacity constraint is always satisfied given that the scheduling does not depend on the customer number. The parameters used to calculate the total cost function are the same as reported in Demir et al. [7]. Let SI and SD denote the solution of the time-independent approach and the time-dependent approach. For the computational results, the table reports cases in the first column. Then for each solution, the table reports (i) the set of traversed arcs, (ii) the distance of the arc, (iii) the speed at which each arc is traversed (for an arc traversed during the transient region, both the congestion speed and free-flow speed are reported), (iv) the departure time from the origin node, and (v) the total cost TC. The last row of Dep denotes the arrival time at the airport. All the mixed integer problems are solved by CPLEX 12.0 and all the time parameters given below are measured in seconds.Example 1 (u≤a).
In this example, the vehicle is in the all congestion period. The parameters are as follows:l=1084, u=2489, MRT1=657, and MRT2=541. The solutions to the time-independent and time-dependent approaches are displayed in Table 1.Table 1
Results in Example1.
Arc Dis S D S I Speed (m/s) Dep (s) TC (£) Speed (m/s) Dep (s) TC (£) (0,1) 6370 5.28 0 4.4925 21.91 648 1.7637 (1,2) 580 5.28 1207 0.4095 21.91 939 0.1610 (2,3) 2600 5.28 1317 1.8377 21.91 965 0.7238  Total   1810 6.7397  1084 2.6485Example 2 (l≤a≤u).
In this example, the vehicle is in the transient region; the vehicle leaving within this region traverses a distance of congestion period and then the vehicle travels the remaining (if exists) distance with the free-flow speed. The parameters are as follows:l=2929, u=4179, MRT1=2738, and MRT2=2814. The solutions are displayed in Table 2.Table 2
Results in Example2.
Arc Dis S D S I Speed (m/s) Dep (s) TC (£) Speed (m/s) Dep (s) TC (£) (0,1) 5117 5.28 2582 3.61 21.91 1877 1.42 (1,2) 5294 5.28, 30.56 3551 0.94 21.91 2110 1.47 (2,3) 12653 30.56 3765 4.07 21.91 2352 3.52  Total   4179 8.62  2929 6.41Example 3 (a≤l).
In this example, the vehicle arrives at the airport after the congestion period. The vehicle may firstly traverse a distance of congestion period and then the vehicle travels the remaining (if exists) distance with the free-flow speed. The parameters are as follows:l=4013, u=4179, MRT1=2738, and MRT2=251. The solutions are displayed in Table 3. We do not consider the case of all free-flow region as it is actually the time-independent approach.Table 3
Results in Example3.
Arc Dis S D S I Speed (m/s) Dep (s) TC (£) Speed (m/s) Dep (s) TC (£) (0,1) 5117 5.28, 30.56 2746 2.03 21.91 3160 1.42 (1,2) 8440 30.56 3677 2.72 21.91 3393 2.35 (2,3) 5104 30.56 3734 1.64 21.91 3780 1.42  Total   4179 6.39  4013 5.19From Tables1–3, we can see that the time-dependent approach yields a higher cost than the time-independent approach. The best speeds of the time-independent approach all exceed the congestion speed vc, which is not feasible in the congestion period. We conclude that congestion is likely to increase costs or even leads to an infeasible solution. Thus, the congestion should be considered in the study of the pollution routing of FPDS.From the last column of Tables2 and 3, we see that the vehicle arrives at the airport at the maximum of the time window in order to avoid the congestion. The vehicle will never wait even if the wait time is allowed, which is not compatible with the results of Franceschetti et al. [9]. The reason is that the time window is limited to the final destination airport instead of the pickup node and the maximum ride time of each order is constrained in our problem, which makes the optimal schedule delay the departure time and decrease the wait time so as to avoid the congestion and reduce the customers ride time.From the tables, we can see that the free-flow speeds in the time-dependent and time-independent approaches are the same in all the arcs. As a consequence, in the next section, we assume that the free-flow speed of a vehicle is the same even if it travels the different arc and provide a heuristic for the scheduling of a fixed route.


## 3.3. A Heuristic for DSP

In this section, we propose a heuristic for solving DSP. From Section3.2, we can see that the DSP can be solved by a mixed integer programming. However, solving the MIP in Section 3.1 requires considerable computational effort due to the large number of binary decision variables and the accuracy of the solution depends on the level of discretization of the free-flow speeds. To overcome these limitations, we propose a heuristic algorithm which, in our numerical experiments, has been observed to solve the problem at least as well as the MIP solutions in most cases we have considered.From the case study in Section3.2, we can see that the free-flow speeds do not change in the route. Accordingly, we assume that the free-flow speed is unchanged during the route (0,1,2,…,n,n+1). Then the DSP converts to scheduling the departure time and free-flow speed on a single arc with two nodes, the depot and the airport. This special case of a single arc network has been studied by Franceschetti et al. [9]. Our problem differs with the case of Franceschetti et al. [9] as there are maximum ride time constraints in the TDFPDS. We introduce a new speed function as the maximum ride speed together with the speed functions considered in Franceschetti et al. [9] to solve the DSP.In order to ensure the consistency and readability of the paper, we firstly give the speed functions used in Franceschetti et al. [9]. We convert route (0,1,2,…,n,n+1) to a new single arc (0,n+1), with the distance of d=∑i=0ndi and time window [l,u] denoting the time in which the vehicle should arrive at the airport.Letvwt be the free-flow speed required for the driver to arrive at node n+1 exactly at time t when leaving the depot at time w. Then (14)vwt=d-a-w+vct-max⁡a,w,ifw∈0,t,t>a,∞,otherwise.Thenvwu is the free-flow speed required for the driver to arrive at node n+1 exactly at time u when leaving the depot at time w. In other words, vwu is the minimum speed required to arrive at the airport which is less than or equal to u when u>a. vwl is the free-flow speed required for the driver to arrive at node n+1 exactly at time l when leaving the depot at time w and meanwhile is the maximum speed required to arrive at the airport which is greater than or equal to l when l>a.Letwmaxu denote the time at which the vehicle needs to depart from the depot to reach the node n+1 at exactly time u, with free-flow speed vmax. wmaxu is an upper bound on the departure time since the free-flow speed is no greater than vmax. If wmaxu<0, then the route is infeasible. Without loss of generality, we assume that wmaxu≥0 hereinafter.Lemma 4.
Consider a single arc instance to minimize the emission cost and driver wage cost in the absence of time window with fixed departure timew. The optimal free-flow speed is v¯=((fck1+fd)/(2fck2))1/3.Using Lemma4, we can reduce DSP to one-dimensional optimization problem; that is, we set w as the unique decision variable. Proof of Lemma 4 is given in Appendix A.We then consider the maximum ride time constraints. For each orderi(1≤i≤n) of route (0,1,2,…,n,n+1), the minimum speed without congestion to satisfy its maximum ride time constraint is vfreei=(∑j=indj)/MRTi. The minimum speed of the route is vfree=max1≤i≤n{vfreei}. If vfree>vmax, the route is infeasible and the algorithm is stopped. If vfree≤vc, which makes the maximum ride time constraints always feasible, the maximum ride time constraints are trivial and the results are given in Franceschetti et al. [9]. We set that vfree=vmin if vfree<vmin in Cases 2 and 3. We integrate the congestion period into computation. For each node i, let wridei denote the departure time from node 0 with free-flow speed vmax so that the vehicle travels from order i to the airport exactly for time MRTi, written as (15)wridei=a-∑j=indj-MRTivmaxvc-vmax-∑j=0i-1djvc.If wridei<0, we can see that the maximum ride time of order i is always feasible with free-flow speed vmax, in which case we set wridei=0. If wridei>wmaxu, the route is infeasible. The minimum departure time to meet the maximum ride time constraints is denoted as wride=max1≤i≤n{wridei}.Letvridei denote the free-flow speed required for the driver to travel from node i to node n+1 exactly for time MRTi when leaving the depot at time w. In other words, vridei is the minimum speed to meet the maximum ride time constraint of order i, which is written as follows: (16)vridei=∑j=indj-vca-w-∑j=0i-1dj/vc+MRTi-a-w-∑j=0i-1dj/vc+.Then the minimum free-flow speed to meet the maximum ride time constraints when leaving the depot at timew is denoted as vride=max1≤i≤nvridei. Figure 1(a) shows the minimum free-flow speed vride of a vehicle as a function of departure time w.Figure 1
Speed functions as a function ofw.
(a)
v r i d e (b)
v r i d e and vwu (c)
Three speed curvesThe calculation ofvride suggests that the planning horizon can be divided into two consecutive time regions in terms of the departure time w as follows. The first one wride≤w≤wfree is called the all decrease region: the vehicle leaving the depot within this region makes vride decrease all the time. The second one w>wfree is called the stable region: the vehicle leaving the depot within this region makes vride remain a constant.Lemma 5.
When the vehicle is leaving the depot within the all decrease region with free-flow speedvride, the emission cost and driver wage cost are monotonically decreasing with respect to the departure time w.Using Lemma5, the optimal departure time in the decrease region can be easily solved. Proof of Lemma 5 is given in Appendix A.We consider three cases: (1)l≤u≤a, (2) l≤a≤u, and (3) a<l<u.Case 1 (l≤u≤a).
In this case, the vehicle travels in the all congestion period. Ifvfree>vc, the maximum ride time constraint is infeasible. Otherwise, the vehicle travels with speed vc in the trip at any time w in [(l-d/vc)+,wmaxu]. The results of optimal departure time and the total cost are given in Appendix B.1.Case 2 (l≤a≤u).
In this case, the earliest time to arrive at the airport is less thana, which means that the vehicle travels with speed vc when arriving at the airport exactly at l. We conclude that wride≥(l-d/vc)+ since the vehicle arrives at the airport after a if leaving the depot at time wride. The feasible departure time belongs to [wride,wmaxu]. Figure 1(b) shows the minimum free-flow speed as a function of departure time w. Let wunion denote the intersection point of the speed curves vwu and vride. Then the calculation of the free-flow speed can be divided into two consecutive time regions in terms of the departure time w. In the first one wride≤w≤wunion, the feasible free-flow speed belongs to [vride,vmax]. In the second one wunion≤w≤wmaxu, the feasible free-flow speed belongs to [vwu,vmax].
The results of optimal departure time and the total cost are given in AppendixB.2.Case 3 (a<l<u).
In this case, the earliest time to arrive at the airport is greater thana, which makes the choice of the free-flow speed more complicated. vwl, as the maximum speed to arrive at the airport greater than or equal to l, also needs to be considered. Let wmaxl denote the time at which the vehicle needs to depart from the depot to reach the node n+1 at exactly time l, with free-flow speed vmax. If the condition wmaxl≤wride holds, which means that the maximum speed already reaches vmax, then vwl does not work and the feasible departure time belongs to [wride,wmaxu] which converts to Case 2. Otherwise, let wini denote the intersection point of the speed curves vwl and vride. Figure 1(c) shows the minimum free-flow speed and the maximum free-flow speed as functions of departure time w. The calculation of the minimum free-flow speed can be divided into two consecutive time regions in terms of the departure time w. In the first one wini≤w≤wunion, the feasible free-flow speed belongs to [vride,min{vwl,vmax}]. In the second one wunion≤w≤wmaxu, the feasible free-flow speed belongs to [vwu,min{vwl,vmax}].
The result of optimal departure time and the total cost is given in AppendixB.3.


## 4. A Set-Partitioning Method for Solving TDFPDS

This section presents a set-partitioning based method for solving TDFPDS following Dong et al. [10]. The set-partitioning method is a two-phase procedure. The candidate set of feasible routes is generated in the first phase and the set-partitioning model is solved to obtain the final solution in the second phase by using CPLEX 12.0 optimization software.In phase one, we firstly sort the orders in increasing sequence by their earliest delivery time. Each order is selected as the seed order by the sorted sequence. Then all the possible routes containing combinations of the seed order and the following orders to meet the time window and capacity constraints are generated. The feasibility check and scheduling of the route is conducted using the mixed integer programming or the heuristic for DSP in Sections3.1 and 3.3. If the feasible routes of the combinations are not single, the one with the least cost is selected to the candidate set. The candidate set of feasible routes is generated by looping all the orders. In phase two, the minimal cost set of best feasible routes is achieved as the optimal solution by solving the set-partitioning model.


## 5. Computational Results

This section presents the results of computational experiments using the mixed integer programming formulation and the heuristic for DSP in Sections3.1 and 3.3, HE and MIP for short hereafter, with the whole algorithm generated in Section 4. All tests were carried out using data generated randomly with orders 30, 40, and 50. Two service areas are considered, [-7km,7km]×[-4km,4km] and [-5.5km,5.5km]×[-4km,4km], with the depot located in the center of the area and the airport in top right corner of the region. The locations of all the orders are uniformly and independently distributed in the area. The delivery time is generated in two intervals, [0.5h,4h] and [0.5h,3h], to distinguish the different order intensity degree. For each of the orders 30,40,50, three instances, different in the service area and the delivery time factor intensity, are generated. The maximum ride time of order i is calculated as follows: MRTi=β1t1+β2t2, where t1 and t2 are the travel time in the congestion region and the travel time with free-flow speed vmax from the order directly to the airport and arriving at the airport exactly at Di. In Sections 5.1 and 5.2, set β1=1.1 and β2=1.5. In both instances, the congestion speed is set to 19km/h and vmin=40km/h. The same parameter values as in Demir et al. [7] have been used; that is, k1=1.0176×10-3, k2=1.4122×10-7, k3=8.4036×10-9, fc=1.4£/L, and fd=0.0022£/s. The curb weight μ is set to 1.5 ton and the average wight per person ν is set to 60 kg. The maximum free-flow speed vmax is set to 70km/h and 110km/h, respectively, to test the different cases of Appendix B. In a word, 18 different data sets are generated to test the performance of the algorithms. The whole algorithm is calculated on an Intel i5 PC computer running at 3.2 GHz with 4096 M of RAM memory. The first phase of the algorithm is coded with Matlab software.


### 5.1. Performance of the Heuristic

This section compares the performance of HE with MIP. We test all cases and propose the total cost and computation time with the two methods as the fixed route optimization procedure in Table4. Columns TCHE and TCMIP present the average total cost produced by the respective formulations and tHE and tMIP present the associated average computational times required to solve each type of instance. Column Dev presents the deviation between the two methods, computed as Dev=100(TCMIP-TCHE)/TCMIP. Column Num presents the number of cases in which TCHE≤TCMIP. Compared with MIP, HE is superior in terms of the computational time, especially in 50 node instances, with the average solution time reducing from 154.74 s to 0.41 s. HE also can solve 14 instances with better or equal results compared with MIP, in particular the 40 and 50 node instances. Even in the worst case, the deviation of the heuristic to the mix integer programming formulation is -1.2%, which is an acceptable result due to its efficient computation time.Table 4
Comparison with HE and MIP.
Ins T C H E (£) t H E (s) T C M I P (£) t M I P (s) Dev Num I30 62.87 0.09 62.89 8.32 0.02 5 I40 95.10 0.36 94.95 33.75 −0.15 4 I50 122.22 0.41 122.34 154.74 0.09 5


### 5.2. Importance of Modeling Traffic Congestion

In this section, we compare the results of cases with and without congestion. More specifically, by using HE as the fixed route optimization procedure, we compute two time-dependent optimal solutions with respect to congestion period duration of3600 s and 7200 s. Using MIP and fixing the congestion period to zero, we also compute a time-independent optimal solution. The results are provided in Table 5, where the total cost and the number of feasible routes (denoted by TC(N) and Num(N)) of time-independent problem and the total cost and number of feasible routes (denoted by TC and Num) using different peak hours are reported. The results show that in the presence of traffic congestion the total cost increases significantly and the number of feasible routes decreases, which imply that the congestion cannot be ignored in the actual situation. Ignoring the congestion period even obtains infeasible solutions. Furthermore the results also suggest that the cost is in a sharp increase and the number of feasible paths is significantly reduced with the increasing of congestion duration. It should be mentioned that the number of feasible routes does not decline substantially. This is because the maximum ride time also increases in the congestion period.Table 5
Effect of the congestion.
Ins TC(N) (£) Num(N) a = 3600 s a = 7200 s TC (£) Num TC (£) Num I30 54.57 148 62.87 139 94.48 135 I40 70.94 302 95.10 276 130.18 256 I50 91.95 742 123.81 555 181.97 477


### 5.3. Impact of the Maximum Ride Time Constraints

In this section, we study impact of the maximum ride time constraints. Four service quality scenarios “H,” “M,” “L,” and “N” constrained by maximum ride time are considered.β1 is set to 1.05, 1.1, and 1.2 and β2 is set to 1.3, 1.5, and 1.8 to denote the high, middle, and low ride time service, “H,” “M,” and “L” for short. Scenario “N” denotes the case without maximum ride time constraints. The congestion period is set to 3600 s. The results are provided in Table 6. Columns TC and Num present the average total cost and number of the feasible routes produced by the respective scenarios. Results suggest that the maximum ride time constraints significantly affect the solutions of TDFPDS both in the total cost and in the number of feasible routes. The total cost decreases and the number increases with the reduction of the service quality.Table 6
Impact of the maximum ride time constraints.
Ins H M L N TC (£) Num TC (£) Num TC (£) Num TC (£) Num I30 65.29 123 62.87 139 61.62 151 56.33 164 I40 98.24 221 95.10 276 94.40 309 87.39 350 I50 128.88 408 123.81 555 113.32 660 108.55 724


## 5.1. Performance of the Heuristic

This section compares the performance of HE with MIP. We test all cases and propose the total cost and computation time with the two methods as the fixed route optimization procedure in Table4. Columns TCHE and TCMIP present the average total cost produced by the respective formulations and tHE and tMIP present the associated average computational times required to solve each type of instance. Column Dev presents the deviation between the two methods, computed as Dev=100(TCMIP-TCHE)/TCMIP. Column Num presents the number of cases in which TCHE≤TCMIP. Compared with MIP, HE is superior in terms of the computational time, especially in 50 node instances, with the average solution time reducing from 154.74 s to 0.41 s. HE also can solve 14 instances with better or equal results compared with MIP, in particular the 40 and 50 node instances. Even in the worst case, the deviation of the heuristic to the mix integer programming formulation is -1.2%, which is an acceptable result due to its efficient computation time.Table 4
Comparison with HE and MIP.
Ins T C H E (£) t H E (s) T C M I P (£) t M I P (s) Dev Num I30 62.87 0.09 62.89 8.32 0.02 5 I40 95.10 0.36 94.95 33.75 −0.15 4 I50 122.22 0.41 122.34 154.74 0.09 5


## 5.2. Importance of Modeling Traffic Congestion

In this section, we compare the results of cases with and without congestion. More specifically, by using HE as the fixed route optimization procedure, we compute two time-dependent optimal solutions with respect to congestion period duration of3600 s and 7200 s. Using MIP and fixing the congestion period to zero, we also compute a time-independent optimal solution. The results are provided in Table 5, where the total cost and the number of feasible routes (denoted by TC(N) and Num(N)) of time-independent problem and the total cost and number of feasible routes (denoted by TC and Num) using different peak hours are reported. The results show that in the presence of traffic congestion the total cost increases significantly and the number of feasible routes decreases, which imply that the congestion cannot be ignored in the actual situation. Ignoring the congestion period even obtains infeasible solutions. Furthermore the results also suggest that the cost is in a sharp increase and the number of feasible paths is significantly reduced with the increasing of congestion duration. It should be mentioned that the number of feasible routes does not decline substantially. This is because the maximum ride time also increases in the congestion period.Table 5
Effect of the congestion.
Ins TC(N) (£) Num(N) a = 3600 s a = 7200 s TC (£) Num TC (£) Num I30 54.57 148 62.87 139 94.48 135 I40 70.94 302 95.10 276 130.18 256 I50 91.95 742 123.81 555 181.97 477


## 5.3. Impact of the Maximum Ride Time Constraints

In this section, we study impact of the maximum ride time constraints. Four service quality scenarios “H,” “M,” “L,” and “N” constrained by maximum ride time are considered.β1 is set to 1.05, 1.1, and 1.2 and β2 is set to 1.3, 1.5, and 1.8 to denote the high, middle, and low ride time service, “H,” “M,” and “L” for short. Scenario “N” denotes the case without maximum ride time constraints. The congestion period is set to 3600 s. The results are provided in Table 6. Columns TC and Num present the average total cost and number of the feasible routes produced by the respective scenarios. Results suggest that the maximum ride time constraints significantly affect the solutions of TDFPDS both in the total cost and in the number of feasible routes. The total cost decreases and the number increases with the reduction of the service quality.Table 6
Impact of the maximum ride time constraints.
Ins H M L N TC (£) Num TC (£) Num TC (£) Num TC (£) Num I30 65.29 123 62.87 139 61.62 151 56.33 164 I40 98.24 221 95.10 276 94.40 309 87.39 350 I50 128.88 408 123.81 555 113.32 660 108.55 724


## 6. Conclusions

In this paper, we have addressed a time-dependent pollution-routing and scheduling problem of free pickup and delivery of airline passengers to the airport faced by flight ticket sales companies. The problem is formulated under the framework of pollution-routing problem with time windows. The objective of the model is the emission cost and the driver wage cost, which proposes a reasonable calculation of the companies’ cost and the impact of the carbon emissions. Moreover, no examples could be found in the literature that simultaneously considered time-dependency and maximum ride time constraints in the VRP. A mixed integer linear programming formulation and a heuristic algorithm are then proposed for optimizing a given route.Through the experimental results, the mixed integer linear programming formulation produces optimal schedules with same travel free-flow speed in each arc of the route and without wait time. Then the heuristic is proposed according to the analysis of the experimental results. The heuristic combines the speed functions generated by the time windows and maximum ride time constraints and displays the optimal schedule in each case. Experimental results show the efficiency of the heuristic in total cost and computation time compared with the mixed integer linear programming formulation.On the other hand, the key technology of the heuristic lies in the conversion to a single arc path under the consumption that the service time of each order is neglected. In the calculation model, the parameters values of the carbon emissions are used directly from Demir et al. [7], which may not be the same with the vehicle considered in our problem. Moreover, if a fleet of vehicles is composed of several different types of vehicles, the proposed value should be modified. There is an opportunity for future research to develop a more efficient optimization strategy considering the service time and heterogeneous fleet and thereby extend the results of the present research.



---

*Source: 1918903-2017-01-10.xml*