Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma

YAKICI AYAN, Tuba

Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma

Tuba YAKICI AYAN (Karadeniz Teknik Üniversitesi, İktisadi ve İdari Bilimler Fakültesi, Ekonometri Bölümü, Trabzon, Türkiye)

Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi

3 0

Yıl: 2008 Cilt: 10 Sayı: 1 Sayfa Aralığı: 97 - 116 Metin Dili: Türkçe İndeks Tarihi: 29-07-2022

Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma

Öz:

Bu makalede klasik ulaştırma probleminin (UP) bir uzantısı olan sabit maliyetli ulaştırma problemini (SMUP) çözmek için bir genetik algoritma (GA) sunulmaktadır. SMUP nin temel özelliği, taşınan miktara orantılı bir değişken maliyetin yanı sıra taşınan miktardan bağımsız bir sabit maliyetin de söz konusu olmasıdır. Matematiksel formülasyonu bir tamsayılı programlama problemi olmakla birlikte amaç fonksiyonundaki kesikli yapı nedeni ile problemin bilinen optimizasyon algoritmaları ile çözülmesi mümkün değildir. Doğal seleksiyona dayanan bir evrimsel süreç olarak GA, SMUP nin çözümünde son derece etkin bir araçtır. Bu çalışmada önerilen GA için başlangıç kitlesinin oluşturulması, çaprazlama ve tamir süreçlerine dair algoritma parçaları açıklandıktan sonra DELPHI de kodlanmakta ve bir örnek problem çözülerek işlerliği ve etkinliği ortaya konulmaktadır.

Anahtar Kelime:

Konular: İşletme İktisat

A Genetic Algorithm for Fixed Charge Transportation Problem

Öz:

In this paper, a genetic algorithm (GA) for fixed charge transportation problem (FCTP) which is an extension of classical transportation problem (TP) is presented. In FCTP, a fixed cost is incurred, independent of the amount transported, along with a variable cost that is proportional to the amount shipped .The mathematical formulation of the problem indicates that the model is an integer linear programming problem but that cost structure results in the objective function being a step function. Therefore FCTP can not been solved by known optimization algorithms. GA is an efficient procedure that finds solution to FCTP by an evolutionary process based on natural selection. In order to solve the problem, a GA with initial population, crossover and repair sub algorithm is presented. The proposed algorithm is coded with DELPHI language and illustrated with a numerical example. Numerical experimental results show that the proposed algorithm is efficient for solving FCTP.

Anahtar Kelime:

Konular: İşletme İktisat

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

