# Optimizing the Composite Cost Involved in Road Motor-Transporting Trucks by Taking into Account Traffic Condition

Authors: Hongying Fei; Chengyi Zhang
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

With the rapid development of modern automotive logistics industry, vehicle logistics has drawn more and more attention. Since the vehicle transporters mainly are the severe-polluting heavy-duty vehicles and their exhaust emissions vary under different traffic conditions, it is necessary to improve the planning of road motor-transporting services by taking into account road traffic condition, especially for urban areas. This study aims at minimizing the composite cost, including both the economic cost related to the driver cost and fuel consumption, and the social cost related to the vehicle emissions. The dynamic road traffic condition is imitated dynamically with a discretization technique. A metaheuristic is applied with data collected from a dense district in a huge city. Experimental results show that the proposed approach can always converge quickly to the best solution and the solution with minimal composite cost can always dominate the other solutions with classic route optimization goals.


---

## Body

## 1. Introduction

Besides the labor cost of truck drivers, vehicle fuel consumption and emissions are also critical aspects in the transportation planning process, especially for companies using heavy-duty trucks in recent years.Having been the largest automobile market and factory, thousands of motors are being transported from their assembly factories to the 4S dealers by motor-transporting trucks, which are normally heavy-duty diesel trucks. It has been reported that the transportation cost takes up about 80% of the total logistics cost for the whole process of vehicle delivery in china, which is even higher than doubled cost in Europe. Therefore, it is quite important for the managers to arrange the vehicle delivery process in an efficient and effective manner.Early vehicle routing problems are mainly focused on the minimization of economic transportation cost, travel time, or/and empty loading rate; however, it is no more the case in recent years. Since more and more people realize that the transportation plays a significant role in air pollution, the corporations, especially logistics companies, are forced to take their responsibilities of reducing vehicles emissions while performing their delivery services.Urban roads are limited resources, while the number of vehicles has been increasing dramatically in recent years. In consequence, traffic jams can be observed everywhere. Once involved in the traffic jam, the vehicles consume much more fuel, resulting in a high level of pollutant emissions. Thus the traffic condition, which dynamically changes, has an important impact on vehicles emissions.How can we optimize the delivery routes of the motor-transporting trucks so as to minimize both economic cost and pollutant emissions? A non-traffic-jam shortest path may be ideal solution. Unfortunately, it is almost impossible to attain such situation in the real world, especially in metropolitan areas. On the contrary, we should make a concession to the existence of traffic congestions and take actions to improve the transportation plan based on a thorough investigation of the traffic condition in the targeted area, as is the objective of this study.The paper is organized as follows: the literature review on time-dependent vehicle routing problems, especially the studies taking into account traffic conditions, is presented in Section2. Section 3 is dedicated to the problem description and some preliminaries. The key points of the proposed metaheuristic are described in Section 4, and numerical experiments are presented in Section 5 and this paper ends up with an overall conclusion made in Section 6.


## 2. Literature Review

According to the literature, numerous researchers were interested in dealing with time-dependent vehicle routing problems (VRP) since this kind of problems arises naturally in a variety of applications [1]. Since the travel time impacts greatly the vehicle speed, which is an important factor of car emissions, the green vehicle routing problems, that is, the minimizing-emission VRPs, are normally considered as variants of time-dependent VRPs strongly related to road traffic conditions. In this section, a brief literature review of studies focused on time-dependent VRPs, especially traffic-condition-related VRPs, in recent years is given.Time-dependent routing problems may be classified with respect to a number of criteria, such as the topology of the network, the objectives, and the constraints. Although some authors, such as Franceschetti et al. [2], provided an analytical characterization of the optimal solution for a single-arc version, most of the studies dealt with network version. As for the paths connecting two nodes, most of the work supposed that only one arc is defined between two nodes, though some others allowed multiple selection on arcs between two nodes [3, 4].As for the objectives, it was observed that most of the early studies were considered to minimize the travel time [5–13], and social costs are considered widely in recent years, such as the congestion charge [14] and emissions [2, 15–19]. It reveals the importance the society attaches to the environmental protection.With regard to the methodology, most of the studies were based on heuristics (e.g., [4, 7, 9, 12, 14, 20]) and metaheuristics, such as Tabu search [3, 5, 6, 13, 16], Variable Neighborhood Search [8], Ant Colony System [10], and particle swam optimization [17, 21].To sum up, vast publications can be observed in the literature related to time-dependent vehicle routing problem, and more and more scholars focused their studies on emission-minimizing problems by taking into account the traffic condition. Except some that provided analytic model for single-arc problem, most of the studies are based on heuristics or metaheuristics, though few obtain great achievements on dealing with the real-world traffic congestions, especially for the heavy-duty motor-transporting trucks. In this study, the dynamic change of traffic congestion is considered to obtain grounded evaluation of the velocity of motor-transporting trucks, and a metaheuristic will also be applied to solve this time-dependent vehicle routing problem with an objective to minimize both economical cost (driver cost and fuel consumption) and social cost (emission of CO2, CO, and NOx).


## 3. Problem Description

### 3.1. Assumptions

As described in the previous section, in general, motor-transport trucks start from a given depot and deliver cars to 4S dealers’ parks, with each 4S dealer being served by one truck, according to predefined orders, and finally return back to the same depot to complete the route. The aim of this paper is to define the best path for each motor-transport truck by taking into account the uncertainty of road traffic condition, especially the congestion, so as to minimize composite cost, composed of not only the economic cost, fuel cost, and maneuver cost but also the social cost represented as the emission of those trucks. It is worth mentioning that since the vehicle emission depends on their running conditions which are closely correlated with the congestion of the route, the distribution of road congestion has been discretized in this study to imitate the real situation in an efficient way.Some important assumptions are as follows:(1)
Distribution of the road traffic congestion situation is investigated in advance.(2)
There is one depot. The locations of the depot and 4S dealers are given.(3)
The capacity of a truck is enough to serve any 4S dealer, and the requirements of a 4S dealer cannot be shared among different motor-transport trucks.(4)
The route of each truck starts from and eventually ends at the storage depot.(5)
The storage in the depot could meet all customers’ needs.(6)
Not only will the motors be transported but also the motor-transport trucks are uniform.(7)
The composite cost is composed of three parts: fuel consumption, drivers’ salaries, and the exhaust emissions of motor-transport trucks.(8)
Tree traffic conditions are considered, as usually shown in various navigation maps using green, yellow, and red. The trucks run with at the maximum authorized speed under “green” condition, the limited speed under “yellow” condition and the extremely low speed, defined as 10 in this study, under “red” condition. The distributions of various road traffic conditions during the whole day have been discretized into 24 intervals, each corresponding to one hour, and evaluated after we conducted an analysis of the real situation of each route with the data collected from navigation maps during certain observation period.(9)
One and only one driver is responsible for a motor-transport truck.(10)
No stop accounts for road junctions.


### 3.2. Notations

The vehicle routing problem considered in this study can be described in an undirected graphG={N,A}.Nrepresents the nodes, including the depot i0, 4S dealers, and road junctions.A represents the set of arcs linking pairs of nodes according to the traffic road map.Notation H: Total number of motor-transporting trucks Ω: Global set of nodes, including the depot, 4S dealers, and road junctions Ω L: Set of 4S dealers Ω h: Set of nodes passed by the truck h∈1,…,H P d: Driver’s hourly salary P e: Estimated emission-treatment fee per km per vehicle P f: Fuel consumed per km per vehicle C d: Total driver cost C f: Total fuel-consumption cost C s: Total social cost considering the treatment of car emissions t i h: Departure time of truck h at node i t F h: Arrival time of truck h at the depot, node 0 Δ t: Length of unit time interval used in this study to discretize the distribution of traffic condition d i j: Travel distance between nodes i and j v i j G: Maximum speed, under “Green” traffic condition, along the route connecting nodes i and j V i j Y: Speed of the truck under “Yellow” traffic condition along the route connecting nodes i and j V i j R: Speed of the truck under “Red” condition along the route connecting nodes i and j V - i j ( t ): Expected speed of the truck on the route connecting nodes i and j at timet P i j G ( t ): Probability of “Green” condition for the route i,j at time t P i j Y ( t ): Probability of “Yellow” condition for the route i,j at time t P i j R ( t ): Probability of “Red” condition for the route i,j at time t T 0: Earliest possible leaving time from the depot T f: Latest possible arrival time at the depotDecision Variables (1) x i j h t = 1 , truck h takes the route connecting nodes i and j at  time t 0 , otherwise


