本节我们将结合一个具体实例，介绍求解带道路容量限制的多配送中心选址问题的算法。

某连锁企业的需求点分布在江苏省的20个城市（见表3-13）。为了提高服务效率、降低物流成本，该企业决定在省内最多建立3个物流配送中心。配送中心备选点位置分别在灌云县、宿迁市、淮安市、高邮市、宝应县、南通市、高淳县、溧水县。各个需求点对应的序号及年需求量见表3-13，货物在各配送中心备选点的单位周转费用、年固定费用见表3-14，从生产基地到配送中心备选点的单位运输费用见表3-15，从配送中心备选点到需求点的单位运输费用见表3-16。两个生产基地每年的最大生产量见表3-17，表3-18和表3-19分别列出了从生产基地到配送中心备选点、从配送中心备选点到需求点的道路容量限制。问如何从8个配送中心备选点中选择最多3个建立配送中心，使得总费用最低？

表3-13 需求点对应序号及年需求量

表3-14 各个配送中心备选点的单位周转费用和年固定费用

表3-15 从生产基地到配送中心备选点的单位运输费用 （单位：元/t）

表3-16 从配送中心备选点到需求点的单位运输费用 （单位：元/t）

表3-17 生产基地的最大年产量

表3-18 从生产基地到配送中心备选点的道路容量 （单位：t）

表3-19 从配送中心备选点到需求点的道路容量 （单位：t）

（续）

1.精确算法

由于带道路容量限制的多配送中心选址问题可以表示成一个整数线性规划模型，利用Lingo软件编程可以直接求解该模型，得到问题的精确最优解。对于例题的模型，利用Lingo软件编程求解，得到的最佳选址结果是建立3个配送中心，分别在宝应县、南通市和溧水县，总费用为2344988.4元，具体配送方案见表3-20、表3-21和图3-2。表3-20列出了从生产基地到配送中心的货物配送情况，表3-21列出了从配送中心到需求点的货物配送情况，图3-2则描述了各个配送中心及需求点的相对位置及货物配送关系。

表3-20 利用精确算法求出的从生产基地到配送中心的货运量 （单位：t）

表3-21 精确算法求出的从配送中心到需求点的货运量 （单位：t）

图3-2 精确算法的选址结果

注：图3-2中未画生产基地。其中9、13、16为选定的配送中心，其余为需求点。若某个需求点只需要一个配送中心提供配送服务，则使用一种图标表示，并在该需求点与配送中心之间连线；若某个需求点需要由两个配送中心提供服务（如镇江市、泰州市、南京市、常州市和无锡市），则使用两种图标表示，并分别在该需求点与两个配送中心之间连线。

2.启发式算法

按照启发式算法的基本思想，可将物流配送中心选址问题的求解过程划分为两个阶段。首先，根据配送中心备选点到需求点的道路容量、单位运输费用以及配送中心备选点的年固定费用等选择配送中心位置，并确定各个配送中心的配送服务范围及相应的配送量；然后，计算各个配送中心的总配送量，根据生产基地到配送中心的道路容量限制、生产基地的生产能力限制等确定生产基地为配送中心配送货物的数量。(www.daowen.com)

启发式算法的基本步骤：

第一步，根据备选点到需求点的道路容量选取配送中心，并初步确定各个配送中心的配送服务范围及配送量。

1）对于每个需求点j，计算出各个配送中心备选点到该需求点的道路容量，并统计非零道路容量配送线路的条数S_j（S_j表示可为需求点j提供配送服务的备选点个数），选出S_j最小的需求点j。

2）为S_j最小的需求点j选取配送中心，选取的原则主要有以下几点：

若只有一个配送中心备选点i可单独满足需求点j的需求量（指配送中心备选点i到需求点j的道路容量不小于需求点j的需求量），则选定备选点i建立配送中心，并确定备选点i为需求点j配送货物的数量等于需求点j的需求量。

若有多个配送中心备选点均可单独满足需求点j的需求量，比较各个备选点对应的可服务需求点个数以及总配送量，选择可服务需求点个数最多（或总配送量最大）的备选点；若有多个备选点对应的可服务需求点个数同时达到最大（或总配送量同时达到最大），则比较各个备选点对应的单位总费用（单位产品的周转费+单位产品的年均固定费用+该备选点与需求点j之间的单位运费），选择单位总费用最小的备选点建立配送中心，并确定该配送中心为需求点j配送货物的数量等于需求点j的需求量。

