运输的分支定界算法

Question

我正在尝试应用 B&B 算法来解决交通问题，但结果我收到“找不到可行的解决方案”，我无法理解为什么会发生这种情况。正确答案是210。

在输出中，我需要接收最优解、节点数以及迭代和运输流的分配。

预先感谢您的帮助。

import numpy as np
import heapq

# Node class to represent each branch in the tree
class Node:
    def __init__(self, level, cost, assignment, supply_left, demand_left):
        self.level = level  # depth of node (number of assignments made)
        self.cost = cost  # current cost
        self.assignment = assignment  # current assignment
        self.supply_left = supply_left  # remaining supply for each supply point
        self.demand_left = demand_left  # remaining demand for each demand point
    
    def __lt__(self, other):
        return self.cost < other.cost  # for priority queue comparison

# Cost calculation function (objective function)
def calculate_cost(cost_matrix, assignment):
    total_cost = 0
    for supply_idx, demand_assignments in enumerate(assignment):
        for demand_idx, assigned_amount in enumerate(demand_assignments):
            if assigned_amount > 0:
                total_cost += cost_matrix[supply_idx, demand_idx] * assigned_amount
    return total_cost

# Branch and Bound Algorithm for transportation problem
def branch_and_bound(cost_matrix, supplies, demands):
    num_supplies, num_demands = cost_matrix.shape
    pq = []  # priority queue for branch and bound nodes
    root = Node(0, 0, [[0] * num_demands for _ in range(num_supplies)], supplies[:], demands[:])  # initial node
    heapq.heappush(pq, root)
    
    best_cost = float('inf')  # store the minimum cost
    best_assignment = None
    node_count = 0  # count number of nodes explored
    total_iterations = 0  # to track iterations (steps in the process)

    while pq:
        node = heapq.heappop(pq)  # get the node with the lowest cost
        node_count += 1
        total_iterations += 1  # count this as an iteration
        
        if node.level == num_supplies:  # All supply points have been processed
            # Check if all demands are met (i.e., no demand left unfulfilled)
            if node.cost < best_cost and all(d == 0 for d in node.demand_left):
                best_cost = node.cost
                best_assignment = node.assignment[:]
        else:
            # Explore all demands for the current supply
            for demand_idx in range(num_demands):
                if node.supply_left[node.level] > 0 and node.demand_left[demand_idx] > 0:
                    # Determine the amount to assign
                    assign_amount = min(node.supply_left[node.level], node.demand_left[demand_idx])
                    
                    # Create new assignment
                    new_assignment = [row[:] for row in node.assignment]
                    new_assignment[node.level][demand_idx] = assign_amount
                    
                    new_supply_left = node.supply_left[:]
                    new_supply_left[node.level] -= assign_amount
                    
                    new_demand_left = node.demand_left[:]
                    new_demand_left[demand_idx] -= assign_amount
                    
                    new_cost = calculate_cost(cost_matrix, new_assignment)
                    
                    # Only add the child node if it does not exceed the best cost found
                    if new_cost < best_cost:
                        child_node = Node(node.level + 1, new_cost, new_assignment, new_supply_left, new_demand_left)
                        heapq.heappush(pq, child_node)

    return best_assignment, best_cost, node_count, total_iterations

指定数据的使用示例：

supplies = [17, 8, 10, 9]   # supply capacities
demands = [6, 15, 7, 8, 8]  # demand requirements
cost_matrix = np.array([
    [10, 8, 5, 9, 16],    
    [4, 3, 4, 11, 12],    
    [5, 10, 29, 7, 6],    
    [9, 2, 4, 1, 3]
])

best_assignment, best_cost, nodes_explored, iterations = branch_and_bound(cost_matrix, supplies, demands)

if best_assignment is not None:
    print("Best Cost:", best_cost)
    print("Best Assignment:")
    for row in best_assignment:
        print(row)
else:
    print("No feasible solution found.")
    
print("Nodes Explored:", nodes_explored)
print("Iterations Made:", iterations) 

Answer 1

此代码仅进行

num_demands

迭代改进，每次迭代仅从一个供应中获取。然而，在这种情况下，为了获得完整的任务，某些需求需要从多个供应中提取，因此永远不会达到

all(d == 0 for d in node.demand_left)

条件。