(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111615194.2 (22)申请日 2021.12.27 (71)申请人 上海交通大 学 地址 200240 上海市闵行区东川路80 0号 (72)发明人 谢德明　黄江林　 (74)专利代理 机构 上海交达专利事务所 31201 代理人 王毓理　王锡麟 (51)Int.Cl. G06F 30/20(2020.01) G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06F 111/04(2020.01) G06F 111/06(2020.01) (54)发明名称 基于VDP的汽 车零部件配送中心选址优化方 法 (57)摘要 一种基于VDP的汽车零部件配送中心选址优 化方法， 根据选址时的约束条件和选址目标进行 数学建模， 将配送中心选址问题转变为常见的0 ‑ 1整数规划问题， 再将该0 ‑1整数规划问题规约到 VDP问题， 然后用最大化其中一个子问题区域的 方法找到用分治法解决VDP问题的分割点， 找出 VDP问题所有的可行解， 再根据其解计算目标函 数， 即最大化选址方案的利润， 得到最优解， 从而 的得到了最优的汽车零部件配送中心选址方案。 最大化用分治法解决VDP问题时其中一个子问题 区域的方法是使得高效解决VDP问题的关键。 本 发明能够快速的计算NP 难的配送中心选址问题， 且最后给出的选址方案是最优解， 具有实际应用 价值。 权利要求书1页 说明书4页 附图1页 CN 114282373 A 2022.04.05 CN 114282373 A 1.一种基于VDP的汽车零部件配送中心选址优化方法， 其特征在于， 根据选址时的约束 条件和选址目标进 行数学建模， 将 配送中心选址问题转变为常见的0 ‑1整数规划问题， 再将 该0‑1整数规划问题规约到VDP问题， 然后用最大化其中一个子问题区域的方法找到用分治 法解决VDP问题的分割点， 找出VDP问题所有的可行解， 再根据其解计算目标函数， 即最大化 选址方案的利润， 得到最优解， 从而的得到了最优的汽车零部件配送中心选址方案， 最大化 用分治法解决VD P问题时其中一个子问题区域的方法是使得高效解决VD P问题的关键 。 2.根据权利要求1所述的基于VDP的汽车零部件配送中心选址优化方法， 其特征是， 所 述的选址目标包括 最后选址方案含有配送中心的个数限制、 投资成本限制。 3.根据权利要求1所述的基于VDP的汽车零部件配送中心选址优化方法， 其特征是， 所 述的建造成本是指： 零部件配送中心从开始规划到建成投入使用需要的投资额。 4.根据权利要求1所述的基于VDP的汽车零部件配送中心选址优化方法， 其特征是， 所 述的运维成本是指： 配送中心投入使用后， 人力、 物力的开销以及运输费用投入额。 5.根据权利要求1所述的基于VDP的汽车零部件配送中心选址优化方法， 其特征是， 所 述的年化利润是指： 该配送中心一 年的营业收入额。 6.根据权利要求1所述的基于VDP的汽车零部件配送中心选址优化方法， 其特征是， 所 述的约束条件是指： 对任一投资方案投资总额不能超过一定值； 某一区域内配送中心个数 上限和下限， 包括建造配送中心的成本、 建成后的运维成本、 运输费用。 7.根据权利要求1所述的基于VDP的汽车零部件配送中心选址优化方法， 其特征是， 所 述的目标函数 是指： 配送中心方案 选定后， 使得年利 润最大化。 8.根据权利要求1所述的基于VDP的汽车零部件配送中心选址优化方法， 其特征是， 所 述的VDP问题是指： 给予两组d维的向量组A和B， 从A中找到一个向量u， B中找 一个向量v使 得 满足u≥v， 大于指向量的每一维的值都大于 。 9.根据权利要求1所述的基于VDP的汽车零部件配送中心选址优化方法， 其特征是， 所 述的最大化其中一个子问题 区域是指： 对于将汽车零部件技术问题转化为要解决的VDP问 题后， 可表示为T(A,B,d)， 用分治法解决该问题会将其划分为T(A ‑,B‑,d)， T(A+,B+,d)和T (A+,B‑,d‑1)进行解答， 要最大化的便是T(A+,B ‑,d‑1)该问题的区域， 即|A+| ×|B‑|， |A+| 和|B‑|分别表示A+和B ‑的大小。权　利　要　求　书 1/1 页 2 CN 114282373 A 2基于VDP的汽车零部件配送中心选址优化方 法 技术领域 [0001]本发明涉及的是一种汽车零部件制造商配送中心选址的技术， 具体是一种基于 Vector Domination Problem(VD P)的汽车零部件配送中心选 址优化方法。 背景技术 [0002]现有配送中心选址技术包括： 基于遗传算法， 首先根据选址约束条件和目标进行 数学建模， 再对每一个配送中心编 码， 并找到一个合适的适应函数， 通过遗传算子找到一个 解。 这种方法容易陷入局部最优解， 找到的解不一定是最优解。 现有的物流站 点的选址技术 过于依赖 于外部软件进行最后的求 解， 寻找最后的选 址方案分为两 部， 耗时长 。 发明内容 [0003]本发明针对现有技术存在的上述不足， 提出一种基于VDP的汽车零部件配送中心 选址优化方法， 能够快速的计算NP难的配送中心选址 问题， 且最后给出的选址方案是最优 解， 具有实际应用价 值。 [0004]本发明是通过以下技 术方案实现的： [0005]本发明涉及一种基于VDP的汽车零部件配送中心选址优化方法， 根据选址时的约 束条件和选址目标进 行数学建模， 将 配送中心选址问题 转变为常见的0 ‑1整数规划问题， 再 将该0‑1整数规划问题规约到VDP问题， 然后用最大化其中一个子问题区域的方法找到用分 治法解决VDP问题的分割点， 找出VDP问题所有的可行解， 再根据其解计算目标函数， 即最大 化选址方案的利润， 得到最优解， 从而的得到了最优的汽车零部件配送中心选址方案。 最大 化用分治法解决VD P问题时其中一个子问题区域的方法是使得高效解决VD P问题的关键 。 [0006]所述的选 址目标包括 最后选址方案含有配送中心的个数限制、 投资成本限制等。 [0007]所述的建造成本是指： 零部件配送中心从开始规划到建成投入使用需要的投资 额。 [0008]所述的运维成本是指： 配送中心投入使用后， 人力、 物力的开销以及运输费用等投 入额。 [0009]所述的年 化利润是指： 该配送中心一 年的营业收入额。 [0010]所述的约束条件是指： 对任一投资方案投资总额不能超过一定值； 某一区域内配 送中心个数 上限和下限， 包括建造配送中心的成本、 建成后的运维成本、 运输费用等。 [0011]所述的目标函数 是指： 配送中心方案 选定后， 使得年利 润最大化。 [0012]所述的VDP问题是指： 给予两组d维的向量组A和B， 从A中找到一个向量u， B中找一 个向量v使得满足u≥v， 大于指向量的每一维的值都大于 。 [0013]所述的最大化其中一个子问题区域是指： 对于将汽车零部件技术问题转化为要解 决的VDP问题后， 可表示为T(A,B,d)， 用分治法解决该问题会将其划分为T(A ‑,B‑,d)， T(A+, B+,d)和T(A+,B ‑,d‑1)进行解答， 要最大化的便是T(A+,B ‑,d‑1)该问题的区域， 即|A+| ×| B‑|， |A+|和|B ‑|分别表示A+和B ‑的大小。说　明　书 1/4 页 3 CN 114282373 A 3