Open AccessNew construction heuristic algorithm for solving the vehicle routing problem with time windows
Author(s) -
Liu Jun,
Feng Shuo,
Niu Qun,
Ji Lijuan
Publication year - 2019
Publication title -
iet collaborative intelligent manufacturing
Language(s) - English
Resource type - Journals
ISSN - 2516-8398
DOI - 10.1049/iet-cim.2019.0035
Subject(s) - vehicle routing problem , heuristics , mathematical optimization , computer science , heuristic , path (computing) , constraint (computer aided design) , constructive , routing (electronic design automation) , algorithm , mathematics , computer network , geometry , process (computing) , programming language , operating system
The vehicle routing problem with time windows (VRPTW) is the most important and widely studied combinational optimisation problem. However, most constructive heuristics create a new path when the customer violates the constraint and cannot insert into any existing path, causing the time window constraint to be tight and generating more paths. Aiming at the above problems, a new constructive heuristic algorithm is proposed. The algorithm firstly uses the convex hull of the customer location to determine the initial seed client and reduces the redundant path; meanwhile, the calculation method of the traditional optimal insertion position is improved, and the calculation efficiency is improved to some extent; in addition, for customers who cannot insert any feasible path, the exchange operator is introduced to give the current solution a disturbance instead of directly creating a new seed client and a new path to further reduce the redundant path. The experimental results show that the algorithm can effectively solve the close time window of VRPTW for evenly distributed customers, and even provide a strict time window for evenly distributed customers and a certain amount of hybrid geographic cluster customers.