A Simulated Annealing Algorithm Based Solution Method for a Green Vehicle Routing Problem with Fuel Consumption

Abstract

This chapter presents a new G-VRP model that aims to reduce the fuel consumption of the vehicle’s gas tank. The fuel consumption of a vehicle is related to total vehicle weight through route and thus, this changes the CO₂ levels as a result of the changes of total weight and distance for any arc {i, j} in the route. To minimize CO₂ levels, a simulated annealing-based algorithm is proposed. About the experiments, firstly, we applied small-VRP problem set for defining the proposed algorithm and then, the Christofides et al. (Combinatorial optimization. Wiley, 1979) small/medium scale C1–C14 datasets are used with proposed G-VRP model and a convex composition solution with two objective functions. The proposed methods are compared with statistical analysis techniques to explain the statistical significance of solutions. The procedures are also tested using additional examples previously analyzed in the literature. The result has shown good solutions for minimizing the emitted CO₂ levels.

1 Introduction

Logistics is a term describing essential components of a production process such as transportation, storage, and handling of products from raw material to the final consumption points (McKinnon 2010). Among these components, transport activity is the most important. It is related to the movement and coordination of goods. During the transport of goods, different vehicles can be used depending on the type and specification of the product, the underlying technology, the relevant infrastructure and the nature of the respective operations (Bektas 2017). Transportation allows the carriage of loads from door-to-door, that is, between the starting and arriving points, which is a significant effect as a complementary element in other modes of transport.

Environmental pollution, which is widely spreading on a large area all over the world, is one of the most critical threats to the survival of living beings. Because of the processes such as electric power generation, industrial processes, heating, and transportation, millions of kilograms of carbon dioxide (CO₂) are spreading to the atmosphere everyday. Electricity and industrial production areas are suitable for filtration systems due to high CO₂ emission values. Numerous small energy consumption points and vehicles used in transportation define other sectors that are not currently available for filtration. In the coming years, the technological changes in production technologies and the characteristics of transportation fuels may enable the reduction of carbon dioxide emissions. Green logistics practices are also eco-friendly business processes. Environmental management of the supply chain and logistics activities (green logistics) is now becoming increasingly popular as an enterprise practice.

The Vehicle Routing Problem (VRP) is a favorite and NP-Hard class combinatorial optimization problem. Depending on a set of constraints, it is a generalized version of the Travelling Salesman Problem and defined as the problem of determining the lowest-cost routes for deliveries to geographically separate customers from a warehouse. VRP is the primary element of many operational research problems and has many variations. The exact solution methods and many common heuristics have been proposed to solve VRPs.

In recent years, significant emphasis has been placed on sustainable logistics practices in order to overcome environmental concerns. The version that focuses on sustainable business practices is called Green Vehicle Routing Problem (G-VRP) in general. Due to the fact that it is an important area within the logistics activities, studies related to G-VRP has shown a significant increase in recent years. In this type of VRP, unlike the original VRP, the effect of the routing on the environment is being tried to be minimized. It is known that there is a direct effect of energy (fuel) consumption on the CO₂ emissions depending on the movement and the load of vehicles.

Most of the vehicles in road transport work with diesel or gasoline fuel in Turkey. Today, although vehicles that use alternative energy sources (LPG, electricity, biodiesel etc.) have been developed, gasoline and diesel vehicles continue to be used predominantly in this sector. Emissions from freight transport largely depend on the type of fuel used (Piecyk 2010). Higher use of roads in freight and passenger transport has led to increased traffic intensity and air pollution as well as transportation costs (Aydemir and Cubuk 2016). According to the statistics of the Turkish Statistical Institute (TSI) in 2014, total Green House Gas (GHG) emissions as CO₂ equivalent increased by 125% in 2014 compared to the emissions in 1990 and the share of the transportation sector in total greenhouse gas emission values is about 19%. Figure 1 shows the change in emission values between 1990 and 2014. Despite declining in some years, there is a tendency to increase in greenhouse gas emissions per capita in general. The CO₂ equivalent emission per capita was 6.08 tonnes in 2014, while it was 3.77 tonnes for the year 1990 (TSI 2014).

Fig. 1

GHG emissions per capita in Turkey, 1990–2014 (TSI 2014)

Investments and promotions that aim to direct drivers to public transport and freight transport from road to rail have been the result of efforts to reduce the use of fossil fuels. Although the effort being undertaken in this direction is obviously beneficial, achieving the significant decline will only be possible with a multi-perspective approach (Erdoğan and Miller-Hooks 2012). Governments should continue to increase their promotional and financial support for the use of greener energy resources. On the other hand, both public institutions and private sector companies should prefer eco-friendly energy sources in vehicles they use for transportation.

