---

（北京航空航天大学  经济管理学院，北京100083）

   摘要：建立了“选址一路线”问题的数学模型，并且给出了求解问题的启发式算法。该启发式算法是基于改进的 Clarke－ Wright算法和旅行推销员问题。在账单递送的实际案例中，这种启发式算法，和传统手工方法相比，求解速度更快，同时降低了运作成本，减少了递送时间。

   关键词：选址一路线；Clarke and Wright算法；案例研究

   中图分类号：F224  文献标识碉：A   文章编号：1008－2204（2002）01－0033－05

 

一、引言

在供应链管理中，选址问题是一个非常重要的组成部分，其目的是确定一个或者多个设施的地址，使一些判断标准获得优化的同时（如达到成本最小或服务时间最短的目标），及时向顾客提供其所需的产品和服务。

    Hamers（1999年）把这类问题描述为和中国邮递员问题有关的成本分配问题：中心把产品或服务提供给顾客，一方面希望递送费用低，另一方面还要考虑如何把总成本合理分摊到各个顾客。他采用赋权的连通无向图来描述这个问题，其中边代表具有固定成本的街道，点代表分销中心，服务人员沿着图的边行走，最后回到分销中心。

    从分销中心到各个递送点的具有不同容量卡车的路径优化问题由Clarke and Wright（1964年）首次给出了解的具体描述和算法设计，算法思想是尽量减少循环，从而快速找到最优路径。这一方法至今仍在使用。Hansen等（1994年）提出的启发式方法可以更高效地解决广义的选址一路径问题。其解决方法是将问题分解为三个于问题，然后分别解决。Bookbinder and Reece（1988年）将从工厂到顾客的分销分为一个两阶段过程未考虑：首先是工厂到分销中心，然后是分销中心到顾客，从而将多商品和有能力限制的分销模型归结为一个非线性混合整数规划。Min等（1998年）从算法的发展和模型复杂性方面对以往的选址一路径问题的研究讲展进行了总结。一般地，选址一路径问题包括以下一系列问题：

    （l）建立分销中心的数目；（2）分销中心位置的确定；（3）居民小区怎样和分销中心匹配；（4）确定各个居民小区和其相关的分销中心的路线；（5）居民小区在4中确定的路线上的排列顺序；（6）整个分销链运行的绩效度量的依据，如成本降低和效率提高。下文首先介绍了广义的“选址一路线”问题的定义和基本概念，然后给出了它的数学模型描述，并讨论了启发式算法对干问题的重要意义，最后针对一个具体的案例分析了算法的可行性。

二、模型与算法

    （一）选址一路线问题的定义

    在选址问题中，一个最直接的考虑是顾客直接从分销中心获得产品或服务，如图1所示。这个模型遵从了从中心到每个顾客的出度和入度均为1的原则。

    然而，在很多实际倩况中，分销中心为降低运营成本，往往会考虑花费最少的时间服务最多的顾客，这样，并非每一个顾客分别从中心获得产品或服务，分销中心不一定和每个顾客之间存在一条路径，也就是说，从分销中心出发的一条服务路径可以包括多个顾客。如此，问题变得更加复杂，需要涉及到选址、分配和路径的混合优化问题，如图2所示。

“选址一路径”问题可以描述为：分销中心为顾客提供产品或服务，顾客的数量、地点和需求己知或可以估算，产品或服务到顾客的过程可以是未源干一个或多个分销中心，并且每个顾客只能由一个分销服务；假设候选分销中心的位置己知，每个候选中心的建设成本己知，分销的成本和交通工具的运输距离或时间有关，每个分销中心有能力限制，而且交通工具也有能力限制；“选址一路径”决策就是在确定分销中心的建设地点的前提下，设计从中心到顾客的路线，在满足不超过交通工具的运输能力和时间（如每日8h的工作）的条件下，减少整个建设和分销的成本。

中心1

中心2

 

图1 顾客直接获得服务的分销模型                                        图2 一条路线上多个顾客的分销模型

 

 （二）选址一路线问题的数学模型

    根据不同的约束条件和目标，可以采用不同形式的整数规划或者混合整数规划模型未描述“选址一路线”问题（Hansen，1999年，Tuzun andBurke，1999年），以下是选址一路线混合优化的数学规划模型，可以通过对它的求解未获得问题的解决。

    模型参数：

I=需求节点集

J=分销中心候选地点集合

N＝ IUJ＝所有节点集

K=交通工具集合

h_i=顾客节点i的需求

f_i=选址在候选节点j上的固定成本

c_ijk=采用交通工具k在节点i和节点j之间

    的运输成本

g_k=使用交通工具k的固定成本

uk=交通工具k的容量决策变量:

