Fermatean fuzzy vehicle routing problem with profit: solution algorithms, comparisons and developments

Abstract

In this work, a fermatean fuzzy vehicle routing problem with profits (FFVRPP) is considered. Fermatean fuzzy numbers are used to represent the various coefficients of the problem. The objectives of FFVRPP is to obtain a set of routes that originates and terminates at the source node while keeping in mind the objective function and route restriction constraints. The objective function here is to maximizes the difference between the profit function and the expense function. The route restriction constraints provides an upper bound on the number of customers that can be served in single visit of any vehicle. We propose two stage solution methodologies for solving FFVRPP where the first stage corresponds to the selection of subset of customers which gives the maximum profit and the second stage corresponds to formation of routes for the selected customers such that the expenses incurred in serving them comes out to be a minimum. The inclusion of qualitative factors like relationship of customers with the seller and the risk of transportation of goods across various edges with the help of fermatean fuzzy numbers makes the model more realistic and applicable in real life situations. Three different methodologies based on various clustering and routing algorithms are proposed to solve the problem. The feasibility and richness of the proposed algorithms is demonstrated with the help of a numerical example.

1 Introduction

Vehicle routing problem with profits (VRPP) is a well known extension of the vehicle routing problem which differs from classical problem in two different ways; a) the subset of customers to serve are to be selected, and b) the clustering of customers into various routes and ordering of customers into those routes is also performed. In general, a profit is associated with each customer which decides the attractiveness of the customer. So, any route which originates and terminates at depot node can be measured in terms of profit as well as that of cost. VRPPs have been used to model real-life problems and applications in a variety of areas such as manufacturing [1], tourist trip design [2], athlete recruitment [3], mobile crowd sourcing [4], collection of used products and reverse logistics [5], and many more. The VRPPs is discussed in detail in [6]. Figure 1 represents VRPP in a network with 6 customers out of which 4 were selected to serve.

Figure 1

A real life application of VRPP.

1.1 Literature review

The most basic version of the problem, known as orienteering problem, was first studied by Tsiligirides [7] and Golden, Levy and Vohra [8]. They studied the problem of routing of oil tankers to serve ships at different locations. The name orienteering problem is derived from orienteering sport where the objective is to maximize the total collected prize within given time limit when a prize is associated with each node in the network. Various variants of orienteering problems are discussed in [9]. Routing problem with inventory management are also considered in [9]. A multi-stage clustering based metaheuristic is proposed in [10] for solving large orienteering problem in an effective or controlled computation time. A four phase heuristic approach is proposed by Ramesh and Brown in [11] to plan the visits of a salesperson for solving orienteering problem. The problem of outsourcing of unprofitable customers is discussed by Chu in [12]. The problem of customer selection in less than truckload transportation is discussed by Archetti et al in [13]. An introduction to various variants of single VRPPs and the concerned mathematical modes are presented in detail in [14]. The difference and the similarities among three models, namely; the profitable tour problem, the prize collecting travelling salesman problem and the orienteering problem are discussed.

A real life application of the problem in the field of transportation optimization is considered in [15] where a competitive factor namely customer satisfaction is also taken into account along with the cost reduction. An application of orienteering problem in personal tourist trip planning has been discussed in [16], where nodes are clustered into different categories and the objective is to find a tour among all nodes from all categories such that the total collected profit is maximum. However, the profit assigned to each node is not fixed and profit decreases as number of nodes selected from its category increases. A multi objective genetic algorithm is proposed in [17] to solve team orienteering problem with time windows. The objective is to determine the optimal travel routes keeping in mind the accessibility of point of interests. A meta-heuristic algorithm based on cuckoo optimization algorithm is used to solve the problem where simulated annealing algorithm is used to accelerate the cuckoo clustering. The environment aspect of the problem is considered in [18] where the objective is to select the subset of customers which maximizes the aggregated prize values collected and minimize the CO2 emissions during route operation. A solution approach based on firefly algorithm is presented to solve the environmental prize collecting vehicle routing problem. A vehicle routing problem with a private fleet and a common carrier is considered in [19] where some customers can be delegated to an external carrier subject to a cost. The objectives are to select subsets of customers, assign them to vehicles and construct sequence of deliveries for each route. A neighbourhood search algorithm based on resource constrained shortest path is proposed in [19]. A vehicle routing problem with vector profits is considered in [20] where a vector is associated with each node where $k^{th}$ element represent the profit value for the $k^{th}$ stakeholder. The objective of the problem is to maximize the profit sum for the least satisfied stakeholder. An approach based on linear programming relaxation and column generation is developed to solve this max-min type routing problem. A multi-chaotic variant of differential evolution is used to solve VRPPs in [21].