Along with the increased emphasis on supply chain management in the environmental sense, the need to develop models to reduce environmental pollution has emerged. At this point, sustainable transport, which aims to efficiently transfer goods, services and sustainable transport and delivery systems, has become an important issue for companies. The development of theoretical models is the first step in these studies. Factors such as travel distance, vehicle weight and vehicle speed which affect the emission value produced by the vehicle should be controlled. Another critical factor that determines the emission value is the total vehicle weight, which is the sum of the cargo and the vehicle’s empty weight (Ayadi et al. 2014). Improvements to the above factors will help to achieve sustainable transport goals.

In this section, three analytical models were used to identify the G-VRP. A Simulated Annealing-based solution algorithm is preferred for the solution of large-scale test instances. The results obtained from this solution algorithm are compared with the results of the classical G-VRP model. Although there are many studies in the literature for G-VRP, the current contribution of the study is to propose new mathematical models alongside the classical models used for G-VRP and solve them quickly and efficiently with the Simulated Annealing method.

2 Background

Vehicle Routing Problem (VRP), first described by Dantzig and Ramser (1959), is a generalized version of the Travelling Salesman Problem and defined as the problem of determining the lowest-cost routes for deliveries to geographically separated customers from geographical locations, depending on a number of factors (Cetin and Gencer 2010). The main components of VRP are the road network, warehouses, and vehicles. VRP is generally describes by vehicle capacity or route distance constraints. If only capacity-related constraints are identified, the problem is named as Capacitated Vehicle Routing Problem (CVRP).

CVRP has been a problem that has attracted many researchers since its first definition. Many exact solution methods have been developed taking into account the capacity constraints. Some of them are applied with the necessary modifications to distance limited problems. However, the heuristics methods that are developed often add accountability to both constraints (Barhant and Laporte 2006). One of the first methods proposed for this problem is Clarke and Wright (1964) (C–W) Savings Algorithm. They introduced the savings concept which is based on the computation of savings for combining two customers into the same route (Pichpibul and Kawtummachai 2013). Since then, many different types have been introduced by adding new constraints to VRP, and many models and algorithms have been developed for these types of problems. In order to obtain different types of VRP, each component may be supplemented with different constraints and states, or each can achieve specific goals.

The literature on VRP is extensive and to date, many different VRP variations have been developed. The main types of VRP are Capacitated VRP (e.g., Bräysy and Gendreau 2005), VRP with Time Windows (e.g., Alvarenga et al., 2007), VRP with Backhauls (e.g., Gribkovskaia et al. 2008), VRP with Pick-up and Delivery (e.g., Ganesh and Narendran 2007), VRP with Heterogeneous Vehicle Fleet (e.g., Salhi et al. 2014), Open VRP (e.g., Özyurt et al. 2006), Periodic VRP (e.g., Cacchiani et al. 2014) and Stochastic VRP (e.g., Yan et al. 2006). The version that focuses on sustainable business practices is named as Green Vehicle Routing in general. Research on VRP, in which environmental issues such as fuel consumption and greenhouse gases (GHG) were assessed, has begun quite recently. Since this study is related to G-VRP, the following section only refers to the literature related to this type of problems.

In the above-mentioned types of vehicle routing problems, variations of the G-VRP arise when the objective function is formed by considering the fuel consumption or emission values. During the last ten years period, a series of literature reviews have been conducted on the G-VRP. Lin et al. (2014) presented an extensive literature review of G-VRP. They provide a classification of G-VRP that categorizes G-VRP into Green-VRP as Pollution-Routing Problem, VRP in Reverse Logistics, and suggested research gaps between its state and more luxurious models describing the complexity in real-world cases. Eglese and Bektaş (2014), described the current fuel consumption and emission models in the literature and the ways in which these models can be integrated into existing formulations or approaches for VRP. As an extension of the classical VRP, the Pollution-Routing Problem (PRP) accounts the amount of greenhouse emissions, fuel, travel times and costs (Bektaş and Laporte 2011; Koç et al. 2014; Kramer et al. 2015). Demir et al. (2014) provide a review of recent research on green road freight transportation. In this research, they focus on the scientific literature related to fuel reduction in road freight transportation by means of operations research techniques. Park and Chae (2014) focus on solution approaches for papers related to G-VRP which were published after 2000. Zhang et al. (2014) reviewed 115 studies published over the last 2 decades and observed the practice of Swarm Intelligence (SI) in Green Logistics (GL). The integration of GL and SI has been systematically classified into GL and SI categories by analyzing the context of the problem and the methodology used. Toro et al. (2016) conducted a literature survey including variations, solution models and methodologies of the VRP, in which the G-VRP is included. Recent studies related to G-VRP are summarised in the following sections.

