# A Hybrid Tabu Search Algorithm for a Real-World Open Vehicle Routing Problem Involving Fuel Consumption Constraints

Authors: Yunyun Niu; Zehua Yang; Ping Chen; Jianhua Xiao
Journal: Complexity
 (2018)

---

## Abstract

Outsourcing logistics operation to third-party logistics has attracted more attention in the past several years. However, very few papers analyzed fuel consumption model in the context of outsourcing logistics. This problem involves more complexity than traditional open vehicle routing problem (OVRP), because the calculation of fuel emissions depends on many factors, such as the speed of vehicles, the road angle, the total load, the engine friction, and the engine displacement. Our paper proposed a green open vehicle routing problem (GOVRP) model with fuel consumption constraints for outsourcing logistics operations. Moreover, a hybrid tabu search algorithm was presented to deal with this problem. Experiments were conducted on instances based on realistic road data of Beijing, China, considering that outsourcing logistics plays an increasingly important role in China’s freight transportation. Open routes were compared with closed routes through statistical analysis of the cost components. Compared with closed routes, open routes reduce the total cost by 18.5% with the fuel emissions cost down by nearly 29.1% and the diver cost down by 13.8%. The effect of different vehicle types was also studied. Over all the 60- and 120-node instances, the mean total cost by using the light-duty vehicles is the lowest.


---

## Body

## 1. Introduction

Many developing countries are confronted with two problems: how to reduce economic costs and how to develop an environment-friendly society. As a result, researchers as well as companies with integrated logistics expertise tend to adopt new transportation models to counter these problems. Outsourcing logistics operations to the third-party logistics would reduce costs through better resource utilization and operations efficiency in freight transportation. It plays an increasingly important role in freight transportation. In that case, a company can hire vehicles from other companies to deliver its goods. Vehicles do not need return to the company as usual. They are usually described as the open vehicle routing problem (OVRP) [1]. Compared with the vehicle routing problem (VRP), routes in the OVRP model are open; see Figure 1.Figure 1
Open vehicle routing problem.The OVRP is NP-hard [2], so heuristics or metaheuristics methods are usually used to deal with it [3], such as the tabu search [4], the neighborhood-based search [5], particle swarm optimization [6], ant colony optimization [7], or evolutionary computing [8]. Hybrid metaheuristic algorithms were also designed to solve the OVRP [9]. Moreover, several variants of the OVRP were studied to model specific practical problems. OVRP with time windows (OVRPTW) was presented by [10] to model the delivery of multiproduct newspapers. The multidepot OVRP (MDOVRP) was first proposed by [11] to model the distribution of fresh meat. The open vehicle routing problem with decoupling points (OVRP-DP) was introduced in [12] to describe open routes performed by more than one carrier. The OVRP with uncertain demands was investigated to deal with nondeterministic customer demands and avoid unsatisfied demands or more extra operation cost [13]. However, among models studied in the past there are rare formulations considering the impact of fuel and carbon emission [14]. This paper is a contribution to this line of research.Carbon emissions along with freight transportation have hazardous impacts on the environment. How to minimize the fuel consumption becomes a hot topic. In [15], six fuel consumption models were compared with each other and several factors affecting carbon emissions in road transportation were analyzed. In [16], the pollution-routing problem (PRP) was introduced to evaluate the greenhouse gas emissions for the VRP. The total energy consumed on each road can be directly translated into greenhouse gas emissions with the PRP model. Reference [17] considered a heterogeneous vehicle fleet and extended the PRP model. Reference [18] presented a recent review of studies on green freight transportation problems.This study has been motivated by a real problem in Beijing, China. As outsourcing logistics is playing a more and more important role in China’s freight transportation, many companies hire vehicles from the third-party logistics. Vehicles do not need return to the depot after delivering products to customers. Each route departs from the depot and ends up with one of the customers. These companies are facing the problem of minimizing the total cost, including both fuel consumption cost and driver salaries.The main contributions of our paper are summarized as follows. (1) Fuel consumption was analyzed in the context of the OVRP; and the green open vehicle routing problem (GOVRP) model was constructed. With the purpose of optimizing the fuel emissions cost in the model, we introduced the comprehensive modal emission model (CMEM) into the OVRP model and extend the OVRP with an objective that accounts for the amount of greenhouse emissions. (2) A hybrid tabu search algorithm involving several neighborhood search strategies was proposed to solve the GOVRP. A modified nearest neighborhood heuristic (mNNH) was proposed to get the initial solution. It considered two factors load and distance when searching for a suitable initial solution. And then four neighborhood search operators were designed to produce the neighborhood of the current solution. (3) Computational experiments were conducted on instances derived from real geographical data of customers in Beijing, China. Both the effect of open routes and the effect of vehicle types were analyzed in respects of reducing total cost.


## 2. Mathematical Model of the GOVRP

The CMEM was developed by [19, 20] to calculate fuel emissions. In this section, we introduced the CMEM to the OVRP and formulated the mathematical model of the GOVRP. The fuel consumption Fh (in liters) of vehicle type h is given by [21] (1)Fh=λkhNhVhdv+Mhγhαd+βhγhdv2,where λ=ξ/κψ, γh=1/1000ntfη, α=τ+gsin⁡θ+gCrhcos⁡θ, and βh=0.5CdAhρ are constraints. Mh is the total vehicle weight, d is the distance, and v is the vehicle speed. Three terms of Fh are referred to as the engine module, the weight module, and the speed module, respectively. Notations and their default values are listed in the following two tables [17, 22]. Common parameters of vehicles are listed in Table 1. Specific parameters for different vehicle types are listed in Table 2.Table 1
Common parameters of vehicles.
Notation Description Typical values ξ Fuel-to-air mass ratio 1 g Gravitational constant (m/s2) 9.81 ρ Air density (kg/m3) 1.2041 Crh Coefficient of rolling resistance 0.01 η Efficiency parameter for diesel engines 0.45 fc Fuel and CO2 emissions cost (RMB/liter) 12.0165 fd Driver wage (RMB/s) 0.0111 κ Heating value of a typical diesel fuel (kj/g) 44 ψ Conversion factor (g/s to L/s) 737 ntf Vehicle drive train efficiency 0.45 vl Lower speed limit (m/s) 0 vu Upper speed limit (m/s) 27.8 (or 100 km/h) τ Acceleration (m/s2) 0Table 2
Specific parameters for different vehicle types.
Notation Description Light duty Medium duty Heavy duty w Curb weight (kg) 3500 5500 14,000 Q Maximum payload (kg) 4000 12,500 26,000 k Engine friction factor (kj/rev/liter) 0.25 0.20 0.15 N Engine speed (rev/s) 38.34 36.67 30.0 V Engine displacement (liter) 4.5 6.9 10.5 Cd Coefficient of aerodynamics drag 0.6 0.7 0.9 A Frontal surface area (m2) 7.0 8.0 10.0LetN=0,…,n be the set of customers and the depot, and let A={(i,j):i,j∈N,i≠j,j≠0} be the set of arcs. Node 0 denotes the depot, so the customer set is N0=N∖{0}. Q represents the capacity of vehicles. Variables qi means the demand of customer i. Variables dij is the distance from node i to node j. Variables fij are the total amount of flow on arc (i,j). The mathematical model of GOVRP is defined as follows:(2)Minimize∑i,j∈AλfckNVdij∑r=1Rzijrvr(3)+∑i,j∈Aλfcγαijdijwxij+fij(4)+∑i,j∈Aλfcβγdij∑r=1Rvr2zijr(5)+∑j∈N0fdsj(6)subject  to∑j∈N0x0j≤N0(7)∑i∈Nxij=1,∀j∈N0(8)∑j∈Nxij≤1,∀i∈N0(9)∑i=1nxi0=0(10)qjxij≤fij≤Q-qixij,∀i,j∈A(11)∑j∈Nfij-∑j∈Nfji=qi,∀i∈N0(12)∑r=1Rzijr=xij,∀i,j∈A(13)xij∈0,1,∀i,j∈A(14)zijr∈0,1,∀i,j∈A(15)fij≥0,∀i,j∈A.Formula (2)–(5) describes the objective of the GOVRP, where terms (2)–(4) calculate the total fuel consumption cost and term (5) measures the total driver wages. More specifically, fc is the fuel emissions cost per liter, and terms (2)–(4) calculate the fuel consumption costs induced by the engine module, the weight module, and the speed module, respectively. sj denotes the total time spent on a route where j is the last served customer.The binary variablexij is equal to 1 if there is a vehicle traveling on arc (i,j); otherwise, xij is equal to 0. Constraints (6)–(9) ensure that each customer is served by one vehicle and it is served only once. Vehicles do not return to the deport. If i is the last served customer, constraint (8) can be written as ∑j∈Nxij=0. Otherwise, it can be written as ∑j∈Nxij=1. Constraints (10) and (11) define flows. The binary variable zijr is equal to 1 when a vehicle travels on arc (i,j) at speed vr.


