Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
A Probabilistic Hill-Climbing Algorithm for the Single-Source Transportation Problem
This paper proposes a probabilistic hill-climbing algorithm, called PH, for the single-source transportation problem (STP). PH is a tree search algorithm in which each node contains an assignment problem (AP) transformed from the STP being solved. The transformation converts each source’s product units into product lots; a product lot equals multiple product units. The AP aims to find the optimal assignment of product lots to destinations to minimize the total assignment cost. PH uses the Hungarian method to find the optimal solution of the AP in every node, which is a solution of the STP. For the AP of the root node (as the initial current node), the number of each source’s product lots is set to be small enough to guarantee the generation of a feasible solution for the STP. To generate every subsequent level, the current node is branched into multiple child nodes, in which the number of child nodes equals the number of sources in the STP. The AP of each child node is modified from the AP of the current node by adding one more product lot into a specific different source. Consequently, each child node provides a solution that is better than or the same as the current node’s solution; however, some child nodes’ solutions may be infeasible for the STP due to the insufficiency of a source’s capacity. If all of the child nodes cannot find a better feasible solution than the current node’s solution, PH stops its procedure. To diversify the search, PH selects one of the child nodes as the new current node in a probabilistic way, instead of always selecting the best child node. The experiment’s results in this paper reveal the performance of the three variants of PH.
A Probabilistic Hill-Climbing Algorithm for the Single-Source Transportation Problem
This paper proposes a probabilistic hill-climbing algorithm, called PH, for the single-source transportation problem (STP). PH is a tree search algorithm in which each node contains an assignment problem (AP) transformed from the STP being solved. The transformation converts each source’s product units into product lots; a product lot equals multiple product units. The AP aims to find the optimal assignment of product lots to destinations to minimize the total assignment cost. PH uses the Hungarian method to find the optimal solution of the AP in every node, which is a solution of the STP. For the AP of the root node (as the initial current node), the number of each source’s product lots is set to be small enough to guarantee the generation of a feasible solution for the STP. To generate every subsequent level, the current node is branched into multiple child nodes, in which the number of child nodes equals the number of sources in the STP. The AP of each child node is modified from the AP of the current node by adding one more product lot into a specific different source. Consequently, each child node provides a solution that is better than or the same as the current node’s solution; however, some child nodes’ solutions may be infeasible for the STP due to the insufficiency of a source’s capacity. If all of the child nodes cannot find a better feasible solution than the current node’s solution, PH stops its procedure. To diversify the search, PH selects one of the child nodes as the new current node in a probabilistic way, instead of always selecting the best child node. The experiment’s results in this paper reveal the performance of the three variants of PH.
A Probabilistic Hill-Climbing Algorithm for the Single-Source Transportation Problem
Pisut Pongchairerks (Autor:in)
2023
Aufsatz (Zeitschrift)
Elektronische Ressource
Unbekannt
Metadata by DOAJ is licensed under CC BY-SA 1.0
Developing Combined Genetic Algorithm-Hill-Climbing Optimization Method for Area Traffic Control
| Online Contents | 2006
Automatic climbing device for stable climbing transportation of vertical rod
| Europäisches Patentamt | 2024
Comparison of methods for determining hill climbing ability of trucks
| Engineering Index Backfile | 1939