Typical problem and execution method
Consider the allocation destination $ L = \ {L_1, L_2, \ dots, L_n \} $ of the object $ P = \ {P_1, P_2, \ dots, P_n \} $. Given the transport volume $ q_ {ij} $ between the object $ P_i $ and $ P_j $ and the distance $ d_ {kl} $ between the allocation destinations $ L_k $ and $ L_l $, the transport volume and Find the allocation that minimizes the sum of the products of distances.
usage
Signature: quad_assign(quant, dist)
Docstring:
Secondary allocation problem
Full search
input
quant:Transport volume between targets
dist:Distance between allottees
output
List of allocation destination numbers for each target
python
from ortoolpy import quad_assign
quad_assign([[0, 2, 0], [0, 0, 1], [0, 0, 0]], [[0, 2, 4], [2, 0, 3], [4, 3, 0]])
result
(0, 1, 2)
python
# pandas.DataFrame
from ortoolpy.optimization import QuadAssign
QuadAssign('data/quad_assign_quant.csv', 'data/quad_assign_dist.csv')[1]
| target | pos | |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
You can think of various issues, such as the Traveling Salesman Problem (TSP), as secondary assignment issues. The secondary allocation problem is a highly abstract problem. However, it is a very difficult problem to solve. It is useful to reduce to the secondary allocation problem to understand the structure of the problem, but it is not recommended to solve it as it is. It should be solved by reconsidering it as a more specific problem. For example, for TSP, it would be more efficient to use a TSP-specific solution.
Recommended Posts