## 3. Hybrid Tabu Search Algorithm for the GOVRP

In this study, a hybrid tabu search algorithm including several neighborhood search strategies was designed to solve the GOVRP. The flowchart of this algorithm is shown in Figure2. The detailed steps are listed as follows.Figure 2
The flowchart of our algorithm.Step 1.
The initial setup includes initializing an empty tabu list and an empty candidate list, creating an initial solution, setting that initial solution as the best solution to date. A modified nearest neighborhood heuristic (mNNH) is used to gain the initial solution. We will elaborate on it specifically in Section3.1.Step 2.
If the stopping condition is satisfied, the search process stops, and the best solution is returned. Otherwise, it turns to Step3.Step 3.
The solution space is explored each step from a current solution to the accepted solutions in the neighborhood by using four efficient neighborhood search algorithms. For each neighbor of the current solutionXcurrent, the optimal speed on each arc of their routes is set by using the speed optimization algorithm according to [23].Step 4.
The neighboring solutions are checked for tabu elements. We search for the best solution and update the candidate list.Step 5.
If the best local candidate is better than the current best solution, update the current best solution. The local optimal solution is added to the tabu list. Then, turn to Step2.In this paper, the stopping condition is the maximum number of iterationsXmax. When our algorithm is iterated Xmax times, the algorithm is terminated.


### 3.1. The Initial Solution

We use a modified nearest neighborhood heuristic (mNNH) to obtain an initial solution. The mNNH considers two factors load and distance when searching for a suitable initial solution. In a delivery system, a vehicle can reduceqj load after servicing customer j. We define (16)Δfij¯=qjdij,i∈N,j∈Nucs,where Nunc is defined as the unrouted customer set.The mNNH builds routes one by one according to the following steps. The first route begins with an unrouted customerr, which can be calculated by the following equation:(17)r=argmaxj∈Nucs⁡Δf0j¯.Then, we calculate Δfij¯ between the current node r and the other unrouted nodes. We choose the node with the greatest current Δfij¯ value as the next node if the current route does not violate the vehicle capacity constraint. We update the current node r and search for the next node in the same way. When no customer can be assigned to the route, a new route is started. When all the customers are already routed, the process stops. The algorithm is described as Algorithm 1.Algorithm 1:A modified nearest neighborhood heuristic.
Input: Q, q1,…,qn Output: path (1) Set Nucs=1,…,n, path=∅, route=∅ (2) while  Nucs≠∅  do (3) Select a car (4) Set q←Q (5) while  q-qj≥0 and Nucs≠∅  do (6) Set route←route∪r, q←q-qj, i←j (7) Nucs←Nucs/j, r←arg⁡maxj∈Nucs⁡Δfij¯ (8) Set path←path∪route,route=∅ (9) return  path


### 3.2. The Neighborhood Search

The neighborhood of the current solutionXcurrent is first obtained by four neighborhood search operators. They cannot violate the capacity constraint during this process as before. Then, the optimal speed on each route is set according to [23].(  1) Random Operator (RO). It randomly selects one node from the solution and then randomly finds a possible position for it.(  2) High-Cost-Node Improvement Operator (HCNIO). As illustrated in Figure 3, the operator tries to reassign the high cost node u∗, because the total distance between its preceding customer and its following customer is the longest. Customer u∗ can be calculated as follows: (18)u∗=argmaxu∈N⁡diu+duj,where i is the preceding customer and j is the following customer.Figure 3
High-cost-node improvement operator.We compute the best possible position for nodeu based on (19)ci∗,u,j∗=min⁡ci,u,j,i,j∈N,i,j≠Nucs,where c(i,u,j)=diu+duj-dij is the cost for inserting node u between customer i and customer j and Nucs¯⊆N is the set of currently routed customers.(  3) Short-Route Improvement Operator (SRIO). The operator tries to combine or delete short routes by reassigning nodes belonging to those routes. A threshold l is set to evaluate the length of a route. Only if the length of a route is shorter than the threshold l, the nodes in that route can be reassigned to other positions. The process can be illustrated in Figure 4 (l=2). First, arcs in the shorter routes are deleted and then isolated nodes are assigned to other longer routes.Figure 4
Short-route improvement operator.The best possible position for each unrouted nodeu is also calculated by (19). By using (20), the most suitable customer is selected to be inserted in the route repeatedly. Unrouted nodes will be inserted to the current routes one by one. (20)c′i∗,u∗,j∗=min⁡ci∗,u,j∗.(  4) Random-Route-Improvement Operator (RRIO). Each route in the current solution has a chance p of being destroyed. In that case, customers in that route should be reassigned. The best possible position for each node u is calculated by (19). Then best customer to be inserted in the route is selected by using (20) repeatedly. All other unrouted customers will be inserted into the sequence one by one. As shown in Figure 5, two routes included in the dotted oval are destroyed; nodes in those routes are reassigned in possible positions.Figure 5
Random-route-improvement operator.For each neighbor of the current solutionXcurrent, the optimal speed on each route is set. According to [23], the optimal speed is (21)v∗=kNV2βγ+fd2βγfc1/3.


## 3.1. The Initial Solution

We use a modified nearest neighborhood heuristic (mNNH) to obtain an initial solution. The mNNH considers two factors load and distance when searching for a suitable initial solution. In a delivery system, a vehicle can reduceqj load after servicing customer j. We define (16)Δfij¯=qjdij,i∈N,j∈Nucs,where Nunc is defined as the unrouted customer set.The mNNH builds routes one by one according to the following steps. The first route begins with an unrouted customerr, which can be calculated by the following equation:(17)r=argmaxj∈Nucs⁡Δf0j¯.Then, we calculate Δfij¯ between the current node r and the other unrouted nodes. We choose the node with the greatest current Δfij¯ value as the next node if the current route does not violate the vehicle capacity constraint. We update the current node r and search for the next node in the same way. When no customer can be assigned to the route, a new route is started. When all the customers are already routed, the process stops. The algorithm is described as Algorithm 1.Algorithm 1:A modified nearest neighborhood heuristic.
Input: Q, q1,…,qn Output: path (1) Set Nucs=1,…,n, path=∅, route=∅ (2) while  Nucs≠∅  do (3) Select a car (4) Set q←Q (5) while  q-qj≥0 and Nucs≠∅  do (6) Set route←route∪r, q←q-qj, i←j (7) Nucs←Nucs/j, r←arg⁡maxj∈Nucs⁡Δfij¯ (8) Set path←path∪route,route=∅ (9) return  path


## 3.2. The Neighborhood Search

