Reach Us
+44-1522-440391

**Seyed Mohammad Seyedhosseini ^{1*}, Shima Kabirian^{1}, Ahmad Makui^{1} and Nooraddin Dabiri^{2}**

^{1}Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran, Iran

^{2}Department of Industrial Engineering, Faculty of Engineering, Golestan University, Golestan, Iran

- *Corresponding Author:
- Seyed Mohammad Seyedhosseini

Department of Industrial Engineering

Iran University of Science and Technology

Narmak, Tehran, Iran

**Tel:**+98 9121261744

**Fax:**+98 21 77240482

**E-mail:**[email protected]

**Received** February 03, 2012; **Accepted** April 27, 2012; **Published** April 30, 2012

**Citation:** Seyedhosseini SM, Kabirian S, Makui A, Dabiri N (2012) A Possibilistic Programming Approach for Vehicle Routing Problem with Fuzzy Fleet Capacity (FCVRP). Ind Eng Manage 2:101. doi:10.4172/2169-0316.1000101

**Copyright:** © 2012 Seyedhosseini SM, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

**Visit for more related articles at** Industrial Engineering & Management

In this paper we present the vehicle routing problem with fuzzy fleet capacity (FCVRP) to find short routes with the minimal transportation cost. We propose a possibilistic 0-1 linear programming model to deal with such issues. To solve the proposed possibilistic optimization model, we apply an efficient possibilistic method proposed by Parra et al. [1] The FCVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, we develop a hybrid genetic algorithm (HGA). For the model verification, some small, medium and large-scale test problems are solved by HGA and the results are compared with obtained results from Lingo 9.0. Finally, we do a case study in the Kalleh Company in Amol and publish the results.

Fuzzy mathematical programming; Vehicle routing problem; Fuzzy fleet capacity; Possibilistic programming; Hybrid genetic algorithm

Transportation has an important role in various domains, such as enterprise, economic and service systems. By this way, researchers are interested in improving the routes, deleting the unnecessary travels and creating the replacement short routes. In addition, many problems, such as traveling salesman problem (TSP), vehicle routing problem (VRP) and the like, are developed by this approach. The Vehicle Routing Problem (VRP) is a widely studied combinatorial optimization problem that was introduced in 1959 by Dantzig and Ramser [2]. VRP is one of the most significant problems in distribution management. Its objective is to find the optimal routes for distributing various shipments [3], such as goods, mail and raw materials. The basic VRP consists of a number of geographically scattered customers, each requiring a specified weight (or volume) of goods to be delivered (or picked up). A fleet of identical vehicles dispatched from a single depot is used to deliver the goods required and once the delivery routes have been completed, the vehicles must return to the depot. Each vehicle can carry a limited weight and only one vehicle is allowed to visit each customer. It is assumed that all problem parameters, such as customer demands and travel times between customers are known with certainty. Solving the problem consists of finding a set of delivery routes which satisfy the above requirements at minimal total cost. In the literature the above described problem is called capacitated VRP (CVRP). In CVRP the total cost equals to the total distance or travel time [4]. Hundreds of papers in world literature have been devoted to this problem. But most of them assume that all information is deterministic, such as customer information, Vehicle information, state of roads information as well as dispatcher information and soon, and the proposed algorithm is only used to solve the deterministic VRP [5]. Actually, in some new systems, it is hard to describe the parameters of the vehicle routing problem as deterministic VRP because there exist much uncertain data such as customer demands, traveling time as well as the set of customers to be visited.

Erbao and Mingyong [5] considered a vehicle routing problem with fuzzy demand. Yanwen and Masatoshi [6] considered a vehicle routing problem where vehicles had finite capacities and demands of customers were uncertain. Yang and Yemei [7] proposed a novel real number encoding method of Particle Swarm Optimization (PSO) to solve the vehicle routing problem with fuzzy demands (FVRP). Erbao and Mingyong [8] considered the open vehicle routing problem with fuzzy demands (OVRPFD). Lian and Xiaoxia [9] considered the vehicle routing problem with fuzzy demands and established a fuzzy constrained programming mathematical model based on possibility theory. Changshi and Fuhua [10] proposed the vehicle routing problem with fuzzy demand at nodes. Tang et al. [11] proposed the vehicle routing problem with fuzzy time windows. They applied membership functions to characterize the service level issues associated with time window violation in a vehicle routing problem and proposed VRPFTW. Gupta et al. [12] considered multi objective fuzzy vehicle routing problem. Zheng and Liu [13] considered the vehicle routing problem in which the travel times are assumed to be fuzzy variables.

