1 Introduction

In recent years, global warming has been one of the most controversial issues in the world. Scientists believe that one of the main causes of global warming is the accumulation of greenhouse gases created by human activities [1]. Studies show that fuel consumption in the transportation sector has a large share in the spread of this pollution. Such that according to reports from the International Energy Agency (IEA), a large ratio of the produced greenhouse gases are related to the transportation sector (about 23%), where the share of greenhouse gases produced by the road sector is close to 75%. Therefore, there is an urgent need to reduce CO2 emissions produced by the road sector and the optimal use of vehicles will doubly important.

The classical routing problem is performed to route the vehicle fleet in a given network to service a set of customers under specified constraints of supply and demand. In the last two decades, the concept of the "green routing" problem has been grown rapidly. Kara et al. [2] have addressed this issue for the first time in the routing literature. They claimed that the "cost" depends not only on the distance traveled but also on the vehicle load. After that, Palmer [3] investigated the CO2 emissions effects on vehicle routing problems (VRP). Bektas and Laporte [4] present a Mathematical model for the Pollution-Routing Problem (PRP), as an extension of the classical routing problem to minimizing the travel distance, the amount of greenhouse emissions, fuel, travel times, and their costs. Different types of PRP have been introduced in the literature. For example Jabali et al. [5] and Franceschetti et al. [6] addressed time-dependent PRP, and Sameh and Bahadori [7] focused on the homogeneous fleet of vehicles, time windows PRP. Mirzapour and Rekik [8], integrated the concept of inventory with the PRP. Gajanand and Narendran [9] proposed a mathematical model for minimizing the fuel consumption in a multiple-routing problem by using alternative routes approach between nodes. The concept of the Green Open Location Routing Problem (GOLRP) is addressed by [10]. They proposed a bi-objective mathematical model to minimize both operational costs and the environmental effects.

The comprehensive reviews of PRP and its variants were done by [11, 12] and [13]. Recently Mara et al. [14] reviewed current works on location- routing problem (LRP) and its extensive versions. LRP is a more general form of vehicle routing problem in which location and vehicle routing decisions are made simultaneously. It should be noted that it has been proven that [15] independent decision-making for location and routing can lead to sub-optimal solutions. Govindan et al. [16] described a bi-objective two echelon time windows LRP. This problem is addressed the perishable food supply chain network including retailers, distribution centers and manufacturers. They also proposed a metaheuristics algorithm based on particle swarm optimization and multi-objective variable neighborhood search. A similar approach was proposed by Wang et.al [17]. They consider a two-echelon time window LRP including pickup and delivery services. The first echelon is related to the large eco-package transport, intending to minimize transport time. And the second echelon refers to small eco-package pickups and deliveries, which is trying to minimize the cost of location-routing transportation cost and the environmental effects. The effect of fleet composition, location and routing on greenhouse gas emissions for urban transportation in Green Location Routing Problem (GLRP) have been analyzed by Koc¸ et al. [18]. In their GLRP model, three areas with different speeds are considered for each city and the vehicle speed in each area is considered as a constant value. An adaptive large neighborhood search algorithm was applied to solve the proposed model.

A relatively new approach has been used by Toro et al. [19], to the calculation of greenhouse gas emissions in GLRP. They deliver a bi-objective model concerning minimizing operating costs and minimizing environmental impacts. Dukkanci et al. [20] present a mathematical formulating for time window GLRP. In this problem the facility location of depots is done on a subset of a discrete set of points and also routing the vehicles for servicing the customers from depots as well as setting the value of speed for all leg of the journey are performed as a main goals. The objective includes minimizing the fixed operating costs of location for depots and the costs of the fuel and CO2 emissions. In their proposed model, the authors used an emission formulation to computation the fuel consumption and emissions which is addressed by Scora and Barth [21], Barth et al. [22], Barth and Boriboonsomsin [23]. Dukkanci et al. [20] have considered main parameters including time window and variable speed in the GLRP simultaneously. We can also refer to some references which consider both issues for the green-routing problem (GRP). In [24] a multi-objective mathematical model was developed for soft time window GRP by considering time-varying vehicle speed during the planning period. Franceschetti et al. [6] proposed a time window PRP, intending to determine the speed on each route segment to minimize the cost of driver’s wage as well as environmental effects. In [25] the impact of Fuel-efficient behavior of GRP with variable speed on the route cost and fuel consumption was investigated Figliozzi [26] proposed a mathematical model for time windows GRP, in which minimizing the speed-dependent CO2 emission is a part of the objective function. In the model, the planning horizon time is divided into a set of time zone, and then a set of speeds have corresponded to each arc of the transport network.

In addition to the GRP features mentioned above, another important factor that should be considered is traffic congestion. Indeed, considering the traffic congestion, especially at the distribution of urban transportation, gives a realistic insight into GRPs.

Congestion in urban areas is a common phenomenon and usually, speeds are significantly reduced in the morning and evening. This means that in addition to the distance travelled the travel time between two points also depends on the speed of the vehicle as well as the time of the day. On the other hand, road congestion, in turn, leads to increased fuel consumption and CO2 emissions [23]. In short, congestion increases travel time, fuel consumption, and as a result more CO2 emissions. Figliozzi [27], analyzed different levels of congestion and time-definitive customer demands on CO2 emissions in an urban distribution network. Jabali et al. [5] have been used the ideas from [27] to time window VRP. In their model, the planning horizon is partitioned into two periods, i.e.; a free-flow speed and a peak period speed. The peak period includes the fixed travel speed and in a free-flow speed period, the model decides on its optimal speed value. Time-Dependent PRP (TDPRP) introduced by Franceschetti et al. [28]. One of the main approaches of TDPRP is to determine the speeds on each leg of the routes. In this respect, it is different from similar issues and is more practical. Inspired by Jabali et al. [5], Xiao and Konak [29] addressed the GRP model with a time window by considering time-varying traffic congestion. The impact of traffic congestion and vehicle loads on emissions has been verified in their work. A hybrid algorithm based on iterated neighborhood search was applied to solve the model. Hoshmand and Mirhassani [30], applied the same concepts to Time-Dependent GRP (TDGRP) model. The objective was to minimize the CO2 emissions, considering the presence of congestion. Due to congestion and instability of the vehicle speeds during the day, the planning horizon is divided into three time periods: morning peak, free-flow speed, and evening peak. Different speeds are associated with each period. After proposing MILP mathematical modeling, they applied a hybrid heuristic algorithm based on some decomposes technique and simulated annealing method. Raeesi and Zografos [31], developed TDGRP for urban freight distribution networks. They consider several factors affecting fuel consumption and emission includes, including load vehicle, fleet size and mix, departure times, and traffic-congested urban road. Liu et al. [32], proposed a mathematical model TDGRP with the hard time window, wherein some factors such as vehicle speeds, travel time, load vehicle, and service time that affecting fuel consumption and the resulting emission, were considered. The same model was developed by Zhang et al. [33]. To solve the model, a hyper-heuristic algorithm based on greedy search and tabu algorithms was applied.