若没有配送中心备选点可单独满足需求点j的需求量，则根据单位总费用（单位产品的周转费+单位产品的年均固定费用+备选点与需求点j之间的单位运费）从小到大的顺序，依次选择单位总费用最小的两个或多个备选点作为选定的配送中心，并按单位总费用由小到大的顺序依次确定各个配送中心到需求点j的配送量，即首先将单位总费用最小的线路安排满，再安排单位总费用次小的线路的运量，依次类推，直到需求点j的需求量全部得到满足为止。

3）对于2）中选定的配送中心，检查其对应的其他可服务需求点，并尽可能安排该配送中心为各个需求点提供配送服务，同时确定相应线路上的配送量。

4）检查各个需求点，若某需求点的需求量已经全部由选定的配送中心满足，则划去该需求点；若某需求点的部分需求量已经由选定的配送中心满足，则修改该需求点的需求量（即从原需求量中减去已经由选定配送中心满足的部分）。

5）将已经选定的配送中心从备选点中划去，按照修改后的需求量返回1）继续进行计算。

重复步骤1）～5），直到所有需求点的需求量均得到满足为止。

第二步，对第一步得到的初始配送方案进行调整，以降低配送运费。对于每个需求点，根据各个选定的配送中心到该需求点的单位运费，调整选定的配送中心为该需求点配送货物的路径及配送量，即根据单位运费由低到高的顺序重新安排相应线路上的货物配送量，优先在单位运费低的线路上安排配送量。

第三步，针对前两步选定的配送中心，根据生产基地的生产能力和从生产基地到配送中心的道路容量限制确定从生产基地到各个配送中心的货物配送量。对于每一个选定的配送中心，先根据各个生产基地到该配送中心的单位运输费用选择一条单位运费最小的配送路线，尽可能多地在该条路线上安排配送量，如果在该条路线上全部安排满（即实际安排的运量达到道路容量上限或生产基地的生产能力达到上限）也无法满足配送中心需要提供的总配送量，则继续选择下一条单位运费最小的配送路线，再在该条路线上尽可能多地安排剩余的配送量，依此类推，直到该配送中心需要提供的总配送量全部得到满足或所有配送路线的运量均已达到上限（或对应生产基地的生产能力已经达到上限）为止。

第四步，计算各个配送中心从生产基地得到的货物数量，若所有配送中心从生产基地得到的货物总量均等于需要由该配送中心提供的总配送量，则已经找到问题的近似最优解，计算结束。否则，若某个配送中心从所有生产基地得到的货物总量小于需要由该配送中心为需求点提供的总配送量，则说明需要由该配送中心提供的总配送量超过该配送中心的配送能力限制。

第五步，将超过配送中心配送能力限制部分的配送量调整给另外两个选定配送中心中的一个，并相应调整生产基地到配送中心以及配送中心到需求点的配送量。调整的方法是：检查该配送中心服务范围内的需求点（已经由该配送中心提供配送服务的需求点），选择其中可以由其他选定配送中心提供配送服务的需求点（在满足道路容量限制的前提下），利用这些需求点对应的配送路径，将超出配送中心配送能力限制部分的配送量调整给其他的选定配送中心并修改生产基地到相应配送中心以及配送中心到需求点的配送量。对于有多种调整方案的，通过比较调整后的运费增加量，选择调整后运费增加量最低的方案。

利用启发式算法对例题进行求解。

首先根据算法第一步求出配送中心选址位置及初始配送方案（计算过程略），见表3-22。

表3-22 由启发式算法第一步得到的配送中心位置及初始配送方案

再根据算法第二步，对初始配送方案进行调整，得到调整后的配送方案见表3-23。

表3-23 调整后配送中心为各个需求点配送货物的数量 （单位：t）

根据算法第三步，确定从生产基地到各个配送中心的货物配送量。结果见表3-24。

表3-24 从生产基地到选定的配送中心的货物配送量、各配送中心需要提供的总配送量 （单位：t）

根据算法第四步判断，需要将超出配送中心13的配送能力部分的10t货物调整给配送中心9或者16。

根据算法第五步，通过计算各种可行调整方案对应的费用增加量，确定出最佳调整方案是将原来由配送中心13配送给需求点12的10t货物调整给由配送中心9提供。调整后的具体配送方案与精确算法得到的配送方案完全相同。