The neighborhood of the current solutionXcurrent is first obtained by four neighborhood search operators. They cannot violate the capacity constraint during this process as before. Then, the optimal speed on each route is set according to [23].(  1) Random Operator (RO). It randomly selects one node from the solution and then randomly finds a possible position for it.(  2) High-Cost-Node Improvement Operator (HCNIO). As illustrated in Figure 3, the operator tries to reassign the high cost node u∗, because the total distance between its preceding customer and its following customer is the longest. Customer u∗ can be calculated as follows: (18)u∗=argmaxu∈N⁡diu+duj,where i is the preceding customer and j is the following customer.Figure 3
High-cost-node improvement operator.We compute the best possible position for nodeu based on (19)ci∗,u,j∗=min⁡ci,u,j,i,j∈N,i,j≠Nucs,where c(i,u,j)=diu+duj-dij is the cost for inserting node u between customer i and customer j and Nucs¯⊆N is the set of currently routed customers.(  3) Short-Route Improvement Operator (SRIO). The operator tries to combine or delete short routes by reassigning nodes belonging to those routes. A threshold l is set to evaluate the length of a route. Only if the length of a route is shorter than the threshold l, the nodes in that route can be reassigned to other positions. The process can be illustrated in Figure 4 (l=2). First, arcs in the shorter routes are deleted and then isolated nodes are assigned to other longer routes.Figure 4
Short-route improvement operator.The best possible position for each unrouted nodeu is also calculated by (19). By using (20), the most suitable customer is selected to be inserted in the route repeatedly. Unrouted nodes will be inserted to the current routes one by one. (20)c′i∗,u∗,j∗=min⁡ci∗,u,j∗.(  4) Random-Route-Improvement Operator (RRIO). Each route in the current solution has a chance p of being destroyed. In that case, customers in that route should be reassigned. The best possible position for each node u is calculated by (19). Then best customer to be inserted in the route is selected by using (20) repeatedly. All other unrouted customers will be inserted into the sequence one by one. As shown in Figure 5, two routes included in the dotted oval are destroyed; nodes in those routes are reassigned in possible positions.Figure 5
Random-route-improvement operator.For each neighbor of the current solutionXcurrent, the optimal speed on each route is set. According to [23], the optimal speed is (21)v∗=kNV2βγ+fd2βγfc1/3.


## 4. Computational Analysis

Experiments are run with data derived from real geographical distances of customers in Beijing. Three smaller classes with 10, 20, and 30 customers and four larger classes with 60, 80, 100, and 120 customers are generated. Each class includes 10 instances. All the customers involved in this study are shown in Figure6. The algorithmic parameters values are given in Table 3.Table 3
Algorithmic parameters values.
Notation Description Typical values Xmax The maximum iteration number 500 lt The length of Tabu list 5 n1 The number of RO in each step 40 n2 The number of HCNIO in each step 5 l The threshold in SRIO in each step 3 p Each route has a chancep to be improved 50%Figure 6
Customer nodes.


### 4.1. Effect of Objectives Min TD, Min FEC and Min DC

Three different objectives, Min TD (total distance), Min FEC (fuel emissions cost), and Min DC (driver cost), are used to minimize the total distance, fuel emissions cost, and driver cost, respectively. We obtained solutions with different cost components on each performance measure and analyzed the effect of different objectives. Experiments were conducted on 10-, 20-, and 30-node instances by using light-duty vehicles. The mean result of each instance collected over ten runs is reported; see Tables4, 5, and 6. The columns display total distance (TD), execution time (ET), fuel emissions cost (FEC), driver cost (DC), total cost (TC), and CO2 emissions (CE). Table 7 presents the average results of each class.Table 4
Cost components with Min TC.
Instances TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) BJ10_01 160000 1.52 641.04 1427.23 2068.27 123.77 BJ10_02 215400 1.21 860 1669.73 2529.73 166.04 BJ10_03 148200 1.43 598.82 1515.92 2114.74 115.61 BJ10_04 125700 1.32 512.95 1604.03 2116.98 99.03 BJ10_05 131600 1.39 527.49 1261.2 1788.69 101.84 BJ10_06 195700 1.28 800.49 1731.86 2532.35 154.55 BJ10_07 161200 1.51 629.72 1462.42 2092.15 121.58 BJ10_08 160500 1.46 643.06 1598.9 2241.96 124.15 BJ10_09 174300 1.29 708.01 1687.92 2395.93 136.69 BJ10_10 196900 1.32 794.67 1724.37 2519.03 153.42  BJ20_01 207050 1.78 847.71 2872.04 3719.75 163.67 BJ20_02 327870 1.89 1313.52 3411.58 4725.1 253.6 BJ20_03 214080 1.84 869.09 2954.44 3823.52 167.79 BJ20_04 255540 2.01 1012 2740.72 3752.73 195.39 BJ20_05 276920 1.88 1118.67 3355.55 4474.22 215.98 BJ20_06 289340 2.18 1144.59 3143.29 4287.89 220.98 BJ20_07 303290 1.74 1257.06 3656.81 4913.87 242.7 BJ20_08 272120 1.8 1118.93 2995.08 4114.01 216.03 BJ20_09 310000 1.93 1250.4 3023.52 4273.93 241.41 BJ20_10 273670 2.25 1086.06 2945.31 4031.37 209.68  BJ30_01 383030 2.52 1594.7 4489.58 6084.28 307.89 BJ30_02 413850 2.62 1653.91 4497.14 6151.06 319.32 BJ30_03 425160 2.27 1763.89 4932.42 6696.31 340.55 BJ30_04 422810 2.55 1735.05 4702.76 6437.8 334.98 BJ30_05 348850 2.82 1405.68 4627.92 6033.6 271.39 BJ30_06 459680 2.28 1907.54 4772.35 6679.89 368.28 BJ30_07 460900 2.51 1900.86 4826.39 6727.26 367 BJ30_08 423510 2.38 1742.33 4625.07 6367.4 336.39 BJ30_09 447060 2.35 1869.31 4768.26 6637.57 360.9 BJ30_10 281950 2.59 1141.17 4007.94 5149.11 220.32Table 5
Cost components with Min FEC.
Instances TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) BJ10_01 160000 1.5 641.04 1427.23 2068.27 123.77 BJ10_02 215400 1.21 860 1669.73 2529.73 166.04 BJ10_03 148200 1.56 598.82 1515.92 2114.74 115.61 BJ10_04 126500 1.37 511.94 1607.36 2119.3 98.84 BJ10_05 132750 1.47 519.04 1265.98 1785.02 100.21 BJ10_06 195500 1.31 800.42 1731.02 2531.45 154.54 BJ10_07 161200 1.57 629.72 1462.42 2092.15 121.58 BJ10_08 161900 1.5 640.76 1604.72 2245.47 123.71 BJ10_09 174300 1.3 708.01 1687.92 2395.93 136.69 BJ10_10 196900 1.33 794.67 1724.37 2519.03 153.42  BJ20_01 207400 1.76 849.35 2873.49 3722.84 163.98 BJ20_02 328330 1.95 1309.37 3413.49 4722.86 252.8 BJ20_03 214900 1.97 872.32 2957.85 3830.17 168.42 BJ20_04 255610 2.18 1011.35 2741.01 3752.36 195.26 BJ20_05 277600 1.94 1120.84 3358.38 4479.21 216.4 BJ20_06 289930 2.25 1139.38 3145.75 4285.12 219.98 BJ20_07 304560 1.79 1262.84 3662.1 4924.93 243.81 BJ20_08 273430 1.88 1118.78 3000.53 4119.3 216 BJ20_09 309870 2.04 1247.69 3022.98 4270.67 240.89 BJ20_10 273750 2.25 1082.62 2945.65 4028.27 209.02  BJ30_01 382650 2.42 1589.04 4488 6077.04 306.79 BJ30_02 413260 2.74 1652.82 4494.69 6147.51 319.11 BJ30_03 421230 2.27 1747.69 4916.08 6663.77 337.42 BJ30_04 422830 2.43 1736.24 4702.84 6439.08 335.21 BJ30_05 352760 2.75 1417.82 4644.18 6062 273.74 BJ30_06 458930 2.19 1903.61 4769.23 6672.84 367.53 BJ30_07 458810 2.49 1884.59 4817.7 6702.3 363.86 BJ30_08 426290 2.32 1748.32 4636.63 6384.94 337.54 BJ30_09 452450 2.3 1890.76 4790.68 6681.44 365.05 BJ30_10 281430 2.6 1135.95 4005.78 5141.73 219.32Table 6
Cost component with Min DC.
Instances TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) BJ10_01 159400 1.44 644.62 1424.74 2069.36 124.46 BJ10_02 215400 1.21 860 1669.73 2529.73 166.04 BJ10_03 148200 1.47 598.82 1515.92 2114.74 115.61 BJ10_04 125200 1.39 518.15 1601.95 2120.11 100.04 BJ10_05 131600 1.39 530.81 1261.2 1792 102.48 BJ10_06 195620 1.3 800.46 1731.52 2531.99 154.54 BJ10_07 161200 1.45 629.72 1462.42 2092.15 121.58 BJ10_08 160400 1.48 646.39 1598.48 2244.87 124.8 BJ10_09 174300 1.29 709.63 1687.92 2397.55 137.01 BJ10_10 196900 1.32 794.67 1724.37 2519.03 153.42  BJ20_01 206800 1.74 846.78 2871 3717.78 163.49 BJ20_02 329150 1.82 1327.82 3416.9 4744.72 256.36 BJ20_03 215720 1.81 879.27 2961.26 3840.53 169.76 BJ20_04 256490 1.99 1018.96 2744.67 3763.63 196.73 BJ20_05 280140 1.85 1134.25 3368.94 4503.19 218.99 BJ20_06 292080 2.1 1158.64 3154.69 4313.33 223.7 BJ20_07 303580 1.7 1259.44 3658.02 4917.46 243.16 BJ20_08 272670 1.78 1123.32 2997.37 4120.69 216.88 BJ20_09 310710 1.89 1254.84 3026.47 4281.31 242.27 BJ20_10 271600 2.18 1076.31 2936.7 4013.01 207.8  BJ30_01 381430 2.35 1589.86 4482.93 6072.79 306.95 BJ30_02 420450 2.47 1689.85 4524.59 6214.44 326.26 BJ30_03 427000 2.15 1773.68 4940.07 6713.75 342.44 BJ30_04 422740 2.35 1748.59 4702.47 6451.05 337.6 BJ30_05 352590 2.57 1423.67 4643.47 6067.14 274.87 BJ30_06 458020 2.17 1904.47 4765.45 6669.91 367.69 BJ30_07 459540 2.33 1897.68 4820.74 6718.42 366.38 BJ30_08 430970 2.21 1784.59 4656.09 6440.68 344.55 BJ30_09 445190 2.18 1864.22 4760.49 6624.71 359.92 BJ30_10 282940 2.44 1146.82 4012.06 5158.88 221.42Table 7
Cost components with different objectives.
Instances Objective TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) 10-node Min FEC 167265 1.41 670.44 1569.67 2240.11 129.44 Min DC 166822 1.37 673.33 1567.83 2241.15 130 Min TC 166950 1.37 671.63 1568.36 2239.98 129.67  20-node Min FEC 273538 2 1101.45 3112.12 4213.57 212.66 Min DC 273894 1.89 1107.96 3113.6 4221.57 213.91 Min TC 272988 1.93 1101.8 3109.83 4211.64 212.72  30-node Min FEC 407064 2.45 1670.68 4626.58 6297.27 322.56 Min DC 408087 2.32 1682.34 4630.84 6313.18 324.81 Min TC 406680 2.49 1671.44 4624.98 6296.43 322.7On average of 10-node class, the fuel emissions cost represents about 30% of the total cost. For 20- and 30-node classes, the fuel emissions cost accounts for approximately 26% of the total cost. The carbon dioxide emissions increase with the number of customers. Only considering the driver cost in the objective leads to the most carbon dioxide emissions and the poorest total cost performance. Only considering the fuel emissions gets solutions with the lowest carbon dioxide emissions, but a higher total cost. Min TC as an objective yields the lowest total cost and the shortest total distance.