A tabu search heuristic is used to solve the formulated mixed integer linear programming models where the objective is to select a subset of dealers which gives maximum gross profit and the acquisition price paid to these dealers is minimum. A consistent vehicle routing problem where the set of customers is divided into two sets, namely frequent customers (known profit) and non-frequent potential customers (estimated profit) is considered in [22]. A multi-depot multi-period VRP with time windows has been solved by Paul et al by using tabu search and variable neighbourhood search in [23]. An adaptive tabu search method is developed with an objective of determining vehicle routes which maximizes net profits while satisfying constraints such as consistency constraints, vehicle capacity constraints and route duration constraint to solve the discussed problem. A mixed integer linear programming model is used to formulate a profitable heterogeneous vehicle routing problem with cross docking is presented in [24]. Three meta-heuristic algorithm namely hybrid genetic algorithm with variable neighbourhood search, artificial bee colony and simulated annealing algorithm are designed to solve the said problem. A hybrid genetic algorithm is proposed to solve a full truckload vehicle routing problem with profits in [25]. The objective of the problem is to select a subset of customers which will be served by the company itself by using a private fleet and a subset of customers which will be served by any other logistic company at a certain cost in a way such that the profit earned during this entire operation is maximum. Various variants of the problem exists when the information about the network or the customers is not available well in advance or completely. A stochastic orienteering problem where the objective is to maximize rewards for visited vertices while obeying travel budget with stochastic cost within a given probability of failure is presented in [26]. The probabilistic orienteering problem is solved by embedding a Monte Carlo evaluator into a Tabu Search algorithm in [27]. A Biased Random-Key genetic algorithm for solving the set orienteering problem where customers are grouped in clusters and profit associated with each cluster is collected by visiting at least one of the customers in the respective cluster is presented in [28]. Pointer network models are trained using reinforcement learning to solve the orienteering problem with time windows in [29]. A greedy randomized adaptive search procedure is proposed to solve the multi-constraints multi-modal team orienteering problem with time windows for groups with hetrogeneous preferences in [30]. Various heuristic methods and some exact methods have been defined for solving numerous variants of vehicle routing problem such as nearest neighbour algorithm [31], branch and bound algorithm [32, 33], Clark and wright algorithm [34] and many more.

1.2 Motivation

Various parameters of VRPPs include the structure of the network, the profit associated with the customers in the network the cost matrix(time matrix) and many more. In real life situations, these parameters can not always be predicted precisely and are better represented imprecisely. Profits associated with the customers in the network, the edge weights representing the cost of traversal across various edges are some factors which are responsible for the impreciseness [35] in the problem. Although a lot of work has been done on vehicle routing problem with profits but on careful inspection, it is found that factors like impreciseness which are inevitable in real life situations are seldom incorporated. Also, in real life situations, factors like relationship of customer with seller plays an important role in the service provider’s mind. The accessibility of the customer is also a qualitative factor which can never be ignored as the customers who share a good bond with the seller (or service provider) and/or the customers which are more accessible; i.e. are present on a route which has better transportation facilities, lesser risk of transportation etc. are always given more importance over others. So, this work is done with the motive of bridging the gap between the problems formulated by researchers in academia and the complexities of the problems existing in real world arena.

1.3 Contributions

The major contributions of this work are summarized as follows:-

• 1. In the FFVRPP under consideration, all of the parameters, such as the transportation cost, profit associated with customers, risk of transportation of goods and the relation of customers with the seller are considered as fermatean fuzzy numbers. The use of fermatean fuzzy numbers offers us the following benefits:-

  • (a) Using Fermatean fuzzy numbers facilitates us to write the membership grades of an element x as pair of values in the unit interval $\langle \mu (x), \vartheta (x) \rangle$, one of which indicates support for membership in the fuzzy set and the other indicates the support against membership. Thus, the hesitancy in the data can be presented easily.

  • (b) In case of Fermatean fuzzy sets, $\mu _F^3(x) + \vartheta _F^3(x) \le 1$ which is not the case with other fuzzy extensions, such as Pythagorean fuzzy numbers and intuitionistic fuzzy numbers, which allows the representation of hesitancy in data.

    In case of intuitionistic fuzzy numbers, $\mu _I(x) + \vartheta _I(x) \le 1$ .

    In case of Pythagorean fuzzy numbers, $\mu _P^2(x) + \vartheta _P^2(x) \le 1$.

  Representing these fuzzy membership and non-membership grades in a diagram gives figure 2, where one can easily observe that fermatean fuzzy numbers enables the representation of a bigger body of non-standard membership functions than intuitionistic fuzzy numbers and Pythagorean fuzzy numbers.

• 2. Qualitative factors representing the relationship of customers with the seller is also given importance in addition to the quantitative factors like cost of serving the customers and profit associated with each customer while solving the first stage of the problem, i.e. selecting the subset of customers to be served.

