一类基于客户满意的LRP问题研究

吴建文，孙桂林（北京交通大学，北京 100044）

随着全球贸易的快速增长，集成化物流管理的概念被越来越多的企业所接受，提高分销效率成为了企业在激烈的竞争中，获得战略制高点的必由之路。定位—运输路线安排问题（LRP问题）相对与独立的定位—配送问题（LA问题）和运输路线安排问题（VRP）更贴近目前的集成化物流管理系统的实际特征，对其研究有很大现实的意义[1]。

1 定位—运输路线安排问题（LRP）的定义及研究现状

1.1 定位—运输路线安排问题（LRP）的定义

运输路线安排问题（Location-Routing Problem，LRP）可以表示为给定与实际问题相符的一系列潜在的设施点，在这些潜在的点中确定出一系列的设施位置，同时要确定出一套以各个设施到各个客户点的运输路线，确定的依据是满足问题的目标（通常是总的费用最小）。客户点的位置和客户的需求量是已知的或可估算的，货物有一个或多个设施点位置已知，问题的目标是把那些潜在的设施建立起来，以使总的费用最小[2]。

1.2 LRP问题的研究现状

国外，在20世纪70年代初期就开始了对LRP问题的研究。Cooper[4]把定位问题与运输问题结合起来，提出了运输—定位问题（Transportation-Location problem），降低了运输成本。Tapiero[5]于1971年改善了Cooper的研究工作，把时间的复杂度引入普通运输定位模型中。到了70年代中期，Watson-Gandy和Dohrn[6]将运输车辆多点停留特性与定位运输网络结合起来开展了研究。后来Bookbinder和Reece[7]定义了三层多商品配送体系，建立了非线性混合整数规划模型，并将问题分解为定位配给和运输问题两部分。

我国对定位—运输路线安排问题的研究是在20世纪90年代后期才慢慢开始兴起，比国外滞后了30多年。现在对于问题的研究依旧处于起步阶段。汪寿阳，赵秋红[3]等是较早在国内开始LRP问题研究的学者，在其论文中详细介绍了国外对于集成物流管理系统中LRP问题的研究进展，分析了的主要内容和特征，提出有关求解问题的算法分类，并对以后该领域的研究方向提出了几点建议，该文献对我国在该领域的研究起了指引作用。张潜，高立群等[8]从算法优化的角度出发，对LRP问题中的定位配给、运输车辆路线安排、定位—运输路线安排三类问题的具体优化方法进行了分析和比较，并在此基础之上提出两阶段启发式算法来求解LRP问题。张长星等采用遗传算法来求解定位—运输路线安排问题。其特点在于没有采用普遍的两阶段求解的思路，而是将其看作一个整体进行求解，避免了在求解过程中出现局部最优解的情况，为求解LRP问题和其他相关大规模组合优化问题提出了一条新的思路。黄春雨等建立了以缩短物流多阶响应周期和成本优化为目标的多目标模型。与其他模型所不同的是，在该模型之中加入了对不同运输方式的选择，同时在成本计算时，考虑了订货成本和分拣中心的处理成本。李鑫丽[9]建立了以准时到达和总成本最小的多目标模型，并在此基础上加入了逆向物流的概念，从定位、路线选择、回收几个方面综合对LRP问题进行了研究，取得了很好的效果。

通过上述分析，我们发现国内对问题的研究具有以下一些特点：

（1）起步较晚，研究的团体不多，所取得的成果也较少；

（2）主要集中于算法的研究上，理论性较强；

（3）对于模型的构造多以单目标为主，以及运用模型来解决实际问题的研究则较少。

2 LRP模型的建立

2.1 建模思想

在传统的多目标LRP问题研究中，主要从准时到达和总成本最小或者利润最大的角度对问题进行研究，取得了非常好的效果。实际上，作为物流商，配送货物到客户的主要目的就是让客户满意，不光是准时到达就能让客户满意，准时到达只是客户满意的一个方面，象产品质量、包装、是否和要求相符等一系列指标都是客户是否满意的衡量指标。本文就从客户满意和利润最大的角度对LRP问题进行研究。

2.2 模型的建立

本文建立一个最基本的三级模型（如图1），其中A为生产厂家，B为配送中心，C为客户，带箭头的连线为货物流动方向。

图1 一个三级物流链模型

本文LRP模型做如下假设：

（1）客户的需求量一定且为已知；

（2）有多个潜在的配送中心，如果能满足约束条件

则建立配送中心，否则不建立配送中心；

（3）配送中心之间不存在相互配送；

（4）一个客户只接受一辆车的服务；

（5）一辆车从一个配送中心出发并且在配送过程中不再经过任何配送中心；

（6）生产地A能满足客户C的需求；

（7）配送中心的选择与其固定投资无关；

