物流/路径规划类任务中有两个核心问题, 很不幸, 都是NP完全性问题.

  1. 分团问题, 把一个团中的联通定点分成团.
  2. 货郎担问题(又名旅行商问题), 简单的说就是找到最短的汉密尔顿路径.

这两个问题如果是解决地表运输(包括航运), 那么经纬度距离计算就成为一个大问题. 100个点就需要100*99/2, 大约5000次计算, 如果点数更多, 计算量就会更大, 虽然我们可以用丰巢六边形进行分割, 限制计算量范围, 但是, 基础计算几百几千个点还是很正常的. 一个中等规模的仓库里面sku都会有几千个, 而这几千个其实是不能用六边形分割的, 他们必须是全联通的.

  • 经度就像是橘子, 一瓣一瓣的.
  • 纬度不同纬度是顺着切的, 类似我们切土豆片.
  • 因此纬度每度的公里数都可以理解为一样的(不考虑地球其实是椭圆).
  • 经度每度的公里数就需要考虑纬度因素了. 在北纬90度, 那个地方经度多少度对应的公里数就都是0了, 因为理论上那是一个点.

IMG_3253

IMG_3253

为啥是cos, 画个图就明白了, 原点为o.
oc/od=oc/oa
这其中 od=oa=地球半径
线衫oc/oa=cos(30)