Table 1 summarizes the findings of this study. Accordingly, it can be observed that there is no mathematical model for Time-dependent GLRP with a time window to consider the variable speed in a different time-dependent congested urban area. Typically, traffic congestion has an interval speed limits range, and due to time windows, the speed of a vehicle may not be the same, on two different routes with the same speed range. So, in this paper, an extension of the GLRP is addressed, in which time-dependent traffic-congested, soft and hard time window, and variable speed are considered simultaneously within a single optimization model. The main contributions are as follows.

  1. (1)

    The GLRP by considering, traffic time congestion, variable speed, soft and hard time window simultaneously is defined formally.

  2. (2)

    A new mixed integer nonlinear programming (MINLP) model for the addressed problem is developed in Sect. 2.

  3. (3)

    By using some linearization techniques, an equivalent mixed integer linear programming (MILP) model is delivered.

  4. (4)

    Then, a Quantum Binary PSO (QBPSO) algorithms is modified to solve the proposed model in Sect. 3; and in the end in Sect. 4.

  5. (5)

    Computational analyses on the model to evaluate the performance of the QBPSO method and some sensitive analysis to verify the effect of some factors of the model are conducted.

Table 1 Summary of works done on the “green location-routing and green location” problems
Full size table

2 Problem description and formulation

In the considered problem, there is the number of customers in definite locations with known demands that they are served by a set of vehicles. Customers’ demands can be met through several potential depots that the location of depots, as well as vehicle routing, are determined after solving the problem. The vehicle routing is accomplished according to traffic congestion, variable speed of vehicles, and time windows for serving customers. In addition, one of the main parts of the objective function is to reduce CO2 emissions from transportation and fuel consumption. In this section, firstly a mathematical formulation of the TDGLRP with variable speed will be addressed. And then, the calculation of fuel consumption and emissions for a considered network, which is also available in the literature, is briefly stated.

2.1 Problem description and formulation

The defined problem is considered on a complete directed graph \(G = (N,A)\). Let \(N = \left\{ {1,2,...,n} \right\}\) is the set of nodes for representing both the set of potential sites and customers. It is assumed that the depots are located at the maximum \(P\) nodes, \(A = \left\{ {\left( {i,j} \right):i,j \in N,i \ne j} \right\}\) is the set of arcs with distance \(d_{ij}\) for any arc \(\left( {i,j} \right) \in A\), and \(c_{i}\) is the fixed operating cost of a depot at node \(i \in N\). Also there are fleet of \(m\) same vehicles, by capacity \(C\) that try to serve the customers (with nonnegative demand \(q_{i}\) for a customer \(i\)) across the at most \(P\) depot(s).

For the, soft and hard time windows and service time at node \(i \in N\) the notations \(\left[ {l_{i} ,u_{i} } \right]\), \(\left[ {a_{i} ,b_{i} } \right]\) and \(s_{i}\) are applied respectively. The continuous nonnegative variable \(t_{i}\) is considered for the service start time at node \(i \in N\). If a vehicle arrives at customer \(i\) before \(l_{i}\), it penalties as much as \(PL(l_{i} - t_{i} ) \ge 0\), and if a vehicle arrives at customer \(i\) after \(u_{i}\), it penalties as much as \(PU(t_{i} - u_{i} ) \ge 0\). Also, the vehicles are not allowed to service the demand point \(i\) before \(a_{i}\) and after \(b_{i}\).

Congestion has always been a common phenomenon, and so there are various restrictions on the speed of vehicles during the day. Furthermore, each arc has its speed limitations. So, In addition, to consider the vehicle speed as a variable, the restrictions on the speed of vehicles during the day are taken into account. For this reason, three time periods with different limitation speeds are associated with the planning horizon periods called the morning peak, the free-flow speed, and the evening peak. In the morning and evening peak periods which incorporate with rush hours, the speed is low relatively. Whereas in the free-flow speed period, which incorporates with the middle of the day, the speed of a vehicle is more than the other two periods (because the traffic density is lower).

Let \(\left[ {0,T_{\max } } \right]\) denoted for the planning horizon time for any arc \((i,j)\), and \(a_{1}\) and \(a_{2}\) are considered as breakpoints of this interval for speeds change (\(0 < a_{1} < a_{2} < T_{\max }\)) on this arc.

The three traffic situations with different speeds on arc \((i,j)\) can be described as Fig. 1.

Fig. 1
figure 1

Different speed on a time dependent travel time for arc \((i,j)\)

Full size image

In addition, it is assumed that the departure time of the vehicles from the depots is not necessarily zero time and it may be, the vehicle starts moving from non-zero time. Given the penalties for early and late service, it makes sense for the vehicle to have a non-zero departure time. In this respect, the following proposed model is different from the models addressed in the literature. The utilized sets, indices, and parameters in the model formulation are as Tables 2 and 3:

Table 2 Parameters and notations
Full size table
Table 3 The variables
Full size table

With respect to above notations, a mathematical formulation of the TDGLRP with variable speed model is as:

$$ P_{1} :Z_{1} = {\text{min}}\sum\limits_{j \in N} {PL\max \{ l_{j} - t_{j} ,0\} + PU\max \{ t_{j} - u_{j} ,0\} } + \sum\limits_{k \in N} {c_{k} y_{kk} } + eFC $$
(1)
$$ {\text{S}}.{\text{T}}\sum\limits_{k \in N} {y_{ik} } = 1\quad \forall i $$
(2)
$$ y_{ik} \le y_{kk} \quad \forall i,k $$
(3)
$$ \sum\limits_{k \in N} {y_{kk} } \, \le p $$
(4)
$$ \sum\limits_{k \in N} {\sum\limits_{{j \in N - \left\{ k \right\}}} {x_{kj}^{k} } } \le m $$
(5)
$$ \sum\limits_{{j \in N - \left\{ i \right\}}} {x_{ij}^{k} } = y_{ik} \quad \forall i,k:k \ne i $$
(6)
$$ \sum\limits_{{j \in N - \left\{ k \right\}}} {x_{jk}^{k} } = y_{ik} \quad \forall i,k:k \ne i $$
(7)
$$ \sum\limits_{{j \in N - \left\{ k \right\}}} {x_{jk}^{k} } = \sum\limits_{{j \in N - \left\{ k \right\}}} {x_{kj}^{k} } \quad \forall k:k \ne j $$
(8)
$$ d_{ij} x_{ij}^{k} = \sum\limits_{p} {z_{ij}^{p} } \quad \forall \left( {i,j} \right) \in A,k $$
(9)
$$ t_{ij}^{p} = \frac{{z_{ij}^{p} }}{{v_{ij}^{p} }}\quad \forall \left( {i,j} \right) \in A,p $$
(10)
$$ t_{i} + s_{i} + t_{ij}^{1} - a_{1} \le M\delta_{ij}^{1} \quad \forall \left( {i,j} \right) \in A $$
(11)
$$ t_{ij}^{2} \le b_{j} \delta_{ij}^{1} \quad \forall \left( {i,j} \right) \in A $$
(12)
$$ a_{1} - t_{i} - s_{i} - t_{ij}^{1} \le M(1 - \delta_{ij}^{1} )\quad \forall \left( {i,j} \right) \in A $$
(13)
$$ t_{i} + s_{i} + t_{ij}^{1} + t_{ij}^{2} - a_{2} \le M\delta_{ij}^{2} \quad \forall \left( {i,j} \right) \in A $$
(14)
$$ t_{ij}^{3} \le b_{j} \delta_{ij}^{2} \quad \forall \left( {i,j} \right) \in A $$
(15)
$$ a_{2} - t_{i} - s_{i} - t_{ij}^{1} - t_{ij}^{2} \le M(1 - \delta_{ij}^{2} )\quad $$
(16)
$$ t_{ij}^{p} \le T_{\max } \sum\limits_{k} {x_{ij}^{k} } \quad \forall \left( {i,j} \right) \in A $$
(17)
$$ t_{i} + s_{i} + \sum\limits_{p} {t_{ij}^{p} } - (b_{i} + s_{i} )(1 - x_{ij}^{k} ) \le t_{j} \quad \forall \left( {i,j} \right) \in A,k:k \ne i,j $$
(18)
$$ t_{k} + \sum\limits_{p} {t_{ij}^{p} } - T_{\max } (1 - x_{kj}^{k} ) \le t_{j} \quad \forall k,j:k \ne j $$
(19)
$$ t_{i} \le T_{\max } \quad \forall i $$
(20)
$$ v_{ijl}^{p} \le v_{ij}^{p} \le v_{iju}^{p} \quad \forall \left( {i,j} \right) \in A,p $$
(21)
$$ a_{j} (1 - y_{jj} ) \le t_{j} \le b_{j} (1 - y_{jj} ) + T_{\max } y_{jj} \quad \forall j $$
(22)
$$ \sum\limits_{{j \in N - \left\{ i \right\}}} {f_{ji} } \le \sum\limits_{{j \in N - \left\{ i \right\}}} {f_{ij} } - q_{i} (1 - y_{ii} ) + \sum\limits_{k \in N} {q_{k} y_{ii} } \quad \forall i $$
(23)
$$ f_{ij} \le C\sum\limits_{k \in N} {x_{ij}^{k} } \quad \forall \left( {i,j} \right) \in A $$
(24)
$$ \sum\limits_{{j \in N - \left\{ i \right\}}} {f_{ji} } \le C(1 - y_{ii} )\quad \forall i $$
(25)
$$ x_{ij}^{k} ,y_{ik} ,\delta_{ij}^{1} ,\delta_{ij}^{2} \in \left\{ {0,1} \right\}\quad \forall i,j,k $$
(26)
$$ v_{ij}^{p} ,t_{ij}^{p} ,z_{ij}^{p} ,t_{j} ,f_{ij} \ge 0\quad \forall i,j,p $$
(27)