### 3.3. Preliminaries

As mentioned in the previous section, this study aims at minimizing the composite cost including the labor costCd related to drivers’ salaries, the fuel cost Cf related to the consumption of fuel along the trajectories, and the social cost Cs considering the treatment of car emissions. In this part, the calculations of these costs are detailed, respectively.


#### 3.3.1. Evaluation of Drivers’ Labor Cost

The drivers’ labor cost,Cd, is mainly determined by the total time used by truck drivers to complete their missions. In this study, the total travel time of trucks is applied to evaluate the drivers’ labor cost.Since the drivers must be along with their trucks from their departure from the depot until their arrival at the same depot, in one word, drivers’ labor costs can be defined as the drivers’ hourly pay,Ps, multiplied by their traveling time: (2)Cd=Ps·∑h=1Ht0h-tFhwheret0h and tFh,h∈1,…,H denote the departure time of truck h from the depot and the arrival time of that truck at the depot, respectively. Obviously, all t0h,h∈Ωh are normally given in advance according to the delivery schedule, while tFh depends on not only the departure of truck h from the depot but also the traffic condition of the road which is uncertain. In this study, the distribution of the road traffic condition for each segment of the road is predefined according to the survey from a popular navigation map during a certain observation period and then discretized into several parts, each corresponding to one time unit, so that the arrival time of the truck at successive nodes can be calculated dynamically with a recursive formula. The specific solving process for a certain segment of the route is shown in Figure 1 as an example.Figure 1
Description of how to define the arrival time of the truck at the successive node in condition that the departure time at the precedent node is given.According to the dynamic threshold shown in a popular application of navigation map, one of the most popular navigation maps in China, dynamic traffic conditions are recorded and generally visualized with three colors. If one route’s road condition is quite clear, the corresponding line on the map is marked green and the vehicle can run at the maximum authorized speed. If the vehicles on one route should slow down to a predefined threshold (e.g., 30 km/h in Baidu Map), the corresponding line is marked yellow and the vehicles are supposed to run at that threshold. Red lines in the navigation maps indicate that those lines are facing congestion and no cars can run at a speed over 5 km/h; that is, all the cars must experience stop-and-goes.Suppose that a truck passed by road junctioni at time tih towards road junctionj, where h∈1,…,H,i∈Ω, and j∈Ω.The route between these two road junctions (nodes) can be divided into kijh∗+1 segments, where any of the first kijh∗segments corresponds to the distance, covered by the truck, which is calculated according to the current traffic condition within one unit time interval Δt, and the truck’s travel duration for the last segment may be part of the time unit Δt, as shown in Figure 1.Since a predefined distribution of traffic condition is given for each segment at any time, the expected speed of any vehicle passing through the route that connects nodesi and j at time t can be calculated with the following formula:(3)V-ijt=VijGt·PijGt+VijYt·PijYt+VijRt·PijRtIn consequence, if the truckh departed from node i at time tih, its arrival time at the successive node j can be defined as follows: (4)kijh∗=argmin⁡Δt·12V-ijtih+∑k′=1k-1V-ijtih+k·Δt+12V-ijtih+k·Δt∣Δt·12V-ijtih+∑k′=1k-1V-ijtih+k′·Δt+12V-ijtih+k·Δt>dij(5)tjh=tih+kijh∗·Δt+εijtihwhere(6)εijtih=dij-Δt1/2V-ijtih+∑k′=1k∗-1V-ijtih+k′·Δt+1/2V-ijtih+kijh∗·ΔtV-ijtih+kijh∗·ΔtConstraint (4)-(6) indicates the calculation of the passing time of the truck h at each node by discretizing the route that connects the pair of nodes with segments covered by the truck h within unit time interval Δt.


#### 3.3.2. Evaluation of Social Cost That Is Related to the Treatment of Car Emissions

The social costCs mainly depends on the amount of exhaust emissions. Since Li [22] has created the formula of vehicle emission related to the three most important factors CO, HC, and NOx after taking real-world experiments, the formulas are applied in this study to evaluate the emission of motor-transport trucks, which are normally heavy diesel vehicles (HDV). The corresponding fitting models are shown in Table 1.Table 1
Fitting models based on comprehensive emission factor of HC, CO, and NOx for HDVs.
Pollutant gases Seasons Emission factor fitting models (unit: gram/unit.km) HC Summer E H C v = 15.2935 - 0.4129 v + 0.0050 v 2 - 2 ⋅ 10 - 5 v 3 Winter E H C v = 15.2935 - 0.4129 v + 0.0050 v 2 - 2 ⋅ 10 - 5 v 3  CO Summer E C O v = 64.5194 - 2.2960 v + 0.0319 v 2 - 0.0001 v 3 Winter E C O v = 64.5194154 - 2.2960 v + 0.0319 v 2 - 0.0001 v 3  NOx Summer E N O x v = 77.3436 - 1.6314 v + 0.0179 v 2 - 3 ⋅ 10 - 5 ⋅ v 3 Winter E N O x v = 77.3436 - 1.6314 v + 0.0179 v 2 - 3 ⋅ 10 - 5 ⋅ v 3It is worth mentioning that since HC was excluded from the list of pollutant emissions in “Environmental Air Quality Standards,” only the costs for CO andNOxwill be discussed in this study. Furthermore, as shown in Table 1, no significant difference is observed between different seasons; in consequence, two universal fitting models, presented in (7) and (8), are applied in this study to evaluate the emission of CO and NOx, respectively.(7)ECOv=64.5194-2.2960v+0.0319v2-0.0001v3(8)ENOxv=77.3436-1.6314v+0.0179v2-3·10-5·v3It is obvious that the vehicles’ speed is strongly related to the road traffic conditions and the road restrictions; considering that certain regularity can be observed in the road traffic conditions in practice, in this study, the road traffic conditions are imitated with the data collected during an observation period for estimating the expected speed for the routes that connect the pair of nodes in the network. Afterwards, formulas (3)-(6) are applied to estimate the emission of trucks on those routes by using the corresponding expected speed at the passing time.Furthermore, since “Technical Guidelines for Environmental Impact Assessment-Atmospheric Environment (HJ2.2-2008)” assessed that the conversion formula for the hourly average and daily average ofNO2 and NOx is NO2=0.9·NOx,NOx can be replaced by NO2 for further analysis without significant influence on the experimental results.As for the treatment fee of the exhaust gases, the environmental degradation costs for CO andNO2 are considered, where the environmental degradation costs are the corresponding depreciation costs for the environmental degradation because the nature absorbed the polluting gases of the trucks during the distribution process.According to the regulation “sewage charges standard management approaches” promulgated by the Chinese government, the standard polluting discharge fee is set as 0.6 RMB per pollutant equivalent. The specific pollutant equivalent value is 16.7kg and 0.95kg for CO andNO2, respectively. In consequence, unit control cost (UCC) for different pollutant gases can be calculated with the following formulas:(9)Pollutant Equivalents=Quality of Emissions Unit (kg)Corresponding Equivalent Value (kg)(10)Unit Control Cost (UCC)=Quality of the pollutant per Emission Unit (kg)Corresponding Equivalent Valuekg∗Adjustment coefficientIn consequence, the social cost for one motor-transporting truck running with speed v (km/h) can be defined with formula (11). It is worth noting that the parameter 10-3 is used in formula (11) for the purpose of adjustment because the unit “gram/km” is used in formulas (7) and (8) for calculating the emission, while the unit “kg” is applied in formula (9) for calculating the unit control cost.(11)Pev=UCCNO2·ENO2v+UCCCO·ECOv=0.6·10.95·1·ENO2v·10-3+0.6·116.7·1·ECOv·10-3Although the emission is not in linear relationship with the vehicle’s speed, it can be calculated as the sum of the emissions for each segment in which the vehicle traveled during unit time interval and the quality of the results depends on how the unit time interval is defined. In the extreme case, if the unit time interval is small enough, no significant difference will be observed between the sum of those segmental emission values and the exact emission. In consequence, the calculation of emission is simplified by using the segmental processing method with the average expected speed for each segment. The total social cost could be calculated with the following formula:(12)Cs=∑h=1H∑i∈Ω∑j∈Ωdij·Pe12V-ijtih+∑k=1kijh∗PeV-ijtih+k·Δt+Pe12V-ijtih+kijh∗·Δt+εijtih


#### 3.3.3. Evaluation of the Cost Related to the Consumption of FuelCf

