物流节点动态布局优化模型及其求解算法研究＊

张得志，李双艳

(1.华中科技大学 管理学院，湖北 武汉 430074;2.威胜集团 物流中心，湖南 长沙 410205;3.中南大学 交通运输工程学院，湖南 长沙 410075)

物流节点动态布局优化模型及其求解算法研究＊

张得志1，2，3，李双艳3

(1.华中科技大学 管理学院，湖北 武汉 430074;2.威胜集团 物流中心，湖南 长沙 410205;3.中南大学 交通运输工程学院，湖南 长沙 410075)

在分析物流节点定义及其布局内涵的基础上，针对本文所研究的物流节点系统结构特点，构建了多时期、多物流节点、多种类型物流的物流节点系统动态布局优化模型，该模型考虑物流节点建设固定成本、物流处理费用和物流节点的规模经济效益等因素。针对该模型的特点，设计了基于扩展最小费用最大流的混合遗传算法。

物流节点;动态选址;优化模型;启发式规则;遗传算法

物流节点，是物流网络中连接物流线路的结节之处［1］。广义的物流节点是指所有进行物资中转、集散和储运的节点，包括港口、空港、火车货运站、公路枢纽、大型公共仓库及现代物流(配送)中心、物流园区等。狭义的物流节点仅指现代物流意义的物流(配送)中心、物流园区和配送网点。

物流节点布局就是在区域范围内部确定不同物流节点(物流园区、物流中心、配送中心等)的规模、数量、功能;以及物流节点之间的协调、物流节点与物流需求之间的协调等。本文主要研究区域内容不同时期物流节点中的物流量的变化，物流节点最优协同布局问题。

国外对于物流节点布局(选址理论)研究的文献比较多，其研究理论也比较成熟。近年来的研究趋势与热点是将经典选址问题和车辆路径、库存管理综合考虑，并考虑带随机需求和多阶段动态选址是研究的重点和热点，主要包括以下几个方面［2－5］:

(1)经典的选址模型。主要包括:P－中位问题(p－median problems)、P－中心问题(p－center problems)、覆盖问题(covering problems)等。

(2)选址结合库存控制网络设计模型(Location–Inventory Network Design Problem)，该类模型将选址和库存控制一起考虑，使得整体费用最小。

(3)设施选址结合车辆径路问题(Location－Routing Network Design Problem，RNDP)，该类问题将选址和车辆配送路径一起考虑，使得整体费用最小。

(4)枢纽网络设计(Hub Network Design Problem)。该类问题研究最早起源于航空网络设计问题，现在广泛应用于计算机网络、通信网络和运输枢纽等问题研究。O’Kelly开创了Hub选址问题的研究工作。

(5)动态选址问题(Dynamic Location Problem)。在这方面，国内外学者的研究主要集中在仓库或者企业物流中心的多阶段动态选址研究上，主要的求解算法有动态规划法、启发式算法和分支定界法等［5－6］。

国内外研究大多集中在企业的仓库、工厂、物流中心和配送中心单个设施的动态选址，且考虑物流中心、配送中心的处理成本和规模经济因素的研究文献很少。而在物流网络中心，不同的物流节点具有不同的技术经济特性，因此在物流节点布局时要考虑不同物流节点的协同配置问题［7］。

基于此，本文以一级物流节点(物流园区)和二级物流节点(物流中心和配送中心)组成的物流节点系统为研究对象，并考虑不同物流节点运行的规模效益，构建多时期、多货物类型的物流节点动态选址优化模型，并给出了基于混合遗传算法和启发式规则相结合的求解算法。

1 数学模型

一个城市根据未来15年物流需求变化，规划分3个阶段(第一阶段为1－5年，第二阶段为6－10年，第三阶段为11－20年)逐步完善该城市的物流节点系统，提高城市物流配送效率。规划建设由一级物流节点(物流园区)和二级物流节点(物流中心和配送中心)组成的物流节点系统，假设一级物流节点的候选地点共有n1个，二级物流节点的候选点共有n2个，该城市有m个物流需求点，各候选物流节点的建设成本，最大物流处理能力和其他相关参数已知，各物流需求点在各时期的物流需求量和物流需求点到各潜在的物流节点之间的距离已知，考虑物流节点关闭和重新开放的变迁费用。如何合理根据实际需要布局物流节点使得在整个规划期内社会物流成本最低(包括物流配送费用、物流节点的建设费用、物流节点的处理费用及其物流节点变动的变迁费用)。

