常见的末端配送模式主要有送货上门和自助取货，前者虽然为顾客取货节省了时间和成本，但难以协调同一条线路上顾客的时间，因此造成一次配送失败率高^[1]。对许多物流企业来说，设置末端节点、采用客户自取货模式是其主要选择。末端节点位置的选择作为物流网络规划的关键环节，直接影响流通效率、物流成本和客户满意度。因此，探讨和研究末端节点的选址问题，对企业和顾客而言都具有重要的意义和价值。

节点选址对企业具有重要的战略意义，许多学者从不同角度对此进行了深入研究，并对其进行分类和归纳，提出对应的模型和求解方法。一般地，选址问题从变量的角度可以分为离散选址和连续选址两大类。已有文献对离散选址问题通常采用评价模型和排序方法、混合整数模型和优化算法等，对连续选址问题则采用各类启发式算法予以求解。倪冠群等^[2]考虑道路的通行能力限制，建立避难场所中心点选址的连续变量模型，设计基于图论的求解算法并分析了算法的复杂度。代文锋等^[3]对应急配送中心选址问题建立评价指标体系，结合灰熵改进关联系数，并结合理想解法中的贴近度对备选方案进行优劣排序。韦忆立和高咏玲^[4]分析了配送中心能力约束、流量约束和配送时间约束，在考虑遗憾系数的基础上建立了成本最小化的选址决策模型，并在不确定条件下对模型进行鲁棒优化。

一些学者运用聚类算法对选址问题进行了研究。唐东明等^[5]研究了基于块划分的选址问题和基于道路网络的选址问题，给出集合仿射传播的聚类算法进行求解。Boujelben等^[6]研究了多约束下的两阶段设施选址问题，第1阶段通过聚类算法划分客户集合，第2阶段建立混合整数模型并给出启发式求解算法。周翔等^[7]以顾客满意度最大和运输成本最低为目标，对末端节点数量、配送中心位置和节点与顾客对应关系进行研究，建立两阶段优化模型，二次聚类算法确定节点数量和位置，基于最小树的聚类算法确定配送中心位置。此外，不少学者对基于密度的聚类算法和均值聚类算法的理论和应用进行了深入研究^[8-13]。

本文不讨论客户集合划分的合理性，仅针对自取货模式下的单一节点连续选址问题，将客户满意度表达成模糊隶属度函数，通过均值求得初始解并设计了三角形外心和等分点的启发式算法优化初始解，过程中允许接受一次次优解以避免陷入局部最优。不同于遗传算法、禁忌搜索等优化算法，本文在考虑满意度的情形下给出一种图上寻优的启发式算法，并与基于点密度的聚类算法进行比较，证明所设计算法的寻优效果。

1 问题和假设

在客户自取货模式下，末端节点负责区域内的所有客户，物流公司将货物送达节点由客户自行取货。每个客户根据货物时效性和自身需要，都提出一个最远取货距离的要求，即末端节点和客户的距离不能超过最远取货距离，通过每个客户的最远取货距离选择可行域，类似于非等覆盖半径圆问题^[14]。为方便分析问题和建立模型，做如下假设。

1) 考虑单一物流节点的选址问题。顾客集合的分割可以看作一类聚类问题，一般以距离均方差作为目标函数，很难跟满意度隶属函数建立直接关系，对于这类分割集合−节点定位的问题，可以建立双层规划模型予以解决。

2) 不考虑末端节点容量。研究对象为单一节点，因此假设节点容量足够。

3) 客户数量和地理位置已知。为方便设计图上优化算法，将客户与节点间距离以其平面欧氏距离表示，实际问题中可以加入距离转换系数。

4) 考虑货物的时效性和客户需求的迫切性，每个客户各自存在到末端节点不同的期望取货距离和最远取货距离，期望取货距离内满意度最高，在期望距离和最远距离之间满意度依次递减，且不能超过最远取货距离。

5) 存在可行域，且聚类中心在可行域内。从几何角度，可以从非等覆盖半径的角度理解，以每个客户为圆心，最远取货距离为半径，这些圆存在公共区域，即问题的可行域。本文重点不是探究解的存在性，而是寻优的过程。

