tsp领域的问题, 并不都是tsp问题, 但是, tsp相关的算法一般都能解决, 只要你能为某一个充满个性的问题儿子找到他亲生的解决方案爸爸.

经过前面7篇的努力, 我们实际上已经解决了订单分配问题, 因为派件时间窗其实不是一个分配问题. 下面我们详细分析一下

需求概述
  1. 某样物品, 客户要求在下午4:00前收到.
  2. 某样物品, 客户要求在中午12:00前收到.
分析
  • 这些其实并不是需求, 原因是: 我们无法保证满足, 除非用类似无人机这样的设备, 直接空投过去. 不然, 受各种因素干扰, 我们一般情况下只能说, 预计某一天到达. 快递的目标就是把这个某一天尽量提前, 比如全球次日达.
  • 然后, 当单量上升到一定地步的时候, 我们可以把工作时间段逐步拆碎, 比如每天分成3段, 这个货预计上午9:00-12:00到. 单量再上升, 甚至可以半个小时一段. 比如配餐服务.
  • 如果客人一定要求我们更快速配送, 比如支付很多费用, 那么可以通过路线调整来满足.
  • 但是, 实际上配送效率还是我们服务的整体质量中最核心的内容, 因此, 我们应该针对所有客户给一个相当快的配送效率, 而不是针对某些客户提供付费服务.
结论
  • 我们应该提供更高效的服务.
  • 比如当日达, 我们要保证当日能到达, 并且当日能让尽量多的订单到达.
  • 由此, 线路规划还是非常有用的. 而且有与实际工作中我们的订单有诸多的限制, 因此, 这个线路规划不能使用生成类方法比如:
    • 插入类算法, 如: 最远插入法……
    • 生成树类算法, 包括christofides
  • 可以使用尝试类算法例如
    • 线性规划LP
    • LK交换算法
    • 遗传算法
    • 动态规划
  • 这些算法里面, LP, LK和遗传我们后文讨论, 这里我们先聊一下动态规划.
动态规划 held-karp算法

这个算法很优雅, 也是目前精确算法中理论速度最好的, 可惜的是, 他的开销是2的n次方. 所以, 他不实用, 很遗憾, 我试过了, 确实不实用, 但是他的思路对我们还是有很多启发的.

  • 每一步都计算所有的点位最后一个点的可能性.
  • 每一步都依赖前一步的结果.

例如

  • 一共有10个点.
  • 假设现在是第六步,
    • 我要计算4为最后一步的所有结果.
    • 那么, 以 1, 2, 3, 5, 6, 7, 8, 9, 10为最后一个点的5个点的集合, 并且是不包含4的集合.
    • 然后可以得到以4为终点的所有含有6个点的结果.

总体思路

  • 关键是编码规则. 建议规则

    _id1_id2_id3_

  • 比如已经生成了3个元素的所有集合.

  • (1, 2, 3) 这三个元素的集合可以顺序生成,

    • ((1, 2, 3,) 4,) , ((1, 2, 3,) 5,) , ((1, 2, 3,) 6,)…… 等等.

  • 然后同理(1, 2, 4), 可以顺序生成 ((1, 2, 4,) 3,),

  • ((1, 2, 3,) 4,) 和 ((1, 2, 4,) 3,) 都是(1,2,3,4)的一部分, (1,2,3,4)包含了所有的情况.

时间开销: 以((1, 2, 3,) 4,)举例, 最后一步.

  1. (1, 2, 3) 这里是c43, 是四个挑3个. cnm, n是总数, m是当前的轮次.
  2. 然后, 和最后一个数字的结合是p42, 是排列, 4*3的排列=n * (n-1)

总体步骤

  • 初始化:

    • 生成(1), (2), (3),…….(10)

    • 生成((1), 2), ((1), 3)……((10),9)

    • 此时(1, 2), 包含((1), 2)和 ((2), 1)

    • 这里(1, 2)是一个karp, 他的id

      _id1_id2_

  • 实际运算

    • 生成(1, 2, 3), (1, 2, 4)……(8,9,10)

    • 顺序生成4个元素……

    • 一直到全部10个元素的一个karp, 他的id:

      _id1_id2_id3_id4_id5_id6_id7_id8_id9_id10_

  • 数据定义

    • 所有的karp都在一个held结构里面.
    • 可以快速的索引到, 期望的karp, 如果对应的karp没有索引到, 就新建一个.

算法

  • 一个for循环
    • 每个层次都处理当前层次的held结构.
    • 处理的过程中生成下一个层次的held.

数据结构

  • held结构包含本层次的所有karp,
    • 比如held(2)包含所有的karp(1, 2), karp(1, 3)….. karp(9,10)
    • held里面可以顺序遍历自己的所有karp.
    • held可以索引自己的karp.
      • 如何索引到合适的karp.
      • 根据一组key数组, 索引到合适的karp.
      • 这一个数组key, 可以组合为一个字符串. 用这个串作为karp的key
  • karp
    • 插入
      • 插入某个包含key的值.
    • key, 整体包括所有key(element->e).
      • 包含的key,
        • 反正都要indexof, 不如就用array吧.
      • 不包含的key
function algorithm TSP (G, n)
  for k := 2 to n do
    C({k}, k) := d1,k
  end for

  for s := 2 to n-1 do
    for all S ⊆ {2, . . . , n}, |S| = s do
      for all k ∈ S do
        C(S, k) := minm≠k,m∈S [C(S\{k}, m) + dm,k]
      end for
    end for
  end for

  opt := mink≠1 [C({2, 3, . . . , n}, k) + dk,1]
  return (opt)
end