• 3. Qualitative factors representing the risk of transportation of goods from one node to another is also given importance in addition to the quantitative factors like cost of transportation of goods from one node to another while solving the second stage of the problem, i.e. making the routes to serve the customers.

• 4. In contrast to most existing approaches, which provides crisp solution, the proposed method provides a fermatean fuzzy feasible solution.

• 5. Three different existing algorithms namely Clark and Wright algorithm, nearest neighbour algorithm and modified nearest neighbour algorithm are used for solving the second stage routing problem and this gives rise to three different solution methodologies to solve the concerned problem.

Figure 2

Comparison of space of Fermatean fuzzy sets, Pythagorean fuzzy sets and Intuitionistic fuzzy sets.

1.4 Organization

This paper is organized as follows: In section 2, some basic definitions regarding fermatean fuzzy set theory and their operations are reviewed, In section 3, a mathematical model for solving FFVRPP has been presented. Section 4 comprises of three different solution methodologies, namely, fermatean fuzzy Clark and Wright algorithm, fermatean fuzzy Nearest Neighbour algorithm and Fermatean fuzzy modified nearest neighbour algorithm to solve FFVRPP. In Section 5, the application of the proposed method is shown using a numerical example and the obtained results are compared and discussed. Section 6 ends this paper with a brief conclusion and suggestions for future directions.

2 Preliminaries: concepts and definitions

This section briefly introduces some basic concepts and arithmetic operations based on fermatean fuzzy sets which are applied throughout this paper.

Definition 1

Fermatean fuzzy sets [36]:- Let X be universe of discourse. A Fermatean fuzzy sets F in X is an object having the form given by Eq. (1)

$$\begin{aligned} F=\lbrace <x,\alpha _{F}(x), \beta _{F}(x)> : x \in X \rbrace \end{aligned}$$

(1)

where,

$$\begin{aligned} \alpha _F(x) : X \rightarrow [0,1] \end{aligned}$$

and

$$\begin{aligned} \beta _F(x) : X \rightarrow [0,1]\ \end{aligned}$$

including the condition

$$\begin{aligned} 0 \le \left( \alpha _F(x)\right) ^3 + \left( \beta _F(x)\right) ^3 \le 1 \quad \forall x \in X \end{aligned}$$

The number $\alpha _F(x)$ and $\beta _{F}(x)$ denote respectively the degree of membership and the degree of non-membership of the element x in the set F.

Definition 2

Score Function [36]:- Let $F = \left( \alpha _F, \beta _F\right)$ be a fermatean fuzzy set then the score function of F can be represented by Eq. (2).

$$\begin{aligned} score(F) = \alpha _{F}^3 - \beta _{F}^3 \end{aligned}$$

(2)

For any $FFS, F = \left( \alpha _F, \beta _F \right)$, the suggested score function, $score(F)\in [-1, 1]$.

Definition 3

Accuracy Function [36]:- Let $F = \left( \alpha _F, \beta _F \right)$ be a fermatean fuzzy set, then the accuracy function regarding F can be represented by Eq. (3)

$$\begin{aligned} acc(F) = \alpha _{F}^3 + \beta _{F}^3 \end{aligned}$$

(3)

Clearly, $acc(F) \in [0, 1]$. Bigger the value of acc(F), higher the accuracy of FFS, F will be.

Definition 4

Degree of Indetreminacy [36]:- For any fermatean fuzzy set, F and $x \in X$, the degree of indeterminacy of x to F is given by Eq. (4)

$$\begin{aligned} \pi _F(x) =\root 3 \of {1-\alpha _{F}(x)^{3}-{\beta _{F}(x)^{3}}} \end{aligned}$$

(4)

Definition 5

Ranking Principle using Score and Accuracy function [36, 37]:- Let $F_1 = (\alpha _{F_1}, \beta _{F_2})$ and $F_2 = (\alpha _{F_2}, \beta _{F_2})$ be two FFSs. $Score(F_i)$ and $acc(F_i)$, $i = 1, 2$ are the score values and accuracy values of $F_1$ and $F_2$ respectively; then the ranking principle using score and accuracy function is defined as follows:

• 1. If $score(F_1) < score(F_2)$, then $F_1 < F_2$.

• 2. If $score(F_1) > score(F_2)$, then $F_1 > F_2$.

• 3. If $score(F_1) = score(F_2)$, then

  • (a) If $acc(F_1) < acc(F_2)$, then $F_1 < F_2$.

  • (b) If $acc(F_1) > acc(F_2)$, then $F_1 > F_2$.

  • (c) If $acc(F_1) = acc(F_2)$, then $F_1 = F_2$.

Definition 6

Arithmetic operation on Fermatean fuzzy number [38]:- Let $F=(\alpha _F(x),\beta _F(x))$, $F_1=(\alpha _{F_1}(x),\beta _{F_1}(x))$ and $F_2=(\alpha _{F_2}(x),\beta _{F_2}(x))$ be three FFSs and $\lambda > 0$, then their operations are defined as follows:

