See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/312322617

An improved savings method for vehicle routing problem

Conference Paper · July 2016

DOI: 10.1109/CCSSE.2016.7784340

CITATIONS READS
2 145

4 authors, including:

Xing Wang
Jilin University
6 PUBLICATIONS   13 CITATIONS   

SEE PROFILE

All content following this page was uploaded by Xing Wang on 27 January 2022.

The user has requested enhancement of the downloaded file.

 An Improved Savings Method for Vehicle Routing Problem

WANG Xing, ZHAO Shu-zhi WANG Xing, CHU Hao

School of Transportation, School of Management,
Jilin University Jilin University
Changchun 130025, China Changchun 130025, China
wang_xing@jlu.edu.cn; zhaosz@jlu.edu.cn wang_xing@jlu.edu.cn; chu176@sohu.com

LI Yan
Department of Finance and Economics,
Hebei Construction Material Vocational and Technology College
Qinhuangdao 060004, China
68113033@qq.com

Abstract—The Clarke and Wright’s savings method is a concerned, such as VRP with time windows, VRP with
classical and widely used heuristics for the Vehicle routing pickups, VRP with backhauls and mixed problems. There are
problem (VRP). It is an effective method which reaches a also multi-object VRPs, such as minimizing both the
reasonably good solution for small and medium size problems. distance of route and number of vehicle.
For large-scale VRP, more complex heuristics are developed The VRP has been proved to be a Non-deterministic
by different scholars. In this paper, an improved savings Polynomial hard (NP-hard) problem [2]. Algorithms for the
method has been proposed based on modification the rules of VRP can be classified into two categories: exact algorithm
forming new links during iteration. The improved savings and heuristics. Exact algorithm, such as enumeration,
method offers a better solution than the classical savings
branch-and-bound schemes, dynamic programming, offers
method in the given example. Numerical experiments are
conducted to test the effectiveness of the algorithm. The result
an optimal solution. However, they are suitable only for VRP
shows that the improved savings method offers a better with few customers because it becomes highly sophisticated
solution than classical savings method in about 75 percent with the increasing number of customers. Exact polynomial
situation in every 1000 numerical experiments. algorithm has not been found for the VRP with large number
of customers. Thus, the developments of VRP algorithm
Keywords-system engineering; vehicle routing problem; mainly focus on the development and improvement of
Clarke and Wright; improved savings method; distribution. heuristics. The savings algorithm, proposed by G. Clarke and
J.V. Wright in 1964 [3], is the most well-known and widely
used heuristics for the VRP. It describes an easily
I. INTRODUCTION understandable and effective method reaching a reasonably
good solution. It can also be extended to different constraints.
There are many occasions where efficient collection and The algorithm of VPR aims at reaching a best route for
distribution are desired in our society. For example, a KFC vehicles based on road network. The road network is
distribution center must send frozen chicken and ingredients described by a graph where its vertices represent the depot
to its chain stores based on their demand and location. A and customers. The demand of each customer and the limit
courier must send mails and packages to recipients. In these of truck are given. During the past 50 years, several
situations, an optimal collection or distribution route is enhancements to this algorithm have been proposed [4]. In the
important to improve operational efficiency and reduce cost. early days, many achievements are made to reduce the
All these problems are application of the vehicle routing computational work of classical method. But this becomes
problem, which is one of the most typical problems in less meaningful with the emergence and fast development of
combinational optimization and operations research. computer and programming [5]. Other enhancements have
The Vehicle Routing Problem was first introduced by mainly addressed three directions: increasing or decreasing
G.B. Dantzig and J.H. Ramser in 1959[1]. The basic VRP constrains [6-8]; extending to multi-objective problem [9-10];
describes this kind of problem: a set of customers with combining with another heuristics to achieving a better
known location and demand are to be supplied from a depot solution [11-12]. The purpose of this article is to propose an
by vehicles of limited capacity. The solution of vehicle improved route combination method based on classical
routes, each starts from and ends with the depot, such that savings method. In this paper we consider the capacitated
each customer is visited exactly once. It means the demand vehicle routing problem. It means that only one depot exists
of each customer should be satisfied in a single and all vehicles have the same capacity.
delivery.With the development of VRP, more constraints are
 The article is organized as the following outline. First, TABLE I. COORDINATES AND DEMAND OF D0 AND EACH CUSTOMER
