The Inventory Pollution-Routing Problem Under Uncertainty

Abstract

Carbon emissions from supply chain operations are extensively contributing to the global warming. Sustainable supply chain management literature has seen more emphasis on greening of production operations and designing of greener supply networks, considering transportation emissions as “necessary evil”. This chapter aims to investigate the economic and environmental consequences of transport routing decisions in a supply chain with vertical collaboration, for instance through Vendor Managed Inventory. An optimization model and solution method is presented for an Inventory Pollution-Routing Problem (IPRP) in which inventory and transportation costs and emissions as well as demand uncertainty concerns are explicitly incorporated. The proposed model can be used to explore possible tradeoffs between emissions costs and operational costs for green inventory routing decision making. A set of computational tests are designed for performance benchmark of the proposed model and solution method.

1 Introduction

Reducing and mitigating carbon emissions, the culprit of global warming and climate change, is an increasingly important concern for both industry practitioners and governments (IPCC 2007). In the UK, the government has targeted to reduce carbon emissions by 60 % from 1990 levels by 2050 (Carbon Trust 2006). The UN, the EU, and many countries have enacted legislations or designed/implemented mechanisms, such as carbon tax, carbon offset, clean development, and cap and trade, to curb the total amount of carbon emissions. In response to such mandates and to address the related stakeholder concerns, companies worldwide have undertaken initiatives to reduce their carbon footprints.

However, these initiatives have largely focused on investment in new technology, developing energy-efficient equipment and facilities, and finding cleaner energy sources. While such efforts are valuable, they tend to ignore a potentially more significant sources of emissions derived. It is therefore necessary to address the problem of carbon emissions reduction from a supply chain and logistics perspective. Carbon Trust (2006) in the UK suggests that companies use a supply chain perspective to look for new ways of reducing carbon emissions. For example, it is shown that supply chain emissions reduction program may be less costly to achieve the same emissions reduction goals obtained by cleaner technologies (Benjaafar et al. 2013).

Recent literature reviews have identified a growing need for developing quantitative models, empirical research, and decision support tools for green production, operations, logistics and supply chain management (Fahimnia et al. 2015b). At the forefront of this call for future research is greening of transportation and distribution sub-system, one of the major contributors to Greenhouse Gas (GHG) emissions. According to the corporate GHG emissions report published by OECD, transportation is responsible for almost 14 % of total CO₂ emissions, since these emissions are directly proportional to the amount of fuel consumed by vehicles (OECD 2012). Only road-based transportation takes approximately 80 % of the transportation-related emissions. Within the EU, about 28 % of emissions are due to transportation with about 71 % of which is caused by road transport. This introduces the transportation sector as second biggest polluter after energy industries and the only sector that was not able to reduce its emissions compared to recent years (EU 2012). Unlike these, transportation activities are not currently subject to strict environmental regulations with respect to GHG emissions, although it is highly advisable to consider environmental metrics in distribution decision makings (Fahimnia et al. 2015a).

One possibility to reduce emissions from transportation activities is to improve transport efficiency which can be measured through a vehicle’s average load factor and the amount of empty trips. The improvement of these two measures is very attractive for companies, since both economic and environmental performance can be enhanced at the same time (Edwards and McKinnon 2010).

In this regard, vehicle emissions (CO, HC and NO_x) directly relate to the rate of fuel consumption (FC) (Barth et al. 2005). Routing vehicles for efficient distribution of goods so as to minimize the total FC can be a green logistics initiative. The selection of routes to be travelled by a vehicle is a tactical decision which can easily be implemented for a given network. From a broader perspective, reducing the FC serves the twin goals of improved emissions performance and reduced resource depletion.

Sbihi and Eglese (2007) discussed the impact of logistics activities on the society and presented a review of the combinatorial optimization problems in green logistics (reverse logistics, waste management, and vehicle routing and scheduling). Dekker et al. (2012) described the role of operations research in integrating the environmental aspects with logistical practices. They presented a review of the available methods and possible developments in green logistics. Jensen (1995) analyzed the relationship between travel speeds and emissions on different types of roads. Models to estimate the energy and FC by a vehicle based on operating parameters (such as speed, load and acceleration) and on vehicle parameters are available (Akçelik and Besley 2003; Barth et al. 2005). A comparison of FC models using real-time measurements under different conditions is available in the works of Silva et al. (2006), Demir et al. (2011) and Koç et al. (2014).

There is a considerable amount of ongoing research on the methods to reduce CO₂ emissions. However, observations show that, in many situations, when one factor is improved in a logistics system, the costs of other factors increase accordingly (Savelsbergh and Song 2007). Having inventory management on one side, where the routing aspects of the transportation is not properly treated, and routing on the other, with a number of predefined orders to serve, a natural extension to both problems is to study a combined problem where the key components of both inventory management and routing problems are explicitly incorporated. The integration of the two well-studied problems of inventory management and the Vehicle Routing Problem (VRP) arrives at the so-called Inventory Routing Problem (IRP).

In the inventory side of IRP, it is practical to combine groups of products in a single replenishment order to yield substantial cost savings due to the sharing of fixed replenishment costs. It therefore makes a great deal with resupplying policy of customers over a short or long-term planning period. The literature is quite limited on the ecological aspects of this important research topic with carbon emissions used as the predominant environmental measure.

Benjaafar et al. (2013) incorporated carbon emissions constraints on single and multi-stage lot-sizing models with a cost minimization objective. Four regulatory policy settings are considered, based respectively on a strict carbon cap, a tax on the amount of emissions, the cap-and-trade system and the possibility to invest in carbon offsets to mitigate carbon caps. Insights are derived from an extensive numerical study. In a paper proposing a research agenda for designing environmentally responsible inventory systems, Bonney and Jaber (2011) briefly presented an illustrative model that includes vehicle emissions cost into the economic order quantity (EOQ) model. The authors referred to this model as an “environmental EOQ”. Emissions associated with the storage of products are not taken into account. The order quantity is thus larger than the classical EOQ. Hua et al. (2011) extended the EOQ model to take carbon emissions into account under the cap-and-trade system. Analytical and numerical results are presented and managerial insights are derived. Except Venkat (2007) who did not consider the cost, these papers can be classified as a regulation based integration of sustainable development (or its restriction to carbon footprint) into inventory models.

To the best of our knowledge, the number of researches in “green IRP” area are extremely virginal. In this chapter, we extend a new mathematical modeling framework. A new IRP variant, called the Inventory Pollution-Routing Problem (IPRP) that take emissions pollution from vehicle travels into account.

The two more related works in this context are the studies of Treitl et al. (2012) and Mirzapour Al-e-hashem and Rekik (2014). Treitl et al. (2012) focused on the analysis of transport processes and showed the economic and environmental concerns associated with routing decisions in a supply chain with vertical collaboration. An IRP model was presented and further applied to a case study from the petrochemical industry. Another work is Mirzapour Al-e-hashem and Rekik (2014) who addressed an environmental issue for an IRP model with a transshipment option. This was done by considering the interrelationship between the transportation cost and GHG emissions level. Given the significance of research in this area, our modeling effort in this chapter focuses on presenting an integrated model that incorporates the environmental aspects into a traditional economic-oriented IRP, an early attempt for IPRP modeling and analysis. There are several solution approaches to solving IRPs. We contribute by introducing an exact solution method and exploiting a brand-new decomposition algorithm for the simultaneous inventory management and vehicle routing. Computational results of the performance benchmark exercise confirm the efficiency of the algorithm in terms of the quality of solutions obtained.

2 Problem Description

The way of introducing the IRP model in this chapter is slightly different. It is considered that there are k vehicles of the same capacity under an EOQ policy delivering some goods from a central warehouse to a set of customer nodes N = {1, 2, …, n} in a complete directed graph with arc set Λ where Λ $= \left\{ {\left( {i,j} \right){:}\, i,j \in N,\;i \ne j} \right\}$ Euclidean distance is an arc set which assumed that the underlying distance matrix is symmetric and satisfies the triangle inequalities. At the beginning of the planning horizon, customer i supplied with a delivery quantity Q _i and this process lasts to the end of the period. Each customer i is characterized by a demand D _i , and may not be satisfied in an infinite time horizon which means shortage assumption is permitted. Considering the differentiations in customers’ time periods, the delivery process continues while total demands fulfilled. Similar planning will be projected for the next periods; therefore, restarting each period, there is a routing policy with known delivery quantities. Also it is considered that a limited amount of inventory can be stored at the customer sites as well as the warehouse from which it is delivered; however, transfers between sites are not allowed (Herer et al. 2006). The vehicle working time is made of a set of heterogeneous routes K where each route starts and ends at the warehouse. We assume, without loss of generality, that the routes are served in the order 1, 2, …, k. The warehouse is denoted by 0; the symbol $N^{ + }$ is used for $N \cup 0$ and Λ ⁺ for Λ $= \left\{ {\left( {i,j} \right){:}\, i,j \in N^{ + } ,\;i \ne j} \right\}.$ The goal is to determine an inventory policy and routing strategy such that the long-run costs are minimized to serve all customers while satisfying the capacity constraints.

3 Mathematical Model

Considering the importance of inventory insight, we first launch the problem formulation by specifying the inventory policy, thereafter, continue with contributing the routing, and finally assembling a variant presentation for the IRP. The prevailing mathematical expression tries to capture economic of lot sizing in material purchasing. To make more information available for cost, we model the cost issue linked to logistics and warehousing activities as part of the design objectives rather than as constraints, considering the single product replenishment problem based on the traditional EOQ model and applying a direct accounting approach, and assuming that the product demand is deterministic, the product price is exogenous and the customers decide only the order size. The full average cost of replenishment, we assumed, is expressed by the sum of four terms: holding cost (c _1i ), shortage cost (c _2i ), setup cost (c _3i ), and purchasing cost (c _4i ) that appropriately calculated for customer i.

More specifically, our policy taken, closely resembles to the class of Fixed Partition policies introduced by Bramel and Simchi-Levi (1997) for an IRP in which a single item is distributed among retailers. Although such policies are generally not optimal, they are important from a practical standpoint, as they are easy to implement. In particular, they allow for efficient integration of several business functions. Chan et al. (1998) and Chan and Simchi-Levi (1998) have shown that such policies can be highly effective, by deriving an asymptotic error bound on the obtained solution under different assumptions on the transportation cost structure.

