摘要
为满足不同用户对不同厂家、不同产品的数量要求,以运输总费用最小为目标,建立有供需要求运输问题的线性规划模型。将中转站顶点、用户顶点拆分后与厂家顶点、产品顶点分别关联,构建运输问题网络模型;推导出中转能力和直供能力一定条件下的中转站边和直供边容量约束方程;通过增设平行边,将容量有上下界约束的网络流问题转化为一般网络流问题;采用改进的最小费用最大流问题算法求出初始解。通过扩大直供边和中转站边的容量,使潜在的负回路显现,根据搜索的目的不同,有选择地切断部分直供边和配送边,从而在不同的范围内搜索负回路,并在负回路上调整流量,使初始解最终转化为最优解。通过算例分析,验证了模型和算法的可行性。
In order to satisfy the demands of different companies to the quantities of the different products,the linear programming model of transportation problem with supply-demand requirements is set up aimed at the minimum transport costs.The transfer nodes,customer nodes are connected with the company nodes and the product nodes to form the transportation network model.The constraint equation for the transfer station arcs and the direct-supply arcs is deduced under the condition of given transfer capacity and direct supply capacity. By adding the parallel arcs, the network flow problem with the upper and lower bounds is transformed to the ordinary network flow problem. The proved algorithm for the problem of minimum-cost maximum flow problem is adopted to get the primary solution. By expanding the capacity of transfer station arcs and the direct-supply arcs, the potential negative loop is emerged. According to different searching goal, the selected direct-supply arcs and the distribution arcs are cut off and the negative loops are searched in different scopes and the fluxes are adjusted to make the primary solution approach to the optimal solution. Finally, a case study is carried out, and the results show that the model and the algorithm are feasible.
出处
《中国铁道科学》
EI
CAS
CSCD
北大核心
2009年第5期109-115,共7页
China Railway Science
关键词
货物运输
供需平衡
运输网络
网络模型
网络流
优化设计
Freight transportation
Balanced supply and demand
Transportation network
Network model
Network flow
Optimal design
