背景介绍：物流配送

随着电子商务的迅猛发展，电商平台对物流配送的需求日益增长。为了确保货物能够按时、高效地送达消费者手中，电商平台与第三方物流公司建立了紧密的合作关系。然而，面对大量的货物和多样的目的地，如何制定合理的运输策略成为了物流公司面临的一大挑战。

 

传统的物流优化方法在应对复杂的运输需求时往往具有较高的复杂度。为了解决这个问题，物流公司希望借助量子计算技术来自动计算运输综合策略，从而可以更合理地规划运输路线、选择合适的运输方式和工具，并确保在规定的时间内将货物送达目的地。这样不仅能够提高物流效率，降低运输成本，还能够提升消费者对电商平台的满意度。

 

量子计算，尤其是相干伊辛机(Coherent Ising Machine, CIM)，在处理复杂优化问题方面展现出了巨大的潜力。由于其和相干伊辛机的紧密联系，QUBO（Quadratic Unconstrained Binary Optimization）模型构成了量子计算中的一类核心问题。QUBO模型是一种适配相干伊辛机（CIM）的模型，其形式为

 

 

其中Q为n*n的系数矩阵。

 

问题介绍

 

有两个第三方物流公司，负责每周将电商平台的货物送往各地。当前时间是周一，以下货物需要在 7 天内从当前城市运往目的地。

 

 

货物需要运往的城市

 

 

场上有12吨载重卡车和5吨载重卡车两种卡车供租赁，租金分别为每天5000元和每天3000元。这些卡车可以在任何地方租赁，并且客户可以根据自己的需求选择合适的卡车类型和租赁时长。假设每个城市有足够数量的可供租赁的卡车。

 

为节约成本，各小组间可在任何一个城市拼货和中转运输。拼货是指将来自不同发货人的货物合并在一起，由同一辆车或同一批运输工具运送的方式。同时货物可以由一辆车辆全部或者部分卸货后，暂存在当前城市，待后续的车辆将其运走。通过拼货可以更加灵活地安排运输计划，提高运输效率，降低成本，优化运输路线和运输资源的利用。

 

已知卡车上述6个城市两两之间运货一次需要花费的时间，以及普通卡车A（12吨）和普通卡车B（5吨）在上述6个城市之间运货的单趟成本。

 

除了陆路运输，货物也可以通过航空运输，题目中考虑的任意两个城市之间都可以通过航空运输进行货物运输。为简化计算，假设货物的国内航空运价无论远近均为 10000 元/吨，当日到达；

 

（1）假设这两个物流公司独立运营，拼货只发生在公司内部。你的任务是以最小化单个物流公司的运营成本为目标，建立QUBO模型，使用Kaiwu SDK中的CIM模拟器和模拟退火求解器分别求解，为两个物流公司分别设计货车租赁方案和货物运输方案。

（2）当这两个物流公司之间合作运营时，公司之间可以拼货运输，此时的优化目标为最小化两个公司的总成本。请使用Kaiwu SDK中的CIM模拟器和模拟退火求解器求解，给出最优的货车租赁方案和货物运输方案，以及合作运营带来的总体成本减少量。

 

定义

 

为了规范化表述，将上述物流配送问题用到的集合与数据做以下定义：

将城市定义为节点，6个城市构成6个节点的图。

定义从节点j出发到节点i需要的天数为

定义第k种类型的车辆从节点i到节点j的日租金为

定义第k种类型的车辆的容量

定义空运的单位成本

定义节点i的货物需求量，需要向节点i运送的货物量大小为

定义节点i在初始时刻的货物存储量

 

问题解答

 

模型

 

定义类型k的卡车在第t天从节点i到节点j的卡车数量为。

定义类型k的卡车在从节点i到节点j前进时携带的货物数量为

定义从节点i到节点j通过空运运送的货物数量

 

目标

空运费用：

 

 

租金：

 

 

载重成本：

 

 

约束条件

运载货物不超过车辆容量：

 

 

到第T天为止，流入节点i的货物量不小于流出节点i的货物量

对于有货物需求的城市，需要7天内把货物送到

 

 

第1问和第2问的区别

第一问的时候拼货只发生在公司内部，所以两个公司需要分别构建图，求解两次

第二问的时候，拼货可以在公司之间发生，所以将两次的货物合起来，求解一次

 

代码

import numpy as np
import pandas as pd
import kaiwu as kw
import kaiwu.qubo as kq
from utils import SubQuboSolver # 根据参考论文实现

def kw_integer(name):
    return kq.Integer(name, 0, 3) # 根据实际情况调整

