基于匈牙利算法的运输问题改进算法

详细信息    查看全文 | 推荐本文 |

英文篇名：An Improved Algorithm of Transportation Problem Based on Hungarian Algorithm 作者：张雨晨 ; 王竹芳 英文作者：ZHANG Yu-chen;WANG Zhu-fang;School of Management,Shenyang University of Technology; 关键词：匈牙利算法 ; 运输问题 ; 改进算法 英文关键词：Hungarian algorithm;;transport problem;;improved algorithm 中文刊名：JZGC 英文刊名：Value Engineering 机构：沈阳工业大学管理学院; 出版日期：2019-01-14 出版单位：价值工程 年：2019 期：v.38;No.516 基金：辽宁省教育厅人文社会科学研究项目(WQGD2017015) 语种：中文; 页：JZGC201904025 页数：5 CN：04 ISSN：13-1085/N 分类号：84-88

摘要

基于运输问题的模型和特点,提出了一种与匈牙利算法结合的改进算法,匈牙利算法作为一种较成熟的基本算法,在计算运输问题时省去大量求解检验数的计算。改进算法将运输问题分解成多个指派问题,利用匈牙利算法求解分解后的指派问题,最后将所有指派问题的结果求和得到最优解。给出了一个改进算法的案例,详细的介绍了改进算法的计算过程,证明了改进算法的有效性。
        Based on the model and characteristics of transportation problems, an improved algorithm combined with Hungarian algorithm is put forward to solve transportation problem in this paper. Hungarian algorithm, as a more mature basic algorithm, eliminates the calculation of a large number of solution numbers when calculating transportation problems. The improved algorithm decomposes the transportation problem into multiple assignment problems, uses the Hungarian algorithm to solve the decomposed transportation problem,finally sums the results of all assignment problems to obtain an optimal solution. This paper presents a case of the improved algorithm,introduces the calculation process of the improved algorithm in detail, and proves the effectiveness of the improved algorithm.

引文

[1]贾春玉.运输问题新解法的探讨[J].系统工程学报,2004(02):207-211,217.
    [2]夏少刚,张建华.求解运输问题的一种新算法[J].运筹与管理,2007(01):32-36.
    [3]夏少刚,费威.基于最小调整法求解最短时限指派问题[J].数学的实践与认识,2009,39(17):179-187.
    [4]林健,冯允成.多物资流多运输方式动态随机运输问题的解析模型[J].中国流通经济,1995(04):35-39.
    [5]郭强,陈新庄.平衡和不平衡运输问题与分配问题的通用迭代算法[J].运筹与管理,2007(06):57-62.
    [6]陈星明,刘飞,王平,聂能,胡向东,陈勇,冯辉宗.邮政运输问题的数学模型[J].重庆大学学报(自然科学版),2000(02):120-122.
    [7]Tadei R, Perboli G, Croce F D. A Heuristic Algorithm for the Auto-Carrier Transportation Problem[J]. Transportation Science,2002, 36(1):55-62.
    [8]Rao R C, Shaftel T L. Computational experience on an algorithm for the transportation problem with nonlinear objective functions[J]. Naval Research Logistics, 2010, 27(1):145-157.
    [9]Chizat L, PeyréG, Schmitzer B, et al. Scaling algorithms for unbalanced optimal transport problems[J]. Mathematics of Computation, 2017.
    [10]孙文龙,张发明.受时间限制的运输问题的新算法[J].运筹与管理,2013,22(06):52-56.
    [11]Serdar K oru kog姚lu, Serkan Balli. An Improved Vogel’s Approximation Method for the transportation problem[J].Mathematical&Computational Applications, 2011, 16(2):370-381.
    [12]韩伟一,张庆普.运输问题表上作业法的一点注记[J].运筹与管理,2009,18(04):7-9.
    [13]《运筹学》教材编写组.运筹学(第四版)[M].北京:清华大学出版社,2013.