The fuel costCf could be obtained by the accumulation of the fuel cost per unit distance, and the calculation process applied by Wen et al. [12] for a Diesel LGV Euro II type vehicle, formula (13), is adopted in this study. (13)EFv=77.43+0.009v-0.015v2+0.00015v3+519v-1-70v-2wherev represents the vehicle’s travel speed (unit: km/h); EFv represents the fuel consumption (unit: gram/ km). It is worth noting that one liter of diesel weights about 840 grams. Although the price of diesel is strongly related to that of petroleum which keeps changing, this parameter cannot be regarded as sensitive in this model, so a predefined constant works. Therefore, the price of diesel is set as 5.4 RMB/L, the average price in the targeted region during the observation period, and the cost related to the consumption of fuel for one truck running with an average speed V- per kilometer (unit: RMB/(vehicle·Km)) can be evaluated with formula (14), where the average speed is calculated by using the segmental processing method based on the average speed for segments in which the vehicle traveled within unit time interval Δt. In consequence, the total fuel cost can be calculated with formula (15), which is quite similar to formula (12), except that Pf is used instead of Pe.(14)PfV-=5.4·77.43+0.009V--0.015V-2+0.00015V-3+519V--1-70V--2÷840(15)Cf=∑h=1H∑i∈Ω∑j∈Ωdij·Pf12V-ijtih+∑k=1kijh∗PfV-ijtih+k·Δt+Pf12V-ijtih+kijh∗·Δt+εijtih


### 3.4. Mathematical Model

(16) m i n  C t o t a l = C d + C f + C sSubject to(2), (12), and (15),(17)∑i=1H∑i∈Ωh∑j∈Ωhxijht≤H,T0≤t≤Tf(18)∫T0Tf∑j∈Ωox0jht=∫T0Tf∑i∈Ω0xiohth∈1,…,H(19)∫T0Tf∑h=1H∑i∈Ω∖jxijht=1,j∈ΩL(20)∫ToTf∑i∈Ω∑i∈ΩLxijht=1,h∈1,…,H(21)xijht∈0,1,T0≤t≤TfThe objective is to minimize both transportation cost, including drivers’ labor cost and fuel consumption, and treatment cost of pollutant emissions. Constraint (17) indicates that the number of the trucks which leave from the storage depot could not exceed the total number of the trucks owned by storage depot. Constraint (18) denotes that all trucks must start from and end at the only depot. Constraints (19) and (20) indicate that one 4S dealer could only be served by one truck.


## 3.1. Assumptions

As described in the previous section, in general, motor-transport trucks start from a given depot and deliver cars to 4S dealers’ parks, with each 4S dealer being served by one truck, according to predefined orders, and finally return back to the same depot to complete the route. The aim of this paper is to define the best path for each motor-transport truck by taking into account the uncertainty of road traffic condition, especially the congestion, so as to minimize composite cost, composed of not only the economic cost, fuel cost, and maneuver cost but also the social cost represented as the emission of those trucks. It is worth mentioning that since the vehicle emission depends on their running conditions which are closely correlated with the congestion of the route, the distribution of road congestion has been discretized in this study to imitate the real situation in an efficient way.Some important assumptions are as follows:(1)
Distribution of the road traffic congestion situation is investigated in advance.(2)
There is one depot. The locations of the depot and 4S dealers are given.(3)
The capacity of a truck is enough to serve any 4S dealer, and the requirements of a 4S dealer cannot be shared among different motor-transport trucks.(4)
The route of each truck starts from and eventually ends at the storage depot.(5)
The storage in the depot could meet all customers’ needs.(6)
Not only will the motors be transported but also the motor-transport trucks are uniform.(7)
The composite cost is composed of three parts: fuel consumption, drivers’ salaries, and the exhaust emissions of motor-transport trucks.(8)
Tree traffic conditions are considered, as usually shown in various navigation maps using green, yellow, and red. The trucks run with at the maximum authorized speed under “green” condition, the limited speed under “yellow” condition and the extremely low speed, defined as 10 in this study, under “red” condition. The distributions of various road traffic conditions during the whole day have been discretized into 24 intervals, each corresponding to one hour, and evaluated after we conducted an analysis of the real situation of each route with the data collected from navigation maps during certain observation period.(9)
One and only one driver is responsible for a motor-transport truck.(10)
No stop accounts for road junctions.


## 3.2. Notations

The vehicle routing problem considered in this study can be described in an undirected graphG={N,A}.Nrepresents the nodes, including the depot i0, 4S dealers, and road junctions.A represents the set of arcs linking pairs of nodes according to the traffic road map.Notation H: Total number of motor-transporting trucks Ω: Global set of nodes, including the depot, 4S dealers, and road junctions Ω L: Set of 4S dealers Ω h: Set of nodes passed by the truck h∈1,…,H P d: Driver’s hourly salary P e: Estimated emission-treatment fee per km per vehicle P f: Fuel consumed per km per vehicle C d: Total driver cost C f: Total fuel-consumption cost C s: Total social cost considering the treatment of car emissions t i h: Departure time of truck h at node i t F h: Arrival time of truck h at the depot, node 0 Δ t: Length of unit time interval used in this study to discretize the distribution of traffic condition d i j: Travel distance between nodes i and j v i j G: Maximum speed, under “Green” traffic condition, along the route connecting nodes i and j V i j Y: Speed of the truck under “Yellow” traffic condition along the route connecting nodes i and j V i j R: Speed of the truck under “Red” condition along the route connecting nodes i and j V - i j ( t ): Expected speed of the truck on the route connecting nodes i and j at timet P i j G ( t ): Probability of “Green” condition for the route i,j at time t P i j Y ( t ): Probability of “Yellow” condition for the route i,j at time t P i j R ( t ): Probability of “Red” condition for the route i,j at time t T 0: Earliest possible leaving time from the depot T f: Latest possible arrival time at the depotDecision Variables (1) x i j h t = 1 , truck h takes the route connecting nodes i and j at  time t 0 , otherwise


## 3.3. Preliminaries

As mentioned in the previous section, this study aims at minimizing the composite cost including the labor costCd related to drivers’ salaries, the fuel cost Cf related to the consumption of fuel along the trajectories, and the social cost Cs considering the treatment of car emissions. In this part, the calculations of these costs are detailed, respectively.


### 3.3.1. Evaluation of Drivers’ Labor Cost

The drivers’ labor cost,Cd, is mainly determined by the total time used by truck drivers to complete their missions. In this study, the total travel time of trucks is applied to evaluate the drivers’ labor cost.Since the drivers must be along with their trucks from their departure from the depot until their arrival at the same depot, in one word, drivers’ labor costs can be defined as the drivers’ hourly pay,Ps, multiplied by their traveling time: (2)Cd=Ps·∑h=1Ht0h-tFhwheret0h and tFh,h∈1,…,H denote the departure time of truck h from the depot and the arrival time of that truck at the depot, respectively. Obviously, all t0h,h∈Ωh are normally given in advance according to the delivery schedule, while tFh depends on not only the departure of truck h from the depot but also the traffic condition of the road which is uncertain. In this study, the distribution of the road traffic condition for each segment of the road is predefined according to the survey from a popular navigation map during a certain observation period and then discretized into several parts, each corresponding to one time unit, so that the arrival time of the truck at successive nodes can be calculated dynamically with a recursive formula. The specific solving process for a certain segment of the route is shown in Figure 1 as an example.Figure 1
Description of how to define the arrival time of the truck at the successive node in condition that the departure time at the precedent node is given.According to the dynamic threshold shown in a popular application of navigation map, one of the most popular navigation maps in China, dynamic traffic conditions are recorded and generally visualized with three colors. If one route’s road condition is quite clear, the corresponding line on the map is marked green and the vehicle can run at the maximum authorized speed. If the vehicles on one route should slow down to a predefined threshold (e.g., 30 km/h in Baidu Map), the corresponding line is marked yellow and the vehicles are supposed to run at that threshold. Red lines in the navigation maps indicate that those lines are facing congestion and no cars can run at a speed over 5 km/h; that is, all the cars must experience stop-and-goes.Suppose that a truck passed by road junctioni at time tih towards road junctionj, where h∈1,…,H,i∈Ω, and j∈Ω.The route between these two road junctions (nodes) can be divided into kijh∗+1 segments, where any of the first kijh∗segments corresponds to the distance, covered by the truck, which is calculated according to the current traffic condition within one unit time interval Δt, and the truck’s travel duration for the last segment may be part of the time unit Δt, as shown in Figure 1.Since a predefined distribution of traffic condition is given for each segment at any time, the expected speed of any vehicle passing through the route that connects nodesi and j at time t can be calculated with the following formula:(3)V-ijt=VijGt·PijGt+VijYt·PijYt+VijRt·PijRtIn consequence, if the truckh departed from node i at time tih, its arrival time at the successive node j can be defined as follows: (4)kijh∗=argmin⁡Δt·12V-ijtih+∑k′=1k-1V-ijtih+k·Δt+12V-ijtih+k·Δt∣Δt·12V-ijtih+∑k′=1k-1V-ijtih+k′·Δt+12V-ijtih+k·Δt>dij(5)tjh=tih+kijh∗·Δt+εijtihwhere(6)εijtih=dij-Δt1/2V-ijtih+∑k′=1k∗-1V-ijtih+k′·Δt+1/2V-ijtih+kijh∗·ΔtV-ijtih+kijh∗·ΔtConstraint (4)-(6) indicates the calculation of the passing time of the truck h at each node by discretizing the route that connects the pair of nodes with segments covered by the truck h within unit time interval Δt.


