基于图论的物流中心线上选址研究

1 引言

在互联网技术与商业结合起来以后, 我国的电子商务得到了快速发展, 同时这也促使我国的物流需求大大增加。物流中心作为物流活动的最重要的节点, 其选址的方法必然是非常重要的, 这直接关乎以后物流活动的运营成本和效率。

关于物流中心的选址方法, 目前的研究成果比较丰富。从选址数量角度分为单点选址和多点选址问题。单点选址问题中要建立的物流中心数量只有一个, 而多点选址问题中要建立的物流中心数量有多个, 一般情况下是2~5个。从选址方法角度分为重心法、微分法 (改进的重心法) 和评价模型。重心法作为经典的物流中心选址方法, 是基于平面的选择方法, 也就是说最优点的选择范围是整个平面, 但是这明显在实际运作中是不行的, 因为平面上的大多数点是不可行解, 这些点可能被公共场所或者其他公司占用。更为关键的是平面上的点不一定在道路旁边, 如果用重心法求解出的物流中心没有在道路旁边, 那还需要建设道路使得物流中心与现有道路连接, 这就增加了建设成本。另一种物流中心选址的方法是评价模型, 使用该方法之前已经确定了几个位置作为物流中心的候选地址, 然后根据所建立物流中心的目的, 设置一套评价体系, 对各个候选点进行评价排序, 最后选择综合评价最好的候选点作为最终的物流中心点。在这种评价模型中, 用到比较多的就是模糊平价法、层次分析法和运筹学中的优化方法。

本文主要针对重心法的不足之处, 将可行集的范围限制在线上, 也就是道路旁边, 并运用图论的方法, 建立基于线上的寻优模型, 求解出在线上 (也就是在道路旁) 的最优位置, 这样就能使得模型能够运用于实际的物流中心选址活动, 从而使选址更加科学化和精确化。

在理论层面, 本文所提出的基于线上的物流中心选址方法丰富了物流中心选址的方法, 并且将最优化理论与图论结合起来建立了一种寻找图中最优点的方法, 对具有图论特点的类似寻优问题有一定的借鉴意义。

2 问题描述与建模

2.1 物流中心线上选址问题描述

某公司需要在开拓某一区域的市场, 现在需要在这个区域内选择一个物流中心服务于这个区域内的客户。首先该公司预测了各个客户点每年与物流中心之间的货物周转量, 考虑到以后运作中物流中心与客户点之间会频繁运输, 公司要求选出的物流中心与所有客户的货物周转量之和最小, 为了减少建设成本, 第二个要求是物流中心必须建立现有的道路旁边。

2.2 符号说明

假设物流中心服务的客户的集合为ℕ, 将这些客户的位置抽象为图中的点, 将客户之间的道路抽象为图中的边, 其中集合ℕ*表示这个图中相邻点的集合;客户的个数为N;各个客户之间的在图里的距离为dij, 其中;各个客户之间的最短距离为d*ij, 其中i, j∈ℕ;各个客户的货物需求量为mi, 其中i∈ℕ;我们所要求解的目标是在这个图中边或者点上找到一点Z, 使得Z到各个客户点的货物周转量 (运输距离乘以货运量) 之和最小。

2.3 物流中心线上选址模型建立

假设目标函数, 即各个客户点的货物周转量之和为Q, Qij表示假设将Z点选在边 (i, j) 上时的货物周转量, 与之相对应的Z点与i点的距离用xij表示。

首先我们建立Qij的表达式:

式中前两项表示在边Z点到点i和点j的货物周转量, 第三项表示Z点到除过i点和j点其他客户点的货物周转量的总和。

式 (1) 只考虑了特定的边 (i, j) 上的可行解, 综合考虑其他各边上的点, 目标函数可以写为如下表达式:

约束条件1, 目标点必须在边 (i, j) 上, 表达式如下:

约束条件2, 目标点只能在图中的某一个边上, 即目标点所在的边必须仅属于集合中的一个, 表达式如下:

综上, 可以将目标表达式 (1) 和约束条件总和考虑, 整个物流中心线上选址模型如下:

3 求解算法

该模型首先需要计算出各个客户点之间的最短距离, 其中i, j∈ℕ, 这个问题在图论中已经研究得相当成熟了, 可以用Floyd算法很好求解出, 在此不再赘述。

针对本问题的综合模型, 我们可以采用分层计算, 第一层可以逐次计算出各条边上的最优点, 第二层再从这些边上计算出来的最优点选择一个最优边上的最优点。

4 算例计算与结果分析

针对本模型, 本文设计了一个算例来说明基于线上的物流中心选址的计算过程。某公司需为了开拓市场, 需要给在一个片区的5个客户点配送物资, 5个客户的位置如图1, 其中5个客户点的需求量是已知的, 如表1, 5个客户点之间的距离矩阵如表2, 公司需要在这个图上选择一个点作为物流中心的位置, 使得总的货物周转量之和最小。

首先用Floyd算法, 计算出各个客户点之间的最短距离矩阵, 如表3,

最后根据上述的分层算法, 计算出在各个边上的最优点的货运周转量, 如表4,

我们可以看出CD上的最优点时, 货运周转量最小, 为17771吨千米, 所以该物流中心在边CD上的最优点上。然后我们看程序运行出来的在各个边上的最优点, 如表5。

可以看出在边CD上取最优点时, 该最优点与C点的距离是0, 所以物流中心应该建立在C点处。

5 结语

综上所述, 本文主要是考虑了物流中心选址的限制条件必须在线上, 建立了数学模型, 并进行了算法和程序求解, 最后针对具体算例, 阐述了本模型的求解过程, 说明了求解的可行性。

此模型还可以进行扩展, 如果某些线路上存在一些区段不能作为备选点, 比如说这些区段已经被占用, 针对这种情况, 只需要改变公式 (3) , 将不能选的区段剔除掉即可。

模型的限制条件仅仅考虑了货运周转量, 如果加入其他限制条件, 比如地价、运作成本、环境等因素, 这就需要在本模型的基础上对目标函数和约束条件进行改动即可, 可作为后续研究内容。

在以后的研究中, 还可以考虑运用此方法的思想解决多点物流中心线上选址问题。

摘要：在物流中心的选址模型中, 重心法是经典和常用方法, 可是重心法的可行集是整个平面, 这在实际物流中心选址中是不可行的。在实际运作中, 物流中心必须选择在道路的旁边, 所以本文就建立了基于图论的物流中心线上选址模型, 最后针对一个算例进行求解, 说明了此方法的可行性。

关键词：物流中心选址,线上,图论

参考文献

[1] 孙惠.物流中心选址的双层规划模型及算法研究[D].山东师范大学, 2009.

[2] 王春颖, 肖丽娜, 肖朋民.物流中心选址方法的研究[J].武汉理工大学学报 (交通科学与工程版) , 2007 (6) .

[3] 荣海涛, 宁宣熙.GIS对重心法的改进及其应用[J].企业经济, 2008 (5) .

[4] 代修宇, 程国忠.Floyd算法的改进与优化[J].西昌学院学报 (自然科学版) , 2012 (1) .

[5] 张涛.基于层次分析法的物流中心选址研究[D].武汉科技大学, 2008.

[6] 李永立, 吴冲.基于图模型和最优化的评价方法[J].系统工程学报, 2013 (3) .