Capacitated Vehicle Routing Using Nearest Neighbor Algorithm in Supply Chain

Capacitated Vehicle Routing Using Nearest Neighbor Algorithm in Supply Chain

Sanjay Kulkarni, Dr. Nagendra Sohani

(Dept of Mechanical Engineering) IET-DAVV

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

1. 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 NP-Hard 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 Hasani-Goodarzi, Reza Tavakkoli-Moghaddam5 (2012) first considered split delivery by allowing vehicle to visit a node more than once.

2. 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.

3. 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.

   1. 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.

   2. 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.

   .

4. 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 pick-up and delivery node. Weight at each node varies from 5 to 50 for pick-up and delivery process. Table 1 describes the problem data in tabular format.

   TABLE I – NUMERICAL EXAMPLE DATA DESCRIPTION

   Parameter	Problem-1	Problem-2
   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 :

5. RESULTS

   1. 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

   2. 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

6. 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.

7. REFERENCES

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

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

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

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

5. Asefeh Hasani-Goodarzi, Reza Tavakkoli-Moghaddam (2012)Capacitated Vehicle Routing Problem for Multi-Product Cross Docking with Split Deliveries and Pickups, Social and Behavioral Sciences, 62, 1360-1365.

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

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

8. 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. 6868-6873

9. 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. 1283-1295

10. 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. 249-254

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