A single vehicle of capacity $\kappa$ is available. This vehicle is able to perform one route at the beginning of each time period to deliver products from the supplier to a subset of customers. A routing cost $c_{ij} d_{ij}$ is associated with arc (i, j). Whereas many distribution systems make use of several vehicles, most research in the field of inventory-routing still considers only one vehicle, and there are indeed practical applications in which a single vehicle is used at a given echelon of the supply chain, such as in the case study described by Mercer and Tao (1996).

3.1 Inventory Definition

Let the amount of stock for ith customer be R _i at time t = 0 (see Fig. 6.1). In the interval $(0,T_{i} ( {=}\, t_{1i} + t_{2i} )),$ the inventory level gradually decreases to meet demands. By this process the inventory level reaches zero level at time t _1i and then shortages S _i are allowed to occur in the interval (t _1i , T _i ). The cycle then repeats itself.

Fig. 6.1

Inventory level of ith customer

The differential equation for the instantaneous inventory q _i (t) at time t in (0, T _i ) is given by

$$\frac{{\partial q_{i} (t)}}{\partial t} = \left\{ {\begin{array}{*{20}l} { - D_{i} ,} \hfill & {0 \le t \le t_{1i} } \hfill \\ { - D_{i} ,} \hfill & {t_{1i} \le t \le T_{i} } \hfill \\ \end{array} } \right.$$

with the initial conditions $q_{i} (0) = R_{i} ( = Q_{i} - S_{i} ),q_{i} \left( {T_{i} } \right) = - S_{i} ,q_{i} \left( {t_{1i} } \right) = 0.$

For each period a fixed amount of shortage is allowed and there is a penalty cost c _2i per items of unsatisfied demand per unit time. From the above differential equation,

$$q_{i} (t) = \left\{ {\begin{array}{*{20}l} {R_{i} - D_{i} t,} \hfill & {0 \le t \le t_{1i} } \hfill \\ {D_{i} (t_{1i} - t),} \hfill & {t_{1i} \le t \le T_{i} } \hfill \\ \end{array} } \right.$$

So, R _i  = D _i  t _1i , S _i  = D _i  t _2i , Q _i  = D _i  t _3i .

Consequently, the holding cost is $c_{1i} \int_{0}^{{t_{1i} }} {q_{i} (t)dt = } ( {c_{1i} (Q_{i} - S_{i} )^{2} /2Q_{i} } )T_{i} ,$ shortage cost is $c_{2i} \int_{{t_{1i} }}^{{T_{i} }} {( - q_{i} (t))dt = ( {c_{2i} S_{i}^{2} /2Q_{i} } )T_{i} }$ and purchasing cost is c _4i Q _i . Therefore, the total cost is $c_{4i} Q_{i} + c_{3i} + c_{1i} ( {(Q_{i} - S_{i} )^{2} /2Q_{i} })T_{i} + c_{2i} ( {S_{i}^{2} /2Q_{i} })T_{i} .$ And the total average cost for ith customer will be $c_{4i} D_{i} + c_{3i} ( {D_{i} /Q_{i} } ) + c_{1i} ( {(Q_{i} - S_{i} )^{2} /2Q_{i} } ) + c_{2i} ( {S_{i}^{2} /2Q_{i} } ).$

3.2 Model for IRP

In the IRP, the total cost to be minimized is mainly the sum of inventory cost at the supplier and of routing cost for the supplier’s vehicle:

$${\text{Min}}\quad \sum\limits_{i \in N} {\left\{ {c_{4i} D_{i} + c_{3i} {\raise0.7ex\hbox{${D_{i} }$} \!\mathord{\left/ {\vphantom {{D_{i} } {Q_{i} }}}\right.\kern-0pt} \!\lower0.7ex\hbox{${Q_{i} }$}} + c_{1i} \frac{{(Q_{i} - S_{i} )^{2} }}{{2Q_{i} }} + c_{2i} \frac{{S_{i}^{2} }}{{2Q_{i} }}} \right\} + \sum\limits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\limits_{r \in K} {c_{ij} d_{ij} x_{ijr} } } }$$

(6.1)

where x _ijr is equal to 1 if and only if customer j immediately follows customer i on the route r of supplier’s vehicle. The objective function (6.1) includes both inventory costs of each customer and as is standard in vehicle routing, travel costs are distance-dependent in which c _ij d _ij denotes the cost of travelling on arc (i, j).

The constraints are as follows.

3.2.1 Routing Constraints

These constraints guarantee that a feasible route is designed to visit all customers served:

• (a) A single vehicle is available: Constraints (6.2) require that only one vehicle can leave from retailer i once. Constraints (6.3) denote that only one vehicle can arrive at retailer j once:

$$\sum\limits_{{j \in N^{ + } }} {\sum\limits_{r \in K} {x_{ijr} = 1} } ,\quad \forall i$$

(6.2)

$$\sum\limits_{i \in N} {\sum\limits_{r \in K} {x_{ijr} = 1} } ,\quad \forall j$$

(6.3)

• (b) Flow conservation constraints: these constraints impose that the number of arcs entering and leaving a vertex should be the same, in other words, for each retailer ℓ, the entering vehicle must eventually leave this node:

$$\sum\limits_{i \in N} {x_{i\ell r} = \sum\limits_{j \in N} {x_{\ell jr} } } ,\quad \forall \ell \in N,r$$

(6.4)

• (c) Constraints (6.5) designate that each vehicle can leave the warehouse once at most:

$$\sum\limits_{j \in N} {x_{0jr} \le 1} ,\quad \forall r$$

(6.5)

• (d) Constraints (6.6) are the vehicle capacity constraints that links two terms of inventory and distribution systems of the model:

$$\sum\limits_{i \in N} {\sum\limits_{j \in N} {Q_{j} x_{ijr} } \le \kappa } ,\quad \forall r$$

(6.6)

• (e) Sub-tour elimination constraints:

$${\varvec{q}}_{j} \ge {\varvec{q}}_{i} - Q_{i} + D_{i} (1 - x_{ijr} ),\quad \forall i,j,r$$

(6.7)

in which it keeps track of the load q _i on the vehicles and guarantees if customer i is the immediate predecessor of customer j on a route, then the load on the vehicle before visiting customer j must be less than or equal to the load just before visiting customer i minus the amount delivered, which is represented by the variable Q _i . Because the load on each vehicle is monotonically decreasing as customers are visited. Constraints (6.7) also provide the added benefit of eliminating sub-tours. Note that it is considered that D _i is large enough.

3.2.2 Integrality and Non-negativity Constraints

$$x_{ijr} \in \left\{ {0,1} \right\},\quad \forall (i,j) \in\Lambda ^{ + } ,r$$

(6.8)

$$0 \le \text{q}_{i} \le \kappa ,\quad \forall i$$

(6.9)

$$0 \le S_{i} \le \bar{S},\quad \forall i$$

(6.10)

$$Q_{i} \ge 0.\quad \forall i$$

(6.11)

Constraints (6.8) designate x _ijr as a 0 − 1 integer variables. After all deliveries are made, the fleet returns to the warehouse empty so q ₀ can be set to 0. To conclude the formulation, variables are defined in Constraints (6.9)–(6.11).

4 Uncertain Modeling

In the real world, after designing a network of facilities, the respective costs, demands, distances, times and other relevant data may change due to uncertain circumstances happening when working in a dynamic and chaotic business environment. For example, in IRPs, with variability in the demand may result in huge and non-measureable costs, such as lost-opportunity and lost-sale costs due to causing unsatisfied customers. Typically, there are two types of modeling techniques for addressing uncertain data, namely, stochastic programming and fuzzy programming.

Therefore, one important consideration is in line with combined inventory management and routing so that there are technical uncertainties due to transportation conditions and equipment, as well as environmental, economical or market uncertainties. In many businesses the market conditions have changed dramatically over the last years with new market opportunities arising continuously. As a result, the demand for products becomes highly uncertain in some business areas. Moreover, most companies are not aware of the possibilities of introducing uncertain elements in the planning. Neither they are familiar nor confident with uncertain planning systems. For recent reviews on the IRP, one can refer to Coelho and Laporte (2013, 2014) and Coelho et al. (2014).

In this regard, demand is widely accepted to be dynamic and stochastic in real life inventory routing problems. Studies on uncertain IRPs also assume full knowledge of the demand data, which may be unavailable or difficult to obtain. There is clearly a need to consider the IRP with demand data in a tractable way, where no information for the probability distribution function (PDF) of demand is required. Nevertheless, in many practical situations, due to lack of historical data for some parameters such as demand, it is hard or even impossible to fit a PDF. In these cases, it is more reasonable to adopt a suitable possibility distribution for each demand based upon the available (but often insufficient) objective data as well as subjective opinions of DMs, or a fully subjective (preference-based) fuzzy set for each judgmental data based upon expert’s subjective knowledge, experience and professional feelings. Though, in both cases, fuzzy programming approaches should be used to cope with such vague uncertainties (Panda et al. 2014). Herein, these variants of IRPs are called IRPs with “hybrid uncertainty” since we are dealing with a mixture of uncertain data (i.e., fuzzy and random data) in our problem. To the best of our knowledge, in IRPs no attempt have been formally made where fuzziness and randomness coexist. Hence, the second objective of this study is to, indeed, deliberating IPRP under uncertainty.

In the following the aim is to extend the formulation into an IRP under hybrid uncertain demand which is also common problem in practice. Doing so, we first refer the readers to Appendix to find the type of uncertainty scheme brought here and its deterministic counterpart formulation.

$$\begin{aligned} & {\text{Min}}\;\left\{ {\sum\limits_{i \in N} {c_{4i} \underline{{\tilde{D}}}_{i} + c_{3i} \left( {\underline{{\tilde{D}}}_{i} /Q_{i} } \right) + c_{1i} \left( {(Q_{i} - S_{i} )^{2} /2Q_{i} } \right) + c_{2i} \left( {S_{i}^{2} /2Q_{i} } \right)} } \right\} + \sum\limits_{{(i,j) \in\Lambda ^{ + } }} {\sum\limits_{r \in K} {c_{ij} d_{ij} x_{ijr} } } \\ & {\text{st}}. \\ \end{aligned}$$

(6.12)

$${\varvec{q}}_{j} \ge {\varvec{q}}_{i} - Q_{i} + \underline{{\tilde{D}}}_{i} (1 - x_{ijr} ),\quad \forall i,j,r$$

(6.13)

(6.2)–(6.6) and (6.8)–(6.11).

Considering the imperfect nature of the demands, the model is converted into its deterministic version. Then by definition of $\underline{{\tilde{D}}}_{i} = \left( {D_{1i} ,D_{2i} ,D_{3i} } \right)\left( + \right)^{\prime } \left( {\mu_{i} ,\sigma_{i}^{2} } \right),\forall i,$ and following the mathematical theory of hybrid numbers described in Appendix the objective function (6.12) and constraints (6.13) extend to:

$$\begin{aligned} & {\text{Min}}\;TC = E\tilde{T}C( + )^{\prime}(0, VTC) \\ & {\text{st}}. \\ \end{aligned}$$

(6.14)

$$E\left( {{\varvec{q}}_{j} - {\varvec{q}}_{i} + Q_{i} - \underline{{\tilde{D}}}_{i} (1 - x_{ijr} )} \right) \ge 0,\quad \forall i,j,r$$

(6.15)

$$V\left( {{\varvec{q}}_{j} - {\varvec{q}}_{i} + Q_{i} - \underline{{\tilde{D}}}_{i} (1 - x_{ijr} )} \right) \ge 0,\quad \forall i,j,r$$

(6.16)

(6.2)–(6.6) and (6.8)–(6.11),

where E(·) and V(·) are mean and variance operators, respectively. On the other hand, $E\tilde{T}C = \left( {ETC_{1} ,ETC_{2} ,ETC_{3} } \right)$ with $ETC_{m} = \sum\nolimits_{i\in N} \{ {c_{4i} ( {D_{mi} + \mu_{i} } ) + c_{3i} ( {( {D_{mi} + \mu_{i} } )/Q_{i} } ) + c_{1i} ( {( {Q_{i} - S_{i} } )^{2} /2Q_{i} } ) + c_{2i} ( {( {S_{i} } )^{2} /2Q_{i} } )} \},\;\forall m \in \{ {1,2,3} \}.$ So the approximated value of $E\tilde{T}C$ is $E \hat{T} C = \raise.5ex\hbox{$\scriptstyle 1$}\kern-.1em/ \kern-.15em\lower.25ex\hbox{$\scriptstyle 4$} ( {ETC_{1} + \, 2ETC_{2} + ETC_{3} } ) = \sum_{i \in N} \{ {c_{4i} ( {\hat{D}_{i} + \mu_{i} } ) + c_{3i} ( {( {\hat{D}_{i} + \mu_{i} } )/Q_{i} } ) + c_{1i} ( {( {Q_{i} - S_{i} } )^{2} /2Q_{i} } ) + c_{2i} ( {( {S_{i} } )^{2} /2Q_{i} } )} \}\,{\text{if}}\,\hat{D}_{i} = \raise.5ex\hbox{$\scriptstyle 1$}\kern-.1em/ \kern-.15em\lower.25ex\hbox{$\scriptstyle 4$} ( {D_{1i} + D_{2i} + D_{3i} + D_{4i} } ).$

Hence, Constraints (6.12) and (6.13) is reduced to a “bi-objective mixed integer nonlinear program” as follow:

$$\begin{aligned} & {\text{Min}}\;\left\{ {AETC,VTC} \right\} \\ & {\text{st}}. \\ \end{aligned}$$

(6.17)

$${\varvec{q}}_{j} \ge {\varvec{q}}_{i} - Q_{i} + \hat{D}_{i} (1 - x_{ijr} ),\quad \forall i,j,r$$

(6.18)

$$\sigma_{i}^{2} (1 - x_{ijr} )^{2} \ge 0,\quad \forall i,j,r$$

(6.19)

(6.2)–(6.6) and (6.8)–(6.11),

where $AETC = E\hat{T}C + \sum\nolimits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\nolimits_{r \in K} {c_{ij} d_{ij} x_{ijr} } } ,$ and $VTC = \sum\nolimits_{i \in N} {\left\{ {c_{4i}^{2} \sigma_{i}^{2} + c_{3i}^{2} ({{\sigma_{i}^{2} } \mathord{\left/ {\vphantom {{\sigma_{i}^{2} } {Q_{i}^{2} )}}} \right. \kern-0pt} {Q_{i}^{2} )}}} \right\}} .$ As seen, from (6.8), Constraints (6.19) is evident, so it will be omitted from the rest of our computations.