（8）配送中心无容量限制；

（9）任意两点之间单位运输成本相同。

2.3 数学模型的建立

2.3.1 模型中参数的含义

S1＝｛si/ 1 ≤i≤I｝为潜在的物流中心点的集合；S2=｛sj/I+1≤j≤I+J｝为需要物流服务的客户节点；S=｛S1｝∪｛S2｝为潜在物流中心节点与客户节点数的总和；V=｛vk/1 ≤k≤K｝为物流中心拥有的车辆的集合；Fi为在i（i=1,2,…,I）处建立物流中心的成本；Wi为在i（i=1,2,…,I）处建立物流中心的运营成本；Zi（∀i∈ G）表示是否在i处建立物流中心，如果是，则Zi=1，否则便为零；dij为从物流中心节点i到客户节点j的距离；Qk为车辆k的容量；xijk（i∈S1,j∈S,k∈V,i≠j）表示车辆k是否从节点i到节点j，如果是，则xijk=1，如果否，则为零；e为客户对产品的期望满意度，按照Parasuraman A等提出的7点标定法标定客户满意度，分别为：非常满意（very satisfied 7），满意（satisfied 6），稍满意（somewhat satisfied 5），中立（mid-level 4），稍不满意（somewhat dissatisfied 3），不满意（dissatisfied 2），非常不满意（very dissatisfied 1）。我们取的e值为集合｛非常满意7，满意6，稍满意5｝中元素。qj（e）为客户j的物流需求量，与e成正比；任意两节点之间的平均单位运输成本为C（e）；

2.3.2 建立模型

目标函数是：

约束条件为：

模型中各式的简要说明：目标函数表示对总成本求极小值，式（1）中第1项表示运输成本，第2项表示建设和运营物流中心所需的成本；约束条件中式（2）表示每个客户仅有一辆车提供服务；式（3）表示每辆车配送的客户需求量之和不超过其装载量；式（4）保证运输路线具有空间连续性；式（5）保证能配送到任何一个客户；式（6）保证每辆车的运输路线都源自于物流中心；式（7）表示每辆车的运输路线上只能有一个物流中心；式（8）表示客户满意度的取值范围。

3 基于客户满意的LRP模型的优化求解

3.1 指导思想

通常，物流配送系统的LRP包含选择配送中心、选择运输车辆、确定车辆配载、选择行车路线、确定发车时间等几个方面的规划问题，因此在解决这些问题的时候，采用分而治之的解决思路。即把整个LRP分解成几个子问题，先考虑各个子问题的解决方法，然后再考虑问题的整体性，综合起来就得到问题的解决方法。为了简化起见，将本文研究的LRP问题分解为以下两个子问题：一是配送中心的分派子问题，二是车辆运行路线安排子问题。其中配送中心的分派子问题是指选择出货物配送中心的问题，求所有客户点对于配送中心的一个分派（即确定客户应该归属于那个配送中心）；车辆运行路线安排子问题是在选择配送中心子问题的基础上进一步安排每个选定的配送中心的车辆问题。这包括决定每个配送中心将采用哪几辆车参加运货；每辆车装载那几个客户的货物；每辆车的发车时间以及行车路线等。

对LRP进行分解之后，这两个子问题不是彼此孤立的，而是密切联系的。此LRP问题是一个整数规划问题，对它进行分解的目的是为了求解方便。分解后的子问题之间是紧密联系在一起的。车辆运行路线安排子问题是在选择配送中心子问题的基础上进行求解的，只有在选择配送中心子问题之后，车辆运行路线安排子问题才能进行求解。解决选择配送中心子问题的关键是使车辆运行路线安排子问题的求解结果最优，使整个问题求解的资源消耗尽量小，各个子问题的求解过程是循环递进的。当选择配送中心子问题解决后，得到的结果除了选定的点之外，还有在构建配送中心子问题的启发函数时考虑车辆运行路线，即解决分配问题。在这个基础上，解决车辆运行路线问题，就是决定每个配送中心中的每辆车装载那几个客户的货物、何时发车、车辆如何行使（即行车路线安排）等问题[10]。

3.2 问题求解的两阶段启发式算法

对于配送中心分派子问题的求解步骤，一般情况下，客户应该由距离其最近的配送中心供货才是最合理的。当货运量一定且客户的信息确定后，就可以把N个客户按照就近原则分配给M个配送中心。计算方法是通过求每个客户点到每个配送中心的距离，然后取其距离的最小值，由此确定的启发函数如下：

其中Lij是客户j到配送中心i的距离。这样，第一阶段的如何分配配送中心子问题就解决了。对于已经分派的配送中心和其要配送的用户，采用遗传搜索算法搜寻优化运输路线。