2.1 Exact Solution Methods for G-VRP

It is possible to obtain an optimal solution in small-scale problems with exact solution methods. However, it is difficult and time-consuming to find optimal solutions in large-scale problems as the energy consumption or emission values assigning a specific customer to a tour depend on the other customers that are assigned to the tour. Studies using exact solution methods such as branch and bound dynamic programming for solving the problem are included in the literature. Kara et al. (2007) proposed a new cost function based on distance and load of the vehicle for the Energy Minimizing Vehicle Routing Problem (EMVRP). They developed an Integer Programming (IP) formulation with O(n²) binary variables and O(n²) constraints. Bektaş and Laporte (2011) offered a new integer programming formulation for the Pollution-Routing Problem which minimizes a total cost function composed of labor, fuel and emission costs expressed as a function of load, speed, and other parameters. The proposed model is solved by the branch-cut method, which is an advantageous method for integer programming problems. Huang et al. (2012) studied a G-VRP with simultaneous pickup and delivery problem (G-VRPSPD). They suggested a linear integer programming model including CO₂ emission and fuel consumption costs for G-VRPSPD, modified from the commodity flow based VRPSPD formulation.

Treitl et al. (2014) proposed an integer programming model for Inventory Routing Problem to minimize total transport costs as well as costs for CO₂ emissions from transport activities and warehousing activities over the planning horizon. Ramos et al. (2012) developed a modular and innovative solution approach for the multi-depot VRP and applied to a real case-study in order to restructure the current operation and achieve a more environmental-friendly solution. The primary goal of the research is to define service areas and vehicle routes that minimize the CO₂ emissions of a logistics system with multiple products and depots. They solved the decomposition solution method using the branch-and-bound algorithm.

Pan et al. (2013) adopted the emissions functions in a Mixed Integer Linear Programming (MILP) to minimize the CO₂ emissions related to freight transport in two extensive supply chains. Franceschetti et al. (2013) described an integer linear programming formulation of The Time-Dependent Pollution-Routing Problem (TDPRP) consists of routing a fleet of vehicles in order to serve a set of customers and determining the speeds on each leg of the routes. Taha et al. (2014) presented an integer programming based exact solution model for the small size G-VRP. Alkawaleet et al. (2014) investigated the effect of CO₂ emissions on the inventory and routing decisions determined over a given time horizon. They formulate a mixed integer programming for the inventory routing problem of a product distributed to a number of customers from a single distribution center. Andelmin and Bartolini (2017) developed an exact algorithm for the G-VRP based on a set partitioning formulation using a multigraph. They weakened their formulations by adding weak subset sequence inequalities, subset sequence inequalities, and k-path cuts.

2.2 Heuristic and Meta-Heuristic Algorithms for G-VRP

Real-life optimization problems are very complex and require analysis of large data sets. Although an exact solution model has been developed for G-VRP, it is impossible to obtain a solution in an acceptable time. It is often enough to find an approximate solution to real-life problems. Therefore, there are many heuristic and meta-heuristic methods developed for G-VRP solutions. When the literature is examined, it is seen that the proposed heuristic methods are based on the route construction and neighborhood search. The Clark and Wright’s Saving Algorithm (Clark and Wright 1964) is the most commonly used method to construct routes in G-VRP. Faulin et al. (2011) and Ubeda et al. (2011) constructed some algorithms with environmental criteria based on the Saving Algorithm to address the need for solutions to real problems in delivery companies or logistic carriers. Aranda et al. (2012) also developed an environmental performance method based on Life Cycle Assessment (LCA) and complemented with the Saving Algorithm to qualify the environmental performance of the end of life tyres (ELTs) management system, in terms of CO₂ emissions. Peiying et al. (2013) suggested a heuristic method called Bi-directional Optimization Heuristic Algorithm (BOHA) to reduce the most cost based on low carbon emissions. Zhou and Lee (2017) proposed a nonlinear mixed integer programming model with vehicle speeds, vehicle weights, road grades, and vehicle routes as decision variables. They used sweep algorithm for the initial solution and 2-opt local search algorithm for the improvements to find vehicle routes of G-VRP.

