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
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.
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
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:// 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).
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.
Select your language of interest to view the total content in your interested language
Share This Article
Relevant Topics
Disc ACS Nano
Disc AI Algorithm
Disc Advanced Materials
Disc Aerodynamics
Disc Aeroelasticity
Disc Aerospace Dynamics
Disc Aerospace Engineering techniques
Disc Air Safety
Disc Aircraft
Disc Aircraft Flight Mechanics
Disc Android Technology
Disc Applied Arts
Disc Applied Engineering
Disc Applied Statistics
Disc Applied Theories on Machines
Disc Architect
Disc Architectural Designing
Disc Architectural Drawing
Disc Architectural Engineering
Disc Astrodynamics
Disc Automated Mining
Disc Automation
Disc Automation Devices
Disc Automobile Engineer
Disc Automotive Engineering
Disc Automotive Industry
Disc Aviation
Disc Avionics
Disc Bioengineering Application
Disc Biological Engineering
Disc Biomaterial Science
Disc Biomedical Equipment
Disc Biomedical Instrumentation
Disc Biomedical Services
Disc Biomedical science
Disc Biomimetics
Disc Bioprocessing
Disc Bioreactors
Disc Biosensor elements
Disc Biotechnology Engineering
Disc Bridges
Disc Brittle Materials
Disc Building design
Disc Buildings
Disc Cell Apoptosis
Disc Ceramics Engineering
Disc Chemistry
Disc Cloud
Disc Cognitive Systems Engineering
Disc Cold Formed Steel
Disc Color science
Disc Commercialization of New Techniques
Disc Composite Materials
Disc Computation theory
Disc Computational Neuroscience
Disc Computer Hardware
Disc Computer Simulation
Disc Concrete
Disc Conditioning Monitoring
Disc Construction
Disc Construction Engineering
Disc Construction Estimating Software
Disc Control System
Disc Controllers
Disc Cryptography
Disc Design and Microfabrication
Disc Development Process
Disc Diesel Engine
Disc Digital Image Processing
Disc Dyes
Disc Dynamic Information
Disc Dynamical System
Disc Earthquake Engineering
Disc Earthquake Resistance
Disc Electronic Material Development
Disc Engine
Disc Engine Performance
Disc Engineering Design
Disc Engineering Drawing
Disc External Force
Disc Fabric Formwork
Disc Fashion Design
Disc Fashion Technology
Disc Fermentation Science
Disc Fiber
Disc Fiber Engineering
Disc Fiber Innovation
Disc Fibrous Materials
Disc Flight Dynamics
Disc Fluid Bodies
Disc Flying Wheel
Disc Fuel Economy
Disc Fuzzy Logic
Disc Gene Expressions
Disc Genetics
Disc Germ cell tumours
Disc Global optimization
Disc Health care management
Disc Helmet
Disc Human-Machine-Interfaces
Disc Hydraulic Engineering
Disc IT Management
Disc Ignititon System
Disc Image Recognition
Disc Industrial Crystallization
Disc Industrial Engineering
Disc Industrial Robotics
Disc Information Systems
Disc Information Technology
Disc Information Visualization
Disc Intelligent Robotics
Disc Interior Design
Disc Interior Designing
Disc Internet Communication Technology
Disc Internet computing
Disc Landscape Architecture
Disc Logistics
Disc Machine
Disc Machines
Disc Management Cybernetics
Disc Manufacturing system
Disc Material Sciences
Disc Materials Engineering
Disc Materials Management
Disc Mathematical Model
Disc Mathematical optimization
Disc Mechanical Properties
Disc Mechanical Systems
Disc Mechanism
Disc Mechatronics
Disc Mechatronics and Robotics
Disc Medical Device
Disc Medical Robotics
Disc Medical Textile
Disc Metallic Materials (Ferrous & Nonferrous)
Disc Mobile Device
Disc Mobile Repots
Disc Modeling and Simulation
Disc Modular Architecture
Disc Molecular Electronics
Disc Molecular and Medicine science
Disc Nano Composites
Disc Nano Materials
Disc Nano Particles
Disc Nano Structures
Disc Network
Disc Neural Networks
Disc Neurorobotics
Disc Nonlinear Dynamics
Disc Operations Research
Disc Parallel Processing
Disc Polymer Sciences
Disc Polymer Structure
Disc Polymeric Materials
Disc Porous Materials
Disc Power System
Disc Process Engineering
Disc Product Quality
Disc Production and Operations Management
Disc Project development
Disc Real Time
Disc Regenerative Medication
Disc Rehabilitation Technology
Disc Reinforced Concrete
Disc Reliability engineering
Disc Robotic Rehabilitation
Disc Robotics Methods
Disc Rocketry
Disc Seismic Design
Disc Semiconductors
Disc Sensor Technology
Disc Signal Processing
Disc Simulation
Disc Simulator
Disc Social Robots
Disc Sociology of Architecture
Disc Soft Computing and Computational Intelligent
Disc Software Architecture
Disc Software Component
Disc Software Quality
Disc Software design
Disc Space
Disc Spark Ignition
Disc Splitting Method
Disc Stainless Steel
Disc Steel Industry
Disc Stochastic control
Disc Structural Design
Disc Structural Engineering
Disc Structural Steel
Disc Sustainability
Disc Technologies Management
Disc Technology
Disc Telerobotics
Disc Textile Design
Disc Textile Engineering
Disc Textile Industries
Disc Textile Science
Disc Textile Technology
Disc Thermodynamics Methods
Disc Tissue Engineering Development
Disc Ubiquitous Computing
Disc Unmanned-Vehicles
Disc Urban Design
Disc Urban Planner
Disc Web Service
Disc Wireless Sensor
Disc Wireless Technology
Recommended Journals
Disc Steel Structures Journals
Disc Optimization Journals
Disc Engineering and Technology Journals
Disc Electrical Engineering Journals
Disc Software Engineering Journals
Disc Architectural Engineering Journals
Disc Automation Journals
Disc Management Journals
Disc Bioengineering Journals
Disc Aerospace Engineering Journals
Disc Instrumentation Engineering Journals
Disc Tissue Engineering Journals
Disc Engineering Journals
Disc Textile Science Journals
Disc Aeronautics Journal
Disc Material Sciences Journal
Disc Mechanical Engineering Journal
Disc Automobile Engineering Journal
  View More»