• $F_1 \boxplus F_2=\left( \root 3 \of {{\alpha _{F_1}^3}+{\alpha _{F_2}^3}-{\alpha _{F_1}^3}{\alpha _{F_2}^3}},{\beta _{F_1}}{\beta _{F_2}}\right)$

• $F_1\boxminus F_2 = \left( \root 3 \of {\dfrac{\alpha _{F_1}^3 - \alpha _{F_2}^3}{1-\alpha _{F_2}^3}} , \dfrac{\beta _{F_1}}{\beta _{F_2}}\right)$ if $\alpha _{F_1} > \alpha _{F_2}$, $\beta _{F_1} \le \text{ min } \left( \beta _{F_2}, \dfrac{\beta _{F_2}\pi _1}{\pi _2} \right)$

• $F_1\boxtimes F_2=\left( {\alpha _{F_1}}{\alpha _{F_2}},\root 3 \of {\beta _{F_1}^3+{\beta _{F_2}^3}- {\beta _{F_1}^3}{\beta _{F_2}^3}}\right)$

• $F_1 \tilde{\div } F_2 = \left( \dfrac{\alpha _{F_1}}{\alpha _{F_2}}, \root 3 \of {\dfrac{\beta _{F_1}^3 - \beta _{F_2}^3}{1-\beta _{F_2}^3}} \right)$ if $\alpha _{F_1} \le \text{ min } \left( \alpha _{F_2}, \dfrac{\alpha _{F_2}\pi _1}{\pi _2} \right)$ and $\beta _{F_1} > \beta _{F_2}$

• $\lambda F = \left( \root 3 \of {1 - \left( 1 - \alpha _{F}^3\right) ^{\lambda }}, \beta _{F}^\lambda \right)$

• $F^{\lambda } = \left( \alpha _{F}^\lambda , \root 3 \of {1 - \left( 1 - \beta _{F}^3\right) ^{\lambda }}\right)$

3 Vehicle routing problem with profits

In this section, the vehicle routing problem with profits in a deterministic environment and in a fermatean fuzzy environment are explained and the assumptions which are to be kept in mind while solving FVRPP are discussed. This section also presents the linear programming formulations of VRPP in both deterministic and fermatean fuzzy environment.

3.1 Vehicle routing problem with profits in a deterministic environment

The classical version of the vehicle routing problem [39] deals with serving each customer present in the network, in such a way that the operational costs incurred are minimum. In VRPP, it is not compulsory to provide service to the complete set of customers; rather, a profit is associated with each customer present in the network and a subset of customers that gives the maximum profit is to be visited. The team orienteering problem is the name given to this variant of vehicle routing problem where the objective is to select a subset of customers and traverse them so as to maximize the collected profits under some constraints on each vehicle.

The mathematical programming formulation of vehicle routing problem with profits in a deterministic environment with a single vehicle case is given as follows:

$$\begin{aligned} \text{ Maximize } &\alpha \sum _{i \in V} p_i y_i - \sum _{(i,j) \in E} c_{ij}x_{ij} \end{aligned}$$

(5)

$$\begin{aligned} \text{ subject to} &\sum _{j \in V} x_{ij} = y_{i} \quad \forall i \in V \end{aligned}$$

(6)

$$\begin{aligned}&\sum _{j \in V} x_{ji} = y_{i} \quad \forall i \in V \end{aligned}$$

(7)

$$\begin{aligned}&\sum _{(i,j) \in S}x_{ij} \ge y_h \quad \forall S \subseteq V - \lbrace 0 \rbrace , h \in S \end{aligned}$$

(8)

$$\begin{aligned}&y_{i} \in \lbrace 0, 1 \rbrace \quad \forall i \in V \end{aligned}$$

(9)

$$\begin{aligned}&x_{ij} \in \lbrace 0, 1\rbrace \quad \forall (i, j) \in A \end{aligned}$$

(10)

The objective function represented by Eq. (5) maximizes the difference between collected profits multiplied by $\alpha$ and travelling cost. Constraint represented by Eq. (6) and Eq. (7) ensures that one arc enters and one arc leaves each visited vertex. Sub-tours are eliminated through constraint represented by Eq.(8) and the constraints represented by Eq. (9) and Eq. (10) are variable definitions.

3.2 Vehicle routing problem with profits in a fermatean fuzzy environment

Conventional vehicle routing problem with profits assume precise values for the transportation cost, profits and demands. However, these values are often imprecise and ambiguous in practical applications. In real life situations, qualitative components like relationship of the customers with the seller is also given importance while choosing the subset of customers to serve and the qualitative factor of risk of transportation of goods across various edges is also considered during route formation Further, the factors like impreciseness may creep into the environment because of the components like profit earned while serving a customer, edge weights and many more. In this work, the nature of the network is known well in advance but in an imprecise form. Corresponding to each customer, fermatean fuzzy numbers represent the profit associated and the willingness of the service provider to serve the customer and these factors are considered while selecting the subset of customers. Additionally, corresponding to each edge in the network, a fermatean fuzzy number represents the fuzzy cost and fuzzy risk associated with the edge which are considered while forming the route.