class CIMSolver:
    def __init__(self):
        """初始化参数"""
        self.num_node = 6
        self.time_limit = 7

        self.dis = None
        self.price_rent = np.array([5000, 3000])
        self.capacity_v = np.array([12, 5])
        self.price_v = np.zeros((2, self.num_node, self.num_node))
        self.storage = None
        self.demand = None
        self.price_air = 10000
        self.ising_model = None

    def prepare_data(self):
        """载入数据，可以粘贴到文件或者代码硬编码"""
        self.dis = pd.read_csv("data/D.csv", header=None, index_col=None).to_numpy()
        self.price_v[0] = pd.read_csv("data/PA.csv", header=None,
            index_col=None).to_numpy()
        self.price_v[1] = pd.read_csv("data/PB.csv", header=None,
            index_col=None).to_numpy()
        self.storage = pd.read_csv("data/storage.csv", header=None,
            index_col=None).to_numpy()
        self.demand = pd.read_csv("data/demand.csv", header=None,
            index_col=None).to_numpy()

    def prepare_model(self):
        """QUBO建模"""
        num_vehicle = kq.ndarray((self.time_limit, 2,
                                    self.num_node, self.num_node), "n", kw_integer)
        vehicle = kq.ndarray((self.time_limit, 2,
                                    self.num_node, self.num_node), "x", kw_integer)
        air = kq.ndarray((self.num_node, self.num_node), "f", kw_integer)
        air_cost = air.sum() * self.price_air
        # 剪枝，减少变量数
        for i in range(self.num_node):
            for j in range(self.num_node):
                if i == j:
                    num_vehicle[:, :, i, j] = 0
                    vehicle[:, :, i, j] = 0
                    air[i, j] = 0
                for t in range(self.time_limit):
                    for k in range(self.num_type):
                        if t + self.dis[i, j] >= self.time_limit:
                            num_vehicle[t, k, i, j] = 0
                            vehicle[t, k, i, j] = 0

        tmp = num_vehicle * self.price_rent[None, :, None, None]
        vehicle_rent_cost = tmp.sum(axis=1)* self.dis[np.newaxis, :]
        vehicle_rent_cost = vehicle_rent_cost.sum()
        vehicle_cost = (num_vehicle * self.price_v[None, :]).sum()

        constr_c_slack = kq.ndarray((self.time_limit, 2,
                                    self.num_node, self.num_node), "c_slk", kw_integer)
        # 松弛变量可以通过ALM求解去掉
        capacity_limit = num_vehicle * self.capacity_v[None, :, None, None]
        constr_capacity = (vehicle - capacity_limit + constr_c_slack) ** 2
        constr_capacity = constr_capacity.sum()

        constr_e_slack = kq.ndarray((1, self.num_node), "e_slk", kw_integer)
        trans_out = np.zeros((self.time_limit,
                            self.num_node, self.num_node), dtype=object)
        for t in range(self.time_limit):
            for i in range(self.num_node):
                for j in range(self.num_node):
                    if t-self.dis[i, j] >= 0:
                        trans_out[t, i, j] += vehicle[t-self.dis[i, j], :, i, j].sum()
            if t > 0:
                trans_out[t] += trans_out[t - 1]
        constr_equ = (self.storage - air.sum(axis=1)[None, :] + trans_out.sum(axis=2)\
                        - vehicle.sum(axis=(1,3)) + constr_e_slack) ** 2
        constr_equ = constr_equ.sum()

        constr_demand = trans_out[-1].sum(axis=0) + air.sum(axis=1) - \
                        vehicle.sum(axis=(0, 1, 3)) - self.demand
        constr_demand = (constr_demand ** 2).sum()

        obj = air_cost + vehicle_cost
        constr = constr_capacity + constr_equ + constr_demand
        qubo_made = kq.make(obj + 100 * constr)
        self.ising_model = kq.qubo_model_to_ising_model(qubo_made)

    def solve(self):
        """求解"""
        self.prepare_data()
        self.prepare_model()
        ising_mat = self.ising_model.get_ising()["ising"]
        worker = SubQuboSolver()
        output = worker.solve(ising_mat)

        # Sort the results
        opt = kw.sampler.optimal_sampler(ising_mat, output, bias=0, negtail_ff=False)
        # Select the best solution
        cim_best = opt[0][0]
        # If the linear term variable is -1, perform a flip
        cim_best = cim_best * cim_best[-1]
        return cim_best

if __name__ == "__main__":
    kw.init
    solver = CIMSolver()
    solver.solve()

 

总结

 

电商平台迅速发展加剧了对高效物流配送的需求，采用量子计算技术来优化运输策略是一个有效的方案。 通过求解QUBO模型，物流公司能够更有效地规划路线、选择运输方式，以降低成本并提升消费者满意度。

 

