Combinatorial optimization-Typical problem-Secondary allocation problem

Typical problem and execution method

Secondary allocation problem

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.

Execution method

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

data

Supplement

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

Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-typical problems and execution methods