On the Quadratic Transportation Problem

Affiliation(s)

University of Baltimore, Baltimore, MD, USA.

Department of Transportation, Middletown, CT, USA.

University of Baltimore, Baltimore, MD, USA.

Department of Transportation, Middletown, CT, USA.

ABSTRACT

We present a direct analytical algorithm for solving transportation problems with quadratic function cost coefficients. The algorithm uses the concept of absolute points developed by the authors in earlier works. The versatility of the proposed algorithm is evidenced by the fact that quadratic functions are often used as approximations for other functions, as in, for example, regression analysis. As compared with the earlier international methods for quadratic transportation problem (QTP) which are based on the Lagrangian relaxation approach, the proposed algorithm helps to understand the structure of the QTP better and can guide in managerial decisions. We present a numerical example to illustrate the application of the proposed method.

Cite this paper

V. Adlakha and K. Kowalski, "On the Quadratic Transportation Problem,"*Open Journal of Optimization*, Vol. 2 No. 3, 2013, pp. 89-94. doi: 10.4236/ojop.2013.23012.

V. Adlakha and K. Kowalski, "On the Quadratic Transportation Problem,"

References

[1] V. Adlakha and K. Kowalski, “An Alternative Solution Algorithm for Certain Transportation Problems,” International Journal of Mathematical Education in Science and Technology, Vol. 30, No. 5, 1999, pp. 719-728. doi:10.1080/002073999287716

[2] H. Arsham, “Postoptimality Analysis of the Transportation Problem,” JORS: Journal of the Operational Research Society, Vol. 43, No. 2, 1992, pp. 121-139.

[3] S. K. Goyal, “Improving VAM for Unbalanced Problems,” JORS, Journal of the Operational Research Society, Vol. 35, No. 12, 1984, pp. 1113-1114.

[4] J. Intrator and W. Szwarc, “An Inductive Property of Transportation Problem,” Asia-Pacific Journal of Operational Research Society, Vol. 5, 1988, pp. 79-83.

[5] M. A. Hakim, “An Alternative Method to Find Initial Basic Feasible Solution of a Transportation Problem,” Annals of Pure and Applied Mathematics, Vol. 1, No. 2, 2012, pp. 203-209.

[6] A. Shafaat and S. K. Goyal, “Resolution of Degeneracy in Transportation Problems,” Journal of the Operational Research Society, Vol. 39, No. 4, 1988, pp. 411-413.

[7] A. Sultan, “Heuristic for Finding an Initial B. F. S. in a Transportation Problem,” Opsearch, Vol. 25, 1988, pp. 197-199.

[8] C. E. Wilsdon, “A Simple, Easily Programmed Method for Locating Rook’s Tours in the Transportation Problem,” Journal of the Operational Research Society, Vol. 41, No. 9, 1990, pp. 879-880.

[9] S. Korukoglu and S. Balli, “An Improved Vogel’s Approximation Method for the Transportation Problem,” Mathematical and Computational Applications, Vol. 16, No. 2, 2011, pp. 370-381.

[10] V. Adlakha and H. Arsham, “Simplifying Teaching the Transportation Problem,” International Journal of Mathematical Education in Science and Technology, Vol. 29, No. 2, 1998, pp. 271-285. doi:10.1080/0020739980290210

[11] W. Szwarc, “Instant Transportation Solutions,” Naval Research Logistics Quarterly, Vol. 22, No. 3, 1975, pp. 427-440. doi:10.1002/nav.3800220303

[12] J. R. Evans, “The Factored Transportation Problem,” Management Science, Vol. 30, No. 8, 1984, pp. 1021-1025. doi:10.1287/mnsc.30.8.1021

[13] D. S. Hochbaum, R. Shamir and J. G. Shanthikumar, “A Polynomial Algorithm for an Integer Quadratic NonSeparable Transportation Problem,” Mathematical Programming, Vol. 55, No. 1-3, 1992, pp. 359-371.

[14] N. Megiddo and A. Tamir, “Linear Time Algorithms for Some Separable Quadratic Programming Problems,” Operations Research Letters, Vol. 13, No. 4, 1993, pp. 203-211. doi:10.1016/0167-6377(93)90041-E

[15] S. Cosares and D. S. Hochbaum, “Strongly Polynomial Algorithms for the Quadratic Transportation Problems with a Fixed Number of Sources,” Mathematics of Operations Research, Vol. 19, No. 1, 1994, pp. 94-111. doi:10.1287/moor.19.1.94

[16] M. B. Eduardo, S. J. D. Francisco and J. R. Real, “Adapting Productivity Theory to the Quadratic Cost Function, An application to the Spanish electric sector,” Journal of Productivity Analysis, Vol. 20, No. 2, 2003, pp. 233-249.

