Heuristic solutions for general concave minimum cost network flow problems

被引:27
|
作者
Fontes, Dalila B. M. M.
Goncalves, Jose Fernando
机构
[1] Univ Porto, Fac Econ, P-4200464 Oporto, Portugal
[2] LIACC, P-4200464 Oporto, Portugal
关键词
network flow; heuristics; genetic algorithms; local search; concave-cost optimization; combinatorial optimization;
D O I
10.1002/net.20167
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We address the single-source uncapacitated minimum cost network flow problem with general concave cost functions. Exact methods to solve this class of problems in their full generality are only able to address small to medium size instances, since this class of problems is known to be NP-Hard. Therefore, approximate methods are more suitable. In this work, we present a hybrid approach combining a genetic algorithm with a local search. Randomly generated test problems have been used to test the computational performance of the algorithm. The results obtained for these test problems are compared to optimal solutions obtained by a dynamic programming method for the smaller problem instances and to upper bounds obtained by a local search method for the larger problem instances. From the results reported it can be shown that the hybrid methodology improves upon previous approaches in terms of efficiency and also on the pure genetic algorithm, i.e., without using the local search procedure. (C) 2007 Wiley Periodicals, Inc.
引用
收藏
页码:67 / 76
页数:10
相关论文
共 50 条
  • [41] A feasibility pump heuristic for general mixed-integer problems
    Bertacco, Livio
    Fischetti, Matteo
    Lodi, Andrea
    DISCRETE OPTIMIZATION, 2007, 4 (01) : 63 - 76
  • [42] Solving minimum distance problems with convex or concave bodies using combinatorial global optimization algorithms
    Carretero, JA
    Nahon, MA
    IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 2005, 35 (06): : 1144 - 1155
  • [43] Heuristic genetic algorithms for general capacitated lot-sizing problems
    Xie, JX
    Dong, JF
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2002, 44 (1-2) : 263 - 276
  • [44] Determining the Minimum Cost Steiner Tree for Delay Constrained Problems
    Martins, Lucia
    Santos, Dorabella
    Gomes, Teresa
    Girao-Silva, Rita
    IEEE ACCESS, 2021, 9 : 144927 - 144939
  • [45] Heuristic solutions for transshipment problems in a multiple door cross docking warehouse
    Alpan, Guelguen
    Ladier, Anne-Laure
    Larbi, Rim
    Penz, Bernard
    COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 61 (02) : 402 - 408
  • [46] Minimum-Cost Multiple Paths Subject to Minimum Link and Node Sharing in a Network
    Zheng, S. Q.
    Wang, Jianping
    Yang, Bing
    Yang, Mei
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2010, 18 (05) : 1436 - 1449
  • [47] An O(nm2) time algorithm for solving minimal cost network flow problems
    Fathabadi, HS
    Shirdel, GH
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2003, 20 (02) : 161 - 175
  • [48] On seeking efficient Pareto optimal points in multi-player minimum cost flow problems with application to transportation systems
    Shuvomoy Das Gupta
    Lacra Pavel
    Journal of Global Optimization, 2019, 74 : 523 - 548
  • [49] On seeking efficient Pareto optimal points in multi-player minimum cost flow problems with application to transportation systems
    Das Gupta, Shuvomoy
    Pavel, Lacra
    JOURNAL OF GLOBAL OPTIMIZATION, 2019, 74 (03) : 523 - 548
  • [50] A Minimum Cost of Network Hardening Model Based on Attack Graphs
    Ma Jun-chun
    Wang Yong-jun
    Sun Ji-yin
    Chen Shan
    CEIS 2011, 2011, 15