In recent years, many meta-heuristic methods are used to solve the G-VRP. The most preferred methods in the G-VRP solution are Genetic Algorithms (GA), Tabu Search (TS) and Simulated Annealing (SA). In addition to these methods, Scatter Search (SS), Near-Exact (NEA), Local Search (LS), Iterative Route Construction and Improvement (IRCI), Artificial Bee Colony (ABC) algorithms are also used in the literature. Maden et al. (2010) described a TS based heuristic algorithm for vehicle routing and scheduling problems to minimize the total travel time, where the time required for a vehicle to travel along any road in the network varies according to the time of travel. Kuo and Lin (2010) proposed a model to calculate the total fuel consumption when given a routing plan. They consider three factors that affect fuel consumption and used a simple Tabu Search to optimize the routing plan. Jabali et al. (2012) presented a model that considers travel time, fuel consumption, and CO₂ emissions costs accounting for time-dependent travel times between customers. They solved the model using a tabu search procedure. Li (2012) presented a mathematical model for the VRP with time windows (VRPTW) with a new objective function of minimizing the total fuel consumption and solved the problem using a novel TS algorithm with a random variable neighborhood descent procedure (RVND). This algorithm uses an adaptive parallel route construction heuristic, introduces six neighborhood search methods and employs a random neighborhood ordering and shaking mechanisms. Kwon et al. (2013) adopted a mixed integer-programming model for the objective of minimizing the sum of variable operation costs, including a cost-benefit assessment of acquiring carbon rights under a cap-and-trade regime. They deployed TS algorithms were deployed together with three neighborhood generation methods. Úbeda et al. (2014) proposed a TS algorithm based on Gendreau et al.’s (1994) approach to solving the green distance CVRP. They applied this approach on a set of instances obtained from the company Eroski producing the cleanest solutions in all cases. Ene et al. (2016) presented a SA and TS-based hybrid metaheuristic algorithm to analyze the effect of a heterogeneous fleet on reducing fuel consumption. They used a time-oriented nearest neighbour heuristic to generate the initial solution for the algorithm and preferred local search method to generate neighbours.

Kuo (2010) suggested a model for calculating total fuel consumption for the time-dependent vehicle routing problem (TDVRP). Then a SA algorithm is used to find the vehicle routing with the lowest total fuel consumption. Suzuki (2011) developed an approach to the time-constrained, multiple-stop, truck-routing problem that minimizes the fuel consumption and pollutants emission. They used the enumeration technique to find the optimal solutions for instances with n = 5 or n = 10 and the compressed annealing (Ohlmann and Thomas 2007) for experiments in which n = 15. Xiao et al. (2012) presented a mathematical model for Fuel Consumption Rate (FCR) considered CVRP (FCVRP) in which the fuel consumption rate is added to the CVRP. They developed SA algorithm for the proposed model. In this algorithm, Swap, Relocation, 2-opt, and Hybrid exchange rules are used. Yasin and Vincent (2013) adopted a model using the mathematical model of Erdoğan and Miller-Hooks (2012) and developed a SA based solution method for the G-VRP. Küçükoğlu and Öztürk (2015) formulated G-VRP with time windows (G-VRPTW) using a mixed integer linear programming model. They adopted a memory structure SA (MSA-SA) meta-heuristic algorithm due to the high complexity of the proposed problem. To calculate fuel consumption and CO₂ emissions, they integrated proposed an algorithm with a calculation procedure. Koç and Karaoglan (2016) proposed a SA heuristic based exact solution approach to solve the G-VRP by considering a limited driving range of vehicles in conjunction with limited refueling infrastructure. They used branch-and-cut algorithm based exact algorithm to improve lower bounds and a heuristic algorithm based on SA to obtain upper bounds. Vincent et al. (2017) generated a mathematical model to minimize the total cost of travel by driving Plug-in Hybrid Electric Vehicle (PHEV) for the hybrid vehicle routing problem (HVRP), which is an extension of the G-VRP.

Urquhart et al. (2010) used an Evolutionary Multi-Objective Algorithm to investigate the trade-off between CO₂ savings, distance and number of vehicles used in a typical vehicle routing problem with Time Windows (VRPTW). Omidvar and Tavakkoli-Moghaddam (2012) used SA and GA methods along with a partial heuristic method and an exact algorithm for solving small-scale problems. They aimed to minimize the total cost of vehicles, traveled distance, travel time and emissions solving time-dependent VRP. Jemai et al. (2012) implemented the NSGA-II evolutionary algorithm to the bi-objective G-VRP to minimize the total traveled distance and the total CO₂ emissions with respect to classical routing constraints. Ayadi et al. (2014) proposed a mathematical model for the G-VRP with multiple trips developed a solution method by combining a GA with a local search procedure to solve it. Oliveira et al. (2017) used GA that incorporates elements of local and population search to minimize CO₂ emission per route for G-VRP. Bouzekri et al. (2014) defined the bi-objective G-VRP (bi-GVRP) in the context of sustainable transportation and applied the genetic algorithm to solve bi-GVRP benchmarks. Hsueh (2016) proposed a mathematical model considering heterogeneous fleet which is affected several factors such as vehicle types and conditions, travel speeds, roadway gradients, and payloads. They developed a customized GA for solving the model. Cooray and Rupasinghe (2017) implemented a GA to solve the Energy-Minimizing VRP and used machine learning techniques to determine the parameters of the developed GA. Tunga et al. (2017) developed a mathematical model to minimize the total energy consumed and balancing the routes, and proposed GA for finding out a solution to the G-VRP with different constraints.