### 3.3.2. Evaluation of Social Cost That Is Related to the Treatment of Car Emissions

The social costCs mainly depends on the amount of exhaust emissions. Since Li [22] has created the formula of vehicle emission related to the three most important factors CO, HC, and NOx after taking real-world experiments, the formulas are applied in this study to evaluate the emission of motor-transport trucks, which are normally heavy diesel vehicles (HDV). The corresponding fitting models are shown in Table 1.Table 1
Fitting models based on comprehensive emission factor of HC, CO, and NOx for HDVs.
Pollutant gases Seasons Emission factor fitting models (unit: gram/unit.km) HC Summer E H C v = 15.2935 - 0.4129 v + 0.0050 v 2 - 2 ⋅ 10 - 5 v 3 Winter E H C v = 15.2935 - 0.4129 v + 0.0050 v 2 - 2 ⋅ 10 - 5 v 3  CO Summer E C O v = 64.5194 - 2.2960 v + 0.0319 v 2 - 0.0001 v 3 Winter E C O v = 64.5194154 - 2.2960 v + 0.0319 v 2 - 0.0001 v 3  NOx Summer E N O x v = 77.3436 - 1.6314 v + 0.0179 v 2 - 3 ⋅ 10 - 5 ⋅ v 3 Winter E N O x v = 77.3436 - 1.6314 v + 0.0179 v 2 - 3 ⋅ 10 - 5 ⋅ v 3It is worth mentioning that since HC was excluded from the list of pollutant emissions in “Environmental Air Quality Standards,” only the costs for CO andNOxwill be discussed in this study. Furthermore, as shown in Table 1, no significant difference is observed between different seasons; in consequence, two universal fitting models, presented in (7) and (8), are applied in this study to evaluate the emission of CO and NOx, respectively.(7)ECOv=64.5194-2.2960v+0.0319v2-0.0001v3(8)ENOxv=77.3436-1.6314v+0.0179v2-3·10-5·v3It is obvious that the vehicles’ speed is strongly related to the road traffic conditions and the road restrictions; considering that certain regularity can be observed in the road traffic conditions in practice, in this study, the road traffic conditions are imitated with the data collected during an observation period for estimating the expected speed for the routes that connect the pair of nodes in the network. Afterwards, formulas (3)-(6) are applied to estimate the emission of trucks on those routes by using the corresponding expected speed at the passing time.Furthermore, since “Technical Guidelines for Environmental Impact Assessment-Atmospheric Environment (HJ2.2-2008)” assessed that the conversion formula for the hourly average and daily average ofNO2 and NOx is NO2=0.9·NOx,NOx can be replaced by NO2 for further analysis without significant influence on the experimental results.As for the treatment fee of the exhaust gases, the environmental degradation costs for CO andNO2 are considered, where the environmental degradation costs are the corresponding depreciation costs for the environmental degradation because the nature absorbed the polluting gases of the trucks during the distribution process.According to the regulation “sewage charges standard management approaches” promulgated by the Chinese government, the standard polluting discharge fee is set as 0.6 RMB per pollutant equivalent. The specific pollutant equivalent value is 16.7kg and 0.95kg for CO andNO2, respectively. In consequence, unit control cost (UCC) for different pollutant gases can be calculated with the following formulas:(9)Pollutant Equivalents=Quality of Emissions Unit (kg)Corresponding Equivalent Value (kg)(10)Unit Control Cost (UCC)=Quality of the pollutant per Emission Unit (kg)Corresponding Equivalent Valuekg∗Adjustment coefficientIn consequence, the social cost for one motor-transporting truck running with speed v (km/h) can be defined with formula (11). It is worth noting that the parameter 10-3 is used in formula (11) for the purpose of adjustment because the unit “gram/km” is used in formulas (7) and (8) for calculating the emission, while the unit “kg” is applied in formula (9) for calculating the unit control cost.(11)Pev=UCCNO2·ENO2v+UCCCO·ECOv=0.6·10.95·1·ENO2v·10-3+0.6·116.7·1·ECOv·10-3Although the emission is not in linear relationship with the vehicle’s speed, it can be calculated as the sum of the emissions for each segment in which the vehicle traveled during unit time interval and the quality of the results depends on how the unit time interval is defined. In the extreme case, if the unit time interval is small enough, no significant difference will be observed between the sum of those segmental emission values and the exact emission. In consequence, the calculation of emission is simplified by using the segmental processing method with the average expected speed for each segment. The total social cost could be calculated with the following formula:(12)Cs=∑h=1H∑i∈Ω∑j∈Ωdij·Pe12V-ijtih+∑k=1kijh∗PeV-ijtih+k·Δt+Pe12V-ijtih+kijh∗·Δt+εijtih


### 3.3.3. Evaluation of the Cost Related to the Consumption of FuelCf

The fuel costCf could be obtained by the accumulation of the fuel cost per unit distance, and the calculation process applied by Wen et al. [12] for a Diesel LGV Euro II type vehicle, formula (13), is adopted in this study. (13)EFv=77.43+0.009v-0.015v2+0.00015v3+519v-1-70v-2wherev represents the vehicle’s travel speed (unit: km/h); EFv represents the fuel consumption (unit: gram/ km). It is worth noting that one liter of diesel weights about 840 grams. Although the price of diesel is strongly related to that of petroleum which keeps changing, this parameter cannot be regarded as sensitive in this model, so a predefined constant works. Therefore, the price of diesel is set as 5.4 RMB/L, the average price in the targeted region during the observation period, and the cost related to the consumption of fuel for one truck running with an average speed V- per kilometer (unit: RMB/(vehicle·Km)) can be evaluated with formula (14), where the average speed is calculated by using the segmental processing method based on the average speed for segments in which the vehicle traveled within unit time interval Δt. In consequence, the total fuel cost can be calculated with formula (15), which is quite similar to formula (12), except that Pf is used instead of Pe.(14)PfV-=5.4·77.43+0.009V--0.015V-2+0.00015V-3+519V--1-70V--2÷840(15)Cf=∑h=1H∑i∈Ω∑j∈Ωdij·Pf12V-ijtih+∑k=1kijh∗PfV-ijtih+k·Δt+Pf12V-ijtih+kijh∗·Δt+εijtih


## 3.3.1. Evaluation of Drivers’ Labor Cost

