# Carbon Footprint Management of Road Freight Transport under the Carbon Emission Trading Mechanism

Authors: Jin Li; Qihui Lu; Peihua Fu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Growing concern over environmental issues has considerably increased the number of regulations and legislation that aim to curb carbon emissions. Carbon emission trading mechanism, which is one of the most effective means, has been broadly adopted by several countries. This paper presents a road truck routing problem under the carbon emission trading mechanism. By introducing a calculation method of carbon emissions that considers the load and speed of the vehicle among other factors, a road truck routing optimizing model under the cap and trade mechanism based on the Travelling Salesman Problem (TSP) is described. Compared with the classical TSP model that only considers the economic cost, this model suggests that the truck routing decision under the cap and trade mechanism is more effective in reducing carbon emissions. A modified tabu search algorithm is also proposed to obtain solutions within a reasonable amount of computation time. We theoretically and numerically examine the impacts of carbon trading, carbon cap, and carbon price on truck routing decision, carbon emissions, and total cost. From the results of numerical experiments, we derive interesting observations about how to control the total cost and reduce carbon emissions.


---

## Body

## 1. Introduction

According to an assessment report [1] released by the Intergovernmental Panel on Climate Change, greenhouse gases mainly cause global warming and extreme weather, which gravely harm the ecosystem and human security. Greenhouse gases are principally generated from carbon emissions caused by human activities, such as fossil fuel burning in the production and transport sectors. To reduce the greenhouse gas emissions, the United Nations (UN), European Union (EU), and many other countries and organizations have adopted legislation and designed a variety of mechanisms for regulating the total amount of emissions. Carbon emission trading is one of the most cost effective market mechanisms broadly adopted by the UN, EU, and a number of countries. The European Union Emission Trading System (EU ETS) is by far the largest carbon market in the world, which implements a mandatory cap and trade system in the EU member countries. The number of emissions trading systems around the world is increasing. In addition to the EU ETS, national or subnational systems are already operating in Australia, Japan, New Zealand, and the United States and are planned in Canada, China, South Korea, and Switzerland [2]. To establish a domestic carbon emission trading system, China has launched its first regional market for compulsory carbon trading in the southern city of Shenzhen. Following Shenzhen, other carbon trading pilots have been initiated in six provinces and cities (e.g., Beijing, Tianjin, Shanghai, and Hubei).The environmental impact of freight transport operations has attracted great attention because it is a major source of carbon dioxide (CO2) emissions. According to a report by Stern [3], global transport is responsible for 14% of the total greenhouse gas emissions, and three-quarters of these emissions are from the road sector. In the United Kingdom, road freight transport accounts for 22% of the CO2 emissions from the transport sector or 6% of the CO2 emissions in the country [4]. The road freight transport in the United States constitutes 78% of the total transport emissions, and the percentage of total greenhouse gas emissions from the transport sector increased from 24.9% to 27.3% between 1900 and 2005 [5]. Similar figures appear in China, where road freight transport accounts for 30% of the CO2 emissions from the transport sector, the percentage of total transport carbon emissions has also increased in China in recent years. In the future, governments in the world are expected to implement comprehensive regulations on carbon emissions. First, to reduce carbon emissions, firms can use equipment facilities and vehicles with low energy consumption technologies. Second, they can make optimal operational decisions in the production, inventory, and transport sectors. Compared with the adoption of energy efficient technologies, the optimal operational decisions may be an effective and low cost approach to reduce carbon emissions [6]. Therefore, how does a government design a carbon emission trading mechanism to reduce carbon emissions? How do the firms consider the impact of carbon emissions on freight transport operations? These challenging and interesting research problems are the focus of this paper.Literature that considers carbon footprint management in supply chain management is sparse. A carbon footprint pertains to the total amount of greenhouse gas emissions produced directly and indirectly by an organization, event, product, or person and is typically expressed in equivalent tons (or kg) of carbon dioxide [7]. Several studies focus on the identification, measurement, and analysis methods of carbon emissions in the supply chain. For instance, Elhedhli and Merrick [8] considered a supply chain network design problem with emission cost and modeled the relationship between CO2 emissions and vehicle weight by investigating a concave minimization problem. Pattara et al. [9] introduced a standard and objective methodology and a related tool for calculating carbon footprint. They applied this tool to a wine supply chain by using the life cycle assessment (LCA) methodology. Rizet et al. [10] used a generic methodology to compare the energy consumption and CO2 emissions across the supply chains of products, supply chains, and countries. Lee [11] adopted a case study approach to investigate carbon emissions in automobile supply chain management. Sundarakani et al. [12] proposed an analytical and finite difference method to approximate a three-dimensional infinite carbon footprint model. Leonardi and Browne [13] focused on the maritime sector and developed a method for the calculation of the carbon footprint of international supply chains. In this paper, we consider the carbon footprint of road freight transport under the carbon emission trading mechanism.A few studies incorporated carbon emission regulations into the logistics and transport operations decisions. Kim et al. [14] examined the relationship between freight transport costs and carbon dioxide emissions in a given intermodal and truck-only freight networks using a multiobjective optimization technique. Suzuki [15] developed an approach to a time-constrained, multiple-stop, truck routing problem that minimizes the fuel consumption and pollutants emission. Hoen et al. [16] investigated the effect of two regulation mechanisms (i.e., emission cost and emission constraint) on the transport mode selection decision. They suggested that policy-makers should implement a constraint on freight transport emissions. Harris et al. [17] examined the impact of the traditional cost optimization approach to strategic modeling on overall logistics costs and the CO2 emissions by considering the supply chain structure and different freight vehicle utilization ratios. Tajik et al. [18] addressed a time window pick-up-delivery pollution routing problem and presented a new mixed integer programming approach under uncertainty. Different from these studies, we investigate the effect of the carbon emission trading mechanism on road freight transport.Several scholars attempted to study how to reduce fuel consumption and emissions in maritime, land, and air transport by optimizing speed on the routes [19–21]. For instance, Bektaş and Laporte [22] presented a pollution routing problem (PRP), which accounted not only the travel distance, but also the amount of greenhouse gas emissions, fuel, travel times, and their costs. They also investigated the tradeoffs between various parameters, such as vehicle load, speed, and total cost. Demir et al. [23] presented an adaptive large neighborhood search for the PRP. Demir et al. [24] reported the biobjective pollution routing problem with two conflicting objective functions pertaining to minimization of driving time and fuel. They also proposed an adaptive large neighborhood search algorithm to solve it. Jabali et al. [25] proposed a framework for modeling the CO2 emissions in a time-dependent vehicle routing context and solved the model via a tabu search procedure. They suggested that limiting vehicle speeds is desired from a total cost perspective. This paper mainly examines the operations decisions of road freight transport when managing the carbon footprints of a firm under the carbon emission trading mechanism.Studies on the operations decisions that consider the carbon emission trading mechanism are limited. Hua et al. [26] introduced an environmental inventory model under the cap and trade mechanism and derived the optimal order quantity and provided managerial insights. Klingelhöfer [27] examined the effects of emissions trading on investments in end-of-pipe-technologies by employing duality theory of linear programming and sensitivity analysis. Chaabane et al. [28] presented a mixed integer linear programming-based framework for sustainable supply chain design that considered life cycle assessment principles in addition to the traditional material balance constraints at each node in the supply chain. They suggested that current legislation and Emission Trading Schemes (ETS) must be strengthened and harmonized at the global level to derive a meaningful environmental strategy. Kwon et al. [29] studied heterogeneous fixed fleet vehicle routing with carbon emission, proposed a tabu search algorithm to solve the problem, and found that we could reduce the amount of carbon emission without sacrificing the cost due to the benefit obtained from carbon trading.To the best of our knowledge, few related studies on the road freight transport under the carbon emission trading mechanism have been found. Suggesting road transport firms to appropriately respond to carbon emission trading would be very helpful. Based on the classical Traveling Salesman Problem (TSP), we construct an environmental road freight transport model with regard to the cap and trade system. Comparing our model with the classical TSP model allows us to examine the effects of emission trading, carbon cap, and carbon price on freight routing decision, the amount of carbon emissions, and total cost. We employ the combination of theoretical and numerical analyses. We also expect to provide decision makers with managerial insights from the research observations.The remainder of this paper is organized as follows. This section consists of the introduction and relevant literature. Section2 describes the carbon footprint management problem of the road freight transport and formulates the environmental truck routing model under the cap and trade mechanism. In Section 3, we theoretically examine the effects of carbon emission trading on the freight operations decisions. Section 4 illustrates the modified tabu search algorithm for solving the proposed model and shows how the different components of the algorithm work together. In Section 5, we use the numerical analysis to investigate the impacts of emission trading, carbon cap, and carbon price on the freight routing decision, the amount of carbon emissions, and the total cost. Finally, Section 5 highlights the main findings and recommends directions for future research.


