优化地面布局
仓库布局: 存储与移动的几何
一个仓库是一个几何优化问题。每平方英尺都是存储(持有产品的货架)或移动(人和叉车的走道)。这个权衡是基本的:走道宽度越宽,移动越容易但存储空间越少。走道宽度越窄,存储空间越多但需要特殊(昂贵)的设备。
标准走道宽度:
- 常规叉车: 11-13英尺(叉车需要有足够的空间来转身与托盘)
- 达到车: 8-10英尺(臂部延伸到达货架)
- 非常窄走道(VNA): 5-6英尺(专用转体车,昂贵但最大化存储空间)
拣货路径策略: 工人按照收集物品的几何路线:
- S-图案(S-pattern): 进入每个走道,沿着走道的全长旅行,从其他端退出。简单但访问了每个走道即使只需要在那里取一件物品。
- 最大的间隙: 只进入有需要拣货的走道。如果走道中没有拣货,跳过走道。Within an aisle, turn around at the largest gap between picks instead of traveling the full length.
- 交叉码头: 对于直接从收货转移到出货的物品:跳过存储。交叉码头布局将收货和出货码头放在相反的两侧,中间有一个明确的路径。
存储密度计算
一个仓库宽200英尺长400英尺(总面积80,000平方英尺)。当前布局使用常规叉车,走道宽12英尺。货架深4英尺(每侧单个托盘深度)。布局交替:货架,走道,货架,走道。
每个rack-aisle-rack单元为: 4 (货架) + 12 (走道) + 4 (货架) = 20英尺宽。
立方利用率和箱子装配
堆叠：每个拖车的3D几何
北美的标准货架尺寸为 48英寸×40英寸（GMA货架）。这是在物流几何中的基本单元。
立方利用率衡量如何有效地填充空间：实际产品体积除以可用体积。一个重量满的拖车但体积只占一半的拖车有低的立方利用率。一个装满天花板的拖车有优秀的立方利用率。
柱状堆叠：每层都相同，箱子直接叠放在一起。结构上较弱但使用空间效率高。
交错（扭曲）堆叠：交替层旋转90度。比柱状堆叠更稳定但会在边缘创建void，浪费5-15%的货架面积。
集装箱装载是真正的几何挑战：将各种大小的矩形箱子放入40英尺的集装箱（内部尺寸约为39'5"×7'8"×7'10"）。这是在计算机科学中的经典NP-hard问题之一：3D箱子装配。没有算法可以在合理的时间内为大型实例提供最优解。
在实际操作中，物流公司使用启发式方法：首先放置最大的物品，先填充地面面积再堆叠高度，根据目的地效率将物品分组。
货架装载效率
你需要将长12英寸、宽10英寸、高8英寸的箱子放入标准的48"×40"货架。最大堆叠高度为48英寸。
为什么路线优化变得困难
旅行推销员问题（TSP）
假设你必须访问10个客户并返回你的基地。什么是最短的路线？这就是旅行推销员问题：数学和计算机科学领域中最受关注的问题之一。
!【TSP 路线：最近邻居 vs 2-opt](/static/diagrams/geometry_tsp_routes.svg)
难点在于组合爆炸。对于N个停靠点，有(N-1)!/2个唯一路线（除以2因为顺时针和逆时针的距离相同）。
- 5个停靠点：12条路线：在毫秒内检查所有它们
- 10个停靠点：181,440条路线：计算机仍然可以承受
- 15个停靠点：43.6亿条路线：需要数小时
- 20个停靠点：60.8万亿条路线：需要数百年
- 50个停靠点：比可观察宇宙中的原子更多
TSP是NP-hard：没有已知的算法可以在多项式时间内解决。随着N的增长，精确解决方案变得不可能，我们必须使用启发式算法：快速找到好的（但不一定是最优的）解决方案的算法。
常见启发式算法：
- 最近邻居：从当前位置，始终去访问但未访问的最近停靠点。速度较快，但通常会产生有很多交叉的路线
- 凸包插入：首先使用外部停靠点（凸包：几何边界）。然后将内部停靠点一个接一个地插入，直到它们添加的距离最小。
- 2-opt改进：在完成的路线上尝试交换边对。如果移除两个边并重新连接使路线更短，保留更改。直到找不到改进为止重复。
启发式算法vs精确解决方案
一个配送公司今天有12个停靠点。他们的驾驶员使用最近邻策略：在每个点上，前往最接近未访问的停靠点。
区域、密度和车辆路线问题
最后一英里配送：几何与经济学的交汇点
最后一英里：从配送中心到客户门steps的路程，占总运输成本的40-50%。这是供应链中几何约束最严重的部分。
从仓库辐射出的径路：配送车辆从一个中心配送中心辐射出。每辆车的路线应该覆盖一个紧凑的地理区域：不允许两辆车相互交叉。
配送密度 决定了一切。在拥挤的城市地区，一辆车可能在8小时内完成150次配送。在农村地区，一辆车可能完成20-30次。几何原因：城市停靠点紧密相连（短途车辆间的距离），而农村停靠点相隔较远。
基于区域的路线 将服务区域划分为地理集群。每个区域分配给一辆车。好的区域应该是紧凑的（大致圆形或方形）和连续的（没有间隙或孤立的小袋子）。目标：最小化总距离，同时确保每条路线都在时间/容量限制内。
车辆路径问题（VRP） 将 TSP 扩展到多个车辆。给定一个仓库、N 个客户和 K 辆货车（每辆车有载货能力和时间限制），将客户分配给货车，并为每辆车编排路线，以最小化总距离。车辆路径问题也属于 NP-hard 类别。
一个设计得当的区域图会使得每个驾驶员的路径形成一个 紧凑的几何形状：一个从仓库延伸出的粗糙的圆形或lobe。如果您看到一个路径自交或与另一个驾驶员的区域重叠，说明路线效率不高。
区域设计
一个配送公司位于城市中心的仓库运营。他们有 4 名驾驶员和 200 个订单，涵盖一个大约为 10 英里半径的圆形服务区域。