复杂环境下动态车辆路径问题的建模与求解

复杂环境下动态车辆路径问题的建模与求解 Modeling and Solving of Dynamic Vehicle Routing Problem in Complex Environment 王江晴 WANG Jiangqing 1 first-author 张潇 ZHANG Xiao 1 中南民族大学计算机科学学院 中南民族大学计算机科学学院 College of Computer Science,South-Central University for Nationalities College of Computer Science,South-Central University for Nationalities 针对复杂环境下带时间窗的动态车辆路径问题（dynamic vehiclerouting problem with time windows,DVRPTW）,构建了一个考虑多个优化目标的该类问题的混合整数规划模型和状态转换模型,设计了求解规划路径的计算方法,建立了环境复杂度指标对实验环境进行准确描述和合理评价.模型从实际应用系统的需求出发,针对实际交通网络中任意一条路径均可能发生交通不畅或阻塞的情形,采用最短行驶时间对路径进行优化,并引入模糊集合理论对路况进行更准确的描述.实验结果显示,对于复杂环境下随机生成的DVRPTW问题,该模型具有较强的可行性和实用性. In order to solve the dynamic vehicle routing problem in complex environment,a new mixed integral programming model and a status transfer model which consider multi-objective optimization were proposed,algorithms solving the programming routes were designed,and the metrics of environment complexity was established for accurate description and reasonable evaluation of the experimental environment. Considering the requirements of practical application systems,the models focus on the situation that the traffic jam may occur in any route in real transportation network,and use the shortest driving time to optimize routes,and induce fuzzy set theory to give more accurate description to the road situation. Experimental results show that,for the DVRPTW problem randomly generated in complex environment,the proposed models presents more feasibility and practicality. 动态交通网络 模糊信息 车辆路径问题 时间窗 dynamic traffic network fuzzy information vehicle routing problem time windows 10.14188/j.1671-8836.2010.04.022 TP301.6 国家自然科学基金资助项目（60842004） 2010-04-01 2021-04-01 4 56