遗传算法（Genetic A lgorithm,GA）是20世纪60～70年代美国密歇根大学的霍兰德（Holland）教授及其学生莫伊生物进化机制发展起来的优化搜索算法，该算法将操作对象看做是一个生物群体，经过多代进化后选择出优秀个体作为系统的最优解[11]。本系统个体是由M个子串构成，客户号采用自然数编码，即叙述编码，对于长度为n的染色体，每位在1到n中取互不相同的值，对于车辆调度问题，设配送中心序号从1到M，依次对各客户点编号形成染色体，该染色体表示了车辆调度，路线安排等各种信息，例如染色体5655315，表示一条路线是从配送中心点5出发，依次经过客户6、5后，回到配送中心5；另一条路线从该配送中心出发，依次经过客户5、3、1后，回到配送中心5。

染色体的适应度是反映染色体性能优劣的唯一指标，适应度越大，表明在以后遗传中存活几率就越大，车辆运输路线的染色体适应度是根据其目标函数得到，对于遗传编码中个体k的适应度fk为：

则个体k被选中的概率为：

其中L是群体大小数，通过计算染色体的选择概率产生0～1的随机数，选中对应的染色体，并复制到下一代。

染色体的交叉和变异算子都局限在子串内进行。交叉体现了有性繁殖，用于组合出新个体，交叉操作采用部分映射交叉和类似OX交叉相结合；变异操作采用启发式变异，过程为：对于需要变异的染色体，随机选出λ个基因，列出所有选出基因的可能换位产生的领域，评估所有的领域点，选出最好的作为变异产生的后代进行车辆优化的变异操作。

4 算例分析

有4个待选配送中心和8个客户节点。选择出合适的配送中心并给出车辆配送路线。

首先，对配送中心和客户进行编号，其中1～8表示客户，9～12表示配送中心。配送中心和客户、配送中心之间、客户之间的最短距离以及配送中心的建设和运营费用及客户的配送需求量见表1。采用同种型号的车辆，且容量为8t，车辆的单位平均运输成本为2元/t·km。

表1 基本参数数据

其计算步骤为：

（1）根据客户应该由距离其最近的配送中心供货才是最合理的原理，首先找出确定每一个客户由对应的配送中心配送。

（2）设定群体规模n=8,交叉概率Pc=0.7,变异概率Pm=0.005。

（3）计算每一条配送线路的适应度值。

（4）遗传操作（选择适应度值大的个体保留，按照一定概率进行交叉和变异操作）。

通过编制MATLAB程序[12]对该算例进行求解，最后得到的结果为（9 1 3 4 10 8 10 2 5 11 6 7），即编号为9 10 11的配送中心按照一定的车辆路径所构成的物流通道为客户提供物流服务的费用最小。

5 结束语

目前我国物流服务业整体水平不高，对于物流网络的优化研究主要还停留在对成本优化的阶段。本文从成本和客户满意两个角度建立了基于客户满意、总成本最低的多目标优化LRP数学模型，然后用启发式两阶段法对模型求解。希望本文提出的模型可以为企业物流配送问题提供一些有益的启示。

[1]张潜，高立群，胡祥培.集成化物流中的定位—运输路线安排问题（LRP）优化算法评述[J].东北大学学报，2003,24(1):31－32.

[2]林岩，胡祥培，王旭茵.物流系统优化中的定位—运输路线安排问题（LRP）研究评述[J].管理工程学报，2004，18（4）：45－46.

[3]汪寿阳，赵秋红，夏国平.集成物流管理系统中的定位—运输线路安排问题的研究[J].管理科学学报，2000,3(2):69－75.

[4]Leon Cooper.An efficient heuristic algorithm for the transportation－location problem[J].Journal of Regional Science,1976,16(3):305－309.

[5]Tapiero C S.Transportation－location－allocation problems over time[J].Journal of Regional Science,1971,11(3):377－384.

[6]Watson－Gandy C,Dohrn P.Depot location with van salesman－A practical approach[J].Omega,1973,1(3):321－329.

[7]Bookbinder J H,Reece K E.Vehicle routing considerations in distribution system design[J].European J of Operation Research,1988,37(2):204－213.

[8]张潜，高立群，刘雪梅,等.定位—运输路线安排问题的两阶段启发式算法控制与决策[J].控制与决策，2004,19(7):773－777.

[9]李鑫丽.LRP及其图论模型研究[D].南京：南京信息工程大学（硕士学位论文），2007.

[10]郭伏，王红梅，罗丁.城市物流配送系统的多目标优化LRP模型研究[J].工业工程管理，2005(5):3－4.

[11]程赐胜，蒲云虎，王正武.高速公路物流网络规划LRP模型及算法研究[J].长沙交通学院学报，2008,24(1):37－43.

[12]王小平，曹立明.遗传算法——理论、应用与软件实现[M].西安：西安交通大学出版社，2002.