节约里程法

基本原理

节约里程法的基本思路是：已知O点为配送中心，它分别向用户A和B送货。设O点到用户A和用户B的距离分别为a和b，用户A和用户B之间的距离为c。现有两种送货方案：方案(a)中配送距离为2(a+b)，方案(b)中配送距离为a+b+c。由三角形几何性质可知，a+b－c＞0，因此方案(b)优于方案(a)，节约了(a+b-c)的里程。这种分析方案优劣的思想就是节约里程法的基本思想。

核心思想与应用

节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。

以宝洁公司广州配送中心为例，该公司客户分布在全国各地，以广东省内7家客户及省外一家特殊客户的一次配送为例。配送中心提供三种车型，载重量分别为2吨、5吨和8吨，不同车型的运输单价不一样。通过节约里程法进行优化，初始方案使用4辆2吨和4辆5吨的车，运输线路总距离1768公里，总运费4476.3元。经过多次线路优化，最终方案将部分客户合并线路，总距离降至1047公里，总运费降至3384.55元，节约里程721公里，节约成本1091.75元。