A variant fisher and Jaikuamr algorithm to solve capacitated vehicle routing problem
Vehicle Routing Problem (VRP) is a real life constraint satisfaction problem to find minimal travel distances of vehicles to serve customers. Capacitated CVRP (CVRP) is the simplest form of VRP considering vehicle capacity constraint. Constructive and clustering are the two popular approaches to...
| Main Authors: | , , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English English |
| Published: |
IEEE
2017
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/61954/ http://irep.iium.edu.my/61954/ http://irep.iium.edu.my/61954/ http://irep.iium.edu.my/61954/1/61954-A%20Variant%20Fisher%20and%20Jaikuamr%20Algorithm.pdf http://irep.iium.edu.my/61954/2/61954-A%20variant%20fisher%20and%20Jaikuamr%20algorithm-SCOPUS.pdf |
| Summary: | Vehicle Routing Problem (VRP) is a real life
constraint satisfaction problem to find minimal travel distances
of vehicles to serve customers. Capacitated CVRP (CVRP) is the
simplest form of VRP considering vehicle capacity constraint.
Constructive and clustering are the two popular approaches to
solve CVRP. A constructive approach creates routes and
attempts to minimize the cost at the same time. On the other
hand, a clustering based method first assigns nodes into vehicle
wise cluster and then generates route for each vehicle. Route
generation is a traveling sales man problem (TSP) and any TSP
optimization method is useful for this purpose. Fisher and
Jaikumar algorithm is a well-known cluster based method which
creates clusters with a geometric method partitioning the
customer plane into equal angular cones where the total cones
are equal to the number of vehicles. This study investigates a
variant of Fisher and Jaikumar algorithm owning to solve CVRP
efficiently. In the proposed method clusters form such a way that
each cluster cone contains equal number of nodes. The initial
clusters formation in a method are subjected to route
optimization. Three prominent metaheuristic methods (i.e.,
genetic algorithm, ant colony optimization, particle swarm
optimization) for TSP are considered for route optimization. The
efficiency of the proposed method is identified while solving
benchmark CVRPs. Experimental result reveals that variant
Fisher and Jaikumar with particle swarm optimization is an
effective method in solving CVRP. |
|---|