1.1 符号说明

I表示一级物流节点(物流园区)候选点集合;J表示二级物流节点(物流中心、配送中心)候选点集合;N表示客户需求点集合;M表示货物类型集合;T表示物流规划时间段集合;Fk表示物流节点k建设的固定成本，k∈I∪J;(t)表示t时期从一级物流节点i到二级物流节点j的单位运输成本;(t)表示t时期从二级物流节点j到客户需求点n的单位运输成本;(t)表示t时期客户需求点n对第m种货物的需求量;U1i(t)表示t时期一级物流节点最初设计最大物流处理能力，i∈I;U2j(t)表示t时期二级物流节点j最初设计最大物流处理能力，j∈J;(t)表示t时期一级物流节点扩能后的最大物流处理能力，i∈I;(t)表示t时期二级物流节点j扩能后的最大物流处理能力，j∈J;)分别表示t时期一级物流节点i和二级物流节点j的单位处理成本;(t)，(t)分别表示t时期一级物流节点i和二级物流节点j的规模经济效应因子，一般而言，0≤(t)≤(t)≤1，且规模经济因子越小，规模经济效益越大;(t)，(t)分别表示t时期通过一级物流节点i和二级物流节点j的流量;表示t时期一级物流节点i进行扩能的扩建费用表示t时期二级物流节点j进行扩能的扩建费用;表示t时期关闭物流节点k的而剩下的残值，有(将物流节点的残值折算的关闭年的现值;表示物流节点k的投资回收期;r为资金的贴现率;Ak(t)为物流节点k一次性投资转化为投资回收期内的每年的等价投资额，根据资金回收公式得:Ak(t)=Fk

Dec(f)为符号函数，当f＞0时其值为1，f＜0时其值为0。

决策变量:(t)表示t时期由一级物流节点i流向二级物流节点j的第m种货物的物流量;Xmjn(t)表示t时期由二级物流节点j流向客户需求点n的第m种货物的物流量;Yk(t)表示t时期候选物流节点k是否运作的指示变量，当其值为1表示在t时期运作，为0表示不运作;Ek(t)表示t时期候选物流节点k是扩能的指示变量，当其值为1表示在t时期要扩能，为0表示不扩能;

1.2 数学模型(DMLNLP)

上述数学模型中，目标函数表示整个规划期的总费用的净现值最小，其总费由3部分构成:第一部分表示整个物流网络的配送费用;第二部分表示物流节点的固定建设费用和运作费用之和，第三部分表示物流节点扩能和关闭的费用;式(2)表示进入一级物流节点的物流量不能超过其最大的物流处理能力;式(3)表示进入二级物流节点的物流量不能超过其最大的物流处理能力;式(4)表示每个客户的需求要得到满足;式(5)表示每个二级物流节点(物流中心、配送中心)输入输出流量达到平衡;式(6)～(7)分别表示流入各一级物流节点和二级物流节点的物流量;式(8)～(9)分别判断各已经运作的一级物流节点和二级物流节点是否要扩能;式(10)～(12)表示流入各物流节点的物流量为非负;式(13)表示各物流节点在t时期运作与否。

2 求解算法分析

上述模型是一个非线性的优化问题，而且该优化模型是静态选址问题的扩展，其静态选址已证明是一个NP问题，所以该问题也是一个NP问题。对于动态的非线性选址问题一般优化算法很难得到其最优解。本文给出一个基于启发式算法和遗传算法相结合的方法来搜寻其最优解。

2.1 算法的基本思想

首先将候选物流节点的设计容量由小到大排序，并计算最大需要建设的物流节点数量。在各级物流节点建设数目确定的前提下，通过虚拟一个发点和收点，将原问题转化为一个节点和弧都带有容量限制的虚拟物流网络，然后利用改进的最小费用最大算法和基本遗传算法相结合的混合遗传算法，可以得出第一个规划阶段物流节点最优布局。

其次，根据第一个规划阶段的静态最优布局，运用下述相应启发式规则来得到第二个阶段的最优布局;同理，可以得出第三阶段的最优布局。

2.2 启发式规则描述

在详细描述算法前，对相应的启发式规则说明如下:

不妨假设，Ko(t)表示t时期进行建设或者重新运作的物流节点集;KC(t)表示t时期关闭的物流节点集，并且有，Ko(t)∪Kc(t)=I∪J。

记Z(Ko(t))为在t时期开放的物流节点集为Ko(t)所对应的目标函数中配送成本和运作成本之和(即目标函数中TC和OC值之和)。

记Z()，Z()分别表示在t时期开放的物流节点j扩能后和扩能前所对应的目标函数中配送成本和运作成本之和(即目标函数中TC和OC值之和)。

记DDj(t)为开放在t时期开放物流节点j带来整个网络配送成本和运作成本之和的变化值。

记DOj(t)为开放在t时期关闭物流节点j带来整个网络配送成本和运作成本之和的变化值。

记DEj(t)为开放在t时期物流节点j扩能带来整个网络配送成本和运作成本之和的变化值。

启发式规则

(1)开放规则:若在t时期，开放一个物流节点带来物流成本节约大于其最大投资增加额时，开放该物流节点是合理的，用数学表达式描述如下:

(2)关闭规则:若在t时期，关闭一个物流节点带来物流成本增加小于其关闭回收投资额时，关闭该物流节点是合理的，用数学表达式描述如下:

(3)扩建规则:若在t时期，对一个物流节点扩能带来物流成本节约大于其最大投资增加额时，扩建该物流节点是合理的，用数学表达式描述如下:

2.3 总体求解算法

Step 1:将物流节点按其设计容量从小到大排序，并计算最大需要建设的物流节点数量。

Step2:根据各级物流节点需要建设的数量，构建虚拟物流网络。

Step3:利用基于扩展的最小费用最大流的混合遗传算法得到T=1时期的最优物流节点配置方案，其目标函数值记为Z1(，)，其中分别表示该阶段最优配置方案所对应的一级物流节点和二级物流节点数量。

Step4:将T=2时期的客户点的物流需求加载在T=1时期的最优配置的物流网络上，若所有的流量加载完毕，转Step9，否则转Step 5。

Step 5:根据扩能启发式规则，计算未加载的客户需求点附近的物流节点是否满足扩能条件，并计算完成流量加载的最小扩能费用，记为Z2(E)。

Step 6:根据开放启发式规则，计算在未加载的客户需求点附近的物流节点是否满足开放要求，并计算满足未分配流量的最小新建费用，记为Z2(O)。

Step 7:比较Z2(n)，Z2(O)值的大小，若Z2(n)＜Z2(O)，则进行扩建;否则进行新建。

由此，可得到能力紧张时T=2时期的最佳配置方案，转Step 9。

Step 8:计算物流节点的利用率，并按照利用率值从小到大排序;依次计算排序较前的物流节点是否满足关闭条件，若满足则关闭。由此可以得出能力过剩T=2时的最佳物流配置方案。

Step 9:将T=3时的流量加载在T=2时的最优配置网络中，并类似Step4－Step 8操作，可以得出T=3时期的最佳网络配置方案。

Step 10:输出各时期的最优配置方案。

2.4 虚拟物流网络的构建方法

如图1所示，假设有m个一级物流节点候选点(物流园区)、n个二级物流节点(物流中心、配送中心)候选点和p个客户需求点。虚拟一个发点s和收点t，发点s到各候选物流园区点i的距离记为dsi，发点s到各候选物流园区点i的流量限制记为capsi;收点t到各候选客户需求k的距离记为dkt，收点t到各候选客户需求k的流量限制记为capkt，并有:dsi=0，capsi=∞;dkt=0，capkt=∞。

图1 虚拟物流网络图Fig.1 Virtural logistics netowork

2.5 编码及相关遗传操作说明

在遗传算法进行优化计算的过程中，染色体的编码、适应度的计算及交叉和变异操作是几个非常重要的环节。

染色体的编码采用二进制编码，编码形式如下:［u1，u2，…um|v1，v2，…，vn］，若ui=1，表示在第i个候选的地修建一个一级物流节点，否则，不修建。若vj=1，表示在第j个候选的地修建一个二级物流节点，否则，不修建。

在一级物流节点和二级物流节点都确定的条件下，按照上述虚拟物流网络构建的方法，可将原问题转化为一个弧和节点都带有容量限制的扩展的最小费用最大流问题，通过计算该扩展最小费用流，可得其总的最小费用和网络中流量分配情况。将其最小总费用作为相应染色体的适应度值。

遗传算子中的交叉运算采用双断点交叉。为了保证交叉后生产的后代染色体的可行性，对非可行解进行修复。修复策略详细见文献［8］，变异运算采用反转变异运算。

3 结论

(1)物流节点的合理布局可以提升区域物流的运行效率，降低区域物流运作成本。

(2)区域物流节点需要根据区域产业布局和需求变化的实际情况，在不同的规划周期内进行不断动态调整与优化，以提升整个区域物流运行效率。

(3)针对由物流园区、物流中心和配送中心组成的物流节点系统，构建了多规划周期、多种物流类型的区域物流节点动态布局优化模型，并提出基于扩展最小费用最大流的混合遗传算法。

［1］王之泰.新编现代物流学［M］.北京:首都经济贸易大学出版社，2005.

WANG Zhi-tai.New editor for modern logistics［M］.Beijing:Capital Economic and Business University Press，2005.

［2］Klose A，Drexl A.Facility location models for distribution system design［J］.European Journal of Operational Research，2005，162(1):4 －29.

［3］Bas G.Towards collaborative，intermodal hub networks:a case study in the fast moving consumer goods market［J］.Transportation Research Part E，2005(41):567 －583.

［4］Canel C.An algorithm for the capacitated，multi－ commodity multi－ period facility location problem［J］.Computers＆ Operations Research，2001(28):411－427.

［5］Current J，Ratick S，Revelle C.Dynamic facility location when the total number of facilities is uncertain:A decision analysis approach［J］.European Journal of Operational Research，1997(110):597 －609.

［6］牟伦英.物流网络节点的动态选址研究［J］.工业工程与管理，2005(2):102－105.

NIU Lun-ying.Research on dynamic location for logistics network nodes［J］.Industry Engineering and Management，2005(2):102 －105.

［7］张得志.物流节点系统演化机理研究［J］.铁道科学与工程学院，2008，5(1):81 －86.

ZHANG De-zhi.Evolution mechanism of logistics nodes system［J］.Journal of Railway Science and Engineering，2008，5(1):81 －86.

［8］赵晓煜.供应链中二级分销网络优化设计方法的研究［D］.沈阳:东北大学管理学院，2001.

ZHAO Xiao-yu.Research on optimization method of two classes distribution network of supply chain［D］.Shengyang:School of Management，North East University，2001.

Research on an optimization model for logistics nodes dynamic location and its solution algorithm

ZHANG De-zhi1，2，3，LI Shuang-yan3

(1.School of Management，Huazhong University of Science and Technology，Wuhan 430074，China;2.Logistics Center Department of Wasion Group，Changsha 410205，China;3.School of Transportation Engineering，Central South University，Changsha 410075，China)

Based on the analysis of the definition of logistics node and intension of Logistics node spatial layout，the model constructed in this paper presented the character of logistics nodes system，which is consist of the first－class logistics node(logistics park)and second－class logistics nodes(including logistics center and distribution center).According to the above analysis，a dynamic logistics nodes location model of multi－period，multi－type cargo flow and multiple logistics nodes was given.The optimization model considered the factors including fixed cost for logistics opening，handling cost and economic of scale of different type logistics nodes.An effective algorithm based on the heuristic rules and hybrid genetic algorithm was presented according to the characteristic of optimization problem.

logistics nodes;dynamic location;optimization model;heuristic rules;genetic algorithm

U294

A

1672－7029(2011)05－0096－05

2011－06－02

国家社会科学基金资助项目(11CGL032);中国博士后科学基金资助项目(20090460941);湖南省自然科学基金资助项目(09JJ3135);湖南省科技计划项目(2010FJ3007);中央高校科研项目(201012200100)

张得志(1976－)，男，湖南祁东人，副教授，博士，博士后，从事物流系统优化研究