基于p-中值模型的物流中心选址问题研究 Research on Logistics Center Location Problem Based on p-Median Model
 

Advances in Applied Mathematics
Vol.05 No.02(2016), Article ID:17667,6 pages
10.12677/AAM.2016.52035

Research on Logistics Center Location Problem Based on p-Median Model

Xu Tong, Huan Liang, Lina Zheng, Yanyan Wang, Rongyu Luo

School of Mathematics and Statistics, Northeastern University at Qinhuangdao, Qinhuangdao Hebei

Received: May 3rd, 2016; accepted: May 23rd, 2016; published: May 26th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

For logistics center location problem, this paper analyzed and compared several commonly used location methods and algorithms. The p-median model for solving the logistics center location problem is established and the fast solution of the model is realized by using Greedy Dropping Heuristic Algorithm. Combined with specific cases, a kind of actual location problem is solved to verify the correctness of the model and the feasibility of the algorithm by writing the program corresponding to the algorithm.

Keywords:Logistics Center, Location, p-Median, Heuristic Algorithm

基于p-中值模型的物流中心选址问题研究

童 旭,梁 欢,郑丽娜,王岩焱,罗融宇

东北大学秦皇岛分校数学与统计学院,河北 秦皇岛

收稿日期:2016年5月3日;录用日期:2016年5月23日;发布日期:2016年5月26日

摘 要

针对物流中心选址问题,分析和比较了几种常用的选址方法和求解算法。建立了用于求解物流中心选址问题的p-中值模型,利用贪婪取走启发式算法(Greedy Dropping Heuristic Algorithm),实现了模型的快速求解。结合具体案例,编写了算法对应的程序,解决了一类实际的选址问题,验证了模型的正确性和算法的可行性。

关键词 :物流中心,选址,p-中值,启发式算法

1. 引言

随着电子商务和互联网的高速发展,网购逐渐成为消费者乐于选择的购物方式,随之迅速发展的是物流行业。现代物流业在全世界范围内正在蓬勃快速的发展,新的理念和运作方式导致了一大批理论与应用的研究问题的产生,从而也推动了一系列的研究工作 [1] 。各个学科的理论成果在物流领域的应用也逐渐发展起来,其中运筹学是用来解决物流领域优化一类问题的常用方法,可以系统地分为定量分析和综合评定两类,具体有混合整数非线性规划、双层规划、层次分析法、数据包络分析法等方法 [2] 。

影响物流中心职能发挥的首要问题是如何科学地选址,在考虑物流规划部门和客户双方利益的基础上,可以采用双层规划模型描述物流配送中心的选址问题,并通过层次遗传算法来求解 [3] 。多物流配送中心布局对其中心功能的发挥影响极大,对于多物流配送中心选址问题,可以采用一种基于改进蚁群算法来解决 [4] 。用于物流选址问题的模型主要分为连续选址模型和离散选址模型两大类,针对不同的问题,采用相应的方法科学地进行选址,不仅会降低物流中心运营费用,也可最大程度为需求者提供便利的服务。

2. 问题分析

按照待选目标区域特征,可以将选址问题分为连续选址和离散选址 [5] 。连续选址是根据目标函数,在一定区域内进行全平面选址,连续选址的代表方法是交叉中值法和重心法。离散选址是在若干备选地址中选取所需数量的地址,使得目标函数达到最优。离散选址常用的模型有最大覆盖模型、集合覆盖模型和p-中值模型。

在连续选址中,通过交叉中值法选出的地址可能不是最优地址,通过重心法只能实现单一物流中心选址。连续选址的结果有可能不符合实际要求,可作为实际选址问题中的参考。本文采用离散选址方法,建立了p-中值模型,并利用启发式算法对该模型进行快速求解。

3. 模型的建立和实现

p-中值模型是指在给定m个备选物流中心位置中,选取p个位置,并为每个需求点指定相应的物流中心,使得各个物流中心到需求点的运输费用之和最低 [6] (如图1所示)。

3.1. 基本假设

① 各需求区域和备选物流中心均当作几何上的点看待,各需求点的需求量和位置以及备选物流中心的位置已知;

② 需求点到物流中心的距离按直线距离计算;

③ 需求点到物流中心的运费与两点之间的距离成正比;

④ 各需求点的需求均可得到物流中心的满足。

Figure 1. Schematic diagram of p-median model

图1. p-中值模型示意图

3.2. 模型建立

为了简化模型,可以将需求点的权重与需求点到物流中心的距离的乘积之和作为需要优化的目标函数,即目标函数为:

(1)

根据选址要求得到的约束条件为:

(2)

(3)

(4)

(5)

(6)

