小一笔记（18）：TSP——让每一次配送少走冤枉路

大家好，欢迎来到IT知识分享网。

分享兴趣，传播快乐，增长见闻，留下美好！

亲爱的您，这里是LearningYard新学苑。

今天小编为大家带来文章

“小一笔记（18）：TSP——让每一次配送少走冤枉路”

欢迎您的访问。

Share interest, spread happiness, increase knowledge, leave a beautiful!

Dear, this is LearningYard Academy.

Today Xiaobian brings you an article

“Xiaoyi Notes (18): TSP–Let every delivery go the wrong way less”

Welcome to your visit.

一、TSP概念 The concept of TSP

旅行商问题（Traveling Salesman Problem，简称 TSP）听起来像一道数学谜题，却是物流人每天都在面对的“送货车该怎么走”。它把复杂的现实场景抽象成一句话：一辆车从仓库出发，必须拜访完所有客户并回到起点，怎样规划路线才能总里程最短、耗时最少、成本最低。

The Traveling Salesman Problem (TSP) sounds like a mathematical puzzle, but it is the “How should the delivery truck go” that logistics people face every day. It abstracts complex real-world scenarios into one sentence: when a car departs from the warehouse, it must visit all customers and return to the starting point. How to plan the route can have the shortest total mileage, the least time-consuming, and the lowest cost.

二、TSP分类 TSP classification

在真实业务里，TSP并不会一成不变。如果城市里有单行线，去程和回程的距离就不对称，于是出现了非对称 TSP；如果客户只能在上午九点到十一点收货，迟到就要赔偿，那就成了带时间窗的 TSP；而当车辆载重有限，无法一次性装下全部订单，我们又得把问题拆分成若干子路线，形成容量约束的 TSP。正是这些变体，让 TSP 能够贴切地对应物流中的不同痛点。

In real business, TSP will not be static. If there is a single line in the city, the distance between the outbound and the return journey is asymmetric, so there is an asymmetric TSP; if the customer can only receive the goods from 9:00 to 11:00 in the morning, and compensation is required for lateness, it becomes a TSP with a time window; and when the vehicle load is limited and it is impossible to place all orders at once, we have toThe problem has to be split into several sub-routes to form a TSP with capacity constraints. It is these variants that allow TSP to aptly correspond to different pain points in logistics.

三、TSP价值 TSP value

把 TSP 用在物流系统规划，价值体现在三个层面。战略选址阶段，把候选仓到所有门店的最优闭环算一遍，就能直观看出哪些仓“辐射半径”太大，直接筛掉；战术排线阶段，每天清晨把当天订单扔进算法，十几秒就能给出司机手中的路线图，平均里程可立即下降一成左右；而当临时加单、交通管制等突发状况出现时，实时 TSP 插入算法能在毫秒内重算局部路径，确保司机始终走最顺的路，不再凭经验绕圈。

When TSP is used in logistics system planning, the value is reflected in three levels. In the strategic location selection stage, calculate the optimal closed loop from the candidate warehouse to all stores, and you can intuitively see which warehouses have too large “radiation radii” and screen them out directly; in the tactical routing stage, the order of the day is thrown into the algorithm every morning, and the road map in the driver’s hand can be given in ten seconds, on average.The mileage can be immediately reduced by about 10%; and when emergencies such as temporary order increases and traffic control occur, the real-time TSP insertion algorithm can recalculate the local path within milliseconds to ensure that the driver always takes the smoothest path and no longer circles empirically.

面对不同规模的数据，算法的选择也有讲究。节点在 100 以内，用整数规划模型配合 Excel 的 Solver 即可跑出全局最优；节点上千时，经典的 2-opt 改进再叠加 LKH 启发式，误差通常能控制在 1% 以内；若节点过万，则先用聚类把区域切开，再对每个子区域跑 TSP，最后把结果拼起来，既省算力又能保持高质量。

In the face of data of different sizes, the choice of algorithms is also particular. If the node is within 100, the integer programming model can be used with Excel’s Solver to run out the global optimization; when the node is in the thousands, the classic 2-opt improvement is superimposed on the LKH heuristic, and the error can usually be controlled within 1%; if the node is over 10,000, the area is cut by clustering first, and then the area is cut.Run TSP in each sub-region, and finally put the results together, which saves computing power and maintains high quality.

要让 TSP 真正落地，数据、约束和闭环缺一不可。精确的经纬度、实时路况、每站卸货时长必须全部到位，才能避免“纸上谈兵”。把迟到罚金、早到等待成本写进目标函数，算法就会在“快”与“省”之间自动权衡。更进一步的数字孪生每月跑一次仿真，把真实运营数据再喂回模型，路线就能像生物进化一样持续优化。

For TSP to truly land, data, constraints, and closed loops are indispensable. Accurate latitude and longitude, real-time traffic conditions, and the length of unloading time at each station must all be in place in order to avoid “talking on paper.” Write the penalty for lateness and the cost of waiting for early arrival into the objective function, and the algorithm will automatically weigh between “fast” and “save”. Further, the digital twin runs a simulation once a month, feeds the real operation data back to the model, and the route can be continuously optimized like biological evolution.

一句话总结，TSP 并不只是数学家的游戏，而是把“少跑、快跑、准时跑”翻译成算法语言的日常工具。当你下一次看到司机顺畅地完成最后一单并提前回到仓库，背后很可能就是 TSP 在默默发挥作用。

To sum up in one sentence, TSP is not just a game for mathematicians, but a daily tool for translating “run less, run fast, and run on time” into algorithmic language. The next time you see the driver smoothly completing the last order and returning to the warehouse early, it is likely that TSP is silently playing a role behind it.

今天的分享就到这里了

如果您对今天的文章有独特的想法

欢迎给我们留言

让我们相约明天

祝您今天过得开心快乐！

That’s all for today’s sharing.

If you have a unique idea about the article

please leave us a message

and let us meet tomorrow

I wish you a nice day!

文案|ls

排版|ls

审核|yue

参考资料：物流系统规划与设计（第三版），李浩、刘桂云编著，kimi

翻译来源：ChatGPT

本文由LearningYard新学苑整理并发出，如有侵权请在后台留言！