5 Integrating Ecological Issues

The way of considering ecological issues in routing problem is rather interesting. We present fundamental ideas to enrich VRPs by green aspects in the following. Several ecologically oriented extensions of the VRP have been introduced which aim at minimizing the fuel consumption or the amount of CO₂ emission. In any of these problems, the evaluation of transportation plans relies on an estimation of the quantity of fuel consumed for request fulfillment. There exists a variety of methods for estimating fuel consumption and emissions of road transportation in dependence of a bunch of parameters. Most of the estimation methods are based on analytical emissions models. The methods found in the literature differ in the assumed basic principles and with respect to the parameters they take into account for estimation. A comparison of several vehicle emission models for road freight transportation can be found in Demir et al. (2011). In addition to comparing different methods for estimating fuel consumption and pollution, Demir et al. (2011) analyze the discrepancies between the results yielded by the models on the one hand and the results of measurements of on-road consumptions of real vehicles on the other hand. For other relevant references and a state-of-the-art coverage on green road freight transportation, the reader is referred to the survey of Lin et al. (2014) and Demir et al. (2014). In this chapter, we follow the idea of chose by Bektaş and Laporte (2011).

5.1 Model to Estimate Fuel Consumption

The comprehensive modal emission model developed by Barth et al. (2005), Barth and Boriboonsomsin (2009) for diesel engines gives a good estimate of the vehicular emissions (Bektaş and Laporte 2011; Demir et al. 2011); it considers the speed, load carried and other vehicle parameters. They relate the tail-pipe emissions e directly to the fuel use rate F as e = ϐ ₁ F + ϐ ₂ (Bektaş and Laporte 2011) where ϐ ₁ and ϐ ₂ are GHG emissions index parameters.

The expression for the instantaneous fuel consumption or fuel use rate F mL/s for a diesel engine with displacement φ L is given as follows Barth and Boriboonsomsin (2009) and Barth et al. (2005):

$$F \approx \psi {\kern 1pt} \left( {Es\varphi + \frac{P}{\eta }} \right)$$

(6.20)

where $\psi = \left( {1/0.85} \right) \cdot \left( {1/43.2} \right) \cdot (1 + b_{1} (s - s_{0} )^{2} ),E = E_{0} (1 + c(s - s_{0} ))$ is the engine friction factor, and s the engine speed (revolutions/s), P the total engine power requirement (watt), η the efficiency of diesel engine, E ₀ the engine friction factor when the vehicle is idle, s ₀ ≈ 30 (3/ϕ)^½, c ≈ 0.00125 and b ₁ ≈ 10⁻⁴ are constant coefficients, 43.2 kJ/g the lower heating value of diesel and 0.85 kg/L the density of diesel. The engine power requirement P for a vehicle with drive-train efficiency ϑ is expressed as

$$P = \frac{{P_{tract} }}{\vartheta } + P_{acc}$$

(6.21)

P _acc accounts for the power required by the vehicle air conditioner and other accessories.

The tractive power required P _tract (watt) by the vehicle to carry a weight M (including the load to be carried) can be determined from the following expression (Barth and Boriboonsomsin 2009; Bektaş and Laporte 2011):

$$P_{tract} = M\left( {a + g\,\sin \theta + g\,C^{roll} \cos \,\theta } \right)v + 0.5A\,\rho C_{d} {\kern 1pt} v^{3}$$

(6.22)

where v m/s is the velocity of the vehicle, θ the road angle (degree), A (m²) the frontal surface area of the vehicle, ρ (kg/m³) the air density, a (m/s²) the acceleration of the vehicle, g (m/s²) the acceleration due to gravity, C ^roll the coefficient of rolling resistance and C _d the coefficient of aerodynamic drag.

The expression for the fuel use rate (F) provides the estimate of the fuel consumption (FC) by a vehicle on travelling a route.

5.2 Factors Affecting Fuel Consumption

If the velocity v and other parameters of a vehicle remain constant, the FC by a vehicle travelling and distance d can be estimated from the fuel use rate F as follows:

$${\mathbf{FC}} \approx F\left( \frac{d}{v} \right)$$

(6.23)

The FC by a vehicle in a trip is proportional to the distance travelled and the load carried. The FC on an arc depends on the load carried and varies according to the sequence of nodes to be visited. The FC by an empty truck depends on its curb weight (Barth and Boriboonsomsin 2009; Barth et al. 2005; Bektaş and Laporte 2011). For the sake of uniformity of scale, we also take the load to be carried in units of weight (kg in this study).

The product of η and ϑ is inversely proportional to the FC. Thus, choosing a vehicle with higher values of engine and drive-train efficiencies will result in better fuel economy. The FC is fairly low for moderate speeds (35–45 km/h) and high for very low and very high speeds. Variations in driving speeds contribute significantly to the FC and emissions than driving at a steady speed (Tong et al. 2000). A driver who maintains a constant speed and drives within a moderate speed range will help to reduce the consumption of fuel. In general, the average speed of travel in an arc is assumed (Bektaş and Laporte 2011; Suzuki 2011) for modeling purposes. The most likely average speed with which a vehicle can travel can be predicted using historical and real-time data (Rice and Van Zwet 2004).

The parameters θ and C ^roll, which are entirely dependent on the nature of the road, are very sensitive and play a dominant role in the FC by the vehicle. C _d depends on climatic conditions and is a measure of the drag force exerted on the vehicle due to air resistance. Apart from these parameters, the velocity of travel also depends on the nature of the road and other road conditions. Hence, alternative routes have to be considered for distribution planning to determine the velocity and the road to be travelled in order to reduce the fuel consumption. Table 6.1 offers a description of all the parameters.

Table 6.1 Parameters used in the computational experiments

5.3 Nature of Alternative Routes

A variety of alternative routes can exist between a pair of nodes and each route is taken as a distinct arc connecting the two nodes. If each lane of a highway is considered as an alternative route, the length is the same but the velocity is different. Another possibility is the existence of multiple routes with different lengths and different average velocities. The availability of multiple routes between two nodes can be observed in countries which rely heavily on road transport for freight movement. The average velocity along each route can be determined based on the condition of the road, past data etc. The nature of the routes is illustrated in Fig. 6.2. It shows a U-shape curve between FC and speed, which is consistent with the behavior of functions suggested by other authors (e.g., Demir et al. 2011), confirming that low speeds (as in the case of traffic congestion) lead to very high fuel use rate.