Xj=1 如果我们选择在候节选点j建立分销中心

  ＝0 否则

_jk=1 如果交通工具k为候选节点j的运输工具

  ＝0 否则

Z_ijk＝1 如果在交通工具k的路线上，节点I是节点j的直接前驱

   ＝0 否则

 

 

    目标函数式（l）是要使整个建设成本、交通工具的租用成本及运输成本之和最小化；约束式（2）表示每个顾客j必须在一条路线上，每个节点前后都只有一个节点（顾客或中心）；流量约束式（3）表明，如果交通工具k从节点i进入节点j，它一定要从节点j离开，到其他节点l。

    约束式（4）是用干防止一个交通工具被分配到需求节点集但不访问一个中心，它要求对干任意的有两个及以上元素的子集G,子集中所有节点间的关联数必须不大干于集的元素数目减一，对干任何一个节点子集，仅访问子集内节点的子路线的关联数等干于集的节点数目。

    约束式（5）和式（6）表明,如果交通工具被分配到始干j的分销中心的路线上，那么流入节点j或流出节点j的至少有一条边；约束式（7）表明，一个交通工具能被分配到始干j点的线路上，当且仅当 j点是分销中心；约束式（8）表示，每个交通工具至多能够被分配到一个设施上；约束式（9）是交通工具的能力约束；最后，式（10）、式（11）和式（12）是整数约束。

    上述表达的问题有8类不同的约束，这样，即使是一个很小的问题，约束数目也将变得很多。式（4）的约束数目最多，因为它作用干需求节点的所有子集。对干一个仅有20个需求节点的小问题，就会有2388个变量和 1049023个约束，Hansen（1996年）列举了整数规划模型表示的不同规模问题的变量和约束数目，认为现实问题的复杂性需要更加快速的计算机、大量的CPU时间和更有效的算法。笔者决定在下文引入启发式算法来求解“选址一路线”问题。

    Step2：针对每个中心节点，通过改进的Clarke-Wright算法确定交通工具的路线。

    Step3：在一条路线中，通过顾客节点间的置换来优化旅行距离。这个内部路线的初始化过程可以通过TSP未实现。

    Step4：通过把当前路线上的顾客节点替代到另一条路线上（single displacement procedure）来减少旅行距离，这是外部路线初始化。它可通过执行改进的Clarke－Wright算法将一条路线上的顾客区域替换到另一条路线上未实现。

    Step5：通过交换不同路线上的两个顾客节点（exchange Procedure）进一步减短旅行距离。这是外部路线初始化，可以通过执行改进的Clarke－Wright算法来交换任意两条路线中的每个顾客区域。

    Step6：在考虑容量和时间约束的同时，通过将一条路线替换给另外的候选中心未减少候选中心数目。

三、案例及计算分析

    （一）案例背景介绍

    C＆W是香港一家通讯服务公司。1999年，公司有3600 000条商用和住宅电话线路，拥有948 000位移动用户和 322 000名因特网和多媒体用户。

    面对大量的顾客群和业务量，帐单递送成为公司的一个大问题。首先，从现金管理的角度未说，公司为了尽早回收资金，帐单应该尽可能早地到达顾客手中；其次，递送的成本给整个运作成本造成了很重的负担。

    近年来，信息技术的发展使得这种倩况有所改善，电子帐单（通过 e－mail和 internet传递帐单）和电子支付（自动支付、自动柜员机和电话支付）等手段己经成功得到实施，但是，出干公司或者个人的一些实际需要，仍有很多顾客愿意接受纸质帐单。

