邵俊岗，郑芳瑜

(上海海事大学水运经济科学研究所 上海201306)

0 引 言

在商品经济高速发展的今天，高效的集中、分销、配送显得尤为重要.不同的商品必须由仓库分销到各个零售商:牛奶企业到不同的奶农处收购牛奶，面包必须从仓库发出到不同的零售商店或超市，不同小区的垃圾也要由车辆运送至垃圾处理厂.因此，若能对货物做到有效地集中和配送便能使库存保持在一个较低的水平，更能节省资源和能源，使世界发展更加可持续化.

根据最新口径下的《2013 年中国物流运行情况通报》［1］，2013 年全国范围内消耗的物流总费用约10.2 万亿元，同比上年增长了9.3%，约占GDP的18%.特别突出的是运输费用一项，高达5.4 万亿元，在物流总费用中的占比搞到52.25%之多.由此，降低物流成本显得重要且迫切，而对车辆运输路径的优化正可以降低运输费用.

如果面包厂要向11 个不同的杂货店配货，理论上可能的不同路径可达39 916 800(=11!)，在短时间内很难找到最经济的优化方案.当只看线路图可以排除过长的路线，但要想找到最短路线是远远无法达到的.本文介绍了著名的运用于运输路线优化问题的传统Clarke－Wright 节约算法和允许分割配送的节约算法，针对Clarke－Wright 节约算法下运输车辆数目已经最优的情况，允许分割配送的节约算法不再适用，本文提出了对传统节约算法进行连接点优化的方法来解决这一问题.

1 传统节约算法

1.1 节约算法原理

Clarke G.和Wright J.W.在1964 年率先提出了Clarke－Wright 节约算法，目标为路径最短……