### 4.2. Effect of Open Routes

In this subsection, we compared the total cost of open routes with that of closed routes. Experiments were also conducted on smaller instance classes by using light-duty vehicles. The mean results of closed routes collected over ten runs are listed in Table8. The average results of each class are reported in Table 9 to illustrate the effect of open routes. As shown in Table 9, open routes reduce the total cost by 18.5% with the fuel emissions cost down by nearly 29.1% and the diver cost down by 13.8% over all the instances.Table 8
Cost components with closed routes.
Instances TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) BJ10_01 243300 1.35 973.42 1773.67 2747.08 187.94 BJ10_02 287900 1.23 1143.69 1971.25 3114.95 220.81 BJ10_03 233000 1.28 929.49 1868.6 2798.09 179.46 BJ10_04 193600 1.33 774.88 1886.42 2661.31 149.61 BJ10_05 190300 1.33 752.29 1505.32 2257.61 145.24 BJ10_06 306900 1.26 1216.62 2194.33 3410.94 234.89 BJ10_07 225500 1.19 914.3 1729.84 2644.14 176.52 BJ10_08 222400 1.33 883.91 1856.33 2740.24 170.65 BJ10_09 250200 1.29 1001.88 2003.58 3005.46 193.43 BJ10_10 285200 1.3 1133.7 2091.6 3225.3 218.88  BJ20_01 296880 1.75 1191.94 3245.63 4437.57 230.13 BJ20_02 432490 1.74 1733.98 3846.68 5580.66 334.78 BJ20_03 302470 1.93 1227.85 3322.04 4549.9 237.06 BJ20_04 350360 1.8 1408.36 3135.07 4543.43 271.91 BJ20_05 397350 1.75 1601.07 3856.4 5457.48 309.12 BJ20_06 404900 1.76 1627.02 3623.9 5250.92 314.13 BJ20_07 453910 1.79 1833.88 4283.23 6117.1 354.06 BJ20_08 377970 1.71 1526.82 3435.3 4962.12 294.78 BJ20_09 458430 1.79 1842.5 3640.83 5483.32 355.73 BJ20_10 380810 1.75 1533.55 3390.9 4924.45 296.08  BJ30_01 544130 2.53 2213.58 5159.58 7373.16 427.37 BJ30_02 602750 2.32 2434.58 5282.76 7717.34 470.04 BJ30_03 603420 2.25 2446.55 5673.79 8120.33 472.35 BJ30_04 574210 2.51 2328.31 5332.41 7660.72 449.52 BJ30_05 495510 2.46 2006.16 5237.86 7244.02 387.33 BJ30_06 636960 2.23 2584.8 5509.64 8094.44 499.04 BJ30_07 666890 2.43 2711.67 5683.09 8394.76 523.54 BJ30_08 588990 2.25 2385.82 5313.28 7699.1 460.63 BJ30_09 640480 2.22 2600.55 5572.68 8173.23 502.08 BJ30_10 394830 2.35 1599.07 4477.4 6076.47 308.73Table 9
Cost components of different types of routes.
Instances Type of routes TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) 10-node Open 166950 1.37 671.63 1568.36 2239.98 129.67 Closed 243830 1.29 972.42 1888.09 2860.51 187.74  20-node Open 272988 1.93 1101.8 3109.83 4211.64 212.72 Closed 385557 1.78 1552.7 3578 5130.7 299.78  30-node Open 406680 2.49 1671.44 4624.98 6296.43 322.7 Closed 574817 2.36 2331.11 5324.25 7655.36 450.06


### 4.3. Results for Larger Scale Instances