背景介绍：物流配送

随着电子商务的迅猛发展，电商平台对物流配送的需求日益增长。为了确保货物能够按时、高效地送达消费者手中，电商平台与第三方物流公司建立了紧密的合作关系。然而，面对大量的货物和多样的目的地，如何制定合理的运输策略成为了物流公司面临的一大挑战。

 

传统的物流优化方法在应对复杂的运输需求时往往具有较高的复杂度。为了解决这个问题，物流公司希望借助量子计算技术来自动计算运输综合策略，从而可以更合理地规划运输路线、选择合适的运输方式和工具，并确保在规定的时间内将货物送达目的地。这样不仅能够提高物流效率，降低运输成本，还能够提升消费者对电商平台的满意度。

 

量子计算，尤其是相干伊辛机(Coherent Ising Machine, CIM)，在处理复杂优化问题方面展现出了巨大的潜力。由于其和相干伊辛机的紧密联系，QUBO（Quadratic Unconstrained Binary Optimization）模型构成了量子计算中的一类核心问题。QUBO模型是一种适配相干伊辛机（CIM）的模型，其形式为

 

 

其中Q为n*n的系数矩阵。

 

问题介绍

 

有两个第三方物流公司，负责每周将电商平台的货物送往各地。当前时间是周一，以下货物需要在 7 天内从当前城市运往目的地。

 

 

货物需要运往的城市

 

 

场上有12吨载重卡车和5吨载重卡车两种卡车供租赁，租金分别为每天5000元和每天3000元。这些卡车可以在任何地方租赁，并且客户可以根据自己的需求选择合适的卡车类型和租赁时长。假设每个城市有足够数量的可供租赁的卡车。

 

为节约成本，各小组间可在任何一个城市拼货和中转运输。拼货是指将来自不同发货人的货物合并在一起，由同一辆车或同一批运输工具运送的方式。同时货物可以由一辆车辆全部或者部分卸货后，暂存在当前城市，待后续的车辆将其运走。通过拼货可以更加灵活地安排运输计划，提高运输效率，降低成本，优化运输路线和运输资源的利用。

 

已知卡车上述6个城市两两之间运货一次需要花费的时间，以及普通卡车A（12吨）和普通卡车B（5吨）在上述6个城市之间运货的单趟成本。

 

除了陆路运输，货物也可以通过航空运输，题目中考虑的任意两个城市之间都可以通过航空运输进行货物运输。为简化计算，假设货物的国内航空运价无论远近均为 10000 元/吨，当日到达；

 

（1）假设这两个物流公司独立运营，拼货只发生在公司内部。你的任务是以最小化单个物流公司的运营成本为目标，建立QUBO模型，使用Kaiwu SDK中的CIM模拟器和模拟退火求解器分别求解，为两个物流公司分别设计货车租赁方案和货物运输方案。

（2）当这两个物流公司之间合作运营时，公司之间可以拼货运输，此时的优化目标为最小化两个公司的总成本。请使用Kaiwu SDK中的CIM模拟器和模拟退火求解器求解，给出最优的货车租赁方案和货物运输方案，以及合作运营带来的总体成本减少量。

 

定义

 

为了规范化表述，将上述物流配送问题用到的集合与数据做以下定义：

将城市定义为节点，6个城市构成6个节点的图。

定义从节点j出发到节点i需要的天数为

定义第k种类型的车辆从节点i到节点j的日租金为

定义第k种类型的车辆的容量

定义空运的单位成本

定义节点i的货物需求量，需要向节点i运送的货物量大小为

定义节点i在初始时刻的货物存储量

 

问题解答

 

模型

 

定义类型k的卡车在第t天从节点i到节点j的卡车数量为。

定义类型k的卡车在从节点i到节点j前进时携带的货物数量为

定义从节点i到节点j通过空运运送的货物数量

 

目标

空运费用：

 

 

租金：

 

 

载重成本：

 

 

约束条件

运载货物不超过车辆容量：

 

 

到第T天为止，流入节点i的货物量不小于流出节点i的货物量

对于有货物需求的城市，需要7天内把货物送到

 

 

第1问和第2问的区别

第一问的时候拼货只发生在公司内部，所以两个公司需要分别构建图，求解两次

第二问的时候，拼货可以在公司之间发生，所以将两次的货物合起来，求解一次

 

代码

import numpy as np
import pandas as pd
import kaiwu as kw
import kaiwu.qubo as kq
from utils import SubQuboSolver # 根据参考论文实现

def kw_integer(name):
    return kq.Integer(name, 0, 3) # 根据实际情况调整