目前的情况是，每月大约有 3000000份纸质帐单需要递送到顾客手中，如果这些帐单全部由邮局递送，按照一份帐单1．2元计算，成本是每月360万元。为了节省这笔巨大的开支，必须设计一种递送帐单的高效方案，以缩减成本、提高服务水平。

    管理部门决定建立内部递送小组，由它把帐单递送到顾客所在的住宅小区。由干住宅小区结构化程度很高、人口密集，因此，这种递送方式是比较有效的，其他地区的帐单仍然由邮局递送。

    目前，内部递送办公室有60名员工未处理帐单，包括打印、分类、包装和递送。工作时间每大8h。帐单通过汽车运送到住宅小区，每辆汽车的最大容量时5 000份，这样九龙地区每月600000份的递送容量基本可以覆盖200多个相关的住宅小区。

    管理部门考虑重新对现有的分发中心进行选择，在现有的公司交易大楼里建立一些递送中心，递送中心每天应该有处理25000份帐单的能力。

    （二）解的质量

    虽然启发式方法给出的解是可行解，而非最优解，但是由干它使用简单、计算快速、易干理解，因此被广泛使用。启发式解的质量可以从以下角度进行分析：管理部门的意见、相对干手工的运作成本、时间的复杂性。用启发式方法得到的路线分配如表1所示。

    1．管理部门意见

    有必要在P3和P4点建立分发中心。因为这两个设施能分别服务城市的东区和西区。根据规划，居民楼（estates）聚集而为小区（ district），小区聚集而为大区（zones）。在每个大区分别建立一个分发中心是很有必要的。

    根据目前的手工处理过程，需要计划同一小区里的居民楼在帐单递送人的路线上如何分配。根据经验，在同一小区通常有3～6座居民楼。一个送信人通常一大能够处理2～3个居民楼。这种规模的问题使得路径选择很简单。这个路线可以通过以下规则未决定。最先分配同一小区中最多帐单量，直到整个帐单数量和旅行时间超过限制为止。表2表示了当前手工方法的路线和的分配。

 

    2．运作成本

    从成本角度未说，启发式算法得出的运作成本和手工方法的比较见表3，因为两种情况都需要建立两个分发中心，固定成本相同；从变动成本来考虑，前者有11条路线，后者有12条路线，启发式方法成本节省了7．5％；同时考虑到前者节约了人力资源成本，启发式方法的效率提高了 9％。

    3．时间的复杂性

    部门经理评价说，即使建立计算的工作簿，手工方法中的重复计算还是非常费事。采用启发式算法，他可以lh内获得求解；采用手工计算却需要3h来进行重复计算。从这个角度说，启发式算法的效率是手工方法的3倍。通过进一步优化计算的方法，启发式算法的效率会更高。

四、结论

    选址一路线问题的设计是一项复杂的任务，涉及到许多因素。开发和应用启发式模型是解决问题的一个简单、快速的工具，计算结果表明，方法是可行的。启发式模型可以通过开发计算机用户界面产生重复结果来进一步提高。随着国际贸易、网上购物和后勤运输概念的增长，各种选址一路线模型和解决算法的应用将成为将来的热点。

    模型还可以进一步考虑更复杂的问题，例如：

    （l）随机需求问题；

    （2）两层次分销选址（生产工厂和分销中心）问题；

    （3）不同时间窗的多产品分销问题；

   （4）多目标问题。

 

参考文献：

[1] Bookbinder J H, Reece K E. Vehicle Routing Considerations in Distribution System Desin[J]. Evropean Journal of Opertional Research, 1988,(37): 204-213.

[2] Clarke G, Wright J W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J]. Operations Research, 1964,(12):568-581.

[3] Hamers H. Cost Allocation in the Chinese Ostman Problem[J].European Journal of Operational Research, 1999,(118):153-163.

[4]Hansen P H, Hegedahl B, Hjortkjaer S, et al. A Heuristic Solution to the Warehouse Location-routing Problem[J]. European Journal of Operational Research, 1994,(76):111-127.

[5] Min H, Jayaraman V, Srivastava R. Combined Location-routing Problems:A synthesis and Future Research Direction[J]. European Journal of Operational Research,1998,(108):1-15.

[6] Moore G C, Re Velle C. The Hierarchical Service Location Problem [J]. Manage  Science,1982,(28):775-780.

[7]Ree S, Yoon B S. A Two-stage Heuristic Approach for the Newsparer Delivery Poroblem[j]. Computer Industrial  Engineering,1996,(30):501-509.

[8]Srivastava R, Benton W C. The Location-routing Problem:Consideration in Physical Distribution System Design[J]. Computers Operations Research,1990,(17):427-435.

[9]Tuzun D, Burke L I. A Two-phase Tabu Search Approach to the Location Routing Problem[J].European Journal of Operational Research,1999,(116):87-99.

[10]Welch S B. The Obnoxious p Facility Network Location Problem with Facility Interaction[J]. European Journal of Operational Research,1997,(102):302-319.

 

                            Modeling and Algorithm of Location-routing Problems

ZHANG Jing, LIU Lu, CHEN An

(School of Economics and Management, Beijing University of Aeronautics and Astronautics, Beijing 100083, China)

Abstract: A mathe matical model to solve location-routing problem is worked out and the heuristic algorithm proposed with the latter based on TSP and Modified Clarke-Wright saving algorithm. In the case of bill delivery, the optimised heuristic algorithm, compared with the traditional method, can acquire satisfactory solutions more quickly with the lowering of the operating cost and saving of the delivery time.

Key words: location-routing; Clarke and Wright algorithm; case study

收槁日期：  2001－  06－  12

基金项目：国家自然基金资助项目NSFC-RGC(7991061987）;教育部博士点资助项目（2000000601）

作者简介：张静（1977－），女，湖北沙市人，硕士研究生