Uncertainty modeling in multi-objective vehicle routing problem under extreme environment

Abstract

Assumption of fuzziness in the vehicle routing problems under extreme conditions is necessary for modelers, because there are usually insufficient objective input data. In extreme situations, the complexity of the description of vehicles’ movement on routes may cause by two poles: the imprecision of movement time and the uncertainty of the possibility of movement on roads. Traditionally, a fuzzy value has been used to represent the data’s impreciseness; hence, only one pole of expert’s information is taken in the aggregation results. The main objective of this paper is to present an efficient way for fuzzy vehicle routing modeling to minimize the decision-making risks in the optimal planning of routes network and from distribution centers to demand points. To address this, a new two-stage possibilistic bi-criteria vehicle routing problem (VRP) is presented under extreme conditions. In the first stage, the sample of so-called “promising” closed routes are selected based on a “constructive” approach using a simulation algorithm. The expected times of the vehicle movement between demand points are taken as fuzzy triangular numbers. In the second stage, based on Choquet integral’s, a bi-criteria partitioning model for the fuzzy VRP has been constructed. The constraint approach has been defined to obtain the optimal solution of the model. For numerical experiments, a parallel algorithm is created based on D. Knuth’s algorithm of dancing links. An example is presented with the results of our approach for the VRP, where all Pareto-optimal solutions are found from the promising routes.

1 Introduction

1.1 Problem presentation and work motivation

In the modern world of growing economies and mass consumption, managing the transportation of goods is becoming more and more complicated and diversified. Among the many challenges connected with the distribution of goods, one of the most important is the selection of optimal routes, which becomes even more difficult in extreme conditions. Such situations may include: (1) the management of secure and optimal supply of goods to medical, military, or strategic objects in geographical zones damaged by natural disasters, earthquakes, weapons of mass destruction, etc.; (2) planning of the rapid and safe assistance to the population in difficult situations; (3) strategic management of transportation routes in places of military action; (4) management of optimal vehicle routes on roads with overloaded traffic, places of public demonstrations and strikes, slippery, snowy roads, and more.

Route planning problems, also known as VRP, have been widely investigated in many directions, such as Operations Research, Artificial Intelligence, etc. The standard VRP was firstly considered in 1959 by Dantzig & Ramser (1959) and it is a complex combinatorial optimization problem. Some versions of the initial problem have been put forward and strong formulations offered. These problems often are reduced to discrete programming problems. If the finding optimal solutions must be guaranteed, then exact methods are used, but solving large-dimensional problems with these methods is generally impossible. Therefore, these approaches are usually paired with various heuristic methods in a wide scope of applications.

Given that the complex, flexible, and dynamic nature of real logistical planning produces, a high degree of uncertainty in the modeling process occurred and hence it is not expecting that all the necessary information is available at the onset of the problem. The most common scenarios provide uncertain and imprecise information of some parameters and variables (Sirbiladze 2021, 2022; Sirbiladze et al. 2021; Zacharia et al. 2021). Therefore, the use of the theory of fuzzy sets in the construction of solving systems for decision-making is very appropriate. A fuzzy approach to modeling of VRPs—Fuzzy VRPs (FVRP) is common in modern literature (Brito et al. 2012). The majority of them assume vagueness of the following parameters: travel and service times, time windows are imprecise, as well as fuzzy customer demands. Modeling of uncertainty in the FVRP is the main study direction of this work which guarantees minimization of vehicle movement risks on routes under extreme conditions.

Various difficulties and problems of movement inevitably lead to the imprecision and uncertainty of vehicle motion on the routes. For the VRPs presented in this work, when observing extreme conditions on roads, stochastic models may not work because the probability distributions of some input parameters are unknown due to their vagueness. These parameters include vehicle movement time, representing a total value of demand point-to-demand point movement times. In such cases, evaluating and considering the routing reliability is also required when various obstacles can hinder the movement on the routes.

Our country, Georgia, is mountainous, and meteorological extreme conditions (earthquakes, severe storms, floods, fog, and other reasons causing the lack of visibility, slippery or snowy roads, and others) often impede the vehicle routes. The existing VRP software doesn’t support the optimal rearrangements of routes and all difficulties are solved based on the knowledge and experience of experts (managers or routing network dispatchers). This is why the development of a new approach to FVRP was decided (based on our experience in similar problems of fuzzy covering and partitioning). The new approach would integrate the knowledge of experts and managers into the solution of problems faced by the possibilistic approach to VRP. It would add to existing objective criteria (minimization of total travel time or travel distance of movement on the closed routes and others) a new criterion, which is the minimization of the infeasibility of vehicle movement on the closed routes.

1.2 Brief consideration of multi-objective FVRP approaches

Due to the high traffic and other daily circumstances found in routing networks, both—motion and service times are often fuzzy. In Teodorović and Kikuchi (1991), a vehicle routing model which treats travel times to customers as fuzzy numbers is introduced. The offered model in developing vehicle routes uses the principles of the classical Clarke–Wright algorithm. The presented examples describe the route pattern of a vehicle which varies significantly according to the fuzziness level of motion time. In Liu (2006) the author considers the VRP with time windows while assuming that the travel times are inevitably imprecise, and handled as fuzzy numbers. In Tang et al. (2007) the travel time in the fuzzy mathematical model of the VRP also has a fuzzy nature.

Sometimes, the information on customers’ (or demand points in our case) needs is not sufficiently precise. Thus, there is imprecision regarding the demands vector. In Lucić and Teodorović (2007), the authors resolved a VRP where customers’ demand is imprecise and is expressed with a triangular fuzzy number (TFN). The model is built on the metaheuristic “sweeping” algorithm, by which it is determined whether to serve a customer. The model utilizes special procedures for the calculation of the preference index. The same authors have proposed a solution to this problem (Lucić and Teodorović 2007; Lucić and Teodorović 2007) when customer demand is measured only after visiting. This is accomplished using the fuzzy set theory and Ant Colony systems.

Multi-objective fuzzy VRPs before 2010 years were considered in Ghannadpour et al. (2014); Gupta et al. (2010). Other approaches of the VRP under fuzzy impression are also considered in Brito et al. (2008, 2012). The main trends in the FVRP in the 2010–2015 years can be found in Allahviranloo et al. (2014); Brito et al. (2015); Sandhya and Katiyar (2014). A good overview of the literature of these years for the FVRP and the ways of its solution is presented in (Brito et al. 2009). The main results on the FVRP in the recent 5 years look as follows.

In Yalcın and Erginel (2015) the vehicle routing problem with backhauls (VRPB) is presented. This study aims to propose a new algorithm based on fuzzy multi-objective programming (FMOP-VRPB algorithm) to solve the VRPB. The FMOP-VRPB algorithm has three phases—clustering, routing, and local search. New recent approaches in evolutionary programming problems are also developed in Chauhan et al. (2021a, b, c). In Brito et al. (2015) a multi-objective variant of vehicle routing problems is considered, in which the customer demands are supposed to be triangular fuzzy numbers and the objective functions are also disrupted by fuzziness. However, the propagation of fuzzy demands to the objectives can affect the reliability of generated solutions. The new approach tries to achieve robust routes that minimize two fuzzy-valued objectives, the total traveled distance and total tardiness time. In Nucci (2017) authors study the single-vehicle routing problem with time windows, multi-shift, and fuzzy uncertainty. In this problem, one vehicle is used repeatedly to serve demand over a planning horizon of several days. The problem is inspired by a routing problem in maintenance activities, where one maintenance crew uses a vehicle to perform jobs in various locations. The effect of uncertainty in travel and job processing time on KPI is studied. An Artificial Immune Heuristic to solve the addressed problem is developed. The vehicle routing problem with multiple fuzzy time windows is investigated in Cao et al. (2017). The dynamic change of traffic flow and the fuzzy time window of customers are considered. A multi fuzzy time window vehicle routing model based on time‐varying traffic flow is proposed, and the objective function is to minimize the total cost of distribution and maximize customer satisfaction. Wang et al. (2018) investigates a bi-objective vehicle-routing problem with soft time windows and multiple depots, which aims to simultaneously minimize total energy consumption and customer dissatisfaction. To address the problem, the authors first developed mixed-integer programming. Then, an augmented ϵ-constraint method is adopted to obtain the optimal Pareto front for small problems. It is very time-consuming for the augmented ϵ-constraint method to precisely solve even medium-sized problems. For medium- and large-sized problems, two Non-dominated Sorting Genetic Algorithm-II-based heuristics with different rules for generating initial solutions and offspring are designed. In Abad et al. (2019) an optimization model is presented for split loading and unloading products by suppliers and customers, vehicle routing with fuzzy possibilistic time window constraints among them, assignment of vehicles to cross dock, consolidation, and integration of products in the cross dock, and allocation of sorted products to outbound vehicles. The mathematical model provided in this study has three objective functions. The first and second objectives minimize total cost and fuel consumption, and the third one maximizes the satisfaction degrees of suppliers and customers. Two multi-objective meta-heuristic algorithms were utilized to solve the model, namely Multi-Objective Grey Wolf Optimizer and Multi-Objective Imperialist Competitive Algorithm. To minimize the total distribution cost and mean consumer dissatisfaction (Zheng 2020) sets up a VRP model with multiple fuzzy time windows, based on time-varying traffic flow. In addition, the Ito algorithm was improved based on time-varying traffic flow. The model and algorithm were verified through example simulation, in comparison with ant colony optimization. Esmaeilidouki et al. (2021) introduces a bi-objective model for a vehicle routing and scheduling problem of hazardous material distribution problems under the fuzzy condition to minimize both total distribution time and risks. In the proposed model, the fuzzy inference system and fuzzy failure mode and effects analysis are applied to identify and calculate the high-level risks instead of the previous simple methods for the first time. Considering the impact of charging facilities and carbon emission, Zhao et al. 2021) proposes a vehicle routing problem with a mixed fleet of conventional and electric vehicles and soft time windows. A bi-objective programming model is established to minimize total operational cost and time penalty cost. Finally, the nondominated sorting genetic algorithm II (NSGA-II) is employed to deal with this problem.

In general, fuzzy optimization approaches presented above, four different types of problems can be considered. Two of these problems include an imprecision in the objective function(s), such as the case with fuzzy goals and the case with fuzzy costs. The remaining two problems consider fuzzy comparison in the constraints and the coefficients of the technological matrix. In addition, a fifth problem, the general fuzzy problem could be studied in which all of the parameters will be subject to fuzzy considerations. In practice, the search for optimal solutions to FVRP can be done with the following approaches. The simplest approach applies procedures for the fuzzification and defuzzification of variables. It transforms the imprecise information in fuzzy parameters and uses procedures that integrate fuzzy arithmetic to obtain fuzzy solutions. The fuzzy solution is then transformed into a crisp one using some known formulation. This approach may also be used for the introduction of sophisticated fuzzy rules in the decision-making processes to improve their quality. Linguistic variables could be used to facilitate the incorporation of “intelligent” procedures as automatic reasoning, adaptive control, or automatic learning. In this paper, the optimization two-step approach, which deals with vehicle routing planning in extreme conditions, is different from presented here five directions of optimization in FVRP.

1.3 Briefly on extremal poles of experts’ data in the new FVRP

Assumption of fuzziness in the vehicle routing modeling under extreme environments is a necessary action for modelers, because usually, there are insufficient objective input data, from the statistical point of view, at the starting of classical or stochastic VRP models. In the extreme environment for the efficient action of VRP models, the experts’ evaluations play a crucial role. The reader probably has noticed that most of the existing researches of FVRP (discussed in subsection 1.2) considers the imprecise nature of different parameters (transportation costs, movement time, service windows, etc.) by representing them as fuzzy numbers. When the movement (travel) on routes is complicated due to different reasons, fuzzified parameters (travel time, time windows, and others) evaluated in fuzzy numbers represent only one pole of expert information—called information imprecision (Klir and Wierman 1999; Sirbiladze 2013). Thus, existing researches, presented above, ignore the second pole of expert information—uncertainty, represented by a fuzzy (monotone) measure (Sirbiladze 2013; Wang and Klir 2009) which deals with the possibility of the vehicle movement on the routes. It is important to consider uncertainty when expert judgment of the possibility of movement on routes in FVRP models has been introduced. An aggregation of information contained in these two poles creates believe and plausible objective functions in optimization models of FVRP. This is the primary reason why the existing FVRP models are less reliable for optimal routing planning in extreme conditions on the roads.

