《旅行商二元交换与时间窗车辆路径、东京大阪首尔扫货路线最短闭环与专柜开门时间窗母典》各章定量结论
替门店与私域客户在东京、大阪、首尔扫货的买手,最常见的排线办法是由近及远。本书证伪这个做法背后的两个信念:由近及远的路线不会比最短闭环差多少;一天的件数主要取决于路走得够不够短。书中用旅行商问题的最近邻、二元交换(2-opt)、段移位(Or-opt)与 Held-Karp 动态规划量出距离上的差距,再用带时间窗的车辆路径模型量出专柜开门、限量时段与排队对件数的影响。书中的坐标、专柜、营业时段、排队时长与限购件数均为示意,不对应任何真实店铺;全部计算由书中程序生成;本书是非个人化经营建议,跨境所购物品须按各地海关规定如实申报并遵守限购规定,书中不讨论任何规避做法。
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-298 · English version
- 第 1 章 · 由近及远的代价:最近邻路线比最短闭环长多少
第一章核实并修正立项蓝图:文献里最近邻「约高出四分之一」是大规模实例上相对于 Held-Karp 下界的超出;在十站规模上,最近邻只比精确最优平均长 0.092,到六十站才比下界高 0.2501。 - 第 2 章 · Croes 的二元交换:反转一段路、交叉与局部最优
二元交换拆掉两段腿、换上两段、把中间一段倒过来走,只要总长下降就接受。东京示意日上,五步交换把 25.51 公里缩到 20.99 公里,增益依次是 1.52、0.06、0.99、0.10 和 1.85 公里。平面上交叉的路线一定可以改短,但没有交叉的路线可以很差,最近邻就是一个零交叉却长两成的例子。在 200 张随机的十站日上,最近邻起点的二元交换平均只比最优长 0.0093,20 个随机起点取最好者有 0.990 的日子落在最优上。… - 第 3 章 · 段移位与单行道:Or-opt 邻域与非对称行程
段移位把一到三家连续的专柜整段挪到别处,补上了二元交换做不到的那一类改进。示意大阪日上,二元交换停在 23.41 公里、超出 0.070,段移位四步走到 21.93 公里,只比精确最优的 21.89 公里长 0.002。300 张十站日上,两者交替使用平均只超出 0.0009,最坏一天 0.042。行程不对称时,对称增益公式会把近一半的交换做错,朴素二元交换在 3859 次交换中有 1893 次让路线更慢;只做正向段移位就能避开这个陷… - 第 4 章 · Held-Karp 动态规划:精确解、状态数与「高出下界」
Held-Karp 动态规划只记「去过哪些、停在哪里」,把穷举的阶乘降到 $n^2 2n$ 量级。示意首尔日的九站闭环,动态规划用 9216 次扩展、穷举用 181440 条闭环,得到同一个 23.2337 公里。十二站时它只有 24576 个状态,二十站时 10485760 个,二十五站时内存要 3355.4 兆字节;一天十五站以内,精确解随手可得。文献里的「高出约四分之一」量的是大规模下相对于 Held-Karp 下界的超出,六十… - 第 5 章 · 专柜的时钟:时间窗可行性与件数最多的一天
第五章是全书的转折:示意东京日上,20.99 公里的最短闭环只买到 12 件,件数最多的方案多走 0.32 公里就买齐 15 件;随机日上,把最近邻换成最短闭环每天只多买 0.03 件,按时间窗排序多买 2.93 件。 - 第 6 章 · 两位买手与随机排队:带时间窗的车辆路径与计划余量
第六章处理两位买手分工与随机排队的余量:按平均时长排,0.740 的日子全部买到,留两成余量升到 0.915。 - 第 7 章 · 东西方原典考辨:丁谓「一举而三役济」与欧拉的七桥
第七章考辨沈括记丁谓「一举而三役济」(示意账本省下 0.826)与欧拉的七桥。 - 第 8 章 · 实证闭环:扫货路线规划器与预注册检验方案
第八章给出买手日流程、扫货路线规划器与预注册检验方案:距离检验约需 37 个买手日,时钟检验每组约需 55 天。书中以标注框区分已发表的证据、可运行的 Python 计算(19 段程序)、原典与作者的假说。
模型示意算例,非实时报价