0

我编写了一个小程序来解决我遇到的问题，但无法扩展它并且可能需要一些要点/帮助。

数据有3个矩阵

1) 商品价格

price = [
    [11.5, 12.5, 10.75, 11.5],
    [19, 13.5, 12.85, 11.9],
    [1.95, 1.9, 1.75],
    [2.95, 2.45, 1.65, 1.59],
    [8.5, 6.45, 8.5, 8.5],
    [12.5, 10.5, 10.25, 10.5],
    [4.25, 5.5, 5.5, 5],
    [4.25, 5.5, 5.5, 5],
    [4.25, 5.5, 5.5, 5],
    [50],
    [30],
]

2) 名义上的差异，其中 100 = 最佳价格 

diff = [
    [80, 86, 100, 80],
    [47, 66, 93, 100],
    [90, 92, 100],
    [54, 65, 96, 100],
    [100, 66, 100, 100],
    [82, 98, 100, 81],
    [97, 100, 88, 83],
    [97, 100, 88, 83],
    [97, 100, 88, 83],
    [100],
    [100]
]

3) 可以全部或部分交付我的产品的可能供应商

data = [
    [0, 1, 2, 3],
    [0, 1, 2, 3],
    [0, 1, 2],
    [0, 1, 2, 3],
    [0, 1, 2, 3],
    [0, 1, 2, 3],
    [0, 1, 2, 3],
    [0, 1, 2, 3],
    [0, 1, 2, 3],
    [0],
    [0],
]

每个供应商都可以有一个最小订单约束，每行只有一个项目。

deliverer = [0, 1, 2, 3]
min_order = {0: 50, 1: 30, 2: 0, 3: 100}   

combinations = list(itertools.product(*data))

def compute(combinations):

    def get_score(comb):
        score = 0
        available = []
        for index, item in enumerate(comb):
            score += diff[index][item]
            available.append(diff[index][item])
        return (score, all(i > 0 for i in available))

    def get_price(comb):
        price_dict = {key: {'price': 0, 'reached': False} for key in comb}
        for index, item in enumerate(comb):
            p = price[index][item]
            price_dict[item]["price"] += p
            if price_dict[item]["price"] >= min_order[item]:
                price_dict[item]["reached"] = True

        return price_dict

然后，我遍历所有可能的组合并计算得分值，以及是否可以传递从上到下的路径并包含所有项目。

    new_comb = []
    for comb in combinations:
        score, all_items = get_score(comb)
        price_dict = get_price(comb)
        check = [value["reached"] for value in price_dict.values()]
        can_deliver = False
        if all(i is True for i in check):
            can_deliver = True

        if can_deliver is False:
            continue

        new_comb.append({"way": comb, "score": score, "all_items": all_items, "price": price_dict,
                        "can_deliver": can_deliver, "d_count": len(price_dict.keys())})

    return new_comb

在这一步中，我只是对我的最佳解决方案的返回值进行排序。在这里，我需要添加另一个约束以找到最少数量的送货员并逐步提高，直到我拥有可以运送所有物品的最多送货员。

new_comb = compute(combinations)

new_comb = sorted(new_comb, key=lambda k: (k["can_deliver"], k["all_items"], k["score"]), reverse=True)

best_solutions = []
for item in new_comb:
    if item["can_deliver"] is True:
        best_solutions.append(item)

print(best_solutions[:15])

我现在的问题是如何使这种问题规模化。哪些技术可以处理 60x10 或更大的矩阵。

我将不胜感激任何帮助。

4

0 回答 0