Experiments were also conducted on the four largest sets with the objective Min TC. The results collected over ten runs are reported in Table10 by using light-duty vehicles. Notations BS, MS, WS, SD, and ET in columns represent the best solution, mean solution, the worst solution, standard deviation, and execution time, respectively. As shown in Table 10, the total cost increases with the number of customers.Table 10
Computational results on larger scale instances.
Instance BS (RMB) MS (RMB) WS (RMB) SD ET (s) BJ60_01 11061.79 11254.42 11417.58 92.8 5.37 BJ60_02 10309.83 10393.21 10492.87 62.43 4.88 BJ60_03 11574.38 11790.03 11933.82 94.03 5.06 BJ60_04 12094.39 12212.64 12462.25 95.54 5.14 BJ60_05 11236.35 11320.09 11431.91 52.74 5.44 BJ60_06 11883.87 12040.48 12249.58 94.39 4.89 BJ60_07 12600.43 12745.03 12867.3 92.99 4.74 BJ60_08 11939.78 12060.86 12173.83 59.37 4.73 BJ60_09 11583.85 11727.88 11922.82 95.35 4.7 BJ60_10 12938.11 13121.2 13364.03 114.64 4.74  BJ80_01 14787.03 15036.55 15227.3 127.09 7.56 BJ80_02 14018.34 14220.78 14411.5 115.1 7.18 BJ80_03 14714.36 14964.93 15139.74 125.11 7.72 BJ80_04 13872.84 14065.74 14550.33 199.54 7.6 BJ80_05 14613.9 14788.56 15078.73 148.41 7.52 BJ80_06 16857.87 17148.49 17572.08 217.41 6.83 BJ80_07 15371.73 15632.16 15925.82 170.46 7.1 BJ80_08 14273.97 14484.07 14815.66 183.64 7.39 BJ80_09 14526.1 14743.32 14969.09 122.54 7.19 BJ80_10 14736.48 14942.92 15284.86 137.4 7.09  BJ100_01 19330.25 19617.94 20069.92 203.78 10.22 BJ100_02 20194.9 20701.34 21013.24 215.65 10.33 BJ100_03 20081.75 20286.97 20556.28 138.13 10.38 BJ100_04 18483.02 18689.28 18893.14 114.28 9.87 BJ100_05 18776.99 18983.5 19256.85 165.22 10.01 BJ100_06 17478.28 17764.38 18119.14 187.27 10.5 BJ100_07 18451.61 18775.37 18938.18 167.43 10.49 BJ100_08 18527.85 18762.86 18941.62 142.11 10.52 BJ100_09 17458.07 18048.33 18385.66 259.49 10.92 BJ100_10 20847 21099.27 21541.13 201.04 10  BJ120_01 21699.63 21954.27 22209.26 135.47 15.38 BJ120_02 22803.9 23135.32 23736.67 273.1 16.09 BJ120_03 22074.76 22569.41 22921.39 270.03 17.46 BJ120_04 22380.9 22560.26 22764.57 138.1 16.91 BJ120_05 22602.33 23308.71 23666.93 289.5 14.39 BJ120_06 22656.5 22975.25 23166.4 145.56 14.44 BJ120_07 21156.14 21711.99 22170.6 301.69 14.37 BJ120_08 20837.63 21069.17 21418.09 211.61 15.66 BJ120_09 21865.67 22195.93 22498.88 170.26 14.43 BJ120_10 22705.98 23054.33 23556.8 217.54 14.4


### 4.4. Results with Different Vehicle Types

Experiments were conducted on the 60- and 120-node instances by using different types of vehicles. In this subsection, the analysis focuses on which type of vehicle is the most suitable to minimize the total cost. The specific vehicle parameters are listed in Table2. Results with different vehicle types are listed in Tables 11 and 12. Over all the instances in the two classes, the mean total cost by using the light-duty vehicles is the lowest. For 120-node instances, the mean total cost by using medium-duty vehicles increases by 4.8% and the result by using heavy-duty vehicles rises 23.6%. For 60-node instances, the mean total cost by using medium-duty vehicles increases by 7.7% and the value by using heavy-duty vehicles rises 28%.Table 11
Computational results on the 60-node instances by using different vehicles.
Type of vehicles Instance BS (RMB) MS (RMB) WS (RMB) SD ET (s) Only light duty BJ60_01 11061.79 11254.42 11417.58 92.8 5.37 BJ60_02 10309.83 10393.21 10492.87 62.43 4.88 BJ60_03 11574.38 11790.03 11933.82 94.03 5.06 BJ60_04 12094.39 12212.64 12462.25 95.54 5.14 BJ60_05 11236.35 11320.09 11431.91 52.74 5.44 BJ60_06 11883.87 12040.48 12249.58 94.39 4.89 BJ60_07 12600.43 12745.03 12867.3 92.99 4.74 BJ60_08 11939.78 12060.86 12173.83 59.37 4.73 BJ60_09 11583.85 11727.88 11922.82 95.35 4.7 BJ60_10 12938.11 13121.2 13364.03 114.64 4.74  Only medium duty BJ60_01 12449.13 12616.53 12823.93 109.15 4.51 BJ60_02 11328.74 11557.08 11780.96 125.14 4.19 BJ60_03 12959.56 13222.5 13390.12 121.83 4.42 BJ60_04 13411.61 13630.23 13870.71 147.61 4.4 BJ60_05 12515.46 12678.95 12843.89 87.75 4.63 BJ60_06 13037.75 13302.09 13413.95 100.83 4.29 BJ60_07 12360.13 12425.3 12579.82 63.71 4.22 BJ60_08 12942.29 13064.34 13360.38 121.13 4.49 BJ60_09 12112.23 12348.68 12563.22 122.72 4.43 BJ60_10 12832.96 12974.52 13105.98 88.75 4.03  Only heavy duty BJ60_01 14787.24 14995.59 15334.52 176.58 9.38 BJ60_02 13418.08 13700.42 13911.3 143.14 7.91 BJ60_03 15469.9 15746.78 16052.25 183.26 7.54 BJ60_04 16164.2 16411.77 16729.41 172.11 7.78 BJ60_05 14772.72 14937.7 15269.37 154.91 7.98 BJ60_06 15893.22 16093.82 16272.75 133.43 7.41 BJ60_07 14441.09 14606.23 14757.43 103.53 7.46 BJ60_08 15088.73 15473.2 15638.19 152.24 7.61 BJ60_09 14521.68 14811.72 14972.54 119.53 7.22 BJ60_10 14961.08 15164.55 15321.96 109.22 6.88Table 12
Computational results on the 120-node instances by using different vehicles.
Type of vehicles Instance BS (RMB) MS (RMB) WS (RMB) SD ET (s) Only light duty BJ120_01 21699.63 21954.27 22209.26 135.47 15.38 BJ120_02 22803.9 23135.32 23736.67 273.1 16.09 BJ120_03 22074.76 22569.41 22921.39 270.03 17.46 BJ120_04 22380.9 22560.26 22764.57 138.1 16.91 BJ120_05 22602.33 23308.71 23666.93 289.5 14.39 BJ120_06 22656.5 22975.25 23166.4 145.56 14.44 BJ120_07 21156.14 21711.99 22170.6 301.69 14.37 BJ120_08 20837.63 21069.17 21418.09 211.61 15.66 BJ120_09 21865.67 22195.93 22498.88 170.26 14.43 BJ120_10 22705.98 23054.33 23556.8 217.54 14.4  Only medium duty BJ120_01 23290.23 23541.68 23691.38 124.27 12.99 BJ120_02 23133.82 23473.76 23710.98 178.16 12.55 BJ120_03 23320.12 23573.14 23908.95 186.7 12.9 BJ120_04 23117.27 23545.71 23757.64 194.07 13.01 BJ120_05 23687.6 24099.96 24385.48 207.61 13.08 BJ120_06 23273.19 23621.69 23870.13 162.68 12.49 BJ120_07 23136.08 23257.6 23424.7 91.21 13.13 BJ120_08 22752.22 23085.88 23320.75 200.2 13.35 BJ120_09 23171.61 23279.47 23450.24 85.55 12.65 BJ120_10 23476.59 23845.67 24258.76 222.02 12.58  Only heavy duty BJ120_01 27565.54 27974.16 28341.07 204.51 20.49 BJ120_02 27337.33 27628.98 28138.69 243.32 18.79 BJ120_03 26855.88 27379.48 27991.72 327.29 20.89 BJ120_04 27580.86 27834.25 28040.53 168.47 21.69 BJ120_05 28189.69 28500.43 28755.03 186.67 18.96 BJ120_06 27679.42 27933.79 28172.32 143.93 19.15 BJ120_07 26969.4 27668.76 28014.39 286.72 21.03 BJ120_08 26617.8 27268.75 27742.87 315.44 22.64 BJ120_09 27000.07 27382.75 27631.08 187.61 20.21 BJ120_10 27663.24 27887.53 28107.04 126.69 20.54