class CIMSolver:
    def __init__(self):
        """初始化参数"""
        self.num_node = 6
        self.time_limit = 7

        self.dis = None
        self.price_rent = np.array([5000, 3000])
        self.capacity_v = np.array([12, 5])
        self.price_v = np.zeros((2, self.num_node, self.num_node))
        self.storage = None
        self.demand = None
        self.price_air = 10000
        self.ising_model = None

    def prepare_data(self):
        """载入数据，可以粘贴到文件或者代码硬编码"""
        self.dis = pd.read_csv("data/D.csv", header=None, index_col=None).to_numpy()
        self.price_v[0] = pd.read_csv("data/PA.csv", header=None,
            index_col=None).to_numpy()
        self.price_v[1] = pd.read_csv("data/PB.csv", header=None,
            index_col=None).to_numpy()
        self.storage = pd.read_csv("data/storage.csv", header=None,
            index_col=None).to_numpy()
        self.demand = pd.read_csv("data/demand.csv", header=None,
            index_col=None).to_numpy()

    def prepare_model(self):
        """QUBO建模"""
        num_vehicle = kq.ndarray((self.time_limit, 2,
                                    self.num_node, self.num_node), "n", kw_integer)
        vehicle = kq.ndarray((self.time_limit, 2,
                                    self.num_node, self.num_node), "x", kw_integer)
        air = kq.ndarray((self.num_node, self.num_node), "f", kw_integer)
        air_cost = air.sum() * self.price_air
        # 剪枝，减少变量数
        for i in range(self.num_node):
            for j in range(self.num_node):
                if i == j:
                    num_vehicle[:, :, i, j] = 0
                    vehicle[:, :, i, j] = 0
                    air[i, j] = 0
                for t in range(self.time_limit):
                    for k in range(self.num_type):
                        if t + self.dis[i, j] >= self.time_limit:
                            num_vehicle[t, k, i, j] = 0
                            vehicle[t, k, i, j] = 0

        tmp = num_vehicle * self.price_rent[None, :, None, None]
        vehicle_rent_cost = tmp.sum(axis=1)* self.dis[np.newaxis, :]
        vehicle_rent_cost = vehicle_rent_cost.sum()
        vehicle_cost = (num_vehicle * self.price_v[None, :]).sum()

        constr_c_slack = kq.ndarray((self.time_limit, 2,
                                    self.num_node, self.num_node), "c_slk", kw_integer)
        # 松弛变量可以通过ALM求解去掉
        capacity_limit = num_vehicle * self.capacity_v[None, :, None, None]
        constr_capacity = (vehicle - capacity_limit + constr_c_slack) ** 2
        constr_capacity = constr_capacity.sum()

        constr_e_slack = kq.ndarray((1, self.num_node), "e_slk", kw_integer)
        trans_out = np.zeros((self.time_limit,
                            self.num_node, self.num_node), dtype=object)
        for t in range(self.time_limit):
            for i in range(self.num_node):
                for j in range(self.num_node):
                    if t-self.dis[i, j] >= 0:
                        trans_out[t, i, j] += vehicle[t-self.dis[i, j], :, i, j].sum()
            if t > 0:
                trans_out[t] += trans_out[t - 1]
        constr_equ = (self.storage - air.sum(axis=1)[None, :] + trans_out.sum(axis=2)\
                        - vehicle.sum(axis=(1,3)) + constr_e_slack) ** 2
        constr_equ = constr_equ.sum()

        constr_demand = trans_out[-1].sum(axis=0) + air.sum(axis=1) - \
                        vehicle.sum(axis=(0, 1, 3)) - self.demand
        constr_demand = (constr_demand ** 2).sum()

        obj = air_cost + vehicle_cost
        constr = constr_capacity + constr_equ + constr_demand
        qubo_made = kq.make(obj + 100 * constr)
        self.ising_model = kq.qubo_model_to_ising_model(qubo_made)

    def solve(self):
        """求解"""
        self.prepare_data()
        self.prepare_model()
        ising_mat = self.ising_model.get_ising()["ising"]
        worker = SubQuboSolver()
        output = worker.solve(ising_mat)

        # Sort the results
        opt = kw.sampler.optimal_sampler(ising_mat, output, bias=0, negtail_ff=False)
        # Select the best solution
        cim_best = opt[0][0]
        # If the linear term variable is -1, perform a flip
        cim_best = cim_best * cim_best[-1]
        return cim_best

if __name__ == "__main__":
    kw.init
    solver = CIMSolver()
    solver.solve()

 

总结

 

电商平台迅速发展加剧了对高效物流配送的需求，采用量子计算技术来优化运输策略是一个有效的方案。 通过求解QUBO模型，物流公司能够更有效地规划路线、选择运输方式，以降低成本并提升消费者满意度。