Recommended Conferences
Disc 2nd Industrial Biotechnology Congress
July 28-29, 2016, Berlin, Germany
View More»
Article Tools
Disc Export citation
Disc Share/Blog this article
Article usage
  Total views: 3773
  [From(publication date):
February-2013 - Jun 29, 2016]
  Breakdown by view type
  HTML page views : 41
  PDF downloads :3732

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

1-702-714-7001 Extn: 9040

Clinical and Biochemistry Journals

Datta A

1-702-714-7001Extn: 9037

Business & Management Journals


1-702-714-7001Extn: 9042

Chemical Engineering and Chemistry Journals

Gabriel Shaw

1-702-714-7001 Extn: 9040

Earth & Environmental Sciences

Katie Wilson

1-702-714-7001Extn: 9042

Engineering Journals

James Franklin

1-702-714-7001Extn: 9042

General Science and Health care Journals

Andrea Jason

1-702-714-7001Extn: 9043

Genetics and Molecular Biology Journals

Anna Melissa

1-702-714-7001 Extn: 9006

Immunology & Microbiology Journals

David Gorantl

1-702-714-7001Extn: 9014

Informatics Journals

Stephanie Skinner

1-702-714-7001Extn: 9039

Materials Science Journals

Rachle Green

1-702-714-7001Extn: 9039

Mathematics and Physics Journals

Jim Willison

1-702-714-7001 Extn: 9042

Medical Journals

Nimmi Anna

1-702-714-7001 Extn: 9038

Neuroscience & Psychology Journals

Nathan T

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

John Behannon

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

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