Title


Science and Technology Indonesia
e-ISSN:2580-4391 p-ISSN:2580-4405
Vol. 4, No. 4, October 2019

Research Paper

Branch and Cut Method for Solving Capacitated Vehicle Routing Problem
(CVRP) Model of LPG Gas Distribution Routes
Yuliza, E1*, Puspita, F.M1

1Mathematics Department, Faculty of Mathematics and Natural Science, University of Sriwijaya, Indralaya, South Sumatera, Indonesia
*Corresponding author: evibc3@yahoo.com

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.2019.4.4.105-108

1. INTRODUCTION

The Vehicle Routing Problem (VRP) and its variants hae grown
popular. The capacitated vehicle routing problem (CVRP) deals
with the distribution of a single commodity from a centralized
depot to a number of speci�ed customer locations with known
demands (Achuthan et al., 2003; Baldacci et al., 2004; Ralphs et al.,
2003). Vehicle Routing Problem (CVRP) is a VRP subcase, where
vehicles have limited capacity (Beresneva and Avdoshin, 2018).
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
�nding 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 pro-
cess 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 �eet
of trucks can serve oil demand from a number of gas stations
from the depot and minimize mileage. The purpose of this op-
timization is to �nd a set of routes that include n customers
with a minimum overall distance (Jepsen, 2011). The problem
under study is how to serve a set of customers scattered around
a central depot, using a �eet of trucks with various capacities
(Braekers et al., 2016). 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 �nd 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 (Ate� et al., 2018). 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 cus-
tomer 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 (Borčinova, 2017;
Alipour, 2012). One of the main di�erences lies in eliminating
sub-tours, namely cycles that do not go through depots. Cacceta
et al. investigated that reducing the Clarke and Wright algo-
rithm with a hybrid approach to CVRP completion (Caccetta
et al., 2012). Achuthan et al. (2003) has developed an exact branch
and cut algorithm. Letchford et al. (2007) presents the branch
and cut algorithm for the open routing problem, the vehicles are
not required to return to the depot after completing service. In
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 (cuts) at each node within a Branch and Bound
procedure (Yang et al., 2000). PT. Lebong Terang is expected to be

https://doi.org/10.26554/sti.2019.4.4.105-108


Yuliza et. al. Science and Technology Indonesia, 4 (2019) 105-108

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.

2. 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 veri�ed gas bases.

Table 1. Parameters

Parameter Description
d1 demand for gas station 1
d2 demand for gas station 2
d3 demand for gas station 3
d4 demand for gas station 4
d5 demand for gas station 5
d6 demand for gas station 6
d7 demand for gas station 7
d8 demand for gas station 8
d9 demand for gas station 9
d10 demand for gas station 10
d11 demand for gas station 11
d12 demand for gas station 12
d13 demand for gas station 13
d14 demand for gas station 14
d15 demand for gas station 15
d16 demand for gas station 16
d17 demand for gas station 17
d18 demand for gas station 18
d19 demand for gas station 19
d20 demand for gas station 20
d21 demand for gas station 21
d22 demand for gas station 22
d23 demand for gas station 23
d24 demand for gas station 24
Q Vehicle capacity

2.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., 2019).

2.2 Methods
Following are the research steps:

1. LPG gas demand data and distance from the agent to each
gas base.

2. Determine the distance matrix.
3. Formulate the CVRP model.
4. Solve the CVRP model using the branch and cut method.

The calculation process uses the help of LINGO 13.0 software.

3. RESULTS AND DISCUSSION

3.1 Mixed Linear Programming Formulation of CVRP
Given the de�nition of variables and parameters. For each (i, j)
� V, i ≠ j and for each vehicle r de�ned variable :

x
ij

=
{

1; if tℎereisatripfromtℎegasbasetoitotℎegasbasetoj

0; otℎerwisw

}

From Table 1 de�ned 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={0,1,2,3,. . . ,24}. The set P is in
the �rst gas base, the second gas base, ..., the 24th gas base,
P={1,2,3,. . . ,24}. The set of vehicles is a collection of vehicles that
are homogeneous with capacity. Every base i for every i � 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,j�V,i≠j, we calculate the
savings s_ij for joining the cycles 0→i→0 and 0→j→0 using
arc (i,j); s

ij
=c

i0
+c

0j
-c
ij

(Borčinova, 2017).

Table 2. Solution of CVRP model with branch and cut method

The MILP Model Distribution Distance Traveled
Route from CVRP (km)

0-5-11 0.4
0-3-13 7.9
0-17-15 5,5
0-2-20 0.7
0-8-10 2.4
0-14-18 2.85
0-19-21 2.29
0-22-23 0.75
0-4-16 10.8
0-7-9 -1.2
0-12-1 10
0-6-24 -1.5
total 40,8

In this research, we present mixed integer linear program-
ming (MILP) model of CVRP. The objective function of the ILP
model of CVRP minimizes the distance of travel (Yuliza et al.,
2019). 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.4x511+0.4x011 subject to
x05+x011=1
x05+x115=1
x011+x511=1
x511<=1
x115<=1
y5+1050x511+4000x511-y11<=4000