The target functions and restrictions in the approaches presented above, use only fuzzy set theory as an instrument to describe imprecision of expert data and no research would consider possibility measure (in general monotone measure) (Klir and Wierman 1999; Sirbiladze 2020, 2013; Sirbiladze et al. 2019, 2018; Sugeno 1974; Wang and Klir 2009) of information uncertainty, which is the second pole of expert evaluations. To be more specific, the weak side of these studies is that their authors introduce fuzzy imprecision in the form of fuzzy values, related to the expert evaluations, but don’t use such well-known instruments for aggregation of fuzzy data as Choquet Integral (Choquet 1954), Sugeno Integral (Sugeno 1974), OWA type operators (Sirbiladze 2020; Sirbiladze et al. 2019, 2018; Yager 1988). The reason is understandable—such aggregations require the use of nontrivial monotone measures of the second pole of expert information—uncertainty. On the other hand, the use of aggregations with imprecision and uncertainty in FVRP models will make them more consistent, because the expert evaluations of the difficulty of movement on the routes in extreme conditions will be also considered. These evaluations can be represented by the levels of the possibility of the vehicle movement on the routes (the second pole of expert information). The possibility theory was presented by Zadeh (1978) and investigated by Dubois and Prade (1988). Beginning from the 1980s, the possibility theory becomes significant in the decision-making and optimization fields of research (Verdegay 1982). The core differences between probability and possibility theories are considered in Sect. 2.

Although VRP, generally speaking, by its nature is a single-objective optimization problem (that is to find the minimum value of traveling distance or time), however, there is a need to achieve several objectives simultaneously having involved into consideration of different aspects of the problem, even the uncertainty associated with feasibility (unfeasibility) of chosen routes under extreme conditions.

1.4 On new two-stage FVR methodology (TSFVRM) and problem solution scheme

The paper presents a two-stage new methodology in FVRP under extreme conditions. Its multi-criterion optimization problem creates a fuzzy model of the bi-criteria partitioning problem. One criterion is classical—minimization of the total length of vehicles movement on a partitioning of closed routes and second criterion is novation—minimization of the fuzzy infeasibility of vehicles movement on a partitioning of closed routes. Understandably, in the real-world environment, the new criterion does not define anything in the FVRP model under natural environment. But it is also clear that it contains very important details in extreme situations where some degree of damage to the roads between customers (demand points) is expected. Delays in the traffic on the roads are expected at this time. A creation of completely new optimal routes for the fast supply of aids needed in demand points is also expected. The interactive algorithm for the assessment of the degree of non-mobility on the roads has involved an expert—a route network dispatcher, who visually receives information about road damage through drones, helicopters, or video-photo equipment of distance vision from space. The dispatcher processes this information and divides the network of routes into geographical zones according to the degree of road damage (see Appendix A). His/her knowledge of these damages will then be accumulated through the interactive algorithm to the degrees of impossibility of vehicles movement on these roads. The new criterion is the aggregation value for the fuzzy travel times and degrees of impossibility of vehicles movement on these roads. The aggregation tool is the Choquet finite integral, which aggregates two poles of expert information—imprecision (fuzzy travel times) and uncertainty (degrees of impossibility).

The two stages of the methodology are as follows:

Stage 1

• 1. Start-of-the-paper problems include generation and formation of objective input data (the demands for goods by demand points in extreme conditions, the constraints of maximum load and mileage of the vehicles, and others) for Vehicle Routing Problem under extreme conditions. The formation of objective data and software implementation is done using Google Directions API. Users of Intelligent Support System—Optimal Route Planning for Transportation of Goods (ORPTG) have the functionality to input customer coordinates and the system will mark them on Google Maps, create a customer network model, and calculate a matrix of distances between them. This matrix is the input parameter for the problem in the following task. Based on this matrix expected fuzzy times of vehicle’s movement between demand points are created.

• 2. Generation of “promising routes” on the routing network (Algorithm 1). The heuristic approach has been developed which generates so-called “promising routes” from the large set of possible routes.

• 3. Based on the Monte-Carlo approach, the efficient interactive simulation algorithm of estimation of conditional possibilities of vehicle movement between demand points is constructed. For the formation of input expert information in the algorithm, the routing network’s dispatcher is included in the interactive regime (Algorithm 3, Appendix A).

• 4. Construction of a fuzzy infeasibility level of vehicle movement on a closed “promising route” based on Choquet finite integral.

• 5. Construction of new objective function—a fuzzy infeasibility of the vehicle movement on a partitioning of closed “promising routes”.

• 6. Construction of classical objective function—a total distance traveled on a partitioning of closed “promising routes”.

Stage 2

• 1. Creation of Bi-criteria Partitioning Model for the FVRP.

• 2. Modification of $\varepsilon$-constraint approach based on a parallel extension of D. Knuth’s algorithm of dancing links (DLX).

• 3. Construction of Pareto front of new FVRP solutions by the extended $\varepsilon$-constraint approach (Algorithm 2).

In Sect. 2, the brief preliminary concepts on the lattice of fuzzy numbers and probability-possibility interrelationship are given. In Sect. 3, the basic VRP with the criterion—minimization of the total distance is considered. In the same section, subjective expert parameters for a new approach to the VRP are presented. In Sect. 4, using a finite Choquet integral, fuzzy infeasibility level of movement on a closed route is defined. In the same section, a new criterion—minimization of the fuzzy infeasibility of vehicle movement on the closed routes is built and VRP is reduced to a bi-criteria partitioning problem. $\varepsilon$-constraint approach to the determination of all Pareto-optimal solutions for the constructed bi-criteria partitioning problem is given in Sects. 5, 6. Section 7 illustrates the results of the new approach of VRP for an offered numerical example. Finally, a concrete conclusion is presented in Sect. 8.

2 Preliminary concept

The fuzzy numbers (FN) have been studied by many authors (Dubois and Prade 1988). They can be represented in a more complete way as an imprecision variable of incomplete expert information.

Definition 1

$\tilde{\xi }(\tau ):R^{1} \to \left[ {0;1} \right]$ is called a FN which is defined as:

$$ \tilde{\xi }\left( \tau \right) = \left\{ {\begin{array}{*{20}c} {1,} & {{\text{if}}\,\tau \in \left[ {\tau _{2}^{\prime } ;\tau _{{22}}^{{\prime \prime }} } \right]} \\ {\frac{{\tau - \xi _{1} }}{{\tau _{2}^{\prime } - \xi _{1} }},} & {{\text{if}}\,\tau \in \left[ {\xi _{1} ,\tau _{2}^{\prime } } \right]} \\ {\frac{{\xi _{3} - \tau }}{{\xi _{3} - \tau _{{22}}^{{\prime \prime }} }},} & {{\text{if}}\,\tau \in \left[ {\tau _{{22}}^{{\prime \prime }} ,\xi _{3} } \right]} \\ {0,} & {{\text{otherwise}}} \\ \end{array} } \right., $$

where ${\xi }_{1}\le {\tau }_{2}^{^{\prime}}\le {\tau }_{2}^{^{\prime\prime} }\le {\xi }_{3}\in {R}^{1}$.

Let $\tilde{\xi }$ and $\tilde{\zeta }$ be two triangular FNs (TFNs), where $\tilde{\xi }=\left({\xi }_{1},{\xi }_{2},{\xi }_{3}\right)$ and $\tilde{\zeta }=\left({\zeta }_{1},{\zeta }_{2},{\zeta }_{3}\right)$, then some basic arthimetic operations for TFNs (for which ${\tau }_{2}^{^{\prime}}={\tau }_{2}^{^{\prime\prime} }\equiv {\xi }_{2}$) are stated as.

• 1. $\tilde{\xi }+\tilde{\zeta }=\left({\xi }_{1}+{\zeta }_{1},{\xi }_{2}+{\zeta }_{2},{\xi }_{3}+{\zeta }_{3}\right)$;

• 2. $\tilde{\xi }-\tilde{\zeta }=\left({\xi }_{1}-{\zeta }_{3},{\xi }_{2}-{\zeta }_{2},{\xi }_{3}-{\zeta }_{1}\right)$;

• 3. $\tilde{\xi }\times k=\left(k{\xi }_{1},k{\xi }_{2},k{\xi }_{3}\right),k>0$;

• 4. ${\tilde{\xi }}^{k}=\left({\xi }_{1}^{k},{\xi }_{2}^{k},{\xi }_{3}^{k}\right),k>0,\hspace{0.33em}{\xi }_{i}>0$;

• 5. $\tilde{\xi }\cdot \tilde{\zeta }=\left({\xi }_{1}{\zeta }_{1},{\xi }_{2}{\zeta }_{2},{\xi }_{3}{\zeta }_{3}\right),\hspace{0.33em}{\xi }_{i}>0,\hspace{0.33em}{\zeta }_{i}>0$;

• 6. $1/\tilde{\xi }=\left\{\frac{1}{{\xi }_{3}},\frac{1}{{\xi }_{2}},\frac{1}{{\xi }_{1}}\right\},{\xi }_{i}>0$.

Further, it is stated that $\tilde{\xi }>\tilde{\zeta }if{\xi }_{2}>{\zeta }_{2}$, and ${\text{if}} {\xi }_{2}={\zeta }_{2} \,{\text{then}} \,\tilde{\xi }>\tilde{\zeta }{\text{if}} \frac{{\xi }_{1}+{\xi }_{3}}{2}>\frac{{\zeta }_{1}+{\zeta }_{3}}{2}, {\text{otherwise}} \tilde{\xi }=\tilde{\zeta }$.

The set of all TFNs is denoted by $\Psi$ and nonnegative TFNs (${\xi }_{i}\ge 0$) by ${\Psi }^{+}$. Note that on the lattice ${\Psi }^{+}$ ${1}_{{\Psi }^{+}}=\left({1,1},1\right)$ and ${0}_{{\Psi }^{+}}=\left({0,0},0\right)$. The latest notion of inequality induces the total ordering ${\ge }_{t}$ on the lattice ${\Psi }^{+}$ and say that $\tilde{\xi }{\ge }_{t}\tilde{\zeta }$ iff $\tilde{\xi }>\tilde{\zeta }$ or $\tilde{\xi }=\tilde{\zeta }$. The operations of max and min based on the total ordering ${\ge }_{t}$ is stated as ${\mathit{max}}_{t}\{\tilde{\xi };\tilde{\zeta }\}=\tilde{\xi }$ and ${\mathit{min}}_{t}\{\tilde{\xi };\tilde{\zeta }\}=\tilde{\zeta }$ iff $\tilde{\xi }{\ge }_{t}\tilde{\zeta }$.

Before constructing a new, expert knowledge-based criterion for vehicle routing problem in extreme and uncertain environment, let’s say few words about possibility theory. According to the possibility theory (Dubois and Prade 1988; Zadeh 1978), the possibility of any event is maximal among its supportive elementary events possibilities:

$$ Pos\left( D \right) = \mathop {\max }\limits_{{y \in D}} \pi (y). $$

Compared to the event possibility, the probability is an additive sum of elementary probabilities:

$$ \Pr (D) = \sum \limits_{{y \in C}} pr(y). $$

Possibility of occurrence of the event is a potential exposure of an object to achieve desired goal, degree or level of which is reflected within [0, 1] numbers as a result of the expert’s intellectual activity. i.e., the more expectable the occurrence of an event the higher is the possibility level of this event. I.e., the simpler is an event occurrence the higher is the event possibility level. And, unlike probability with “tough” additive feature for incompatible events:

$\mathit{Pr}(V\cup D)=\mathit{Pr}(V)+\mathit{Pr}(D),$ if $V\cap D=\varnothing ,$

possibility has the ability to undertake maximum:

$$Pos(V\cup D)=\mathit{max}\left\{Pos(V);Pos(D)\right\}.$$

Also, if probability sum of elementary events is 1:

$$ \sum \limits_{y} pr(y) = 1, $$

possibility distribution is not limited to it. This requirement is replaced with the following principle: the highest possibility is limited by 1 and at least one event will be undertaken with the possibility value equal to 1:

$$ \mathop {\max }\limits_{y} \pi (y) = 1. $$

For evaluating infeasibility levels of movement between customers possibility measure has been choosen, since it can lead us to the reasonable models, where route infeasibility is defined as maximum infeasibility of its roads.

3 The basic VRP and incorporating expert data

In the beginning, as a basic task, we examine the following well-known problem of optimal routing of vehicles. Let the set of geographical points (customers) $I=\left\{1,\hspace{0.33em}2,\hspace{0.33em}\dots \hspace{0.33em},\hspace{0.33em}n+1\right\}$ be given, where the $n+1$-th point is a depot. Customers are supplied from the depot by vehicles with uniform goods. The demands of goods from customers are known, as well as maximum load and mileage of the vehicles. The specifics of the problem (type of distribution network) influences the maximum distance of the vehicle, but generally, we can assume that the maximum distance for the vehicle is the distance the vehicle (with a full tank) or a driver can cover in the given situation. The problem consists of the following: The goods should be delivered to the customers so that the overall mileage of the vehicles is minimal. It is meant that the demand for goods by each customer is much less than the maximum load of vehicles.

Suppose that $Q$ and $D$ are real numbers—consequently the constraints of maximum load and mileage of the vehicles. Let ${E}_{p}$,$p=1,\hspace{0.33em}2,\hspace{0.33em}..,\hspace{0.33em}n$, represent the demands for goods by p-th customer $0<{E}_{p}<Q$,$p=1,\hspace{0.33em}2,\hspace{0.33em}..\hspace{0.33em},\hspace{0.33em}n$, and be also real numbers. $\Vert {\rho }_{pq}\Vert$,$p,q\in I$, is a matrix of non-negative real numbers and represents the distances between customers.

We have to figure out such closed routes $\bar{M} = \left\{ {M_{k} } \right\}$, $k=1,\hspace{0.33em}2,\hspace{0.33em}\dots \hspace{0.33em},\hspace{0.33em}m$, ${M}_{k}=\left\{\hspace{0.33em}n+1,\hspace{0.33em}{p}_{1}^{k},\hspace{0.33em}\dots \hspace{0.33em},\hspace{0.33em}{p}_{{\mathcal{l}}_{k}}^{k},\hspace{0.33em}n+1\right\}$, where${p}_{j}^{k}\in \left\{\hspace{0.33em}1,\hspace{0.33em}2,\hspace{0.33em}\hspace{0.33em},..\hspace{0.33em}n\right\}$,$j=1,\hspace{0.33em}..\hspace{0.33em},\hspace{0.33em}{\mathcal{l}}_{k}$, ${\mathcal{l}}_{k}\in \{1,..,n\}$ ($m$ and ${\mathcal{l}}_{k}$ are not fixed beforehand), which comply with the following constraints.

$$\bigcup \limits_{k=1}^{m}{M}_{k}=I; {M}_{k}\cap {M}_{s}=\left\{\hspace{0.33em}n+1\right\},$$

$$k,\hspace{0.33em}s\in \left\{\hspace{0.33em}1,\hspace{0.33em}2,\hspace{0.33em}..\hspace{0.33em},\hspace{0.33em}m\hspace{0.33em}\right\},\hspace{1em}k\ne s; \sum \limits _{j=1}^{{\mathcal{l}}_{k}}{E}_{{p}_{j}^{k}}\le Q;$$

(1)

$${\text{Distance}}\,\left({M}_{k}\right)={\rho }_{n+1,\hspace{0.33em}{p}_{1}^{k}}\hspace{0.33em}+{\rho }_{{p}_{{\mathcal{l}}_{k}}^{k},\hspace{0.33em}n+1}+\sum \limits_{j=1}^{{\mathcal{l}}_{k}-1}{\rho }_{{p}_{j}^{k},\hspace{0.33em}{p}_{j+1}^{k}}\le D, k=1,\hspace{0.33em}..\hspace{0.33em},\hspace{0.33em}m;$$

and that have minimal total distance (objective function)

$${g}_{1}\equiv \sum \limits_{k=1}^{m}{\text{Dis}}{\text{tan}}{\text{c}}{\text{e}}\left({M}_{k}\right)= \sum \limits_{k=1}^{m}\left({\rho }_{n+1,\hspace{0.33em}{p}_{1}^{k}}\hspace{0.33em}+{\rho }_{{p}_{{\mathcal{l}}_{k}}^{k},\hspace{0.33em}n+1}+ \sum \limits_{j=1}^{{\mathcal{l}}_{k}-1}{\rho }_{{p}_{j}^{k},\hspace{0.33em}{p}_{j+1}^{k}}\right)\to min$$

(2)

The formulated problem represents a combinatorial optimization NP-hard problem (Bodin et al. 1983; Toth and Vigo 2002). The generalization of the VRP (1)-(2) for uncertain and extreme environments will be presented in Sect. 3.

Various difficulties and problems of movement inevitably lead to the imprecision and uncertainty of vehicle motion on the routes. For the VRPs presented in this work, when observing extreme conditions on roads, stochastic models may not work because the probability distributions of some input parameters are unknown due to their vague nature (an overview of the stochastic VRPs is presented in Oyola et al. (2016). These parameters include transport movement time, representing a total value of customer-to-customer movement times. Evaluating and considering the route reliability is also required when various obstacles can hinder the movement on the route. For a vehicle, let’s call an “admissible route” a closed route, which satisfies the restrictions of maximum distance and maximum capacity. If the vehicle is at customer $p$ of an admissible route, conditional probability distribution of shifting to customer $q$—${\left\{{P}_{pq}\right\}}_{q\in I\backslash \{p\}}$ is unknown, as well as time spent on moving. In extreme situations, it is impossible even to evaluate these distributions due to a lack of appropriate statistical data.

In the stated approach, we use expert knowledge to introduce the following input parameters:

• A. What will be an approximate time of motion of a vehicle from customer $p$ to customer $q$? Let us denote the value by ${\tilde{\tau }}_{pq}$. This is a characteristic of the first pole of the expert information—information imprecision;

• B. What is a possibility that a vehicle will not be able to move from customer $p$ to customer $q$? Let us denote this value by ${\pi }_{pq},0\le {\pi }_{pq}\le 1$. So, ${\left\{{\pi }_{pq}\right\}}_{pq,q\in I-\{p\}}$ reflect on the possible impediments on the roads. This is the second pole of expert information—information uncertainty;

We can generate approximate (fuzzy) times of movements between customers and depot points based on Google Maps Direction API, which gives approximate travel times. Google Maps service can also take into consideration the current traffic on the roads and provide approximate times based on that information. Generally, Google can provide three type of travel times:

• So called “best guess”: refers to the time that is the best regarding the estimates of average statistical and live stream of traffic;

• “Pessimistic”: refers to the time that exceeds the real motion time on most days, though accidental cases with particularly overloaded traffic may return greater value;

• “Optimistic”: refers to the time that does not exceed the real-time on most days, though accidental cases with particularly free traffic may return lesser value;

Based on these three values we can build a triangular fuzzy number (Dubois and Prade 1988), which will represent fuzzy times of movements between the points (customers, plus depot). The experts can modify ${\tilde{\tau }}_{pq}=(pessimistic,bestguess,optimistic)$ values for the roads, for which they will have information about the high traffic or other types of delays.

By default, values ${\pi }_{pq}$ can be set to zero (or to some small number) and experts can modify them for the routes, for which they will have information about the impediments. Usually, experts (e.g., distribution network dispatchers) provide ${\pi }_{pq}$ possibility values using some scale, convenient for them (e.g., 10-point grade scale—{1, 2, …, 10}) and later these values are normalized into [0, 1]. Based on experts’ knowledge reflections on a routing network in extreme conditions, an interactive simulation algorithm for generating a possibility distribution of movement see in Appendix A.

4 Construction of bi-criteria partitioning model for the new VRP

Assumption of fuzziness in the VRP under extreme conditions is a necessary action for modelers, because usually, there are insufficient objective input data, for the starting of classical or stochastic vehicle routing modeling. In extreme conditions, the complexity of the description of vehicles’ movement on routes may cause by two poles: the imprecision of time of movement and the uncertainty of the possibility of movement. Most of the existing researches of fuzzy vehicle routing modeling considers the imprecise nature of different parameters (transportation costs, movement time, service windows, etc.) by representing them as fuzzy values. Therefore, aggregation results, developed in such researches, contain only one pole of expert’s imprecision information. An efficient aggregation of information, contained in these two poles, in new objective functions, is the main goal of modern fuzzy vehicle routing modeling for the decreasing of decision-making risks in the optimal planning of routes network for humanitarian and other type aids from distribution centers to demand points.

It has been noted that most of the existing researches of FVRP (discussed in Sect. 1) considers the imprecise nature of different parameters (transportation costs, movement time, service windows, etc.) by representing them as fuzzy numbers. When the movement (travel) on routes is complicated due to different reasons, these fuzzy numbers represent only one pole of expert information—called information imprecision (Ghvaberidze and Machaidze 1989; Liu 2006). Thus, existing researches ignore the second pole of expert information—uncertainty, represented by a fuzzy (monotone) measure, in our case a possibility measure (Sirbiladze 2013; Wang and Klir 2009). It is important to consider uncertainty when we introduce expert judgment of the possibility of vehicle movement on routes in FVRP models. This is the primary reason why the existing FVRP models are less reliable for optimal route planning in extreme conditions on the roads. This was revealed during the research of fuzzy covering and fuzzy partitioning problems in uncertain and extreme environments performed by the authors of this paper (Sirbiladze 2013; Sirbiladze et al. 2009, 2014a, b, c, 2010a, b, 2011).

Considering both poles of expert information—imprecision and uncertainty, we can construct a new criterion for VRPs in extreme environments. The criterion will serve for minimizing the infeasibility of timely movement on the routes. It gives preference to those routes which are more realistic than the others.

As stated above, different impediments on the roads can be described by two parameters: fuzzy time of movement and possibility of failure of movement between points. Let $\tilde{T }=\{{\tilde{\tau }}_{pq}\}$ be the matrix of triangular fuzzy numbers—fuzzy times of movement from customer $p$ to customer $q$ and $\Pi =\{{\pi }_{pq}\}$ be the matrix of possibility levels of failure of movement from customer $p$ to customer $q$ in extreme conditions on the roads $(p,\,q\, \in \,\{ 1,\,2,\,...,\,n\, + \,1\} )$.

Suppose, that the expert evaluation of the movement time from customer $p$ to customer $q$ is represented by the positive triangular fuzzy number ${\tilde{\tau }}_{pq}=\left({\tau }_{pq}^{1},\hspace{0.33em}{\tau }_{pq}^{2},\hspace{0.33em}{\tau }_{pq}^{3}\right)$, the membership function of which is defined by the following formula (Dubois and Prade 1988):

$${\mu }_{{\tilde{\tau }}_{pq}}(t)=\left\{\begin{array}{l}0 ;\, t\le {\tau }_{pq}^{1}\\ \frac{t-{\tau }_{pq}^{1}}{{\tau }_{pq}^{2}-{\tau }_{pq}^{1}} ;\,{\tau }_{pq}^{1}<t\le {\tau }_{pq}^{2}\\ \frac{{\tau }_{pq}^{3}-t}{{\tau }_{pq}^{3}-{\tau }_{pq}^{2}}, ;\, {\tau }_{pq}^{2}<t\le {\tau }_{pq}^{3}\\ 0 ;\, t\ge {\tau }_{pq}^{3}\end{array}\right.$$

(3)

The closed route turns to be feasible if the difference between the expected travel time and the planned one is minimal. Simply saying, when the delay is minimal. This factor will be used in constructing the second criterion within the framework of this paper—minimizing the infeasibility of vehicle movement on closed routes.

With the consideration that the bigger the speed of movement is, the smaller is the imprecision related to the timely movement between the points (customers and depot). We define the imprecision of movement time between customers $p$ and $q$ with the inverse value of the fuzzy movement speed:

$${\tilde{\psi }}_{pq}=\frac{1}{{\tilde{V }}_{pq}}=\frac{{\tilde{\tau }}_{pq}}{{\rho }_{pq}}.$$

Finally, the imprecision of movement time between customers $p$ and $q$ as a normalized value of ${\tilde{\psi }}_{pq}$ is defined as

$${\tilde{\delta }}_{pq}=\frac{{\tilde{\psi }}_{pq}}{{\tilde{\psi }}_{max}},$$

where ${\tilde{\psi }}_{max}^{\mathit{max}\left\{{\tilde{\psi }}_{pq}\right\}}$, $p,q\in \{{1,2,..,}n+ {1} \}$.

Let us also normalize the matrix of the possibility levels of failure of movement between customers $p$ and $q$ by using denominator ${\pi }_{Max}=\mathit{max}\{{\pi }_{pq}\}$, $p,q\in \{{1,2,..,}n+ {1} \}$, to satisfy the requirement $\underset{p,q}{max}\{{\pi }_{pq}\}=1$.

Let us assume $M=\left\{n+1,{p}_{1},{p}_{2},...,{p}_{k},n+1\right\}$ is some closed route and introduce the set of arcs of the route $M$, denoted by $A(M)$:

1	2	…	$k+1$
$n+1\to {p}_{1}$	${p}_{1}\to {p}_{2}$	…	${p}_{k}\to n+1$

We consider ${\tilde{\delta }}_{pq}$ and ${\pi }_{pq}$, $p,q\in \{{1,2,..,}n+ {1} \}$, quantities for each closed route $M$:

$$\left(\begin{array}{cccc}1& 2& ...& k+1\\ {\tilde{\delta }}_{1}={\tilde{\delta }}_{n+1,{p}_{1}}& {\tilde{\delta }}_{2}={\tilde{\delta }}_{{p}_{1},{p}_{2}}& ...& {\tilde{\delta }}_{k+1}={\tilde{\delta }}_{{p}_{k},n+1}\\ {\pi }_{1}={\pi }_{n+1,{p}_{1}}& {\pi }_{2}={\pi }_{{p}_{1},{p}_{2}}& ...& {\pi }_{k+1}={\pi }_{{p}_{k},n+1}\end{array}\right).$$

(4)

We say that a closed route $M$ is as feasible as small are both—${\tilde{\delta }}_{pq}$ (imprecision) and ${\pi }_{pq}$ (uncertainty) values. For the construction of the infeasibility level as aggregation information of the movement on the closed route, we use finite Choquet integral (Choquet 1954), which is one of the most stable aggregation tools for condensation of imprecision and uncertainty represented in expert data (Kandel 1978; Sirbiladze et al. 2019, 2018). Therefore, we use this aggregation operator for the definition of the infeasibility level of the movement on the closed route.

For the construction of the infeasibility level of the movement on the closed route, we should aggregate both poles of expert information: imprecision related to the movement fuzzy times between customers (${\tilde{\delta }}_{pq}$ values) and uncertainty related to the possible complications on the route between customers (${\pi }_{pq}$ values). Heuristic procedures of the generation of closed routes (see Sect. 4.1) usually create interactive chains of points (routes). Therefore, an aggregation function cannot be additive like mathematical expectation or other additive instruments. We use Choquet averaging aggregation operator (Choquet 1954) as a non-additive and monotone expectation operator (Kandel 1978). Choquet averaging aggregation operator not only considers the importance of the arguments or their ordered positions but also reflects the interactions between combinations of points (customers) on a closed route.

Definition 2

A fuzzy infeasibility level of the movement (FILM) on the closed route $M$ is a Choquet integral of the triangular fuzzy valued − ${\tilde{\delta }}_{pq}$ function relative to the possibility measure (denoted by ${g}_{\pi }$) defined by the possibility distribution ${\pi }_{M}\equiv \left\{{\pi }_{1},{\pi }_{2},...,{\pi }_{k+1}\right\}$:

$$IL\tilde{M }(M)=({\text{Ch}}){\int }_{A(M)}{\tilde{\delta }}_{M}d{g}_{\pi }={\sum }_{i=1}^{k+1}{\tilde{\delta }}_{i}^{*}\left[Pos({A}_{i}^{*}(M))-Pos({A}_{i+1}^{*}(M))\right]={\sum }_{i=1}^{k+1}{\tilde{\delta }}_{i}^{*}\left[{\mathit{max}}_{l=\overline{i,k+1}}\{{\pi }_{l}^{*}\}-{\mathit{ma}x}_{l=\overline{i+1,k+1}}\{{\pi }_{l}^{*}\}\right],$$

(5)

where $A(M)=\{{a}_{1},{a}_{2},...,{a}_{k+1}\}$ is the set of the arcs of closed route $M$, ${A}^{*}(M)=\{{a}_{1}^{*},{a}_{2}^{*},...,\hspace{0.33em}\hspace{0.33em}{a}_{k+1}^{*}\}$ is the permutation of elements of $A(M)$, which orders ${\tilde{\delta }}_{i}^{*}\equiv \tilde{\delta }({a}_{i}^{*})$ values of triangular fuzzy valued function ${\tilde{\delta }}_{M}$ in non-decreasing order; ${A}_{i}^{*}(M)\equiv \{{a}_{i}^{*},{a}_{i+1}^{*},...,\hspace{0.33em}\hspace{0.33em}{a}_{k+1}^{*}\}$, $A_{{k + 2}}^{*} (M) \equiv \phi$, ${\mathit{max}}_{l=\overline{k+2,k+1}}\{{\pi }_{l}^{*}\}\equiv 0$.

Since the 90 s of the past century, the min–max (pessimistic-optimistic, dual) type aggregation fuzzy technologies were introduced in the methods of expert data aggregations. In our case, for introducing a new criterion in FVRP for the construction of feasible closed routes in extreme conditions on the roads we use the min–max aggregation modeling.

Let $\overline{M}=\left\{{M}_{1},{M}_{2},...,\hspace{0.33em}\hspace{0.33em}{M}_{m}\right\}$ be the set of all admissible closed routes. Any of its subsets can be described with Boolean vector $x=\left\{{x}_{1},{x}_{2},...,{x}_{m}\right\}$, where.

$$ x_{j} = \left\{ {\begin{array}{*{20}l} {1,{\mkern 1mu} \mathop { \leftrightarrows }\limits^{{}} {\mkern 1mu} {\text{if}}{\mkern 1mu} M_{j} {\mkern 1mu} \in {\mkern 1mu} M^{\prime } } \hfill \\ {0,{\mkern 1mu} {\text{if}}{\mkern 1mu} M_{j} {\mkern 1mu} \notin {\mkern 1mu} M^{\prime } } \hfill \\ \end{array} ,~{\mkern 1mu} j{\mkern 1mu} = {\mkern 1mu} 1,{\mkern 1mu} ...{\mkern 1mu} ,{\mkern 1mu} m.} \right. $$

We can define the overall fuzzy infeasibility level of vehicle movement on the closed routes ${M}^{{\prime}}$ as a maximum of fuzzy infeasibility levels of its closed routes:

$$ IL\tilde{M}(M^{\prime}) = \mathop {\max }\limits_{{j = \overline{{1,m}} }} \{ IL\tilde{M}(M_{j} ) \cdot x_{j} \} . $$

(6)

Finally, let us define the bi-criteria partitioning problem on $\overline{M}$. In this problem we consider the partitioning of closed routes, satisfying two criteria: the total distance traveled and the fuzzy infeasibility of motion on these routes are minimal:

$$ g_{1} = \sum \limits_{{j = 1}}^{m} {\text{Distance}}\left( {M_{j} } \right) \cdot x_{j} \to \min , $$

$$ \tilde{g}_{2} = \mathop {\max }\limits_{{j = \overline{{1,m}} }} \left\{ {IL\tilde{M}\left( {M_{j} } \right) \cdot x_{j} } \right\} \to \min , $$

$$ \sum \limits_{{j = 1}}^{m} a_{{pj}} x_{j} = 1,p = 1,...,n, $$

$${x}_{j}\in \left\{{0,1}\right\},j=1,...,m,$$

(7)

where ${a}_{pj}=1$ if customer $p$ belongs to the route ${M}_{j}$, otherwise ${a}_{ij}=0$; $p=1,...,n$, $j=1,...,m$.

5 Generation of promising routes

During the last years, among many techniques applied to the solution of multi-objective problems some authors (Ehrgott 2005; Ehrgott and Gandibleux 2002; Jozefowiez et al. 2008a) discern three general groups: scalar methods, Pareto methods, and methods that are beyond these two groups. The first group consists of those methods which utilize intensive mathematical transformations, for example, a weighted linear aggregation. The second group consists of those methods which utilize a notion of Pareto dominance concerning the quality of a solution or comparison of solutions. The last group comprises those techniques which consider the different objectives independently. Our approach to the solution of the built BC-VRP belongs to the second group and to the class of two-phase strategies [classification by Laporte et al. (2000)]. We can observe similar methods of solving VRPs with partitioning problems in Renaud et al. (1996); Ropke and Cordeau (2009). The promising routes can be constructed in different ways. Here we present just one of the variants which is based on an analysis of customers’ demands and their locations.

The promising routes are formed as $n$ -dimensional binary vectors, in which the $p$-th component equals 1 if and only if point $p$ is included in the route.

Algorithm 1 Generating Promising Routes

Stage 1. Building individual routes.

• 1. For each point (customer) $p\in \{1,\hspace{0.33em}2,\hspace{0.33em}...\hspace{0.33em},\hspace{0.33em}n\}$ an individual route is constructed, which together with point $p$ may include the following points:

  • a. Points located in the close neighborhood either to the point $p$ or to the depot;

  • b. Points located on the shortest route between the point $p$ and the depot;

The route is being enriched with new points until one of the constraints (1) are violated;

Stage 2. Extension of the routes.

• 1. Extension #1. If satisfying constraints (1), the following type of routes are added to the set of promising routes:

  • a. $(n+1,\hspace{0.33em}p,\hspace{0.33em}n+1)$, $p\in \{1,\hspace{0.33em}2,\hspace{0.33em}..\hspace{0.33em},\hspace{0.33em}n\}$

  • b. $(n+1,\hspace{0.33em}p,\hspace{0.33em}q,\hspace{0.33em}n+1) p,q\in \{1,\hspace{0.33em}2,\hspace{0.33em}..\hspace{0.33em},\hspace{0.33em}n\}$, $p\ne q$

• 2. Extension #2. The following type of routes are included in the set of promising routes:

  • a. In every route, except the routes of type $(n+1,\hspace{0.33em}p,\hspace{0.33em}n+1)$, the point with the biggest demand is replaced with the points located in the close neighborhood to it if the constraints (1) are not violated;

Remark 1

After the new promising route is constructed, it is checked against the already existing promising routes. In case of coincidence, the route is rejected.

Remark 2

For finding the optimal tour on the route (order of visiting the points), the Traveling Salesman Problem (TSP) is solved for each generated promising route. As it is known, TSP is an NP-hard problem, but often in practical situations the number of points in a single route is not big, and finding the optimal solution quickly is not a problem.

Remark 3

The extension (1.a) guarantees the existence of at least one partitioning. We obtain a nonempty set of feasible solutions to the partitioning problem.

Construction of promising routes happens until their number exceeds some limit, fixed in advance, and is considered as a parameter of the algorithm. In Ghvaberidze et al. (1985) the practice showed that $5n$ could be taken as a value of the limit, where $n$ is the number of customers, but taking into account computers’ capabilities today, we can set a much bigger limit value.

6 ${\varvec{\varepsilon}}$-Constraint approach of solution of the constructed bi-criteria partitioning problem

After generating the promising routes, we have to solve the BCPP (7). Generally, for multi-objective optimization problems, we can rarely find the solutions which satisfy (minimize) all criteria simultaneously. Therefore, usually, we have to find in some sense compromise solutions. From here we consider real numbers as TFNs—$\xi =(\xi ,\xi ,\xi )$ and all following images of functions are considered as a lattice—${\Psi }^{+}$ and operations on numbers as operations on TFNs.

Below we consider the following problem:

$$g\left(x\right)=\left({g}_{1}\left(x\right),\hspace{0.33em}{g}_{2}\left(x\right)\right)\to min,$$

$$x\in X,$$

where $X$ is the set of all workable solutions for the partitioning problem, which means, the elements of $X$ satisfy the constraints given in (7).

Definition 3

$x*\in X$ is called an efficient solution, if there does not exist $x{^{\prime}}\in X$, for which ${g}_{i}(x{^{\prime}})\le {g}_{i}(x*),\hspace{0.33em}i=1,\hspace{0.33em}2;$ and where at least one inequality is strict.

Let $P(X)$ be the set of all Pareto-optimal solutions. Let $Y$ be the objective space—the image of the set $X$ with respect to $g:X\to ({\Psi }^{+}\times {\Psi }^{+})$.

Definition 4

The point $g*=({g}_{1}(x*),\hspace{0.33em}{g}_{2}(x*)),\hspace{0.33em}x*\in P(X)$ of the objective space is called non-dominated. The set of all non-dominated points is called Pareto front $P(Y)=g(P(X))$.

Definition 5

$x*\in X$ element is called a weakly efficient solution, if there doesn’t exist $x{^{\prime}}\in X$ such that ${g}_{i}(x{^{\prime}})<{g}_{i}(x*),\hspace{0.33em}i=1,\hspace{0.33em}2$.

Suppose that $S(X)$ is a set of all weakly efficient solutions. It is obvious that $P(X)\subset S(X)$. Let us also define two important points from the objective space—Ideal (${g}^{I}$) and Nadir (${g}^{N}$) points, which we use below:

$${g}^{I}=({g}_{1}^{I},\hspace{0.33em}{g}_{2}^{I})$$

where ${g}_{1}^{I}=\underset{g\in Y}{min}{g}_{1}$ and ${g}_{2}^{I}=\underset{g\in Y}{min}{g}_{2}$, and

$${g}^{N}=\left({g}_{1}^{N},\hspace{0.33em}{g}_{2}^{N}\right),$$

where $g_{1}^{N} = \mathop {\min }\limits_{{g \in Y}} \{ g_{1} :g_{2} = g_{2}^{I} \}$ and $g_{2}^{N} = \mathop {\min }\limits_{{g \in Y}} \{ g_{2} :g_{1} = g_{1}^{I} \}$.

These points define Ideal and Nadir bounds on the values of efficient solutions.

Various methods are being used in discrete optimization problems to find efficient solutions (Ehrgott and Gandibleux 2002). Branch and bound type algorithms are among them. For solving the minimum covering problem in Ehrgott (2005), a well-known weighted sum scalarization method is used, which solves different single objective sub-problems generated by a linear scalarization of the multiple objectives. Therefore, we solve the sub-problems having an objective function $\alpha {g}_{1}+(1-\alpha ){g}_{2}$, $\alpha \in [0,\hspace{0.33em}1]$. However, this method has some disadvantages:

• 1. In the general case, the method cannot generate exact Pareto front (although it should be mentioned, that in practical situations, the number of Pareto-optimal solutions is big and we do not always need to generate all of them);

• 2. We can get the same solutions for different values of $\alpha$, which means computational inefficiency of the method;

• 3. It is necessary to have all objective functions scaled to a common scale (switch to dimensionless values) before forming the weighted sum (scalarized single objective function);

In this paper, for solving problem (7), we use the approach utilizing $\varepsilon$ -constraint method (Bérubé et al. 2009), which is reputed to be fine in a solution of multi-objective combinatorial optimization problems. By transforming all but one objective into constraints this method creates $\varepsilon$-constraint problems, which represent single objective sub-problems. The upper bounds of these constraints are given by the $\varepsilon$-vector and, by varying it, the exact Pareto front can theoretically be generated. However, in real-world cases, the number of sub-problems may be large and construction of the efficient scheme of variation for $\varepsilon$-vector may be difficult, therefore, generally speaking, it is hard to find exact Pareto front and heuristic schemas are used (Bérubé et al. 2009). But, as we will see later, in certain cases, such as bi-criteria optimization problems, $\varepsilon$-constraint method can generate the exact Pareto front.

There are optimization problems where $\varepsilon$-constraint method was effectively applied, such as a set partitioning problem (SPP) (Ehrgott and Ryan 2000), a special class of the TSP (Bérubé et al. 2009), facility location problem (Leitner et al. 2015). In Mavrotas (2009) the author presents a successful application of the $\varepsilon$-constraint method for multi-criteria optimization problems and shows how we can avoid generating weakly efficient solutions.

Let us discuss $\varepsilon$-constraint method for problem (7) in detail. In a bi-criteria optimization problem, the idea of the method is to minimize one of the objective functions, while the second objective function is transformed into a constraint with some $\varepsilon$ parameter. By varying the $\varepsilon$ parameter and solving the corresponding sub-problems, we obtain weakly efficient solutions. And in the case of the uniqueness of the solution, efficiency (Pareto-optimality) of the solution is guaranteed (Bérubé et al. 2009; Ehrgott 2005). Depending on the choice of criteria, which will be transformed into constraint, we can get the following two sub-problems:

$$ g_{k} \left( x \right) \to \min , $$

$${g}_{m}\left(x\right)\le {\varepsilon }_{k},$$

$$k,m=1,\hspace{0.33em}2;\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}k\ne m;\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}x\in X.$$

Let us denote these sub-problems by ${P}_{k}({\varepsilon }_{m})$. Therefore, for the bi-criteria problem we have two sub-problems: ${P}_{1}({\varepsilon }_{2})$ and ${P}_{2}({\varepsilon }_{1})$.

Let us now consider the algorithm for finding the Pareto front of bi-criteria optimization problems with integer arguments. In this algorithm, a sequence of $\varepsilon$ -constraint problems are solved, where $\varepsilon$ is decreased by a constant value $\Delta$. Setting $\Delta =1$ guarantees that in the case of integer objective values no solution will be missed. The correctness of the algorithm is proved in Bérubé et al. (2009). Let us note that if objective functions don’t have integer values (as in the case of (7)), we can apply $1{0}^{k}$ type multiplier, where the value of $k$ depends on the needed precision of the objective function’s values.

Algorithm 2 Exact Pareto Front of Bi-criteria Optimization Problems with Integer Objective Values

• 1. Compute the Ideal and Nadir points;

• 2. Set $k=1,\hspace{0.33em}m=2$ or $k=2,\hspace{0.33em}m=1$;

• 3. Set $P(Y)=\{({g}_{k}^{I},{g}_{m}^{N})\}$ and ${\varepsilon }_{m}={g}_{m}^{N}-\Delta \hspace{0.33em}\hspace{0.33em}\hspace{0.33em}(\Delta =1)$;

• 4. While ${\varepsilon }_{m}\ge {g}_{m}^{I}$, do:

  • a. Solve the sub-problem ${P}_{k}({\varepsilon }_{m})$ through branch and cut method and add the optimal solution value $({g}_{k}*,{g}_{m}*)$ to $P(Y)$;

  • b. Set ${\varepsilon }_{m}={g}_{m}*-\Delta$;

• 5. Remove dominated points from $P(Y)$ if required.

The step #5 is needed since some dominated points might be found throughout this procedure: there might exist many solutions to ${P}_{i}({\varepsilon }_{j})$ with different values for the objective function $j$. Generally, we have two options for removing dominated solutions:

• (a) Since all non-dominated points will be found after algorithm stops, we can simply exclude the non-efficient solutions to obtain the exact Pareto front;

• (b) We can solve both sub-problems ${P}_{1}({\varepsilon }_{2})$ and ${P}_{2}({\varepsilon }_{1})$ at every iteration of the algorithm. It is shown by Chankong and Haimes (1983), that in this case we obtain Pareto-optimal solution;

Although option (b) guarantees Pareto-optimality and quantity of sub-problems is reduced to the exact quantity of points on the Pareto front, these sub-problems may be more complicated and often require more computational time as compared to the option (a).

Since we use branch and bound type algorithm in single objective optimization problems, ε-constraint method fits our multi-objective optimization problem (7) particularly well since it adds new constraints to a branch and bound procedure and this is quite natural because it often decreases the size of the search tree.

Our algorithm is built on Knuth’s “DLX” algorithm (2000) and uses DLX technique, which effectively consumes computer memory. This is achieved by using the dynamic memory data structures, which allows us to remove and restore the elements very easily and quickly, without creating the copy of the whole data. So, during the navigation in a search tree, we do not have to copy and save the entire state for backtracking at each level, which might also be quite time-consuming.

The modified variant of DLX algorithm offered in this work solves MCPP and MCCP, it can be parallelized and distributed on a multiple-processor platform. Proceeding from this algorithm, we built a new algorithm for the ε-constraint method, where the exact Pareto front can be generated for integer-valued BCPP.

We have made slight modification to our algorithm to exclude dominated solutions: For the partitioning problems with a single objective function (single criterion), our algorithm finds all optimal solutions. This is implemented in the following way: if the objective function’s value on the current solution equals the objective function’s value on the saved optimal solution(s), the current solution is added to the set of saved optimal solutions. Obviously, if the current solution gives a better value for the objective function, the set of saved optimal solutions is emptied and the current solution is saved as the optimal solution. We can effectively modify the algorithm for the ε-constraint method in a way, that it will not save dominated solutions and it will output Pareto-optimal solutions only: on the step, where we compare the objective function’s value on the current solution to the objective function’s value on the saved optimal solution(s), if we find that the values are equal, we are comparing the values of the second objective function on the same solutions and we keep the solution,, which assigns better value to it.

For the convenient and simple presentation of the new FVRP methodology the Scheme 1 is constructed.

Scheme 1

The scheme of the FVRP methodology

7 An illustrative example

For illustration purpose we present an example, which is based on test data from TSPLIB (online library of sample instances for different combinatorial optimization problems). Our example has 18 customers (labeled “1”, “2”, …, “18”) and a depot (labeled “19”). The demand for goods for each customer is given in Table 1. The matrix of distances between the points (customers, depot) is shown in Table 2. The constraints of maximum capacity and maximum mileage for the vehicles are $Q=100$ and $D=200$, respectively.

Table 1 Customers’ demands—$\{{E}_{p}\}$

Table 2 The matrix of distances—$\{{\rho }_{pq}\}$

Let us solve the VRP with the input data given above, considering only the first, classic criterion of minimizing total distance traveled (${g}_{1}$) and also satisfying the constraints. As discussed in Sect. 4.1, we should generate at least $5n=5\cdot 18=90$ promising routes to get reasonable solutions, so let u generate 90 promising routes following the procedures given in Sect. 4.1. After generating the promising routes, we can solve the single-criterion partitioning problem and find the solution, which minimizes the total distance traveled while visiting each of the customers and delivering demanded goods. We get the following optimal solution:

Total distance (${g}_{1}$): 288. Closed routes: (1) 19-11-14-12-3-17-16-8-19; (2) 19-18-5-13-15-9-7-19; (3) 19-4-10-2-6-19; (4) 19-1-19;

Now let us imagine that there is information about some impediments on the central highway, which is part of the routes of the solution given above, with minimal total distance. Specifically, based on the information, there might be some obstacles on the roads between the customers 2 and 6, 4 and depot, 5 and 18, 11 and 14. Taking into account the information of routing network dispatcher (by the interactive Algorithm 3) the level of impossibility of a vehicle movement on the problematic road is equal to 0.9. Let us also generate the matrix of movement times, based on the matrix of distances, and apply some randomization factor (at this stage, let us assume, that the movement times are more or less proportional to the distances). So, having considered the matrix of approximate movement times given in Table 3 and the matrix of possibilities of road impasses given in Table 4 and, using the formula (6), and calculating the infeasibility level of the solution given above (${g}_{2}$), we get the value 0.836853, which indicates on a large risk of ability to implement the solution in practice.

Table 3 The matrix of fuzzy travel times (parts 1 and 2)—$\{{\tilde{\tau }}_{pq}\}$

Table 4 The matrix of possibility levels of movement failure (impossibilities of movement)—$\{{\pi }_{pq}\}$

As seen in the Table 4, small possibilities (with the value 0.1) are taken for the roads for which there is no information about impediments. This is done in order to avoid vanishing second multipliers in the sum of formula (5), which would cause ignoring the information contained in the first multipliers (${\tilde{\delta }}_{i}^{*}$) of the same sum. Instead of 0.1 one can take any small value greater than zero (e.g., 0.001).

The same problem (given in Tables 1, 2, 3 and 4) as bi-criteria optimization problem (7) may have other solutions, with smaller infeasibility levels of movement on the routes, which means smaller risks of implementation failure of these solutions. For example, the following solution has a bit longer total distance, but much better feasibility level of movement:

Total distance: ${g}_{1}$=306. Expectation of fuzzy Infeasibility level: ${g}_{2}$=0.101117. Closed routes: (1) 19-10-8-16-17-3-12-14-19; (2) 19-11-4-1-6-18-19; (3) 19-2-19; (4) 19-5-13-15-9-7-19;

Actually, this solution, as well as the previous one, is Pareto-optimal solution.

And finally, one can see what will be the complete Pareto front when some impediments are expected not only on the above mentioned four roads, but on others too. For this reason, let us replace Tables 4 with 5, which has more possible impediments on the roads. Now, solving the problem by the new approach and generating again 90 promising routes, we get the Pareto front, presented on Fig. 1.

Table 5 The matrix of possibility levels of movement failure (impossibilities of movement)—$\{{\tilde{\delta }}_{pq}\}$

Fig. 1

Objective space and Pareto front (${g}_{1}$, ${g}_{2}$)

Below, one may observe the closed routes for each Pareto-optimal solution, presented on Fig. 1.

Solution #1: Total distance: ${g}_{1}$=288. Expectation of fuzzy infeasibility level: ${g}_{2}$=0.833292. Closed routes: (1) 19-11-14-12-3-17-16-8-19; (2) 19-18-5-13-15-9-7-19; (3) 19-4-10-2-6-19; 4) 19-1-19;

Solution #2: Total distance: 294. Expectation of fuzzy infeasibility level: 0.640664. Closed routes: (1) 19-11-14-12-3-17-16-8-19; (2) 19-6-19; (3) 19-7-2-10-4-1-19; (4) 19-9-15-13-5-18-19;

Solution #3: Total distance: 297. Expectation of fuzzy infeasibility level: 0.612624. Closed routes: (1) 19-3-17-16-8-2-19; (2) 19-6-19; (3) 19-9-15-13-5-18-19; (4) 19-7-10-12-14-11-4-1-19;

Solution #4: Total distance: 307. Expectation of fuzzy infeasibility level: 0.587578. Closed routes: (1) 19-14-12-3-17-16-8-19; (2) 19-5-2-10-11-4-1-19; (3) 19-18-13-15-9-7-19; (4) 19-6-19;

Solution #5: Total distance: 363. Expectation of fuzzy infeasibility level: 0.528593. Closed routes: (1) 19-14-12-3-17-16-8-19; (2) 19-13-15-9-2-19; (3) 19-1-4-10-7-6-19; (4) 19-5-18-19; (5) 19-11-19;

Solution #6: Total distance: 487. Expectation of fuzzy infeasibility level: 0.473878. Closed routes: (1) 19-18-5-13-15-9-7-19; (2) 19-3-17-16-8-2-19; (3) 19-4-19; (4) 19-6-19; (5) 19-1-19; (6) 19-11-19; (7) 19-10-19; (8) 19-14-19; 9) 19-12-19;

Solution #7: Total distance: 519. Expectation of fuzzy infeasibility level: 0.442286. Closed routes: (1) 19-3-17-16-8-2-19; (2) 19-4-19; (3) 19-6-19; (4) 19-5-13-15-9-7-19; (5) 19-1-19; (6) 19-11-19; (7) 19-10-19; (8) 19-14-19; (9) 19-12-19; (10) 19-18-19;

The solutions were calculated in less than 0.5 s using desktop computer (Intel(R) Core (TM) i7 CPU 860 @ 2.80 GHz, 4 GB RAM). As mentioned above, for real-life scenarios much more promising routes can be generated and since the RAM consumed by the algorithm almost does not depend on the size of initial matrix of promising routes, it is just the matter of time for obtaining better results. The decision-maker person may define the waiting time, acceptable for him/her. For example, if the solutions should be calculated in 10 s maximum, then must be generated around 1000 promising routes and still solve the partitioning problem using the exact algorithm. This means that tens of millions of partitionings will be evaluated and the optimal ones will be selected.

As a final remark, we can admit that, after generating the promising routes, our algorithm of partitioning can be stopped any time and it will provide so called “current” optimal solution, based on already evaluated partitionings.

8 Conclusion

With the growth of complexity of a system, the system expert always looks for credible decisions about system behavior to reduce the uncertainty and conflicts between the objects. As a result, there is a need to handle the fuzziness in the classical models and use the fuzzy models under extreme conditions. This study aims to present a new possibilistic method for the VRP with complicated motion on the routes as stated in Eq. (7), which is an efficient tool for FVRP to minimize the decision-making risks the optimal planning of routes network. To address this, a new two-stage possibilistic bi-criteria optimization approach to solve the VRP is presented under extreme conditions. In the first stage, a new heuristic algorithm (in Algorithm 1) is created to generate the “promising routes” on the routing network. Hence, the conditional possibilities of vehicle movement are designed based on the efficient interactive Monte-Carlo simulation approach. The routing network’s dispatcher is included in the interactive regime (Algorithm 3, Appendix A). In the second stage, by utilizing the Choquet integral, two poles’ expert information—expected fuzzy times of vehicles’ movement on a closed route and impossibility of vehicles movement on a closed route are aggregated in this criterion. Together with the classic criterion, a new bi-criteria partitioning problem for the “promising” routes is defined and hence obtain their optimal solution by using $\varepsilon$—constraint approach. An exact parallel algorithm for the partitioning problem is implemented based on D. Knuth’s DLX technique and algorithm DLX. To demonstrate the working of stated approach, a numerical example has been considered in which optimal routes are constructed and compared for extreme conditions on the roads. Future studies plan to extend this approach for complex routing problems like VRP with time windows and q-rung orthopair triangular fuzzy environments. We also plan to use EDA (Estimation of Distribution Algorithm) approaches and combine it with the new exact algorithm for the cases of big distribution networks.

Appendices

Appendix A

Simulation algorithm for the evaluation of possibility levels of vehicle movement on closed routes

2.1 Introduction

The possibility theory is grounded on a fuzzy set notion (Dubois and Prade 1988; Zadeh 1978, 1965). A level of membership of an element in a set, as well as a level of possibility of the same element, can be any number of the unit interval [0, 1], and not only one of the two values {0,1} (Dubois and Prade 1988; Zadeh 1965).

The formalization of this definition has turned out very helpful in developing the principles of applied intelligent systems which model the knowledge of experts in various spheres of man’s activity. The theory of fuzzy sets and the related possibility theory are significant tools for the solution of these problems.

The aim is to create the method of generation of levels of possibilities of vehicle movement between the neighboring customers’ zones on routes network when the traffic is complicated by extreme processes or phenomena and also when the absence of past statistical data makes it impossible to obtain a probability distribution of vehicle movement from one customer to another customer. In such situations, stochastic analysis (and the more so an exact method) cannot be used for determining the optimal routes of vehicle movement. In that case, the possibility theory is applied when data on transport movement can be provided only by an expert. As different from stochastic or exact analysis, one of the advantages of the possibility theory consists in allowing us to simultaneously model the imprecision of expert’s incomplete information (in the form of a fuzzy set) and to quantitatively characterize the uncertainty of the same incomplete information (in the form of a pair of numbers: “possibility” and “necessity” (Dubois and Prade 1988).

The methodology is based on the use of the concept of level sets (Toth and Vigo 2002) induced by the possibility distribution (Dubois and Prade 1988) on the set of customers lying in the neighborhood of a given customer. We construct the process of definition of level sets (defined by experts or routes network’s dispatchers, managers, and so on), which, in its turn, will provide the generation of possibility levels for vehicle movement from a given customer to a neighboring customer. Finally, we obtain the matrix of possibilities of vehicle movement between the neighboring customers.

A matrix of movement possibilities

Often, in a large-scale customers’ network model, the construction of a movement possibility distribution will be reduced by determining a movement possibility distribution between zones created by customers with equal movement possibilities.

Let us assume that customers’ network can be divided into several disjoint zones, there in every such as zone movement possibilities able to be same equal level. Let ${Z}^{({z}_{o})}=\left\{{z}_{1},{z}_{2},...,{z}_{{n}_{o}}\right\}$ be the set of directly neighboring customers zones for some customers zone ${\text{z}}_{{\text{o}}}$ on the routes network. Denote by ${\pi }^{({z}_{o})}\left({z}_{i}\right)=\pi \left({z}_{i}\right)\equiv {\pi }_{i}$ the conditional possibility levels of vehicle movement from the customers’ zone $z_{o}$ to the customers’ zone ${z}_{i}\left(i={1,2},...,{n}_{o}\right)$. Without loss of generality, we may assume that the elements (zones) of the set ${Z}^{(z_{o})}$ are indexed so that $\pi \left({z}_{i}\right)\ge \pi \left({z}_{j}\right)$ if $i>j$ and $\pi \left({z}_{{n}_{o}}\right)=1$ (i.e., the movement from $z_{o}$ in${Z}^{({z}_{o})}$ occurs with a maximal possibility level equal to 1).

We get the distribution of possibilities on the set of customers zones—${Z}^{({z}_{o})}$. To this distribution, we may put into correspondence a fuzzy subset of the set ${Z}^{({z}_{o})}$ that contains all customers zones, where the level of possibilities of vehicle movement is equal at least to $\alpha \left(0<\alpha \le 1\right):{Z}_{\alpha }=\left\{z/z\in {Z}^{({z}_{0})},\pi \left(z\right)\ge \alpha \right\}$. Note that ${Z}_{{\alpha }_{2}}\supseteq {Z}_{{\alpha }_{1}}$ if ${\alpha }_{1}>{\alpha }_{2}$.

Before we describe the procedure of determining the levels of possibilities $0\le {\pi }_{1}\le {\pi }_{2}\le ...\le {\pi }_{{n}_{0}}=1$, we will discuss a random experiment, in which the notion of a level set ${Z}_{\alpha }$ is used. Then we can easily write the level sets.

for $0<\alpha \le {\pi }_{1},{Z}_{\alpha }=\left\{{z}_{1},{z}_{2},...,{z}_{{n}_{o}}\right\}\equiv {Z}_{1},$

for ${\pi }_{1}<\alpha \le {\pi }_{2},{Z}_{\alpha }=\left\{{z}_{2},...,{z}_{{n}_{o}}\right\}\equiv {Z}_{2},$

for ${\pi }_{2}<\alpha \le {\pi }_{3},{Z}_{\alpha }=\left\{{z}_{3},...,{z}_{{n}_{o}}\right\}\equiv {Z}_{3},$

…………………………………

for ${\pi }_{{n}_{o}-2}<\alpha \le {\pi }_{{n}_{o}-1},{Z}_{\alpha }=\left\{{z}_{{n}_{o}-1},{z}_{{n}_{o}}\right\}\equiv {Z}_{{n}_{o}-1},$

for ${\pi }_{{n}_{o}-1}<\alpha \le {\pi }_{{n}_{o}}=1,{Z}_{\alpha }=\left\{{z}_{{n}_{o}}\right\}\equiv {Z}_{{n}_{o}}.$

In the experiment, the values for $\alpha$ are chosen randomly (with uniform distribution on $\left({0,1}\right)$). Then the probability that one of the customers of the set ${Z}_{j}$ will be chosen as a point to which vehicle will move from the initial customers’ zone $z_{o}$ equals $P\left({Z}_{j}\right)={\pi }_{i}-{\pi }_{i-1},j={1,2},...,{n}_{o};\left({\pi }_{o}\equiv 0\right)$.

We suppose that in the process of construction of a closed route the choice of some customers’ zone ${z}_{i}$ from the set ${Z}_{j}$ is directly proportional to the inverse value of the expectation of movement fuzzy time between the customers’ zones $z_{o}$ and ${z}_{i}$. We denote this value by ${e}_{i}\equiv {E}^{Pos}({\tilde{\tau }}_{ij})$. Then to define these probabilities we use the definition of geometrical probability.

$$P\left({z}_{i}/{Z}_{j}\right)\equiv P\left\{\text{customers zone}\right.{z}_{i}\hspace{0.33em}is\hspace{0.33em}chosen\hspace{0.33em}for\hspace{0.33em}the\hspace{0.33em}movment/{Z}_{j}\}=\left\{\begin{array}{l}0,{z}_{i}\notin {Z}_{j}\\ \frac{{{e}_{i}}^{-1}}{{\sum }_{{z}_{k}\in {Z}_{j}}{{e}_{k}}^{-1}},{z}_{i}\in {Z}_{j}\end{array}\right..$$

(8)

For the construction of the next step of the generation method we need is necessary to introduce the definition of a body of evidence that is well known as an instrument for creating decision-making structures for expert data (Klir and Wierman 1999; Shafer 1976).

Definition 6

• (a) A Basic Probability Assignment (BPA) on ${Z}^{({z}_{o})}$ is a map $\text{m:}{2}^{{Z}^{({z}_{o})}}\to [\text{0;1}]$, fulfilling the conditions:

  • (i) $(i)$ $m(\mathrm{\varnothing })=0,$

  • (ii) ${\sum }_{D\subset Z}m(D)={1.}$

• (b) Every $D\in {2}^{{Z}^{({z}_{o})}}$ for which $m(D)>{ 0}$ is usually called a focal element of $m$. If $\mathfrak{I}$ denotes the set of all focal elements, then the pair $<\mathfrak{I},m>$ is called a Body of Evidence.

Definition 7

Let $m$ be a BPA on ${Z}^{({z}_{o})}$. The plausibility $Pl$ and belief Bel measures associated to $m$ are given by the formulas.

$$ Pl(D) = \sum _{{D \cap L \ne \O ,{}L \in \Im }} m(L),Bel(D) = \sum _{{L \subset D,{}L \in \Im }} m(L),\quad \forall D \in 2^{{X(x_{0} )}} . $$

The relationship between $m(D)$ and $Bel(D)$ consists in the following—while $m(D)$ describes the degree of evidence or belief that the element in consideration belongs to the set $D$ alone (i.e. exactly to set $D$), $Bel(D)$ denotes the total evidence of the belief that the element belongs to D, as well as to many special subsets of $D$. The plausibility measure $Pl(D)$ has a different sense: it characterizes not only the total evidence or belief that the element in question belongs to set $D$ or to any of its subsets, but also the additional evidence or belief associated with sets that overlap with $D$. Hence $Pl(D)\ge Bel(D)$.

As a result, the set sequence ${Z}^{{z}_{0}}={Z}_{1}\supset {Z}_{2}\supset ...\supset {Z}_{{n}_{o}-1}\supset {Z}_{{n}_{o}}$ creates the embedded consonant structure (Klir and Wierman 1999) of focal elements with the Basic Probability Assignment:

$$m\left({Z}_{j}\right)={\pi }_{j}-{\pi }_{j-1},j=1,..,{n}_{o};{\pi }_{o}=0.$$

(9)

It is known (Klir and Wierman 1999) that for the consonant structure the plausibility measure is a possibility one. Using the structure of focal elements in the role of a complete system of events and applying the formula of a complete probability, we define the probability that the customers’ zone ${z}_{i}:{z}_{i}\in {Z}^{({z}_{o})}$ will be chosen as the customers’ zone to which vehicle will move from the customers’ zone $z_{o}$.

$$ P\left( {z_{i} } \right) \equiv P\left( {{\text{Customers}}\,{\text{zone}}\,z_{i} \,{\text{is}}\,{\text{chosen}}\,{\text{for}}\,{\text{the}}\,{\text{movement}}} \right)\, = \,\sum \limits_{{j = 1}}^{{n_{o} }} P\left( {\frac{{z_{i} }}{{Z_{j} }}} \right) \cdot m\left( {Z_{j} } \right). $$

(10)

It is a priori assumed that when the vehicle movement transfer takes place in extreme conditions, the probabilities of movement transfer (10) from one customers zone to another become unknown values, which can be estimated only using an expert’s knowledge of a possibility of transfer of vehicle movement to the direct neighboring customers’ zones.

Using formulas (10), we can calculate the probabilities $P\left({z}_{i}\right)$ of such transfer:

$$ \begin{gathered} P\left( {z_{1} } \right) = \frac{{e_{1}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{1} }} e_{j}^{ - 1} }} \cdot \pi_{1} ; \hfill \\ P\left( {z_{2} } \right) = \frac{{e_{2}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{1} }} e_{j}^{ - 1} }} \cdot \pi_{1} + \frac{{e_{2}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{2} }} e_{j}^{ - 1} }} \cdot \left( {\pi_{2} - \pi_{1} } \right); \hfill \\ P\left( {z_{3} } \right) = \frac{{e_{3}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{1} }} e_{j}^{ - 1} }} \cdot \pi_{1} + \frac{{e_{3}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{2} }} e_{j}^{ - 1} }} \cdot \left( {\pi_{2} - \pi_{1} } \right) + \frac{{e_{3}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{3} }} e_{j}^{ - 1} }} \cdot \left( {\pi_{3} - \pi_{2} } \right); \hfill \\ \end{gathered} $$