ABD EL-WAHED, W F. and LEE, S M., (2006), “Interactive Fuzzy Goal Programming for Multi-Objective Transportation Problems”, Omega-The International Journal of Management Science, Vol. 34, No: 2, pp. 158-166.
ADLAKHA, V. and KOWALSKI, K., (2003), “A Simple Heuristic for Solving Small Fixed-Charge Transportation Problems”, Omega-The International Journal of Management Science, Vol. 31, pp. 205-211.
ADLAKHA, V.; KOWALSKI, K.; VEMUGANTI, R.R. and LEV, B., (2007), “More-for-Less Algorithm for Fixed-Charge Transportation Problems”, Omega-The International Journal of Management Science, Vol. 35, pp. 116-127.
BALINSKI, Michel, L., (1961), “Fixed Cost Transportation Problems”, Naval Research Logistic Quarterly, Vol. 8, No: 1, pp. 41-54.
BARR, R.S.; GLOVER, R.S. and KLINGMAN, D., (1981), “A New Optimization Method for Large Scale Fixed Charge Transportation Problems”, Operations Research, Vol. 29, No: 3, pp. 448-463.
CHIEN, William, T., (1993), “Determining Profit-Maximizing Production/Shipping Policies in a one to one Direct Shipping Stochastic Environment”, European Journal of Operational Research, Vol. 64, pp. 83-102.
COOPER, L. and DREBES, C., (1967), “An Approximate Algorithm for the Fixed Charge Problem”, Naval Research Logistic Quarterly, Vol. 14, pp. 101-113.
COOPER, Leon, (1975), “The Fixed Charge Problem-I: A New Heuristic Method”, Computers &Mathematics with Applications, Vol. 1, pp. 89-95.
DIABY, Moustapha, (1991), “Successive Linear Approximation Procedure for Generalized Fixed-Charge Transportation Problems”, Journal of Operational Research Society, Vol. 42, pp. 991-1001.
DORNDORF, U.; DREXL, A.; NIKULIN, Y. and PESCH, E., (2007), “Flight Gate Scheduling: State-of-the-art and Recent Developments”, Omega-The International Journal of Management Science, Vol. 35, No: 3, pp. 326-334.
DRENZLER, D.R., (1969), “An Approximate Method for the Fixed Charge Problem”, Naval Research Logistic Quarterly, Vol. 16, pp. 411-416.
GEN, M. and CHENG, R., (2000), Genetic Algorithms and Engineering Optimization, New York, John Wiley &Sons, pp. 512.
GEN, M. and SYARIF, A., (2003), Multi-Stage Chain Network by Hybrid Genetic Algorithms with Fuzzy Logic Controller, Fuzzy Sets Based Heuristics for Optimization, New York, Springer Verlag , pp. 181-196.
GOLDBERG, David,.E., (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Massachusetts., Addison Wesley Publishing,.pp. 412
GOTTLIEB, J. and PAULMANN, L., (1998), “Genetic Algorithms for the Fixed Charge Transportation Problem”, In Proceedings of IEEE International Conference on Evolutionary Computation, , pp. 330-335, Anchorage, USA.
GRAY, Paul, (1971), “Exact Solutions of the Fixed Charge Transportation Problem”, Operations Research, Vol. 19, pp. 1529-1538.
GREFENSTETTE, John, (1986), “Optimization of Control Parameters for Genetic Algorithms”, IEEE Transactions on Systems, Man, Cybernetics, Vol. 16, pp. 122-128.
Hirsch, W. M. and DANTZIG, G. B., (1968), “The Fixed Charge Problem”, Naval Research Logistic Quarterly, Vol. 15, pp. 413-424.
HITCHCOCK, Frenk L., (1941), “The Distribution of a Product from Several Sources to Numerous Localities”, Journal of Mathematical Physic, Vol. 20, pp. 224-230.
HOLLAND, John. H., (1992), Adaptation in Natural and Artificial Systems, USA, MIT Press, p. 211.
IDA, K.; TOHYAMA, H.; TERAMATSU, C. And FUTATANI, Y., (2004), “A Genetic Algorithm for Fixed Charge Transportation Problem”, Proceedings of the fifth Asia-Pacific Industrial Engineering Management Systems, Vol. 5, pp.3211-3215., Australia.
JIMENEZ, F. and VERDEGAY, J. L., (1996), “Interval Multiobjective Solid Transportation Problems via Genetic Algorithms”, Proceedings of Information Processing and Management of Uncertainty in Knowledge-Based Systems, pp-787-792, Granada, Spain.
KENNINGTON, J. L. and UNGER, V. E., (1976), “A New Branch and Bound Algorithm fort he Fixed Charge Transportation Problem”, Management Science, Vol. 22, No: 10, pp. 1116-1126.
KOWALSKI, Krzysztof, (2005), “On the Structure of the Fixed Charge Transportation Problem”, International Journal of Mathematical Education in Science and Technology”, Vol. 36, No: 8, pp. 879-888.
KOWALSKI, K and LEV, B., (2007), “New Approach to Fixed Charge Problems”, International Journal of Management Science and Engineering Management, Vol. 2, No: 1, pp. 75-80.
KUHN, H.W. and BAUMOL, W.J., (1962), “An Approximation Algorithm for the Fixed Charge Transportation Problem”, Naval Research Logistic Quarterly, Vol. 9, pp. 1-15
KUO, C. and GILLIAN, M. N., (2007), “A Mathematical Modelling Approach to Improving Locomotive Utilization at a Freight Railroad”, Omega- The International Journal of Management Science, Vol. 35, No: 5, pp. 472-485.
LI, Y.; GEN, M. and IDA, K., (1998), “Genetic Algorithms for the Fixed Charge Transportation Problem”, Beijing Mathematics, Vol. 4, No: 2, pp. 239-249.
MICHALEWICZ, Z.; VIGNAUX, G. A. and HOBBS, M., (1991), “A Nonstandard Genetic Algorithm for the Nonlinear Transportation Problem” Orsa- Journal on Computing, Vol. 3, No: 4, pp. 307-316.
MICHALEWICZ, Zbigniew, (1993), “A Hierarchy of Evolution Programs” Evolutionary Computation, Vol. 1, No: 1, pp. 51-76.
MICHALEWICZ, Zbigniew, (1996), Genetic Algorithms+Data Structures = Evolution Program, New York, Springer Verlag , pp. 387.
MİZUNUMA, H. and WATADA, J., (1995), “Fuzzy mixed integer programming based on genetic algorithm and its application to resource distribution", Japanese Journal of Fuzzy Theory and Systems, Vol. 7 No: 1, pp.97-116.
MURTY, Katta, G., (1968), “Solving the Fixed Charge Problem by Ranking the Extreme Points”, Operations Research, Vol. 16, pp. 268-279.
PALEKAR, U. S.; KARWAN, M. H. and ZIONTS, S. A., (1990), “A branch-and bound Method for the Fixed Charge Transportation Problem”, Management Science, Vol. 36, pp. 1092-1105.
SADAGOPAN, S. And RAVINDRAN, A. (1982), “A Vertex Ranking Algorithm for the Fixed-Charge Transportation Problem”, Journal of Operational Theory and Application, Vol. 37, pp. 221-230.
SAKAWA, Masatoshi, (2002), Genetic Algorithms and Fuzzy Multiobjective Optimization”, Boston, Kluwer Academic Publishers, pp. 304.
SANDROCK, Keith, (1988), “A Simple Algorithm for Solving Small Fixed Charge Transportation Problems”, Journal of Operational Research Society, Vol. 39, No: 5, pp. 467-475.
SPEARS, W. M. and De JONG, K. A., “On the Virtues of Parameterized Uniform Crossover”, Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230-236, La Jolla ,CA, USA.
STEINBERG, David, I., (1970), “The Fixed Charge Problem”, Naval Research Logistic Quarterly, Vol. 17, pp. 217-235.
SUN, M.; ARONSON, J. E.; McKEOWN, P. G. and DRINKA, D., (1998), “A Tabu Search Heuristic Procedure for the Fixed Charge Transportation Problem”, European Journal of Operational Research, Vol. 106, pp. 441-456.
SYARIF, A. and GEN, M., (2003), “Solving Exclusionary Side Constraint Transportation Problem by Using a Hybrid Spanning Tree-based Genetic Algorithm”, International Journal of Intelligent Manufacturing, Vol. 14, pp. 389-399.
VİGNAUX, G.A. and MİCHALEWİCZ, Z., (1991), “A genetic algorithm for the linear transportation problem”, IEEE Transactions on Systems, Man and Cybernetics, Vol. 21, pp.445-452.
WALKER, Warren, .E., (1976), “A Heuristic Adjacent Extreme Point Algorithm for the Fixed Charge Problem”, Management Science, Vol. 22, pp. 587-596.

APA	YAKICI AYAN T (2008). Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. , 97 - 116.
Chicago	YAKICI AYAN Tuba Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. (2008): 97 - 116.
MLA	YAKICI AYAN Tuba Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. , 2008, ss.97 - 116.
AMA	YAKICI AYAN T Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. . 2008; 97 - 116.
Vancouver	YAKICI AYAN T Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. . 2008; 97 - 116.
IEEE	YAKICI AYAN T "Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma." , ss.97 - 116, 2008.
ISNAD	YAKICI AYAN, Tuba. "Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma". (2008), 97-116.

APA	YAKICI AYAN T (2008). Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 10(1), 97 - 116.
Chicago	YAKICI AYAN Tuba Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi 10, no.1 (2008): 97 - 116.
MLA	YAKICI AYAN Tuba Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, vol.10, no.1, 2008, ss.97 - 116.
AMA	YAKICI AYAN T Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi. 2008; 10(1): 97 - 116.
Vancouver	YAKICI AYAN T Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma. Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi. 2008; 10(1): 97 - 116.
IEEE	YAKICI AYAN T "Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma." Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 10, ss.97 - 116, 2008.
ISNAD	YAKICI AYAN, Tuba. "Sabit Maliyetli Ulaştırma Problemi İçin Bir Genetik Algoritma". Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi 10/1 (2008), 97-116.