Skip to main content
SpringerLink
Log in

Fractional Polynomial Bounds for the Fixed Charge Problem

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

In this paper we seek to enhance the understanding of the structure of the fixed charge transportation problem (FCTP) and to demonstrate the relationship between fixed charge problems and fractional polynomial functions. We provide a new approach for approximating and solving the FCTP by developing novel fractional polynomial approximations for the objective function to obtain lower and upper bounds for the optimal solution. In addition, the lower bound proposed in the paper can be used to obtain superior initial or starting conditions for any established branch-and-bound or iterative algorithm to accelerate convergence to the optimal FCTP solution.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Murty, K.G.: Solving the fixed charge problem by ranking the extreme points. Oper. Res. 16, 268–279 (1968)

    Article  MATH  Google Scholar 

  2. Sadagopan, S., Ravindran, A.: A vertex ranking algorithm for the fixed-charge transportation problem. J. Optim. Theory Appl. 37, 221–230 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  3. Palekar, U.S., Karwan, M.H., Zionts, S.: A branch-and-bound method for the fixed charge transportation problem. Manag. Sci. 36, 1092–1105 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  4. Steinberg, D.I.: The fixed charge problem. Nav. Res. Logist. Q. 17, 217–235 (1970)

    Article  MATH  Google Scholar 

  5. Adlakha, V., Kowalski, K., Vemuganti, R.R.: Heuristic algorithms for the fixed-charge transportation problem. Opsearch 43, 88–108 (2006)

    MathSciNet  Google Scholar 

  6. Cooper, L.: The fixed charge problem—I: a new heuristic method. Comput. Math. Appl. 1, 89–95 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  7. Cooper, L., Drebes, C.: An approximate algorithm for the fixed charge problem. Nav. Res. Logist. Q. 14, 101–113 (1967)

    Article  MATH  Google Scholar 

  8. Drenzler, D.R.: An approximate method for the fixed charge problem. Nav. Res. Logist. Q. 16, 411–416 (1969)

    Article  Google Scholar 

  9. Wright, D.C., Lanzenauer, H.V.: COLE: A new heuristic approach for fixed charge problem computational results. Eur. J. Oper. Res. 52, 235–246 (1991)

    Article  MATH  Google Scholar 

  10. Aguado, J.S.: Fixed charge transportation problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems. Ann. Oper. Res. 172, 45–69 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  11. Sun, M., Aronson, J.E., McKeown, P.G., Drinka, D.: A tabu search heuristic procedure for the fixed charge transportation problem. Eur. J. Oper. Res. 106, 441–456 (1998)

    Article  MATH  Google Scholar 

  12. Glover, F., Amini, M., Kochenberger, G.: Parametric ghost image processes for fixed charge problems: a study of transportation networks. J. Heuristics 11, 307–336 (2005)

    Article  MATH  Google Scholar 

  13. Klose, A.: Algorithms for solving the single-sink fixed-charge transportation problem. Comput. Oper. Res. 35, 2079–2092 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  14. Jawahar, N., Balaji, A.N.: A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge. Eur. J. Oper. Res. 194, 496–537 (2009)

    Article  MATH  Google Scholar 

  15. Hajiaghaei-Keshteli, M., Molla-Alizadeh-Zavardehi, S., Tavakkoli-Moghaddam, R.: Addressing a nonlinear fixed-charge transportation problem using a spanning tree-based genetic algorithm. Comput. Ind. Eng. 59, 259–271 (2010)

    Article  Google Scholar 

  16. Jo, J.B., Li, Y., Gen, M.: Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm. Comput. Ind. Eng. 53, 290–298 (2007)

    Article  Google Scholar 

  17. Caramia, M., Guerriero, F.: A heuristic approach to long-haul freight transportation with multiple objective functions. OMEGA, Int. J. Manag. Sci. 37, 600–614 (2009)

    Article  Google Scholar 

  18. Ortega, F., Wolsey, L.A.: A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem. Networks 41, 143–158 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  19. Walker, W.E.: A heuristic adjacent extreme point algorithm for the fixed charge problem. Manag. Sci. 22, 587–596 (1976)

    Article  MATH  Google Scholar 

  20. Adlakha, V., Kowalski, K., Lev, B.: A branching method for the fixed charge transportation problem. OMEGA, Int. J. Manag. Sci. 38, 393–397 (2010)

    Article  Google Scholar 

  21. Schrenk, S., Finke, G., Cung, V.D.: Two classical transportation problems revisited: pure constant fixed charges and the paradox. Math. Comput. Model. 54, 2306–2315 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  22. Hirsch, W., Danzig, G.B.: The fixed charge problem. Nav. Res. Logist. Q. 15, 413–424 (1968)

    Article  MATH  Google Scholar 

  23. Adlakha, V., Kowalski, K.: A simple heuristic for solving small fixed-charge transportation problems. OMEGA, Int. J. Manag. Sci. 31, 205–211 (2003)

    Article  Google Scholar 

  24. Kowalski, K.: On the structure of the fixed charge transportation problem. Int. J. Math. Educ. Sci. Technol. 36, 879–888 (2005)

    Article  Google Scholar 

  25. Balinski, M.L.: Fixed cost transportation problems. Nav. Res. Logist. Q. 8, 41–54 (1961)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Management and International Business, University of Baltimore, 1420 N. Charles St., Baltimore, MD, 21201, USA

    V. Adlakha

  2. Dept. of Transportation, State of Connecticut, 121 Cimmarron Road, Middletown, CT, 06457, USA

    K. Kowalski

Authors
  1. V. Adlakha
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. K. Kowalski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. Adlakha.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Adlakha, V., Kowalski, K. Fractional Polynomial Bounds for the Fixed Charge Problem. J Optim Theory Appl 164, 1026–1038 (2015). https://doi.org/10.1007/s10957-013-0437-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-013-0437-y

Keywords

Search

Navigation