© 2019 The Authors. Page 106 of 108



Yuliza et. al. Science and Technology Indonesia, 4 (2019) 105-108

Table 3. Compared the ILP model from CVRP and the MILP model from CVRP

The ILP Model Distance Traveled The MILP Model Distribution Distance Traveled
Distribution Route from CVRP (km) Route from CVRP (km)

0-5-11-0 4.8 0-5-11 0.4
0-3-13-0 21.9 0-3-13 7.9
0-17-15-0 31.5 0-17-15 5,5
0-2-20-0 9.1 0-2-20 0.7
0-8-10-0 7.2 0-8-10 2.4
0-14-18-0 7.25 0-14-18 2.85
0-19-21-0 4.19 0-19-21 2.29
0-22-23-0 1.65 0-22-23 0.75
0-4-16-0 17,8 0-4-16 10.8
0-7-9-0 5.8 0-7-9 -1.2
0-12-1-0 23.2 0-12-1 10
0-24-0 6.6 0-6-24 -1.5
0-6-0 5

Total Distance 145.99 40.8

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.4x511+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
0→11→5→0 represents the route 0→11→5 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
kg. MILP model solutions from CVRP with the branch and cut
method are shown in the Table 2.

3.2 Computational Results
Both of the models, the ILP model distribution route from CVRP
and the MILP model distribution route from CVRP, were solved

using LINGO 13.0. 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
0.4 km. The feasible route, 0→5→11→0 is replaced by a path
from node 0 to node 11, 0→5→11. Ratio of this travel distace
from the ILP model from the CVRP and the MILP model from
the CVRP is 12 km.

4. 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
7.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
of 2.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.5
km. Percentage comparison of �ow formulation from CVRP and
modi�ed assignment formulation from CVRP is 3.578 or 357.8 %.

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

© 2019 The Authors. Page 107 of 108



Yuliza et. al. Science and Technology Indonesia, 4 (2019) 105-108

REFERENCES

Achuthan, N., L. Caccetta, and S. Hill (2003). An Improved
Branch-and-Cut Algorithm for the Capacitated Vehicle Rout-
ing Problem. Transportation Science, 37; 153–169

Alipour, M. M. (2012). A learning automata based algorithm
for solving capacitated vehicle routing problem. International
Journal of Computer Science Issues (IJCSI), 9(2); 138

Ate�, R., M. Salari, L. C. Coelho, and J. Renaud (2018). The open
vehicle routing problem with decoupling points. European
Journal of Operational Research, 265(1); 316–327

Baldacci, R., E. Hadjiconstantinou, and A. Mingozzi (2004). An
Exact Algorithm for the Capacitated Vehicle Routing Prob-
lem Based on a Two-Commodity Network Flow Formulation.
Operations Research, 52(5); 723–738

Beresneva, E. and S. Avdoshin (2018). Analysis of Mathematical
Formulations of Capacitated Vehicle Routing Problem and
Methods for their Solution. Proceedings of the Institute for
System Programming of the RAS, 30; 233–250

Borčinova, Z. (2017). Two models of the capacitated vehicle
routing problem. Croatian Operational Research Review, 8;
463–469

Braekers, K., K. Ramaekers, and I. V. Nieuwenhuyse (2016). The

vehicle routing problem: State of the art classi�cation and
review. Computers & Industrial Engineering, 99; 300–313

Caccetta, L., M. Alameen, and M. Abdul-niby (2012). An im-
proved Clarke and Wright savings algorithm for the capaci-
tated vehicle routing problem. ScienceAsia, 38; 307

Jepsen, M. K. (2011). Branch-and-cut and Branch-and-Cut-and-
Price Algorithms for Solving Vehicle Routing Problems. Kgs.
Lyngby. Denmark: Technical University of Denmark

Letchford, A., J. Lysgaard, and R. Eglese (2007). A Branch-and-
Cut Algorithm for the Capacitated Open Vehicle Routing Prob-
lem. Journal of the Operational Research Society, 58; 1642–1651

Ralphs, T., L. Kopman, W. Pulleyblank, and L. Trotter (2003).
On the capacitated vehicle routing problem. Mathematical
Programming, 94(2-3); 343–359

Yang, X., A. I. Mees, M. Fisher, and L. Jennings, editors (2000).
Progress in Optimization. Springer US

Yuliza, E., F. Puspita, S. Yahdin, and R. Emiliya (2019). Solution
of capacitated vehicle routing problem using Branch and Cut
method and Clarke and Wright Algorithm for determining
LPG gas distribution routes. Conference on Semirata & the 2nd
ICST Unib

© 2019 The Authors. Page 108 of 108


	INTRODUCTION
	EXPERIMENTAL SECTION
	Materials
	Methods

	RESULTS AND DISCUSSION
	Mixed Linear Programming Formulation of CVRP
	Computational Results

	CONCLUSIONS
	ACKNOWLEDGEMENT