ISSN: 2169-0316
Industrial Engineering & Management
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
 
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

A Possibilistic Programming Approach for Vehicle Routing Problem with Fuzzy Fleet Capacity (FCVRP)

Seyed Mohammad Seyedhosseini1*, Shima Kabirian1, Ahmad Makui1 and Nooraddin Dabiri2
1Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran, Iran
2Department 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: seyedhosseini@iust.ac.ir
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

Abstract

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.

Keywords
Fuzzy mathematical programming; Vehicle routing problem; Fuzzy fleet capacity; Possibilistic programming; Hybrid genetic algorithm
Introduction
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.
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.
Fuzzy CVRP Model Formulation
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= {v0,v1,v2,…,vn} is a set of n+1(n≥1) vertices. We distinguish the depot v0 and exactly n customers {v1,v2,…,vn}. E= {(vii,vj) | 0≤ i , j ≤ n , i≠j} is the set of |V|*(|V|-1) edges(arcs) between the vertices, called the roads. D= (dij) is a matrix, where dij≥0 is the distance corresponding to edge (vii,vj); dii is always equal to 0 and dij=dji. 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, xij=1 and otherwise xij=0 and if the node i, visited with the vehicle k, yik=1 and otherwise yik=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.
The Proposed Solution Method
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 ∈Rn 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:
Hybrid Genetic Algorithm
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].
Numerical Examples
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.
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.
Case Study
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.
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).
Conclusion
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.
References

 

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

Share This Article

Relevant Topics

Article Usage

  • Total views: 3836
  • [From(publication date):
    February-2013 - Oct 01, 2016]
  • Breakdown by view type
  • HTML page views : 83
  • PDF downloads :3753
 
 

Post your comment

captcha   Reload  Can't read the image? click here to refresh

OMICS International Journals
 
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
 
 
OMICS International Conferences 2016-17
 
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings
 
 

Contact Us

Agri, Food, Aqua and Veterinary Science Journals

Dr. Krish

agrifoodaquavet@omicsinc.com

1-702-714-7001 Extn: 9040

Clinical and Biochemistry Journals

Datta A

clinical_biochem@omicsinc.com

1-702-714-7001Extn: 9037

Business & Management Journals

Ronald

business@omicsinc.com

1-702-714-7001Extn: 9042

Chemical Engineering and Chemistry Journals

Gabriel Shaw

chemicaleng_chemistry@omicsinc.com

1-702-714-7001 Extn: 9040

Earth & Environmental Sciences

Katie Wilson

environmentalsci@omicsinc.com

1-702-714-7001Extn: 9042

Engineering Journals

James Franklin

engineering@omicsinc.com

1-702-714-7001Extn: 9042

General Science and Health care Journals

Andrea Jason

generalsci_healthcare@omicsinc.com

1-702-714-7001Extn: 9043

Genetics and Molecular Biology Journals

Anna Melissa

genetics_molbio@omicsinc.com

1-702-714-7001 Extn: 9006

Immunology & Microbiology Journals

David Gorantl

immuno_microbio@omicsinc.com

1-702-714-7001Extn: 9014

Informatics Journals

Stephanie Skinner

omics@omicsinc.com

1-702-714-7001Extn: 9039

Material Sciences Journals

Rachle Green

materialsci@omicsinc.com

1-702-714-7001Extn: 9039

Mathematics and Physics Journals

Jim Willison

mathematics_physics@omicsinc.com

1-702-714-7001 Extn: 9042

Medical Journals

Nimmi Anna

medical@omicsinc.com

1-702-714-7001 Extn: 9038

Neuroscience & Psychology Journals

Nathan T

neuro_psychology@omicsinc.com

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

John Behannon

pharma@omicsinc.com

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

social_politicalsci@omicsinc.com

1-702-714-7001 Extn: 9042

 
© 2008-2016 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version