(11)

$$P\left({z}_{{n}_{o}-1}\right)=\frac{{e}_{{n}_{o}-1}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{1}}{e}_{j}^{-1}}\cdot {\pi }_{1}+\frac{{e}_{{n}_{o}-1}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{2}}{e}_{j}^{-1}}\cdot \left({\pi }_{2}-{\pi }_{1}\right)+...+\frac{{e}_{{n}_{o}-1}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{{n}_{o}-1}}{e}_{j}^{-1}}\cdot \left({\pi }_{{n}_{o}-1}-{\pi }_{{n}_{o}-2}\right);$$

$$P\left({z}_{{n}_{o}}\right)=\frac{{e}_{{n}_{o}}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{1}}{e}_{j}^{-1}}\cdot {\pi }_{1}+\frac{{e}_{{n}_{o}}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{2}}{e}_{j}^{-1}}\cdot \left({\pi }_{2}-{\pi }_{1}\right)+...+\frac{{e}_{{n}_{o}}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{{n}_{o}-1}}{e}_{j}^{-1}}\cdot \left({\pi }_{{n}_{o}-1}-{\pi }_{{n}_{o}-2}\right)+\frac{{e}_{{n}_{o}}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{{n}_{o}}}{e}_{j}^{-1}}\cdot \left({\pi }_{{n}_{o}}-{\pi }_{{n}_{o}-1}\right).$$

