动态路网下多车型车辆路径问题研究

摘要

考虑城市路网拥挤程度受城市工商业分布和居民集散特征影响,将路网拥挤情况沿时间轴展开,为确定最佳出发时刻以及服务线路,以配送成本最小为目标函数,构建了考虑服务途中动态拥挤的多车型车辆路径模型,设计了求解该模型的改进遗传算法.计算结果表明:运用本文提出的算法,求解得到最低费用为1085.8元,运输里程为43.51km;运用最短路车辆路径模型,最低费用为1092.7元,运输里程为43.15km.虽然运输里程增加了0.83％,但总费用却降低了0.63％,符合总成本最小的目标函数要求.可见,模型可行,算法有效.%Crowded degree of a urban road network is influenced by the distribution of city industry and commerce,and population distributions.Expanding the crowded degree along the time axis,and determining the best starting time and service lines,and taking the minimum distribution cost as the objective function,a multi-vehicle route model with time window,which considered the dynamic congestion,was constructed.An improved genetic algorithm was designed to solve the model.Calculation results show that using the proposed algorithm,the minimum cost (1085.8yuan) and the transport mileage (43.51 km) were obtained.Meanwhile the lowest cost was 1092.7 yuan,transport mileage was 43.15 km using the shortest path model for vehicle routing.Although the transport mileage increased by 0.83％,but the total cost reduced by 0.63％,which satisfied the objective function with minimum total cost.It is thus clear that the model is feasible,and the algorithm is effective.