 Open Access
 Total Downloads : 454
 Authors : Sanjay Kulkarni, Dr Nagendra Sohani, Neha Sehta
 Paper ID : IJERTV3IS051534
 Volume & Issue : Volume 03, Issue 05 (May 2014)
 Published (First Online): 28052014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Capacitated Vehicle Routing Using Nearest Neighbor Algorithm in Supply Chain
Sanjay Kulkarni, Dr. Nagendra Sohani
(Dept of Mechanical Engineering) IETDAVV
Indore, India
Neha Sehta
Department Of Information Technology SDBCT
Indore, India
Abstract One of the important factors in implementing supply chain management is to efficiently control the physical flow of the supply chain. Due to its importance many organizations are trying to develop efficient methods to reduce cost and improve responsiveness to various customer demands. Travelling Salesman problem (shortest Hamiltonian circuit) is well known for finding giant tour in planning horizon. Being NP Hard in nature there are several methods available to find near optimal solution even for larger problems. In this paper two algorithms based on nearest Neighbor strategy are proposed for capacitated vehicle routing in supply chain and the results are analyzed for the optimization purpose.
Keywords Supply Chain, Capacitated Vehicle Routing, Nearest Neighbor Algorithm

INTRODUCTION
Customer focused market has made the supply chain to continuously redesign and enhance their transportation network. One of the most important things in implementing supply chain management is to efficiently control physical flow of the supply chain. Apte and Vishwanathan1 (2000) mentioned that 30% of price is incurred in the distribution process. Therefore improvement of the material flow through efficient management of the distribution process is considered as an essential activity to increase customer satisfaction. Thus many companies are investigating and developing methods to efficiently control their material flow.
In the planning horizon, to visit a node (supply/ demand destination) with objective to minimize the total distance/ cost is dealt in by Travelling Salesman Problem. Vehicle capacity constraint can be applied on the giant tour to get number of vehicles required to satisfy customers demand and the routes for each vehicle. Being NPHard in nature Lee Y.H. , Jung W
J. Lee K M6, (2006) used ratio of transportation cost to minimum transportation cost to limit the number of feasible solution.
The Classic Vehicle Routing Problem (VRP) involves the service of a set of customer with known demands by a fleet of vehicles from a single distribution centre. The objective of the VRP is to minimize the total distance and the number of vehicles which start and end their tours at the central depot. Mosleiov2 (1998) stated that many applications of VRP involving pickup and delivery services are referred to the pickup and delivery problems (PDP). In a PDP, it is necessary
to meet the needs of two special kinds of customers: demand customers and supply customers. For the demand customer, they need a shipment from a depot. The objective of the problem is to find a minimum length tour for a capacitated vehicle and each supplier or retailer can only be visited only once. Also according to Barbarosogln and Ozgur3 (1999), optimal transportation planning can be replaced by multiple sub optimizations in supply chain management. Thus distribution network with only a cross dock is considered. Asefeh HasaniGoodarzi, Reza TavakkoliMoghaddam5 (2012) first considered split delivery by allowing vehicle to visit a node more than once.

PROPOSED ALGORITHMS In this paper two algorithms are proposed :
Algorithm A First finding Hamiltonian circuit for the given graph using Nearest Neighbor Strategy and then applying capacity constraint to find capacitated vehicle routes allowing split delivery.
Algorithm B Finding a vehicle route using Nearest Neighbor Strategy and considering capacity constraint with split delivery. Then repeating the procedure for the next vehicle on the reduced graph where fully served nodes are excluded while partly served nodes are there with their remaining demand.
Both the algorithms are applied on a data set, generated for a problem (described in section III) in which random values within specified range are generated and assigned to cost matrix, to analyze and compare the results and to establish better performing algorithm.
Section III includes the problem description with proposed Nearest Neighbor algorithms. In Section IV, solution is illustrated with the help of a numerical problem. Results are tabulated and analyzed in Section V. The last section concludes the study.

PROBLEM DESCRIPTION
We consider the Split Delivery Vehicle Routing Problem (SDVRP) where a fleet of homogeneous vehicles has to serve a set of customers. Each customer can be visited more than
once contrary to what is usually assumed in the classical vehicle routing problem (VRP). No constraint on the number of available vehicles is considered. There is a single depot for the vehicles and each vehicle has to start and end its tour at the cross depot. The objective is to find a set of vehicle routes that serves all the customers such that the sum of the quantities delivered in each tour does not exceed the capacity of the vehicle and the total distance travelled is minimized.

