V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
timchou
V2EX  ›  程序员

求点拨: N 个商品, M 种发货渠道,寻找最优解?

  •  
  •   timchou · 2018-05-23 14:39:56 +08:00 · 2667 次点击
    这是一个创建于 2359 天前的主题,其中的信息可能已经有所发展或是发生改变。
    实际中遇到一个实际场景,想了半天没想到合适的方式,有没有算法达人点拨下?

    场景是电商发货中,每个商品都有多种的发货渠道,每种渠道的价格不同,然后还有各种包裹限制,所以需要综合判断,选择一个最优的发货方式:

    1.有 n 个商品,每个商品有:
    a.价格 price
    b.重量 weight
    c.税率 tax

    2.有 m 种渠道,每个渠道都有如下几个属性:
    a.首重成本 x 元(假设首重指的是 1kg)
    b.续重成本 y 元 /kg
    c.单个包裹重量上限 L1
    d.单个包裹价值上限 L2
    e.单个包裹税金上限 L3

    现在要对这些商品进行拆分,寻找最优拆分方式,要求:
    1.成本价最低
    2.单个包裹不能超过上述的限制 L1\L2\L3,也就是说一旦超过后,则需要另外起一个包裹。


    最简单的方式是把所有的可能性都摆出来,然后一一计算,选一个最优的,但是 n 和 m 一多的话,计算量就很大。。

    不知道有什么合适的算法可以处理这种问题吗?

    ps1:
    之前还想这么做:m 个渠道就是 m 个 slot,然后对每个商品,计算该商品丢到各个 slot 后,总的成本价分别是多少,然后选择一个最便宜的丢进去,但是实际上这个每个渠道是由首重+续重来确定费用的,因此商品丢到这个 slot 后,可能当前是最便宜的,但是最终结果不一定,比如渠道 1:首重很便宜,但是续重很贵;渠道 2:首重很贵,但是续重很便宜。。
    24 条回复    2018-05-24 13:40:57 +08:00
    746970179
        1
    746970179  
       2018-05-23 16:26:36 +08:00
    之前做过类似的.
    解决思路是: 为每个渠道计算价格
    解决方案:
    为渠道建表, 将首重, 首重费, 续重单位, 续重费用, 重量限制等当作字段, 保存起来
    然后写一个方法, 方法的工作内容是: 传入渠道数据, 和商品重量, 计算出金额

    这个公式的难点是, 不同的渠道, 不是所有的都是统一的公式, 有的可能没有首重费用, 有的可能有折扣等等
    实际情况中, 不太可能用一个公式保存
    所以根据实际情况, 抽象出几个公式即可
    我之前做的时候, 总共用了三个公式:
    1.线性增长(类似买菜, 精确到克) a+kx (a 是固定费用, k 是每 kg 多少钱, x 是重量)
    2.均匀阶梯增长(通话计费, 每 1 分钟固定 1 毛钱这样, 不足一分钟照 1 分钟算)
    3.不均匀阶梯(不规律的计费, 可能 1kg 的包裹 10 元, 2kg 的包裹 11 元, 3kg 的包裹 20 元这样, 无规律)
    其中 1 和 2, 可以用同一个公式或者分开, 因为 1 就是单位重量为 1g 的均匀阶梯增长
    3 的话, 看起来麻烦, 其实最简单, 一个字段, 用 json 存起来就行, 到时候按表查价格即可

    整理好后, 就能用方法, 为一个商品计算每个物流方式的准确价格了

    但实际情况比这还会复杂很多:
    1. 各种折扣: 首重折扣, 续重折扣, 总价折扣, 地区折扣等
    2. 地区价格: 发往每个地区的价格可能都有变化, 这是一个坑, 整理起来比较费时费力
    3. 商品的多仓库发货, 拆包发货. 这个也很麻烦和复杂. 不过主要看业务需求
    4. 维护问题.
    5. 性能相对来说不是大问题.

    最后效果的话, 如果结合实际业务需求做出来, 便宜 5~10%问题不大
    timchou
        2
    timchou  
    OP
       2018-05-23 16:35:15 +08:00
    @746970179 很感谢!

    您说的:“整理好后, 就能用方法, 为一个商品计算每个物流方式的准确价格了 ”

    这点貌似在我说的场景里不能适用,因为对于某个渠道,一件商品和 N 件商品最后的运费是不一样的,因为渠道有首重和续费

    比如某个渠道,首重很贵,续重便宜,另外有的渠道首重很便宜,续重很贵。。这种情景就很复杂了。
    menc
        3
    menc  
       2018-05-23 17:03:16 +08:00
    典型线性规划问题
    先写出来标准型,然后直接传入 scipy 求解线性规划问题
    menc
        4
    menc  
       2018-05-23 17:04:52 +08:00   ❤️ 2
    简单点说
    你的目标函数 F 是一个线性函数,目标是最大化或者最小化这个目标函数
    你的若干约束都是线性不等式。
    存在有限个参数。
    那八九不离十就是线性规划问题
    wplct
        5
    wplct  
       2018-05-23 17:14:22 +08:00
    额。还要多个商品打包么
    zjsxwc
        6
    zjsxwc  
       2018-05-23 17:16:38 +08:00
    一个商品允许通过 2+个渠道发货吗
    746970179
        7
    746970179  
       2018-05-23 17:25:33 +08:00
    @timchou
    是表述的不准确, 应该是包裹. 是为每个包裹的重量进行计算
    我说的那个方法, 传入的参数是重量, 和物流方式的相关计价参数
    因此, 是商品还是包裹, 问题不大, 最终传入方法的参数类型不变
    takato
        8
    takato  
       2018-05-23 17:25:40 +08:00
    NP-Complete
    746970179
        9
    746970179  
       2018-05-23 17:29:45 +08:00
    @zjsxwc
    这是我的表述不清, 准确的说是一个包裹. 这个就可能包含多件商品了
    yesterdaysun
        10
    yesterdaysun  
       2018-05-23 17:48:22 +08:00
    做过类似的, 我的解决方案是:
    1. 快递费模块, 负责计算一个包裹用特定的仓库特定的渠道, 发特定的地区, 精确的价格是多少, 需要事先把所有需要的规则和价格设置放进系统
    2. 规则模块, 负责判断所有仓库和渠道的规则, 比如某个渠道不发偏远的地区等等
    3. 包裹模块, 负责生成包裹方案, 就是几个包裹, 每个里面放那些产品 /数量, 贪心算法, 从一整个包裹开始算, 每个仓库, 每个渠道这样算, 利用规则模块排除不要的选项, 如果不行就拆包, 就是简单的求 subset 的算法, 一点点拆开穷举

    实际情况是大部分情况一个包裹就搞定了, 少部分一般拆两个包裹也搞定了, 不过如果订单产品数量多的情况下, 拆包穷举的数量是惊人的, 所以我直接就写死试了多少次就直接结束报错等人工处理了, 不过应该还没有遇到这个情况.

    你可以根据自己的情况改进
    tedzhu
        11
    tedzhu  
       2018-05-23 17:58:09 +08:00
    感觉确实是 NP 完全 要搜索+尽量剪枝吧 先分到每个 slot 里再在每个 slot 里排列 另外考虑实际情形 m 会不会不大 m<5? 也许没那么糟糕
    如果 n 比较大 可以考虑先排序 再采用若干策略求近似解 取最好的
    zynlp
        12
    zynlp  
       2018-05-23 17:59:16 +08:00 via iPhone
    云开发🤣
    timchou
        13
    timchou  
    OP
       2018-05-23 18:07:23 +08:00
    谢谢各位提供的思路,我好好研究学习学习,谢谢啦


    @menc
    @746970179
    @takato
    @yesterdaysun
    @tedzhu
    Fulcrum
        14
    Fulcrum  
       2018-05-23 18:17:39 +08:00
    有一个我能回答的问题,百度运筹学-运输问题。
    Fulcrum
        15
    Fulcrum  
       2018-05-23 18:20:19 +08:00
    找一个运筹学课本看一下,运输问题基本都会提出来讲
    stevenbipt
        16
    stevenbipt  
       2018-05-23 18:34:39 +08:00 via Android
    典型的运筹学问题
    takato
        17
    takato  
       2018-05-23 18:38:25 +08:00
    @timchou 首先不建议直接将 X 和 Y 扔进黑箱训练,这样可能能得到一个局部最优解。
    虽然很多时候八九不离十,但是当物品增多的时候有可能翻车。
    geelaw
        18
    geelaw  
       2018-05-23 18:43:03 +08:00 via iPhone
    可以表达为 0-1 规划问题(当然这是平凡的……因为 0-1 规划是 NPC ),应该说可以很自然地表达为 0-1 规划问题。

    每个渠道最多发 n 个包裹,把它看成 mn 个包裹(每个渠道复制 n 份),对每个商品设置 mn 个变量,表示“是否通过这个包裹发送”,对每个包裹设置一个变量,表示“是否有包裹”。

    约束是:

    每个商品的各个变量和是 1 (恰好发送一次)
    每个包裹的“是否有”乘 n 不小于发入这个包裹的商品数
    每个包裹费用 不小于 是否有*首重
    每个包裹费用 不小于 是否有*首重 + (总重-1)*续重
    每个包裹总重约束
    每个包裹价值约束
    每个包裹税金约束

    最小化 费用之和

    具体到求解,可以用分支定界法等。

    该问题是 NPH,因此很难想象到会有多项式时间的算法;尚不清楚这个问题是否是 strongly NPC,可以尝试寻找伪多项式时间的算法。
    oswuhan
        19
    oswuhan  
       2018-05-23 18:53:05 +08:00
    哈哈,考验数学功底的时候到了
    daveze
        20
    daveze  
       2018-05-23 19:29:07 +08:00   ❤️ 1
    我来个比较暴力的方案. 假设商品的价格 和 重量都是可以通过范围来枚举的.
    比如 价格 (1 元,2 元),(2 元,3 元),(1001 元,1002 元)
    重量 (100g, 110g), (110g, 120g)
    这样价格和重量的枚举范围是可以进行组合. 比如
    (1 元-2 元, 100g-110g), (1 元-2 元, 110g-120g), xxxx
    这样我们可以预先计算好每个组合最适合的渠道,如下:
    (1 元-2 元, 100g-110g, 渠道 2), (1 元-2 元, 110g-120g, 渠道 3), xxxx

    要计算一个商品的最佳渠道, 就是在简单的在上述范围内去查找最接近的一个组合(通过 R+tree).
    注意: 如果商品的价格或者重量超过了上面枚举的范围, 再退化到 n * m 的计算方案
    winglight2016
        21
    winglight2016  
       2018-05-23 19:37:39 +08:00
    楼主这个业务规则还是有点模糊:一个商品/包裹,是单独计算费用,还是和其他商品/包裹(同一渠道)合并计算费用?

    如果是合并计费,那可就复杂了,毕竟还有价值、税金上限,这个逻辑很难在通用算法中体现出来
    winglight2016
        22
    winglight2016  
       2018-05-23 19:54:55 +08:00
    忽然发现之前想得复杂了,应该有更简单的方法:
    1.排一个表格,包括:1 ~ 10 公斤(假设全渠道重量上限最小值),分别对应 m 个渠道的价格
    2.根据这个表格排序渠道优先级(基于全部商品重量)
    3.顺序填满 m 个渠道的 slot
    可能三个约束值会影响实际排序,不过,这是个权重问题,假设首重和续重的高权重超过 0.9,那就可以忽略吧
    startar
        23
    startar  
       2018-05-23 20:18:26 +08:00 via Android
    典型的线性规划问题。很多回复里自己设计的方案大概率是错的。建议楼主搞本运筹学看看。
    cdcx
        24
    cdcx  
       2018-05-24 13:40:57 +08:00
    @startar 现在讨论的问题,不是算不出最优解的问题. 而是如何提高效率的问题.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3458 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 11:21 · PVG 19:21 · LAX 03:21 · JFK 06:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.