2 建立模型

对一个服务n个客户的节点选址问题，客户i的期望取货距离为e_i，最远可接受距离为d_i(i=1,...,n)，某状态下实际距离为d_ix，d_il为客户i到末端点l的距离，引入模糊隶属度函数μf_i(x)，对客户与节点之间的距离进行模糊化处理，将满意度通过隶属度函数表达，函数图像如图1所示。

从图1可看出，对每个客户来说，离末端节点越近，其满意度越高。客户i对应的满意度隶属度函数表达如下。

$\qquad \mu {f_i}({d_{il}}) = \left\{ {\begin{array}{*{20}{l}} 1, \;\;\;\; {0 {\text{＜}} {d_i}_l {\text{≤}} {e_i};}\\ 1 - \dfrac{{{d_{il}} - {e_i}}}{{{d_i} - {e_i}}}, \;\;\;\; {{e_i} {\text{＜}} {d_{il}} {\text{≤}} {d_i};}\\ - M,\;\;\;\; {{d_{il}} {\text{＞}} {d_i}{\text{。}}\;\;\;\;} \end{array}} \right.$

(1)

式(1)中，d_il由欧氏距离公式确定。M表示一个足够大的数，使得解的搜索过程中不需要判断是否满足约束条件，且保证选择的节点在任何客户的最远取货距离范围内。从而得到基于满意度的目标函数

$\qquad \max z = \sum\limits_{i = 1}^n {\mu {f_i}({d_{il}})} {\text{。}}$

(2)

基于假设4)，根据均方差最小求聚类中心，即初始可行解。设聚类中心K(x⁰,y⁰)、客户i(x_i,y_i)，均方差为

$\qquad V = \sum\limits_{i = 1}^n {\left[ {{{({x_i} - {x^0})}^2} + {{({y_i} - {y^0})}^2}} \right]} ,$

(3)

$\qquad \frac{{\partial V}}{{\partial {x^0}}} = \sum\limits_{i = 1}^n {2({x_i} - {x^0})} ,$

(4)

$\qquad \frac{{\partial V}}{{\partial {y^0}}} = \sum\limits_{i = 1}^n {2({y_i} - {y^0})} {\text{。}}$

(5)

对式(4)、(5)令偏导数为零，得到聚类中心

$\qquad {x^0} = \frac{1}{n}\sum\limits_{i = 1}^n {{x_i}} ,\;\;\;\;{y^0} = \frac{1}{n}\sum\limits_{i = 1}^n {{y_i}}{\text{。}}$

(6)

即初始可行节点为K(x⁰, y⁰)。根据欧氏距离公式得到每个客户到K的距离，并根据式(2)得到初始可行节点的满意度。

由于可行域不可导的连续选址问题无法求最优解，本文采用基于类内贴近度的点密度聚类算法^[15]作为对比算法，将问题近似为离散选址问题，选择客户点中密度最大的点，紧邻该点选址。任意2个客户点的相似相近的贴近度为

$\qquad t = \frac{{\sum {\max \{ {x_i},{y_i}\} \min \{ {x_i},{y_i}\} } }}{{\sum {{{(\max \{ {x_i},{y_i}\} )}^2}} }}{\text{。}}$

(7)

得到客户点基于贴近度的相关矩阵为

$\qquad {t} = \left[ {\begin{array}{*{20}{c}} 1&{{t_{12}}}& \cdots &{{t_{1n}}}\\ {{t_{21}}}&1& \cdots &{{t_{2n}}}\\ \vdots & \vdots & 　 & \vdots \\ {{t_{n1}}}&{{t_{n2}}}& \cdots &1 \end{array}} \right]{\text{。}}$

(8)

求出相关矩阵中各列之和S_j作为每个客户点的点密度。

$\qquad {S\!_j} = \sum\limits_{i = 1}^n {{t_{ij}}} {\text{。}}$

(9)

3 算法设计