The drivers’ labor cost,Cd, is mainly determined by the total time used by truck drivers to complete their missions. In this study, the total travel time of trucks is applied to evaluate the drivers’ labor cost.Since the drivers must be along with their trucks from their departure from the depot until their arrival at the same depot, in one word, drivers’ labor costs can be defined as the drivers’ hourly pay,Ps, multiplied by their traveling time: (2)Cd=Ps·∑h=1Ht0h-tFhwheret0h and tFh,h∈1,…,H denote the departure time of truck h from the depot and the arrival time of that truck at the depot, respectively. Obviously, all t0h,h∈Ωh are normally given in advance according to the delivery schedule, while tFh depends on not only the departure of truck h from the depot but also the traffic condition of the road which is uncertain. In this study, the distribution of the road traffic condition for each segment of the road is predefined according to the survey from a popular navigation map during a certain observation period and then discretized into several parts, each corresponding to one time unit, so that the arrival time of the truck at successive nodes can be calculated dynamically with a recursive formula. The specific solving process for a certain segment of the route is shown in Figure 1 as an example.Figure 1
Description of how to define the arrival time of the truck at the successive node in condition that the departure time at the precedent node is given.According to the dynamic threshold shown in a popular application of navigation map, one of the most popular navigation maps in China, dynamic traffic conditions are recorded and generally visualized with three colors. If one route’s road condition is quite clear, the corresponding line on the map is marked green and the vehicle can run at the maximum authorized speed. If the vehicles on one route should slow down to a predefined threshold (e.g., 30 km/h in Baidu Map), the corresponding line is marked yellow and the vehicles are supposed to run at that threshold. Red lines in the navigation maps indicate that those lines are facing congestion and no cars can run at a speed over 5 km/h; that is, all the cars must experience stop-and-goes.Suppose that a truck passed by road junctioni at time tih towards road junctionj, where h∈1,…,H,i∈Ω, and j∈Ω.The route between these two road junctions (nodes) can be divided into kijh∗+1 segments, where any of the first kijh∗segments corresponds to the distance, covered by the truck, which is calculated according to the current traffic condition within one unit time interval Δt, and the truck’s travel duration for the last segment may be part of the time unit Δt, as shown in Figure 1.Since a predefined distribution of traffic condition is given for each segment at any time, the expected speed of any vehicle passing through the route that connects nodesi and j at time t can be calculated with the following formula:(3)V-ijt=VijGt·PijGt+VijYt·PijYt+VijRt·PijRtIn consequence, if the truckh departed from node i at time tih, its arrival time at the successive node j can be defined as follows: (4)kijh∗=argmin⁡Δt·12V-ijtih+∑k′=1k-1V-ijtih+k·Δt+12V-ijtih+k·Δt∣Δt·12V-ijtih+∑k′=1k-1V-ijtih+k′·Δt+12V-ijtih+k·Δt>dij(5)tjh=tih+kijh∗·Δt+εijtihwhere(6)εijtih=dij-Δt1/2V-ijtih+∑k′=1k∗-1V-ijtih+k′·Δt+1/2V-ijtih+kijh∗·ΔtV-ijtih+kijh∗·ΔtConstraint (4)-(6) indicates the calculation of the passing time of the truck h at each node by discretizing the route that connects the pair of nodes with segments covered by the truck h within unit time interval Δt.


## 3.3.2. Evaluation of Social Cost That Is Related to the Treatment of Car Emissions

The social costCs mainly depends on the amount of exhaust emissions. Since Li [22] has created the formula of vehicle emission related to the three most important factors CO, HC, and NOx after taking real-world experiments, the formulas are applied in this study to evaluate the emission of motor-transport trucks, which are normally heavy diesel vehicles (HDV). The corresponding fitting models are shown in Table 1.Table 1
Fitting models based on comprehensive emission factor of HC, CO, and NOx for HDVs.
Pollutant gases Seasons Emission factor fitting models (unit: gram/unit.km) HC Summer E H C v = 15.2935 - 0.4129 v + 0.0050 v 2 - 2 ⋅ 10 - 5 v 3 Winter E H C v = 15.2935 - 0.4129 v + 0.0050 v 2 - 2 ⋅ 10 - 5 v 3  CO Summer E C O v = 64.5194 - 2.2960 v + 0.0319 v 2 - 0.0001 v 3 Winter E C O v = 64.5194154 - 2.2960 v + 0.0319 v 2 - 0.0001 v 3  NOx Summer E N O x v = 77.3436 - 1.6314 v + 0.0179 v 2 - 3 ⋅ 10 - 5 ⋅ v 3 Winter E N O x v = 77.3436 - 1.6314 v + 0.0179 v 2 - 3 ⋅ 10 - 5 ⋅ v 3It is worth mentioning that since HC was excluded from the list of pollutant emissions in “Environmental Air Quality Standards,” only the costs for CO andNOxwill be discussed in this study. Furthermore, as shown in Table 1, no significant difference is observed between different seasons; in consequence, two universal fitting models, presented in (7) and (8), are applied in this study to evaluate the emission of CO and NOx, respectively.(7)ECOv=64.5194-2.2960v+0.0319v2-0.0001v3(8)ENOxv=77.3436-1.6314v+0.0179v2-3·10-5·v3It is obvious that the vehicles’ speed is strongly related to the road traffic conditions and the road restrictions; considering that certain regularity can be observed in the road traffic conditions in practice, in this study, the road traffic conditions are imitated with the data collected during an observation period for estimating the expected speed for the routes that connect the pair of nodes in the network. Afterwards, formulas (3)-(6) are applied to estimate the emission of trucks on those routes by using the corresponding expected speed at the passing time.Furthermore, since “Technical Guidelines for Environmental Impact Assessment-Atmospheric Environment (HJ2.2-2008)” assessed that the conversion formula for the hourly average and daily average ofNO2 and NOx is NO2=0.9·NOx,NOx can be replaced by NO2 for further analysis without significant influence on the experimental results.As for the treatment fee of the exhaust gases, the environmental degradation costs for CO andNO2 are considered, where the environmental degradation costs are the corresponding depreciation costs for the environmental degradation because the nature absorbed the polluting gases of the trucks during the distribution process.According to the regulation “sewage charges standard management approaches” promulgated by the Chinese government, the standard polluting discharge fee is set as 0.6 RMB per pollutant equivalent. The specific pollutant equivalent value is 16.7kg and 0.95kg for CO andNO2, respectively. In consequence, unit control cost (UCC) for different pollutant gases can be calculated with the following formulas:(9)Pollutant Equivalents=Quality of Emissions Unit (kg)Corresponding Equivalent Value (kg)(10)Unit Control Cost (UCC)=Quality of the pollutant per Emission Unit (kg)Corresponding Equivalent Valuekg∗Adjustment coefficientIn consequence, the social cost for one motor-transporting truck running with speed v (km/h) can be defined with formula (11). It is worth noting that the parameter 10-3 is used in formula (11) for the purpose of adjustment because the unit “gram/km” is used in formulas (7) and (8) for calculating the emission, while the unit “kg” is applied in formula (9) for calculating the unit control cost.(11)Pev=UCCNO2·ENO2v+UCCCO·ECOv=0.6·10.95·1·ENO2v·10-3+0.6·116.7·1·ECOv·10-3Although the emission is not in linear relationship with the vehicle’s speed, it can be calculated as the sum of the emissions for each segment in which the vehicle traveled during unit time interval and the quality of the results depends on how the unit time interval is defined. In the extreme case, if the unit time interval is small enough, no significant difference will be observed between the sum of those segmental emission values and the exact emission. In consequence, the calculation of emission is simplified by using the segmental processing method with the average expected speed for each segment. The total social cost could be calculated with the following formula:(12)Cs=∑h=1H∑i∈Ω∑j∈Ωdij·Pe12V-ijtih+∑k=1kijh∗PeV-ijtih+k·Δt+Pe12V-ijtih+kijh∗·Δt+εijtih


## 3.3.3. Evaluation of the Cost Related to the Consumption of FuelCf

The fuel costCf could be obtained by the accumulation of the fuel cost per unit distance, and the calculation process applied by Wen et al. [12] for a Diesel LGV Euro II type vehicle, formula (13), is adopted in this study. (13)EFv=77.43+0.009v-0.015v2+0.00015v3+519v-1-70v-2wherev represents the vehicle’s travel speed (unit: km/h); EFv represents the fuel consumption (unit: gram/ km). It is worth noting that one liter of diesel weights about 840 grams. Although the price of diesel is strongly related to that of petroleum which keeps changing, this parameter cannot be regarded as sensitive in this model, so a predefined constant works. Therefore, the price of diesel is set as 5.4 RMB/L, the average price in the targeted region during the observation period, and the cost related to the consumption of fuel for one truck running with an average speed V- per kilometer (unit: RMB/(vehicle·Km)) can be evaluated with formula (14), where the average speed is calculated by using the segmental processing method based on the average speed for segments in which the vehicle traveled within unit time interval Δt. In consequence, the total fuel cost can be calculated with formula (15), which is quite similar to formula (12), except that Pf is used instead of Pe.(14)PfV-=5.4·77.43+0.009V--0.015V-2+0.00015V-3+519V--1-70V--2÷840(15)Cf=∑h=1H∑i∈Ω∑j∈Ωdij·Pf12V-ijtih+∑k=1kijh∗PfV-ijtih+k·Δt+Pf12V-ijtih+kijh∗·Δt+εijtih


## 3.4. Mathematical Model