## 4.1. Effect of Objectives Min TD, Min FEC and Min DC

Three different objectives, Min TD (total distance), Min FEC (fuel emissions cost), and Min DC (driver cost), are used to minimize the total distance, fuel emissions cost, and driver cost, respectively. We obtained solutions with different cost components on each performance measure and analyzed the effect of different objectives. Experiments were conducted on 10-, 20-, and 30-node instances by using light-duty vehicles. The mean result of each instance collected over ten runs is reported; see Tables4, 5, and 6. The columns display total distance (TD), execution time (ET), fuel emissions cost (FEC), driver cost (DC), total cost (TC), and CO2 emissions (CE). Table 7 presents the average results of each class.Table 4
Cost components with Min TC.
Instances TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) BJ10_01 160000 1.52 641.04 1427.23 2068.27 123.77 BJ10_02 215400 1.21 860 1669.73 2529.73 166.04 BJ10_03 148200 1.43 598.82 1515.92 2114.74 115.61 BJ10_04 125700 1.32 512.95 1604.03 2116.98 99.03 BJ10_05 131600 1.39 527.49 1261.2 1788.69 101.84 BJ10_06 195700 1.28 800.49 1731.86 2532.35 154.55 BJ10_07 161200 1.51 629.72 1462.42 2092.15 121.58 BJ10_08 160500 1.46 643.06 1598.9 2241.96 124.15 BJ10_09 174300 1.29 708.01 1687.92 2395.93 136.69 BJ10_10 196900 1.32 794.67 1724.37 2519.03 153.42  BJ20_01 207050 1.78 847.71 2872.04 3719.75 163.67 BJ20_02 327870 1.89 1313.52 3411.58 4725.1 253.6 BJ20_03 214080 1.84 869.09 2954.44 3823.52 167.79 BJ20_04 255540 2.01 1012 2740.72 3752.73 195.39 BJ20_05 276920 1.88 1118.67 3355.55 4474.22 215.98 BJ20_06 289340 2.18 1144.59 3143.29 4287.89 220.98 BJ20_07 303290 1.74 1257.06 3656.81 4913.87 242.7 BJ20_08 272120 1.8 1118.93 2995.08 4114.01 216.03 BJ20_09 310000 1.93 1250.4 3023.52 4273.93 241.41 BJ20_10 273670 2.25 1086.06 2945.31 4031.37 209.68  BJ30_01 383030 2.52 1594.7 4489.58 6084.28 307.89 BJ30_02 413850 2.62 1653.91 4497.14 6151.06 319.32 BJ30_03 425160 2.27 1763.89 4932.42 6696.31 340.55 BJ30_04 422810 2.55 1735.05 4702.76 6437.8 334.98 BJ30_05 348850 2.82 1405.68 4627.92 6033.6 271.39 BJ30_06 459680 2.28 1907.54 4772.35 6679.89 368.28 BJ30_07 460900 2.51 1900.86 4826.39 6727.26 367 BJ30_08 423510 2.38 1742.33 4625.07 6367.4 336.39 BJ30_09 447060 2.35 1869.31 4768.26 6637.57 360.9 BJ30_10 281950 2.59 1141.17 4007.94 5149.11 220.32Table 5
Cost components with Min FEC.
Instances TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) BJ10_01 160000 1.5 641.04 1427.23 2068.27 123.77 BJ10_02 215400 1.21 860 1669.73 2529.73 166.04 BJ10_03 148200 1.56 598.82 1515.92 2114.74 115.61 BJ10_04 126500 1.37 511.94 1607.36 2119.3 98.84 BJ10_05 132750 1.47 519.04 1265.98 1785.02 100.21 BJ10_06 195500 1.31 800.42 1731.02 2531.45 154.54 BJ10_07 161200 1.57 629.72 1462.42 2092.15 121.58 BJ10_08 161900 1.5 640.76 1604.72 2245.47 123.71 BJ10_09 174300 1.3 708.01 1687.92 2395.93 136.69 BJ10_10 196900 1.33 794.67 1724.37 2519.03 153.42  BJ20_01 207400 1.76 849.35 2873.49 3722.84 163.98 BJ20_02 328330 1.95 1309.37 3413.49 4722.86 252.8 BJ20_03 214900 1.97 872.32 2957.85 3830.17 168.42 BJ20_04 255610 2.18 1011.35 2741.01 3752.36 195.26 BJ20_05 277600 1.94 1120.84 3358.38 4479.21 216.4 BJ20_06 289930 2.25 1139.38 3145.75 4285.12 219.98 BJ20_07 304560 1.79 1262.84 3662.1 4924.93 243.81 BJ20_08 273430 1.88 1118.78 3000.53 4119.3 216 BJ20_09 309870 2.04 1247.69 3022.98 4270.67 240.89 BJ20_10 273750 2.25 1082.62 2945.65 4028.27 209.02  BJ30_01 382650 2.42 1589.04 4488 6077.04 306.79 BJ30_02 413260 2.74 1652.82 4494.69 6147.51 319.11 BJ30_03 421230 2.27 1747.69 4916.08 6663.77 337.42 BJ30_04 422830 2.43 1736.24 4702.84 6439.08 335.21 BJ30_05 352760 2.75 1417.82 4644.18 6062 273.74 BJ30_06 458930 2.19 1903.61 4769.23 6672.84 367.53 BJ30_07 458810 2.49 1884.59 4817.7 6702.3 363.86 BJ30_08 426290 2.32 1748.32 4636.63 6384.94 337.54 BJ30_09 452450 2.3 1890.76 4790.68 6681.44 365.05 BJ30_10 281430 2.6 1135.95 4005.78 5141.73 219.32Table 6
Cost component with Min DC.
Instances TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) BJ10_01 159400 1.44 644.62 1424.74 2069.36 124.46 BJ10_02 215400 1.21 860 1669.73 2529.73 166.04 BJ10_03 148200 1.47 598.82 1515.92 2114.74 115.61 BJ10_04 125200 1.39 518.15 1601.95 2120.11 100.04 BJ10_05 131600 1.39 530.81 1261.2 1792 102.48 BJ10_06 195620 1.3 800.46 1731.52 2531.99 154.54 BJ10_07 161200 1.45 629.72 1462.42 2092.15 121.58 BJ10_08 160400 1.48 646.39 1598.48 2244.87 124.8 BJ10_09 174300 1.29 709.63 1687.92 2397.55 137.01 BJ10_10 196900 1.32 794.67 1724.37 2519.03 153.42  BJ20_01 206800 1.74 846.78 2871 3717.78 163.49 BJ20_02 329150 1.82 1327.82 3416.9 4744.72 256.36 BJ20_03 215720 1.81 879.27 2961.26 3840.53 169.76 BJ20_04 256490 1.99 1018.96 2744.67 3763.63 196.73 BJ20_05 280140 1.85 1134.25 3368.94 4503.19 218.99 BJ20_06 292080 2.1 1158.64 3154.69 4313.33 223.7 BJ20_07 303580 1.7 1259.44 3658.02 4917.46 243.16 BJ20_08 272670 1.78 1123.32 2997.37 4120.69 216.88 BJ20_09 310710 1.89 1254.84 3026.47 4281.31 242.27 BJ20_10 271600 2.18 1076.31 2936.7 4013.01 207.8  BJ30_01 381430 2.35 1589.86 4482.93 6072.79 306.95 BJ30_02 420450 2.47 1689.85 4524.59 6214.44 326.26 BJ30_03 427000 2.15 1773.68 4940.07 6713.75 342.44 BJ30_04 422740 2.35 1748.59 4702.47 6451.05 337.6 BJ30_05 352590 2.57 1423.67 4643.47 6067.14 274.87 BJ30_06 458020 2.17 1904.47 4765.45 6669.91 367.69 BJ30_07 459540 2.33 1897.68 4820.74 6718.42 366.38 BJ30_08 430970 2.21 1784.59 4656.09 6440.68 344.55 BJ30_09 445190 2.18 1864.22 4760.49 6624.71 359.92 BJ30_10 282940 2.44 1146.82 4012.06 5158.88 221.42Table 7
Cost components with different objectives.
Instances Objective TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) 10-node Min FEC 167265 1.41 670.44 1569.67 2240.11 129.44 Min DC 166822 1.37 673.33 1567.83 2241.15 130 Min TC 166950 1.37 671.63 1568.36 2239.98 129.67  20-node Min FEC 273538 2 1101.45 3112.12 4213.57 212.66 Min DC 273894 1.89 1107.96 3113.6 4221.57 213.91 Min TC 272988 1.93 1101.8 3109.83 4211.64 212.72  30-node Min FEC 407064 2.45 1670.68 4626.58 6297.27 322.56 Min DC 408087 2.32 1682.34 4630.84 6313.18 324.81 Min TC 406680 2.49 1671.44 4624.98 6296.43 322.7On average of 10-node class, the fuel emissions cost represents about 30% of the total cost. For 20- and 30-node classes, the fuel emissions cost accounts for approximately 26% of the total cost. The carbon dioxide emissions increase with the number of customers. Only considering the driver cost in the objective leads to the most carbon dioxide emissions and the poorest total cost performance. Only considering the fuel emissions gets solutions with the lowest carbon dioxide emissions, but a higher total cost. Min TC as an objective yields the lowest total cost and the shortest total distance.


