1.2.2

下载 Notebook 下载完整案例

拆分配送车辆路径问题 (SDVRP)¶

类别： 路径优化

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

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

问题描述¶

在拆分配送车辆路径问题 (SDVRP) 中，一组具有相同容量的配送车辆必须为对单一商品有已知需求的客户提供服务。车辆从同一个配送中心出发并最终返回该配送中心。每个客户可以由多辆车服务，且送达每个客户的货物总量必须大于或等于其需求量。每辆卡车运送的货物总量不得超过其载重能力。目标是为每辆卡车分配一条客户访问序列，使总行驶距离最小化。

学习要点¶

• 使用 OptAgent 的 list 决策变量表示各卡车的客户访问序列
• 使用 cover 约束确保每个客户至少被访问一次，同时允许拆分配送
• 将列表路线与浮点配送量变量结合，分别约束车辆容量和客户需求

数据¶

所提供的拆分配送车辆路径问题 (SDVRP) 实例来自 Belenguer 等人的基准测试，并遵循 DIMACS challenge 格式。数据文件的格式如下：

• 第一行：客户数量以及每辆卡车的载重能力
• 第二行：各客户的需求量
• 从第三行开始：依次为仓库的坐标以及各客户的坐标

建模思路¶

SDVRP 是 CVRP 的一种松弛形式：客户不必由同一辆卡车服务，货物可以拆分并由不同卡车运送。模型使用 cover 代替 partition，确保所有客户至少被访问一次，同时不限制访问同一客户的卡车数量。

每辆卡车使用一个列表变量表示访问顺序，并为每个客户建立一个浮点配送量变量。沿路线汇总的配送量不得超过卡车容量；各卡车对同一客户的有效配送量之和不得低于该客户的需求。路线距离包含相邻客户之间的距离以及非空路线从仓库出发和返回仓库的距离，目标是最小化所有路线的总距离。

Python 实现¶

import math
from pathlib import Path

from optagent import OptModel, solve


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


def read_input_sdvrp(filename):
    elements = iter(read_elements(filename))

    nb_customers = int(next(elements))
    capacity = int(next(elements))
    demands = [int(next(elements)) for _ in range(nb_customers)]

    depot_x = float(next(elements))
    depot_y = float(next(elements))
    customers_x = [None] * nb_customers
    customers_y = [None] * nb_customers
    for i in range(nb_customers):
        customers_x[i] = float(next(elements))
        customers_y[i] = float(next(elements))

    distance_matrix = compute_distance_matrix(customers_x, customers_y)
    distance_depots = compute_distance_depots(
        depot_x, depot_y, customers_x, customers_y
    )
    return nb_customers, capacity, distance_matrix, distance_depots, demands


def compute_dist(xi, xj, yi, yj):
    exact_dist = math.sqrt(math.pow(xi - xj, 2) + math.pow(yi - yj, 2))
    return int(math.floor(exact_dist + 0.5))


def compute_distance_matrix(customers_x, customers_y):
    nb_customers = len(customers_x)
    distance_matrix = [
        [None for _ in range(nb_customers)] for _ in range(nb_customers)
    ]
    for i in range(nb_customers):
        distance_matrix[i][i] = 0
        for j in range(i + 1, nb_customers):
            dist = compute_dist(
                customers_x[i],
                customers_x[j],
                customers_y[i],
                customers_y[j],
            )
            distance_matrix[i][j] = dist
            distance_matrix[j][i] = dist
    return distance_matrix


def compute_distance_depots(depot_x, depot_y, customers_x, customers_y):
    return [
        compute_dist(depot_x, customer_x, depot_y, customer_y)
        for customer_x, customer_y in zip(customers_x, customers_y)
    ]


def main(input_file, output_file=None, time_limit=20):
    (
        nb_customers,
        truck_capacity,
        dist_matrix_data,
        dist_depot_data,
        demands_data,
    ) = read_input_sdvrp(input_file)
    nb_trucks = nb_customers

    model = OptModel()

    # Sequence of customers visited by each truck.
    customers_sequences = [
        model.list(nb_customers)
        for k in range(nb_trucks)
    ]

    # Quantity carried by each truck for each customer.
    quantity = [
        [
            model.float(0, demands_data[i])
            for i in range(nb_customers)
        ]
        for k in range(nb_trucks)
    ]

    # Every customer must be visited by at least one truck.
    model.constraint(model.cover(customers_sequences))

    dist_matrix = model.array(dist_matrix_data)
    dist_depot = model.array(dist_depot_data)
    route_distances = []

    for k, sequence in enumerate(customers_sequences):
        count = model.count(sequence)

        quantity_array = model.array(quantity[k])
        quantity_lambda = model.lambda_function(
            lambda customer: quantity_array[customer]
        )
        route_quantity = model.sum(sequence, quantity_lambda)
        model.constraint(
            route_quantity <= truck_capacity
        )

        distance_lambda = model.lambda_function(
            lambda position: dist_matrix[
                sequence[position - 1], sequence[position]
            ]
        )
        route_distances.append(
            model.sum(model.range(1, count), distance_lambda)
            + model.iif(
                count > 0,
                dist_depot[sequence[0]]
                + dist_depot[sequence[count - 1]],
                0,
            )
        )

    # Each customer must receive at least its demand.
    for i in range(nb_customers):
        quantity_served = model.sum(
            quantity[k][i] * model.contains(customers_sequences[k], i)
            for k in range(nb_trucks)
        )
        model.constraint(
            quantity_served >= demands_data[i]
        )

    total_distance = model.sum(*route_distances)
    model.minimize(total_distance)

    solution = solve(model, time_limit_s=float(time_limit))
    if not solution.feasible:
        print(f"No feasible solution found; Status = {solution.status}")
        return solution

    output_lines = [str(total_distance.value)]
    for sequence in customers_sequences:
        if sequence.value:
            output_lines.append(
                " ".join(str(customer + 1) for customer in sequence.value)
            )

    result_text = "\n".join(output_lines)
    print(f"Status = {solution.status}\n{result_text}")
    if output_file is not None:
        Path(output_file).write_text(result_text + "\n", encoding="utf-8")
    return solution

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

solution_s51d1 = main(
    INSTANCE_DIR / "S51D1.sd",
    time_limit=1,
)

solution_s76d2 = main(
    INSTANCE_DIR / "S76D2.sd",
    time_limit=1,
)

solution_s101d3 = main(
    INSTANCE_DIR / "S101D3.sd",
    time_limit=1,
)