the principle of Clarke and Wright’s savings method is
D0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10
reviewed. Then an improved savings method is proposed
with steps and equations in a general form. A VRP with one Xi 150 151 159 130 128 163 146 161 142 163 148
depot and ten customers are calculated by both classical and Yi 250 264 261 254 252 247 246 242 239 236 232
improved savings method. Numerical experiments are Qi 0 1.1 0.7 0.8 0.4 2.1 0.4 0.8 0.1 0.5 0.6
conducted in Matlab software to test the effectiveness of the
improved savings method. Comparison is made between According to Clark and Wright’s savings method, we
solutions by two methods. Finally a summary and possibility calculate the distances and savings between each vertex of
of future related work are discussed. the network. All data are accurate to two places of decimals.
All the savings are ranked in descending order as shown in
II. THE SAVINGS METHOD Table Ⅲ. To illustrate, we only list the first twenty savings.
The assumption of the savings method is that the higher
A. Principle of the savings method the savings is, the better it is to link those two customers in a
The principle of this algorithm can be described as follow: route. New links can only be added to the start or end of an
If goods are delivered from one depot D0 to two existing route, with a constraint of the vehicle capacity. We
customers𝐶1 and𝐶2 . Distances between depot to customer 𝐶1 choose the largest saving 39.66 that satisfy capacity limit and
and 𝐶2 are 𝑙01 and 𝑙02 , and the distance between two link customer 𝐶4 and 𝐶3 at the first step. According to
customers is𝑙12 . The demand of two customers is given and sequential algorithm, consider the following savings which
no more than the limit of the vehicle. As illustrated in Fig. contain the customer 𝐶4 or 𝐶3 , the eighth saving 16.59
1(a), the total distance of separate distribution is L = connecting customer 𝐶8 and 𝐶4 comes to the queue. If add
2(𝑙01 + 𝑙02 ) while the total distance by combined customer 𝐶8 to the route, the demand is ∑ 𝑄𝑖 =𝑄4 + 𝑄3 +
distribution is𝐿′ = 𝑙01 + 𝑙02 + 𝑙12 , as demonstrated in Fig. 𝑄8 = 1.3 < 3.5. The route continues to add new customer
1(b). According to the property of triangle, it is easy to till it break the truck capacity limit. Check the savings matrix
till all customers are visited.
understand thatS = L − 𝐿′ = 𝑙01 + 𝑙02 − 𝑙12 ≥ 0, where S
is defined as “saving”. The saving means the distance that TABLE II. THE DISTANCE MATRIX
saved by combined distribution rather than separated
distribution for more than one customer. Then the savings D0 C1 C2 C3 C4 C5 C6 C7 C8 C9
are ranked and customers are added to routes according to C1 14.04
the rank until the capacity of vehicle is reached. A parallel
C2 14.21 8.54
and a sequential version of the algorithm are available.
The savings method aims at minimizing total distribution C3 20.40 23.26 29.83
distance under ideal condition, without considering time and C4 22.09 25.94 32.28 2.83
other practical constraints. Considering the algorithm itself,
C5 13.34 20.81 14.56 33.73 35.36
the main shortcoming is its solution has a gap to the best
solution and that we find this shortcoming can be improved C6 5.66 18.68 19.85 17.89 18.97 17.03
by modify its combine procedure during the calculation. C7 13.60 24.17 19.10 33.24 34.48 5.39 15.52
B. A numerical example C8 13.60 26.57 27.80 19.21 19.10 22.47 8.06 19.24
From a distribution center (D0) commodities should be C9 19.10 30.46 25.32 37.59 38.48 11.00 19.72 6.32 21.21
distributed to ten customers Ci , where i = 1,2, … ,10 . The C10 18.11 32.14 31.02 28.43 28.28 21.21 14.14 16.40 9.22 15.52
location of distribution center and all customers are given in
Table Ⅰ by their coordinates. The demand of each customer TABLE III. SAVING MATRIX IN ORDER (THE FIRST TWENTY SAVINGS)
isQ i . The capacity of each vehicle is 3.5 units.
No. Saving Ci No. Saving Ci
1 39.66 C4 C3 11 12.99 C5 C2
2 26.38 C9 C7 12 11.92 C 10 C4
C1 C2 C1 C2
3 22.49 C10 C8 13 11.49 C9 C8
4 21.69 C10 C9 14 11.20 C8 C6
5 21.56 C7 C5 15 11.17 C3 C1
6 21.45 C9 C5 16 10.24 C 10 C5
7 19.70 C2 C1 17 10.18 C4 C1
D0 D0 8 16.59 C8 C4 18 10.08 C 10 C3
(a)Separated distribution (b)Combined distribution 9 15.31 C 10 C7 19 9.63 C 10 C6
10 14.79 C8 C3 20 8.77 C6 C4
Figure 1. Principle of the savings method.
 TABLE IV. SOLUTION BY CLASSICAL SAVINGS METHOD the arc set. Vertex 𝐷0 stands for the depot whereas other