The objective function includes three components. The first one minimizes the penalty for late and early delivery of services, the second one, is about minimizing the fixed cost of operating depots. In the third part, the total cost of fuel consumption and emissions based on the variable speed is minimized. The third part \(FC\) is obtained based on the CMEM model which will be described briefly in the next subsection.

Equality (2) shows that each customer is allocated to one depot exactly. Restriction (3) states that customers should not be assigned to nodes where there are no open locations. The maximum number of depots used is indicated by Constraint (4). Constraint (5) is about the maximum number of vehicles that can be used for customer service. Constraints (6) and (7) ensure that if a specific depot serviced a customer, a vehicle will refer to the customer before and after the other two customers assigned to that depot.

Due to equality (8), the number of vehicles entering and leaving the depot is the same. The Constraint (9) indicates the distance traveled at different speeds on each arc, and constraints (10) is about the time passed at different speeds. Constraints (11)–(16) stipulate that the vehicle travels on arc \((i,j)\) should occur at one, two or three of the time congestion regions. Constraint (17) guarantees that, a vehicle travels on arc \((i,j)\) in time period \(p\), if both customers \(i\) and \(j\) are allocated to a common depot.

The inequality (18) calculates the arrival time of a vehicle at node \(j\) after leaving the node \(i\).

Constraint (19) computing of the time of arrival of the vehicle to the first customer visited after leaving the depot by departure time \(t_{k}\). Constraint (20) indicates the return time (no later than \(T_{\max }\)) of the vehicle to the depot. The constraint (21) shows the speed limits at different time congestions. Constraint (22) shows the limitation of hard time window for customers.

This inequality also ensure that, if mode \(y_{jj} = 1\) occurs i.e., depot is located at a node \(j\), then departure time of the vehicle is at most \(T_{\max }\). The flow conservation between nodes (except for opened depots) provided by constraint (23). This constraint guarantees that the demands of customer are met as well as vehicle capacity by constraint (24). Notice that \(f_{ij}\) is the total amount of demand (excluding customer \(j\)) in the path, and if \(k\) is selected as the depot, the customer \(k\) is not considered.

It should be noted that load level vehicles restrictions also prevent the creation of sub-tour by constraint (25).

Finally, constraint (26) and (27) show the binary restrictions as well as non-negativity limitations on variables.

2.2 The CMEM model for calculating fuel consumption and emissions

The amount of greenhouse gas emissions is directly related to fuel consumption, so the amount of emissions can be calculated after determining the amount of fuel consumption.

The superior model from the literature to calculate the emission is that takes into account other more precise parameters of the vehicles such as engine friction coefficient, engine speed, and vehicle speed while moving. Scora and Barth [21], Barth et al. [22], Barth and Boriboonsomsin [23], and Dukkanci et al. [20], used a comprehensive modal emission model (CMEM) to calculate emission. In this model, it has been tried to consider all the factors influencing the amount of fuel consumption and emissions. To present and display the model CMEM, it is necessary to define the symbols as follows:

\(\xi\)

The fuel-to-air mass ratio

\(\eta\)

The efficiency parameter for diesel engines

\(\kappa\)

The heating value of a typical diesel fuel

\(n_{tf}\)

The efficiency of the vehicle drive train, which is related to the overall efficiency of all engine transmission components to the wheels

\(p_{acc}\)

The engine power demand related to engine losses and the performance of vehicle accessories such as the use of air conditioning

\(p_{tract}\)

The total tensile power required (in kW)

\(\omega\)

Weight of goods shipped

\(a\)

The instantaneous acceleration

\(S\)

The frontal surface area (in m2)

\(g\)

The gravitational constant (in m/s2)

\(\theta\)

The road angle

\(C_{d}\)

The coefficient of aerodynamic drag

\(C_{r}\)

The coefficient of rolling resistance

\(\rho\)

The air density (in kg/m3)

\(\psi\)

The conversion factor of fuel

\(V\)

The engine displacement (in L)

\(K\)

The engine friction factor

\(\Upsilon\)

The engine speed

The core of the CMEM is the fuel consumption rate. Fuel consumption per cycle is about a linear function of work output per cycle for power level less than two-thirds of the power at wide-open throttle. This is directly related to the engine power demand (\(p\)) and engine speed (\(\Upsilon\)). The basic fuel consumption module (based on [35]) is as follows:

$$ F_{r} = \xi {{\left( {K\Upsilon V + \frac{P}{\eta }} \right)} \mathord{\left/ {\vphantom {{\left( {K\Upsilon V + \frac{P}{\eta }} \right)} \kappa }} \right. \kern-\nulldelimiterspace} \kappa } $$

in which, \(p = {{p_{tract} } \mathord{\left/ {\vphantom {{p_{tract} } {n_{tf} }}} \right. \kern-\nulldelimiterspace} {n_{tf} }} + p_{acc}\) and \(p_{tract}\) in turn, is calculated as follows:

$$ p_{tract} = {{\left( {Ma + Mg\sin \theta + 0.5C_{d} \rho Sv^{2} + MgC_{r} \cos \theta } \right)v} \mathord{\left/ {\vphantom {{\left( {Ma + Mg\sin \theta + 0.5C_{d} \rho Sv^{2} + MgC_{r} \cos \theta } \right)v} {1000}}} \right. \kern-\nulldelimiterspace} {1000}} $$

For simplifying the above formulation of fuel consumption rate \(F_{r}\) (in L) the new parameters are defined. Suppose that the vehicle travels a road of \(d\) units (in m) at a constant speed \(v\), if \(\lambda = {\zeta \mathord{\left/ {\vphantom {\zeta {\kappa \psi }}} \right. \kern-\nulldelimiterspace} {\kappa \psi }}\), \(\gamma = {1 \mathord{\left/ {\vphantom {1 {1000n_{tf} \eta }}} \right. \kern-\nulldelimiterspace} {1000n_{tf} \eta }}\), \(\alpha = a + g\sin \theta + gC_{r} \cos \theta\), \(\beta = 0.5C_{d} \rho S\), then:

$$ F_{r} = \alpha \lambda \gamma dM + \lambda \gamma d\beta v^{2} + {{\lambda K\Upsilon Vd} \mathord{\left/ {\vphantom {{\lambda K\Upsilon Vd} v}} \right. \kern-\nulldelimiterspace} v} $$

Note that, it can be easily shown that function fuel consumption \(F_{r}\) has a minimum point in terms of \(v\) (assuming the other parameters are constant). The minimum point is determined according to the values \(\lambda ,\beta ,\Upsilon ,V\) and \(K\). This means that the fuel consumption is decreased if the speed increases up to a certain value, and after this specified amount, fuel consumption increases in proportion to the increase in speed.

By using the above specific formulations, the third part of the objective function of the mathematical model of TDGLRP is defined as:

$$ F_{r} = FC = \sum\limits_{(i,j) \in A} {\left[ {\left( {\alpha \gamma \lambda d_{ij} \omega \sum\limits_{k \in N} {x_{ij}^{k} } } \right) + (\alpha \gamma \lambda d_{ij} f_{ij} ) + \left( {\beta \gamma \lambda d_{ij} \sum\limits_{(i,j) \in A} {\sum\limits_{p} {(v_{ij}^{p} )}^{2} } } \right. + \left( {K\Upsilon V\lambda d_{ij} \sum\limits_{(i,j) \in A} {\frac{1}{{\sum\limits_{p} {v_{ij}^{p} } }}} } \right)} \right]} $$

All three of these components translate directly into the total cost of fuel consumption and related emissions calculated by the unit cost \(e = (c_{f} + e_{f} )\) multiplied by the total amount of fuel consumed overall links.

The proposed model \(P_{1}\) is different from the other related GLRP models and its extension because of the incorporation of Time-dependent and variable speeds simultaneously. However, due to the variable speed, nonlinear expressions appear both in the in constraints and in the objective function. In the next section and to get rid of nonlinearity terms, some linearization operations are performed and then the problem is solved.

3 Solution method

TDGLRP with variable speed is an extended version of the classical VRP and so it is NP-hard. It is remarkable that, when the number of customers and depots are increased, the model size grows rapidly and so obtaining good or even feasible solutions to medium scale and large scale cases of the proposed model in a reasonable time is not possible with Mixed-Integer Nonlinear Programming (MINLP) solvers. Our proposed model encompasses nonlinear terms in both objective and constraints which makes the model more complicated. In this section, we try to provide an efficient method to achieve optimal or near-optimal solutions in a reasonable computation time. The addressed method is based on two main phases. In the first phase of the approach by using some linearization techniques, the nonlinearity terms associated with the model are linearized. Then in the second phase, the adoptive PSO method is applied to solve the linearized model.

3.1 Linearization phase

For linearization of the first term of objective function i.e. \(\sum\limits_{j \in N} {PL\max \{ l_{j} - t_{j} ,0\} + PU\max \{ t_{j} - u_{j} ,0\} }\), two additional nonnegative continuous variables \(T_{lj}\) and \(T_{uj}\) (for any \(j\)) are added to the problem as well as the following new sets constraint:

$$ l_{j} - t_{j} \le T_{lj} \quad \forall j $$
(28)
$$ t_{j} - u_{j} \le T_{uj} \quad \forall j $$
(29)

Then the first part of objective function is changed to \(\sum\limits_{j \in N} {PLT_{lj} + PUT_{uj} }\).

In the linearization operation of the multiplication of variables, the type of linearization can be different depending on what kind of variables are multiplied. In the main model, the variable speed is continuous. Due to the complexity of linearization of the multiplication of continuous variables, the variable speed is considered as a discrete variable [20] and the linearization is performed based on it. There are different approaches for linearizing expressions that contain integer variables, but using binary variables is a common method for this type of linearization. There are two important approaches to display a discrete variable using binary variables. In the first approach, for each value that a discrete variable can take, a binary variable is defined and a constraint is added to the problem that only one of these variables can take the value 1 to select only one velocity. Although this method is manageable, the number of defined binary variables increases rapidly as the number of states that speed can take. Another method can be used to show the integer variable based on binary variables. This method uses the rule that any integer can be written in base2. So, a finite sets \(R_{ij}^{p} = \left\{ {1,2,3,...r,..} \right\}\) with \(r \in R\), for speed levels are defined corresponds to a fixed speed \(v_{ijr}^{p}\), i.e. \(v_{ij}^{p} \in \left\{ {v_{ij1}^{p} ,v_{ij2}^{p} ,...,v_{ijr}^{p} ,...} \right\}\), to linearize the expressions that contain \(v_{ij}^{p}\)(as a discrete variable). For this reason and for every period \(p\), Since \(v_{ijl}^{p} \le v_{ij}^{p} \le v_{iju}^{p}\), then \(v_{ij}^{p}\) can be written as \(v_{ij}^{p} = \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \tau_{ij\theta }^{p} }\) wherein \(\tau_{ij\theta }^{p}\) are binary variables and \(\Omega\) is the smallest number that holds in the equation \(v_{iju}^{p} \le 2^{\Omega }\) or for convenience we can say \(\Omega = \left[ {\frac{{\ln v_{iju}^{p} }}{\ln 2}} \right] + 1\) (\(\Omega\) is defined as a parameter based on the upper-bound of speed at each arc and period).

To linearize expressions that include \(\left( {v_{ij}^{p} } \right)^{2}\), first, one of the multiplicative variables \(v_{ij}^{p}\) is written based on binary variables \(\tau_{ij\theta }^{p}\) and then the linearization approach by multiplying the integer variables by the binary variables is performed. In this way, a new integer variable \(\sigma_{ij\theta }^{p}\) is defined and replaced by the multiplication of the integer and binary variables \(v_{ij}^{p} \tau_{ij\theta }^{p}\):

$$ \left( {v_{ij}^{p} } \right)^{2} = v_{ij}^{p} v_{ij}^{p} = v_{ij}^{p} \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \tau_{ij\theta }^{p} } = \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } v_{ij}^{p} \tau_{ij\theta }^{p} } = \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \sigma_{ij\theta }^{p} } $$

