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

粮食调运优化问题属于一种多回路运输问题,本文提出了一个解决粮食调运优化问题的两阶段求解方法,在第一阶段,由图搜索算法产生所有可行的运输路线,并根据约束条件对搜索树进行剪枝;在第二阶段,采用整数规划模型从第一阶段产生的可行路线集合中选取最佳路线,使总的运输成本最低.同时基于该方法开发了一个粮食调运决策支持系统,经过测试,该系统在最坏的情况下能节省9%~15%的路程和10%~18%的运输费用.

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

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.