由式(1)、式(2)可知，满意度目标函数由多个分段函数构成，每个分段函数在域内都存在一个不可导点。由此可知，在目标函数的可行域内存在n个不可导点。研究函数的单调性可知，多分段折线函数之和在可行域内有限分段单调，故无法通过单调性求域内最优解。

对于任意一个可行节点，总可以得到客户的满意度排序，类似于各目标权重相等的多目标优化问题不存在一个解使得每个目标达到最优，一般情况下不可能存在另一个节点，能同时提高每个客户的满意度。本文从初始可行解出发，考虑满意度低的客户并以满意度隶属度为几何权重，提出提高满意度的启发式节点寻优方法，每次寻优过程都尽可能提高多个节点的满意度，给出算法原理的说明。不失一般性，设初始解K(x⁰, y⁰)下客户满意度从小到大排列依次为 $1,2,\cdots,n $ ，对应的满意度隶属度为 $\mu f_1,\cdots,$ $\mu f_n $ ，当只考虑提高一个客户即客户1的满意度的时候，只需将节点选择在最靠近客户1的可行域内，显然只考虑提高一个客户的满意度的同时往往会降低多个客户的满意度。

考虑提高2个客户满意度的问题。首先给出考虑2个客户下节点确定规则：对于客户1(x₁,y₁)和客户2(x₂,y₂)，客户1和2之间的中点P、P和K的中点Q坐标为

$\qquad P\left(\frac{{{x_1} + {x_2}}}{2},\frac{{{y_1} + {y_2}}}{2}\right),Q\left(\frac{{2{x^0} + {x_1} + {x_2}}}{4},\frac{{2{y^0} + {y_1} + {y_2}}}{4}\right){\text{。}}$

则末端节点位置选择初始节点K、客户中点P以及两者中点Q当中满意度大的点，记为K₁(x¹,y¹)。

当客户数量较多的情况下，只考虑提高2个客户的满意度进行寻优效果不佳。从节点到客户距离相等的角度出发，给出提高不在同一直线上3个客户的满意度从而确定节点的规则：对于客户1(x₁, y₁)、客户2(x₂, y₂)和客户3(x₃, y₃)，有且仅有一个点到三者距离相等，这个点就是1、2、3组成的三角形的外心，记为M₁(u₁, v₁)。

$\qquad\qquad{u_1} = \frac{{{x_1}^2{y_3} + {x_2}^2{y_1} + {x_3}^2{y_2} - {x_1}^2{y_2} - {x_2}^2{y_3} - {x_3}^2{y_1} + {y_1}{y_2}^2 + {y_2}{y_3}^2 + {y_3}{y_1}^2 - {y_1}{y_3}^2 - {y_2}{y_1}^2 - {y_3}{y_2}^2}}{{2({x_1}{y_3} + {x_2}{y_1} + {x_3}{y_2} - {x_1}{y_2} - {x_2}{y_3} - {x_3}{y_1})}},$

$\qquad\qquad{v_1} = \frac{{{y_1}^2{x_2} + {y_2}^2{x_3} + {y_3}^2{x_1} - {y_1}^2{x_3} - {y_2}^2{x_1} - {y_3}^2{x_2} + {x_1}{x_3}^2 + {x_2}{x_1}^2 + {x_3}{x_2}^2 - {x_1}{x_2}^2 - {x_2}{x_3}^2 - {x_3}{x_1}^2}}{{2({x_1}{y_3} + {x_2}{y_1} + {x_3}{y_2} - {x_1}{y_2} - {x_2}{y_3} - {x_3}{y_1})}}{\text{。}}$

类似于考虑2个客户情况下的取点规则，将线段M₁K二等分，M₁与K的中点记为

$\qquad {O_1}(\frac{{{x^0} + {u_1}}}{2},\frac{{{y^0} + {v_1}}}{2}),$

则末端节点位置选择初始节点K、客户中点M₁以及两者中点O₁当中满意度较大的点，记为K₁(x¹,y¹)。具体如图2所示。

