tsp的理论与实践(7)取件时间窗

731

tsp目录

  1. 最简单的实践 juejin.cn/post/684490…
  2. 最简单的理论 juejin.cn/post/684490…
  3. 当前tsp的现状 juejin.cn/post/684490…
  4. 单起点任务分配 juejin.cn/post/684490…
  5. 多起点任务分配 juejin.cn/post/684490…
  6. 更简洁的多起点分配 juejin.cn/post/684490…
  7. 起点时间窗 juejin.cn/post/684490…
  8. 终点时间窗和hk juejin.cn/post/684490…
  9. LK简介 juejin.cn/post/684490…
  10. tsp系列暂停一下 juejin.cn/post/684490…

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

经过前面六篇的努力, 我们已经可以完美的解决多个发件地址发件的配送分配问题了, 但是, 因为公司有运营在, 所以技术不可能没事干, 所以, 新的业务需求出现了:

需求概述
  1. 客户需要组织生产, 因此要求我们下午再过来取件.
  2. 客户要求我们11:00之后取件.
  3. 客户要求我们13:30之后再来取件.
  4. 总之, 客户要求我们某个时间点之后来取件, 我们至少要计算两件事:
    1. 这单生意我们能接吗? 我们能在当天成功配送吗?
    2. 我们怎么排出最高效的配送方案, 是让配送员提前过去等一下.
分析
  • 之前的算法都是按照物理距离作为权重组织的.

  • 但是现在有了时间窗的概念, 时间上的距离要考虑进来, 比如现在是9:00, 有一单10:00才能取, 这一单只距离我3km, 但是, 我和他之间还有1个小时的时间距离. 所以, 我们的系统里面自然地出现了两类距离:

    • 空间转化的时间距离, 比如3km转化为5分钟.
    • 直接的时间的距离, 比如9:00到10:00是一小时的距离.
  • 但是, 如果直接粗暴的使用时间距离, 会引起很多问题, 比如, 1小时的时间距离, 会掩盖掉物理距离的巨大差异, 比如我们的时速是60km, 那么1小时的时间距离导致距离1km和距离60km的队列的权重是一样的了. 现实中的这种情况, 我们还是期望1km距离的司机上门取货, 宁肯他找个地方休息60分钟. 这样我们节省了汽油和司机的体力.

  • 这个问题我们也不能粗暴的修正, 比如:

    • 我们不能说先判断时间距离, 在时间距离一致的时候, 就判断空间距离, 这个方案的问题在于, 时间距离不会一致, 某个司机分配了一单, 他送完这单要到9:40, 然后系统一看他距离10:00最近了. 所以这相当远的一单就给他了.
    • 如果我们先判断空间距离, 然后, 就让司机原地等待到取件. 这样也是很没有效率的做法, 因为如果一单是下午18:30取件, 那么难道司机早上9:00到了客户那边, 然后等一天吗?
    • 我们也不能说到接近10:00的时候再分配. 比如有一个思路, 当离那个点最近的司机接单也在时效以内了, 那么就给他. 这样会导致一个问题: 本来司机原地等待一下就好了, 结果我们让他往返跑.
  • 因此, 直观的做法是:

    1. 我们按照空间距离来生成树, 但是, 生成的时候要判断下是否达成时间限制, 如果没有, 那么就先不排他, 改为排入距离第二的订单. 此时要记录订单和路径的关系.
    2. 然后继续分配, 依旧是这个逻辑, 如果某一单分进来, 不满足时效, 那么就先不分配.
    3. 此时需要评估一下这个时效单单权重是否依然生效. 参见下图.
    4. 当某一个时效单分进来, 满足取件时效要求了, 这时我们要做一次整体的评估, 历史上需要等待的分配都分一次, 看整体的时间开销哪一种最小.

    第三步的示例:

  1. 此时1号单分进来, 但是还不到取件时间.
  2. 只能分配c单进来, 此时1的权重不变, 因为a点还在.
  3. 然后, 1的取件时间还是不到, 那么我们分配b单进来.
    • 此时要删除a和1两个q之前的权重了.
    • 因为a的独立的对于1的权重是失效的,
    • 因为1号单需要某个时间之后配送, 不能a之后直接配送, a之后一定要做其他的单, 比如b单,
    • 所以a-1这个权重不会再生效了.

至此订单分配问题基本都已经解决了, 后续的分享将以路线规划为主, 会为大家介绍LK, LP以及遗传算法. 敬请期待