回溯法在物流车动态导航中的应用

Application of backtracking in logistics vehicle dynamic navigation

研究物流车的动态导航问题。由于物流车在配送过程中经常会遇到堵车情况,如果物流车仍按照原最优路径进行配送,则会降低物流车的配送效率。传统的TSP算法只能为物流车规划一个静态最优路径,一旦物流车遇到堵车就无法调整,这样的导航不能提高物流车的配送效率。为了避免上述缺陷,提出了一种用回溯法实现物流车配送的动态优化算法。首先,利用回溯法实现物流车配送的静态优化,将该路径作为物流车的初始路径。如果物流车行驶路径的前方出现堵车,则用回溯法对物流车未配送的客户重新规划一条新的最短路径,通过避开堵车路段来提高物流车的配送效率。如果某个路段的堵车解除而该路段两端的客户还未被配送,则用回溯法对未配送的客户重新规划最短路径来提高配送效率。实验结果表明,利用本文算法进行物流车配送的动态优化算法,能够有效提高物流车的配送效率。

In this paper,dynamic navigation problem of a Logistics vehicle is researched. Because a logistics vehicle often encounters a traffic jam situation in the distribution process,so if the car still distributes in accordance with the original optimal path,it will reduce the distribution efficiency of the logistics vehicle. Traditional TSP algorithm can only supply a static optimal route for a logistics vehicle. Once the logistics vehicle is jammed in traffic,the route can't be adjusted so that the navigation can't improve the distribution efficiency of the logistics vehicle. To avoid this shortcoming,this paper presents a backtracking to achieve dynamic optimization distribution algorithm for the logistics vehicle. First,it uses the backtracking to achieve static optimization distribution route for the logistics vehicle and this path is regarded as the initial path of the logistics vehicle. If there is a traffic jam in the path in front of the logistics vehicle,it uses the backtracking to re-plan a new shortest path to improve the distribution efficiency for the logistics vehicle. If a section of the road is jammed and the both ends customers of the line has not been visited,it uses the backtracking to re-plan shortest path for the unvisited customers to improve the delivery efficiency.Experimental results show that the proposed algorithm can effectively improve the distribution efficiency for the logistics vehicle.