(16) m i n  C t o t a l = C d + C f + C sSubject to(2), (12), and (15),(17)∑i=1H∑i∈Ωh∑j∈Ωhxijht≤H,T0≤t≤Tf(18)∫T0Tf∑j∈Ωox0jht=∫T0Tf∑i∈Ω0xiohth∈1,…,H(19)∫T0Tf∑h=1H∑i∈Ω∖jxijht=1,j∈ΩL(20)∫ToTf∑i∈Ω∑i∈ΩLxijht=1,h∈1,…,H(21)xijht∈0,1,T0≤t≤TfThe objective is to minimize both transportation cost, including drivers’ labor cost and fuel consumption, and treatment cost of pollutant emissions. Constraint (17) indicates that the number of the trucks which leave from the storage depot could not exceed the total number of the trucks owned by storage depot. Constraint (18) denotes that all trucks must start from and end at the only depot. Constraints (19) and (20) indicate that one 4S dealer could only be served by one truck.


## 4. Methodology

Since VRP problems are normally NP-hard, it is quite hard to find their exact solutions efficiently and it is important to make a compromise between the quality of the solution and the efficiency of the approach. Considering that genetic algorithm (GA) has been proven to have great parallelism, robustness, and a strong search capability, it is applied to this study as well.


### 4.1. Encoding and Decoding

In this study, the natural number coding is applied, and each natural number corresponds to a position of the node. In total, three kinds of node are defined: storage depot (starting point/end point), vehicle storage points, and the road junction node the trucks may pass by.Suppose that there are in totalR trucks in the depot and k 4S dealer shop demanded for service, and N road junctions are involved in the road map where the storage depot and 4S dealers are connected. Since one truck can be just responsible for one 4S shop, k trucks should be scheduled.By using number 0 to separate the route of different trucks, chromosome is arranged as follows:(0+1, i 1 1 +1, i 2 1 +1, i 3 1 +1, … i g 1 1 +1, j 1 +1, i g 1 + 1 1 +1, …, i g 1 + h 1 1 +1, 0+1, 0, 0+1, i 1 2 +1, i 2 2 +1, i 3 2 +1, … i g 2 2 +1, j 2 +1, i g 2 + 1 2 +1, …, i g 2 + h 2 2 +1, 0+1, 0, …, 0+1, i 1 k +1, i 2 k +1, i 3 k +1, … i g k k +1, j k +1, i g k + 1 k +1, …, i g k + h k k +1,0+1, 0, t 0 1 , t 0 2 , t 0 3 , t 0 4 , …, t 0 k )Storage depot is noted as “0”;ik,k∈{1,…,N} represents the road junctions and 4S dealers passed by the corresponding truck; jl,l∈{1,…,L} represents the 4S dealer served by this truck. In the process of encoding, all path nodes need to plus 1 as the programming language. In fact, this chromosome is composed of k+1 parts: the first k parts correspond to k motor-transporting trucks’ visiting orders, which are separated by “0”, and the last component represents trucks’ departure time from the depot.For example, a possible solution for the problem with 3 motor-transporting trucks serving 3 4S dealers can be as follows: truck 1 is the first one leaving from the storage depot, numbered as node 0, and passes through five route junctions, numbered as node 1 to node 5, to serve the first 4S dealer, numbered as node 1000. Afterwards, this truck will go back to the depot, node 0, passing by four road junctions, nodes 6 to 9. The gene representing the route of this truck can be encoded as (0+1, 1+1, 2+1, 3+1, 4+1, 5+1, 1000+1, 6+1, 7+1, 8+1, 9+1, 0+1)=(1, 2, 3, 4, 5, 6, 1001, 7, 8, 9, 10, 1); truck 2 starts from the storage depot, node 0, and passes through nodes 15 and 17 before serving the 4S dealer, node 1003, and then returns back to the depot by passing through nodes 18 and 16. The gene corresponding to truck 2 can be encoded as (0+1, 15+1, 17+1, 1003+1, 18+1, 16+1, 0+1) = (1, 16, 18, 1004, 19, 17, 1). Truck 3 starts also from the depot, serves 4S dealer 1004 after passing through three nodes, 19, 14, and 12, and returns back to the depot by passing through node 13. Similarly, the gene representing the path of truck 3 can be (0+1, 19+1, 14+1, 12+1, 1004+1, 13+1, 0+1)=(1, 20, 15, 13, 1005, 14, 1). When the departure time of these trucks is given, the last part of the gene can be defined as (t01,t02,t03). Combine all those genes together by inserting three “0”s as boundaries; a chromosome representing the mentioned arrangement is finally defined: (1, 2, 3, 4, 5, 6, 1001, 7, 8, 9, 10, 1, 0, 1, 16, 18, 1004, 19, 17, 1, 0, 1, 16, 18, 1004, 19, 17, 1, 0, 1, 20, 15, 13, 1005, 14, 1, 0, t01, t02, t03).


### 4.2. Generation of Initial Population

Consider the fact that if all the paths were created randomly, then the generated routes may not be feasible probably because of the existence of loop paths. Floyd algorithm is applied to generate a set of shortest paths as the basis of each initial solution so as to improve the quality of the initial population.Afterwards, randomly generate a number k between 0 and 1. If k is smaller than a fixed value set previously, then 2 nodes need to be inserted to the current shortest path, ensuring that the distances between the pair of inserted nodes as well as the distance between the inserted nodes and current nodes should be the shortest ones.The selected node may be inserted either before or after a 4S dealer. The judgement should be decided on each specific matter. It is worth noting that the random generation procedure may result in infeasible solutions, so a preventive feasibility check is necessary. If the solution is infeasible, then fine-tuning will be performed to make the solution feasible, that is, to make all the routes meet with each other and remove the circles except those that will return back to the depot.


### 4.3. Fitness Function and Selection

In this study, the inverse of the objective value is used as the fitness function, as shown in formula (22), and roulette wheel is applied as the selection scheme.(22)Fs=1fswhere F(s) represents the fitness of individual s andfs is the objective value corresponding to this solution.


### 4.4. Crossover and Mutation

Partially matched crossover applied in this study is to exchange the paths before a selected 4S dealer according to the crossover probability. An example is shown in Figure2 describing how two children are generated after the paths before 4S dealer 1001 are exchanged.Figure 2
Crossover procedure.Mutation takes place according to the predefined mutation probability, and the principle of mutation process is to generate a new path to replace a gene of a selected chromosome.


## 4.1. Encoding and Decoding

In this study, the natural number coding is applied, and each natural number corresponds to a position of the node. In total, three kinds of node are defined: storage depot (starting point/end point), vehicle storage points, and the road junction node the trucks may pass by.Suppose that there are in totalR trucks in the depot and k 4S dealer shop demanded for service, and N road junctions are involved in the road map where the storage depot and 4S dealers are connected. Since one truck can be just responsible for one 4S shop, k trucks should be scheduled.By using number 0 to separate the route of different trucks, chromosome is arranged as follows:(0+1, i 1 1 +1, i 2 1 +1, i 3 1 +1, … i g 1 1 +1, j 1 +1, i g 1 + 1 1 +1, …, i g 1 + h 1 1 +1, 0+1, 0, 0+1, i 1 2 +1, i 2 2 +1, i 3 2 +1, … i g 2 2 +1, j 2 +1, i g 2 + 1 2 +1, …, i g 2 + h 2 2 +1, 0+1, 0, …, 0+1, i 1 k +1, i 2 k +1, i 3 k +1, … i g k k +1, j k +1, i g k + 1 k +1, …, i g k + h k k +1,0+1, 0, t 0 1 , t 0 2 , t 0 3 , t 0 4 , …, t 0 k )Storage depot is noted as “0”;ik,k∈{1,…,N} represents the road junctions and 4S dealers passed by the corresponding truck; jl,l∈{1,…,L} represents the 4S dealer served by this truck. In the process of encoding, all path nodes need to plus 1 as the programming language. In fact, this chromosome is composed of k+1 parts: the first k parts correspond to k motor-transporting trucks’ visiting orders, which are separated by “0”, and the last component represents trucks’ departure time from the depot.For example, a possible solution for the problem with 3 motor-transporting trucks serving 3 4S dealers can be as follows: truck 1 is the first one leaving from the storage depot, numbered as node 0, and passes through five route junctions, numbered as node 1 to node 5, to serve the first 4S dealer, numbered as node 1000. Afterwards, this truck will go back to the depot, node 0, passing by four road junctions, nodes 6 to 9. The gene representing the route of this truck can be encoded as (0+1, 1+1, 2+1, 3+1, 4+1, 5+1, 1000+1, 6+1, 7+1, 8+1, 9+1, 0+1)=(1, 2, 3, 4, 5, 6, 1001, 7, 8, 9, 10, 1); truck 2 starts from the storage depot, node 0, and passes through nodes 15 and 17 before serving the 4S dealer, node 1003, and then returns back to the depot by passing through nodes 18 and 16. The gene corresponding to truck 2 can be encoded as (0+1, 15+1, 17+1, 1003+1, 18+1, 16+1, 0+1) = (1, 16, 18, 1004, 19, 17, 1). Truck 3 starts also from the depot, serves 4S dealer 1004 after passing through three nodes, 19, 14, and 12, and returns back to the depot by passing through node 13. Similarly, the gene representing the path of truck 3 can be (0+1, 19+1, 14+1, 12+1, 1004+1, 13+1, 0+1)=(1, 20, 15, 13, 1005, 14, 1). When the departure time of these trucks is given, the last part of the gene can be defined as (t01,t02,t03). Combine all those genes together by inserting three “0”s as boundaries; a chromosome representing the mentioned arrangement is finally defined: (1, 2, 3, 4, 5, 6, 1001, 7, 8, 9, 10, 1, 0, 1, 16, 18, 1004, 19, 17, 1, 0, 1, 16, 18, 1004, 19, 17, 1, 0, 1, 20, 15, 13, 1005, 14, 1, 0, t01, t02, t03).