According to the **Table 1**, no studies that consider the capacity of fleets as fuzzy number have been done. According to statistics published by the freight companies, any vehicle regardless of its capacity can load 500 kg extra load. But with increasing loading, driver satisfaction also decreases. On the other hand, it is not convenient for driver, if he loads less than a certain amount of this. Thus, according to **Figure 1**, the capacity of the vehicle can be considered as fuzzy numbers with triangular membership function.

Fuzzy parameter | References | Category | Objective Function | Solving approach |
---|---|---|---|---|

Fuzzy demand | Erbao and Mingyong (2009) | VRPFD | Minimization of travel cost | Stochastic simulation and differential evolution algorithm |

Yanwen and Masatoshi (2010) | VRPFD | Minimization of travel cost | Two-stage possibilistic programming and ACSO | |

Yang and Yemei (2010) | VRPFD | Minimization of travel cost | Fuzzy constrained programming and PSO algorithm | |

Cao and Lai (2010) | OVRPFD | Minimization of travel cost | Fuzzy simulation and differential evolution algorithm | |

Lian and Xiaoxia (2011) | VRPFD | Minimization of travel cost | Fuzzy simulation and differential evolution algorithm | |

Changshi and Fuhua (2010) | VRPFD | Minimization of travel cost and the number of used vehicle | Possibilistic programming and improved Sweeping algorithm | |

Fuzzy time window | Tang et al. (2009) | VRPTW | Minimization of travel distance and maximization the service level of the suppliers to customers | Two-stage algorithm |

Gupta et al. (2010) | VRPTW | Minimization of fleet size, distance and waiting time and maximization of customer satisfaction grade | Fuzzy genetic algorithm | |

Zheng and Liu (2006) | VRPTW | Minimization of travel distance | Fuzzy simulation and genetic algorithm |

**Table 1:** The State-of-the art.

Possibility theory was proposed by Zadeh in 1978 and developed by Dubois and Prade in 1988. Since the 1980s, the possibility theory has become more and more important in the decision field and several methods have been developed to solve possibilistic programming problems [1].

Possibilistic Linear Programming (PLP) problem is a linear programming with imprecise coefficients restricted by possibilistic distribution. Possibilistic decision making models have provided an important aspect in handling practical decision making problems. Negoita et al. [14] were the first who formulated the possibilistic linear programming [15].

This paper proposes a possibilistic linear programming for vehicle routing problem with fuzzy capacity where the right hand coefficient, is a triangular fuzzy number.

The CVRP can be formulated as follows. A customer is an entity that has a certain demand and therefore the presence of a vehicle, a unit that can move between customers and the depot. The fleet is defined as the total group of vehicles. Moving a vehicle between the depot and the customers come with a certain cost. A route is a sequence of visited customers by a certain vehicle, starting and ending at a depot. The goal of the vehicle routing problem is to serve all customers, minimizing the total cost of the routes of all vehicles. Let us consider that V= {v_{0},v_{1},v_{2},…,v_{n}} is a set of n+1(n≥1) vertices. We distinguish the depot v_{0} and exactly n customers {v_{1},v_{2},…,v_{n}}. E= {(v_{i}i,v_{j}) | 0≤ i , j ≤ n , i≠j} is the set of |V|*(|V|-1) edges(arcs) between the vertices, called the roads. D= (d_{ij}) is a matrix, where dij≥0 is the distance corresponding to edge (v_{i}i,v_{j}); d_{ii} is always equal to 0 and d_{ij}=d_{ji}. C is the capacity of vehicle that is a fuzzy number which have a triangular membership function. We assume that, if the vehicle travels from node i to node j, x_{ij}=1 and otherwise x_{ij}=0 and if the node i, visited with the vehicle k, y_{ik}=1 and otherwise y_{ik}=0.

The problem can be formulated as the following:

Objective function (1) states that the total distance is to be minimized. Constraints (2) and (4) ensure that each demand node is served by exactly one vehicle and constraints (3) and (5) guarantee that each vehicle starts and ends at the distribution depot. Route continuity is represented by (6), i.e. if a vehicle enters in a demand node, it must exit from that node. Constraint (7) is the vehicle capacity constraints. Constraint (8) eliminates the sub-tour and finally, Constraints (9) and (10) define the nature of the decision variable.

Several methods have been developed in the literature to deal with the possibilistic models involving the imprecise coefficients [1,16,17]. Here, we applying an efficient possibilistic method proposed by Parra et al. [1], to convert the proposed possibilistic 0-1 programming model into an equivalent auxiliary crisp model because of its several advantages as follows:

• This method is computationally efficient to solve fuzzy linear problems because it both preserves its linearity and do not increase the number of objective functions and inequality constraints.

