Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Global and Local Search Algorithms for Concave Cost Transshipment Problems

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Traditionally, the minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Recently, some advanced local search algorithms have been developed that can directly solve concave cost bipartite network problems. However, they are not applicable to general transshipment problems. Moreover, the effectiveness of these modified local search algorithms for solving general concave cost transshipment problems is doubtful. In this research, we propose a global search algorithm for solving concave cost transshipment problems. Effecient methods for encoding, generating initial populations, selection, crossover and mutation are proposed, according to the problem characteristics. To evaluate the effectiveness of the proposed global search algorithm, four advanced local search algorithms based on the threshold accepting algorithm, the great deluge algorithm, and the tabu search algorithm, are also developed and are used for comparison purpose. To assist with the comparison of the proposed algorithms, a randomized network generator is designed to produce test problems. All the tests are performed on a personal computer. The results indicate that the proposed global search algorithm is more effective than the four advanced local algorithms, for solving concave cost transshipment problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abuali, F.N., Wainwright, R.L. and Schoenefeld D.A. (1995), Determinant Factorization: a new encoding scheme for spanning trees applied to the probabilistic minimum spanning tree problem, Proceedings of the Sixth International Conference on Genetic Algorithms 470–477.

  2. R.K. Ahuja T.L. Maganti J.B. Orlin (1993) Network Flows, Theory, Algorithms, and Applications Prentice Hall Englewood Cliffs

    Google Scholar 

  3. A. Amiri H. Pirkul (1997) ArticleTitleNew formulation and relaxation to solve a concave cost network flow problem Journal of the Operational Research Society 48 278–287 Occurrence Handle10.1038/sj.jors.2600363

    Article  Google Scholar 

  4. A. Balakrishnan S.C. Graves (1989) ArticleTitleA composite algorithm for a concave-cost network flow problem Networks 19 175–202

    Google Scholar 

  5. D.E. Blumenfeld L.D. Burns J.D. Diltz C.F. Daganzo (1985) ArticleTitleAnalyzing trade-offs between transportation, inventory, and production costs on freight network Transportation Research 19B 361–380

    Google Scholar 

  6. L.B. Booker (1987) Improving search in genetic algorithms L. Davis (Eds) Genetic Algorithms and Simulated Annealing Pitman London 61–73

    Google Scholar 

  7. I. Charon O. Hurdy (1993) ArticleTitleThe noising method: a new method for combinatorial optimization Operations Research Letters 14 133–137 Occurrence Handle10.1016/0167-6377(93)90023-A

    Article  Google Scholar 

  8. Cheng, C.P., Liu, C.W. and Liu, C.C. (2000), Unit commitment by Lagrangian relaxation and genetic algorithms, IEEE Transactions on Power Systems 15, (2).

  9. L. Davis (1987) Genetic Algorithm and Simulated Annealing Morgan Kaufman Publishers Los Altos, CA

    Google Scholar 

  10. Davis, L. (1989), Adapting operator probabilities in genetic algorithms, Proceedings of the Third International Conference on Genetic Algorithms, 61–69.

  11. L. Davis (1991) Handbook of Genetic Algorithms Van Nostrand Reinhold New York

    Google Scholar 

  12. DeJong, K.A. (1975), Analysis of the behavior of a class of genetic adaptive systems, Ph.D. dissertation, University of Michigan.

  13. G. Dueck (1993) ArticleTitleNew optimization heuristics: the great deluge algorithm and the record-to-record travel Journal of Computational Physics 104 86–92 Occurrence Handle10.1006/jcph.1993.1010

    Article  Google Scholar 

  14. G. Dueck T. Scheuer (1990) ArticleTitleThreshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing Journal of Computational Physics 90 161–175 Occurrence Handle10.1016/0021-9991(90)90201-B

    Article  Google Scholar 

  15. D. Kim P.M. Pardalos (2000) ArticleTitleDynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems Networks 35 216–222 Occurrence Handle10.1002/(SICI)1097-0037(200005)35:3<216::AID-NET5>3.0.CO;2-E

    Article  Google Scholar 

  16. G. Gallo C. Sandi C. Sodini (1980) ArticleTitleAn algorithm for the min concave cost flow problem European Journal of Operation Research 4 248–255 Occurrence Handle10.1016/0377-2217(80)90109-5

    Article  Google Scholar 

  17. G. Gallo C. Sandi (1979) ArticleTitleAdjacent extreme flows and application to min concave cost flow problems Networks 9 95–121

    Google Scholar 

  18. M. Gen R. Cheng (1997) Genetic Algorithms and Engineering Design Wiley Interscience Publication MA

    Google Scholar 

  19. F. Glover M. Laguna (1997) Tabu Search Kluwer Academic Publishers Massachusetts

    Google Scholar 

  20. F. Glover (1989) ArticleTitleTabu Search, Part I ORSA Journal on Computing 1 IssueID3 190–206

    Google Scholar 

  21. F. Glover (1990) ArticleTitleTabu Search- Part II ORSA Journal on Computing 2 IssueID1 4–32

    Google Scholar 

  22. D.E. Goldberg (1989) Genetic Algorithms in Search, Optimization, and Machine Learning Addison-Wesley Reading MA

    Google Scholar 

  23. B.L. Golden C.C. Skiscim (1986) ArticleTitleUsing stimulated annealing to solve routing and location problems Naval Research Logistic Quarterly 33 261–279

    Google Scholar 

  24. J. Gu X. Huang (1994) ArticleTitleEfficient local search with search space smoothing: a case study of the traveling salesman problem (TSP), IEEE Transaction on Systems Man and Cybernetics 24 728–739 Occurrence Handle10.1109/21.293486

    Article  Google Scholar 

  25. G.M. Guisewite P.M. Pardalos (1993) ArticleTitleA polynomial time solvable concave network flow problems Networks 23 143–147

    Google Scholar 

  26. Hall, R.W. (1983), Direct versus terminal freight routing on network with concave costs, GMR-4517, Transportation Research Dept., GM Research Laboratories.

  27. Jeffrey, A.J. and Christopher, R.H. (1994), On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GA's, Department of Industrial Engineering North Carolina State University, NC 27695–7906.

  28. Jordan, W.C. (1986), Scale economies on multi-commodity networks, GMR-5579, Operating Systems Research Dept., GM Research Laboratories.

  29. A. Kershenbaum (1997) ArticleTitleWhen genetic algorithms work best INFORMS Journal of Computing 9 IssueID3 253–254

    Google Scholar 

  30. S. Kirkpatrick C.D. Gelatt M.P. Vecchi (1983) ArticleTitleOptimization by simulated annealing Science 220 671–680

    Google Scholar 

  31. H.W. Kuhn W.J. Baumol (1962) ArticleTitleAn approximate algorithm for the fixed-charge transportation problem Naval Res. Logistics Quarterly 9 1–16

    Google Scholar 

  32. T. Larsson A. Migdalas M. Ronnqvist (1994) ArticleTitleA Lagrangian heuristic for the capacitated concave minimum cost network flow problem European Journal of Operational Research 78 116–129 Occurrence Handle10.1016/0377-2217(94)90126-0

    Article  Google Scholar 

  33. Mathias, K.E. and Whitley, L.D. (1994), Initial performance comparisons for the delta coding algorithm, The First IEEE Conference on Evolutionary Computation, Orlando, Florida.

  34. F.J. Nourie F. Guder (1994) ArticleTitleA restricted-entry method for a transportation problem with piecewise-linear concave cost Computer & Operations Research 21 723–733

    Google Scholar 

  35. I.H. Osman J.P. Kelly (1996) Meta-Heuristics: An Overview, Meta-Heuristics Theory & Applications Kluwer Academic Publishers Boston, London, Dordrecht 1–21

    Google Scholar 

  36. C.C. Palmer A. Kershenbaum (1995) ArticleTitleAn approach to a problem in network design using genetic algorithms Networks 26 151–163

    Google Scholar 

  37. Rech, P. and Barton, L.G. (1970), A Non-convex transportation algorithm, In: Beale, E.M. (ed.), Applications of Mathematical Programming Techniques.

  38. C. Reeves (1997) ArticleTitleGenetic algorithms for the operations researcher INFORMS Journal on Computing 9 IssueID3 231–250

    Google Scholar 

  39. Reeves, C.R. (1993), Modern Heuristic Techniques for Combinatorial Problems, John Wiley and Sons, Inc.

  40. G. Rudolph (1994) ArticleTitleConvergence properties of canonical genetic algorithms IEEE Transactions On Neural Networks 5 96–101 Occurrence Handle10.1109/72.265964

    Article  Google Scholar 

  41. Seiichi, K., Maggie, K. and Wayne, W.D. (1995), Genetic Simulated Annealing and Application to Non-slicing Floor plan Design, Baskin Center for Computer Engineering & Information Sciences University of California, Santa Cruz, CA 95064.

  42. M. Srinivas L.M. Patnaik (1994) ArticleTitleAdaptive probabilities of crossover and mutation in genetic algorithms, IEEE Transaction On System Man and Cybern 24 656–667

    Google Scholar 

  43. Suwan, R. and Sawased, T. (1999), Link capacity assignment in packet-switched networks: the case of piecewise linear concave cost function, IEICE Transaction Communications E82-B(10).

  44. T. Taguhi M. Ida. K. Gen (1998) ArticleTitleA genetic algorithm for optimal flow assignment in computer network Computers and Industrial Engineering 35 IssueID(3–4) 535–538 Occurrence Handle10.1016/S0360-8352(98)00152-1

    Article  Google Scholar 

  45. P.T. Thach (1992) ArticleTitleA decomposition method using a pricing mechanism for min concave cost flow problems with a hierarchical structure Mathematical Programming 53 339–359 Occurrence Handle10.1007/BF01585711

    Article  Google Scholar 

  46. Thierens, D. and Goldberg D. (1994), Elitist recombination: an integrated selection recombination GA, The First IEEE Conference on Evolutionary Computation, Orlando, Florida.

  47. B. Yaged (1971) ArticleTitleMinimum cost routing for static network models Networks 1 139–172

    Google Scholar 

  48. S. Yan (1996) ArticleTitleApproximating reduced costs under degeneracy in a network flow problem with side constraints Networks 27 267–278 Occurrence Handle10.1002/(SICI)1097-0037(199607)27:4<267::AID-NET2>3.0.CO;2-E

    Article  Google Scholar 

  49. S. Yan S.C. Luo (1998) ArticleTitleA tabu search-based algorithm for concave cost transportation network problems Journal of the Chinese Institute of Engineers 21 327–335

    Google Scholar 

  50. S. Yan S.C. Luo (1999) ArticleTitleProbabilistic local search algorithms for concave cost transportation network problems European Journal of Operational Research 117 511–521 Occurrence Handle10.1016/S0377-2217(98)00270-7

    Article  Google Scholar 

  51. S. Yan D.H. Yang (1996) ArticleTitleA decision support framework for handling schedule perturbation Transportation Research 30B 405–419

    Google Scholar 

  52. W.I. Zangwill (1968) ArticleTitleMinimum concave cost flows in certain networks Management Science 14 429–450

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Civil Engineering, National Central University, 32054, Taiwan, R.O.C.

    Shangyao Yan, Der-shin Juang, Chien-rong Chen & Wei-shen Lai

Authors
  1. Shangyao Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Der-shin Juang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chien-rong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wei-shen Lai
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yan, S., Juang, Ds., Chen, Cr. et al. Global and Local Search Algorithms for Concave Cost Transshipment Problems. J Glob Optim 33, 123–156 (2005). https://doi.org/10.1007/s10898-004-3133-5

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-004-3133-5

Keywords

Search

Navigation