Accès ouvert

A greedy algorithm for assignment and transportation problems

Article scientifique 2022 Anglais

Résumé

Abstract The transportation and the assignment problems have both been frequently investigated in the field of operations research. For a couple of decades, it has been proven that no greedy algorithm can yield an optimal solution to these problems since their respective underlying structures are not matroids. It is shown in this paper that, even though seeking a greedy algorithm to solve one of the aforesaid problems is fanciful, a heuristic method capable of providing good approximations to the optimal solution can be found. The so-called “hybrid greedy algorithm” is a hybridization of the Balas-Hammer and the Hungarian methods. It can be used to solve both the transportation and the assignment problems. It often provides an optimal solution to small assignment problems and it outperforms the Balas-Hammer (Vogel’s approximation method) and other heuristic methods for solving the transportation problem.JEL Classification: C02 , C61 , C63 MSC Classification: 00A72 , 03D15 , 68Q25 , 68U20 , 68W40 , 90C27

Citer ce document

Ngoie, R., Sakulu, J., Yamba, L., Nsuadi, G., Bonkile, F., Linguma, D., Ulungu, B. (2022). A greedy algorithm for assignment and transportation problems. https://doi.org/10.21203/rs.3.rs-1968435/v1

Accès au document

Voir sur le dépôt source

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Ruffin-Benoît M. Ngoie Jean-Aimé B. Sakulu Lebeau Yamba Glodi Nsuadi Fabrice Bonkile Damos Linguma Berthold E.-L. Ulungu

Statistiques

Consultations : 1

Téléchargements : 0