Algorithm A
To find the route, we applied Nearest Neighbor algorithm which is Greedy in nature , i.e. the node nearest will be the node served next. The route identified will be the path for various vehicles for serving the demands for various nodes. First vehicle with its full capacity starts from 0 serves the nodes in order of the route identified till its capacity exhausted, comes back to 0, then next vehicle start from 0 serving the balance demand of last served node and proceed on route till all the nodes are served.
Proposed algorithm A can be summarized as the following: Step 1: Initialization; Read the transportation matrix, demand vector, capacity of vehicles.
Step 2: Find the giant tour (Hamiltonian circuit) using nearest neighbor, starting from node 0 (CD) and covering all the nodes once and back to node 0.
Step 3: Find the cost of the giant path.
Step 4: Get the total demand and calculate number of vehicles required by using the capacity of vehicle i.e. no of vehicles = total demand/ capacity of a vehicle.
Step 5: While (total demand >0)
Step 5.1: Route new vehicle on giant path
serving the various nodes of the path till its capacity exhausted.
Step 5.2: Route back the vehicle to CD.
Step 5.3: Calculate the total cost incurred for
the vehicle i.e. cost incurred from start node (CD) to end (CD again).
Step 6: Output the findings.

Algorithm B
Capacity constraint and Nearest Neighbor algorithm is used simultaneously. In this Algorithm, First vehicle with its full capacity starts from 0 and follow the strategy: the node nearest will be the node served next till its capacity exhausted. Un served Nodes and partly served node(if any) with balance demand are under consideration for next vehicle. Procedure is repeated till all the nodes are served.
Proposed Algorithm B can be summarized as the following Step 1: Initialization; Read the transportation matrix, demand vector, capacity of vehicles.
Step 2: While (total demand >0)
Step 2.1: Route new vehicle using nearest neighbor strategy, starting from node 0
(CD) till its capacity exhausted.
Step 2.2: Route back the vehicle to CD.
Step 2.3: Calculate the total cost incurred for the vehicle
i.e. cost incurred from start node (CD) to end (CD) again
Step 3: Demand vector is updated with un served nodes and partly served node (if any) with balance demand fo next vehicles
Step 4: Output the findings.
This we elaborate in next section by taking a numerical example.
.


NUMERICAL EXAMPLE
In this section we treat some numerical examples and check the performance of the vehicle routing. We need to find the optimal solution for the given numerical examples with the help of algorithm. There are two problems having (n)10 and
30 nodes so that we can understand our vehicle routing problem better. Each problem is divided in to 3 sections (a,b,c) having 10 instances in each section there by 30 instances in total for problem 1. The number of vehicle required is found out according to demand. The weight W at each node is assumed. The vehicle capacity Q is 70 units which is homogenous for all vehicle. The cost to visit node i to j(cij) varies from 48 to 560. Pn & Dn is number of pickup and delivery node. Weight at each node varies from 5 to 50 for pickup and delivery process. Table 1 describes the problem data in tabular format.
TABLE I – NUMERICAL EXAMPLE DATA DESCRIPTION
Parameter
Problem1
Problem2
n
10
30
Q
70
70
tcij
a=(48,220)
a=(48,220)
b=(220, 390)
b=(220, 390)
c=(390, 560)
c=(390, 560)
pi, di
(5,50)
(5, 50)
Pn
4
7
Dn
6
23
In this paper, only delivery nodes and one cross dock is considered. Data sets of 30 instances for 7 (6 delivery nodes and one cross dock node) and 30 instances for 24(23 delivery nodes and one cross dock node) are generated using Random Number Generator. Sample data set for 7 nodes is as under:
0
170
89
113
72
112
144
170
0
79
122
128
197
116
89
79
0
212
205
53
100
113
122
212
0
127
184
124
TABLE II – COST MATRIX
72
128
205
127
0
51
140
112
197
53
184
51
0
60
144
116
100
124
140
60
0
The Demand Vector : 45 30 20 25 15 40. The total demand at all nodes is 175 :

RESULTS

Sample Output Algorithm A
Minimum cost:608
Path :> 0> 4> 5> 2> 1>
6> 3> 0
The Demand Vector : 45 30 20 25 15 40 The total demand at all nodes is 175 :
No of Trucks = 3 sufficient no of trucks:
tno 1 route 0 – 4 5 2 0
tno 2 route 0 – 1 6 0
tno 3 route 0 – 6 3 0
cost = 1076