## 2. Model Formulation

In this paper, we adopt the TSP model to study a freight truck routing problem under the carbon emission trading mechanism. The carbon emission trading mechanism includes a cap and trade system, which is a market-based approach to control pollution. In the system, firms or national governments can trade emission allowances under an overall cap (or limit). Governmental authority typically sets the cap based on the total amount of carbon emissions. The cap is allocated or sold to firms in the form of carbon permits or credits, which represents the right to emit a specific carbon. The total number of permits cannot exceed the given cap, thereby limiting the total emissions to the objective level. The firm whose carbon emissions exceed its carbon cap must buy permits in the carbon trading market. Moreover, the firm that requires fewer permits can sell its surplus carbon permits. Thus, the buyer will pay a charge for emissions, whereas the seller will be rewarded for emission reduction. The cap and trade system can reduce overall emissions by rewarding the most efficient companies and providing less efficient companies with incentives to work toward more efficiency over time, while ensuring that nationwide emission limits can be met at the lowest economic cost. The carbon trading mechanism can ensure that the self-interest firm seeks the economic objective while considering the environmental objective.In this paper, we employ the TSP model to analyze the routing problem of a supplier under the carbon emissions trading mechanism. We assume that a truck sent by a supplier serves a set of its retailers starting from a distribution center, visits each retailer only once, and returns to the distribution center after serving all retailers. The product demand of each retailer is known and deterministic, and the total demand of all retailers does not exceed the capacity of the truck. The objective function of a supplier is to minimize the total cost consisting of fuel cost, truck usage cost (which depends on the usage time and includes depreciation cost, drivers salary, etc.), and carbon trading costs or gains.


### 2.1. Notations

In the following, we provide the notations and decision variables used in this paper:G=V,E, logistics distribution network;V, the set of nodes, V=0,1,…,n, where 0 represents the distribution center, and other nodes denote the retailers;E, the set of arcs, E=i,j∣i,j∈V,i≠j;dij, the travel distance on arc i,j, where i,j∈E;vij, the truck’s speed on arc i,j, where i,j∈E;cf, the unit cost of fuel;ch, the cost of truck’s usage per unit time;qi, the demand of retailer i, where i∈V∖{0};L, the truck’s capacity;P, carbon price per unit (kg);Q, carbon emission quotas during a planning period in the logistics distribution;xij, a binary decision variable; if a truck travels on arc i,j, then xij=1, otherwise xij=0, where i,j∈E;yij, a nonnegative decision variable; if a truck travels on arc i,j, then the truck’s load is yij>0, otherwise yij=0;Z, a real decision variable; it represents the transfer quantity of carbon emissions.R, the set of real numbers.


### 2.2. Calculation of Carbon Emissions

The calculation of transport carbon emissions is complex and depends on a number of factors, such as modes of transportation, fuel types, total weight of product, and distance traveled [12]. We introduce a calculation method of carbon emissions for road freight transport [16]. We assume that EMij is the amount of carbon emissions of the truck from node i to node j traveling through the arc i,j, which depends on the amount of fuel consumption FCij on the arc i,j and fuel emissions factor FE. The arc carbon emissions are calculated with the following equation:(1)EMij=FE·FCij.The fuel emissions FE factor is defined as the amount of carbon emissions per unit fuel (liter). It is a truck efficiency measure that converts fuel consumption into carbon emissions and is directly related to the vehicle type and fuel type used. For a practical logistics distribution, the fuel emissions factor is commonly a constant. According to the European carbon emission calculation criteria [16], the fuel emissions factor is set to be FE=2.62 kg/L.A number of related studies adopted the calculation method of fuel consumption by considering only the travel distance, which does not meet the actual condition and is inaccurate as well [14, 16]. In this paper, we comprehensively consider the impacts of distance, load, speed, and many other factors on fuel consumption. The total amount of fuel consumed FCij on the arc i,j is calculated as follows [22]:(2)FCij=αijw+yij+βvij2dij,where αij is an arc-specific constant associated with road gradient, acceleration, and rolling resistance, w is the empty vehicle weight, and β is a vehicle-specific constant relying on the air density, drag, and frontal surface area of the vehicle. In most cases, αij∈0.09,0.2, β is related to the vehicle type and set to be β=3.4 for the 20-ton truck used in our numerical experiments.


### 2.3. Decision Model

After considering the fuel and carbon emissions, we obtain the objective function of the supplierTC(X,Y,Z)=∑(i,j)∈E‍cfFCijxij+∑(i,j)∈E‍chdijxij/vij-PZ. With (1) and (2), we obtain the mixed integer programming model (denoted as MT model) of the supplier for the truck routing problem under the carbon emissions trading mechanism as follows:(3)min⁡TCX,Y,Z=∑i,j∈Ecfαijw+βvij2dijxij+∑i,j∈Ecfαijdijyij+∑i,j∈Echdijxijvij-PZ,(4)s.t.∑i∈Vxij=1,∀j∈V,(5)∑j∈Vxij=1,∀i∈V,(6)∑j∈Vyji-∑j∈Vyij=qi,∀i∈V∖0,(7)qjxij≤yij≤L-qixij,∀i,j∈E,(8)FE∑i,j∈Eαijw+βvij2dijxij+∑i,j∈Eαijdijyij+Z=Q,(9)xij∈0,1,yij≥0,∀i,j∈E,Z∈R.The supplier aims to minimize the total cost function (3) that comprises three components, namely, fuel cost, truck usage cost, and carbon trading cost. Constraints (4) and (5) ensure that each retailer would be visited exactly once. Balance of flow is described by constraint (6), in which the flow is increased by the demand of each visited retailer. Constraint (7) guarantees that the total load of the truck would not exceed its capacity. The balance of carbon emissions is imposed by constraint (8), in which the amount of carbon emissions from the road freight transport plus the transfer quantity of carbon emissions equals the carbon emission quotas allocated to the firm. The decision variables are introduced in constraint (9), where X=xij and Y=yij are vectors composed of xij and yij, respectively, xij is binary variable, yij is nonnegative variable, and Z is a real variable. if Z>0, then the firm sells Z units of carbon permits to the carbon market, if Z<0, then the firm buys Z units of carbon permits from the carbon market, and if Z=0, then the firm does not conduct any carbon trading business.Now, we define two benchmark models. Without considering carbon emissions, a model denoted by MC with an objective function only minimizing economic costs is(10)min⁡TCX,Y=∑i,j∈Ecfαijw+βvij2dijxij+∑i,j∈Ecfαijdijyij+∑i,j∈Echdijxijvij,subject to constraints (4)–(7).The decision variables areX and Y, xij∈0,1, yij≥0, ∀(i,j)∈E.If the supplier only considers the carbon emission costs, then the decision problem is described as follows (denoted as ME model):(11)min⁡CEX,Y=FE∑i,j∈Eαijw+βvij2dijxij+∑i,j∈Eαijdijyij.The constraints and decision variables are similar to those in the MC model.Obviously, the MC and ME models are variations of the MT model which is the most general problem. In the MT, MC, and ME model, the optimal solution is denoted as(Xt,Yt,Zt), (Xc,Yc), and (Xe,Ye), the amount of carbon emissions is denoted as CEt, CEc, and CEe, and the total cost is denoted as TCt, TCc, and TCe, respectively. The following conditions evidently hold: CEt≥CEe, CEc≥CEe, and TCc≤TCe.