One may easily verify that (11) is a probabilistic distribution on the set ${X}^{({x}_{o})}$. Therefore

$$P\left({z}_{1}\right)+P\left({z}_{2}\right)+P\left({z}_{3}\right)+...+P\left({z}_{{n}_{o}-1}\right)+P\left({z}_{{n}_{o}}\right)==\frac{1}{{\sum }_{{z}_{j}\in {Z}_{1}}{e}_{j}^{-1}}\cdot \left({e}_{1}^{-1}+{e}_{2}^{-1}+..+{e}_{{n}_{o}}^{-1}\right)\cdot {\pi }_{1}+ \frac{1}{{\sum }_{{z}_{j}\in {Z}_{2}}{e}_{j}^{-1}}\cdot \left({e}_{2}^{-1}+{e}_{3}^{-1}+..+{e}_{{n}_{o}}^{-1}\right)\cdot \left({\pi }_{2}-{\pi }_{1}\right)+\frac{1}{{\sum }_{{z}_{j}\in {Z}_{3}}{e}_{j}^{-1}}\cdot \left({e}_{3}^{-1}+..+{e}_{{n}_{o}}^{-1}\right)\cdot \left({\pi }_{3}-{\pi }_{2}\right)+..+\frac{1}{{\sum }_{{z}_{j}\in {Z}_{{n}_{o}-1}}{e}_{j}^{-1}}\cdot \left({e}_{{n}_{o}-1}^{-1}+{e}_{{n}_{o}}^{-1}\right)\cdot \left({\pi }_{{n}_{o}-1}-{\pi }_{{n}_{o}-2}\right)+\frac{1}{{\sum }_{{z}_{j}\in {Z}_{{n}_{o}}}{e}_{j}^{-1}}\cdot {e}_{{n}_{o}}^{-1}\cdot \left({\pi }_{{n}_{o}}-{\pi }_{{n}_{o}-1}\right)= {\pi }_{1}+\left({\pi }_{2}-{\pi }_{1}\right)+\left({\pi }_{3}-{\pi }_{2}\right)+...+\left({\pi }_{{n}_{o}-1}-{\pi }_{{n}_{o}-2}\right)+\left({\pi }_{{n}_{o}}-{\pi }_{{n}_{o}-1}\right)={\pi }_{{n}_{o}}=1.$$