## 4.2. Generation of Initial Population

Consider the fact that if all the paths were created randomly, then the generated routes may not be feasible probably because of the existence of loop paths. Floyd algorithm is applied to generate a set of shortest paths as the basis of each initial solution so as to improve the quality of the initial population.Afterwards, randomly generate a number k between 0 and 1. If k is smaller than a fixed value set previously, then 2 nodes need to be inserted to the current shortest path, ensuring that the distances between the pair of inserted nodes as well as the distance between the inserted nodes and current nodes should be the shortest ones.The selected node may be inserted either before or after a 4S dealer. The judgement should be decided on each specific matter. It is worth noting that the random generation procedure may result in infeasible solutions, so a preventive feasibility check is necessary. If the solution is infeasible, then fine-tuning will be performed to make the solution feasible, that is, to make all the routes meet with each other and remove the circles except those that will return back to the depot.


## 4.3. Fitness Function and Selection

In this study, the inverse of the objective value is used as the fitness function, as shown in formula (22), and roulette wheel is applied as the selection scheme.(22)Fs=1fswhere F(s) represents the fitness of individual s andfs is the objective value corresponding to this solution.


## 4.4. Crossover and Mutation

Partially matched crossover applied in this study is to exchange the paths before a selected 4S dealer according to the crossover probability. An example is shown in Figure2 describing how two children are generated after the paths before 4S dealer 1001 are exchanged.Figure 2
Crossover procedure.Mutation takes place according to the predefined mutation probability, and the principle of mutation process is to generate a new path to replace a gene of a selected chromosome.


## 5. Case Study

For the purpose of validation of the proposed scheme, the proposed method has been applied with the data collected from district Baoshan at Shanghai, one of the biggest cities in China, and imitates daily delivery of motors from the storage depot of a big vehicle assembly factory located at the northwest of Shanghai to its 4S dealers in the targeted region.


### 5.1. Data Preparation

As shown in Figure3, a simplified version of the road map of the targeted district is designed as follows: firstly, extract the possible paths, that is, the paths in which the heavy trucks are authorized, on the road map; then, number not only the depot but also the selected 4S dealers and all the involved road junctions, and link the pair of nodes with straight lines for all possible paths. As shown in Figure 4, node 0 represents the storage depot of the targeted vehicle assembly factory, nodes 23, 38, 39, 44, 46, 47, and 49 correspond to seven 4S dealers, which are observed and selected in the targeted region with specific address according to the service catalogue of the targeted vehicle brand, respectively, and the rest of the nodes represent road junctions. The numbers noted on the line between two nodes are the actual distance (unit: km).Figure 3
Creation of the simplified road map.Figure 4
Test on algorithm convergence with different objectives.The scheduled departure time of trucks is randomly selected between[9,18], indicating the regular working time of the truck drivers, and we suppose that the trucks set off on the hour.As for the algorithm, the size of the population is set as 60, so only the best 30 individuals will be retained in each iteration, and the rest of inferior individuals will be replaced by the individuals generated by crossover or mutation operations.The algorithm is coded with Matlab2013 on a computer with 2.3GHZ processor and 4.0GB memory with Windows 10. The procedure will terminate after 100 iterations. Crossover probability is set as 0.85, and mutation probability is set as 0.1.


### 5.2. Discussion on Results

#### 5.2.1. Discussion Algorithm Convergence

In order to test the stability of the proposed GA with 100 iterations, a set of monoobjective variants together with the original problems, the problem aiming at minimizing the composite cost, have been tested.As shown in Figure4, the best solution is obtained at around the 50th iteration for minimizing the composite cost; the solution with the minimal fuel cost was found at around the 40th iteration; the solution with the minimal emission cost is obtained at around the 60th iteration and the solution with minimal travel time is already attained around the 20th iteration. To sum up, the proposed GA can be always converged to the best solution within 100 iterations, so the result is quite encouraging.


#### 5.2.2. Discussion on Solution Quality

After we compare the solution for minimizing the composite cost (total cost) with other monoobjective solutions, it is observed that all the solutions pick the same distance (distance = 501.10 km), though the values for the other indicators vary a lot, as shown in Table2. With further analyses, it can be observed that(1)
the amount of emission is highly correlated with the consumption of fuel, though the “green” mode is not always the solution with minimal fuel consumption,(2)
The “green” drive mode, that is, the mode where minimizing the emissions needs much more travel time than the composite solution (more than 8%),(3)
The solution with minimal composite cost can dominate the other solution in total cost while not greatly degrading its quality on other objectives.Table 2
Comparison among solutions with different optimization objectives.
Objective Social cost(RMB) Fuel cost(RMB) Drivers’ cost(RMB) distance(km) Travel time(hour) Total cost (RMB) Min total cost 19.49 304.94 361.75 501.10 7.23 686.17 Min travel time 20.25 311.73 359.27 501.10 7.19 691.25 MinCf 18.00 290.12 394.86 501.10 7.90 702.98 MinCs 17.95 291.64 392.21 501.10 7.84 701.79A further study was organized by comparing the solution obtained by the proposed algorithm with the shortest-path solutions obtained by Floyd algorithm within different time slots. Since road traffic condition is not taken into consideration by Floyd algorithm, the starting time for all trucks remains the same, that is, the trucks set off on hour from 9:00 to 17:00 to evaluate the cost within different time slots, as shown in Table3.Table 3
Shortest-path solutions obtained by Floyd algorithms within various time slots.
Departure time Optimal distance Total cost Social cost Drivers’ cost Fuel cost Total time (km) (RMB) (RMB) (RMB) (RMB) (hour) 9:00 501.1 756.01 21.94 390.74 343.33 7.81 10:00 501.1 745.43 21.95 384.75 338.73 7.69 11:00 501.1 795.80 23.51 401.21 371.08 8.02 12:00 501.1 691.96 20.20 360.28 311.48 7.20 13:00 501.1 693.55 19.71 366.61 307.24 7.33 14:00 501.1 752.59 21.52 391.41 339.66 7.82 15:00 501.1 792.67 22.27 412.20 358.20 8.24 16:00 501.1 799.39 21.87 423.85 353.67 8.47 17:00 501.1 791.44 20.11 434.68 336.64 8.69 Average value 501.1 757.65 21.45 396.19 340.00 7.92Obviously, all costs vary during different time slots, indicating that the traffic condition can greatly influence the emissions, consumption of fuels, and travel time, which shows the importance of our work.While comparing those solutions with the solution obtained by the proposed method to minimize the composite cost, it can be observed that our solution dominates all of the shortest-path solutions!


## 5.1. Data Preparation

