Open Access

ARTICLE

Research on Vehicle Routing Problem with Soft Time Windows Based on Hybrid Tabu Search and Scatter Search Algorithm

Jinhui Ge¹, Xiaoliang Liu^{2, *}, Guo Liang³

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

---

Citations