## 2.1. Notations

In the following, we provide the notations and decision variables used in this paper:G=V,E, logistics distribution network;V, the set of nodes, V=0,1,…,n, where 0 represents the distribution center, and other nodes denote the retailers;E, the set of arcs, E=i,j∣i,j∈V,i≠j;dij, the travel distance on arc i,j, where i,j∈E;vij, the truck’s speed on arc i,j, where i,j∈E;cf, the unit cost of fuel;ch, the cost of truck’s usage per unit time;qi, the demand of retailer i, where i∈V∖{0};L, the truck’s capacity;P, carbon price per unit (kg);Q, carbon emission quotas during a planning period in the logistics distribution;xij, a binary decision variable; if a truck travels on arc i,j, then xij=1, otherwise xij=0, where i,j∈E;yij, a nonnegative decision variable; if a truck travels on arc i,j, then the truck’s load is yij>0, otherwise yij=0;Z, a real decision variable; it represents the transfer quantity of carbon emissions.R, the set of real numbers.


## 2.2. Calculation of Carbon Emissions

The calculation of transport carbon emissions is complex and depends on a number of factors, such as modes of transportation, fuel types, total weight of product, and distance traveled [12]. We introduce a calculation method of carbon emissions for road freight transport [16]. We assume that EMij is the amount of carbon emissions of the truck from node i to node j traveling through the arc i,j, which depends on the amount of fuel consumption FCij on the arc i,j and fuel emissions factor FE. The arc carbon emissions are calculated with the following equation:(1)EMij=FE·FCij.The fuel emissions FE factor is defined as the amount of carbon emissions per unit fuel (liter). It is a truck efficiency measure that converts fuel consumption into carbon emissions and is directly related to the vehicle type and fuel type used. For a practical logistics distribution, the fuel emissions factor is commonly a constant. According to the European carbon emission calculation criteria [16], the fuel emissions factor is set to be FE=2.62 kg/L.A number of related studies adopted the calculation method of fuel consumption by considering only the travel distance, which does not meet the actual condition and is inaccurate as well [14, 16]. In this paper, we comprehensively consider the impacts of distance, load, speed, and many other factors on fuel consumption. The total amount of fuel consumed FCij on the arc i,j is calculated as follows [22]:(2)FCij=αijw+yij+βvij2dij,where αij is an arc-specific constant associated with road gradient, acceleration, and rolling resistance, w is the empty vehicle weight, and β is a vehicle-specific constant relying on the air density, drag, and frontal surface area of the vehicle. In most cases, αij∈0.09,0.2, β is related to the vehicle type and set to be β=3.4 for the 20-ton truck used in our numerical experiments.


## 2.3. Decision Model

After considering the fuel and carbon emissions, we obtain the objective function of the supplierTC(X,Y,Z)=∑(i,j)∈E‍cfFCijxij+∑(i,j)∈E‍chdijxij/vij-PZ. With (1) and (2), we obtain the mixed integer programming model (denoted as MT model) of the supplier for the truck routing problem under the carbon emissions trading mechanism as follows:(3)min⁡TCX,Y,Z=∑i,j∈Ecfαijw+βvij2dijxij+∑i,j∈Ecfαijdijyij+∑i,j∈Echdijxijvij-PZ,(4)s.t.∑i∈Vxij=1,∀j∈V,(5)∑j∈Vxij=1,∀i∈V,(6)∑j∈Vyji-∑j∈Vyij=qi,∀i∈V∖0,(7)qjxij≤yij≤L-qixij,∀i,j∈E,(8)FE∑i,j∈Eαijw+βvij2dijxij+∑i,j∈Eαijdijyij+Z=Q,(9)xij∈0,1,yij≥0,∀i,j∈E,Z∈R.The supplier aims to minimize the total cost function (3) that comprises three components, namely, fuel cost, truck usage cost, and carbon trading cost. Constraints (4) and (5) ensure that each retailer would be visited exactly once. Balance of flow is described by constraint (6), in which the flow is increased by the demand of each visited retailer. Constraint (7) guarantees that the total load of the truck would not exceed its capacity. The balance of carbon emissions is imposed by constraint (8), in which the amount of carbon emissions from the road freight transport plus the transfer quantity of carbon emissions equals the carbon emission quotas allocated to the firm. The decision variables are introduced in constraint (9), where X=xij and Y=yij are vectors composed of xij and yij, respectively, xij is binary variable, yij is nonnegative variable, and Z is a real variable. if Z>0, then the firm sells Z units of carbon permits to the carbon market, if Z<0, then the firm buys Z units of carbon permits from the carbon market, and if Z=0, then the firm does not conduct any carbon trading business.Now, we define two benchmark models. Without considering carbon emissions, a model denoted by MC with an objective function only minimizing economic costs is(10)min⁡TCX,Y=∑i,j∈Ecfαijw+βvij2dijxij+∑i,j∈Ecfαijdijyij+∑i,j∈Echdijxijvij,subject to constraints (4)–(7).The decision variables areX and Y, xij∈0,1, yij≥0, ∀(i,j)∈E.If the supplier only considers the carbon emission costs, then the decision problem is described as follows (denoted as ME model):(11)min⁡CEX,Y=FE∑i,j∈Eαijw+βvij2dijxij+∑i,j∈Eαijdijyij.The constraints and decision variables are similar to those in the MC model.Obviously, the MC and ME models are variations of the MT model which is the most general problem. In the MT, MC, and ME model, the optimal solution is denoted as(Xt,Yt,Zt), (Xc,Yc), and (Xe,Ye), the amount of carbon emissions is denoted as CEt, CEc, and CEe, and the total cost is denoted as TCt, TCc, and TCe, respectively. The following conditions evidently hold: CEt≥CEe, CEc≥CEe, and TCc≤TCe.


## 3. Theoretical Analysis for the Impacts of Carbon Trading Mechanism

