订单拣选问题¶

类别： 路径优化

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

订单拣选问题 描述如下：需要拣选一组订单。拣货员从初始位置出发，拣取订单后返回初始位置卸货。我们考虑一个普通的矩形仓库，其中有一个用于卸货的单一仓库起点。该仓库起点也作为拣货员的初始位置。需要拣取的订单位于垂直通道的两侧，两侧均可到达。垂直通道由水平横向通道环绕，拣货员可通过水平横向通道在仓库内移动。拣货员可以纵向和横向移动。任意两个订单之间的距离使用曼哈顿距离计算。问题的目标是找到使完成订单所需距离（或时间）最小的拣选顺序。

建模要点¶

添加一个 list 决策变量来建模拣选顺序
定义一个 lambda 函数来计算行驶距离
获取 list 变量的值

数据¶

我们提供的订单拣选问题实例来自 Theys et al. 基准。数据文件的格式如下：

第一行：订单数量
接下来若干行：任意两个订单（包括索引 0 处的初始位置）之间的距离矩阵。

建模思路¶

在订单拣选问题的 OptAgent 模型中，我们使用一个 list 决策变量表示拣选顺序。我们也将初始点视为一个待拣选订单。对 list 大小的约束确保所有订单都被拣取。

目标是最小化拣取所有订单所需的距离。为了计算该距离，我们使用一个 lambda 函数返回从一个订单到下一个订单的距离。我们通过对该 lambda 函数在所有订单位置上的求和来计算目标值。

由于拣货员的行驶路径是一个回路，因此不需要将 list 中的第一个元素约束为初始点。这可以在求解后的后处理阶段完成。为此，我们在模型声明中使用 index 算子来恢复 list 中元素 0 的位置。然后我们可以将拣选顺序保存到文件中，从初始点开始。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve


def read_elem(filename):
    return Path(filename).read_text(encoding="utf-8").split()


def read_instance(filename):
    file_iterator = iter(read_elem(filename))
    nb_orders = int(next(file_iterator)) + 1
    distances_data = [
        [int(next(file_iterator)) for _ in range(nb_orders)]
        for _ in range(nb_orders)
    ]
    return nb_orders, distances_data


def main(input_file, output_file=None, time_limit=10):
    nb_orders, distances_data = read_instance(input_file)
    model = OptModel()

    # A full-length list models the permutation of all orders, including node 0.
    picking_list = model.list(nb_orders)
    model.constraint(model.count(picking_list) == nb_orders)

    distances_matrix = model.array(distances_data)
    distance_to_next_order = model.lambda_function(
        lambda position: distances_matrix[
            picking_list[position // 1], picking_list[(position + 1) // 1]
        ]
    )
    objective = model.sum(
        model.range(0, nb_orders - 1), distance_to_next_order
    ) + distances_matrix[
        picking_list[(nb_orders - 1) // 1], picking_list[0]
    ]
    index_initial_position = model.index(picking_list, 0)
    model.minimize(objective)

    solution = solve(model, time_limit_s=float(time_limit))
    order = list(picking_list.value)
    start = index_initial_position.value
    cyclic_order = [
        order[(start + offset) % nb_orders] for offset in range(nb_orders)
    ]
    result_text = f"Total distance = {objective.value}\nOrder: {' '.join(map(str, cyclic_order))}"
    print(result_text)
    if output_file is not None:
        Path(output_file).write_text(
            f"{objective.value}\n{' '.join(map(str, cyclic_order))}\n",
            encoding="utf-8",
        )
    return solution

本地运行¶

在 notebook 所在目录执行以下 cell，即可调用一个小型订单拣选实例。

from pathlib import Path

INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)

solution_order_picking = main(
    INSTANCE_DIR / "Instance_5_3_15_Random_Central_0.txt",
    time_limit=1,
)