• This method relies on the [18] general ranking method which can be applied to different kinds of membership functions such as triangular, trapezoidal and nonlinear ones in both symmetric and asymmetric forms.

• This method is based on the strong mathematical concepts such as expected interval and expected value of fuzzy numbers.

Assume that is a triangular fuzzy number, the following equation can be define as the membership function of :

According to (Jimenez, 1996) [18], the expected interval (EI) and expected value (EV) of triangular fuzzy number can be define as follow:

It is noted that the same equations can be used for a trapezoidal fuzzy number. Moreover, according to the ranking method of Jimenez [18] for any pair of fuzzy numbers and , the degree in which is bigger than is define as follows:

When it will be said that is bigger than or equal to, at least in degree α and it will be represented as

(6)

Also, according to the definition of fuzzy equations in Parra et al. [1], for any pair of fuzzy numbers and , it will be said that is indifferent (equal) to in degree of α if the following relationships hold simultaneously:

Now, we consider the following constraint with fuzzy parameters:

As mentioned by Jimenez et al. [19], a decision vector x ∈R^{n} is feasible in degree if according to (5) and (6), the equation is equivalent to the following ones, respectively:

This equation can be rewritten as follows:

According to above descriptions, the FCVRP model can be formulated as follows:

As it is an NP-hard problem, the instances with a large number of customers and vehicles cannot be solved in optimality within reasonable time. Therefore, the metaheuristics algorithms used to solve these problems [20]. These algorithms can solve these problems with a good solution in reasonable time. The different criteria used for classification metaheuristics algorithms, such as solution-based and population-based, inspiration of nature and without the inspiration of nature and Genetic algorithms like ant colony, bee colony and inspired by nature and will begin work on an initial population of solutions [21].

Genetic algorithm (GA) developed by John Holland in the 1960s, is a stochastic optimization technique. Similar to other artificial intelligence heuristics like SA (Simulated Annealing) and TS (Tabu search), GA can avoid getting trapped in a local optimum by the aid of one of the genetic operations called mutation.

The idea of genetic algorithm based on evolution in nature. GA starts with an initial set of random solutions, called population. Each solution in the population is called a chromosome, which represents a point in the search space. The chromosomes evolve through successive iterations, called generations. During each generation, the chromosomes are evaluated using some measures of fitness. The fitter the chromosomes, the higher the probabilities of being selected to perform the genetic operations, including crossover and mutation. In the crossover phase, the GA attempts to exchange portions of two parents, that is, two chromosomes in the population to generate an offspring. The crossover operation speeds up the process to reach better solutions. In the mutation phase, the mutation operation maintains the diversity in the population to avoid being trapped in a local optimum. A new generation is formed by selecting some parents and some offspring according to their fitness values, and by rejecting others to keep the population size constant. After the predetermined number of generations is performed, the algorithm converges to the best chromosome, which hopefully represents the optimal solution or may be a near-optimal solution of the problem. The mutation and crossover operation used in this algorithm is shown respectively in **Figure 2** and **Figure 3**.