In this section, we theoretically examine the impacts of carbon trade, carbon cap, and carbon price on truck routing decisions, carbon emissions, and total cost. We explore these complex parts through numerical experiments in the next section.Theorem 1.
For the MT model, given a fixed carbon priceP, no matter what the carbon cap Q changes, the road freight routing decisions (Xt,Yt,Zt) and the amount of carbon emissions CEt remain constant.Proof.
From carbon balance constraint (8) of the MT model, we can derive the following conditions:(12)Z=Q-FE∑i,j∈Eαijw+βvij2dijxij+∑i,j∈Eαijdijyij=Q-CEX,Y.
Substitute (12) into (3) and we have(13)min⁡TCX,Y,Z=TCX,Y-PZ=TCX,Y+P·CEX,Y-PQ.
The constraints are independent of the carbon capQ, and PQ is the constant term of the objective function. Thus, the carbon cap Q merely affects the total cost and exerts no impact on the road freight routing decisions (Xt,Yt,Zt) and the amount of carbon emissions CEt.According to Theorem1, taking into account the impacts of the variation of carbon cap on the transfer quantity of carbon emissions and total cost, we obtain the following corollaries. From (12) and (13), we can easily derive Corollary 2.Corollary 2.
For the MT model, given a fixed carbon price, then(1)
if the carbon capQ decreases, then the carbon transfer quantity Z would decrease and the total cost TCt would increase;(2)
if the carbon capQ increases, then the carbon transfer quantity Z would increase and the total cost TCt would decrease.Corollary 3.
For the MT model, given the existence of a thresholdQ0 of carbon cap and Q0=CEt,(1)
ifQ<Q0, then the firm should buy Q0-Q units of carbon permits;(2)
ifQ>Q0, then the firm should sell Q-Q0 units of carbon permits;(3)
ifQ=Q0, then the firm should not conduct the carbon trade.Proof.
From (12), let Z=Q-CEt and Q0=CEt. Set Z<0, Z>0, or Z=0, respectively, and the above conditions can be derived easily.Theorem1 shows that the carbon cap does not affect the road freight routing arrangement of the firm and is unrelated to the amount of carbon emissions. The reason is that the amount of carbon emissions merely depends on the carbon price, and we disregard the effect of carbon cap. However, this result does not imply that the cap and trade mechanism has no influence on reducing the carbon emissions. Actually, using a market trade system allows the cap and trade mechanism to control the total amount of carbon emissions in a region, country, or even the world; nevertheless, it does not guarantee that all of the firms could reduce their carbon emissions. Thus, several firms may maintain or even increase their carbon emissions. The carbon cap and trade mechanism affects the carbon price by curbing the total amount of carbon emissions and then affects the road freight distribution decision and the amount of carbon emissions of the firm. However, the carbon cap allocated to a single firm cannot affect the carbon price, and also cannot affect the firm’s routing decision and the amount of carbon emissions.Corollary2 provides an intuitive result. When the carbon cap decreases, the available carbon permits of the firm will decrease, and the firm has to buy carbon permits, thus undoubtedly increasing the total cost. In contrast, when the carbon cap increases, the available carbon permits of the firm will increase, and the firm will sell its extra carbon permits, thereby reducing the total cost. Corollary 3 indicates that the decision of the firm to conduct carbon trade relies on the carbon cap.Theorem 4.
In the comparison of the MT and MC models, the following results hold:(1)
CEt≤CEc;(2)
The upper bound ofTCt-TCc is PCEc-Q, and if Q≥CEc, then TCt≤TCc;(3)
If the transfer quantity of carbon emissionsZ<0, then TCt>TCc.Proof.
(
1
) From (13), we know, for all (X,Y), there is(14)TCXt,Yt,Zt≤TCX,Y,Z,TCXt,Yt+P·CEXt,Yt-PQ≤TCX,Y+P·CEX,Y-PQ,(15)CEXt,Yt-CEX,Y≤1PTCX,Y-TCXt,Yt.Specifically, let X=Xc, Y=Yc, then (15) can be reformulated as (16) in the following:(16)CEXt,Yt-CEXc,Yc≤1PTCXc,Yc-TCXt,Yt.
SinceTC(Xc,Yc)≤TC(Xt,Yt) and P>0, we have ΔCO2=CE(Xt,Yt)-CE(Xc,Yc)≤0; that is, CEt≤CEc.
(
2
) From (13), we know that ΔTC=TC(Xt,Yt,Zt)-TC(Xc,Yc)=TC(Xt,Yt)+P·CE(Xt,Yt)-PQ-TC(Xc,Yc). From (16), there is ΔTC≤PCE(Xc,Yc)-Q; that is, ΔTC≤PCEc-Q.
Notice that ifQ≥CEc, then ΔTC≤0. Thus, TCt≤TCc.
(
3
) When Z<0, from (13), we obtain TC(Xt,Yt,Zt)=TC(Xt,Yt)-PZt>TC(Xt,Yt)≥TC(Xc,Yc), so TCt>TCc.Theorem4(1) shows that the cap and trade mechanism can effectively guide the self-interest firm to reduce carbon emissions, which may fundamentally explain the extensive practical application of this mechanism. Theorem 4(2) implies that an upper bound exists for the incremental cost arising from the cap and trade mechanism, which is directly related to the carbon price and cap. When the carbon cap is more than a threshold value that equals the amount of carbon emissions of the MC model, the firm will sell its surplus carbon permits and thus reduce the total cost. When the carbon cap is less, our numerical experiments (see Table 2) indicate that the cap and trade mechanism usually will increase the total cost of the firm. Theorem 4(3) shows that when the firm buys the carbon permits, its total cost is bound to increase. However, our numerical experiments (see Table 2) indicate that when the firm sells carbon permits, its total cost usually decreases, and when the firm neither buys nor sells carbon permits, its total cost may remain constant or increase.From Theorem4, the firm would simultaneously reduce carbon emissions and total cost. Corollary 5 provided this result.Corollary 5.
WhenCEt≠CEc and Q>CEc, the firm under the cap and trade mechanism can simultaneously reduce carbon emissions and total cost.Proof.
From the proof of Theorem4(1), when CEt≠CEc, there is ΔCO2<0. From the proof of Theorem 4(2), when Q>CEc, ΔTC≤PCEc-Q<0. So the results hold.The MT, MC, and ME models are related to each other. After comparing these models, we obtain the following theorem.Theorem 6.
The following conditions hold:(1)
IfP=0, then Xt=Xc, Yt=Yc;(2)
IfP=+∞, then Xt=Xe, Yt=Ye;(3)
Ifch=0, then Xt=Xc=Xe, Yt=Yc=Ye;(4)
CEe≤CEt≤CEc.Proof.
(
1
) The MT model has one more carbon balance constraint than the MC model. From the proof of Theorem 1, substituting carbon balance constraint (8) into (13), the MT model will have constraints similar to those in the MC model, and the difference between these two models is simply the objective function. From (13), if P=0, then minTC(X,Y,Z)=TC(X,Y); thus Xt=Xc, Yt=Yc.
(
2
) From (15), if P=+∞, then CE(Xt,Yt)-CE(X,Y)≤0. In particular, let X=Xe, Y=Ye; we have CE(Xe,Ye)≤CE(Xt,Yt)≤CE(Xe,Ye), CE(Xt,Yt)=CE(Xe,Ye), so Xt=Xe, Yt=Ye.
(
3
) From (10), we obtain that(17)TCX,Y=cfFECEX,Y+ch∑i,j∈Edijxijvij.
Ifch=0, then minTC(X,Y)=cfCE(X,Y)/FE, so Xc=Xe, Yc=Ye.
From (13) and (17), we have that(18)TCX,Y,Z=TCX,Y+P·CEX,Y-PQ=cfFE+PCEX,Y+ch∑i,j∈Edijxijvij-PQ.
Ifch=0, then minTC(X,Y,Z)=cf/FE+PCE(X,Y)-PQ, where PQ is constant. So Xt=Xe, Yt=Ye.
We can summarize thatXt=Xc=Xe, Yt=Yc=Ye.
(
4
) From Theorem 4(1), we can derive the results easily.Theorem6((1) and (2)) are intuitive. With the carbon cap and trade mechanism, when the carbon permit is free, the firm will disregard the impacts of carbon emissions and adopt the road truck routing decisions that minimize its economic costs. Conversely, when the carbon permit is extremely expensive, to reduce the total costs, the firm will try its best to reduce carbon emissions and adopt the road truck routing decisions that minimize the amount of carbon emissions. Theorem 6(3) shows that when ch=0 (i.e., the total economic costs only contain the fuel cost), the economic objective of the firm is consistent with its environmental objective. The reason is that the fuel consumed directly affects carbon emissions. Therefore, the MT, MC, and ME models have the same truck routing solutions. Theorem 6(4) implies that the ME and MC models provide lower and upper bounds for carbon emissions. The MT model includes both economic and environmental objective and induces medium carbon emissions.