Fig. 6.2

Fuel consumption as a function of speed, as estimated by function (6.23)

5.4 Fuel Emissions Factors

Let

$$\alpha_{ij} = a + g{\kern 1pt} \,\sin \theta_{ij} {\kern 1pt} + g\,C_{ij}^{roll} \cos \theta_{ij}$$

(6.24)

$$\beta = 0.5\,A\,\rho \,C_{d}$$

(6.25)

Using (6.26), the fuel use rate given in (6.27) can be written as follows:

$$P_{tract} = \alpha_{ij} \,w{\kern 1pt} \,v_{ijr} + \alpha_{ij} \,{\varvec{q}}_{i} \,v_{ijr} + \beta \,v_{ijr}^{3}$$

(6.26)

$$F_{ijr} \approx \psi_{ij} \left( {E_{ij} s_{ij} \phi + \frac{1}{\vartheta \eta }(\alpha_{ij} {\kern 1pt} w{\kern 1pt} {\kern 1pt} v_{ijr} {\kern 1pt} + \alpha_{ij} {\kern 1pt} {\varvec{q}}_{i} {\kern 1pt} v_{ijr} {\kern 1pt} + \beta {\kern 1pt} {\kern 1pt} v_{ijr}^{3} ) + \frac{{P_{acc} }}{\eta }} \right)$$

(6.27)

Assuming that the velocity and other parameters of a vehicle remain constant on a route, the fuel consumed FC _ijr  mL by a vehicle travelling from node i to node j along route r can be estimated from the fuel use rate F _ijr as follow:

$${\mathbf{FC}}_{ijr} \approx F_{ijr} {\kern 1pt} \left( {\frac{{d_{ij} }}{{v_{ijr} }}} \right)$$

(6.28)

where d _ij /v _ijr is the time taken to travel the route.

As perceived from above, the ecologically speaking purpose concerns with consumption of fuel, is based on parameters relating to vehicles, load, speed, distances and road conditions. Substituting (6.27) in (6.28) and rearranging the terms and considering that economic benefits strongly influence decision-making in most businesses. However, unlike same-topic-papers, the “speed” is considered as a decision variable and establish its relevant necessary constraint. Given this, we refer to this problem as “Pollution-Routing Problem” (PRP).

5.5 Model Formulation for IPRP

The proposed “mixed integer nonlinear program” is very difficult to solve. Thus we decompose the decision variables {Q _i , S _i , x _ijr , q _i , v _ijr } into two groups: {Q _i , S _i } and {x _ijr , q _i , v _ijr }. The first group is associated with the inventory problem and the second group is subject to the routing problem.

With the concept of decomposition, Constraints (6.12) and (6.13) schematically, rearranged with the following bi-level structure:

• Upper level:

$$\left\{ {\begin{array}{*{20}l} {\mathop {\text{Min}}\limits_{{\left\{ {Q_{i} ,S_{i} } \right\} \in\Omega _{1} }} } \hfill & {Z_{1} = E\hat{T}C + Z_{PRP} } \hfill \\ {\mathop {\text{Min}}\limits_{{\left\{ {Q_{i} ,S_{i} } \right\} \in\Omega _{1} }} } \hfill & {Z_{2} = \sum\limits_{i \in N} {\left( {c_{4i}^{2} \sigma_{i}^{2} + c_{3i}^{2} \frac{{\sigma_{i}^{2} }}{{Q_{i}^{2} }}} \right)} } \hfill \\ \end{array} } \right.$$

(6.29)

where Ω₁ is the feasible region represented by non-negative Constraints (6.19) and (6.20) in which Z _PRP is the VRP’s objective function including green issue. Accordingly, the Z _PRP is calculated as follows:

• Lower level:

$$\left\{ {\begin{array}{*{20}l} {\mathop {\text{Min}}\limits_{{\{ x_{ijr} ,\varvec{q}_{i} ,v_{ijr} \} \in {\Omega}_{2} }} \;Z_{PRP} = \left( \begin{aligned} & \sum\limits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\limits_{r \in K} {\psi_{ij} d_{ij} \left( {E_{ij} s_{ij} \phi + \frac{{\alpha_{ij} {\kern 1pt} w}}{\vartheta \eta }} \right)} } {\kern 1pt} {\kern 1pt} C_{fuel} x_{ijr} \\ + & \sum\limits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\limits_{r \in K} {\psi_{ij} d_{ij} {\kern 1pt} \left( {{{\alpha_{ijr} } \mathord{\left/ {\vphantom {{\alpha_{ijr} } {\vartheta \eta }}} \right. \kern-0pt} {\vartheta \eta }}} \right){\kern 1pt} {\kern 1pt} C_{fuel} {\kern 1pt} \varvec{q}_{i} } } \\ + & \sum\limits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\limits_{r \in K} {\psi_{ij} d_{ij} \left( {{\beta \mathord{\left/ {\vphantom {\beta {\vartheta \eta }}} \right. \kern-0pt} {\vartheta \eta }}} \right){\kern 1pt} {\kern 1pt} C_{fuel} {\kern 1pt} v_{ijr}^{2} } } {\kern 1pt} x_{ijr} \\ \end{aligned} \right)} \hfill \\ {\text{st}\text{.}} \hfill \\ {\underline{v}_{ijr} x_{ijr} \le v_{ijr} \le \bar{v}_{ijr} x_{ijr} ,\quad \forall i,j,r} \hfill \\ \end{array} } \right.$$

(6.30)

where Ω₂ represents Constraints (6.2)–(6.6), (6.8) and (6.18) with {Q _i , S _i } given. As seen, Constraints (6.6) incurs a nonlinear solution set for problem (6.30). By the decomposition technique that has been carried out here, Z ₁ and Z ₂ solve Q _i and perform Ω₂ to transform into a linear feasible region for problem (6.30).

In the lower level, the objective function is derived from (6.28) and contains three components. The first two, measure the cost comprised by the load carried on the vehicle (including curb weight). Finally, the last component measures the cost implied by variations in speed. All of these three components translate directly into total cost of FC and GHG emissions calculated by the unit cost C _fuel multiplied by the total amount of fuel consumed over each link (i, j) ∈ Λ ⁺.

Constraint $\underline{v}_{ijr} x_{ijr} \le v_{ijr} \le \bar{v}_{ijr} x_{ijr} ,\;\forall i,j,r$ links the green strategy and routing plan, aiming at Greening the Routes. In other words, the adjunct constraint guarantee that if arc (i, j) is traversed on route r, service at node j will be started under limit of lower and upper bounds of vehicle speed; otherwise no value kept for constraint satisfaction if arc (i, j) is not traversed.

If a given {Q _i , S _i } causes problem (6.30) to be in feasible, simply let Z _PRP equal infinity. Note that, since by definition, x _ijr could be either 0 or 1, once it takes 0, then automatically v _ijr becomes 0, and when it takes 1, then v _ijr will be permitted to designate a value among $\underline{v}_{ijr}$ and $\bar{v}_{ijr},$ thus x _ijr could be easily dropped from the last term of the objective function (6.30), and relaxed to $\sum\nolimits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\nolimits_{r \in K} {\psi_{ij} d_{ij} ( \cdot )C_{fule} v_{ijr}^{2} } } .$

The Constraints (6.12) and (6.13) is now converted into a “bi-level bi-objective mixed integer nonlinear program” problems (6.29) and (6.30) with convex solution region.

6 Solution Approach

Problem (6.29) itself can be solved using either a sensitivity-analysis based or a direct search algorithm. The former uses sensitivity analysis to obtain the derivative information of the reaction function (either explicitly or implicitly) while the latter employs only functional evaluations. Since the interdependence between delivery quantity and shortage variables {Q _i , S _i } and vehicle routes {x _ijr , q _i , v _ijr } are too complicated and the derivative information is not available in this problem, we adopted a direct search algorithm to solve the problem. One of the most widely used direct search methods for solving nonlinear unconstrained optimization problems is the Nelder–Mead simplex algorithm (see Nelder and Mead 1965).

In the next two subsections, the Nelder–Mead method with boundary constraints is adopted to solve the upper level inventory problem (6.29) and a plenary exact heuristic algorithm is proposed to solve the lower level the PRP (6.30).

6.1 Solving the Multiobjective Inventory Problem

A “simplex” is a geometrical figure consisting, in n-dimensions, of (n + 1) points y ⁰; …; y ⁿ (Nelder and Mead 1965)¹. If any point of a simplex is taken as the origin, the n other points define vector directions that span the n-dimension vector space.

If we randomly draw as initial starting point y ⁰, then we generate the other n points y ⁱ according to the relation y ⁱ = y ⁰ + λ y ⁰ I _i , where the I _i are n unit vectors, and λ is a turbulence factor which is which is typically equal to one (but may be adapted to the problem characteristics).

Through a sequence of elementary geometric transformations (reflection, contraction, expansion and multi-contraction; internal/external), the initial simplex y ⁰ moves, expands or contracts. To select the appropriate transformation, the method only uses the values of the function to be optimized at the vertices of the simplex considered. After each transformation, the current worst vertex is replaced by a better one. Trial moves shown on Fig. 6.3 are generated according to the following basic operations (where $\hat{y}$ called center of gravity and defined by $\hat{y} = \left( {\Sigma_{i} y_{i} } \right)/n,$ and α, β, γ are constants):

Fig. 6.3

Available moves in the Nelder–Mead simplex method, in the case of 3 variables

• reflection: $y^{r} = \hat{y} +\varvec{\alpha}\left( {\hat{y} - y^{n} } \right)$

• expansion: $y^{e} = \hat{y} +\varvec{\beta}\left( {y^{r} - \hat{y}} \right)$

• internal contraction: $y^{c} = \hat{y} +\varvec{\gamma}\left( {y^{n} - \hat{y}} \right)$

• external contraction: ${\mathop y\limits^{\prime}}{^{c}}= \hat{y} + {\varvec{\gamma}} \left( {y^{r} - \hat{y}} \right)$

