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.
Similar content being viewed by others
References
Murty, K.G.: Solving the fixed charge problem by ranking the extreme points. Oper. Res. 16, 268–279 (1968)
Sadagopan, S., Ravindran, A.: A vertex ranking algorithm for the fixed-charge transportation problem. J. Optim. Theory Appl. 37, 221–230 (1982)
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)
Steinberg, D.I.: The fixed charge problem. Nav. Res. Logist. Q. 17, 217–235 (1970)
Adlakha, V., Kowalski, K., Vemuganti, R.R.: Heuristic algorithms for the fixed-charge transportation problem. Opsearch 43, 88–108 (2006)
Cooper, L.: The fixed charge problem—I: a new heuristic method. Comput. Math. Appl. 1, 89–95 (1975)
Cooper, L., Drebes, C.: An approximate algorithm for the fixed charge problem. Nav. Res. Logist. Q. 14, 101–113 (1967)
Drenzler, D.R.: An approximate method for the fixed charge problem. Nav. Res. Logist. Q. 16, 411–416 (1969)
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)
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)
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)
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)
Klose, A.: Algorithms for solving the single-sink fixed-charge transportation problem. Comput. Oper. Res. 35, 2079–2092 (2008)
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)
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)
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)
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)
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)
Walker, W.E.: A heuristic adjacent extreme point algorithm for the fixed charge problem. Manag. Sci. 22, 587–596 (1976)
Adlakha, V., Kowalski, K., Lev, B.: A branching method for the fixed charge transportation problem. OMEGA, Int. J. Manag. Sci. 38, 393–397 (2010)
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)
Hirsch, W., Danzig, G.B.: The fixed charge problem. Nav. Res. Logist. Q. 15, 413–424 (1968)
Adlakha, V., Kowalski, K.: A simple heuristic for solving small fixed-charge transportation problems. OMEGA, Int. J. Manag. Sci. 31, 205–211 (2003)
Kowalski, K.: On the structure of the fixed charge transportation problem. Int. J. Math. Educ. Sci. Technol. 36, 879–888 (2005)
Balinski, M.L.: Fixed cost transportation problems. Nav. Res. Logist. Q. 8, 41–54 (1961)
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-013-0437-y