3.2.1 Assumption

Before discussing the mathematical model of FFVRPP, some basic assumptions regarding the model are presented that will be used throughout the paper. The very first assumption is regarding the network and it states that the network under consideration is symmetric and follows triangle inequality i.e. the cost of traversal from i to j is denoted by $c_{ij}$ then $c_{ij} = c_{ji}$ and $c_{ij} \le c_{ik} + c_{kj}$. In this work, we have assumed that edge weights represent the expense of traversal of edges, which is given by the weighted sum of risk of traversal of edges and cost of traversal of edges. The components like risk of traversal of edges and cost of traversal of edges are imprecise in nature and hence are given by fermatean fuzzy numbers. The profit associated with each customer and willingness of service provider to serve each customer is given by fermatean fuzzy numbers. The willingness of a service provider to serve a customer is determined by the relation of the customer with the distributor and it is an important qualitative feature while dealing VRPP in real life situations. The selection of subset of customers is based on a weighted average function of profit associated with the customer, willingness to serve the customer and the fuzzy cost to traverse the customer node directly from the origin. The journey of the fleet is assumed to originate and terminate at the source vertex (depot node) only. It is assumed that customer is traversed exactly once. The fleet of vehicles present at depot node is assumed to be homogeneous i.e. all the vehicles have identical operating costs and they have the same carrying capacity.

3.2.2 Mathematical model

A Fermatean fuzzy vehicle routing problem with profits is represented by a complete weighted graph $G = (V, E)$ where V is the set of vertices in the network and E is the set of edges joining these vertices. The set of vertices includes a depot node and a finite number of customer nodes. A homogeneous fleet of vehicles is assumed to be present at the depot node. We are given a set of N total customers and the distributor has only a capacity of serving M customers out of N, where $M \le N$. The objective is to select M customers out of N and visit these M customers through different vehicle routes with the limitation that no more than K customers are visited in a single trip, where $K \le M \le N$. The objective here is to maximize the difference between the favourability function and the expense function. The favourability function is a weighted average function of profit associated with each customer, willingness to serve the customer and the fuzzy cost to traverse the customer node directly from the origin. The expense function is a weighted average function of cost associated with traversal of each edge and the risk associated with the traversal of each edge. Thus, a mathematical model for solving FFVRPP is given as follows:

$$\begin{aligned} \text{ Maximize } {}&\alpha \widetilde{\sum _{i \in V}} \tilde{f} \sum _{r \in R}y_{ir} \boxminus \widetilde{\sum _{(i, j) \in A}} \widetilde{exp_{ij}} \sum _{r \in R}x_{ijr} \end{aligned}$$

(11)

$$\begin{aligned} \text{ subject } \text{ to } &\sum _{j \in V} x_{ijr} = y_{ir} \quad \forall i \in V, r \in R \end{aligned}$$

(12)

$$\begin{aligned}&\sum _{j \in V} x_{jir} = y_{ir} \quad \forall i \in V, r \in R \end{aligned}$$

(13)

$$\begin{aligned}&\sum _{r \in R} y_{0r} \le |R |=\lceil \frac{M}{K} \rceil \end{aligned}$$

(14)

$$\begin{aligned}&\sum _{r \in R} y_{ir} \le 1 \quad \forall i \in V - \lbrace 0\rbrace \end{aligned}$$

(15)

$$\begin{aligned}&\sum _{i \in V-\lbrace 0 \rbrace } y_{ir} \le k \quad \forall i = 1, 2, \ldots , m , \, \forall r \in R \end{aligned}$$

(16)

$$\begin{aligned}&y_{ir} \in \lbrace 0, 1 \rbrace \quad \forall i \in V, r \in R \end{aligned}$$

(17)

$$\begin{aligned}&x_{ijr} \in \lbrace 0, 1\rbrace \quad \forall (i, j) \in A, r \in R \end{aligned}$$

(18)

In the mathematical model presented above, Eq. (11) represents the objective function. The objective here is to maximize the difference between the favourability function and the expenditure function. Constraints given by Eq. (12) and Eq. (13) ensures that one arc enters and one arc leaves for each visited vertex. Constraint represented by Eq. (14) limits the number of routes to be at most $|R |$, hence ensuring the full utilization of fleet of vehicles. Eq. (15) represents that each customer is visited at most once. The constraint given by Eq. (16) represents the route restriction, i.e. for any route $r \in R$, at most K customers are visited. Constraint represented by Eq. (17) ensures that $y_{ir}$ is a binary variable which takes the value 1 if the node i is traversed in route r and 0 otherwise. Similarly, the constraint represented by Eq. (18) ensures that $x_{ijr}$ is a binary variable which takes the value 1 if edge ij is traversed in route r and 0 otherwise.