At the beginning of the algorithm, one moves only the point of the simplex, where the objective function is worst (this point is called “high”), and one generates another point image of the worst point. This operation is the reflection. If the reflected point is better than all other points, the method expands the simplex in this direction; otherwise, if it is at least better than the worst one, the algorithm performs again the reflection with the new worst point. The contraction step is performed when the worst point is at least as good as the reflected point, in such a way that the simplex adapts itself to the function landscape and finally surrounds the optimum. If the worst point is better than the contracted point, the multi-contraction is performed. For each rejected contraction step, we replace all y ⁱ of the simplex by ½(y ⁱ + y ¹) (y ^l is the vertex of the simplex where the objective function is “low”); thus we obtain the multi-contraction (internal/external) of the simplex, and the process restarts.

The stopping criterion is a measure of how far the simplex was moved from one iteration h to the following one (h + 1). The algorithm stops when:

$$\frac{1}{n}\sum\limits_{i = 1}^{n} {\left\| {y_{i}^{h} - y_{i}^{h + 1} } \right\|^{2} } < \varepsilon ,$$

(6.31)

where y ^h+‏1 is the vertex replacing y ^h at the iteration (h + 1), and ε is a given “small” positive real number.

Because the Nelder–Mead method (NM) is originally applied to an unconstrained problem, an adjustment is necessary that projects its coordinates on the bounds if the new point is out of the domain. However, since the inventory part of the problem is of multiobjective form, it also needs a preparation step before the adjustment.

We start the preparation with a topic of normalized normal constraint method (NNCM; Messac et al. 2003). This method normalizes the design space and introduces new constraints. Considering the new constraints, optimization of only one of the objectives returns a non-dominated solution. When several of these single-objective optimization problems are solved, several non-dominated solutions are obtained. The difference between this method and varying user preferences in a non-generating method is that here the set of constraints are introduced to spread the final solutions uniformly in the criterion space. NNCM is an algorithm for generating a set of evenly spaced solutions on a pareto-frontier (Messac et al. 2003). This method yields pareto-optimal solutions, and its performance is independent of the scale of the objective functions. NNCM method and some related definitions are presented in this section.

Definition 1

(utopia point) Considering a multiobjective optimization problem, a point ₣ ^o ∈ ω in the criterion space (ω) is called a utopia point if and only if:

$$f_{i}^{o} = \hbox{min} \left\{ {f_{i} (y)\left| {y \in \zeta } \right.} \right\},\quad \forall i$$

(6.32)

where ζ ⊂ Rⁿ is the feasible region in the design space. Because of contradicting objectives, the utopia point is unattainable.

Definition 2

(anchor point) A non-dominated point ₣ ^o ∈ ω is an anchor point if and only if it is pareto-optimal and at least for one $i, \,f_{i}^{**} = \min_{y} \{ f_{i} (y)|y \in \zeta \} .$

The first step in NNCM is to normalize the design space. For this purpose, the utopia and the anchor points are required. These points are found by optimizing only one of the objectives at a time. After finding these points, the criterion space is normalized using the following transformation.

$$\bar{f}_{i} = \frac{{f_{i} - f_{i}^{o} }}{{f_{i}^{\hbox{max} } - f_{i}^{o} }}$$

(6.33)

$$f_{i}^{\hbox{max} } = \hbox{max} \left\{ {f_{i} (y);y \notin Y^{*} } \right\}$$

(6.34)

where Y ^* is All pareto-optimal points in the design space.

The normalization process locates the utopia point at the origin and the anchor points at the unit coordinates. Figure 6.4a shows the original criterion space and the pareto-frontier of a generic bi-objective problem. Figure 6.4b represents the pareto-frontier of the same problem after normalization. The next step is to form the utopia hyperplane, which is a hyperplane with vertices located at the anchor points. For a bi-objective problem, the utopia hyperplane is a line as shown in Fig. 6.4c. Next, a grid of evenly distributed points on the utopia hyperplane is generated. The number of points in this grid is defined by the user. Figure 6.4c shows, for example, a grid of six points on the utopia line. If these points are projected onto the pareto-frontier, several pareto-optimum solutions are obtained. To find the pareto-optimum solution corresponding to each point in this grid, a single-objective optimization problem must be solved. This problem entails minimizing one of the normalized objectives with an additional inequality constraint. For example, the pareto-optimum solution corresponding to point P in Fig. 6.4c can be found by minimizing $\bar{f}_{ 2}$ while the feasible region is cut by the line passing through this point and perpendicular to the utopia line. The feasible region of this single-objective optimization problem is shown in Fig. 6.4c. The solution of this problem, $\bar{f}^{*} ,$ is a pareto-optimum solution for the original multiobjective problem. Other pareto-optimal points can be found by repeating the same procedure for other points on the utopia line.

Fig. 6.4

a A typical bi-criterion space, b normalized criterion space, c a normal constraint introduced by NNCM and the feasible region of the resulted single-objective problem (min $\bar{f}_{ 2}$)

If the objective functions have local optima, it is possible to have some dominated solutions among the final solutions. Model (6.29) has local optima; therefore, dominated solutions are expected.

In order to find each pareto-optimum solution, NNCM requires solving a single-objective optimization problem. Since this algorithm is proposed for solving model (6.29), in which the gradients of the objectives are not available; a direct optimization method is required. On the other hand, considering the time consuming analysis of the model, an evolutionary algorithm may not be a good choice due to the low rate of convergence. Hence, integrating with Nelder–Mead simplex algorithm would be an appropriate choice we implement here. We now proceed to formally state the Algorithm 1, as follows:

Algorithm 1

NM

• 1 Initialization

  • 1.1 Find an initial solution {Q _i , S _i } (designated as y ⁰) of (6.29) as follows, and solve corresponding VRP (6.30) considering NNCM. The initial delivery quantity Q _i is usually set as the mean value of the demand quantity with the initial shortage value (S _i ) of zero. Calculate the value of objective function (6.29).

  • 1.2 Determine other vertices y ¹, …, y ⁿ of the initial simplex by disturbing y ⁰ as follows: y ⁱ = y ⁰ + λ y ⁰ I _i , ∀i where λ is a turbulence factor and I _i is a unit base vector. Project its coordinates on the bounds, if y ⁱ is out of the domain. Solve the corresponding VRP (6.30) and calculate the value of objective function (6.29), respectively.

• 2 Identify the vertices with the highest function value as y ^u, the vertices with the lowest function value as y ^l, the vertices with the second lowest function value as $\hat{y} ,$ the center of gravity of the simplex (without y ^l), and the corresponding objective function values as Z(y ^u), Z(y ^l), Z($\hat{y}$); where Z is the combined objective functions Z ₁, Z ₂ calculated by NNCM.

• 3 Apply a reflection with respect to y ^l: y ^r = $\hat{y}$ + α($\hat{y} - y^{l}$) and project its coordinates on the bounds, if y ^r is out of the domain.

• 4 Update the simplex. We distinguish between three cases:

  • (a) If Z(y ^r) > Z(y ^u), it means that the reflection created a better solution. We attempt to get an even better point through expansion of y ^r: y ^e = $\hat{y}$ + β($y^{r} - \hat{y}$). Project its coordinates on the bounds, if necessary. Replace y ^l with y ^e if Z(y ^e) > Z(y ^r); otherwise, replace y ^l with y ^r.

  • (b) If Z(y ^r) ≥ Z($\hat{y}$), replace y ^l with y ^r.

  • (c) If Z(y ^r) ≤ Z(y ^l), it was probably wrong to do the reflection along that direction. An internal contraction from y ^l in direction $\hat{y} - y^{l}$ will be applied:

  y ^c = $\hat{y} +\varvec{\gamma}\left( {y^{l} - \hat{y}} \right) ,$ project its coordinates on the bounds, if necessary. Else, if Z(y ^l) < Z(y ^r) < Z($\hat{y}$), the selected direction may be right. However, since all vertices except y ^l are better than y ^r, it can be concluded to go closer to the simplex again. An external contraction from y ^r will be applied:

  ${\mathop y\limits^{\prime}}{^{c}}= \hat{y} + \gamma \left( {y^{r} - \hat{y}} \right),$ project its coordinates on the bounds, if necessary. After the internal or external contraction, if Z(y ^c) > Z(y ^l) (or if Z(${\mathop y\limits^{\prime}}{^{c}}$) > Z(y ^l)), replace y ^l with y ^c (or ${\mathop y\limits^{\prime}}{^{c}}$). Otherwise, a total contraction is performed since all attempts to get improvement failed; y ⁱ = y ^u + γ (y ⁱ − y ^u) ∀i ≠ u

• 5 Check convergence. If the distance between y ^u and any other vertices is smaller than a certain tolerance, then stop; y ^u and its corresponding vehicle route is the best solution. Otherwise, go to 2. Another choice of stopping criterion which is more applicable, according to (6.31), is the difference of Z(y ^u) − Z(y ^l) less than a preset tolerance.

6.2 Solving the PRP

6.2.1 The Proposed Method

When addressing convex MINLPs, two of the classical methods available in the literature are Generalized Benders Decomposition (GBD) (Geoffrion 1972) and the Outer-Approximation (OA) algorithm (Duran and Grossmann 1986; Fletcher and Leyfer 1994). Both methods are iterative coordination techniques that cycle between the solutions of a relaxed master problem (RMP) and of a sub-problem (SP). While the former, a mixed integer program (MIP), provides lower bounds for the optimal solution, the latter, a linear problem (LP), allows the generation of violated cuts that enrich the RMP at each iteration.

As proved by Duran and Grossman (1986), the lower bounds obtained by the OA method are greater or equal to the ones attained by the GBD, implying, hence, in less iterations for convergence. However, these bounds are provided at the cost of an RMP with a number of variables and constraints larger than the RMP of the GBD. Consequently, the largest instance size that the OA technique is able to tackle, is smaller than the largest of the GBD.

Nevertheless, on MINLPs, whenever a model can be reformulated by separating the nonlinear from the large-scale part via the addition of a family of variables, a hybrid strategy can be efficiently used.

Moreover, the reformulation suggests two possibilities: on one hand, the solution of the entire problem can be done by means of GBD, by projecting out all the non-complicating variables—the large-scale system and the additional variables. On the other hand, the solution can be achieved by means of an RMP that has the complicating and the additional variables—similar to the OA’s RMP.