Route Load Total distance
vertices correspond to customers. m is the number of
customers.
D0 - C6 -C9 -C8 - C4 - C3 - C1 - D0 3.3 p and q stand for the vertex of customer, p, q ∈
D0 - C7 -C5 - D0 2.9 201.49 {0,1, ⋯ , 𝑚}. d is the distance between any two vertex of the
D0 - C10 - C2 - D0 1.3 graph. We consider the symmetric case in this article, where
𝑑𝑖𝑗= 𝑑𝑗𝑖 for all (i, j) ∈ A.
x𝑖 represents the X coordinate of vertex i , while y𝑖
represents the Y coordinate of vertex.
265 𝑠𝑝𝑞 is the saving of linking customer p and q.
C1 (151,264)
R is the set of route. Re is either end of route R.
260 C2
(159,261)
C3 C. Steps of improved savings method
255 (130,254)
In improved savings method, the first and second steps
250 C4 D0 (150,250) are the same with classical saving method. The difference is
(128,252)
C5 (163,247)
the rules of selecting which savings and adding which
245 C6 (146,246) customer to the routes. The steps of improved savings
method can be described as follow:
C7 (161,242)
240 1) step one: Calculate the distance between every two
C8 (142,239) customers and between each customer to the depot.
235 C9 (163,236)
dpq = √(xp − xq )2 + (yp − yq )2 (1)
C10 (148,232)
230
125 130 135 140 145 150 155 160 165
2) step two: Calculate all savings between every two
customers. Rank the savings and omit those below zero.
spq = dp0 + dq0 − dpq (2)
Figure 2. Distribution routes by classical savings method. 3) step three: Choose two customers with maximum
savings satisfied the truck load limit as the initial route.
We got the solution and the routes are demonstrated as
R1 = {p, q} (3)
Table Ⅵ and Fig. 2. There are three routes and the total
distance of vehicle is 201.49. 4) step four: In the remainder of savings, choose the
largest one that contains same customer of either the start or
III. IMPROVED SAVINGS METHOD end of previous route. Decide whether this savings is the
largest one for this customer. If not, turn to the second
A. Principle of improved savings method
largest savings. Add the customer to previous route if the
In classical savings method, some larger savings cannot sum of the demand does not exceed the truck load.
be added to the rout because of the constraint of vehicle {R i , p} spRe = max sp
capacity. So we have to choose a smaller savings and add a R i+1 = { (4)
customer. This means we add a customer to the route using a R i spRe ≠ max sp
smaller savings while abandon a larger savings of the same 5) step five: Repeat step four till no customer can be
customer. added to the route subjected to the limit of the truck load.
According to above principles, we proposed a new route 6) step six: Repeat steps three, four and step five till all
merging method based on making use of every larger savings. customers have been added to the routes.
The improved savings method is proposed based on two
basic principles. IV. APPLICATION OF IMPROVED SAVINGS METHOD
1) One of the constraints in classical saving algorithm is
A. Solution by improved savings method
described as “a customer cannot be inserted as an inside
vertex to a route”. In other words, we can only combine In the first iteration, customer 𝐶4 and 𝐶3 is added to the
customers to the start or end of a route. PENG [13] has proved route. Then the eighth saving 16.59 connecting customer
𝐶8 and 𝐶4 comes to the queue. According equation (4),
this.
customer 𝐶8 cannot be added to the route because this saving
2) In an optimized route, a vertex can only connect with is not the maximum saving for it. Check all remaining
two other vertex, one customer and the depot, or two savings that no customer satisfies the condition in this route.
customers. Then we come to start a new route from the top the
B. Assumption of symbols unselected savings queue. Customer 𝐶9 and 𝐶7 is selected as
the first two ends of a new route. Then the saving 21.56
In this article, we define the following symbols for connecting customer 𝐶7 and 𝐶5 satisfies the condition. No
improved saving algorithm. other customers can add to this route. So far, the routes and
Let G = (V, A) be a non-directed graph, where V = updated savings are illustrated as in Fig.3 and Table Ⅵ.
{0, ⋯ , 𝑛} is the vertex set and A = {(𝑖, 𝑗): 𝑖, 𝑗 ∈ 𝑉, 𝑖 ≠ 𝑗} is
 B. Discussion
265
C1 (151,264)
C2(159,261) The total distance of routes optimized by improved
260 savings method is 34.18 shorter than solution of original
savings algorithm. Better solution is achieved with less
C3 (130,254)
255 distance and avoiding crossover in the improved algorithm.
D0 (150,250) As the improved savings method belongs to heuristics, there
250 C4 (128,252)
C5(163,247) is no grantee that it will always get a better solution than the
245
C6 (146,246) classical savings method. To test the effectiveness of this
improvement of the algorithm, we have conducted numerical
C7
240 (161,242) experiment with 1000 problems. The coordinate values of
C8 (142,239) the customers are generated within a certain radius. It is
235 C9 (163,236) possible to change the number of customers and location of
C10 (148,232) the depot. By serval times of 1000 problems experiment,
230
125 130 135 140 145 150 155 160 165 about 75 percent of the solution given by the improved
savings method is better than by classical savings method.
Figure 3. First two routes by improved savings method. V. CONCLUSION