3 Mathematical Models

3.1 A Classical Green VRP Model

VRPs have many different forms; however, most of them minimize the distance cost while visiting each customer once and with respect to vehicles capacity constraints. Actually, the consumed fuel amount is more important than the traveled distance for fuel cost savings (Xiao et al. 2012). In G-VRP, a set of delivery routes are determined to satisfy the demand with a minimum distance costs and the minimum volume of emitted CO₂. The G-VRP is also an NP-hard problem due to the fact that it is an extension of the standard VRP considering with green supply chain preferences.

Consider a G-VRP defined over a directed graph G = (V, A ) where V = { 0,  1,  2, …, n} the node set where is V=0 is the depot and A = { (i, j ) : i, j ∈ V,  i ≠ j} is the set of arcs the components of which are given as:

d _ij :

Distance between nodes iand j

q _i :

Non-negative weight (demand and supply) of node i

c _ij :

Traveling cost between nodes i and j

Q :

Capacity of a vehicle (truck)

k :

Number of identical vehicles

K :

Number of vehicles

n :

Number of customers

An unlimited number of the homogeneous vehicle fleet is available at the depot to serve customers with fuel tank capacity Q (liters) and fuel consumption rate r (liters per km). The problem is to determine the corresponding vehicle routes so as to minimize the total cost subject to the following assumptions (Kara et al. 2007; Koç and Karaoglan 2016):

• Each vehicle is used for at most one route,

• Each route starts and ends at the depot,

• Each node is served exactly by one vehicle,

• Fuel level at the vehicle’s tank must be greater than or equal to the fuel consumption between any two nodes,

• The amount of fuel in a vehicle’s tank is sufficient to be able to visit any pair of nodes,

• The load of a vehicle does not exceed its capacity Q.

The decision variables are:

• q _ij: the amount filled to the vehicle k between nodes i and j