The latter separation represents a great advantage since it allows the parallel solution of the SPs of the OA and BD methods, and hence the addition of both cuts to the RMP. Further, assuming that the required number of additional variables is much smaller than the number of variables of the large-scale system, using the RMP having the complicating and the additional variables may reduce the computational effort when compared to the standard application of OA or GBD. This enhancement is due to the combined effect of having improved lower bounds and a reduced solution overhead of the RMP.

Therefore, despite the chosen sequence of presentation of this article, it is indifferent to think on solving the OA’s RMP by BD or on tackling the RMP of the BD by OA, when the MINLP can be reformulated by separating the nonlinear from the large-scale part via the addition of a family of variables.

The OA method is a simple but effective technique based on a cutting plane approach for solving MINLP (Duran and Grossmann 1986; Fletcher and Leyfer 1994). A general survey of the technique can be found at Grossmann and Kravanja (1995). The method is a coordination technique between an MP and a SP, as aforementioned.

In order to understand the development of the OA technique for the VRP, a general overview of the method is required. Given an MINLP in its most basic algebraic representation, where x and y are the sets of continuous and discrete variables, respectively, $f{:} \, {\text{R}}^{n \times q} \to {\text{R}}$ and $g{:}\,{\text{R}}^{n \times q} \to {\text{R}}^{m}$ are two continuously differentiable functions, and X and Y are polyhedral sets:

$$({\text{ONP}})\left\{ {\begin{array}{*{20}l} {{\text{Min}}\;f(x,y)} \hfill \\ {{\text{st}}.} \hfill \\ {g_{j} (x,y) \le 0,\quad \forall j} \hfill \\ {y \in \varvec{Y},\quad y \in \text{Z}^{q} } \hfill \\ {x \in \varvec{X}.} \hfill \\ \end{array} } \right.$$

It is possible to reduce this problem to a pure nonlinear program (ONP) by choosing a fixed vector y = y ^h, y ^h ∈ Y, for some iteration h, yielding the following nonlinear NSP:

$$(\text{NSP})\left\{ {\begin{array}{*{20}l} {\text{Min}\;f(x,y^{h} )} \hfill \\ {\text{st}.} \hfill \\ {g_{j} (x,y^{h} ) \le 0,\quad \forall j} \hfill \\ {x \in \varvec{X}.} \hfill \\ \end{array} } \right.$$

When solved, the above NSP permits to infer the gradient of the functions f (x, y) and g _j (x, y), ∀j at (x ^h, y ^h). If no further feasibility constraints are required, then a straightforward manipulation enables the ONP to be equivalent to an MIP:

$$(\text{OLP})\left\{ {\begin{array}{*{20}l} {\text{Min}\;\;\xi } \hfill \\ {\text{st}.} \hfill \\ {f(x^{h} ,y^{h} ) + \nabla f(x^{h} ,y^{h} )^{T} \left( \begin{aligned} x - x^{h} \hfill \\ y - y^{h} \hfill \\ \end{aligned} \right) \le \xi ,\quad \forall h} \hfill \\ {g(x^{h} ,y^{h} ) + \nabla g(x^{h} ,y^{h} )^{T} \left( \begin{aligned} x - x^{h} \hfill \\ y - y^{h} \hfill \\ \end{aligned} \right) \le 0,\quad \forall h} \hfill \\ {y \in \varvec{Y},\quad y \in \text{Z}^{q} } \hfill \\ {x \in \varvec{X}} \hfill \\ {\xi \ge \text{0}\text{.}} \hfill \\ \end{array} } \right.$$

Problem OLP is known as the OA’s MP. The two first constraints are responsible for performing the OA of the objective function and the feasible region, respectively. When functions g(x, y) are proper convex and a constraint qualification holds for every solution of NSP, then the second constraints are necessary and sufficient to outer approximate the feasible region.

In the case of model (6.30), the objective function is separable on the linear and nonlinear terms. Then, before applying OA, we should prove that the continuous relaxation of the objective function is convex in order to assure optimality and applicability of the OA approach. Lemma establishes this property.

Lemma

The objective function of model ( 6.30 ) is convex.

Proof

By linearity, it suffices to show that the nonlinear term is convex. Let us first expand the function then for all v _ijr we have:

$$f_{ijr} (v_{ijr} ) = \psi_{ij} d_{ij} (\beta /\vartheta \eta )C_{fuel} {\kern 1pt} v_{ijr}^{2}$$

If f(v) has a second derivative in [${\underline{v}} ,\bar{v}$], then a necessary and sufficient condition for it to be convex on is that the second derivative ${{\partial^{2} f(v)} \mathord{\left/ {\vphantom {{\partial^{2} f(v)} {\partial v^{2} }}} \right. \kern-0pt} {\partial v^{2} }} \ge 0$ for all v in [${\underline{v}} ,{\bar{v}}$].

$$\begin{aligned} \frac{{\partial f_{ijr} (v_{ijr} )}}{{\partial v_{ijr} }} & = 2\psi_{ij} d_{ij} \left( {\beta /\vartheta \eta } \right)C_{fuel} v_{ijr} \\ \Rightarrow \frac{{\partial^{2} f_{ijr} (v_{ijr} )}}{{\partial v_{ijr}^{2} }} & = 2\psi_{ij} d_{ij} \left( {\beta /\vartheta \eta } \right)C_{fuel} \ge 0. \\ \end{aligned}$$

This establishes the convexity of this function, completing the proof.

Given values for the integer decision variables, the OA’s SP finds the optimal value for the continuous variables, providing a feasible point in order to approximate the nonlinear objective function (6.30). In OA algorithm, the SP is typically the algorithmic bottleneck because it requires solving an NLP at each iteration.

We can build the OA’s MP provided that the optimal values for variables $\hat{x}^{h} ,{\hat{\mathbf{q}}}_{i}$ and $\hat{v}^{h}$ at every iteration h is available. The following proposition shows how the linear approximations of the objective function (6.30) is calculated.

Proposition

If $\hat{v}^{h}$ is an optimal solution for the nonlinear of the OA’s SP algorithm at iteration h, there exists a valid linear OA cut for the objective function ( 6.30 ).

Proof

From Lemma, f(v) is convex. Given a feasible assignment point of $\hat{v}^{h}$ at iteration h for ONP, by convexity of f(v) we again set

$$f_{ijr} (v_{ijr} ) = \psi_{ij} d_{ij} \left( {{\beta \mathord{\left/ {\vphantom {\beta {\vartheta \eta }}} \right. \kern-0pt} {\vartheta \eta }}} \right){\kern 1pt} {\kern 1pt} C_{fuel} {\kern 1pt} v_{ijr}^{2} ,$$

then, the linear approximation provides

$$\psi_{ij} d_{ij} ({\beta \mathord{\left/ {\vphantom {\beta {\vartheta \eta }}} \right. \kern-0pt} {\vartheta \eta }}){\kern 1pt} {\kern 1pt} C_{fuel} {\kern 1pt} \left( {(\hat{v}_{ijr}^{h} )^{2} + 2{\kern 1pt} \hat{v}_{ijr} (v_{ijr} - \hat{v}_{ijr}^{h} )} \right) \le \xi_{ijr} ,\quad \forall h,i,j,r.$$

(6.35)

and the proof is complete.

Hence applying the OA algorithm only requires the replacement of $\xi_{ijr} ,\,\forall i,j,r$ on the objective function and the addition of the first constraints of OLP in the form (6.36). The equivalent formulation of the OA’s MP can then be given as²:

$$\begin{array}{*{20}l} {\mathop {\text{Min}}\limits_{{\{ x_{ijr} ,\varvec{q}_{i} ,v_{ijr} \} \in {\Omega}_{2} }} } \hfill & {\sum\limits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\limits_{r \in K} {\psi_{ij} d_{ij} \left( {E_{ij} s_{ij} \phi + \frac{{\alpha_{ijr} {\kern 1pt} w}}{\vartheta \eta }} \right)} } C_{fuel} x_{ijr} } \hfill \\ {} \hfill & {\quad + \sum\limits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\limits_{r \in K} {\psi_{ij} d_{ij} \left( {{{\alpha_{ij} } \mathord{\left/ {\vphantom {{\alpha_{ij} } {\vartheta \eta }}} \right. \kern-0pt} {\vartheta \eta }}} \right)C_{fuel} \varvec{q}_{i} } } } \hfill \\ {} \hfill & {\quad + \sum\limits_{{(i,j) \in {\Lambda}^{ + } }} {\sum\limits_{r \in K} {\xi_{ijr} } } } \hfill \\ {{\text{st}} .} \hfill & {} \hfill \\ \end{array}$$

(6.36)

constraints of (6.30), (6.35)

$$\xi_{ijr} \ge 0,\quad \forall i,j,r$$

(6.37)

The OLP’s second constraints are not present in formulation (6.36)–(6.37), because all of the constraints are linear, thus making unnecessary to perform an OA of the feasible region.

A sketch of the implemented algorithm is detailed in Algorithm 2, where ε′, UB^* and LB^* are the stopping criteria, the objective function value of the current solution, and the objective function optimal value of the OA’s MP, respectively.

Algorithm 2

NM-OA

• 0 Initialize with the given values from Algorithm 1

• 1 Set UB ← +∞, LB ← −∞, h = 1, h = 1

• 2 If (UB − LB) < ε´, then stop. Terminate a near-optimal solution has been obtained

• 3 Solve the OA’s MP (6.36)–(6.37), obtaining LB^* and the optimal values for the variables x ^h

• 4 Add an OA cut to the OA’s MP using (6.35)

• 5 Increase h

• 6 If h > C then go to 3

• 7 Solve the OA’s MP (6.36)–(6.37), obtaining LB^* and the optimal values for the variables x ^h

• 8 Add an OA cut to the OA’s MP using (6.35)

• 9 $\begin{aligned}&\text{UB}^{\text{*}} =\sum\nolimits_{{(i,j)\in {\Lambda}^{ + }}} {\sum\nolimits_{r \in K}{\psi_{ij} d_{ij}\left( \circ\right){\kern 1pt} {\kern 1pt} C_{fuel}x_{ijr}^{h} } }+\sum\nolimits_{{(i,j) \in {\Lambda}^{ + } }}{\sum\nolimits_{r \in K} {\psi_{ij} d_{ij} \left( \circ\right){\kern 1pt} {\kern1pt}C_{fuel} q_{i} } } +\\&\sum\nolimits_{{(i,j) \in {\Lambda}^{ +} }}{\sum\nolimits_{r \in K}{\psi_{ij} d_{ij} \left({{\beta\mathord{\left/ {\vphantom {\beta{\vartheta \eta }}}\right.\kern-0pt} {\vartheta \eta }}}\right){\kern 1pt} {\kern1pt}C_{fuel} {\kern 1pt} (\hat{v}_{ijr}^{h})^{2} } }\end{aligned}$

• 10 If UB^* < UB^h−1 then set UB^h = UB^*

• 11 Increase h and go to 2

At lines 3 and 7 of Algorithm 2, the OA’s MP is solved after relaxing and imposing the integrality constraints (6.8), respectively. In lines 3 through 6, OA cut is added to the OA’s MP while a given number of cycles C is not reached. The solution time of the OA’s MP (line 7) is usually much higher than the SP because of the integrality constraints. A common strategy to short it is to reduce the number of MPs solved by embedding the generation of the OA cut in a standard B&C framework.

7 Computational Results

The proposed models have been tested on a large set of instances. Since no instances are available in the literature for our specific problem formulation, we have combined two datasets of benchmark instances introduced by Aghezzaf et al. (2006) and Bektaş and Laporte (2011) for the IPRP. Each instance set is of a different nature, characterized by the average number of vehicles (minimum number required based on load), and load. All instances are available for downloading from www.apollo.management.soton.ac.uk/prplib.htm.

Hereby, we explain the design of these experiments. Experiments were run with data generated as realistically as possible. Three classes of problems with cities were generated, where each class includes 10 instances and nodes represent United Kingdom cities. All experiments were performed with a single vehicle having a curb weight of three tonnes (implying it could carry goods weighing approximately the same amount). It is considered that the single-vehicle case in the analyses since any savings obtained with one vehicle translate into similar savings for several vehicles. Analyses were carried out for cases where customer demands are initially generated randomly according to a discrete uniform distribution on the interval [130, 150].

All experiments were conducted on a server with 2.13 GHz and 3 GB RAM. We used CPLEX with its default settings as the optimizer to solve the lower level integer linear programming model and the solver was allowed to run its B&C in a parallel mode (up to four threads) to enhance the solution process. A common time-limit of 2 h was imposed on the solution time of all instances.

To assess the quality of NM-OA algorithm, we have compared our algorithm with the LP-Metric standard B&B method. In Tables 6.2 and 6.3, we present the computational results on the instances with 75 and 100 nodes, respectively. Ten separate runs were performed for each instance as done by B&B, the best of which is reported. For each instance, a boldface entry indicates a new best-known solution.

Table 6.2 Computational results on the 75-node PRP instances

Table 6.3 Computational results on the 100-node PRP instances

As seen the first column displays the instances. The other columns show the total cost (TC) in ₤, percentage deterioration in solution quality (Dev.) with respect to the B&B method, and the optimal speed in km/h (Speed). The rows named Avg., Min (%) and Max (%) show the average results, as well as minimum and maximum percentage deviations across all benchmark instances, respectively.

The results clearly show that NM-OA outperforms B&B on all instances in terms of solution quality. The average cost reduction is 1.43 % for 75-node instances, for which the minimum and maximum improvements are 0.98 and 2.21 %, respectively. For 100-node instances, the corresponding values are 1.68 % (average), 0.03 % (minimum) and 2.37 % (maximum). On average, the B&B is faster on the 75-node instances, however, this difference is less substantial on the 100-node instances.

In order to quantify the added value of changing speeds, we have experimented with three other versions of the model in which the speed on all arcs is fixed at 70, 85 or 100 km/h. Table 6.4 presents the results of these experiments. The results suggest that while optimizing speeds with NM-OA yields the best results, using a fixed speed of 100 km/h deteriorates the solution quality by only 1.12 % on average. On the other hand, using a fixed speed of 70 km/h deteriorates the solution value by an average value of 14.01 %.

Table 6.4 The effect of the speed

8 Concluding Remarks

This chapter studied a variant IRP model, Inventory Pollution-Routing Problem (IPRP), in an environment with uncertain demand characteristic. An optimization model was presented in which a cost-minimization objective function was formulated as a mixed-integer nonlinear programming problem. An appropriate solution algorithm was developed. The algorithm can be utilized as a useful tool for optimizing both linear and nonlinear Vehicle Routing Problem (VRP) functions. The effectiveness of the algorithm was investigated through a set of computational tests comparing its performance with that of the LP-Metric standard B&B approach in terms of the solution quality.

We observed in this chapter that considering economic and environmental performance measures in isolation can result in varying solutions. There are however tradeoff solutions where environmental performance can be significantly improved at a minimal logistics cost increase. The development and application of IPRP models in which carbon emissions are implicitly or explicitly incorporated will be of increasing importance in the future, especially as tighter environmental regulations with respect to excessive transport emissions come into force. The availability of decision tools and optimization models, like what we presented in this chapter, can help companies and their supply chains more effectively tackle current and future regulatory mandates, enhance their competitive positioning, and take further steps towards the development of greener supply chains.

Appendix

1.1 Fuzzy Number

The theory of fuzzy sets introduced by Zadeh (1965) was developed to describe vagueness and ambiguity in the real world system. Zadeh defined a fuzzy set ${{\tilde{a}}}$ in a universe of discourse X as a class of objects with a continuum of grades of memberships. Such a set is characterized by a membership function $\mu_{{\tilde{a}}} (x)$ which associates with each point x in X a real number in the interval [0,1]. $\mu_{{\tilde{a}}} (x)$ represents the grade of membership of x in ${{\tilde{a}}}.$ A fuzzy set ${{\tilde{a}}}$ in the universe of discourse R (set of real numbers) is called a fuzzy number if it satisfies the following conditions:

• (i) ${{\tilde{a}}}$ is normal i.e. there exists at least one $x \in {\text{R}}$ such that $\mu_{{\tilde{a}}} (x) = 1.$

• (ii) ${{\tilde{a}}}$ is convex.

• (iii) the membership function $\mu_{{{\tilde{a}}}} (x) , x \in {\text{R}}$ is at least piecewise continuous.

1.1.1 Triangular Fuzzy Number

Triangular fuzzy number (TFN) $({{\tilde{a}}})$ is the fuzzy number with the membership function $\mu_{{{\tilde{a}}}} (x) ,$ a continuous mapping: $\mu_{{{\tilde{a}}}} (x) : {\text{R}} \to [0,1] ,$ where

$$\mu_{{\tilde{a}}} (x) = \left\{ {\begin{array}{*{20}l} 0 \hfill & \{ - \infty < x < a_{1} \} \hfill \\ {\frac{{x - a_{1} }}{{a_{2} - a_{1} }}} \hfill & {a_{1} \le x < a_{2} } \hfill \\ {\frac{{a_{3} - x}}{{a_{3} - a_{2} }}} \hfill & {a_{2} \le x \le a_{3} } \hfill \\ 0 \hfill & {a_{3} < x < \infty .} \hfill \\ \end{array} } \right.$$

(6.38)

1.1.2 α-Cut of a Fuzzy Number

An α-cut of a fuzzy number ${{\tilde{a}}}$ is defined as a crisp set

$$a_{\alpha } = \left\{ {x{:}\, \mu_{{\tilde{a}}} (x) \ge \alpha ,\quad x \in {\text{R}}} \right\}\quad {\text{where}}\,\eta \;\left[ {0,1} \right].$$

1.1.3 Approximate Value of Triangular Fuzzy Number (TFN)

According to Kaufmann and Gupta (1991), the approximated value of TFN $\tilde{a} \equiv \left( {a_{1} ,a_{2} ,a_{3} } \right)$ is given by $\hat{a} = {\raise0.5ex\hbox{$\scriptstyle 1$} \kern-0.1em/\kern-0.15em \lower0.25ex\hbox{$\scriptstyle 4$}}\left( {a_{1} + 2a_{2} + a_{3} } \right).$

1.1.4 Algebraic Operation of Fuzzy Numbers

Addition

Let $\tilde{a} \equiv \left( {a_{1} ,a_{2} ,a_{3} } \right)$ and $\underline{{\tilde{b}}} \equiv \left( {b_{1} ,b_{2} ,b_{3} } \right)$ be two triangular fuzzy numbers. Using max-min convolution on fuzzy numbers ${{\tilde{a}}}$ and ${{\tilde{b}}}$ the membership function of the resulting fuzzy number ${{\tilde{a}}} \, ({+}) \, {{\tilde{b}}}$ can be obtained as $\vee_{z = x + y} \left( {\mu_{{\tilde{a}}} (x) \wedge \mu_{{\tilde{b}}} (y)} \right),\;\forall_{x,y,z} \in {\text{R}}$ where the symbols ‘$\wedge$’ and ‘$\vee$’ are used for minimum and maximum, respectively. In short we can write $\tilde{a} \, ( + ) \, \tilde{b} = \left( {a_{1} ,a_{2} ,a_{3} } \right) ( { + )}\left( {b_{1} ,b_{2} ,b_{3} } \right).$

Scalar multiplication

For any real constant t,

$$t\tilde{a} = \left\{ \begin{aligned} (ta_{1} ,ta_{2} ,ta_{3} )\quad t \ge 0 \hfill \\ (ta_{3} ,ta_{2} ,ta_{1} )\quad t < 0. \hfill \\ \end{aligned} \right.$$

1.1.5 Fuzzy Possibility Techniques

Let ${{\tilde{a}}}$ and ${{\tilde{b}}}$ be two fuzzy quantities with membership functions $\mu_{{\tilde{a}}} (x)$ and $\mu_{{\tilde{b}}} (y),$ respectively. Then according to Dubois and Prade (1980), Liu and Iwamura (1998a, b) $pos\left( {\tilde{a}*\tilde{b}} \right) = \sup \left\{ {\hbox{min} \left( {\mu_{{\tilde{a}}} (x),\mu_{{\tilde{b}}} (y)} \right) {:}\, x,y \in {\text{R}}, \, x*y} \right\},$ where the abbreviation ‘pos’ represents possibility and * is any of the relations <, >, =, ≤, ≥.

If ${\tilde{a}}$ and ${\tilde{b}}$ are two fuzzy numbers defined on R and ${\tilde{u}} = f({\tilde{a}}, {\tilde{b}})$ where $f {:} \, {\text{R}} \times {\text{R}} \to {\text{R}}$ is a binary operation then the membership function $\mu_{\tilde{u}}$ of ${\tilde{u}}$ is defined as $\mu_{\tilde{u}} (u) = \sup \{ {\min(\mu_{\tilde{a}}(x), \mu_{\tilde{b}}(y)) {:}\, x, y \in {\text{R}} }$ and u = f(x,y), ∀u ∈ R}.

1.2 Random Variable

Let $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} \, ( {=} (m,\sigma^{2} ))$ be a continuous random variable with probability density function (PDF) $f_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} }} \left( l \right)$ whose mean and variance are m and σ ², respectively. Similarly, let $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L}^{\prime} \,( {=} (m^{\prime} , \sigma^{\prime 2} ))$ be another random variable with pdf $f_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L^{\prime}} }} (l^{\prime}).$ If ${\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} }$ and ${\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L^{\prime}} }$ are two independent random variables, then we have the following algebraic operations:

• Addition:

$$\underline{L}_{1} [ + ]\underline{L}_{2} = (m_{1} ,\sigma_{1}^{2} )[ + ]{\kern 1pt} {\kern 1pt} (m_{2} ,\sigma_{2}^{2} ) = \,(m_{1} + m_{2} ,\sigma_{1}^{2} + \sigma_{2}^{2} ).$$

Here, according to sum-product convolution $\varvec{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} }( = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} + \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L}^{\prime})$ is a random variable with the same type of pdf $f_{{\varvec{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} }}} \left( \varvec{l} \right) = (\int\nolimits_{\text{R}} f(\varvec{l} - l^{\prime})f^{\prime} (l^{\prime})dl^{\prime}$ with mean $\varvec{m^{\prime}}^{2} ( {=} m^{2} + m^{\prime} )$ and variance $\varvec{\sigma}^{\prime 2} ( = \sigma^{2} + \sigma^{\prime 2} ) .$

• Scalar multiplication:

$t\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} = (tm,t^{2} \sigma^{2} ).$ Here tL and L have the same type of PDF.

1.3 Hybrid Number (Kaufmann and Gupta 1991)

Assume $\tilde{A}( = (\tilde{A},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} ))$ is a hybrid number. Here the couple ($\tilde{A},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L}$) represents the addition to a fuzzy number with a random variable without altering the characteristic of each one and without decreasing the amount of available information where à is a fuzzy number and L is the random variable with density function $f_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} }} \left( l \right).$ Let $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\tilde{A}} ( = (\tilde{A},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} ))$ and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\tilde{A}}^{\prime}( = (\tilde{A}^{\prime},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L}^{\prime}))$ be two hybrid numbers in R where $f_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} }} \left( l \right)$ and $f_{{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L}^{\prime}}} (l^{\prime})$ are the pdfs of L and L′, respectively. So a hybrid convolution for addition will be defined as $(\tilde{A},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} ) \oplus (\tilde{A}{\prime} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L}^{\prime}) = (\tilde{A}\left( + \right)\tilde{A}^{\prime} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} [ + ]\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L}^{\prime}) = (\tilde{\varvec{A}},\varvec{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} }),$ where (+) represents the max-min convolution for addition of fuzzy subsets and [+] represents the sum-product convolution for addition of random variables. We denote the couple $(\tilde{\varvec{A}},\varvec{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} })$ by the symbol $\tilde{\varvec{A}}( + )^{\prime}\varvec{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} } .$

So,${\kern 1pt} \mu_{{\tilde{A}_{1} ( + )\tilde{A}_{2} }} (z) = \vee_{z = x + y} (\mu_{{\tilde{A}_{1} }} (x) \wedge \mu_{{\tilde{A}_{2} }} (y)),\forall x,y,z \in \text{R}$ and $f(l) = \int\nolimits_{\text{R}} f_{1} (l - l_{2} )f_{2} (l_{2} )dl_{2}$ or $\int\nolimits_{\text{R}} f_{1} (l_{1} )f_{2} (l - l_{1} )dl_{1} .$

Note 1

A fuzzy number is a special case of a hybrid number if $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\tilde{A}} = (\tilde{A},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{0} ),$ where 0 is the trivial random variable with the following probabilities:

$$\begin{aligned} P(l) & = 1,\quad l = 0 \\ & = 0{\kern 1pt} ,\quad l \ne 0. \\ \end{aligned}$$

Note 2

A random variable is also a special case of a hybrid number if $\tilde{\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} } = \left( {\tilde{0},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} } \right),$ where ${\tilde{0}}$ is the trivial fuzzy number with membership function

$$\begin{aligned} \mu_{{\tilde{0}}} (x) & = 1,\quad x = 0 \\ & = 0{\kern 1pt} ,\quad x \ne 0. \\ \end{aligned}$$

Note 3

$\underline{{\tilde{0}}} = (0, 0)$ is the neutral for addition of hybrid numbers.

If $\tilde{u}_{1}$ is a fuzzy cost, $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{u}_{2}$ is a random cost and u ₃ is a fixed cost then the total cost can be expressed as

$$\tilde{u}_{1} [ + ]{\kern 1pt} \underline{u}_{2} [ + ]{\kern 1pt} u_{3} = (\tilde{u}_{1} ,0){\kern 1pt} [ + ]{\kern 1pt} (0,\underline{u}_{2} ){\kern 1pt} [ + ]{\kern 1pt} (0,u_{3} ) = (\tilde{u}_{1} ,\underline{u}_{2} ( + )^{\prime}u_{3} ) = (\tilde{u}_{1} ( + )u_{3} ,\underline{u}_{2} ){\kern 1pt} .$$

(6.39)

We can consider the fixed number like a sum of two parts $u_{3} = u^{\prime}_{3} + u^{\prime\prime}_{3}$ and write for (6.39)

$$\tilde{u}_{1} [ + ]{\kern 1pt} \underline{u}_{2} [ + ]{\kern 1pt} u_{3} = (\tilde{u}_{1} [ + ]{\kern 1pt} u^{\prime}_{3} ,\underline{u}_{2} [ + ]{\kern 1pt} u^{\prime\prime}_{3} ).$$

(6.40)

The mathematical expectation of a hybrid number is defined as follows.

A function ϕ(x) in R that is nonnegative and monotonically increasing is:

$$\begin{aligned} & \forall x_{1} ,x_{2} \in {\text{R}}: \\ & (x_{1} > x_{2} ) \Rightarrow (\varphi (x_{2} ) \ge \varphi (x_{1} )){\kern 1pt} . \\ \end{aligned}$$

(6.41)

For a closed interval of R, $[a_{\alpha }^{1} ,a_{\alpha }^{2} ]$ we have:

$$[\phi {\kern 1pt} (a_{\alpha }^{1} ),\phi {\kern 1pt} (a_{\alpha }^{2} )] \subset \text{R}$$

(6.42)

and for l ∈ R:

$$[\phi {\kern 1pt} (a_{\alpha }^{1} + l),\phi {\kern 1pt} (a_{\alpha }^{2} + l)] \subset \text{R}.$$

(6.43)

If l is the value of the random variable L, the lower and upper bounds of (6.43) depend only on l for a given level α. The mathematical expectation for each bound is now computed:

$$E[\phi {\kern 1pt} (a_{\alpha }^{1} + l),\phi {\kern 1pt} (a_{\alpha }^{2} + l)] = \left[ {\int\limits_{{l_{1} }}^{{l_{2} }} \phi (a_{\alpha }^{1} + l){\kern 1pt} \cdot {\kern 1pt} f(l)dl,\int\limits_{{l_{1} }}^{{l_{2} }} \phi (a_{\alpha }^{2} + l){\kern 1pt} \cdot {\kern 1pt} f(l)dl} \right].$$

(6.44)

Theorem

(Kaufmann and Gupta 1991). The membership function of the mathematical expectation of a hybrid number $(\tilde{A},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} )$ is the membership of $\tilde{A}$ shifted by the mathematical expectation of $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L}$

Proof

Using the intervals of confidence of level α:

$$\begin{aligned} E_{\alpha } (\tilde{A}[ + ]\underline{L} ) & = \left[ {\int\limits_{{l_{1} }}^{{l_{2} }} (a_{\alpha }^{1} + l){\kern 1pt} \cdot f(l)dl,\int\limits_{{l_{1} }}^{{l_{2} }} (a_{\alpha }^{2} + l){\kern 1pt} \cdot f(l)dl} \right] \\ & = \left[ {a_{\alpha }^{1} {\kern 1pt} \cdot {\kern 1pt} \int\limits_{{l_{1} }}^{{l_{2} }} f(l)dl{\kern 1pt} + {\kern 1pt} \int\limits_{{l_{1} }}^{{l_{2} }} l{\kern 1pt} \cdot {\kern 1pt} f(l)dl,a_{\alpha }^{2} {\kern 1pt} \cdot {\kern 1pt} \int\limits_{{l_{1} }}^{{l_{2} }} f(l)dl{\kern 1pt} + {\kern 1pt} \int\limits_{{l_{1} }}^{{l_{2} }} l{\kern 1pt} \cdot {\kern 1pt} f(l)dl} \right] \\ & = \left[ {a_{\alpha }^{1} + E(l){\kern 1pt} {\kern 1pt} ,{\kern 1pt} {\kern 1pt} a_{\alpha }^{2} + E(l)} \right] \\ \end{aligned}$$

(6.45)

Hence, in a hybrid sum, if the random variables satisfy their random expectation, they will have the same effect as ordinary numbers, shifting the sum of fuzzy numbers.

Using the notation $({\tilde {A}},\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} ) = {\tilde{A}}( + )^{\prime} \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{L} ,$ where $\tilde{A}$ is a triangular fuzzy number, the following example is illustrated.

Example

Let $\tilde{A}_{1} = (3,5,9)( + )^{\prime}(6,1.2)$ and $\tilde{A}_{2} = (6,7,10)( + )^{\prime}(7,1.8)$ be two hybrid numbers, then

$$\begin{aligned} \underline{{\tilde{A}}}_{1} \oplus \underline{{\tilde{A}}}_{2} & = [(3,5,9)( + )^{\prime}(6,1.2)] \oplus [(6,7,10)( + )^{\prime}(7,1.8)] \\ & = [(9,11,15)( + )^{\prime}(0,1.2)] \oplus [(13,14,17)( + )^{\prime}(0,1.8)] \\ & = (22,25,32)( + )^{\prime}(0,3.0). \\ \end{aligned}$$