## 4. A Tabu Search Algorithm

Tabu search (TS) is an iterated local search metaheuristic. It makes use of adaptive memory to guide the search to escape local optima. The algorithm has been successfully used for solving many classes of TSPs and VRPs [29–31]. The TS algorithm starts from an initial solution x0 and tries to make the best possible moves to generate a new solution x′ in the neighborhood N(x) of the current solution x even if the move may worsen the objective function value. To avoid cycling over a sequence of solutions, a set of moves are temporarily forbidden in a tabu list. The aspiration criterion is used to revoke tabu status of some moves if they create a solution better than the current best solution.We propose a tabu search (TS) procedure for the MT model and use most of the important TS concepts in the following: tabu list, tabu tenure, aspiration criteria, neighbourhood and moves, and so forth. Next, the main components of the algorithm are described.


### 4.1. Initial Solution Generation

The initial solution is obtained as follows. First, the tour starts with the depot and each time a customer with the greatest demand from the set of unassigned node is selected and then inserted into the tour using the GENI algorithm presented by Gendreau et al. [32]. Finally, after all nodes are assigned, the solution is improved using the 3-opt heuristic [33].


### 4.2. Neighbourhood Structure and Tabu Rules

Neighborhood operators are applied to explore the neighborhood of the current solution and to produce set of admissible candidate solutions. We consider four different neighborhood operators, that is, Or-opt, 2-opt, Exchange, and Reverse which are shown in Figure1. In our TS scheme, the best improving (or least nonimproving) feasible move is chosen after performing each cycle of neighborhood search.Figure 1
Neighborhoods of the TS algorithm.The Or-opt scheme involves removing one, two, or three adjacent retailers and inserting them in another position of the route. Figure1(b) shows the adjacent retailers 2 and 3 are reinserted in another position of the route.The 2-opt is to delete two nonadjacent arcs and add another two to generate a new route. Figure1(c) shows the arcs (2,3) and (5,6) are deleted while the arcs (2,5) and (3,6) are added.The Exchange operator swaps two retailers of the route. It realizes the permutation between two retailers. In Figure1(d), the retailers 2 and 5 are swapped.The Reverse movement involves reversing the route direction. Figure1(e) shows the directions of all the arcs are reversed.The computational complexity of the neighborhoods Or-opt, 2-opt, and Exchange iso(n2) while the computational complexity of Reverse is o(n).The tabu status of a move is set in the following way: if a nodei is removed from a position of the route, it cannot return to it during the next l iterations, where l is the tabu tenure. We adopt the random tabu tenure; that is, l is randomly selected between [lmin,lmax]. However, we use an aspiration criterion: the tabu status of a move is revoked if it produces a solution that is better than the ones found in the past.


### 4.3. Restart Strategy and Perturbation Mechanism

To avoid a solution stagnating in a local optimal area, we consider a restart strategy which chooses a new solution as current solution for proceeding the search. If the best-so-far solutionx∗ is not improved within Ir iterations, the TS algorithm chooses the solution x∗ as the current solution, makes the tabu list empty, and exploits the search experience to lead the search escaping from local optimal.To change the search direction, we consider a perturbation mechanism to explore more search spaces. Similar to the strategies used in Cordeau and Maischberger [30], our TS algorithm randomly chooses two operators to implement from the four neighborhoods (Or-opt, 2-opt, Exchange, and Reverse) to diversify the search.


### 4.4. Termination Condition

The maximum total number of iterations for the TS algorithm isImax. However, if a best solution is found when the remaining number of iterations is less than ψ, the remaining number of iterations is changed to be 2ψ.


### 4.5. Detailed Description of the TS

The detailed procedure of the TS algorithm is listed in the following.Step 1.
Generate the initial solutionx0. Set the initial parameters of the algorithm: limit of the total number of iterations Imax, limit of number of iterations without improving the best solution Ir, and the threshold ψ of updating Imax, set the iteration counter of the whole algorithm t=0, set the iteration counter without improving the best solution tr=0, set the best solution x∗=x0, set the current solution x=x0, and empty the tabu list.Step 2.
Repeat while the stopping criterion (t>Imax) is not met.Step 2.1. Generate the neighborhood of x by performing the movements Or-opt, 2-opt, Exchange, and Reverse in sequence, choose the solution x′ that minimizes the total cost and is not tabu or satisfies its aspiration criteria, update the tabu list, and set t=t+1.Step 2.2. If x′ is better than the current best solution x∗, then update the best solution, that is, x∗=x′, and set tr=0; else set tr=tr+1.Step 2.3. If tr>Ir, then restart, empty tabu list, and perform two neighborhood operators randomly selected from the neighborhoods Or-opt, 2-opt, Exchange, and Reverse to change the current search direction.Step 2.4. If a new best solution is found and Imax-t<ψ, then set Imax=t+2ψ, tr=0.Step 2.5. Update x to x′; that is, x=x′.Step 3.
Return the best solutionx∗.


## 4.1. Initial Solution Generation

The initial solution is obtained as follows. First, the tour starts with the depot and each time a customer with the greatest demand from the set of unassigned node is selected and then inserted into the tour using the GENI algorithm presented by Gendreau et al. [32]. Finally, after all nodes are assigned, the solution is improved using the 3-opt heuristic [33].


## 4.2. Neighbourhood Structure and Tabu Rules

Neighborhood operators are applied to explore the neighborhood of the current solution and to produce set of admissible candidate solutions. We consider four different neighborhood operators, that is, Or-opt, 2-opt, Exchange, and Reverse which are shown in Figure1. In our TS scheme, the best improving (or least nonimproving) feasible move is chosen after performing each cycle of neighborhood search.Figure 1
Neighborhoods of the TS algorithm.The Or-opt scheme involves removing one, two, or three adjacent retailers and inserting them in another position of the route. Figure1(b) shows the adjacent retailers 2 and 3 are reinserted in another position of the route.The 2-opt is to delete two nonadjacent arcs and add another two to generate a new route. Figure1(c) shows the arcs (2,3) and (5,6) are deleted while the arcs (2,5) and (3,6) are added.The Exchange operator swaps two retailers of the route. It realizes the permutation between two retailers. In Figure1(d), the retailers 2 and 5 are swapped.The Reverse movement involves reversing the route direction. Figure1(e) shows the directions of all the arcs are reversed.The computational complexity of the neighborhoods Or-opt, 2-opt, and Exchange iso(n2) while the computational complexity of Reverse is o(n).The tabu status of a move is set in the following way: if a nodei is removed from a position of the route, it cannot return to it during the next l iterations, where l is the tabu tenure. We adopt the random tabu tenure; that is, l is randomly selected between [lmin,lmax]. However, we use an aspiration criterion: the tabu status of a move is revoked if it produces a solution that is better than the ones found in the past.


## 4.3. Restart Strategy and Perturbation Mechanism