The probabilistic distribution (11) can also be rewritten in a simple recurrent form

$$ \begin{gathered} P\left( {z_{1} } \right) = \frac{{e_{1}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{1} }} e_{j}^{ - 1} }} \cdot \pi_{1} ; \hfill \\ P\left( {z_{2} } \right) = \frac{{e_{2}^{ - 1} }}{{e_{1}^{ - 1} }} \cdot P\left( {z_{1} } \right) + \frac{{e_{2}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{2} }} e_{j}^{ - 1} }} \cdot \left( {\pi_{2} - \pi_{1} } \right); \hfill \\ P\left( {z_{3} } \right) = \frac{{e_{3}^{ - 1} }}{{e_{2}^{ - 1} }} \cdot P\left( {z_{2} } \right) + \frac{{e_{3}^{ - 1} }}{{\mathop \sum \nolimits_{{z_{j} \in Z_{3} }} e_{j}^{ - 1} }} \cdot \left( {\pi_{3} - \pi_{2} } \right); \hfill \\ \end{gathered} $$

(12)

$$P\left({z}_{{n}_{o}-1}\right)=\frac{{e}_{{n}_{o}-1}^{-1}}{{e}_{{n}_{o}-2}^{-1}}\cdot P\left({z}_{{n}_{o}-2}\right)+\frac{{e}_{{n}_{o}-1}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{{n}_{o}-1}}{e}_{j}^{-1}}\cdot \left({\pi }_{{n}_{o}-1}-{\pi }_{{n}_{o}-2}\right);$$

