如何用GRASP求解协作装配线双目标优化问题

需求说明 #

采用元启发式算法中的**GRASP（贪婪随机自适应搜索过程）**方法，对协作装配线进行双目标优化建模，核心优化目标为：

• 最小化人工与工位综合成本
• 最小化机器人能耗

已通过ε约束法得到帕累托前沿，明确成本与能耗的权衡关系，现需基于GRASP算法求解更优解，代码需实现26项初始任务的分配逻辑：

• 为任务分配操作主体（人工/机器人）
• 为任务分配操作模式（单独、协作、并行），模式差异会改变操作速度，进而影响加工时间

核心代码实现 #

1. 贪婪随机构造阶段 #

该函数按照给定任务顺序，通过构建受限候选列表（RCL），随机选择任务分配方式（加入当前工位/新建工位）及操作模式，生成初始可行解。

import random
from typing import Dict, List, Tuple

def greedy_random_construction(data: Dict, order: List[int], alpha: float, w_energy: float) -> List[List[Tuple[int, int]]]:
    # 工位列表：每个工位是(task_id, mode_id)的列表
    station_tasks: List[List[Tuple[int, int]]] = []
    # 当前工位的状态信息：是否有人工、是否有机器人、当前工位负载（加工时间总和）
    current_station = []  # 当前工位的任务列表
    current_human = False
    current_robot = False
    current_load = 0.0

    for j in order:
        candidates = []  # 候选方案：(目标值, 是否加入当前工位, 操作模式)
        # 评估当前任务在每种模式下的分配选项
        for m in data['M']:
            t = data['t_jm'][(j, m)]  # 当前任务在该模式下的加工时间
            e = data['E_jm'][(j, m)]  # 当前任务在该模式下的机器人能耗
            h, r = mode_flags(m)      # 该模式对应的操作主体标识（是否需要人工/机器人）

            # 选项1：若当前工位存在且负载允许，将任务加入当前工位
            if current_station and current_load + t <= data['T']:
                cost_incr = 0.0
                # 若当前工位无人工但模式需要，增加人工成本
                if h and not current_human:
                    cost_incr += data['C_w']
                # 若当前工位无机器人但模式需要，增加机器人成本
                if r and not current_robot:
                    cost_incr += data['C_c']
                energy_incr = e
                # 计算加权后的目标增量
                obj = cost_incr + w_energy * energy_incr
                candidates.append((obj, True, m))

            # 选项2：新建工位（始终可行）
            # 新建工位需承担工位固定成本，加上模式所需的人工/机器人成本
            cost_incr_new = data['C_s']
            if h:
                cost_incr_new += data['C_w']
            if r:
                cost_incr_new += data['C_c']
            energy_incr_new = e
            obj_new = cost_incr_new + w_energy * energy_incr_new
            candidates.append((obj_new, False, m))

        # 构建受限候选列表（RCL）并随机选择
        objs = [cand[0] for cand in candidates]
        min_obj = min(objs)
        max_obj = max(objs)
        # 计算RCL阈值：alpha控制随机性，0为纯贪婪，1为纯随机
        threshold = min_obj + alpha * (max_obj - min_obj)
        rcl = [cand for cand in candidates if cand[0] <= threshold + 1e-12]
        chosen_obj, use_current, chosen_m = random.choice(rcl)

        # 根据选择结果分配任务
        t = data['t_jm'][(j, chosen_m)]
        e = data['E_jm'][(j, chosen_m)]
        h, r = mode_flags(chosen_m)
        if use_current and current_station and current_load + t <= data['T']:
            # 将任务加入当前工位
            current_station.append((j, chosen_m))
            current_human = current_human or h
            current_robot = current_robot or r
            current_load += t
        else:
            # 若当前工位存在，先将其加入工位列表
            if current_station:
                station_tasks.append(current_station)
            # 新建工位并分配当前任务
            current_station = [(j, chosen_m)]
            current_human = h
            current_robot = r
            current_load = t
    # 将最后一个工位加入列表
    if current_station:
        station_tasks.append(current_station)
        
    return station_tasks

2. 局部搜索阶段 #

该函数对初始解进行邻域搜索，通过修改任务的操作模式寻找更优解，直到无法改进或达到最大迭代次数。

def local_search(station_tasks: List[List[Tuple[int, int]]], data: Dict, w_energy: float, max_iter: int = 1) -> List[List[Tuple[int, int]]]:
    # 复制初始解作为当前解
    solution = [list(station) for station in station_tasks]

    # 计算当前解的成本、能耗及加权目标值
    current_cost, current_energy = evaluate_solution(solution, data)
    current_obj = current_cost + w_energy * current_energy

    for _ in range(max_iter):
        improved = False
        # 遍历所有工位及工位内的任务
        for si, station in enumerate(solution):
            # 预计算当前工位的总负载、是否有人工、是否有机器人
            station_load = sum(data['t_jm'][(j, m)] for j, m in station) 
            station_human = any(mode_flags(m)[0] for _, m in station)
            station_robot = any(mode_flags(m)[1] for _, m in station)

            for ti, (j, m) in enumerate(station):
                # 尝试所有替代操作模式
                for m2 in data['M']:
                    if m2 == m:
                        continue
                    
                    # 计算模式修改后的工位负载，若超过工位容量则跳过
                    t_old = data['t_jm'][(j, m)]
                    t_new = data['t_jm'][(j, m2)]
                    if station_load - t_old + t_new > data['T'] + 1e-9:
                        continue  # 超过工位时间容量，不可行

                    # 计算模式修改前后的操作主体标识
                    h_old, r_old = mode_flags(m)
                    h_new, r_new = mode_flags(m2)
                    # 更新工位的操作主体标识
                    new_human = station_human
                    new_robot = station_robot
                    # 若原模式是工位唯一需要人工的模式，则更新为新模式的人工需求
                    if h_old and not any((mode_flags(mk)[0] for k, (jk, mk) in enumerate(station) if k != ti)):
                        new_human = h_new
                    else:
                        new_human = new_human or h_new
                    # 同理更新机器人需求
                    if r_old and not any((mode_flags(mk)[1] for k, (jk, mk) in enumerate(station) if k != ti)):
                        new_robot = r_new
                    else:
                        new_robot = new_robot or r_new

                    # 生成修改后的解并评估
                    new_solution = [list(st) for st in solution]
                    new_solution[si][ti] = (j, m2)
                    new_cost, new_energy = evaluate_solution(new_solution, data)
                    new_obj = new_cost + w_energy * new_energy
                    # 若新解更优，则接受该修改
                    if new_obj + 1e-9 < current_obj:
                        solution = new_solution
                        current_obj = new_obj
                        current_cost = new_cost
                        current_energy = new_energy
                        improved = True
                        break
                        
                if improved:
                    break
            if improved:
                break
        # 若当前迭代无改进，提前终止
        if not improved:
            break
    return solution

依赖函数说明 #

• mode_flags(m)：输入操作模式ID，返回该模式是否需要人工、是否需要机器人的布尔值元组
• evaluate_solution(solution, data)：输入解（工位-任务分配列表），返回该解对应的总成本、总能耗

内容的提问来源于stack exchange，提问作者Hind Bhr