mckpath v1.2.6

mckpath readme

这里是path的基础结构(不含tsp) 数据结构放到了testinput.js.

2019-06-03

• 10:44am 测试下stamp是否可以使用getter和setter

2019-05-27

• 12:40am 半夜
  • 重写mpath部分, 加入mplan概念.
  • 并且把所有的计算都围绕时间展开, 都换算成秒.
    • 距离也是秒.
    • 权重也是秒.
  • 白天继续写一下uds-core, 看看mplan的需求.
• 11:04am
  • 写uds-core
  • 然后看线性规划.

2019-05-25

• 4:20pm
  • 拨开迷雾, mpath也要遵守模式, 从自身创造自身.
• 4:32pm
  • 改造完成.

2019-05-24

• 10:49am
  • path不需要知道tsp. 只要调用tsp计算最佳方案就好了.
  • tsp需要知道path的数据结构.

2019-05-23

• 9:54am
  • 两种情况, 一种要做内部判断, 一种做外部判断. 依赖于path数据结构.
  • 点和订单的关系维护在点上有问题, 还是应该维护在q上, 然后在path里面保持一个对q的引用.
  • q的进度直接受外部参数的影响才可以.
  • q本身不该维护列车游标, 这个游标彻底由外部维护. q只是读取指定位置就好了.
  • 貌似这样分析, 不需要rdq了, 只要visibledot就可以了.
  • 然后, 就用… , pop, shift, push等等数组操作解决问题了.
  • visibeldot有三个数据结构
    • qs, 一个点队列数组.
    • trains, 点队列的游标数组. 如果直接处理点队列, 那么这个可以去掉.
    • keys, 可以访问的点, 如果直接操控qs, 那么这个可以省略.
• 11:39am
  • Point 不能彻底静态化, 因为他还是要记录自己的原始Q的状态.
  • point.dad, point.no, point.s=静态引用.
• 2:14pm
  • 最小生成树 + 线性规划可以解决时间窗口问题.
  • 最小生成树做排序用. 如果线性规划无法规划出来, 那么这个人就是不能送这一单.
• 3:42pm
  • train测试成功.
  • 不对, 新建train的测试还没做.
• 4:13pm
  • 构思mpath. udscore, mpath, mcktsp, 看一遍. 捋一下思路.
  • travel知道path, 拿到path的数据结构做遍历.
  • udscore知道path和travel, 安排tsp遍历path, 生成path.
  • mpath把自己作为参数传给tsp, tsp计算出最终合理的path.
• 10:38pm
  • mpoint和train验证了, 没问题了.
  • mpath要能够根据数据结构, 构造train.
• 11:35pm
  • mpath测试通过.
  • 后面写好travel和judge就好了.

2019-05-22

• 11:46am
  • visibledot不适合批量插入q, 因为每个q都有一个position的情况.
• 1:56pm
  • 遍历, 每次都保留当前局面. 顺序访问可以访问的点.
  • 然后, 在访问了某个点的情况下, 进入下一个局面.
• 3:14pm
  • 改变思路, visibledot必须用自身的数据结构初始化, 否则可以初始化一个空的, 然后再付入点队列.
• 8:02pm
  • visibledot内部是没有状态的, 内部的q各自维护自己的状态. visibledot只要能维护好自己的每个q的可访问点就好了.

2019-05-22之前

技术框架

• 全部使用stamp写法, 用sm前缀.
• 用es6 module做.

path的关系

• 所有的司机的basepath到达这个新的点的权重.

业务思路:

• 如果没有大规模重分机制, 那么算法毫无意义.
• 如果要启动大规模重分机制, 那么需要软件的导航机制, 需要这个软件是持续使用保持在前台的.

重大突破

• 用树的深度遍历长度来作为计算依据.
• driver->bus, 不再考虑订单, 他不需要知道任何订单的信息. 他只要维护自己的basepath和leftpath就好了.

整体规划:

• 有一个函数getpath, 在sa数据结构中定义了.
• 他的参数和返回值都是一个数据结构: path, 这个定义在核心数据里面.

-------------------------------不确定内容--------------------------------

整体思路有疑问: todo

• 司机和路径形成矩阵关系.
• 每次选出最短路径做分配. 这个是克鲁斯卡尔思路.

一个核心思考:

• 判断是放到每个路径中. 还是放到最终权重判断的时候?
• dijkstra是否可以让我一次把所有司机的权重算出来?