$$P\left({z}_{{n}_{o}}\right)=\frac{{e}_{{n}_{o}}^{-1}}{{e}_{{n}_{o}-1}^{-1}}\cdot P\left({z}_{{n}_{o}-1}\right)+\frac{{e}_{{n}_{o}}^{-1}}{{\sum }_{{z}_{j}\in {Z}_{{n}_{o}}}{e}_{j}^{-1}}\cdot \left({\pi }_{{n}_{o}}-{\pi }_{{n}_{o}-1}\right).$$

Description of a Monte-Carlo simulation for the evaluation of possibility levels of vehicle movement on the routes

The real problem, in the solution of which we are interested, occurs when the possibility levels are not given by experts and the problem exists only in terms of an expert who evaluates ${\pi }_{1}\le {\pi }_{2}\le ...\le {\pi }_{{n}_{o}}=1$.

The problem consists in trying to determine the possibility levels as a result of generating possibility levels in a random experiment. Using the results of the preceding section, we can construct a consistent method of generation of possibility levels.

Let us express the possibility levels ${\pi }_{i}$ via the probabilities $P\left({Z}_{j}\right)$. From system (12), after algebraic transformations, we obtain

$$ \begin{gathered} \pi_{1} = \frac{{\mathop \sum \nolimits_{{z_{j} \in Z_{1} }} e_{j}^{ - 1} }}{{e_{1}^{ - 1} }} \cdot P\left( {z_{1} } \right); \hfill \\ \pi_{2} = \frac{{\mathop \sum \nolimits_{{z_{j} \in Z_{2} }} e_{j}^{ - 1} }}{{e_{2}^{ - 1} }} \cdot P\left( {z_{2} } \right) + P\left( {z_{1} } \right); \hfill \\ \pi_{3} = \frac{{\mathop \sum \nolimits_{{z_{j} \in Z_{3} }} e_{j}^{ - 1} }}{{e_{3}^{ - 1} }} \cdot P\left( {z_{3} } \right) + P\left( {z_{2} } \right) + P\left( {z_{1} } \right); \hfill \\ \end{gathered} $$