To avoid a solution stagnating in a local optimal area, we consider a restart strategy which chooses a new solution as current solution for proceeding the search. If the best-so-far solutionx∗ is not improved within Ir iterations, the TS algorithm chooses the solution x∗ as the current solution, makes the tabu list empty, and exploits the search experience to lead the search escaping from local optimal.To change the search direction, we consider a perturbation mechanism to explore more search spaces. Similar to the strategies used in Cordeau and Maischberger [30], our TS algorithm randomly chooses two operators to implement from the four neighborhoods (Or-opt, 2-opt, Exchange, and Reverse) to diversify the search.


## 4.4. Termination Condition

The maximum total number of iterations for the TS algorithm isImax. However, if a best solution is found when the remaining number of iterations is less than ψ, the remaining number of iterations is changed to be 2ψ.


## 4.5. Detailed Description of the TS

The detailed procedure of the TS algorithm is listed in the following.Step 1.
Generate the initial solutionx0. Set the initial parameters of the algorithm: limit of the total number of iterations Imax, limit of number of iterations without improving the best solution Ir, and the threshold ψ of updating Imax, set the iteration counter of the whole algorithm t=0, set the iteration counter without improving the best solution tr=0, set the best solution x∗=x0, set the current solution x=x0, and empty the tabu list.Step 2.
Repeat while the stopping criterion (t>Imax) is not met.Step 2.1. Generate the neighborhood of x by performing the movements Or-opt, 2-opt, Exchange, and Reverse in sequence, choose the solution x′ that minimizes the total cost and is not tabu or satisfies its aspiration criteria, update the tabu list, and set t=t+1.Step 2.2. If x′ is better than the current best solution x∗, then update the best solution, that is, x∗=x′, and set tr=0; else set tr=tr+1.Step 2.3. If tr>Ir, then restart, empty tabu list, and perform two neighborhood operators randomly selected from the neighborhoods Or-opt, 2-opt, Exchange, and Reverse to change the current search direction.Step 2.4. If a new best solution is found and Imax-t<ψ, then set Imax=t+2ψ, tr=0.Step 2.5. Update x to x′; that is, x=x′.Step 3.
Return the best solutionx∗.


## 5. Numerical Experiments

### 5.1. Numerical Settings

In this section, we present a series of numerical examples to illustrate the aforementioned analytical results and simultaneously investigate the impacts of carbon cap and carbon price on road truck routing decisions, the amount of carbon emissions, and total cost and provide interesting observations. Our experiments will run with the data generated as realistically as possible. The logistics distribution network is an intercity network consisting of 20 city nodes in five provinces or cities in China (i.e., Shanghai, Zhejiang, Jiangsu, Anhui, and Jiangxi provinces). Shanghai was selected as the distribution center, and the retailers were located in other cities. The relative coordinates of these 20 nodes are shown in Table1. The distance dij between two nodes (xi,yi) and (xj,yj) is defined as the Euclidean distance; namely, dij=(xi-xj)2+(yi-yj)2.Table 1
Relative coordinates of city nodes in an intercity logistics distribution network in China.
Cities
X (km)
Y (km)
Shanghai
4177
2244
Lianyungang
3929
1892
Nanjing
3918
2179
Wuxi
4062
2220
Xuzhou
3751
1945
Yangzhou
3972
2136
Hangzhou
4061
2370
Jiaojiang
4207
2533
Jinhua
4029
2498
Ningbo
4201
2397
Wenzhou
4139
2615
Anqing
3766
2364
Bengbu
3777
2095
Hefei
3780
2212
Huangshan
3896
2443
Wuhu
3888
2261
Yingtan
3789
2620
Jingdezhen
3796
2499
Jiujiang
3678
2463
Nanchang
3676
2578Table 2
Results of experiments from the MT and MC models.
n
TC
c
StdTC
c
CE
c
Q
TC
t
StdTC
t
CE
t
Δ
CO
2
ΔTC
CPU (s)
10
3103.95
5.21
843.46
800
3234.33
4.87
843.46
0
130.38
7
843.46
3103.95
5.13
843.46
0
0
8
850
3084.34
4.92
843.46
0
−19.62
6
900
2934.34
6.07
843.46
0
−169.62
7
15
3804.27
7.17
1064.74
1000
3976.06
7.51
1050.14
−14.60
171.79
16
1050
3826.06
6.86
1050.14
−14.60
21.79
17
1050.14
3825.64
7.38
1050.14
−14.60
21.37
15
1100
3676.06
7.55
1050.14
−14.60
−128.21
16
20
4808.98
10.57
1365.76
1300
5000.47
9.26
1354.63
−11.13
191.48
24
1350
4850.47
9.78
1354.63
−11.13
41.48
21
1354.63
4836.58
11.23
1354.63
−11.13
27.59
24
1400
4700.47
10.35
1354.63
−11.13
−108.51
25The demand of each retailer is an integer randomly generated in interval500,5000 (kg). A truck with capacity L=20 tons and empty vehicle weight w=20 tons is used to complete the deliveries of all retailers. The parameters related to the measure of the carbon emissions of the truck are set as [22] αij=0.15, β=3.4, FE=2.62 kg/L, P=3 CNY/kg, Q=1000 kg, cf=7.0 CNY/L, and ch=30 CNY/h. The speed vij on each arc i,j∈E is an integer randomly generated in interval 40,100 (km/h). The delivery trucks seldom visit more than 20 retailers per tour in a practical logistics distribution [15]; hence, we limit the problem sizes to n≤20.Based on the above data, we generate three classes of problems with the number of the retailers in each class beingn=10, 15, and 20, respectively. Each class of problem includes 60 examples generated randomly, in which the total demand of the retailers in each instance does not exceed the capacity of the truck, and the test results are calculated from the average value across these 60 examples.We used the TS algorithm to solve the proposed mixed linear integer programming models. The TS algorithm is coded in C language and compiled on VC++8.0. All the experiments are conducted on a server with CPU P8400 1.58 GHz PC under Windows 8. In terms of preliminary experiments, the parameters chosen for the TS algorithm are summarized in the following:Imax=700, Ir=100, ψ=150, lmin=15, and lmax=25.


### 5.2. Impacts of Carbon Trading on Road Tuck Routing Decisions

In this section, we consider the impacts of carbon trading on truck routing decisions. In the numerical analysis, we compare the results between the MT and MC models in Table2. To examine the relationships between total cost and carbon emissions of the ME, MC, and MT models, the results of experiments for these models are shown in Table 3. The last column listed in Table 2 reports the average computational time (CPU) over 60 trials. The columns StdTCe,StdTCc, and StdTCt of Tables 2 and 3 also show the standard deviation of the total cost across the 60 examples for ME, MC, and MT models, respectively. The data in Tables 2 and 3 verify the theoretical findings.Table 3
Comparisons of the total cost and carbon emissions from the ME, MC, and MT models.
n
TC
e
StdTC
e
TC
c
StdTC
c
TC
t
StdTC
t
CE
e
CE
c
CE
t
10
3179.27
5.18
3103.95
6.25
2634.33
4.87
820.49
843.46
843.46
15
3825.64
7.22
3804.27
7.39
3976.06
6.95
1050.14
1064.74
1050.14
20
5001.47
10.35
4809.98
9.73
5900.47
10.76
1349.07
1365.76
1354.63
Ave.
4002.13
7.58
3905.74
7.79
4170.29
7.53
1073.24
1091.32
1082.74


### 5.3. Impacts of Carbon Cap and Carbon Price on Carbon Emissions and Total Cost