I为需求点集合,为第i个需求点的权重(例如需求量);J为备选物流中心的集合,J = {1,2,…,m};p为拟建立的物流中心的个数且p < m;表示的含义为,当需求点i在物流中心j处得到满足时为1,否则为0,(2)式表示每个需求点只能被指派给一个物流中心;的含义为,当物流中心在j点建立时为1,否则为0,(3)表示最终选取的物流中心的个数为p;(4)式保证需求点不会被指派到未被选中的物流中心 [7] 。

3.3. 模型实现

由模型建立的过程可以看出,实现p-中值模型需要选择合适的物流中心位置,并且将各个需求点指派到所选出来的物流中心。

求解p-中值模型的算法有精确算法和启发式算法,精确算法不适用于规模较大的问题,常用的是贪婪取走启发式算法,算法的具体步骤如下 [8] :

Step 1:设置循环变量k = m,将m个备选物流中心全部选中,将每个需求点指定到离该需求点最近的备选物流中心(下面称为备选点);

Step 2:取遍,将指派给j的需求点按照最近的原则重新指派到其他备选点,计算新的指派下的目标函数值,记为

Step 3:当j取遍集合J后,选取使得,令

Step 4:若k = p,则算法停止,否则返回Step 2。

4. 案例分析

秦皇岛市留守营镇有66个村庄,图2为该镇地图(来源:百度地图),为方便村民收发快递,现拟在该镇建立若干个快递代收点。

查阅资料可获取该镇各村庄地理位置信息(见表1),经过实地考察,根据地理、交通和周围环境等因

Figure 2. The map of Liushouying town

图2. 留守营镇村庄地图示意

Table 1. The latitude and longitude of the villages in Liushouying town

表1. 留守营镇村落经纬度表

素,初步选出15个符合当地实际情况的快递代收点备选地址并记录其位置(见表2)。现拟从中选出8个作为建设快递代收点的位置,选择的原则是方便各村的村民,即各村庄离拟建立的快递代收点的加权距离之和最小。

这个实际问题可用p-中值模型来解决。考虑到现实因素,将该镇相隔较近的村落看作一个村落,少数偏远村落则可适当忽略,最终需要考虑村落共55个,利用MATLAB软件做村落分布点图,如图3所示。

由于各村人数相差不大,并且对快递服务需求量相当,所以为简化问题,将各村需求量看作是相同的,即(1)式中的。用Dev-C++编写贪婪取走算法的程序,运行可知所选出的8个地址标号分别为:1、4、7、8、10、11、12、15,并且55个村落被指派到相应的快递代收点,指派方案见表3

Table 2. The latitude and longitude of alternate express collection points

表2. 备选快递代收点经纬度表

Table 3. The latitude and longitude of alternate express collection points

表3. 备选快递代收点经纬度表

Figure 3. The map of Liushouying town

图3. 留守营镇村庄地图示意

5. 结语

本文通过对物流中心选址问题的详细研究,建立了用于解决一类选址问题的p-中值模型,介绍了贪婪取走启发式算法,实现了模型的快速求解,使物流中心选址问题中的运费达到最小化,为以后物流中心选址研究提供了借鉴。但本文有些假设与现实有所不同,会在一定程度影响到选址的结果,这也是下一步研究的重要内容。

基金项目

东北大学秦皇岛分校大学生科创基金项目,项目编号CX16505。

文章引用

童旭,梁欢,郑丽娜,王岩焱,罗融宇. 基于p-中值模型的物流中心选址问题研究
Research on Logistics Center Location Problem Based on p-Median Model[J]. 应用数学进展, 2016, 05(02): 276-281. http://dx.doi.org/10.12677/AAM.2016.52035

参考文献 (References)

  1. 1. 曹钦. 物流配送中心选址问题研究[J]. 劳动保障世界(理论版), 2013(11): 180.

  2. 2. 崔荣升. 运筹学在物流配送中心优化布局的应用综述[J]. 物流工程与管理, 2015(11): 58-59.

  3. 3. 李昌兵, 杜茂康, 曹慧英. 基于层次遗传算法的物流配送中心选址策略[J]. 计算机应用研究, 2012(1): 57-59.

  4. 4. 王勇, 何宇. 基于改进蚁群算法的多物流配送中心选址[J]. 经营管理者, 2011(2): 298.

  5. 5. 卢海容, 金晓辉, 刘士通, 肖学福, 吴会博. 基于LAP-GA的多军事物流配送中心选址[J]. 军事交通学报, 2014(1): 69-73.

  6. 6. 严冬梅. 城市物流中心选址问题研究[D]: [博士学位论文]. 天津: 天津大学, 2004: 36-46.

  7. 7. 张彩庆, 赵璐. 基于P-中值模型的电网检修公司分部选址模型[J]. 系统管理学报, 2014(4): 501-506.

  8. 8. 关怀庆, 张毕西, 欧江艳. 贪婪取走启发式算法在离散网络选址中的研究[J]. 系统科学学报, 2010(3): 49-52.

期刊菜单