Science and Technology Indonesia e-ISSN:2580-4391 p-ISSN:2580-4405 Vol.
No.
October 2019 Research Paper Branch and Cut Method for Solving Capacitated Vehicle Routing Problem (CVRP) Model of LPG Gas Distribution Routes Yuliza.
E1 *.
Puspita.
1 Mathematics Department.
Faculty of Mathematics and Natural Science.
University of Sriwijaya.
Indralaya.
South Sumatera.
Indonesia *Corresponding author: evibc3@yahoo.
Abstract Capacitated Vehicle Routing Problem (CVRP) is a problem that discusses how to choose several routes that must be passed by a number of transport vehicles in the process of distributing goods that combine customer demand with regard to transport capacity.
CVRP designs an optimal delivery route where each vehicle only takes one route, each vehicle has the same characteristics, each customer has a request and there is only one depot.
In this paper, two CVRP models were formulated.
Formulation of the first CVRP model without regard to vehicle loads and vehicles returned to the depot.
The second CVRP model formulation takes into account the vehicle load and the vehicle does not return to the depot.
Determination of LPG gas distribution routes is completed using the Branch and Cut method.
Keywords Capacitated Vehicle Routing Problem.
Branch and Cut Received: 23 September 2019.
Accepted: 19 October 2019 https://doi.
org/10.
26554/sti.
INTRODUCTION
The Vehicle Routing Problem (VRP) and its variants hae grown The capacitated vehicle routing problem (CVRP) deals with the distribution of a single commodity from a centralized depot to a number of specified customer locations with known demands (Achuthan et al.
, 2003.
Baldacci et al.
, 2004.
Ralphs et al.
Vehicle Routing Problem (CVRP) is a VRP subcase, where vehicles have limited capacity (Beresneva and Avdoshin, 2.
Optimal route search in daily life is needed to minimize the time and costs incurred, especially for large companies that distribute their products every day by using a vehicle.
The problem of finding the optimal vehicle route or the Vehicle Routing Problem (VRP) is a problem that discusses how to choose several routes that must be passed by a number of transport vehicles in the process of distributing goods that combine customer demand with regard to transport capacity.
VRP was introduced by Dantzig and Ramser in 1959 on the problem of modeling truck deliveries.
The problem under investigation is, how a homogeneous fleet of trucks can serve oil demand from a number of gas stations from the depot and minimize mileage.
The purpose of this optimization is to find a set of routes that include n customers with a minimum overall distance (Jepsen, 2.
The problem under study is how to serve a set of customers scattered around a central depot, using a fleet of trucks with various capacities (Braekers et al.
, 2.
VRP has experienced developments that are tailored to real- world problems.
A company faces a vehicle route problem to determine the optimal route.
Classic VRP aims to find a set of vehicle routes that start and end at a depot for vehicles with the same capacity so that each customer is visited exactly once (Atefi et al.
, 2.
Classic VRP is also known as Capacitated Vehicle Routing Problem (CVRP).
CVRP designs an optimal delivery route where each vehicle only takes one route, each vehicle has the same characteristics, each customer has a demand and there is only one central depot to meet customer demand with the number of vehicle loads that does not exceed capacity.
There are various Integer Linear Programming (ILP) models from CVRP, as already examined (Borsinova, 2017.
Alipour, 2.
One of the main differences lies in eliminating sub-tours, namely cycles that do not go through depots.
Cacceta et al.
investigated that reducing the Clarke and Wright algorithm with a hybrid approach to CVRP completion (Caccetta et al.
, 2.
Achuthan et al.
has developed an exact branch and cut algorithm.
Letchford et al.
presents the branch and cut algorithm for the open routing problem, the vehicles are not required to return to the depot after completing service.
this study, the ILP model formulated from CVRP was solved by the Branch and Cut method.
Distribution of LPG gas products to several customers in the city of Palembang.
Basically, this method attempts to strengthen the lower bounds by the addition of constraints .
at each node within a Branch and Bound procedure (Yang et al.
, 2.
PT.
Lebong Terang is expected to be Science and Technology Indonesia, 4 .
105-108 Yuliza et.
able to create reliable shipping performance in the distribution of gas products.
The conversion of kerosene to gas makes LPG gas demand continues to increase.
During this time the distribution process that has been good, but not yet maximum which resulted in the long enough shipping distance and resulting in greater distribution costs, for this reason the company is expected to have a plan in determining the distribution channel so that the product distribution process can run optimally at a low cost .
This research will formulate a CVRP model to determine the LPG gas distribution route using the branch and cut method.
EXPERIMENTAL SECTION
The research is a case study.
LPG gas distribution routes at PT Terang Lebong in Palembang.
The data is the result of a survey of 3 LPG gas base data collected by the surveyor, in the form of a list of verified gas bases.
Table 1.
Parameters Parameter Description demand for gas station 1 demand for gas station 2 demand for gas station 3 demand for gas station 4 demand for gas station 5 demand for gas station 6 demand for gas station 7 demand for gas station 8 demand for gas station 9 demand for gas station 10 demand for gas station 11 demand for gas station 12 demand for gas station 13 demand for gas station 14 demand for gas station 15 demand for gas station 16 demand for gas station 17 demand for gas station 18 demand for gas station 19 demand for gas station 20 demand for gas station 21 demand for gas station 22 demand for gas station 23 demand for gas station 24 Vehicle capacity 1 Materials The data used in this study is the distribution of 3 kg LPG gas.
The gas is distributed to 24 gas bases (Yuliza et al.
, 2.
2 Methods Following are the research steps:
LPG gas demand data and distance from the agent to each gas base.
A 2019 The Authors.
Determine the distance matrix.
Formulate the CVRP model.
Solve the CVRP model using the branch and cut method.
The calculation process uses the help of LINGO 13.
0 software.
RESULTS AND DISCUSSION
1 Mixed Linear Programming Formulation of CVRP Given the definition of variables and parameters.
For each .
, .
yun V, i O j.
nd for each vehicle r defined variable :
ycnyce ycEayceycyceycnycycaycycycnycyyce ycycuycoycEayceyciycaycycaycaycyceycycuycnycycuycEayceyciycaycycaycaycyceycycuyc ycuycEayceyc ycycnycyc From Table 1 defined parametres.
VRP problems in LPG gas distribution can be determined as a graph G=(V,E).
The set V consists of a combined set of P gas bases and warehouses.
V=.
,1,2,3,.
The set P is in the first gas base, the second gas base, .
, the 24th gas base.
P=.
,2,3,.
The set of vehicles is a collection of vehicles that are homogeneous with capacity.
Every base i for every i yun V has a demand in so that the length of the route is limited by the capacity of the vehicle (Q).
For all pairs i,jyunV,iOj, we calculate the savings s_ij for joining the cycles 0IeiIe0 and 0IejIe0 using arc .
sij =ci0 c0j -cij (Borsinova, 2.
Table 2.
Solution of CVRP model with branch and cut method The MILP Model Distribution Route from CVRP Distance Traveled .
0-5-11
0-3-13
0-17-15
0-2-20
0-8-10
0-14-18
0-19-21
0-22-23
0-4-16
0-7-9
0-12-1
0-6-24
In this research, we present mixed integer linear programming (MILP) model of CVRP.
The objective function of the ILP model of CVRP minimizes the distance of travel (Yuliza et al.
Now, instead of minimizing the distance of travel, will be maximize the total saving of the distance of travel.
The CVRP model for LPG gas distribution is can be stated as:
Max 0.
4x011 subject to x05 x011 =1 x05 x115 =1 x011 x511 =1 x511 <=1 x115 <=1 y5 1050x511 4000x511 -y11 <=4000 Page 106 of 108 Science and Technology Indonesia, 4 .
105-108 Yuliza et.
Table 3.
Compared the ILP model from CVRP and the MILP model from CVRP The ILP Model Distribution Route from CVRP Distance Traveled .
The MILP Model Distribution Route from CVRP Distance Traveled .
0-5-11-0
0-3-13-0
0-17-15-0
0-2-20-0
0-8-10-0
0-14-18-0
0-19-21-0
0-22-23-0
0-4-16-0
0-7-9-0
0-12-1-0
0-24-0
0-6-0
Total Distance 0-5-11
0-3-13
0-17-15
0-2-20
0-8-10
0-14-18
0-19-21
0-22-23
0-4-16
0-7-9
0-12-1
0-6-24
y11 1200x115 4000x115 -y5 <=4000 y5 >=1200 y5 <=4000 y11 =1050 y11 <=4000 the function value of the CVRP model is 0.
4 and the value x115 = 0.
792, x011 = 0.
792, x511 = 0.
207, x05 = 0.
207, y11 = 1050 and y5 = 4000.
The decision variables are non-integer values so branching is done.
After branching, the CVRP model is obtained Max 0.
4x115 subject to x05 x011 =1 x05 x115 =1 x011 x511 =1 x511 <=1 x511 <=1 y5 1050x511 4000x511 -y11 <=4000 y11 1200x511 4000x115 -y5 <=4000 y5 >=1200 y5 <=4000 y11 >=1050 y11 <=4000 x511 <=0 The function value of the CVRP model is 0.
4 and the value x115 = x011 = 1, x511 = x05 = 0, y11 = 1050 dan y5 = 4000.
Path 0Ie11Ie5Ie0 represents the route 0Ie11Ie5 where gas base 11 has demand 1050 kg, gas base 5 has demand 1200 kg, the value of the vehicle load is 1050 kg the value of the vehicle load is 4000 MILP model solutions from CVRP with the branch and cut method are shown in the Table 2.
2 Computational Results Both of the models, the ILP model distribution route from CVRP and the MILP model distribution route from CVRP, were solved A 2019 The Authors.
using LINGO 13.
From Table 3 compared the ILP model from CVRP and the MILP model from CVRP to get the optimal solution.
ILP model from CVRP and MILP model from CVRP were solved by branch and cut method.
From the Table 3.
, the optimal route of the ILP model from CVRP is 0-5-11-0 with travel distance 4.
8 km.
the optimal route of the MILP model from CVRP is 0-5-11 with travel distance 4 km.
The feasible route, 0Ie5Ie11Ie0 is replaced by a path from node 0 to node 11, 0Ie5Ie11.
Ratio of this travel distace from the ILP model from the CVRP and the MILP model from the CVRP is 12 km.
CONCLUSIONS
From the result and discussion, it can be concluded the optimal solution of the CVRP model using branch and cut method is the route with optimum distance obtained as follows: 0-5-11 with an optimal distance of 12 km, 0-3-13 with an optimal distance of 9 km, 0-7-15 with an optimal distance of 5.
5 km, 0-2-20 with an optimal distance of 0.
7 km, 0-8-10 with an optimal distance 4 km, 0-14-18 with an optimal distance of 2.
85 km, 0-19-21 with an optimal distance of 2.
29 km, 0-22-23 with an optimal distance of 0.
75 km, 0-4-16 with an optimal distance of 10.
8 km, 0-7-9 with an optimal distance of -1.
2 km, 0-12-1 with an optimal distance of 10 km and 0-6-24 with an optimal distance of -1.
Percentage comparison of flow formulation from CVRP and modified assignment formulation from CVRP is 3.
578 or 357.
8 %.
ACKNOWLEDGEMENT
This research is supported by Faculty of Mathematics and Natural Sciences.
University of Sriwijaya through Sains and Technology (SATEKS) Research Grant Scheme, year 2019 Page 107 of 108 Yuliza et.
REFERENCES