In this section, we analyze the impacts of carbon cap on the carbon emissions and total cost. To this end, for each class of problems with different numbers of nodes, we select six parameter values of the carbon capQ and calculate the amount of carbon emissions and the total cost of various instances based on different carbon caps (see Figure 2). Figure 2 shows that the carbon cap does not affect the carbon emissions of the firm in the three classes of problems with n=10, 15, and 20. The total cost will decrease whereas the carbon cap allocated to the firm will increase. Interestingly, the carbon cap is a key resource in the cap and trade mechanism, which directly affects the cost of the firm. When the firm has more carbon caps, it will save more costs and vice versa.Figure 2
Effects of carbon cap on the carbon emissions and total cost.
(a)
(b)
(c)To examine the impacts of carbon price on the carbon emissions and total cost, we only analyze the data of the 10-node problem. The total cost is related to the carbon cap; thus, we discuss the impacts of carbon price on the carbon emissions and total cost considering five scenarios of carbon caps (Figure3): (1)  Q<CEe; (2)  Q=CEe; (3)  CEe<Q<CEc; (4)  Q=CEc; and (5)  Q>CEc. The carbon prices are set from 1 to 10.Figure 3
Effects of carbon price on the carbon emissions and total cost.
(a)
n
=
10; Q=CEe
(b)
n
=
10; Q<CEe
(c)
n
=
10; CEe<Q<CEc
(d)
n
=
10; Q=CEc
(e)
n
=
10; Q>CEc
(f)
n
=
20; Q>CEcFigure3 shows that the carbon emissions follow a “ladder-shaped” decreasing curve when the carbon price increases. The reason is that the higher the carbon price, the higher the cost paid by the firm to emit carbon or buy carbon permits; hence, the firm will exert efforts to decrease the carbon emissions or buy less carbon permits to reduce the total cost. The appearance of the curve of carbon emissions in the shape of a ladder with a decreasing tendency is attributed to the capacity of the firm to reduce the total cost more than the carbon emissions-minimizing ones in low-carbon price by adopting the economic cost-minimizing truck routing strategies. In high carbon price, saving the total cost by adopting the truck routing strategies that keep the carbon emissions as low as possible is a better approach to the firm. Meanwhile, the carbon emissions of the firm will decrease in a step-down manner (e.g., when P≥4 in this experiment) only when the carbon price surpasses a threshold; the firm makes the truck routing decisions that minimize carbon emissions, which forms the ladder-type curve that declines only after the carbon price reaches a threshold.Figure3 illustrates five types of curves of the total cost relative to the carbon price; namely, (1) the total cost initially increases sharply, and then the incremental value decreases; (2) the total cost initially increases and then remains constant; (3) the total cost initially increases and then decreases; (4) the total cost initially remains constant and then decreases; and (5) the total cost initially decreases, and then the decrement value increases. Interestingly, the inflection point of the total cost curve is at the threshold of the carbon price. Therefore, we can conclude that the total cost of the firm depends on the carbon cap.Figure3(f) reports the results of the impacts of carbon price on the carbon emissions and total cost when n=20 and Q>CEc. The carbon emissions curve is likewise in a decreasing ladder shape and has several thresholds of the carbon price. The curve of the total cost still has a declining trend, and the decrement value increases when the carbon price exceeds several thresholds. The implication is that, for the problems with more nodes, the curve of carbon emissions still has a significant ladder-type declining trend, and the curve of the total cost depends on the carbon cap. Another interesting observation is that the conditions of simultaneously reducing the total cost and carbon emissions is Q>CEe and P≥P0, where P0 is the initial threshold of carbon price.


## 5.1. Numerical Settings

In this section, we present a series of numerical examples to illustrate the aforementioned analytical results and simultaneously investigate the impacts of carbon cap and carbon price on road truck routing decisions, the amount of carbon emissions, and total cost and provide interesting observations. Our experiments will run with the data generated as realistically as possible. The logistics distribution network is an intercity network consisting of 20 city nodes in five provinces or cities in China (i.e., Shanghai, Zhejiang, Jiangsu, Anhui, and Jiangxi provinces). Shanghai was selected as the distribution center, and the retailers were located in other cities. The relative coordinates of these 20 nodes are shown in Table1. The distance dij between two nodes (xi,yi) and (xj,yj) is defined as the Euclidean distance; namely, dij=(xi-xj)2+(yi-yj)2.Table 1
Relative coordinates of city nodes in an intercity logistics distribution network in China.
Cities
X (km)
Y (km)
Shanghai
4177
2244
Lianyungang
3929
1892
Nanjing
3918
2179
Wuxi
4062
2220
Xuzhou
3751
1945
Yangzhou
3972
2136
Hangzhou
4061
2370
Jiaojiang
4207
2533
Jinhua
4029
2498
Ningbo
4201
2397
Wenzhou
4139
2615
Anqing
3766
2364
Bengbu
3777
2095
Hefei
3780
2212
Huangshan
3896
2443
Wuhu
3888
2261
Yingtan
3789
2620
Jingdezhen
3796
2499
Jiujiang
3678
2463
Nanchang
3676
2578Table 2
Results of experiments from the MT and MC models.
n
TC
c
StdTC
c
CE
c
Q
TC
t
StdTC
t
CE
t
Δ
CO
2
ΔTC
CPU (s)
10
3103.95
5.21
843.46
800
3234.33
4.87
843.46
0
130.38
7
843.46
3103.95
5.13
843.46
0
0
8
850
3084.34
4.92
843.46
0
−19.62
6
900
2934.34
6.07
843.46
0
−169.62
7
15
3804.27
7.17
1064.74
1000
3976.06
7.51
1050.14
−14.60
171.79
16
1050
3826.06
6.86
1050.14
−14.60
21.79
17
1050.14
3825.64
7.38
1050.14
−14.60
21.37
15
1100
3676.06
7.55
1050.14
−14.60
−128.21
16
20
4808.98
10.57
1365.76
1300
5000.47
9.26
1354.63
−11.13
191.48
24
1350
4850.47
9.78
1354.63
−11.13
41.48
21
1354.63
4836.58
11.23
1354.63
−11.13
27.59
24
1400
4700.47
10.35
1354.63
−11.13
−108.51
25The demand of each retailer is an integer randomly generated in interval500,5000 (kg). A truck with capacity L=20 tons and empty vehicle weight w=20 tons is used to complete the deliveries of all retailers. The parameters related to the measure of the carbon emissions of the truck are set as [22] αij=0.15, β=3.4, FE=2.62 kg/L, P=3 CNY/kg, Q=1000 kg, cf=7.0 CNY/L, and ch=30 CNY/h. The speed vij on each arc i,j∈E is an integer randomly generated in interval 40,100 (km/h). The delivery trucks seldom visit more than 20 retailers per tour in a practical logistics distribution [15]; hence, we limit the problem sizes to n≤20.Based on the above data, we generate three classes of problems with the number of the retailers in each class beingn=10, 15, and 20, respectively. Each class of problem includes 60 examples generated randomly, in which the total demand of the retailers in each instance does not exceed the capacity of the truck, and the test results are calculated from the average value across these 60 examples.We used the TS algorithm to solve the proposed mixed linear integer programming models. The TS algorithm is coded in C language and compiled on VC++8.0. All the experiments are conducted on a server with CPU P8400 1.58 GHz PC under Windows 8. In terms of preliminary experiments, the parameters chosen for the TS algorithm are summarized in the following:Imax=700, Ir=100, ψ=150, lmin=15, and lmax=25.


## 5.2. Impacts of Carbon Trading on Road Tuck Routing Decisions