such that \(\sigma_{ij\theta }^{p} \in {\rm Z}^{ + }\). And the following constraints also added to the model because of substituting \(v_{ij}^{p} \tau_{ij\theta }^{p} = \sigma_{ij\theta }^{p}\).

$$ \sigma_{ij\theta }^{p} \le M\tau_{ij\theta }^{p} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(30)
$$ M(\tau_{ij\theta }^{p} - 1) + v_{ij}^{p} \le \sigma_{ij\theta }^{p} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(31)
$$ \sigma_{ij\theta }^{p} \le M(1 - \tau_{ij\theta }^{p} ) + v_{ij}^{p} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(32)

These constraints guarantee that, if \(\tau_{ij\theta }^{p} = 1\), then \(\sigma_{ij\theta }^{p} = v_{ij}^{p}\) and if \(\tau_{ij\theta }^{p} = 0\) then \(\sigma_{ij\theta }^{p} = 0\).

Now, consider the nonlinearity term \(\frac{1}{{\sum\limits_{p} {v_{ij}^{p} } }}\), the following method can be used to linearize this expression, firstly define the new continues variable \(h_{ij}\) and let \(\frac{1}{{\sum\limits_{p} {v_{ij}^{p} } }} = h_{ij}\), then \(1 = \sum\limits_{p} {h_{ij} v_{ij}^{p} }\), so

$$ h_{ij} v_{ij}^{p} = h_{ij} \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \tau_{ij\theta }^{p} } = \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } h_{ij} \tau_{ij\theta }^{p} } = \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \pi_{ij\theta }^{p} } $$

where in \(\pi_{ij\theta }^{p} = h_{ij} \tau_{ij\theta }^{p}\) for every \(\left( {i,j} \right) \in A,p,\theta\). And the constraints similar to the previous constraints are added to the problem:

$$ \pi_{ij\theta }^{p} \le M\tau_{ij\theta }^{p} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(33)
$$ M(\tau_{ij\theta }^{p} - 1) + h_{ij} \le \pi_{ij\theta }^{p} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(34)
$$ \pi_{ij\theta }^{p} \le M(1 - \tau_{ij\theta }^{p} ) + h_{ij} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(35)

Finally for nonlinearity term \(t_{ij}^{p} = \frac{{z_{ij}^{p} }}{{v_{ij}^{p} }}\) the same technique is applied. To this end, in first, let \(v_{ij}^{p} t_{ij}^{p} = z_{ij}^{p}\) and so \(\sum\limits_{\theta = 0}^{\Omega } {2^{\theta } t_{ij}^{p} \tau_{ij\theta }^{p} } = z_{ij}^{p}\). By defining the new nonnegative continues variable \(\kappa_{ij\theta }^{p}\), we have \(\sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \kappa_{ij\theta }^{p} } = z_{ij}^{p}\) which \(\kappa_{ij\theta }^{p} = t_{ij}^{p} \tau_{ij\theta }^{p}\) for every \((i,j) \in A,p,\theta\). And following constraints are also added to the main model:

$$ \kappa_{ij\theta }^{p} \le M\tau_{ij\theta }^{p} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(36)
$$ M(\tau_{ij\theta }^{p} - 1) + t_{ij}^{p} \le \kappa_{ij\theta }^{p} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(37)
$$ \kappa_{ij\theta }^{p} \le M(1 - \tau_{ij\theta }^{p} ) + t_{ij}^{p} \quad \forall \left( {i,j} \right) \in A,p,\theta $$
(38)

So, the problem \(P_{1}\) is converted to the following problem \(P_{1}^{\prime }\):

$$ \begin{aligned} P^{\prime}_{1} :Z_{1} & = {\text{min}}\sum\limits_{j \in N} {\sum\limits_{j \in N} {PLT_{lj} + PUT_{uj} } } + \sum\limits_{k \in N} {c_{k} y_{kk} } \\ & \quad + e\sum\limits_{(i,j) \in A} {\left[ {\left( {\alpha \gamma \lambda d_{ij} \omega \sum\limits_{k \in N} {x_{ij}^{k} } } \right) + (\alpha \gamma \lambda d_{ij} f_{ij} ) + \left( {\beta \gamma \lambda d_{ij} \sum\limits_{(i,j) \in A} {\sum\limits_{p} {\sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \sigma_{ij\theta }^{p} } } } + \left( {K\Upsilon V\lambda d_{ij} \sum\limits_{(i,j) \in A} {h_{ij} } } \right)} \right.} \right]} \\ & {\text{S}}.{\text{T}}\;(2) - (9)\;and\;(11) - (37) \\ & \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \kappa_{ij\theta }^{p} } = z_{ij}^{p} \quad \forall i,j,p \\ \end{aligned} $$
(39)
$$ \tau_{ij\theta }^{p} , \in \left\{ {0,1} \right\}\quad \forall i,j,p,\theta $$
(40)
$$ T_{lj} ,T_{uj} ,\kappa_{ij\theta }^{p} ,\pi_{ij\theta }^{p} ,h_{ij} \ge 0,\sigma_{ij\theta }^{p} ,v_{ij}^{p} \in Z^{ + } \quad \forall i,j,p,\theta $$
(41)

3.2 Quantum BPSO algorithm

QBPSO is comprehensively applied to solve IP problems. One of the main contributions of this paper is adapting the algorithm to solve the transformed Mixed Integer problem efficiency. The modification is carried out on the global best position at each iteration to improve the overall algorithm performance.

3.2.1 Preliminaries

The particle swarm optimization (PSO) method is a population-based algorithm originally proposed by Kennedy and Eberhart [36]. In the system, the social behavior of the flock of birds is simulated, so that the birds (particles) represent the nomination solutions to the problem, flying through the search space to gain the optimal solution. In each iteration, the particles move to the desired level by tracing their best-discovered solutions so far and determine the best global position by each particle in the swarm.

Suppose the dimension of the search space is \(K\). For the \(i\)-th particle, the current position and velocity vectors are represented as \(X_{i} = (x_{i}^{1} ,...,x_{i}^{j} ,...,x_{i}^{K} )\) and \(V_{i} = (v_{i}^{1} ,...,v_{i}^{j} ,...,v_{i}^{K} )\). Let \(Pbest_{i} = (pbest_{i}^{1} ,...,pbest_{i}^{j} ,...,pbest_{i}^{K} )\) demonstrate the best position of the \(i\)-th particle and \(Gbest = (gbest^{1} ,...,gbest^{j} ,...,gbest^{K} )\) be the group's best position recorded so far. The following equations show how to update the velocity and position of \(i\)-th particle at \(t\)-th iteration to \(t + 1\)-th iteration:

$$ V_{i} (t + 1) = wV_{i} (t) + c_{1} r_{1} (Pbest_{i} (t)) - X_{i} (t)) + c_{2} r_{2} (Gbest(t)) - X_{i} (t)) $$
(42)
$$ X_{i} (t + 1) = X_{i} (t) + V_{i} (t + 1) $$
(43)

where \(w\) is the inertia weight, \(c_{1}\) and \(c_{2}\) are utilise to show the acceleration coefficients. These coefficients represent the degree of belief on the particle's own experience and the whole swarm experience, respectively. Also \(r_{1}\) and \(r_{2}\) are random values in the interval \(\left[ {0,1} \right]\).