TABLE V. RENEWED SAVINGS IN ORDER The classical savings algorithm is widely used as an
important heuristics and a base of other algorithm. This work
No. Saving Ci No. Saving Ci mainly addressed to improve the quality of its solution. The
1 effectiveness of this improvement has been proven with
22.49 C10 C8 11 1.07 C8 C1
comparative computation. Further study of this improved
2 19.70 C2 C1 12 1.01 C6 C1 savings method can be addressed to consider diverse
3 11.20 C8 C6 13 0.02 C6 C2 constrains or multi-objectives.
4 9.63 C10 C6 14 0.01 C8 C2
REFERENCES
5 1.31 C 10 C1 15 0.01 C 10 C1 [1] G.B. Dantzig and J.H. Ramser. The truck dispatching problem.
Management Science, 1959(6) , pp.80–91.
TABLE VI. SOLUTION BY IMPROVED SAVINGS METHOD
[2] Garey M.R., Johnson D.S. Computers and Intractability: A Guide to
the Theory of NP-completeness. 1979.
Route Load Distance
[3] G. Clarke and J.V. Wright. Scheduling of vehicles from a central
D0 - C4 - C3 -D0 1.2 depot to a number of delivery points. Operations Research, 1964 (12) ,
D0 - C9 - C7 - C5 -D0 3.4 pp. 568–581
167.31 [4] Graham K Rand. The life and times of the savings method for vehicle
D0 - C10 - C8 - C6 - D0 1.1 routing problems, ORiON, 2009, 25(2), pp.125-145
D0 - C2 - C1 - D0 1.8 [5] Gilbert Laporte and Michel Gendreau. Classical and Modern
Heuristics for the Vehicle Routing Problem. 1999.3
265 [6] FAN En-hai. Another pattern of saving-algorithm for delivery
C1 (151,264) management. Journal of Taiyuan University of Technology,
C2(159,261)
260
vol.3,1999, pp. 217-219
[7] HUO Jia-zhen, ZHANG Lei. Savings based algorithm for truckload
255 C3 (130,254) vehicle routing problem with time window. Industrial Engineering
D0 (150,250)
and Management. 2006 (4) , pp. 39-42.49
250 C4 (128,252)
C5(163,247)
[8] LIN Xiao-yu, LI Jin-ming, JI Shou-wen. Improvement and
computation of Clarke-Wright algorithm for vehicle routing
C6 (146,246)
245 problem.Traffic and Computer, 2004(22) , pp. 72-75
C7
[9] WU Ke. Simulation for material delivery plan in multi-objective
240 (161,242) system. Systems Engineering-Theory &Practice, 1994(11), pp. 41-47
C8 (142,239)
[10] Mehrjerd, Yahia Zare. A multiple objective stochastic approach to
235 C9 (163,236) vehicle routing problem, International Journal of Advanced
C10 (148,232)
Manufacturing Technology, 2014, 74 pp. 1149-1158
230 [11] ZHANG Jian-tong, FENG Zi-yan. Improved CW saving method for
125 130 135 140 145 150 155 160 165
vehicle routing problem. Proceedings of the 10th China Annual
Conference on Uncertainty, 2012, pp. 75-83
Figure 4. Distribution routes by improved savings method. [12] S.Milan, S.Bogdana, V.Mirko. Enhanced savings calculation and its
applications for solving capacitated vehicle routing problem. Applied
Mathematics and Computation, 2013(219) , pp. 10302-10312
When all customers are added to the route, we got the
solution by improved savings method. The result is given in [13] PENG Xin, QI Ming-yao, MIAO Lixin. Review and analysis of
saving algorithm for vehicle routing problem. China Logistics
Table Ⅵ and the routes are illustrated in Fig.4.The total Research: State of the Art (2008-2009). China Logistics Publishing
distance is 167.31, which is 34.18 shorter than the solution House, 2008, pp. 399-408.
by classical savings method.
 AUTHORS’ BACKGROUND

Your Name Title* Research Field Personal website

WANG Xing Phd candidate transportation and logistics
ZHAO Shuzhi full professor traffic and transportation
CHU Hao associate professor logistics management
LI Yan lecture logistics and E-commerce
*This form helps us to understand your paper better, the form itself will not be published.

*Title can be chosen from: master student, Phd candidate, assistant professor, lecture, senior lecture, associate professor,
full professor

View publication stats