4 Solution methodology

In this section, three different solution methodologies namely Fermatean fuzzy Nearest Neighbour algorithm, Fermatean fuzzy Clark and Wright algorithm and Fermatean fuzzy modified nearest neighbour algorithm are proposed to solve FFVRPP.

4.1 Customer selection in Fermatean fuzzy vehicle routing problem with profits

Clearly, fermatean fuzzy vehicle routing problem with profits is a two stage problem. The first stage of the solution methodology corresponds to the selection of M customers out of N customers on the basis of their favourability of getting served by the distributor. The favourability of a customer i present in a network is a weighted average function of profit, $\widetilde{P_i}$, willingness, $\widetilde{W_i}$ of distributor to serve the customer and the cost $\widetilde{C_{0i}}$ of serving the customer from the depot node. The favourability function for the $i^{th}$ customer is given by Eq. (19).

$$\begin{aligned} F\left( \alpha _1 \widetilde{P_i}, \alpha _2 \widetilde{W_i}, \alpha _3 \widetilde{C_{0i}}\right) = score\left( \alpha _1 \widetilde{P_i} \boxplus \alpha _2 \widetilde{W_i} \right) - score\left( \alpha _3 \widetilde{C_{0i}} \right) \end{aligned}$$

(19)

where $\alpha _1, \alpha _2$ and $\alpha _3$ are weights such that $\alpha _1 + \alpha _2 + \alpha _3 = 1$. The selection of subset of M customers is done by selecting the customers corresponding to the maximum value of the favourability function. This part of solution methodology is same while using all the proposed algorithms and it is presented using Algorithm 1.

After selection of these M customers in the first stage, the second stage of problem solving corresponds to the formation of routes so that all these selected M customers are traversed exactly once in such a way that the total expense of this operation comes out to be the minimum while keeping in mind the route restriction constraints, i.e. no more than K customers can be traversed in any route. The total expense of any route is a weighted function of sum of cost of traversal of edges traversed and the sum of risk of transportation of goods on the edges traversed. The formation of routes in second stage can be done by following the strategies to solve capacitated vehicle routing problem with route constraints. The two very famous heuristic methods, namely, Clark and Wright algorithm and Nearest Neighbour algorithm have been modified in this work to propose three different solution methodologies to solve the given problem in fermatean fuzzy environment. The first step in route formation involves the formation of an expense matrix which store the fermatean fuzzy expense incurred in traversing each edge.

4.2 Fermatean fuzzy nearest neighbour algorithm

In this subsection, we present the fermatean fuzzy nearest neighbour algorithm to solve the concerned problem. The formation of routes is done according to the nearest neighbour algorithm which is based on the idea that the un-served customer nearest to customer’s nearest location is served first. With respect to this work, the un-served customer which can be served at minimum expense from current location is selected as next customer. The method is considered as computationally the simplest one, as it involves only finding the best un-served customer (customer that can be served with minimum expense) from the current location. Upon reaching the route capacity limit(the only route constraint here), the vehicle is bound to return to depot node and then the algorithm restarts until all the selected customers are served. The time complexity of solving the fermatean fuzzy nearest neighbour algorithm is of logarithmic order and space complexity is of polynomial order. The methodology of Fermatean fuzzy Nearest Neighbour method is presented in Algorithm 2 and the block diagram that represents the methodology of solving FFVRPP using Fermatean fuzzy nearest neighbour algorithm is given by figure 3.

Figure 3

A Block Diagram representing Fermatean fuzzy nearest neighbour algorithm.

Fermatean fuzzy Nearest Neighbour approach is a greedy and myopic approach and often returns the feasible but non-optimal solution. Fermatean fuzzy nearest neighbour approach can be further modified by selecting the permutation of nodes in each route that corresponds to minimum expense.

4.3 Fermatean fuzzy modified nearest neighbour algorithm

In this subsection, we present the methodology for solving the concerned problem by using fermatean fuzzy modified nearest neighbour algorithm. The idea of the algorithm is to find all the permutations of routes obtained in subsection 4.2 and then calculate their expenses. The routes corresponding to minimum expenses are the desired routes. This methodology is supposed to be used lesser as compared to fermatean fuzzy nearest neighbour methodology as it has the exponential time complexity. It becomes extremely difficult to solve when the number of customers in a single route is even greater than 10. The fermatean fuzzy modified nearest neighbour algorithm is presented in Algorithm 3 and the block diagram that represents the methodology of solving the problem is given by figure 4.

Figure 4

A Block Diagram representing Fermatean fuzzy modified nearest neighbour algorithm.