3.2.2 Binary PSO (BPSO)

Kennedy and Eberhart [36] proposed the Binary version of PSO (BPSO). In this version, each particle is represented by a string of 0 and 1. Particle velocity is related to the probability with which a little flip will occur [37]. Remarkably, the updating equation for velocity (42) is remained unchanged while the equation of updating position changes as follows:

$$ x_{i}^{j} (t) = \left\{ {\begin{array}{*{20}l} 1 \hfill & {if\,u_{i}^{j} (t) > S(v_{i}^{j} (t))} \hfill \\ 0 \hfill & {otherwise} \hfill \\ \end{array} } \right. $$
(44)

where \(u_{i}^{j} (t)\) is a random number belonging to \(\left[ {0,1} \right]\), and \(S(v_{i}^{j} (t))\) is the velocity value sigmoid function (\(1/(1 + exp( - v_{i}^{j} (t)))\)) that specifies the probability of the \(j\)th bit of \(i\)th particle, i.e., \(x_{i}^{j} (t)\) being 0 or 1 at tth iteration.

3.2.3 Quantum Binary PSO (QBPSO)

The idea of "mechanism of biological evolution" and "simulation of things" have produced successful theories, one of which is binary quantum PSO (QBPSO) proposed by Yang et al. [38]. One of the major drawbacks of the BPSO method is being unintelligent \(S(v_{i}^{j} )\), making it unable to lead the particles to the promising region of the search space. Furthermore, parameter selection is difficult. QBPSO overcomes these disadvantages. In QBPSO, a population of quantum particle vector \(Q(t)\) is used instead of a sigmoid function. Remarkably, quantum bit or ‘qubit’, is the smallest unit that carries information which can be either "1" or "0" or at each extraordinary position. Hence, the quantum particle population is expressed as \(Q(t) = [Q_{1} (t),...,Q_{i} (t),...,Q_{N} (t)]\), where \(Q_{i} (t) = [q_{i}^{1} (t),...,q_{i}^{j} (t),...,q_{i}^{K} (t)]\) and \(0 \le q_{i}^{j} (t) \le 1\,,\,\,i = 1,2,...,N,j = 1,2,...,K\) represent the probability of the \(i\)th particle in the \(j\)th bit for taking zero value at the \(t\)th iteration.

In QBPSO, a quantum particle vector \(Q_{i} (t) = [q_{i}^{1} (t),...,q_{i}^{j} (t),...,q_{i}^{K} (t)]\) updates the position of particles by the following rule:

$$ x_{i}^{j} (t) = \left\{ {\begin{array}{*{20}l} 1 \hfill & {if\,u_{i}^{j} (t) > q_{i}^{j} (t)} \hfill \\ 0 \hfill & {otherwise} \hfill \\ \end{array} } \right. $$
(45)

Also, for updating the quantum particle vector, the following rules are used:

$$ Q_{groupbest} (t) = \alpha * Gbest(t) + \beta * (1 - Gbest(t)) $$
(46)
$$ Q_{selfbest,i} (t) = \alpha * Pbest_{i} (t) + \beta * (1 - Pbest_{i} (t)) $$
(47)
$$ Q_{i} (t + 1) = w * Q_{i} (t) + c_{1} * Q_{selfbest,i} (t) + c_{2} * Q_{groupbest} (t) $$
(48)

where \(\alpha ,\beta\) are control parameters and satisfied in relations \(\alpha + \beta = 1,\,\,0 \le \alpha ,\beta \le 1\). Furthermore, these parameters are tuned to control the degree of \(Q_{i}\). \(w,c_{1} ,c_{2}\) are PSO parameters and satisfied in relations \(w + c_{1} + c_{2} = 1,\,\,0 \le w,c_{1} ,c_{2} \le 1\). The parameters represent the degree of belief on oneself, local maximum, and global maximum, respectively. The general framework of QBPSO for the proposed model is described as follows:

3.2.4 QBPSO for solving the proposed BLPP

Below, the QBPSO algorithm is adopted for solving mixed-integer linear problems. In this algorithm, by the calculation fitness function iteratively, it is possible to get closer to the optimal solution step by step.

Adopted QBPSO algorithm.

Step 1: (Initialization).

1.1 Set the values parameters of the QBPSO algorithm and population sizes \(N\), \(Q_{i}\).

1.2. By Eq. (44), for any particle, the initialized value of the decision variables \(X_{m} = (x_{ij}^{km} ,y_{ik}^{m} ,\,\delta_{ij}^{1m} ,\delta_{ij}^{2m} ,\tau_{ij\theta }^{pm} )\) generate randomly; then, by fixing \(X_{m}\) in the problem \(P^{\prime}\), the linear problem is solved. (Of course, since the values of \(v_{ij}^{p}\) are determined with respect to the values of \(\tau_{ij\theta }^{p}\) and also, \(\sigma_{ij\theta }^{p}\) values are set based on \(v_{ij}^{p}\) values, so practically, after determining the values of \(\tau_{ij\theta }^{p}\), the variables \(v_{ij}^{p}\) and \(\sigma_{ij\theta }^{p}\) have the role of parameter in the model).

Let \(Y_{m}^{ * } = (t_{ij}^{p} ,z_{ij}^{p} ,t_{j} ,f_{ij} ,T_{lj} ,T_{uj} ,h_{ij} ,\kappa_{ij\theta }^{p} ,\pi_{ij\theta }^{p} )_{m}^{ * }\) be the optimal solution to the linear problem. Then, by fixing \(X_{r}\) and optimal values of the \(Y_{m}^{ * }\) (regarding \(X_{r}\)) in the objective function of problem \(P^{\prime}\), the fitness value of the current position of m-th particle \((X_{m} ,Y_{m}^{ * } )\) is calculated by using \(F(X_{m} ,Y_{m}^{ * } )\), where \(F\) known as \(P^{\prime}\)'s objective function. Consider the personal best position of m-th particle \(Pbest_{m} = (Xbest_{m} ,Ybest_{m} )\) equal to \((X_{m} ,Y_{m}^{ * } )\) and set the global best position \(Gbest = (Xbest,Ybest)\);

Step 2: (Updating \(X_{m}\)) Change \(Q_{m}\) and update \(X_{m}\) according to the QBPSO algorithm;

Step3: (Determining the particle's fitness) By fixing the new \(X_{m}\) in the problem \(P^{\prime}\), the related optimal continuous variables \(Y_{m}^{ * }\) are obtained. Then, by fixing \((X_{m} ,Y_{m}^{ * } )\) in the objective functions of problem \(P^{\prime}\), the position and fitness value of \(F(X_{m} ,Y_{m}^{ * } )\) is calculated;

Step4: (Updating the personal best position) If the fitness value of \((X_{m} ,Y_{m}^{ * } )\) is better than that of \(Pbest_{i} = (Xbest_{i} ,Ybest_{i} )\), update \(Pbest_{i}\);

Step5: (Updating the global best position) After comparing fitness value of \(Gbest\) with that of all personal best positions, the \(Gbest\) is updated with the global best position \(Gbest = (Xgbest,Ygbest)\);

Step6: (Termination) Go to step2 until the stopping criterion is met.

Note that, in the initialization phase, feasible solutions are generated, and this property is kept during the algorithm implementation.

4 Computational experiments

In this section, the evaluation of the proposed model and the efficiency of the algorithm are done. Firstly, the setting procedure of existing parameters in the algorithm will be explained. Then, the computational results on some existing test problems are provided by the proposed algorithm.

Computations are performed on a PC running with a Core(TM) i5, 3.19 GHz processor, and 4.0 GB RAM, and Windows 10 operating system. Also, GAMMS mathematical modeling-language with ILOG CPLEX 12.6 solver is used for coding the QBPSO algorithm.

4.1 Test instances and determining the value of parameters

The base of instances tested here are available at [39]. All values of emission parameters extracted from [20], and the VRP parameters are considered based on instances available at [39].

Of course these parameters does not include any information about the planning horizon congestion traffic times and the upper and lower levels of speed for arcs. For these reason, we assume that the planning horizon starts at the time 0, the points \(a_{1}\), \(a_{2}\), and \(T_{\max }\) are set at the times 2, 6, and 9 h, correspondingly. Each \(v_{ijl}^{1} ,v_{iju}^{1} ,v_{ijl}^{2} ,v_{iju}^{2} ,v_{ijl}^{3}\) and \(v_{iju}^{3}\) are generated randomly based on integer part of uniform distribution from \(U(24,26),U(44,48),U(53,57),U(85,95),U(27,31)\) and \(U(48,52)\) respectively. It is remarkable that, because of \(v_{ij}^{p} \in Z^{ + }\), then after identifying the upper and lower bounds of allowable speed, the value of \(v_{ij}^{p}\) is belong to the set \(\{ v_{ijl}^{p} ,v_{ijl}^{p} + 2,....,v_{ijl}^{p} + 2k,v_{iju}^{p} \}\) where \(v_{ijl}^{p} + 2k = v_{iju}^{p}\) or \(v_{ijl}^{p} + 2k < v_{iju}^{p}\). Also, the hard time windows for delivering services are obtained from \(U(\max \{ l_{j} - 600,0\} ,\min \{ u_{j} + 900,32400\} )\) in s.

The performance of the proposed approach is evaluated on different instances that described in previous section. To this end, the best parameters of the solution algorithm must be selected in the best way. One of the best techniques for determining the values of parameters in metaheuristics algorithms in order to obtain optimum performance is the Taguchi method. Hence, in this step, to reach the optimal or near-optimal solution, the impact of parameters \(c_{1} ,c_{2} ,w\), \(\alpha\), and \(\beta\) on the QBPSO efficiency and capability is provided. Remarkably, based on the relations \(\alpha + \beta = 1\) and \(w + c_{1} + c_{2} = 1\), setting the values of parameters \(c_{1} ,c_{2}\), \(\alpha\) is enough. For these factors, five levels are considered in Table 4. For this reason, the Taguchi \(L_{25}\) orthogonal array is selected (due to the number of parameters and their selected levels). Therefore, 25 experiments should be performed using a combination of levels for each parameter in accordance with \(L_{25}\).

Table 4 The levels of parameters
Full size table

The medium size of the instance (UK50_10 from the [39]) is used to calibrate the parameters of the proposed hybrid-based heuristic algorithm. Twenty-five particles are considered as population size, and the maximum iteration number of 100 is used for stopping criterion. For each set of parameters, ten runs of the algorithm are considered. The average value of objective function as the signal to noise (S/N) ratio is performed and reported in Table 5.

Table 5 The orthogonal array and the S/N ratios
Full size table

As a result, to identify the best optimal combination of the levels of parameters, the mean value of (S/N) is computed for each level. The results are depicted in Fig. 2.

Fig. 2
figure 2

SNR graph

Full size image

The results from the above figure show that the effects of the parameter \(\alpha\) on QBPSO performance in reaching the optimal value of a leader's profit are more significant than the two remaining parameters \(c_{1} ,c_{2}\). However, the optimum level of parameter \(c_{1} ,c_{2}\) and \(\alpha\) are \(c_{1} (2) = 0.2,c_{2} (3) = 0.3\) and \(\alpha (1) = 0.1\).

Table 6 reports the analysis of variance to determine the most effective parameters in QBPSO performance. The column percentage contribution shows the significance of parameter effects on the PSO-based method performance. It can be clearly deduced that \(\alpha\) is an important and unique parameter in this method with a 98.3% share in yield.

Table 6 The analysis of variance
Full size table

Finally, based on the above analysis, the proposed hybrid algorithm with an optimal combination of parameters is used to solve the problem under study.

4.2 Computational results

Based on the number of nodes from the [39], 9 different data sets are categorized for test instances and each of them involving 5 instances. The parameters used to create these instances are encoded in the filename as follows: these instances are based on real distances collected from randomly chosen UK cities as shown in [39]. The first number in the file name after UK shows the number of nodes contained in the instance. The second is the order number of the instance within the group.

So, totally 45 test instances have been used to verify the efficiency of the QBPSO algorithm. The computational results of the instances are brought in Table 7.

Table 7 Computational results obtained from comparison of methods
Full size table

The first column of the table demonstrate the name of each data set. \(Z_{CP}\) indicates the best objective value corresponding to the feasible solution obtained by CPLEX for the \(P^{\prime}\) within a time limit of 7200 s. CPLEX solver can obtained to the desired optimal solution for small instances (includes instances with 10 and 15 nodes). While, for medium size tests (includes instances with 20, 25, 50 and 75 nodes), CPLEX could not complete the solving process in a timely manner and therefore the best value obtained from the objective function was reported as a best solution found. Also for large scale data sets (includes instances with 100, 150 and 200 nodes) CPLEX cannot find any feasible solution for \(P^{\prime}\). In fact by increasing the size of the problem, the computing time performed by CPLEX increases too rapidly.

The labels \(Z_{PSO}\) and \(Z_{QBPSO}\) demonstrate the best solutions of the objective value obtained by the PSO and QBPSO methods, respectively.

The label \(Gap_{PSO}\)(\(Gap_{QbPSO}\)) is about the gap between \(Z_{CP}\) and the \(Z_{PSO}\)(\(Z_{QBPSO}\)) which is calculated by \(\frac{{Z_{PSO} (Z_{QbPSO} ) - Z_{CP} }}{{Z_{CP} }}\). The labels \(T_{CP}\), \(T_{PSO}\) and \(T_{QBPSO}\), represent the time (per second) required to solve the proposed model \(P^{\prime}\) by CPLEX, PSO and QBPSO respectively.

According to Table 7, the QBPSO can obtain the optimal solution for all small size cases except for the UK20_02, and the optimality gaps ranges are from 0 to 0.01, which showed the efficiency of the proposed algorithm for finding an optimal solution for these instances.

For some medium cases in particular, for size instances with 50 and 75 nodes, a feasible solution not available, by the CPLEX within the given time limit. In most of these cases, the proposed algorithm either introduces a better solution or at least finds a solution equal to the upper bound provided by CPLEX. Of course, this fact is confirmed by non-positive gaps. However, the gap between the upper bound obtained by CPLEX and the objective value of the QBPSO solution and is negligible, i.e. 0.1.

As the problem size increases the computation time required by CPLEX becomes very high. As a result, in all large-scale datasets, CPLEX is not able to find any feasible solution. Since the PSO and QBPSO method can obtain at least a feasible solution for large-scale instances, so the computation time and the performances of the PSO and QBPSO were reported. The computational results indicate that the time solutions of the PSO and QBPSO are appropriate and slightly increases with the size of the problem.

If we want to make a general comparison between the two PSO and QBPSO methods, we can say that the PSO method works relatively faster, but the QBPSO obtains more accurate solutions.

Remarkably, the existing time difference (albeit small) is related to the additional operation performed in the QBPSO method. Generally, the time required increases as expected but is still reasonable for this kind of problem.

4.3 Sensitive analysis of the model

In this section, some analysis for the model \(P^{\prime}\) is conducted, to evaluate of the solutions about the input data changes, such as the congestion time periods, the variables speeds, number of depots and vehicles and time windows. For this reason, we will provide a summary of the results for the samples that differ in one parameter.

4.3.1 The effect of congestion time periods

The congestion time period is one of the restrictions that have an effect on speed in delivery service time, costs and the emissions. For assessing the effect of congestion time dependent, three different of periods are considered. In the first one, the model is considered without any time dependent congestion, and in this case, there is only a period time \([0,T_{\max } ]\) and the model \(P^{\prime}\) becomes same as the model proposed in [20]. In the second test intermediate intervals are considered narrow and in the third one intermediate intervals are considered open range.

The obtained results show that using various interval traffic congestion period yields different results of the costs and the average speed (km per h).

Table 8, indicate that a lack of speed break points (without any time traffic congestion), total costs are decreased as well as the average speed and fuel consumption and hence the amount of emission and the related cost also decreased. In the second case (\(a_{1} = 3,a_{2} = 7\)), the first traffic interval, which has a higher speed limit, considered to be larger. Due to the fact that the vehicle speed is lower during this interval, the average speed decreases sharply. On the other hand, the penalty for late or early delivery of the service will be increased, and the emission costs are high due to increased fuel consumption. The second interval congestion \([a_{1} ,a_{2} ]\) known as free-flow speed, and when the limit of this interval is reduced, (considered a more open interval), the average speed of the vehicle increases and the fuel consumption as well as pollution decreased. This can be clearly seen in the third mode. In this case, the penalty for late or early delay is less and the cost is lower than in the second case. Although the best results are for the case without any time traffic congestion, but it does not occur in the real world.

Table 8 Different time depend analysis
Full size table

4.3.2 The effect of variables speeds

In this section, we try to show the effect of variable speed is related to the objective function on different tests. To this end, three different of constant speed as well as variable speed are considered. The computational results are shown in Table 9.

Table 9 Analysis of variables speed vs different fixed speed
Full size table

The results of Table 9 show that using a low constant speed (with traffic congestion) increases fuel consumption and hence emission cost, as well as increases the amount of penalty early or delay service, and ultimately the final cost is higher than the optimal cost. While high speeds reduce the penalty for early or late service, and of course if the speed increases to a certain level, the cost of emission decreases as fuel consumption decreased, and if the speed increases too much, the fuel consumption increased as well emission costs. However, the low-speed level has an undeniable difference from the optimal value. The value closest to objective function No.1 is obtained with the mean value (No. 3) of speeds, but again in no case with constant speed has reached the optimal value of No. 1. These results demonstrate that by considering the variable speed, the model seeks to find a balance between the cost of penalties and emission and other costs.

4.3.3 The effect of the fuel consumption cost

In the previous analysis, it was shown that determining an appropriate speed causes it to go down the fuel consumption and greenhouse gas emissions and hence the related costs.

Now, we try to do additional tests to evaluate the sensitivity of the resulting solutions to changes in unit fuel costs. For this reason, we consider different amounts of costs in interval \(\left[ {0.5\,\,2.4} \right]\). Remarkably, the basic cost per liter in the samples is 1.4. Table 10 reports a summary of results, the columns of which show the value of an objective function, fuel consumption, average vehicle speed, and penalty function.

Table 10 Analysis of the effect of different value of the fuel cost
Full size table

The computational results from Table 10 show that the fewer changes of the unit fuel consumption do not significantly alter emission cost, penalty cost, and overall the solutions obtained.

However, more drastic changes may lead to significant differences in the solution obtained. The higher the fuel cost, leads to a decrease in average speed, a decrease in fuel consumption and consequently a decrease in emission cost, an increase in the amount of late and early penalties, and the total increase in the objective function value. Also, the lower the fuel cost, leads to an increase in average speed, an increase in fuel consumption and consequently an increase in emission cost, a decrease in the amount of late and early penalties, and the total increase in the objective function value. Of course, it can also be inferred that the effect of fuel consumption on the objective function is almost less than the soon and late penalty. In fact in some cases for serving customers within the predetermined hard time windows or even soft time windows (with high penalties for delayed and early), vehicles are forced to increase their speed even if it leads to the need for more fuel and so emission. In the next analysis, the effects of time windows on the overall costs and fuel consumption are investigated.

4.3.4 The effect of time windows

In this section, the effects of time windows are investigated on the addressed model. The results reported in Table 11 for narrowing the hard and soft time windows simultaneously are narrowed up to 50%, i.e. the distance from upper and lower bounds are decreased up to 50%.

Table 11 Analysis of the effect of different value of the fuel cost
Full size table

It is deduced from the results that narrowing up to up to 20% has no significant effect on solutions. Whereas it causes to increase the total cost and the fuel consumption up to is less than 2%. While, if time windows are narrowed down by more than 30%, there are considerable changes on the solutions in terms of fuel consumption (and so emission cost) and objective costs, as far as these changes are close to 10%. Also, as the distance between soft and hard time windows decreases, the amount of penalties decreases, and instead, using more speed for timely service is needed. Therefore the emission costs are increased.

5 Conclusions

This paper developed a variant of GLRP. And an attempt has been made to present a model whose vacancy is sensed in the literature and is considered practical and close to reality.

To this end, the routing problem for a fleet of vehicles in the presence of traffic congestion with different time zones was done while taking variable speed decisions into account. Due to the variable speed of the vehicle, the model was considered nonlinear and we have proposed some linearization techniques to get rid of linear expressions to obtain the optimal or near-optimal solutions. Then heuristic QBPSO algorithm was developed for solving the linearized model.

In continue, comparison of the proposed QBPSO method with PSO and CPLEX solver in terms of solution quality and time was reported. Computational results confirmed the efficiency of the proposed method for different sizes of the problem. One of the advantages of this method is its ability to be widely used to solve similar linear and nonlinear programming problems. Also, we believe that the applied method has the adaptable ability to improve itself or integrate with other algorithms to develop the methods.

In the end different sensitivity analyses have conducted for the computational study of the proposed model. To this end some key parameters such as the congestion time, speeds, time window and fuel consumption and emission cost are changed. The overall results show that how much the fuel consumption, emissions, and objective functions are affected by these parameters. Our experiments confirm the superiority of the proposed model over time-independent approaches as well as constant velocity, both in terms of emission and final costs. It seems that the proposed model can be used for problems with alternative fuels or even cold GVRP, which can be considered as a suggested work for future research. Furthermore, the structure of the linearized model is such that heuristic methods such as benders decomposition and Lagrangean relaxation can be applied to solve it.

Herein, some parameters such as time windows and demands were assumed to be a fixed values that may be considering as a nondeterministic parameters would be a worthy for future research.