(13)

$${\pi }_{{n}_{o}-1}=\frac{{\sum }_{{z}_{j}\in {Z}_{{n}_{o}-1}}{e}_{j}^{-1}}{{e}_{{n}_{o}-1}^{-1}}\cdot P\left({z}_{{n}_{o}-1}\right)+{\sum }_{j=1}^{{n}_{o}-2}P\left({z}_{j}\right); {\pi }_{{n}_{o}}=P\left({z}_{{n}_{o}}\right)+{\sum }_{j=1}^{{n}_{o}-1}P\left({z}_{j}\right)=1.$$

Recall that if $i>j$, then ${\pi }_{i}\ge {\pi }_{j}$. From system (13) we see that if we know the probabilities with which in the experiment described here the customers’ zones are chosen from ${Z}^{({z}_{o})}$, then this information can be used for determining the possibility levels. Therefore, if we know how to derive estimates for the probabilities contained in the right-hand parts of the equations of the system (12), then we can use these estimates for calculating the vehicle movement possibilities.

With customers zone ${z}_{i}$ we connect the value ${T}_{i}$, initially equal to zero, which will be equal to the number of occurrences of ${x}_{i}$ in the role of the sampling of customers zone from ${X}_{i}$.

Algorithm 3

• 1. Fix the initial customers zone $z_{o}$ and the set ${Z}^{({z}_{o})}$.

• 2. Determine the size of the sampling $M$ (e.g., $M=25,M=50,M=100$) needed for successful work.

• 3. Divide the unit interval into $M$ parts of equal length. For example, if $M=50$, we obtain $\left\{{1,0.98,0.9}6,....,0.02\right\}$. Denote this set by $S$.

• 4. Choose randomly without replacing an element $\alpha$ from $S$.

• 5. Ask the expert(s) (routing network’s dispatchers and so on), who determines the possibility levels of customers zone—to—customers zone vehicle movement, which are the zones from all zones ${Z}^{({z}_{o})}$ with movement from the initial customers’ zone $z_{o}$ at the chosen level $\alpha$.

• 6. If $k$ is the quantity of customers zones included in the level set, which is constructed in step 4, then for each occurrence of a new customers zone ${x}_{i}$ in the generation process, for this level we must add $\frac{{e}_{i}^{-1}}{{\sum }_{{z}_{s}\in {Z}_{k}}{e}_{s}^{-1}}$ to ${T}_{i}$; ${T}_{i}={T}_{i}+\frac{{e}_{i}^{-1}}{{\sum }_{{z}_{s}\in {Z}_{k}}{e}_{s}^{-1}}$.

• 7. Repeat steps 3–5 until all $\alpha$ from $S$ are used.

• 8. Calculate $P\left({Z}_{i}\right);P\left({Z}_{i}\right)=\frac{{T}_{i}}{M}$.

• 9. Arrange the obtained probability estimates in the increasing order and substitute them into (13). Calculate the levels of possibilities of the set of neighboring customers zones ${Z}^{({z}_{o})}$.

• 10. Repeat steps 0–8 for each customer $z,z\in I$ and determine all levels of possibilities in the customers’ zones distribution graph.

• 11. Form the matrix of vehicle movement possibilities for all customers zones—$\{{\pi }_{ij}\},i,j\in T,i\ne j$, and, therefore, form the matrix of vehicle movement possibilities for all customers on the routing network.

Numerical example

Let ${Z}^{({z}_{o})}=\left\{f,e,d,c,b,a\right\}$. Suppose that the expectations of fuzzy movement time from the initial customers’ zone $z_{o}$ to the customers’ zones of ${Z}^{({z}_{o})}$ are as follows:

$$ e_{a} = 1.5\,{\text{min}},\,e_{b} = 2.0\,{\text{min}},\,e_{c} = 3.0\,{\text{min}},\,e_{d} \, = \,1.5\,{\text{min}}, $$

$$ e_{e} = 3.5\,{\text{min}},e_{f} = 1.8\,{\text{min}}. $$

Based on experts’ knowledge, it is supposed that

$$0<\pi \left(f\right)\le \pi \left(c\right)\le \pi \left(a\right)\le \pi \left(e\right)\le \pi \left(b\right)\le \pi \left(d\right)=1.$$

Assume that the sampling size is $M=25$. Then $S=\left\{{1,0.96,0.92},....,{0.8,0.4}\right\}$.

Suppose that, choosing the values of the level randomly, we obtain from the expert the following level sets of neighboring customers zones (they can be obtained in the interactive mode):

$$ \begin{array}{*{20}l} {Z_{{0.92}} = \left\{ d \right\}} \hfill & {Z_{{0.04}} = \left\{ {f,a,c,de,b} \right\}} \hfill & {Z_{{0.56}} = \left\{ {e,d,b} \right\}} \hfill \\ {Z_{{0.60}} = \left\{ {e,d,b} \right\}} \hfill & {Z_{{0.68}} = \left\{ {e,d,b} \right\}} \hfill & {Z_{{1.00}} = \left\{ d \right\}} \hfill \\ {Z_{{0.36}} = \left\{ {c,a,b,d,e} \right\}} \hfill & {Z_{{0.24}} = \left\{ {c,a,b,d,e} \right\}} \hfill & {Z_{{0.28}} = \left\{ {e,a,c,b,d} \right\}} \hfill \\ {Z_{{0.32}} = \left\{ {c,a,e,b,d} \right\}} \hfill & {Z_{{0.76}} = \left\{ {b,d} \right\}} \hfill & {Z_{{0.16}} = \left\{ {c,a,b,d,e} \right\}} \hfill \\ {Z_{{0.72}} = \left\{ {d,b} \right\}} \hfill & {Z_{{0.52}} = \left\{ {e,d,b} \right\}} \hfill & {Z_{{0.20}} = \left\{ {c,a,b,d,e} \right\}} \hfill \\ {Z_{{0.44}} = \left\{ {a,b,d,e} \right\}} \hfill & {Z_{{0.40}} = \left\{ {c,a,b,d,e} \right\}} \hfill & {Z_{{0.48}} = \left\{ {a,b,e,d} \right\}} \hfill \\ {Z_{{0.88}} = \left\{ {d,b} \right\}} \hfill & {Z_{{0.12}} = \left\{ {c,e,d,b,a} \right\}} \hfill & {Z_{{0.96}} = \left\{ d \right\}} \hfill \\ {Z_{{0.08}} = \left\{ {f,c,d,b,a,e} \right\}} \hfill & {Z_{{0.80}} = \left\{ {d,b} \right\}} \hfill & {} \hfill \\ {Z_{{0.84}} = \left\{ {d,b} \right\}} \hfill & {Z_{{0.64}} = \left\{ {e,d,b} \right\}} \hfill & {} \hfill \\ \end{array} $$

Using the obtained answers of the process of intelligent simulation of the expert’s knowledge, we can calculate ${\varvec{T}}$ for each customer.

First, we compile Table 6 of the values of $P_{i/\,k} \equiv P(z_{i} /Z_{k} ) = \frac{{e_{i}^{ - 1} }}{{\sum\limits_{{z_{s} \in Z_{k} }} {e_{s}^{ - 1} } }}$, which depend on two indexes $i$ and $k$:

Table 6 Values of the set ${{\varvec{P}}}_{{\varvec{i}}/{\varvec{k}}}$

Then

$$ T_{a} = 2 \cdot 0.222 + 8 \cdot 0.271 + 2 \cdot 0.314 = 3.24\,\,\, \Rightarrow \,\,P\left( a \right) = \frac{{T_{a} }}{25} = 0.1296 $$

$$ T_{b} = 2 \cdot 0.167 + 8 \cdot 0.206 + 2 \cdot 0.238 + 5 \cdot 0.347 + 5 \cdot 0.431 = 6.348\,\,\, \Rightarrow \,\,P\left( b \right) = 0.2539 $$

$$ T_{c} = 2 \cdot 0.111 + 8 \cdot 0.135 = 1.302\,\,\, \Rightarrow \,\,P\left( c \right) = 0.0521 $$

$$ T_{d} = 2 \cdot 0.221 + 8 \cdot 0.272 + 2 \cdot 0.314 + 5 \cdot 0.458 + 5 \cdot 0.569 + 3 \cdot 1 = 11.381\,\,\, \Rightarrow \,\,P\left( d \right) = 0.4552 $$

$$ T_{e} = 2 \cdot 0.095 + 8 \cdot 0.116 + 2 \cdot 0.134 + 5 \cdot 0.195 = 2.361\,\,\, \Rightarrow \,\,P\left( e \right) = 0.0945 $$

$$T_{f} = 2 \cdot 0.184 = 0.368\,\,\, \Rightarrow \,\,P\left( f \right) = 0.0147$$

Substituting the obtained probability values into (13), we calculate the levels of possibilities of a vehicle movement from the customers’ zone ${{\varvec{z}}}_{{\varvec{o}}}$ to the customers’ zones $f,e,d,c,b,a$:

Let us compile the table of the values of $\frac{1}{{P}_{i/i}}=\frac{{\sum }_{{z}_{s}\in {Z}_{i}}{e}_{s}^{-1}}{{e}_{i}^{-1}}$ needed for calculation of the levels of possibilities in (13) (Table 7):

Table 7 Values of the set $\frac{1}{{{\varvec{P}}}_{{\varvec{i}}/{\varvec{i}}}}$

Then we obtain

$$ \pi_{f} = 5.434 \cdot 0.0147 = 0.0798 $$

$$ \pi_{c} = 7.407 \cdot 0.0521 + 0.0147 = 0.4006 $$

$$ \pi_{a} = 3.185 \cdot 0.1296 + 0.0147 + 0.0521 = 0.4796 $$

$$ \pi_{e} = 5.128 \cdot 0.0945 + 0.0147 + 0.0521 + 0.1296 = 0.6810 $$

$$ \pi_{b} = 2.320 \cdot 0.2539 + 0.0147 + 0.0521 + 0.1296 + 0.0945 = 0.8799 $$

$\pi_{c} = 1 \cdot 0.4552 + 0.0147 + 0.0521 + 0.1296 + 0.0945 + 0.2539 = 1$.

At the end of the example, we give the combined probability and possibility data for the zones $f,e,d,c,b,a$ (Table 8):

Table 8 Vehicle movement probabilities and possibilities

and the diagram of the neighboring customers of $z_{o}$ if the ranging of the choice of the customer was like this: $f\prec c\prec a\prec e\prec b\prec d$ (see Fig. 2).

Fig. 2

Diagram of customers zones in the neighborhood of $z_{o}$ with expectations of movement fuzzy time and possibilities

Remark 4

In this appendix, it is developed a simulation algorithm for the determination of the possibility levels of vehicle motion between the customers. These parameters define the possibility levels of failure of movement between customers.