[17] E. F. Wanner, F. G. Guimaraes, R. H. C. Takahashi and P. J. Fleming, “Local Search with Quadratic Approximations into Memetic Algorithms for Optimization with Multiple Criteria,” Evolutionary Computation, Vol. 16, No. 2, 2008, pp. 185-224. doi:10.1162/evco.2008.16.2.185

[18] Z. Lu, R. D. C. Monteiro and J. W. O’Neal, “An Iterative Solver-Based Long-Step Infeasible Primal-Dual PathFollowing Algorithm for Convex QP Based on a Class of Preconditioners,” Optimization Methods & Software, Vol. 24, No. 1, 2009, pp. 123-143. doi:10.1080/10556780802414049

[1] V. Adlakha and K. Kowalski, “An Alternative Solution Algorithm for Certain Transportation Problems,” International Journal of Mathematical Education in Science and Technology, Vol. 30, No. 5, 1999, pp. 719-728. doi:10.1080/002073999287716

[2] H. Arsham, “Postoptimality Analysis of the Transportation Problem,” JORS: Journal of the Operational Research Society, Vol. 43, No. 2, 1992, pp. 121-139.

[3] S. K. Goyal, “Improving VAM for Unbalanced Problems,” JORS, Journal of the Operational Research Society, Vol. 35, No. 12, 1984, pp. 1113-1114.

[4] J. Intrator and W. Szwarc, “An Inductive Property of Transportation Problem,” Asia-Pacific Journal of Operational Research Society, Vol. 5, 1988, pp. 79-83.

[5] M. A. Hakim, “An Alternative Method to Find Initial Basic Feasible Solution of a Transportation Problem,” Annals of Pure and Applied Mathematics, Vol. 1, No. 2, 2012, pp. 203-209.

[6] A. Shafaat and S. K. Goyal, “Resolution of Degeneracy in Transportation Problems,” Journal of the Operational Research Society, Vol. 39, No. 4, 1988, pp. 411-413.

[7] A. Sultan, “Heuristic for Finding an Initial B. F. S. in a Transportation Problem,” Opsearch, Vol. 25, 1988, pp. 197-199.

[8] C. E. Wilsdon, “A Simple, Easily Programmed Method for Locating Rook’s Tours in the Transportation Problem,” Journal of the Operational Research Society, Vol. 41, No. 9, 1990, pp. 879-880.

[9] S. Korukoglu and S. Balli, “An Improved Vogel’s Approximation Method for the Transportation Problem,” Mathematical and Computational Applications, Vol. 16, No. 2, 2011, pp. 370-381.

[10] V. Adlakha and H. Arsham, “Simplifying Teaching the Transportation Problem,” International Journal of Mathematical Education in Science and Technology, Vol. 29, No. 2, 1998, pp. 271-285. doi:10.1080/0020739980290210

[11] W. Szwarc, “Instant Transportation Solutions,” Naval Research Logistics Quarterly, Vol. 22, No. 3, 1975, pp. 427-440. doi:10.1002/nav.3800220303

[12] J. R. Evans, “The Factored Transportation Problem,” Management Science, Vol. 30, No. 8, 1984, pp. 1021-1025. doi:10.1287/mnsc.30.8.1021

[13] D. S. Hochbaum, R. Shamir and J. G. Shanthikumar, “A Polynomial Algorithm for an Integer Quadratic NonSeparable Transportation Problem,” Mathematical Programming, Vol. 55, No. 1-3, 1992, pp. 359-371.

[14] N. Megiddo and A. Tamir, “Linear Time Algorithms for Some Separable Quadratic Programming Problems,” Operations Research Letters, Vol. 13, No. 4, 1993, pp. 203-211. doi:10.1016/0167-6377(93)90041-E

[15] S. Cosares and D. S. Hochbaum, “Strongly Polynomial Algorithms for the Quadratic Transportation Problems with a Fixed Number of Sources,” Mathematics of Operations Research, Vol. 19, No. 1, 1994, pp. 94-111. doi:10.1287/moor.19.1.94

[16] M. B. Eduardo, S. J. D. Francisco and J. R. Real, “Adapting Productivity Theory to the Quadratic Cost Function, An application to the Spanish electric sector,” Journal of Productivity Analysis, Vol. 20, No. 2, 2003, pp. 233-249.

[17] E. F. Wanner, F. G. Guimaraes, R. H. C. Takahashi and P. J. Fleming, “Local Search with Quadratic Approximations into Memetic Algorithms for Optimization with Multiple Criteria,” Evolutionary Computation, Vol. 16, No. 2, 2008, pp. 185-224. doi:10.1162/evco.2008.16.2.185

[18] Z. Lu, R. D. C. Monteiro and J. W. O’Neal, “An Iterative Solver-Based Long-Step Infeasible Primal-Dual PathFollowing Algorithm for Convex QP Based on a Class of Preconditioners,” Optimization Methods & Software, Vol. 24, No. 1, 2009, pp. 123-143. doi:10.1080/10556780802414049