As shown in Figure3, a simplified version of the road map of the targeted district is designed as follows: firstly, extract the possible paths, that is, the paths in which the heavy trucks are authorized, on the road map; then, number not only the depot but also the selected 4S dealers and all the involved road junctions, and link the pair of nodes with straight lines for all possible paths. As shown in Figure 4, node 0 represents the storage depot of the targeted vehicle assembly factory, nodes 23, 38, 39, 44, 46, 47, and 49 correspond to seven 4S dealers, which are observed and selected in the targeted region with specific address according to the service catalogue of the targeted vehicle brand, respectively, and the rest of the nodes represent road junctions. The numbers noted on the line between two nodes are the actual distance (unit: km).Figure 3
Creation of the simplified road map.Figure 4
Test on algorithm convergence with different objectives.The scheduled departure time of trucks is randomly selected between[9,18], indicating the regular working time of the truck drivers, and we suppose that the trucks set off on the hour.As for the algorithm, the size of the population is set as 60, so only the best 30 individuals will be retained in each iteration, and the rest of inferior individuals will be replaced by the individuals generated by crossover or mutation operations.The algorithm is coded with Matlab2013 on a computer with 2.3GHZ processor and 4.0GB memory with Windows 10. The procedure will terminate after 100 iterations. Crossover probability is set as 0.85, and mutation probability is set as 0.1.


## 5.2. Discussion on Results

### 5.2.1. Discussion Algorithm Convergence

In order to test the stability of the proposed GA with 100 iterations, a set of monoobjective variants together with the original problems, the problem aiming at minimizing the composite cost, have been tested.As shown in Figure4, the best solution is obtained at around the 50th iteration for minimizing the composite cost; the solution with the minimal fuel cost was found at around the 40th iteration; the solution with the minimal emission cost is obtained at around the 60th iteration and the solution with minimal travel time is already attained around the 20th iteration. To sum up, the proposed GA can be always converged to the best solution within 100 iterations, so the result is quite encouraging.


### 5.2.2. Discussion on Solution Quality

After we compare the solution for minimizing the composite cost (total cost) with other monoobjective solutions, it is observed that all the solutions pick the same distance (distance = 501.10 km), though the values for the other indicators vary a lot, as shown in Table2. With further analyses, it can be observed that(1)
the amount of emission is highly correlated with the consumption of fuel, though the “green” mode is not always the solution with minimal fuel consumption,(2)
The “green” drive mode, that is, the mode where minimizing the emissions needs much more travel time than the composite solution (more than 8%),(3)
The solution with minimal composite cost can dominate the other solution in total cost while not greatly degrading its quality on other objectives.Table 2
Comparison among solutions with different optimization objectives.
Objective Social cost(RMB) Fuel cost(RMB) Drivers’ cost(RMB) distance(km) Travel time(hour) Total cost (RMB) Min total cost 19.49 304.94 361.75 501.10 7.23 686.17 Min travel time 20.25 311.73 359.27 501.10 7.19 691.25 MinCf 18.00 290.12 394.86 501.10 7.90 702.98 MinCs 17.95 291.64 392.21 501.10 7.84 701.79A further study was organized by comparing the solution obtained by the proposed algorithm with the shortest-path solutions obtained by Floyd algorithm within different time slots. Since road traffic condition is not taken into consideration by Floyd algorithm, the starting time for all trucks remains the same, that is, the trucks set off on hour from 9:00 to 17:00 to evaluate the cost within different time slots, as shown in Table3.Table 3
Shortest-path solutions obtained by Floyd algorithms within various time slots.
Departure time Optimal distance Total cost Social cost Drivers’ cost Fuel cost Total time (km) (RMB) (RMB) (RMB) (RMB) (hour) 9:00 501.1 756.01 21.94 390.74 343.33 7.81 10:00 501.1 745.43 21.95 384.75 338.73 7.69 11:00 501.1 795.80 23.51 401.21 371.08 8.02 12:00 501.1 691.96 20.20 360.28 311.48 7.20 13:00 501.1 693.55 19.71 366.61 307.24 7.33 14:00 501.1 752.59 21.52 391.41 339.66 7.82 15:00 501.1 792.67 22.27 412.20 358.20 8.24 16:00 501.1 799.39 21.87 423.85 353.67 8.47 17:00 501.1 791.44 20.11 434.68 336.64 8.69 Average value 501.1 757.65 21.45 396.19 340.00 7.92Obviously, all costs vary during different time slots, indicating that the traffic condition can greatly influence the emissions, consumption of fuels, and travel time, which shows the importance of our work.While comparing those solutions with the solution obtained by the proposed method to minimize the composite cost, it can be observed that our solution dominates all of the shortest-path solutions!


## 5.2.1. Discussion Algorithm Convergence

In order to test the stability of the proposed GA with 100 iterations, a set of monoobjective variants together with the original problems, the problem aiming at minimizing the composite cost, have been tested.As shown in Figure4, the best solution is obtained at around the 50th iteration for minimizing the composite cost; the solution with the minimal fuel cost was found at around the 40th iteration; the solution with the minimal emission cost is obtained at around the 60th iteration and the solution with minimal travel time is already attained around the 20th iteration. To sum up, the proposed GA can be always converged to the best solution within 100 iterations, so the result is quite encouraging.


## 5.2.2. Discussion on Solution Quality

After we compare the solution for minimizing the composite cost (total cost) with other monoobjective solutions, it is observed that all the solutions pick the same distance (distance = 501.10 km), though the values for the other indicators vary a lot, as shown in Table2. With further analyses, it can be observed that(1)
the amount of emission is highly correlated with the consumption of fuel, though the “green” mode is not always the solution with minimal fuel consumption,(2)
The “green” drive mode, that is, the mode where minimizing the emissions needs much more travel time than the composite solution (more than 8%),(3)
The solution with minimal composite cost can dominate the other solution in total cost while not greatly degrading its quality on other objectives.Table 2
Comparison among solutions with different optimization objectives.
Objective Social cost(RMB) Fuel cost(RMB) Drivers’ cost(RMB) distance(km) Travel time(hour) Total cost (RMB) Min total cost 19.49 304.94 361.75 501.10 7.23 686.17 Min travel time 20.25 311.73 359.27 501.10 7.19 691.25 MinCf 18.00 290.12 394.86 501.10 7.90 702.98 MinCs 17.95 291.64 392.21 501.10 7.84 701.79A further study was organized by comparing the solution obtained by the proposed algorithm with the shortest-path solutions obtained by Floyd algorithm within different time slots. Since road traffic condition is not taken into consideration by Floyd algorithm, the starting time for all trucks remains the same, that is, the trucks set off on hour from 9:00 to 17:00 to evaluate the cost within different time slots, as shown in Table3.Table 3
Shortest-path solutions obtained by Floyd algorithms within various time slots.
Departure time Optimal distance Total cost Social cost Drivers’ cost Fuel cost Total time (km) (RMB) (RMB) (RMB) (RMB) (hour) 9:00 501.1 756.01 21.94 390.74 343.33 7.81 10:00 501.1 745.43 21.95 384.75 338.73 7.69 11:00 501.1 795.80 23.51 401.21 371.08 8.02 12:00 501.1 691.96 20.20 360.28 311.48 7.20 13:00 501.1 693.55 19.71 366.61 307.24 7.33 14:00 501.1 752.59 21.52 391.41 339.66 7.82 15:00 501.1 792.67 22.27 412.20 358.20 8.24 16:00 501.1 799.39 21.87 423.85 353.67 8.47 17:00 501.1 791.44 20.11 434.68 336.64 8.69 Average value 501.1 757.65 21.45 396.19 340.00 7.92Obviously, all costs vary during different time slots, indicating that the traffic condition can greatly influence the emissions, consumption of fuels, and travel time, which shows the importance of our work.While comparing those solutions with the solution obtained by the proposed method to minimize the composite cost, it can be observed that our solution dominates all of the shortest-path solutions!


## 6. Conclusions

With the rapid development of the logistics industry, the business managers have realized that effective reduction of logistics cost has direct relationship with the enterprises’ economic interests and the improvement of competitive advantage by taking their social responsibilities. This study aims at optimizing the performance of motor-transporting services by taking into account dynamic traffic conditions. Based on a discretization of the distribution of the road traffic condition, the influence of the road congestion on vehicle speeds has been taken into account so as to create optimal delivery routes for motor-transporting trucks with a composite objective of minimizing both economic cost (driver cost and fuel cost) and social cost (vehicle emissions). A genetic algorithm, one of the most popular metaheuristics, has been proposed to solve this problem.With the data collected from the Baoshan district at Shanghai, one of the biggest cities in China, numerical experiments showed that the proposed algorithm can always converge to the best solution within 100 iterations. Considering the objective values, the solution with composite objective can dominate the others in general, while no significant deterioration is observed for other objectives. The results are quite encouraging.



---

*Source: 8703852-2018-12-02.xml*