一种求解粮食调运优化问题的两阶段方法  

Two-stage Optimization Approach for the Problem of Grain Dispatching and Transportation

作　　者：于海鸿[1,2] 孙吉贵[1,2] 李泽海[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,吉林长春130012

出　　处：《小型微型计算机系统》2007年第3期495-499,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60073039;60273080)资助;吉林省科技发展计划项目(20020306)资助;吉林省杰出青年基金项目(20030107)资助.

摘　　要：粮食调运优化问题属于一种多回路运输问题，本文提出了一个解决粮食调运优化问题的两阶段求解方法，在第一阶段，由图搜索算法产生所有可行的运输路线，并根据约束条件对搜索树进行剪枝；在第二阶段，采用整数规划模型从第一阶段产生的可行路线集合中选取最佳路线，使总的运输成本最低．同时基于该方法开发了一个粮食调运决策支持系统，经过测试，该系统在最坏的情况下能节省9％～15％的路程和10％～18％的运输费用．The problem of grain dispatching and transportation is a vehicle routing problem. This paper presents a two-stage optimization algorithm for solving the problem. In the first stage,all the feasible routes are generated by means of a graph-search algorithm. The search tree is pruned according to the constraints. In the second stage ,an integer programming model is designed to select the optimum routes from the set of feasible routes. The total cost of all the optimum routes is the least. Based on the two-stage approach,a decision support system for grain dispatching and transportation was also developed. The system was tested with a set of real instances. And in a worst-case scenario, the routes obtained ranged from a 9 % to 15 % reduction in the distance and from a 10% to 18% reduction in operational costs.

关 键 词：粮食调运 多回路运输问题 图搜索算法 整数规划 决策支持系统 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]