Since all the permutations of routes are to be considered in fermatean fuzzy modified nearest neighbour algorithm and this increases the time complexity of the algorithm to the exponential order. Despite of the increased time and space complexity, the method does not guarantee an optimal solution. This methodology comes up as an improvement of fermatean fuzzy nearest neighbour but is again a myopic approach. A visionary approach for solving the second stage routing problem which also has a polynomial order time complexity is thus the need of the hour. In the upcoming subsection, a method based on choosing a path that corresponds to maximum savings is presented.

4.4 Fermatean fuzzy Clark and Wright algorithm

In this subsection, we present the fermatean fuzzy Clark and Wright algorithm to solve the concerned problem. The basic idea of fermatean fuzzy Clark and Wright algorithm is to join the tours which gives maximum savings until all customers are served keeping in mind the route restriction constraints. The working of fermatean fuzzy Clark and Wright algorithm can be simply understood by the given steps.

Step 1: Consider the depot node 0 and M demand points.

Step 2: Suppose that the initial solution to the problem consists of using M vehicles and dispatching one vehicle to each one of the M demand points. The total expense of this initial solution is, obviously, $2\sum _{i=1}^{M} expense(0, i)$.

Step 3: If now we use a single vehicle to serve two points, say i and j, on a single trip, the total expense is reduced by the amount as given in eq. (20).

$$\begin{aligned} s(i, j) = expense(0, i) + expense(0, j) - expense(i, j) \end{aligned}$$

(20)

The quantity s(i, j) is known as “savings” resulting from combining the points i and j into a single tour. The larger the savings s(i, j) is, the more desirable it becomes to combine i and j in a single tour. However, i and j can not be combined if in doing so the resulting tour violates any constraint of the problem. So, we connect the demand points in the decreasing order of savings until all the demand points are served while following route restriction constraints. Upon reaching the route restriction, the vehicle is bound to return to the depot node and then the algorithm restarts from depot node until all the customers selected in the first stage are served. The modified fermatean fuzzy Clark and Wright algorithm is presented in Algorithm 4 and the block diagram that represents the methodology of fermatean fuzzy clark and wright algorithm is given by figure 5.

Figure 5

A Block Diagram representing Fermatean fuzzy Clark and Wright algorithm.

Clark and Wright algorithm is one of the most used heuristic as it is computationally as simple as Nearest Neighbour algorithm. The time complexity of fermatean fuzzy Clark and Wright algorithm is of polynomial order. However, the operations here are performed on Savings matrix despite of expense matrix thus resulting in higher space requirements (polynomial order). Since space complexity is of polynomial order which makes the execution of even large sized instance possible.

5 Numerical example

In this section, we present a numerical example to illustrate the applicability and feasibility of the proposed solution methodologies.

5.1 Example 1

Consider a fermatean fuzzy multiple vehicle routing problem with profits with 7 customers and a depot node. The depot node is located at node 0. All the data i.e. profits, costs, willingness and risk are given by fermatean fuzzy numbers. The objective is to first select a subset of 6 customers; as it is assumed that in one day only 6 customers can be served, and then create routes to serve these 6 customers; assuming that in one trip only 3 customers can be served. According to the mathematical model, $N=7, M = 6, K = 3$. Thus, the number of paths is given by $\lceil \dfrac{6}{3} \rceil = 2$.

Table 1 stores the data about the profit satisfaction level offered by all the customers, the willingness of distributor to serve these customers which reflects the relation of the customers with distributor and the fuzzy cost to serve these customers directly from the depot node. Table 2 gives the fuzzy cost of moving from one node to another. Here, the matrix is a symmetric matrix i.e. the fuzzy cost of going from $i^{th}$ node to $j^{th}$ node is same as the fuzzy cost of going from $j^{th}$ node to $i^{th}$ node. All the diagonal cells are empty as no transportation is required from $i^{th}$ node to itself. Table 3 is the risk table indicating the risk involved in moving from $i^{th}$ node to $j^{th}$ node. The higher the membership value, the more risky it is to transport goods between the nodes. Table 4 is calculated with the help of tables 2 and 3. The expense of moving from $i^{th}$ node to $j^{th}$ node is a weighted average function of fuzzy cost and risk involved in moving from $i^{th}$ node to $j^{th}$ node with weights 0.6 and 0.4 respectively.

Table 1 Selection table

First we calculate the value of the favourability function corresponding to each customer. The weights corresponding to profits, willingness and fermatean fuzzy costs are taken as 0.4, 0.4 and 0.2 respectively. Table 5 comprises of the value of the favourability function corresponding to the given set of customers.

Table 2 Fuzzy cost table

Table 3 Risk table

Table 4 Expense table

Table 5 Favourability function

5.2 Comparative and discussion analysis