In this section, we consider the impacts of carbon trading on truck routing decisions. In the numerical analysis, we compare the results between the MT and MC models in Table2. To examine the relationships between total cost and carbon emissions of the ME, MC, and MT models, the results of experiments for these models are shown in Table 3. The last column listed in Table 2 reports the average computational time (CPU) over 60 trials. The columns StdTCe,StdTCc, and StdTCt of Tables 2 and 3 also show the standard deviation of the total cost across the 60 examples for ME, MC, and MT models, respectively. The data in Tables 2 and 3 verify the theoretical findings.Table 3
Comparisons of the total cost and carbon emissions from the ME, MC, and MT models.
n
TC
e
StdTC
e
TC
c
StdTC
c
TC
t
StdTC
t
CE
e
CE
c
CE
t
10
3179.27
5.18
3103.95
6.25
2634.33
4.87
820.49
843.46
843.46
15
3825.64
7.22
3804.27
7.39
3976.06
6.95
1050.14
1064.74
1050.14
20
5001.47
10.35
4809.98
9.73
5900.47
10.76
1349.07
1365.76
1354.63
Ave.
4002.13
7.58
3905.74
7.79
4170.29
7.53
1073.24
1091.32
1082.74


## 5.3. Impacts of Carbon Cap and Carbon Price on Carbon Emissions and Total Cost

In this section, we analyze the impacts of carbon cap on the carbon emissions and total cost. To this end, for each class of problems with different numbers of nodes, we select six parameter values of the carbon capQ and calculate the amount of carbon emissions and the total cost of various instances based on different carbon caps (see Figure 2). Figure 2 shows that the carbon cap does not affect the carbon emissions of the firm in the three classes of problems with n=10, 15, and 20. The total cost will decrease whereas the carbon cap allocated to the firm will increase. Interestingly, the carbon cap is a key resource in the cap and trade mechanism, which directly affects the cost of the firm. When the firm has more carbon caps, it will save more costs and vice versa.Figure 2
Effects of carbon cap on the carbon emissions and total cost.
(a)
(b)
(c)To examine the impacts of carbon price on the carbon emissions and total cost, we only analyze the data of the 10-node problem. The total cost is related to the carbon cap; thus, we discuss the impacts of carbon price on the carbon emissions and total cost considering five scenarios of carbon caps (Figure3): (1)  Q<CEe; (2)  Q=CEe; (3)  CEe<Q<CEc; (4)  Q=CEc; and (5)  Q>CEc. The carbon prices are set from 1 to 10.Figure 3
Effects of carbon price on the carbon emissions and total cost.
(a)
n
=
10; Q=CEe
(b)
n
=
10; Q<CEe
(c)
n
=
10; CEe<Q<CEc
(d)
n
=
10; Q=CEc
(e)
n
=
10; Q>CEc
(f)
n
=
20; Q>CEcFigure3 shows that the carbon emissions follow a “ladder-shaped” decreasing curve when the carbon price increases. The reason is that the higher the carbon price, the higher the cost paid by the firm to emit carbon or buy carbon permits; hence, the firm will exert efforts to decrease the carbon emissions or buy less carbon permits to reduce the total cost. The appearance of the curve of carbon emissions in the shape of a ladder with a decreasing tendency is attributed to the capacity of the firm to reduce the total cost more than the carbon emissions-minimizing ones in low-carbon price by adopting the economic cost-minimizing truck routing strategies. In high carbon price, saving the total cost by adopting the truck routing strategies that keep the carbon emissions as low as possible is a better approach to the firm. Meanwhile, the carbon emissions of the firm will decrease in a step-down manner (e.g., when P≥4 in this experiment) only when the carbon price surpasses a threshold; the firm makes the truck routing decisions that minimize carbon emissions, which forms the ladder-type curve that declines only after the carbon price reaches a threshold.Figure3 illustrates five types of curves of the total cost relative to the carbon price; namely, (1) the total cost initially increases sharply, and then the incremental value decreases; (2) the total cost initially increases and then remains constant; (3) the total cost initially increases and then decreases; (4) the total cost initially remains constant and then decreases; and (5) the total cost initially decreases, and then the decrement value increases. Interestingly, the inflection point of the total cost curve is at the threshold of the carbon price. Therefore, we can conclude that the total cost of the firm depends on the carbon cap.Figure3(f) reports the results of the impacts of carbon price on the carbon emissions and total cost when n=20 and Q>CEc. The carbon emissions curve is likewise in a decreasing ladder shape and has several thresholds of the carbon price. The curve of the total cost still has a declining trend, and the decrement value increases when the carbon price exceeds several thresholds. The implication is that, for the problems with more nodes, the curve of carbon emissions still has a significant ladder-type declining trend, and the curve of the total cost depends on the carbon cap. Another interesting observation is that the conditions of simultaneously reducing the total cost and carbon emissions is Q>CEe and P≥P0, where P0 is the initial threshold of carbon price.


## 6. Conclusion

The low-carbon development of logistics and transport has become an inevitable trend. A number of firms in the world confront an emerging problem of how to manage the carbon footprint in their operations decisions with the subsequent enactment of regulations and legislation on carbon emissions. This paper examined the impacts of the carbon trading mechanism on road truck routing decisions. We initially introduced a calculation method of carbon emissions, including the load and speed of the vehicle. We then constructed an environmental road truck routing model under the cap and trade mechanism based on the classical TSP model. This model explored the impacts of carbon trading, carbon cap, and carbon price on truck routing decisions, the amount of carbon emissions, and the total cost. This model differs from the classical TSP model in the aspect of economic costs. Next, due to the problem complexity, a tabu search algorithm was deployed together with four neighborhoods. We also performed several numerical experiments to illustrate the analytical results and presented interesting implications and managerial insights.The results of the computational experiments on several realistic instances provided the following important insights.(
1
) Under the cap and trade mechanism, the MT model simultaneously considers the economic and environmental aspects. The truck routing optimizing decision actually seeks the balance between minimizing the economic cost and minimizing the carbon emissions. When carbon price is zero, this model aims to minimize the economic cost, and when the carbon price is extremely high, the model aims to minimize the carbon emissions.(
2
) Compared with the MC model that minimizes the economic cost, the MT model under the cap and trade mechanism can effectively induce firms to reduce carbon emissions but may increase their total cost. The MT model may also simultaneously reduce carbon emissions and total cost of the firm when the carbon cap is large.(
3
) The carbon cap and carbon price significantly affect the road truck routing decision, carbon emissions, and total cost of the firm. The carbon cap allocated to a single firm cannot change the carbon emissions of the firm, but it will affect its total cost. Several conditions exist on whether or not the firm should buy the carbon permits. We find that when the carbon cap is less than a threshold, the firm should buy carbon permits; when the carbon cap is higher than a threshold, the firm would sell carbon permits; and when the carbon cap equals the threshold, the firm would not need to conduct carbon trading. With the increasing carbon price, the carbon emissions demonstrate a “ladder-type” declining curve. The carbon emissions would begin to decrease only when the carbon price is higher than a threshold, and the variations of the total costs depend on the carbon cap.Our study provided several insights into the logistics and transport operations of a firm under the carbon emissions trading mechanism and presented an important reference for governments to develop low-carbon and sustainable policies. Several extensions are possible for our study. For instance, in this paper, we assume that the carbon cap has no effect on the carbon price, and a single firm deals with its operations decisions under the carbon trading mechanism. Further research may investigate the impacts of carbon pricing decisions and cooperative games among multiple firms on the amount of carbon emissions. Further research may also incorporate demand uncertainty, multiple types of vehicles, and different transport modes into the low-carbon practice.



---

*Source: 814527-2015-09-07.xml*