选择一个合理的点来提高多个客户的满意度，涉及到多个客户期望取货距离e_i、满意度隶属函数递减区间斜率等，无法在每次寻优过程中全面考虑，因此寻找一个到多个客户距离相等的点作为待选节点合理性较强，而到不在同一直线上3个点距离相等的点即为三点组成三角形的外心。考虑到可行域内目标函数的分段单调性，因此外心和初始节点的中点也作为待选节点，这一过程可看作一维扫描搜索。理论上外心和初始节点连线上选择的待选节点越多越好，但算法的运行效率随着节点数的增多而快速降低。

按上述规则，无法确保同时提高满意度较低的4个客户的满意度，因平面上任意三点不共线的四点中存在1个点，其到4个顶点距离相等，当且仅当4个顶点组成的四边形对角和为180°。无论是三点共线还是对角和等于180°，都属于极小概率事件。当发生三点共线的情况，则忽略中间点，问题退化为两点考虑。

根据算法运行中的不同情况分类给出算法的终止准则如下。

1)理论上存在多次迭代仍无法收敛的可能，即每次搜索寻优过程的优化幅度很小，使得多次搜索后存在进一步优化的空间。根据客户数量，给出最大迭代步数，当客户数较少的情况下，目标函数分段单调区间数较少，每次通过外心和等分点寻优的效果较好，相应设定较小迭代步数，即客户数和迭代步数正相关。本文以客户数n为最大迭代步数。

2)可行域内存在多个单调区间，一维搜索容易陷入局部最优。为了尽可能扩大搜索范围，当一次寻优中M_i、O_i的满意度低于K_i-1时，允许接受一次次优解，使得寻优过程从不同的方向继续进行，当连续两次搜索无法优化当前解的情况下，算法终止。模型中存在M，因此当某次搜索过程中待选节点M_i和O_i的满意度同时出现M，算法终止。

4 算例分析

为了验证算法的可行性，随机给出包含12个客户的物流末端节点选址算例，算法最大迭代步数相应设定为12，距离单位为km，客户的平面坐标、期待取货距离、最远取货距离等信息如表1所示。

如图3所示。K(39.3,30.1)，此时目标函数值为9.3，其中满意度从低到高依次为1、4、3、2、8、7、10、9、12、6、11、5。考虑1、3、4组成的三角形，根据外心公式可求得M₁(35.4,41.4)，等分点O₁(37.4,35.8)，对应满意度目标值分别为－M、8.83，接受次优解，选择O₁作为当前可行节点，记O₁=K₁，此时满意度升序排列为2、6、7、8、12、4、1、9、3、5、10、11。继续寻优，考虑2、6、7组成的三角形，据公式求得外心M₂(44.5,18.5)，等分点O₂(40.9,27.2)，对应满意度目标值分别为－M、9.47，存在更优解，则选择O₂作为当前节点，记O₂=K₂，根据节点寻优规则，记录满意度最低的客户编号分别为1、4、3。此时记1、3、4组成三角形的外心M₃(40.7,31.4)，而M₃=M₁，因此不得不再次选择O₂作为K₃，无法继续寻优。输出最优解K_m(40.9,27.2)，满意度目标值为9.47。

由式(7)、(8)可得点密度权重最大的点为5，S₅=8.49，紧邻该点选址，得到K_m=9.41＜9.47，可知基于三角形外心和等分点设计的图上寻优算法优于均值聚类和点密度聚类算法。

5 结束语

本文在考虑期望取货距离和最远取货距离的基础上，建立以客户满意度函数为目标的数学模型，研究了自取货模式下的物流末端节点的连续选址问题，通过对客户到节点的距离平方和函数求偏导数确定初始可行节点，根据目标函数在可行域内不可导的特点，设计了基于外心和等分点的图上一维搜索算法来提高目标函数，并设置终止准则，算例验证了算法的寻优效果。

算法的改进可以根据不同客户目标函数的变化率作为权重，确定待选节点靠近客户的比例关系，且一维搜索过程中取多等分点进行比较寻优有助于获得更好的可行解。此外，在实际问题中平面距离转换为实际距离需要增加转换系数，即图形中各边的加权长度。