视频字幕
节约里程法是解决车辆路径问题的重要启发式算法。传统配送方式中，每个客户都需要单独配送，车辆需要往返配送中心多次。而节约里程法通过合并配送路径，将多个客户安排在同一条路线上，从而显著减少总的行驶里程，提高配送效率。
节约值是节约里程法的核心概念。计算公式为S(i,j)等于配送中心到客户i的距离加上配送中心到客户j的距离，再减去客户i到客户j的距离。在这个例子中，配送中心到两个客户的距离都是5，客户之间的距离是3，因此节约值为7。节约值越大，说明合并这两个客户的路径能节省更多里程。
节约里程法的算法流程包括四个主要步骤。首先计算所有客户对的节约值，然后按节约值从大到小排序。接下来依次检查每个客户对是否可以合并到同一条路径中，最后更新路径直到所有客户都被安排完毕。该算法的时间复杂度为O(n²log n)，其中n是客户数量。
现在通过一个具体例子演示节约里程法的计算过程。我们有5个客户和一个配送中心，距离矩阵显示了各点之间的距离。首先计算所有客户对的节约值，比如客户1和2的节约值为8加6减4等于10。计算完所有客户对后，按节约值降序排列，最大的是客户对1和2的节约值10。
根据排序后的节约值列表，我们开始构建路径。首先选择节约值最大的客户对1和2进行合并，然后选择客户对1和4，接着是客户对2和3。由于客户对3和4会形成环路，所以不能合并。最终形成两条路径：路径1包含客户1、2、3，路径2只包含客户4。这样就完成了整个节约里程法的路径构建过程。