## 4.2. Effect of Open Routes

In this subsection, we compared the total cost of open routes with that of closed routes. Experiments were also conducted on smaller instance classes by using light-duty vehicles. The mean results of closed routes collected over ten runs are listed in Table8. The average results of each class are reported in Table 9 to illustrate the effect of open routes. As shown in Table 9, open routes reduce the total cost by 18.5% with the fuel emissions cost down by nearly 29.1% and the diver cost down by 13.8% over all the instances.Table 8
Cost components with closed routes.
Instances TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) BJ10_01 243300 1.35 973.42 1773.67 2747.08 187.94 BJ10_02 287900 1.23 1143.69 1971.25 3114.95 220.81 BJ10_03 233000 1.28 929.49 1868.6 2798.09 179.46 BJ10_04 193600 1.33 774.88 1886.42 2661.31 149.61 BJ10_05 190300 1.33 752.29 1505.32 2257.61 145.24 BJ10_06 306900 1.26 1216.62 2194.33 3410.94 234.89 BJ10_07 225500 1.19 914.3 1729.84 2644.14 176.52 BJ10_08 222400 1.33 883.91 1856.33 2740.24 170.65 BJ10_09 250200 1.29 1001.88 2003.58 3005.46 193.43 BJ10_10 285200 1.3 1133.7 2091.6 3225.3 218.88  BJ20_01 296880 1.75 1191.94 3245.63 4437.57 230.13 BJ20_02 432490 1.74 1733.98 3846.68 5580.66 334.78 BJ20_03 302470 1.93 1227.85 3322.04 4549.9 237.06 BJ20_04 350360 1.8 1408.36 3135.07 4543.43 271.91 BJ20_05 397350 1.75 1601.07 3856.4 5457.48 309.12 BJ20_06 404900 1.76 1627.02 3623.9 5250.92 314.13 BJ20_07 453910 1.79 1833.88 4283.23 6117.1 354.06 BJ20_08 377970 1.71 1526.82 3435.3 4962.12 294.78 BJ20_09 458430 1.79 1842.5 3640.83 5483.32 355.73 BJ20_10 380810 1.75 1533.55 3390.9 4924.45 296.08  BJ30_01 544130 2.53 2213.58 5159.58 7373.16 427.37 BJ30_02 602750 2.32 2434.58 5282.76 7717.34 470.04 BJ30_03 603420 2.25 2446.55 5673.79 8120.33 472.35 BJ30_04 574210 2.51 2328.31 5332.41 7660.72 449.52 BJ30_05 495510 2.46 2006.16 5237.86 7244.02 387.33 BJ30_06 636960 2.23 2584.8 5509.64 8094.44 499.04 BJ30_07 666890 2.43 2711.67 5683.09 8394.76 523.54 BJ30_08 588990 2.25 2385.82 5313.28 7699.1 460.63 BJ30_09 640480 2.22 2600.55 5572.68 8173.23 502.08 BJ30_10 394830 2.35 1599.07 4477.4 6076.47 308.73Table 9
Cost components of different types of routes.
Instances Type of routes TD (m) ET (s) FEC (RMB) DC (RMB) TC (RMB) CE (kg) 10-node Open 166950 1.37 671.63 1568.36 2239.98 129.67 Closed 243830 1.29 972.42 1888.09 2860.51 187.74  20-node Open 272988 1.93 1101.8 3109.83 4211.64 212.72 Closed 385557 1.78 1552.7 3578 5130.7 299.78  30-node Open 406680 2.49 1671.44 4624.98 6296.43 322.7 Closed 574817 2.36 2331.11 5324.25 7655.36 450.06


## 4.3. Results for Larger Scale Instances

Experiments were also conducted on the four largest sets with the objective Min TC. The results collected over ten runs are reported in Table10 by using light-duty vehicles. Notations BS, MS, WS, SD, and ET in columns represent the best solution, mean solution, the worst solution, standard deviation, and execution time, respectively. As shown in Table 10, the total cost increases with the number of customers.Table 10
Computational results on larger scale instances.
Instance BS (RMB) MS (RMB) WS (RMB) SD ET (s) BJ60_01 11061.79 11254.42 11417.58 92.8 5.37 BJ60_02 10309.83 10393.21 10492.87 62.43 4.88 BJ60_03 11574.38 11790.03 11933.82 94.03 5.06 BJ60_04 12094.39 12212.64 12462.25 95.54 5.14 BJ60_05 11236.35 11320.09 11431.91 52.74 5.44 BJ60_06 11883.87 12040.48 12249.58 94.39 4.89 BJ60_07 12600.43 12745.03 12867.3 92.99 4.74 BJ60_08 11939.78 12060.86 12173.83 59.37 4.73 BJ60_09 11583.85 11727.88 11922.82 95.35 4.7 BJ60_10 12938.11 13121.2 13364.03 114.64 4.74  BJ80_01 14787.03 15036.55 15227.3 127.09 7.56 BJ80_02 14018.34 14220.78 14411.5 115.1 7.18 BJ80_03 14714.36 14964.93 15139.74 125.11 7.72 BJ80_04 13872.84 14065.74 14550.33 199.54 7.6 BJ80_05 14613.9 14788.56 15078.73 148.41 7.52 BJ80_06 16857.87 17148.49 17572.08 217.41 6.83 BJ80_07 15371.73 15632.16 15925.82 170.46 7.1 BJ80_08 14273.97 14484.07 14815.66 183.64 7.39 BJ80_09 14526.1 14743.32 14969.09 122.54 7.19 BJ80_10 14736.48 14942.92 15284.86 137.4 7.09  BJ100_01 19330.25 19617.94 20069.92 203.78 10.22 BJ100_02 20194.9 20701.34 21013.24 215.65 10.33 BJ100_03 20081.75 20286.97 20556.28 138.13 10.38 BJ100_04 18483.02 18689.28 18893.14 114.28 9.87 BJ100_05 18776.99 18983.5 19256.85 165.22 10.01 BJ100_06 17478.28 17764.38 18119.14 187.27 10.5 BJ100_07 18451.61 18775.37 18938.18 167.43 10.49 BJ100_08 18527.85 18762.86 18941.62 142.11 10.52 BJ100_09 17458.07 18048.33 18385.66 259.49 10.92 BJ100_10 20847 21099.27 21541.13 201.04 10  BJ120_01 21699.63 21954.27 22209.26 135.47 15.38 BJ120_02 22803.9 23135.32 23736.67 273.1 16.09 BJ120_03 22074.76 22569.41 22921.39 270.03 17.46 BJ120_04 22380.9 22560.26 22764.57 138.1 16.91 BJ120_05 22602.33 23308.71 23666.93 289.5 14.39 BJ120_06 22656.5 22975.25 23166.4 145.56 14.44 BJ120_07 21156.14 21711.99 22170.6 301.69 14.37 BJ120_08 20837.63 21069.17 21418.09 211.61 15.66 BJ120_09 21865.67 22195.93 22498.88 170.26 14.43 BJ120_10 22705.98 23054.33 23556.8 217.54 14.4


