基于两阶段求解的动态车辆路径问题研究-《集美大学学报（自然科学版）》

文章信息/Info

Title:: Research on Dynamic Vehicle Routing Problems Based on Two-stage Solving

Author(s):: CHEN Cheng; QIU Rong-zu; (School of Transportation and Civil Engineering，Fujian Agriculture and Forestry University，Fuzhou 350002，China)

Keywords:: dynamic vehicle routing problems; two-stage solving; timing interval; tabu search

摘要:: 采用两阶段求解思想，通过设置定时间隔，将动态信息转化成静态信息，从而实现对动态车辆路径问题的求解.分别建立了初始优化和实时优化阶段的数学模型，以节约算法解为初始解，利用禁忌搜索算法完成初始优化阶段的车辆路径问题求解；在实时优化阶段，分别对节约算法和禁忌搜索算法进行适当修正后再进行求解.利用数值测试实验对客户不同地理位置分布下定时间隔的设置进行测试分析.结果表明，该算法简单明了，易于实现.此外，客户的地理位置分布不同，对定时间隔的敏感性也不同，混合分布最为敏感，其次是随机分布，集聚分布最不敏感；最后，给出了相应的累计服务客户数量曲线，并结合车辆总行驶距离，明确了不同客户位置分布下的较优定时间隔设置.

Abstract:: The idea of two-stage solving is applied and dynamic information is converted into static information by setting timing intervals.Two mathematic models are set up respectively for the periods of initial optimization and real-time optimization.Saving algorithm is used for initial solutions while Tabu search algorithm is used to obtain solutions for vehicle routing issues after initial optimization.In the period of real-time optimization,solutions are obtained after relevant amendments to both algorithms.Then,simulation experiments are carried out to test and analyze settings of time intervals for clients in different geographical locations,and the results prove the simplicity and viability of the proposed solving method.Different sensibilities are shown with different location distributions: mixed distribution is the most sensible to timing intervals;followed by random distribution and then cluster distribution.Finally,the curves corresponding to accumulative numbers of customers served are presented,which,combined with the total travel distances,are used to optimize the setting of timing intervals under different geographic distributions of customers.