基于广义最大覆盖模型的连锁公司货物配送问题

【摘要】本文运用matlab及lingo软件对连锁超市的商品配送的问题进行了深入的探讨。运用了Floyd算法、运筹学、时间序列预测、广义最大覆盖模型等思想对问题进行了求解，力争使用最简单的模型求得最优化的结果。连锁超市货物运送问题中，由于单位运费固定不变，因此，可利用控制变量法，运用最短距离经典算法——Floyd算法结合matlab软件对每两个城镇之间的最短公路距离进行测算，同时结合广义最大覆盖模型，设置01变量及覆盖度权重建立优化模型，利用lingo软件编程对模型进行求解。通过局部最优解，选择连锁店地址使其达到最大销量，以解决连锁超市选址问题。

【关键词】 Floyd算法；二次项曲线模型预测；广义最大覆盖模型；线性规划

一、绪论

随着经济全球化的快速发展，企业之间的竞争日趋激烈，连锁经营已经成为现代化经营的常态并迅速的发展起来。现如今，连锁经营与超市的完美结合，使连锁超市的发展速度日益加快，规模不断扩大。那么，此时，拥有完善的物流系统对超市就显得极为重要，其中，高效率的配送系统发挥着重要的作用，而选址又是建立配送中心的关键环节。因此，本文主要研究配送中心及连锁超市选址问题，考虑连锁超市的不同规模，及其所适宜的不同配送模式，结合国内外相关文献，达到超市及配送中心选址最优化。

二、模型建立

（一）基于弗洛伊德算法的最短距离测度

弗洛伊德算法通过一个图的权值矩阵求解每两点间的最短路径。

从图的带权邻接矩阵A=[a（i，j）]n×n开始，递归地进行n次更新，即由矩阵D（0）=A，按一个公式，构造出矩阵D（1）；继续使用同样地公式由D（1）构造出D（2）；……；最后通过同样的公式由D（n-1）构造出矩阵D（n）。矩阵D（n）的i行j列元素便是i号顶点到j号顶点的最短路径长度，我们称D（n）为图的距离矩阵，同时引入一个后继节点矩阵path来记录两点间的最短路径。

构造赋权图G=（V，E，W），其中，顶点集Vi=v1，…vn，这里i表示各个城镇；E为边的集合，邻接矩阵

W0=w11…w1n

…

wn1…wnn，

其中

wij=d，vi与vj之间有边时

∞，vi与vj之间无边时i≠j

wii=0，i=1，2，…，n

本文中，W0是对称矩阵，wij=wji。

计算时使用的迭代公式如下：

Wk（i，j）=min（Wk-1（i，j），Wk-1（i，k）+Wk-1（k，j））

k是迭代次数，i，j，k=1，2，…，n

最后当k=n时，Wn既是各顶点之间的最短通路值。

（二）二次回归选址分析

对于各连锁超市货物需求量，本文采用二次回归来处理，通过二次回归模型，建立超市所在区域的二次方程，通过二次方程的性质求解其峰值，即需求量达到最大的时间。最后通过比较各地区出现峰值时的需求，找出达到峰值时需求排名靠前和靠后的地区，以获得最优选址地点。

（三）基于广义最大覆盖的选址全覆盖模型

目前，选址问题多应用最大覆盖模型进行研究。对于传统最大覆盖模型，如果供应点和需求点之间的距离小于某个值，认为供应点可以完全覆盖需求点，否则认为不能覆盖。但这种假设有时并不合理，一方面，判断结果只有完全覆盖和不能覆盖两种，判断条件过于简单；另一方面，实际操作中为了简化计算，常将需求区域的中心点坐标作为需求区域的坐标，当中心点与供应点的距离超过限制而认为整个需求区域不能被覆盖时，实际上部分需求区域可以被供应点覆盖。

广义最大覆盖模型最早由Berman等提出，本文结合连锁超市选址实际问题，将传统最大覆盖模型中覆盖度二元化的假设变为多元化假设，提出“部分覆盖”的概念，要求所有需求点都能得到不同程度的覆盖，使覆盖节点的加权和达到最大。

目标函数：max∑i∈I∑j∈Jwicijyij （1）

约束条件：yij-xj≤0（i∈I，j∈J）

（2）

∑j∈Jxj=N

（3）

∑j∈Jyij=1（i∈I）

（4）

xj∈0，1（j∈J）

（5）

yij∈0，1（i∈I，j∈J）

（6）

目标函数：令被覆盖需求点的加权和最大。

约束条件：式（2）表明只有j镇建立连锁店时，需求镇i才可能被连锁店j覆盖；

式（3）表明要从所有城镇中选择N个城镇建立连锁店

式（4）限定每个需求镇i都被1个且只被1个连锁店覆盖；

式（11）和（12）限定，xj和yij为二元值。

覆盖度的确定（与距离有关）：

cij=1 dij=0

0.5 0< dij<10

0.3 dij≥10

（四）穷举法生产基地选址模型

根据弗洛伊德算法及广义最大覆盖模型结果，计算所有城镇的总需求量及应建生产基地个数，利用穷举法对生产基地进行选址，运用运输问题计算方法计算每种方案的最短距离，选择最优的方案。

选址模型目标函数：运输成本最小

约束条件：（1）新增设的生产基地日产量x吨以上；

（2）在生产与销售各环节无产品积压；

目标函数：

（2）在生产与销售各环节无产品积压；

目标函数：

min∑j∈M∑i∈Ajdjyijpsij

约束条件：

s.t.∑j∈Biyij≤1，i∈N∑i∈Ajdiyij≥∑j∈MZxj，j∈MZ≥x0

三、模型分析

（一）模型优点

1. floyd算法容易理解，可以计算任意两节点间的最短距离，代码的编写相对简单。

2. 传统最大覆盖模型可能使个别需求点不能被覆盖，而广义最大覆盖模型能够实现需求点全覆盖。

（二）模型缺点

1、Floyd算法的时间复杂度较高，不适合计算大量数据。

2、广义最大覆盖模型将覆盖度的确定由距离改变为时间，

（三）模型改进

针对本文提出的连锁超市选址问题的缺陷，提出有针对性的模型改进方案，首先对超市货物需求数据及超市地址数据进行前期加工处理，再运用Floyd算法，以降低其时间复杂度。同时，减少预先设置的模型假设，扩大最优解的范围，实现局部最优解向全局最优解的推广。

参考文献：

[1]丁国盛.SPSS统计教程，机械工业出版社，2006.01

[2]李伯德.数学建模方法，甘肃教育出版社，2006.05

[3]张志涌等.MATLAB教程，北京航空航天大学出版社，2010

[4]胡运权等.运筹学教程，清华大学出版社，2012.11