Sample Output Algorithm B
Path : 1 > [0, 4, 5, 2, 0] Cost : > 265
Path : 2 > [0, 3, 1, 6, 0] Cost : > 495
Path : 3 > [0, 6, 0] Cost : > 288
Total Cost : > 1048
TABLE III – Comparison of Results for Data sets of 7 nodes with tcij a(48,220)
TABLE IV – Comparison of Results for Data sets of 7 nodes with tcij b(220,390)
Input Data File
Total cost
Algo. A
Total cost
Algo. B
No. of
vehicles
ds7s0
3096
3096
3
ds7s1
3306
3306
3
ds7s2
2911
2911
3
ds7s3
2776
2776
3
ds7s4
3230
3187
3
ds7s5
3205
3205
3
ds7s6
2793
2957
3
ds7s7
3285
3125
3
ds7s8
3283
3243
3
ds7s9
3012
2964
3
Average
3089.7
3077
TABLE V – Comparison of Results for Data sets of 7 nodes with tcij c(390, 560)
Input Data File
Total cost
Algo. A
Total cost
Algo. B
No. of
vehicles
ds7s0
3096
3096
3
ds7s1
3306
3306
3
ds7s2
2911
2911
3
ds7s3
2776
2776
3
ds7s4
3230
3187
3
ds7s5
3205
3205
3
ds7s6
2793
2957
3
ds7s7
3285
3125
3
ds7s8
3283
3243
3
ds7s9
3012
2964
3
Average
3089.7
3077
TABLE VI – Comparison of Results for Data sets of 24 nodes with tcij a(48,220)
Input Data
File
Total cost
Algo. A
Total cost
Algo. B
No. of
vehicles
ds24f0
3218
2959
8
ds24f1
3334
3304
8
ds24f2
3580
3354
8
ds24f3
3691
3248
8
ds24f4
3772
3637
8
ds24f5
4258
3999
8
ds24f6
3652
3537
8
ds24f7
4350
3764
8
ds24f8
3502
3699
8
ds24f9
3323
3354
8
Average
3668
3485.5
Input Data
File
Total cost
Algo. A
Total cost
Algo. B
No. of
vehicles
ds7f0
1076
1048
3
ds7f1
1215
1215
3
ds7f2
1317
1170
3
ds7f3
1440
1304
3
ds7f4 1413
1391
3
ds7f5
1035
1048
3
ds7f6
1438
1438
3
ds7f7
1196
1196
3
ds7f8
1142
1243
3
ds7f9
1150
1217
3
Average
1242.2
1227
TABLE VII – Comparison of Results for Data sets of 24 nodes with tcij b(220, 390)
Input Data File
Total cost Algo. A
Total cost Algo. B
No. of vehicles
ds24s0
9980
9941
8
ds24s1
9572
9579
8
ds24s2
10010
9744
8
ds24s3
10108
9966
8
ds24s4
10017
9678
8
ds24s5
10121
9733
8
ds24s6
10176
9952
8
ds24s7
9507
9504
8
ds24s8
9681
9498
8
ds24s9
10072
9449
8
Average
9924.4
9704.4
TABLE VIII – Comparison of Results for Data sets of 24 nodes with tcij c( 390, 560)
Input
Data File
Total cost
Algo. A
Total cost
Algo. B
No. of
vehicles
ds24t0
16686
16019
8
ds24t1
16556
16394
8
ds24t2
17270
17073
8
ds24t3
16794
16615
8
ds24t4
16960
16566
8
ds24t5
16294
15869
8
ds24t6
16581
16264
8
ds24t7
16225
16024
8
ds24t8
16692
16519
8
ds24t9
16475
16018
8
Average
16653.3
166336.1


CONCLUSION
Comparing the results of two algorithms clearly shows that performance of Algorithm B is better. For considering the effect of Split and non split and variation in demand in future the same algorithm and data set will be used.

REFERENCES

Apte U.M. , Vishwanathan S. (2000), Effective Cross Docking For Improving Distribution Efficiencies, International Journal of Logistic Research and Applications, 3, 291302.

Mosleiov G, (1998), Vehicle Routing with Pickup and Delivery Tour Partitioning Heuristics, Computer and Industrial Engineering, 34,669684.

Barbarosoglu G., Ozgur D(1999) , A Tabu Search Algorithm for Vehicle Routing Problem, Computer and Operation Research, 26, 255270.

NPTEL Course on Advance Operation Research (nptel,iitm.ac.in).

Asefeh HasaniGoodarzi, Reza TavakkoliMoghaddam (2012)Capacitated Vehicle Routing Problem for MultiProduct Cross Docking with Split Deliveries and Pickups, Social and Behavioral Sciences, 62, 13601365.

Lee Y.H. , Jung W J. Lee K M, (2006) Vehicle Routing Scheduling for Cross Docking In Supply Chain, Computers and Industrial Engineering 51, 247256.

A.B.Arabani, M.Zandieh,S.M.T.FGhom (2011) Multi objective algorithm for cross docking scheduling problem Applied Soft Computing, Vol 11, pp. 49544970

C.J.Liao, Y.Lian,S.C.Shin (2010) Vehicle routing with cross docking in the supply chain Computer and Industrial Engineering, Vol 37, pp. 68686873

C.S.Sung, S.H.Sung (2003) Integrated service network design for a cross docking supply chain managment Journel of Operation Research Society, Vol 54, pp. 12831295

F.A.Santos, G.R.Mateus (2011) A algorithm for a vehicle routing problem with cross docking Electronics Notes in Discrete Mathematics, Vol 37, pp. 249254

M.Gumus , J.H.Bookbinder (2004) Cross docking and its implication in location distribution system Journel of Business LogisticcsVol 25, pp 2