• ${x}_{ij}^k=\left\{\begin{array}{c}1\kern0.5em \\ {}0\ \end{array}\begin{array}{c}\mathrm{if}\ \mathrm{vehicle}\ k\ \mathrm{drives}\ \mathrm{from}\ \mathrm{customer}\ i\ \mathrm{to}\ \mathrm{customer}\ \mathrm{j}\\ {}\mathrm{otherwise}\end{array}\right.$

• ${y}_i^k=\left\{\begin{array}{c}1\kern0.5em \\ {}0\ \end{array}\begin{array}{c}\mathrm{if}\ \mathrm{vehicle}\ k\ \mathrm{visits}\ \mathrm{customer}\ i\\ {}\mathrm{otherwise}\end{array}\right.$

In the solution of a VRP, a matrix representation is used for distance, time and cost parameters between nodes i and j. In G-VRP, a matrix representation also requires showing CO₂ emissions based on the estimation of CO₂ emitted between nodes i and j (Palmer 2007). About the linear formulation of emission volume, considering the delivery with a distance for Heavy Duty Vehicle (HDV) which has the average speed 80 km/h and fully loaded 25 tons (Hassel and Samaras 1999) Eq. (1) is given as follows (Elbouzekri et al. 2013):

$$ {E}_{ij}\left(q,d\right)={d}_{ij}\times \left[\left(\frac{e_f-{e}_e}{Q}\right){q}_{ij}+{e}_e\right] $$

(1)

Where:

• E _ij(q, d): the CO₂ emissions from a vehicle in kg/km with the variable of load q in ton and d in km

• e _f: the CO₂ emissions of a fully loaded vehicle (1.096 kg/km for a HDV truck)

• e _e: the CO₂ emissions of an empty vehicle (0.772 kg/km for a HDV truck)

The objectives are to find a set of m vehicle routes of minimum total cost (distance) and minimum total emitted CO₂ emission level. The mathematical model is given as follows (modified from Xiao et al. 2012; Bouzekri and Alaoui 2014):

$$ \min TotalCost\ (f)=\sum_{i=0}^n\sum_{j=0}^n\sum_{k=1}^K{c}_{ij}.{x}_{ij}^k \vspace*{-3pt} $$

(2)

$$ \min {CO}_2 Emission\ (g)=\sum_{i=0}^n\sum_{j=0}^n\sum_{k=1}^K{d}_{ij}.\left[\left(\frac{e_{f-}{e}_e}{Q}\right).{q}_{ij}^k+{e}_{e1}.{x}_{ij}^k\right] \vspace*{-3pt}$$

(3)

Subject to:

$$ \sum_{i=0}^n{x}_{0i}^k\le 1\kern2.25em \forall k=1,\dots, K \vspace*{-3pt}$$

(4)

$$ \sum_{i=0}^n{x}_{i0}^k\le 1\kern2em \forall k=1,\dots, K \vspace*{-3pt} $$

(5)

$$ \sum_{i=1}^n{y}_i^k\le M.\sum_{j=1}^n{x}_{0j}^k\kern1.5em \forall k=1,\dots, K \vspace*{-3pt} $$

(6)

$$ \sum_{i=1}^n{y}_i^k\le M.\sum_{j=1}^n{x}_{j0}^k\kern1.5em \forall k=1,\dots, K \vspace*{-3pt} $$

(7)

$$ \sum_{k=1}^n{y}_i^k\le 1\kern1.75em \forall k=1,\dots, K \vspace*{-3pt} $$

(8)

$$ \sum \limits_{j=1}^n{x}_{ji}^k=\sum \limits_{j=1}^n{x}_{ij}^k\kern0.5em {\displaystyle \begin{array}{l}\forall k=1,\dots, K\\ {}\forall i=1,\dots, K\end{array}} \vspace*{-3pt} $$

(9)

$$ \sum_{i=0}^n\sum_{\begin{array}{c}j=1\\ {}i\ne j\end{array}}^n{q}_{ij}^k\le Q.{x}_{ij}^k\kern1.5em \forall k=1,\dots, K $$

(10)

$$ \sum_{\begin{array}{c}j=0\\ {}i\ne j\end{array}}^n{q}_{ij}^k-\sum_{\begin{array}{c}j=0\\ {}i\ne j\end{array}}^n{q}_{ji}^k={D}_i\kern1.5em \forall i=1,\dots, n $$

(11)

The f function is related to minimize total traveling cost from i and jcan be expressed as c _ij = c ₀ × d _ij, where c ₀ is the unit fuel cost from i to j. About the g function, it is to minimize the sum of the total vehicle emitted CO₂ emission level considering as a green VRP. The mathematical model has two types of constraint set which are routing and capacity. Constraints (4–9) are related to routing, Constraints (4–7) of them have ensured that each vehicle tour begins and ends at the depot. Constraint (8) also guarantees that each node (except the depot) is visited by a single vehicle and by Constraint (9) each node is linked only with a pair of nodes also except the depot which respects the Kirchhoff Law. Constraints (10 and 11) are the capacity constraints which ensure that no vehicle can be over-loaded and limits the maximal load when ${x}_{ij}^k=0$ respectively. As another feature of Constraint (11), it indicates the reduced cargo of the vehicle and also doesn’t permit any illegal sub-tours.

3.2 Proposed G-VRP Model

The proposed G-VRP model contains some differences compared to the classical model described earlier. First, a new emission calculation equation for the G function is proposed. Accordingly, the weight of the vehicle’s fuel deposit will decrease as the vehicle travels, thus changing the overall weight of the vehicle. As a result, it is predicted that the amount of emitted emissions will also vary. The new emission equation is called G and it is given Eq. (12). In Eq. (12), an assumption of fuel consumption for a truck per km is averagely obtained as 0.3 L from the actual manufacturer’s technical datasets. Generally, this situation is also an assumption of the mathematical models. However, using this approach can be founded in some studies with different ways (Xiao et al. 2012; Koç and Karaoglan 2016).

$$ \min {CO}_2 Emission(G)=\sum_{i=0}^n\sum_{j=0}^n\sum_{k=1}^K{d}_{ij}.\left[\left(\frac{e_{f-}{e}_e}{Q}\right).{q}_{ij}^k-0.3\left(\frac{e_{f-}{e}_e}{Q}\right)+{e}_e\right] $$

(12)

Then, the second important difference of the proposed models in terms of objective functions is the minimization the distance instead of a cost function which is formulated as:

$$ \min ObjFunc\ (F)=\sum_{i=0}^n\sum_{j=0}^n\sum_{k=1}^K{d}_{ij}^k \vspace*{-10pt} $$

(13)

3.3 Convex Composition Model

In fact, the proposed G-VRP mathematical model also has a bi-objective form. At this phase, a convex composition approach is applied in order to obtain an aggregation objective function as a single objective function that is given as follows:

$$ \min ObjFunc\ (H)=\frac{1}{3}F+\frac{2}{3}\ G \vspace*{-3pt} $$

(14)

According to H function, it composes with two objective functions that the extended objective function (G) of emitted CO₂ emission level affects twice as much than the extended objective function (F) of total distance cost.

4 Solution Algorithm: Simulated Annealing

The determination of the optimal solution for the VRP using analytical methods is a difficult task. Depending on this feature, metaheuristic methods are generally referred for solving these problems. The purpose of these methods is to investigate the solution space efficiently and to provide useful solutions close to the optimal solution expeditiously. One of the heuristic methods that can be used to solve vehicle routing problems is also SA, first applied with success on the Ising spin glass problem by Kirkpatrick et al. (1983). It is the algorithmic counterpart to this physical annealing process, using the well-known Metropolis algorithm as its inner loop (Johnson et al. 1989). This method has an extensive use in solving advanced optimization problems similar to other metaheuristic algorithms.

The basic of the algorithm is derived from the solid annealing principle. The first step of the method consists of “melting” the system at a high and efficient temperature. When it is heated, an internal particle of solid rise into disordered shape with the high temperature. At the second step, the temperature of the system is reduced until there is no change. At each temperature, particles reach an equilibrium state. At the last, the temperature reaches the ground state in the room and then internal energy is reduced to the minimum (Lin and Fei 2012). The method has four parameters: the initial temperature, the number of solutions to be produced at each temperature, the temperature reduction function, and the stop criterion. The SA based solution algorithm is given as follows in Table 1 which includes Pseudo-Code and the values of the run parameters in detail.

Table 1 The SA based solution algorithm with proposed CO₂ emission model

5 Experimental Study

This section describes computational experiments obtained to investigate the performance of the proposed model by using SA algorithm. The algorithm was coded in MATLAB^® and run on a computer with i7 2.9 GHz CPU and 8 GB RAM. In this study, three models are used for the instances which are C1–C14 from Christofides et al. (1979) and Set A–B–P from Augerat (1995) as CVRPs.

The investigated models are:

• Model 1: GVRP Model (Xiao et al. 2012; Bouzekri and Alaoui 2014)

• Model 2: Proposed GVRP Model

• Model 3: Convex Composition Model

First of all, in order to show the efficiency of the proposed G-VRP models, an illustrative small example is given in below by Jaramillo (2011). The small instance considers ten customers that will be served from a single depot and the usage of two vehicles, each with a capacity of 12 tons, and a curb weight of 8 tons. Table 2 includes depot and customer locations coordinates, customer demands in tons, and distances between locations in miles.

Table 2 Small VRP instance dataset (Jaramillo 2011)

The results obtained for the sample data set detailed above are summarized in Table 3. In addition, the graphics of solution performance and routes are combined as in Fig. 2 for visualizing the small G-VRP’s best solutions from Model 3 in Table 3.

Table 3 SA solution results for small G-VRP

Fig. 2

The best solution for small G-VRP instance

According to results presented in Table 3, two CO₂ emission calculation methods are used for the comparison of the Models 1–3. One of them is developed by Bouzekri and Alaoui (2014) and the other one is proposed by this study in Eq. (12). In fact, Eq. (12) is also used as an objective function for the Model 2 and 3. However, it is to be an emission calculation method that is used in Bouzekri and Alaoui (2014) model (Model 1) within SA algorithm.

Computational results of the problems were compared using One-way ANOVA and Tukey tests. The averages of the statistically significant results were tested with the Tukey Test and the differences between the different models were investigated. At first, the box-plot graphic is given for the small G-VRP example in Fig. 3 and Differences between models were tested by one-way ANOVA that is given in Table 4. The hypotheses established for the analysis are presented below. H₀ hypothesis is that the averages of the models are equal to each other and, the H₁ hypothesis is that the averages of the models are not equal to each other and they are given Eqs. (14 and 15).

Fig. 3

Box-plot for the small G-VRP instance

Table 4 Results of one-way ANOVA

$$ {H}_0:{\mu}_1={\mu}_2={\mu}_3 \vspace*{-28pt} $$

(14)

$$ {H}_1:{\mu}_1\ne {\mu}_2\ne {\mu}_3 \vspace*{-10pt} $$

(15)

According to the Table 4, the difference between the models for all parameters is statistically significant for the small G-VRP problem. Before testing whether the difference between the models is statistically significant, the Bartlett test was used to test whether the variances of the models were homogeneous. The Bartlett’s test results for the Small G-VRP problem are given in Table 5 .

$$ {H}_0:{\sigma}_1={\sigma}_2={\sigma}_3 \vspace*{-15pt} $$

(16)

$$ {H}_1:{\sigma}_1\ne {\sigma}_2\ne {\sigma}_3 $$

(17)

Table 5 Variance homogeneity test results (Bartlett test)

As can be seen from Table 5, the hypothesis that the variances of the model for distance, CO₂_1, and CO₂_2 are homogeneous is rejected. The hypothesis that the variances are homogeneous for the solution time (Sol_Time) is accepted.

In this study, the parameters of the SA algorithm, max # of iteration 1200, max # of inner iteration 80, Initial temperature 100 and cooling ratio 0.99, are used on the proposed method and each test instance is run 10 times and summarized with the results of average values. About the test instances, Christofides et al. (1979) C1–C14 datasets and Augerat (1995) Set A1–A3, B1–B3 and P1–P3 are used from and their results are respectively given in Tables 6 and 7 which also show the emission savings (kg).

Table 6 Computational results for Christofides et al. (1979) C1–C14 instances

Table 7 Computational results for Augerat (1995) A1–A3, B1–B3 and P1–P3 instances

When the SA solutions given in Tables 6 and 7 which are examined, there is no difference between solution times in terms of absolute differences. However, when examined from the point of view of CO₂ emissions and distances, there is a difference between the absolute differences. In Table 6, 9 of the 14 problems with Model 3, 3 of them with Model 2 and 2 of them with Model 1 are superior to CO₂ emissions. Then, the following solutions are compared in terms of distances: ten of them with Model 3, three of them with Model 2 and one of them with Model 1 are better. Similarly, the absolute differences in terms of CO₂ emissions are shown in Table 7, where four of nine problems with Model 3, three of them with Model 2 and two of them with Model 1 were better solutions for nine problems in Augerat (1995) dataset. In the same way, when absolute differences are compared in terms of distances, it is seen that six of them with Model 3, two of them with Model 1 and one of them with Model 1 have better solutions, respectively.

The “t-test” is used to check whether the difference between the models’ averages is statistically significant. The hypothesizes are given below and the results presented in Table 8.

$$ {H}_0:{\mu}_1={\mu}_2 \vspace*{-12pt}$$

(18)

$$ {H}_1:{\mu}_1\ne {\mu}_2 $$

(19)

Table 8 t-Test results

According to the test results, the hypothesis that the mean values of objective functions are equal for distance, CO₂_1, CO₂_2 for Model 1 and Model 2, and Model 2 and Model 3 is accepted. On the other hand, the difference between Model 1 and Model 3 for these three objective functions was found to be statistically significant at the 5% significance level for the two-tailed test. The difference between Model 1and Model 3, and Model 2 and Model 3 for solution time is found to be statistically significant at the 5% significance level and two-tailed test. The H₀ hypothesis cannot be rejected for the difference between Model 1 and Model 2. Consequently, the proposed G-VRP model is statistically significant and has more efficient solutions. In addition, it can be predicted that it provides some opportunities for challenges on the green supply chain and encourages the researchers and industrial practitioners.

6 Conclusions and Further Research

The results of the research conducted were analyzed in terms of absolute differences and statistical analysis. Two alternative models are proposed in the literature. The Model 1 based on the literature is obtained by adding the effect of fuel consumption as an extension of Model 2 from the proposed models. The Model 3 is obtained by convex composition of two objective functions based on distance minimization with Model 2.

The C1–C14 instances from Christofides et al. (1979) and set A, B and P instances from Augerat (1995) were solved with SA algorithm. Each problem was run 10 times and the best, worst and average solutions were summarized. The results are compared with other solutions in the literature especially Bouzekri and Alaoui (2014) solutions.

The solutions of Model 1, Model 2 and Model 3 with SA were statistically analyzed in detail with absolute values. In absolute difference analysis, a total of 23 problems were compared with respect to CO₂ emissions. Thirteen of them with Model 3, 6 of them with Model 2 and 4 of them with Model 1 were better solutions. About the total distances, 16 of them with Model 3, 4 of them with Model 2 and 3 of them with Model 1 were the best solutions.

In this study, the analysis was made using theoretical VRP test problems. However, the proposed model for G-VRP is tried to be solved depending on vehicle load and total distance relation. It is our expectation that this objective function is considered to provide a more efficient CO₂ emission minimization on real industrial problems and the proposed models are suggested to address green thinking to the researchers. As a further research, the load effect of these models in real life problems, such as slope, altitude, load intensity, etc can be applied as different extensions of G-VRP.