Open Access
ARTICLE
Research on Vehicle Routing Problem with Soft Time Windows Based on Hybrid Tabu Search and Scatter Search Algorithm
Jinhui Ge1, Xiaoliang Liu2, *, Guo Liang3
1 School of Mathematics, Tonghua Normal University, Tonghua, 134000, China.
2 School of Computer Science and Technology, Hunan University of Technology and Business, Changsha,
410205, China.
3 School of Bioinformatics, University of Minnesota, Twin Cities, USA.
* Corresponding Author: Xiaoliang Liu. Email: .
Computers, Materials & Continua 2020, 64(3), 1945-1958. https://doi.org/10.32604/cmc.2020.010977
Received 12 April 2020; Accepted 27 April 2020; Issue published 30 June 2020
Abstract
With the expansion of the application scope of social computing problems,
many path problems in real life have evolved from pure path optimization problems to
social computing problems that take into account various social attributes, cultures, and
the emotional needs of customers. The actual soft time window vehicle routing problem,
speeding up the response of customer needs, improving distribution efficiency, and
reducing operating costs is the focus of current social computing problems. Therefore,
designing fast and effective algorithms to solve this problem has certain theoretical and
practical significance. In this paper, considering the time delay problem of customer
demand, the compensation problem is given, and the mathematical model of vehicle path
problem with soft time window is given. This paper proposes a hybrid tabu search (TS) &
scatter search (SS) algorithm for vehicle routing problem with soft time windows
(VRPSTW), which mainly embeds the TS dynamic tabu mechanism into the SS
algorithm framework. TS uses the scattering of SS to avoid the dependence on the quality
of the initial solution, and SS uses the climbing ability of TS improves the ability of
optimizing, so that the quality of search for the optimal solution can be significantly
improved. The hybrid algorithm is still based on the basic framework of SS. In particular,
TS is mainly used for solution improvement and combination to generate new solutions.
In the solution process, both the quality and the dispersion of the solution are considered.
A simulation experiments verify the influence of the number of vehicles and maximum
value of tabu length on solution, parameters’ control over the degree of convergence, and
the influence of the number of diverse solutions on algorithm performance. Based on the
determined parameters, simulation experiment is carried out in this paper to further prove
the algorithm feasibility and effectiveness. The results of this paper provide further ideas
for solving vehicle routing problems with time windows and improving the efficiency of
vehicle routing problems and have strong applicability.
Keywords
Cite This Article
J. Ge, X. Liu and G. Liang, "Research on vehicle routing problem with soft time windows based on hybrid tabu search and scatter search algorithm,"
Computers, Materials & Continua, vol. 64, no.3, pp. 1945–1958, 2020. https://doi.org/10.32604/cmc.2020.010977
Citations