Розробка евристики для вирішення загальної транспортної задачі

Autor: Elias Munapo
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Zdroj: Eastern-European Journal of Enterprise Technologies, Vol 6, Iss 4 (114), Pp 44-51 (2021)
Eastern-European Journal of Enterprise Technologies; Vol. 6 No. 4 (114) (2021): Mathematics and Cybernetics-applied aspects; 44-51
Eastern-European Journal of Enterprise Technologies; Том 6 № 4 (114) (2021): Математика и кибернетика-прикладные аспекты; 44-51
Eastern-European Journal of Enterprise Technologies; Том 6 № 4 (114) (2021): Математика та кібернетика-прикладні аспекти; 44-51
ISSN: 1729-4061
1729-3774
Popis: The transportation problem is well known and has very important applications. For this well-researched model, there are very efficient approaches for solving it that are available. These approaches include formulating the transportation problem as a linear program and then using the efficient methods such as the simplex method or interior point algorithms. The Hungarian method is another efficient method for solving both the assignment model and the general transportation model. An assignment problem is a special case of the transportation model in which all supply and demand points are 1. Every transportation problem can be converted into an assignment problem since rows and columns can be split so that each supply and each demand point is 1. The transportation simplex method is another method that is also used to solve the general transportation problem. This method is also called the modified distribution method (MODI). To use this approach, a starting solution is required and the closer the starting solution to the optimal solution, the fewer the iterations that are required to reach optimality. The fourth method for transportation models is the network simplex method, which is the fastest so far. Unfortunately, all these approaches for transportation models are serial in nature and are very difficult to parallelize, which makes it difficult to efficiently use the available massively parallel technology. There is a need for an efficient approach for the transportation problem, which is easily parallelizable. This paper presents a See-Saw approach for solving the general transportation problem. This is an extension of the See-Saw approach for solving the assignment problem. The See-Saw moves can be done independently, which makes the approach proposed in this paper more promising than the available methods for transportation models
Транспортная задача хорошо известна и широко применяется. Для этой хорошо изученной задачи существуют очень эффективные методы решения. Эти методы включают формулирование транспортной задачи в виде линейной программы с последующим использованием эффективных методов, таких как симплекс-метод или алгоритмы внутренних точек. Еще одним эффективным методом решения как задачи о назначениях, так и общей транспортной задачи является Венгерский метод. Задача о назначениях является частным случаем транспортной задачи, в которой все точки предложения и спроса равны 1. Каждую транспортную задачу можно преобразовать в задачу о назначениях, поскольку строки и столбцы можно разделить таким образом, чтобы каждая точка предложения и каждая точка спроса равнялись 1. Транспортный симплекс-метод является еще одним способом, который также используется для решения общей транспортной задачи. Этот метод также называется модифицированным методом распространения (МОДИ). Для использования этого подхода требуется исходное решение, и чем ближе исходное решение к оптимальному, тем меньше итераций требуется для достижения оптимальности. Четвертый метод решения транспортных задач – сетевой симплекс-метод, который на данный момент является самым быстрым. К сожалению, все эти методы решения транспортных задач носят последовательный характер и очень трудно поддаются распараллеливанию, что усложняет эффективное использование имеющейся технологии массового параллелизма. Необходим эффективный метод решения транспортной задачи, который легко поддается распараллеливанию. Для решения общей транспортной задачи в работе представлен метод качелей. Это расширение метода качелей для решения задачи о назначениях. Движения качелей могут выполняться независимо, что делает предложенный метод более перспективным, чем доступные методы решения транспортных задач
Транспортна задача добре відома і широко застосовується. Для цієї добре вивченої задачі існують дуже ефективні методи вирішення. Ці методи включають формулювання транспортної задачі у вигляді лінійної програми з подальшим використанням ефективних методів, таких як симплекс-метод або алгоритми внутрішніх точок. Ще одним ефективним методом вирішення як задачі про призначення, так і загальної транспортної задачі є Угорський метод. Задача про призначення є окремим випадком транспортної задачі, в якій всі точки пропозиції і попиту рівні 1. Кожну транспортну задачу можна перетворити на задачу про призначення, оскільки рядки і стовпці можна розділити таким чином, щоб кожна точка пропозиції і кожна точка попиту дорівнювали 1. Транспортний симплекс-метод – це ще один спосіб, що також використовується для вирішення загальної транспортної задачі. Цей метод також називається модифікованим методом розповсюдження (МОДИ). Для використання цього підходу потрібне вихідне рішення, і чим ближче вихідне рішення до оптимального, тим менше ітерацій потрібно для досягнення оптимальності. Четвертий метод вирішення транспортних задач – мережевий симплекс-метод, який на даний момент є найшвидшим. На жаль, всі ці методи вирішення транспортних задач носять послідовний характер і дуже важко піддаються розпаралелюванню, що ускладнює ефективне використання наявної технології масового паралелізму. Необхідний ефективний метод вирішення транспортної задачі, який легко піддається розпаралелюванню. Для вирішення загальної транспортної задачі в роботі представлений метод гойдалки. Це розширення методу гойдалки для вирішення задачі про призначення. Рухи гойдалки можуть виконуватися незалежно, що робить запропонований метод більш перспективним, ніж доступні методи вирішення транспортних задач
Databáze: OpenAIRE
Externí odkaz: