陈小丽， 曲 媛， 肖 鸿

(1．同济大学铁道与城市轨道交通研究院，上海201804;2．上海市城市建设设计研究总院，上海200125;3．北京交通大学交通运输学院，北京100044)

0 引言

配送是物流活动中直接与消费者相连的重要的环节，在物流的各项成本中，配送成本占了相当高的比例[1]．因此，配送线路是否合理直接影响着配送的速度、成本和效益等，如何科学合理地确定配送活动中的配送线路是一项非常重要的工作．

目前烟草行业的很多商业企业已经实行由物流中心直接配送到户的对接配送模式．本文针对宜春市烟草公司各分公司的需求情况、道路交通网、企业车辆及运行限制等因素进行了较充分的分析，利用节约里程算法对公司的配送区域和线路规划进行设计与优化．结果较为理想，可降低运输成本，提高效益．

1 节约算法

节约算法是用来解决运输车辆数目不确定的VRP问题，它是迄今为止用来解决VRP模型最常用的一种启发式算法．

节约算法主要步骤

基本条件:已知车辆的集合NT={1，2，…，m}，各车辆最大载重量为Wi，各配送节点组成的点集为NR={1，2，…，n}，各节点的需求量为Ri，各个节点之间的最短距离为cij．

(1)将车辆按照最大载重量从大到小依次排序，满足W1≥W2≥ … ≥Wi≥ … ≥Wn．

(2)计算所有的客户对(i，j)的节约里程的Δcij值，其中

将其中大于0的Δcij从大到小依次排成队列．

(3)求可行解．确定各车辆的配送点集I1，I2，…，Im，令Ij={j}，(j=1，2，…，n)(先对各点进行单点配送)．

(4)合并配送路径．直到节约里程Δcij的队列空为止，重复下列步骤:按照节约里程Δcij队列从大到……