## 4.4. Results with Different Vehicle Types

Experiments were conducted on the 60- and 120-node instances by using different types of vehicles. In this subsection, the analysis focuses on which type of vehicle is the most suitable to minimize the total cost. The specific vehicle parameters are listed in Table2. Results with different vehicle types are listed in Tables 11 and 12. Over all the instances in the two classes, the mean total cost by using the light-duty vehicles is the lowest. For 120-node instances, the mean total cost by using medium-duty vehicles increases by 4.8% and the result by using heavy-duty vehicles rises 23.6%. For 60-node instances, the mean total cost by using medium-duty vehicles increases by 7.7% and the value by using heavy-duty vehicles rises 28%.Table 11
Computational results on the 60-node instances by using different vehicles.
Type of vehicles Instance BS (RMB) MS (RMB) WS (RMB) SD ET (s) Only light duty BJ60_01 11061.79 11254.42 11417.58 92.8 5.37 BJ60_02 10309.83 10393.21 10492.87 62.43 4.88 BJ60_03 11574.38 11790.03 11933.82 94.03 5.06 BJ60_04 12094.39 12212.64 12462.25 95.54 5.14 BJ60_05 11236.35 11320.09 11431.91 52.74 5.44 BJ60_06 11883.87 12040.48 12249.58 94.39 4.89 BJ60_07 12600.43 12745.03 12867.3 92.99 4.74 BJ60_08 11939.78 12060.86 12173.83 59.37 4.73 BJ60_09 11583.85 11727.88 11922.82 95.35 4.7 BJ60_10 12938.11 13121.2 13364.03 114.64 4.74  Only medium duty BJ60_01 12449.13 12616.53 12823.93 109.15 4.51 BJ60_02 11328.74 11557.08 11780.96 125.14 4.19 BJ60_03 12959.56 13222.5 13390.12 121.83 4.42 BJ60_04 13411.61 13630.23 13870.71 147.61 4.4 BJ60_05 12515.46 12678.95 12843.89 87.75 4.63 BJ60_06 13037.75 13302.09 13413.95 100.83 4.29 BJ60_07 12360.13 12425.3 12579.82 63.71 4.22 BJ60_08 12942.29 13064.34 13360.38 121.13 4.49 BJ60_09 12112.23 12348.68 12563.22 122.72 4.43 BJ60_10 12832.96 12974.52 13105.98 88.75 4.03  Only heavy duty BJ60_01 14787.24 14995.59 15334.52 176.58 9.38 BJ60_02 13418.08 13700.42 13911.3 143.14 7.91 BJ60_03 15469.9 15746.78 16052.25 183.26 7.54 BJ60_04 16164.2 16411.77 16729.41 172.11 7.78 BJ60_05 14772.72 14937.7 15269.37 154.91 7.98 BJ60_06 15893.22 16093.82 16272.75 133.43 7.41 BJ60_07 14441.09 14606.23 14757.43 103.53 7.46 BJ60_08 15088.73 15473.2 15638.19 152.24 7.61 BJ60_09 14521.68 14811.72 14972.54 119.53 7.22 BJ60_10 14961.08 15164.55 15321.96 109.22 6.88Table 12
Computational results on the 120-node instances by using different vehicles.
Type of vehicles Instance BS (RMB) MS (RMB) WS (RMB) SD ET (s) Only light duty BJ120_01 21699.63 21954.27 22209.26 135.47 15.38 BJ120_02 22803.9 23135.32 23736.67 273.1 16.09 BJ120_03 22074.76 22569.41 22921.39 270.03 17.46 BJ120_04 22380.9 22560.26 22764.57 138.1 16.91 BJ120_05 22602.33 23308.71 23666.93 289.5 14.39 BJ120_06 22656.5 22975.25 23166.4 145.56 14.44 BJ120_07 21156.14 21711.99 22170.6 301.69 14.37 BJ120_08 20837.63 21069.17 21418.09 211.61 15.66 BJ120_09 21865.67 22195.93 22498.88 170.26 14.43 BJ120_10 22705.98 23054.33 23556.8 217.54 14.4  Only medium duty BJ120_01 23290.23 23541.68 23691.38 124.27 12.99 BJ120_02 23133.82 23473.76 23710.98 178.16 12.55 BJ120_03 23320.12 23573.14 23908.95 186.7 12.9 BJ120_04 23117.27 23545.71 23757.64 194.07 13.01 BJ120_05 23687.6 24099.96 24385.48 207.61 13.08 BJ120_06 23273.19 23621.69 23870.13 162.68 12.49 BJ120_07 23136.08 23257.6 23424.7 91.21 13.13 BJ120_08 22752.22 23085.88 23320.75 200.2 13.35 BJ120_09 23171.61 23279.47 23450.24 85.55 12.65 BJ120_10 23476.59 23845.67 24258.76 222.02 12.58  Only heavy duty BJ120_01 27565.54 27974.16 28341.07 204.51 20.49 BJ120_02 27337.33 27628.98 28138.69 243.32 18.79 BJ120_03 26855.88 27379.48 27991.72 327.29 20.89 BJ120_04 27580.86 27834.25 28040.53 168.47 21.69 BJ120_05 28189.69 28500.43 28755.03 186.67 18.96 BJ120_06 27679.42 27933.79 28172.32 143.93 19.15 BJ120_07 26969.4 27668.76 28014.39 286.72 21.03 BJ120_08 26617.8 27268.75 27742.87 315.44 22.64 BJ120_09 27000.07 27382.75 27631.08 187.61 20.21 BJ120_10 27663.24 27887.53 28107.04 126.69 20.54


## 5. Conclusions

In this study, the GOVRP was introduced as a formulation considering the impact of fuel emissions for the third-party logistics. The problem was to construct open routes for vehicles to visit all customers with the vehicle capacity constraints. The objective was to minimize the total cost composing of the fuel emissions cost and the driver cost.A hybrid tabu search algorithm was designed to deal with the GOVRP instances. Experiments were conducted on 60 instances derived from real geographical data of customers in Beijing. We analyzed the cost components with different objectives and compared open routes with closed routes in respects of reducing the total cost. A homogenous fleet was considered in this paper. Computational results showed that vehicle type influenced the total cost and it should be changed according to the instance’s size. In the future, a heterogeneous fleet of vehicles can be used to minimize the total cost. Other types of the OVRP, such as OVRPTW and MDOVRP, can be solved by our algorithm with some changes.Nowadays, several novel computing techniques are used to deal with complex problems. Some of them are bioinspired models, such as membrane-inspired evolutionary algorithms [24–26] and probe machine [27]. Their nondeterministic distributed parallel frameworks have been proved to improve the performance of optimization algorithms [28]. Most of them can be used to solve real-life problems [29]. We hope that more competitive results for our GOVRP instances can be obtained by using those algorithms in the future.



---

*Source: 5754908-2018-02-28.xml*