物流配送中心选址问题

杨慧洁 孙莹 胡廷雯 张继雄 刘洋 刘明 刘伟

摘 要：主要分析物流系统中最后一公里，运输、配送中心之间的联系，应用最优化方法建立了物流配送中心选址的数学模型。该模型是一个混合整数规划的求解算法，该模型中约束方程数量的有限性保证了算法的收敛性。

在整个物流系统中，由于可以用联结点即发货点，物流配送中心，需求点和运输路线构成的物流网络来表示。

配送中心配置的必要性：

物流系统中配送中心是重要的一个环节，因此搞好配送中心选址问题对提高整个物流系统的效益具有重要意义，配置配送中心应考虑下述必要性：

首要控制物流成本，再按照集约库存来维持合理的库存量，为了防止库存过剩和库存偏颇，把过去分散在地面上的快递，集约到配送中心进行管理，提高服務水平，美化校园环境，方便师生。

把配送中心配置在校园内部，因为我校是摆地摊式快递区，每当快递多时，师生会浪费很多时间在取快递上，而且快递区不是固定不变的，每当恶略的天气快递区就会转移，致使很多师生不清楚转以后的快递区的低点位置，更浪费大家的时间，所以把配送中心安放在校园内，通过合理的数学模型，将快递柜合理的分散在必要的地段。

建立模型的有关假设

前面论述了建立费送中心的必要性，现在讨论建立配送中心的选址模型，假设如下：

（1）仅在一定的设备选取地点范围内考虑新的配送中心的配置

（2）用户的需求量按楼区总计

（3）用不同水平来表示不同的运输手段

（4）运费是运输量、路程等的函数

（5）对于需要扩建的配送中心，首先扩建到预先确定的最小扩建容量，然后，根据提高经济效益的需求，允许在最小扩建容量与最大扩建容量之间继续扩建，这时所需的扩建费与扩建容量成正比;

（6）新建配送中心应确保刚应用快递柜时的容量，以后允许扩大到预定的最大可能容量为止

模型的建立

（1）模型变量

Xikl——从校外地区k向配送中心i送l产品的物流量

Xijls——用服务水平s，从配送中心i向需求点j送l产品的数量

Yi——超过最小配送容量后，配送中心i还继续扩建时的扩建量

I'——可能新建的配送中心的集合

I″——为已建配送中心的集合

I=I'∪I″

（2）模型参数

Akl——校外地区k对l产品的供货能力

hijls（*）——从配送中心i，用服务水平s，向需求点楼区j运送产品l的运价（路程、运量、运输方式等为自变量的分段函数）

Dljs——楼区j地区对l产品的s服务水平的需求量

Ai——配送中心i的配送能力，i∈I

Bi——配送中心i的配送配送能力的最小扩充量，i∈I″

Qi——配送中心i的配送能力的最大扩充量，i∈I

Cikl（*）——从k到i运输l产品的运价（路程、运量、运输方式等为自变量的分段函数）

NIi——新建配送中心i的基本投资，i∈I'

IEi——配送中心i扩建到最小扩建容量时的扩建费用，i∈I″

CTi——配送中心i继续扩大的单位扩建费用（元/t）i∈I″

KXi——关闭配送中心i将节省的费用，i∈I″

gil——l产品流经i配送中心的单位管理费用，i∈I

Fi——配送中心i的固定管理费用，i∈I

（3）模型

再假设下，物流费用可以主要分成3部分：从校园外到配送中心所需的运输费用;从配送中心到需求点所需的发送费用，经营配送中心所需的费用。包括配送中心的总可变费用，配送中心建设总费用，配送中心管理费用，配送中心的最小扩建费用。因此，模型的目标函数为

元素 含义

L 快递的集合

K 校园外部地区的集合

I 配送中心集合

J 学生个人需求点的集合

S 服务水平集合

4.求解算法

模型（1）是混合整数规划，应当用benders分解算法求解。为此先把原问题式（1）转化成标准形式

（2）

其中：X是限行变量矢量;Y是专门变量矢量（全是0——1变量）。可看出的值一旦被固定，式（2）就成为一个普通的线性规划问题。但选择一定要保证所得规划有可行解。由Farkas引理和对偶原则可以得出式（3）

min U   （3）

其中，P为极点数;R为极限数

由于式（1）带有很大数目的约束，极点数P和极限数R是相当大的，可采用由部分约束集合开始逐步迭代的方法求解。令IP是集合{1，2，...，P}的子集，由此可得式（4）

min U       （4）

设为式（4）的最优解，则考虑下列的问题：

①式（1）有可行解式（3）有可行解

②式（1）有无界解式（3）有无界解

③若有是式（3）的最优解，为下述LP的最优解

min CX

那么就是原问题式（1）的最优解。算法如下：

（a）假定初始集合，解式（4）

（b）这时，具有集合，解式（4）。若式（4）不可行，停止，原问题式（1）无解;若式（4）有界，有最优解，转②;有无界最优解时，令是使得得任一可行解转②;

（c）解LP规划式（5），其中y*是由初始解给出，若LP式（5）不可行，停止，这时式（1）也不可行或有无界最优解，若LP式（5）有无界解，转③;若LP式（5）有有限最优解，转式④;

（d）这时，沿着某个极限有，把相应的约束加到问题式（4）中，扩大后再转①

（e）令为的最有极点解，若则停止，式（4）的解，即为式（3）的、一个最有可行解;若，那么把相应的约束加到式（4）中，即扩大集合，再转①

由于约束条件有限，问题只有有限个极点和极限，所以上面的算法在有限步就会收敛

特殊条件

（1）集散点在同一条直线上。

①在一条笔直的流水线上，假设有5个宿舍楼，现要在流水线上设置一个快递柜，使得各宿舍楼到快递柜的距离总和为最短，问快递柜应设置在哪里？

②一般的，如果是n个宿舍楼，快递柜又应设在哪里？

③如果这条直线上的五个点分别有宿舍楼3，3，2，5，2个，快递柜应设在哪里？

④求函数

的最小值

[分析]

由于绝对值的几何意义可理解为两点的距离，因此该例可与以下的实际模型对应：设在一条东西走向的笔直的公路上，分布有n个路口，其中自西向东的第i个路口聚集着ki个宿舍楼。问快递柜摆放在道路的什么位置，才能使这些宿舍楼到快递柜的距离总和最小？

将“第i个路口聚集着ki个宿舍楼”设想成有ki个路口，它们重合于第i个路口，则由有关线段的几何模型可知：

为奇数时，x取个路口中居中的那个路口所对应的值时，y取最小值;

而当为偶数时，x取个路口中以居中的两个路口为端点的线段（若这两点重合，就取这一点）上任一点所对应的值时，y取最小值。

项目编号：201813896006天津师范大学津沽学院大学生创新创业训练计划项目

（作者单位：天津师范大学津沽学院）