Zafari et al. [22] in “A hybrid genetic algorithm for solving the vehicle routing problem” selected 110 test problems from (http:// branchandcut.org/VRP/data/) and solved them with HGA. In these test problems, the range of the number of customer was 12 to 149. The comparison of the best solution of Lingo and the proposed algorithm showed that the HGA algorithm obtained the best solution of lingo exactly in 85 cases from 110 test problems. Extensive computational tests on standard instances from the literature confirmed the effectiveness of the presented approach. So to solve the proposed FCVRP model, the HGA algorithm is applied.

A simple GA may not perform well in this situation. Therefore, the GA developed in this paper is hybridized with one heuristic to improve the solution further. The 2-opt local search heuristic is generally used to improve the solutions of the hard optimization problems. However, it increases the computational time because every two swaps are examined. If a new solution generated is better than the original one, or parent, in terms of quality, it will replace and become the parent. All two swaps are examined again until there is no further improvement in the parent [23]. The 2-opt exchange operation is shown in **Figure 4**, in which the edge (i, i + 1) and (j, j + 1) are replaced by edge (i, j) and (i +1, j +1), thus reversing the direction of customers between i + 1 and j [24].

In this section, the proposed algorithm is tested on three categories of VRP problems [25]. The first group includes problems that Lingo optimization software can reach optimum solution in a reasonable time. In the second category, the Lingo solution is optimized but the time to solve the problem is not appropriate and finally, the third category, which includes problems Lingo not able to solve them. It is important to note that this algorithm has only been tested 10 times for each problem and the best answer is shown. Then, to evaluate the quality of the solutions, the model is solved by the lingo 9 and the results of this have been compared with the results of the presented metaheuristics algorithm. For this purpose, the relative gap between the best solutions obtained from the Lingo (Z (Lingo)) with the best solutions obtained from the proposed HGA (Z (HGA)) is computed by: 100[Z (HGA)-Z (Lingo)]/Z (Lingo).

The comparison of Lingo with the proposed algorithm shows that our proposed algorithm can obtain approximately an optimal solution in less time than Lingo as shown in **Table 2** and **3**. The average gap between the optimal and the HGA solutions is 0.32% showing the efficiency of the proposed HGA. Furthermore, increasing the size of the problem increases the solution time of Lingo exponentially while it does not tangible effect on the solution time of the proposed algorithm as shown in **Figure 5**. Problem solving results in small, medium and large sizes is shown respectively, in **table 2** and **3**.

Test code | No. of customers | No. of vehicles | α -level | Lingo 9.0 | HGA | Gap (%) | Saving (%) | ||
---|---|---|---|---|---|---|---|---|---|

Best solution | Time Run(Sec) | Best solution | Time Run(Sec) | ||||||

E-n13-k4 | 13 | 4 | 1 | 277 | 280 | 277 | 8 | 0 | |

0.8 | 277 | 280 | 277 | 8 | 0 | ||||

0.6 | 268 | 280 | 268 | 8 | 0 | ||||

0.5 | 247 | 280 | 247 | 8 | 0 | ||||

0.4 | 240 | 280 | 240 | 8 | 0 | 2.9 | |||

0.2 | 237 | 280 | 237 | 8 | 0 | 4.1 | |||

0 | 230 | 280 | 230 | 8 | 0 | 6.9 | |||

P-n16-k8 | 16 | 8 | 1 | Inf | - | Inf | - | - | |

0.8 | Inf | - | Inf | - | - | ||||

0.6 | 461.32 | 409 | 460.83 | 18 | 0.1 | ||||

0.5 | 450 | 409 | 450.45 | 18 | 0.1 | ||||

0.4 | 451.34 | 409 | 451.875 | 18 | 0.1 | 0.4 | |||

0.2 | 440.37 | 409 | 440.33 | 18 | 0 | 2.2 | |||

0 | 428.56 | 409 | 428.63 | 18 | 0 | 4.7 | |||

P-n19-k2 | 19 | 2 | 1 | Inf | - | Inf | - | - | |

0.8 | Inf | - | Inf | - | - | ||||

0.6 | 223.39 | 339 | 231.48 | 19 | 0.1 | ||||

0.5 | 212 | 339 | 212.31 | 19 | 0.1 | ||||

0.4 | 196.65 | 339 | 196.65 | 19 | 0 | 7.3 | |||

0.2 | 196.65 | 339 | 196.65 | 19 | 0 | 7.3 | |||

0 | 196.65 | 339 | 196.65 | 19 | 0 | 7.3 | |||

P-n20-k2 | 20 | 2 | 1 | Inf | - | Inf | - | - | |

0.8 | Inf | - | Inf | - | - | ||||

0.6 | 218.31 | 370 | 222.22 | 22 | 1.8 | ||||

0.5 | 216 | 370 | 217.39 | 22 | 0.6 | ||||

0.4 | 209.12 | 370 | 212.31 | 22 | 1.4 | 1.7 | |||

0.2 | 209.12 | 370 | 212.31 | 22 | 1.4 | 1.7 | |||

0 | 208.20 | 370 | 208.33 | 22 | 0 | 3.6 | |||

P-n21-k2 | 21 | 2 | 1 | Inf | - | Inf | - | - | |

0.8 | 212 | 563 | 215.98 | 26 | 1.8 | ||||

0.6 | 215 | 563 | 215.05 | 26 | 0 | ||||

0.5 | 211 | 563 | 212.77 | 26 | 0.8 | ||||

0.4 | 208.29 | 563 | 208.33 | 26 | 0 | 1.3 | |||

0.2 | 208.29 | 563 | 208.33 | 26 | 0 | 1.3 | |||

0 | 204 | 563 | 204.1 | 26 | 0 | 3.3 | |||

P-n22-k2 | 22 | 2 | 1 | Inf | - | Inf | - | - | |

0.8 | Inf | - | Inf | - | - | ||||

0.6 | 222.22 | 806 | 222.62 | 28 | 0.2 | ||||

0.5 | 217 | 806 | 217.82 | 28 | 0.4 | ||||

0.4 | 212.31 | 806 | 210.53 | 28 | 0.1 | 2.6 | |||

0.2 | 212.31 | 806 | 210.53 | 28 | 0.1 | 2.6 | |||

0 | 207.13 | 806 | 207.81 | 28 | 0 | 3.8 | |||

E-n22-k4 | 22 | 4 | 1 | Inf | - | Inf | - | - | |

0.8 | Inf | - | Inf | - | - | ||||

0.6 | 394.75 | 10843 | 400 | 32 | 1 | ||||

0.5 | 375 | 10843 | 375 | 32 | 0 | ||||

0.4 | 369 | 10843 | 370.37 | 32 | 0.4 | ||||

0.2 | 360.54 | 10843 | 363.64 | 32 | 0.9 | ||||

0 | 355 | 10843 | 357.14 | 32 | 0.6 | ||||

E-n23-k3 | 23 | 3 | 1 | Inf | - | Inf | - | - | - |

0.8 | 569.89 | - | 573.39 | 38 | 0.6 | - | |||

0.6 | 568.57 | 946 | 568.57 | 38 | 0 | ||||

0.5 | 569 | 946 | 569 | 38 | 0 | ||||

0.4 | 564.08 | 946 | 567.85 | 38 | 0.6 | 0.8 | |||

0.2 | 564.08 | 946 | 567.85 | 38 | 0.6 | 0.8 | |||

0 | 563.81 | 946 | 563.81 | 38 | 0 | 1 |

**Table 2:** Comparison of the performance of the proposed HGA for small and medium scale of problem.

Test code | No. of customers/vehicles | α -level | Lingo 9.0 | HGA | The best solution ever found | Gap (%) | Saving | ||
---|---|---|---|---|---|---|---|---|---|

Lower Bound | Time Run(Sec) | Best solution | Time Run(Sec) | ||||||

P-n23-k9 | 23/9 | 1 | Inf | - | Inf | - | - | - | |

0.8 | Inf | - | Inf | - | - | - | |||

0.6 | Inf | - | Inf | - | - | - | |||

0.5 | 416.95 | 1800 |
534.76 | 47 | 529 | 1.08 | |||

0.4 | 416.95 | 1800 | 510.64 | 47 | - | - | 3.5 | ||

0.2 | 361.85 | 1800 | 510.64 | 47 | - | - | 3.5 | ||

0 | 340.23 | 1800 | 504.49 | 47 | - | - | 4.7 | ||

B-n31-k5 | 31/5 | 1 | 498.54 | 1800 | 709.22 | - | - | - | |

0.8 | 498.51 | 1800 | 692.04 | - | - | - | |||

0.6 | 504.14 | 1800 | 692.04 | 82 | - | - | |||

0.5 | 522.35 | 1800 | 689.65 | 82 | 672 | 2.6 | |||

0.4 | 503.16 | 1800 | 632.27 | 82 | - | - | 5.9 | ||

0.2 | 484.17 | 1800 | 617.28 | 82 | - | - | 8.1 | ||

0 | 422.88 | 1800 | 4613.5 | 82 | - | - | 8.7 | ||

A-n33-k6 | 33/6 | 1 | Inf | 1800 | Inf | - | - | - | |

0.8 | 570.52 | 1800 | 813 | - | - | - | |||

0.6 | 572.07 | 1800 | 769 | 112 | - | - | |||

0.5 | 593.16 | 1800 | 751.88 | 112 | 742 | 1.3 | |||

0.4 | 570.95 | 1800 | 735.294 | 112 | - | - | 1 | ||

0.2 | 569.11 | 1800 | 724.64 | 112 | - | - | 2.4 | ||

0 | 535.65 | 1800 | 680.27 | 112 | - | - | 8.3 | ||

A-n37-k6 | 37/6 | 1 | 615.13 | 1800 | 1008 | 172 | - | - | |

0.8 | 610.59 | 1800 | 980.39 | 172 | - | - | |||

0.6 | 612 | 1800 | 972.76 | 172 | - | - | |||

0.5 | 613.63 | 1800 | 949.67 | 172 | 949 | 0 | |||

0.4 | 568.13 | 1800 | 906.32 | 172 | - | - | 4.5 | ||

0.2 | 563.76 | 1800 | 865.59 | 172 | - | - | 8.7 | ||

0 | 569.68 | 1800 | 857.63 | 172 | - | - | 9.6 | ||

A-n38-k5 | 38/5 | 1 | Inf | 1800 | Inf | - | - | - | |

0.8 | Inf | 1800 | Inf | - | - | - | |||

0.6 | 524.84 | 1800 | 833.33 | 144 | - | - | |||

0.5 | 525.20 | 1800 | 769.23 | 144 | 730 | 5.37 | |||

0.4 | 530.96 | 1800 | 751.88 | 144 | - | - | - | ||

0.2 | 526.33 | 1800 | 740.74 | 144 | - | - | - | ||

0 | 524.91 | 1800 | 740.74 | 144 | - | - | - | ||

A-n44-k6 | 44/6 | 1 | Inf | 1800 | Inf | - | - | - | |

0.8 | Inf | 1800 | Inf | - | - | - | |||

0.6 | 864 | 1800 | 1023.57 | 223 | - | - | |||

0.5 | 751.63 | 1800 | 980.39 | 223 | 934 | 5 | |||

0.4 | 728.53 | 1800 | 915.45 | 223 | - | - | 1.9 | ||

0.2 | 712.14 | 1800 | 909.91 | 223 | - | - | 2.7 | ||

0 | 712.14 | 1800 | 909.91 | 223 | - | - | 2.7 | ||

B-n50-k7 | 50/7 | 1 | 672.83 | 1800 | 909.91 | - | - | - | |

0.8 | 653.85 | 1800 | 866.29 | 334 | - | - | |||

0.6 | 625.14 | 1800 | 833.33 | 334 | - | - | |||

0.5 | 598.16 | 1800 | 813.33 | 334 | 741 | 9.7 | |||

0.4 | 538.75 | 1800 | 741.28 | 334 | - | - | 3.6 | ||

0.2 | 512.24 | 1800 | 704.22 | 334 | - | - | 4.9 | ||

0 | 473.46 | 1800 | 689.65 | 334 | - | - | 6.9 | ||

P-n50-k10 | 50/10 | 1 | Inf | - | Inf | - | - | - | |

0.8 | Inf | - | Inf | - | - | - | |||

0.6 | 673.48 | 1800 | 787.40 | 350 | - | - | |||

0.5 | 640.65 | 1800 | 769.23 | 350 | 696 | 11 | |||

0.4 | 555.73 | 1800 | 680.27 | 350 | - | - | 2.2 | ||

0.2 | 541.51 | 1800 | 671.14 | 350 | - | - | 3.5 | ||

0 | 546.13 | 1800 | 666.67 | 350 | - | - | 4.2 |

**Table 3:** Comparison of the performance of the proposed HGA for large-scale of problem.

According to **table 2**, the saving of transportation cost for small and medium scale of problem is computed by: 100[Z(HGA)-Z(Lingoα_{=0.5})]/ Z(Lingoα_{=0.5}) and according to **table 3**, the saving of transportation cost for large scale of problem is computed by:

100[Z(HGA)-Zα_{=0.5} (The best solution ever found)]/Zα_{=0.5} (The best solution ever found).

The comparison of best solution of both Lingo and HGA shows that with decreasing α, also the transportation cost decrease as shown in **Figure 6**. This means that with considering the acceptable extra loading, we have a saving in travel cost.

In order to provide a better understanding of the model, the Kalleh Company’s data of 2011 is used. The Company situated at Amol city and their production activities has started since 1983. Products of this company are divided into three categories: dairy products, sausages and salami, and prepared foods. For studying the proposed model in this company, we consider the customers and the vehicles that assigned to their prepared foods. The company, having 10 trucks, will serve 23 cities in the Iran. These data are shown separately in **tables 4** and **5**.

Name of vehicle | Number of vehicle | Capacity of vehicle(Ton) |
---|---|---|

Ten wheel drive Renault | 5 | 8.5 |

Ten wheel Tkv | 5 | 8.5 |

**Table 4:** Vehicles.

Customer | Rasht | Esfahan | Shiraz | Karaj | Tehran | Sorkhrood | Tonekabon | Sari | Babol | Amol | Arak |

Demand(kilo) | 5635 | 7371 | 6102 | 7173 | 37949 | 918 | 882 | 2528 | 1245 | 1311 | 1486 |

Customer | Gorgan | Yazd | Mashhad | Kerman | Ghazvin | Booshehr | Ahvaz | Bandar-abbas | Tabriz | Hamedan | |

Demand(kilo) | 1290 | 1798 | 2993 | 2293 | 3607 | 4147 | 8521 | 4855 | 3900 | 1835 |

**Table 5:** Demand of the customers.

As we mention before, any vehicle regardless of its capacity can load 500 kg extra load. But with increasing loading, driver satisfaction also decreases. On the other hand, it is not convenient for driver, if he loads less than a certain amount of this. So the capacity of the vehicle can be considered as fuzzy numbers with triangular membership function.

According to **table 6**, the comparison of best solution of both Lingo and HGA shows that with decreasing α, (increasing loading) also the transportation cost decrease. This means that with considering the acceptable extra loading, we have a saving in travel cost (**Figure 7**).

No. of customers | No. of vehicles | α -level | Lingo 9.0 | HGA | Saving (%) | ||
---|---|---|---|---|---|---|---|

Lower Bound | Time Run(Sec) | Best solution | Time Run(Sec) | ||||

23 | 10 | 1 | Inf | - | Inf | - | |

0.8 | Inf | - | Inf | - | |||

0.6 | Inf | - | Inf | - | |||

0.5 | 11217 | 1800 | 14471.78 | 50 | |||

0.4 | 9381 | 1800 | 14285.71 | 50 | 1.2 | ||

0.2 | 7015 | 1800 | 14084.5 | 50 | 2.7 | ||

0 | 7015 | 1800 | 14084.5 | 50 | 2.7 |

**Table 6:** Results of the case study.

This paper has presented a vehicle routing problem with fuzzy fleet capacity (FCVRP) in which the right hand coefficient, is a triangular fuzzy number. According to statistics published by the freight companies, any vehicle regardless of its capacity can load 500 kg extra load. But with increasing loading, driver satisfaction also decreases. On the other hand, it is not convenient for driver, if he loads less than a certain amount of this. Thus, the capacity of the vehicle can be considered as fuzzy numbers with triangular membership function. We proposed a possibilistic 0-1 linear programming model to deal with this problem. To solve the proposed possibilistic optimization model, we apply an efficient possibilistic method proposed by Parra et al. [1]. In addition we developed a hybrid genetic algorithm (HGA) to find the short routes with the minimum travel cost. To verify the solution technique, 16 test problems have been solved by the Lingo 9.0 software and the related results obtained by the proposed hybrid genetic algorithm (HGA) have been very efficient approaching to the optimal solution. For small sizes, the average gap between the proposed HGA and Lingo solutions has been equal to 0.32 showing an acceptable result. The comparison of best solution of both Lingo and HGA shows that with decreasing α, (increasing loading) also the transportation cost decrease. This means that with considering the acceptable extra loading, we have a saving in travel costs.

- Parra AM, Terol AB, Gladish BP, Uria MVR (2005) Solving a multi-objective possibilistic problem through compromise programming. Eur J Oper Res 164: 748-759.
- Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Science 6: 80-91.
- Sharda R, Vob S (2008) The vehicle routing problem: Latest advances and new challenges. Springer Science, New York, USA.
- Master D, Braysy O, Dullaert W (2007) A multi-parametric evolution strategies algorithm for vehicle routing problems. Expert Syst Appl 32: 508-517.
- Erbao C, Mingyong L (2009) A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands. J Comput Appl Math 231: 302-310.
- Yanwen D, Masatoshi K (2010) Two-stage Model of Vehicle Routing Problem with Fuzzy Demands and its Ant Colony System Algorithm. The Ninth International Symposium on Operations Research and Its Applications.
- Yang P, Yemei Q (2010) A particle swarm optimization to vehicle routing problem with fuzzy demands. Journal of Convergence Information Technology 5: 112-119.
- Erbao C, Mingyong L (2010) The open vehicle routing problem with fuzzy demands. Expert Syst Appl 37: 2405-2411.
- Lian X, Xiaoxia D (2011) Research on the Vehicle Routing Problem with Fuzzy Demands. Adv Mat Res 186: 570-575.
- Changshi L, Fuhua H (2010) Hybrid Heuristics for Vehicle Routing Problem with Fuzzy Demands. Third International Joint Conference on Computational Science and Optimization.
- Tang J, Pan Z, Fung RYK, Lau H (2009) Vehicle routing problem with fuzzy time windows. Fuzzy Sets and Systems 160: 683-695.
- Gupta R, Singh B, Pandey D (2010) Multi-Objective Fuzzy Vehicle Routing Problem: A Case Study. Int J Contemp Math Sciences 5: 1439-1454.
- Zheng Y, Liu B (2006) Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm. Appl Math Comput 176: 673-683.
- Negoita CV, Minoiu S, Stan E (1976) On considering imprecision in dynamic programming. Econ Comput Econ Cybernet Stud Res 3: 83-95.
- Zerafat-Angiz M, Saati S, Memariani A, Movahedi MM (2006) Solving Possibilistic Linear Programming problem considering membership function of the coefficients. Adv. in Fuzzy Sets & Systems 2: 131-142.
- Lai YJ, Hwang Ch (1992) Fuzzy mathematical programming: Methods and applications. Springer-Verlag, Berlin, Heidelberg, New York.
- Pishvaee MS, Torabi SA (2010) A possibilistic programming approach for closed-loop supply chain network design under uncertainty. Fuzzy Sets and Systems 161: 2668-2683.
- Jimenez M (1996) Ranking fuzzy numbers through the comparison of its expected intervals. International Journal of Uncertainty, Fuzziness and Knowledge Based Systems 4: 379-388 .
- Jimenez LM, Uria MVR, Arenas M, Bilbao A (2000) Solving a possibilistic linear program through compromise programming. Mathware and Soft Computing 7: 175-184.
- Talbi A, Ghazali E (2009) Metaheuristics: From design to implementation. John Wiley and sons.
- Eiben AE, Smith JE (2003) Introduction to evolutionary computing. Springer, New York.
- Zafari A, Hashemi SMT, Yousefi Khoshbakht M (2010) A Hybrid Effective Genetic Algorithm for Solving the Vehicle Routing Problem. International Journal of Industrial Engineering and Production Management 2: 63-76.
- Ho W, Ho GTS, Ji P, Lau HCW (2008) A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Arti?cial Intelligence 21: 548-557.
- Tavakkoli-Moghaddam R, Gazanfari M, Alinaghian M, Salamatbakhsh A, Norouzi N (2011) A new mathematical model for a competitive routing problem with time windows solved by simulated annealing. Journal of Manufacturing System 30: 83-92.
- http://branchandcut.org/VRP/data/?74c6f3f0

Select your language of interest to view the total content in your interested language

- ACS Nano
- AI Algorithm
- Advanced Materials
- Advantages of E-Business
- Applied Engineering
- Applied Statistics
- Architect
- Architectural Drawing
- Architectural Engineering
- Artificial Intelligence
- Automated Mining
- Automation
- Behavior-based systems
- Bioengineering Application
- Biological Engineering
- Biomaterial Science
- Biomechanics
- Biomechanics and Robotics
- Biomedical Equipment
- Biomedical Instrumentation
- Biomedical Services
- Biomedical science
- Biomimetics
- Bioprocessing
- Bioreactors
- Biosensor elements
- Biotechnology Engineering
- Brittle Materials
- Building design
- Business & Management
- Cell Apoptosis
- Ceramics Engineering
- Cognitive Systems Engineering
- Commercialization of New Techniques
- Composite Materials
- Computational Neuroscience
- Concrete
- Construction
- Construction Engineering
- Construction Estimating Software
- Design and Microfabrication
- Digital Image Processing
- Dynamical System
- Electronic Material Development
- Engineering Drawing
- Entrepreneurship
- Fabric Formwork
- Fermentation Science
- Finance management
- Fuzzy Logic
- Gene Expressions
- Genetics
- Health care management
- Industrial Crystallization
- Industrial Engineering
- Industrial Robotics
- Intelligent Robotics
- Interior Design
- Interior Designing
- Internal Medicine
- Landscape Architecture
- Logistics
- Lovotics
- Management Cybernetics
- Manufacturing system
- Materials Engineering
- Materials Management
- Medical Device
- Medical Robotics
- Medication
- Metallic Materials (Ferrous & Nonferrous)
- Mobile Device
- Mobile Repots
- Molecular Electronics
- Molecular and Medicine science
- Nano Composites
- Nano Materials
- Nano Particles
- Nano Structures
- Neural Networks
- Neurorobotics
- Nonlinear Dynamics
- Operations Research
- Polymeric Materials
- Porous Materials
- Process Engineering
- Production and Operations Management
- Regenerative Medication
- Rehabilitation Technology
- Reliability engineering
- Robotic Rehabilitation
- Semiconductors
- Simulation
- Social Robots
- Sociology of Architecture
- Spintronics
- Stochastic control
- Supply Chain Management
- Technologies Management
- Telerobotics
- Tissue Engineering Development
- Urban Design
- Urban Planner
- swarm intelligence and robotics

- Advances in Robotics & Automation
- Engineering and Technology Journals
- Electrical Engineering Journals
- Software Engineering Journals
- Architectural Engineering Journals
- Automation Journals
- Management Journals
- Bioengineering Journals
- Aerospace Engineering Journals
- Instrumentation Engineering Journals
- Tissue Engineering Journals
- Engineering Journals
- Aeronautics Journal
- Material Sciences Journal
- Mechanical Engineering Journal
- Automobile Engineering Journal

- Total views:
**13408** - [From(publication date):

February-2013 - Jul 17, 2019] - Breakdown by view type
- HTML page views :
**9543** - PDF downloads :
**3865**

**Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals**

International Conferences 2019-20