In this subsection, we present the comparison of various methods that has been proposed in this work to solve fermatean fuzzy multiple vehicle routing problem with profits. The comparison of the methods in Fermatean fuzzy environment and deterministic environment is also performed and the benefits of handling the problem in fermatean fuzzy environment are explained.

5.2.1 Comparison between various proposed methods

Table 6 presents the comparison of various methods defined in this work. The step 1 of the solution procedure is same for all the algorithms. Out of 7 possible customers we choose 6 most attractive or favourable customers. According to the table 6, the fermatean fuzzy Clark and Wright algorithm gives the best result followed by fermatean fuzzy nearest neighbour and fermatean fuzzy modified nearest neighbour algorithm. The satisfaction level obtained by using Fermatean fuzzy Clark and Wright algorithm is (0.79,0.001) which is higher then the satisfaction level given by fermatean fuzzy nearest neighbour and fermatean fuzzy modified nearest neighbour method. Fermatean fuzzy nearest neighbour and fermatean fuzzy modified nearest neighbour provides the same results with the overall satisfactory level as (0.52,0.016). However, in general, fermatean fuzzy nearest neighbour and fermatean fuzzy modified nearest neighbour may not provide the same set of solutions. In general, fermatean fuzzy modified nearest neighbour give us a route which is either same as fermatean fuzzy nearest neighbour or less expensive than fermatean fuzzy nearest neighbour. The fuzzy expected cost is calculated from the table 2.

Table 6 Comparison of various proposed methods for solving FFMVRPP

5.2.2 Comparison between VRPP in fermatean fuzzy and deterministic environment

In deterministic environment, the VRPP models takes only two factors, cost and profit while in fermatean fuzzy environment, the model included cost, profit, risk and willingness variables. Thus the model in fermatean fuzzy environment clearly have a more realistic and practical approach for decision making. The willingness or relation of customer with seller/distributor plays a very dominant role in practical scenerios which is completely ignored in the deterministic approach of the VRPP.

Table 7 VRPP in fermatean fuzzy environment and deterministic environment

From table 7 it is quite clear that applying same algorithm in various environment gives different routes. The absence of any significant difference between the results obtained with pure VRP and VRP with Fermatean fuzzy numbers ensures that the results obtained are promising in nature. However, the results obtained in the case of Fermatean fuzzy VRP have additional degree of membership and the degree of non-membership associated with the cost and profit and they represent the belief of the decision maker and thus helps decision maker in making sound decision. Though the cost of routes and profit associated with selected set of customers is same; but there is a significant change in the overall risk involved. In practical situations, risk plays a more dominant role then profit as most of the firms prefers less risk even if the cost is a bit higher. Additionally, if we remove the willingness and risk factors from our FFVRPP then we would get similar result i.e we would get similar kind of set of customers and routes. The deviation is due to the extra qualitative factors that we have included in our model showing the effect of these factors.

6 Conclusion

In this work, a mathematical model for solving VRPP with fermatean fuzzy numbers as coefficients and the algorithm to solve such a problem has been presented. In practical life situations, when a service provider (distributor) provides service to a subset of customers, the coefficients involved are not always known precisely. Sometimes, a distributor cares not only for the quantitative factors (like cost, profit) but also the qualitative factors (such as the relationship of customers with service provider, risk of serving the customers) while serving the customers. Such practical life situations give rise to FFVRPP as discussed in this work. In mathematical modelling of FFVRPP, the objective is to find a set of routes which serves a subset of M customers in a way such that the difference of the profits earned by serving the selected subset of M customers and the expense incurred in serving the selected subset of customers is maximum. In this work, the coefficients such as profits associated with each customer, willingness of the service provider to serve each customer, the cost incurred in traversal of edges and the risk of transportation of goods across each edge are imprecise in nature and hence are given by Fermatean fuzzy numbers.

A two stage approach is used in this work, i.e. first a subset of M customers is selected and while doing so the risk of transportation of goods across various edges and cost of traversal of edges are not kept in mind. For selection of subset of M customers; a favourability function, which is a weighted average of profit associated with every customer, willingness of serving each customer and cost of serving each customer from depot node; is calculated. The list of customers corresponding to higher value of favourability function is then selected to serve. The sequence of service of customers is decided on the basis of nearest neighbour algorithm and then the sequence of routes which corresponds to minimum expense is traversed. A numerical example has also been solved using the proposed approach. These results will be useful in finding a feasible route for solving a FFVRPP. The combination of uncertainty, revealed by using fermatean fuzzy numbers and qualitative factors, such as willingness of serving a customer, risk of transportation of goods across various edges will surely help us to cover more realistic situations while modelling VRPP. Here, we shall point out that the FFVRPP studied in this paper does not involve the demand and/or service time of the customers in either precise or imprecise manner. Therefore, further research on extending the proposed methodologies to overcome these shortcomings is an interesting stream for future research projects.