资源描述：
《管理论文时变环境下物流中心选址问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、时变环境下物流中心选址问题研究
时变环境下物流中心选址问题研究是小柯论文网通过网络搜集，并由本站工作人员整理后发布的，时变环境下物流中心选址问题研究是篇质量较高的学术论文，供本站访问者学习和学术交流参考之用，不可用于其他商业目的，时变环境下物流中心选址问题研究的论文版权归原作者所有，因网络整理，有些文章作者不详，敬请谅解，如需转摘，请注明出处小柯论文网，如果此论文无法满足您的论文要求，您可以申请本站帮您代写论文，以下是正文。
摘要:研究了在时变环境下,允许从配送中心出发同时访问R个配送点,且兼顾费用与可靠性的选址问题,这里
2、R是预先给定的容量约束。问题本身是NP完备的,给出了一个确定单个配送中心的启发式算法。
关键词:时变网络;容量约束;启发式算法;费用/可靠性比值
1启发式算法
启发式算法的基本思想是,对每个点i,i=1,2...,n,计算从i到其余各点在时间[0,T]内的最小费用/可靠性比值路。接着,考虑每条从i出发到j的最小费用/可靠性比值路。如果j已经在另一条路中出现,则可将到达j点的路去掉。对违反容量约束的路,则将其截短。最后保留下来的最小费用/可靠性比值路就是以i为中心的运送方案,计算i到其余各点的费用与可靠性比值之和。对应和
3、最小的点就是所求的配送中心。
在下面的算法中,我们将直接引用沙丹、许建修在中的算法结果,有兴趣的读者可以直接查看文献。
带容量约束的启发式算法:
(1)对每一个顶点i∈V,依下述方法计算出其到其余各点的运送的费用与可靠性值之和,计为(i):
①以i为起始点,采用BRP算法,求从点i到点j(j∈V{i})的费用与可靠性比值路,记为P(j)。将这些路按其经过的点的个数从多到少排序,记为Р,令Κ={i},Q=;
②在Р中取出第一条路,不妨仍记为P(j)。若j∈Κ,转(v
4、);
③若P(j)包含的不在Κ中的点(称为未访问过的点)的个数不超过R,则令Q:Q∪{P(j)},转(v);
④若P(j)包含的未访问过的点的个数超过了R,则表明此路违反了容量约束。对P(j)做如下处理:沿终点j朝起始点i逆向前进,对途经的不在Κ中的点作标记并记数。设g为第R个不在Κ中的点,f为g的前继点。将P(j)拆分成两条路:一条为P′(f),Q中还还存在着另一条路P(f),比较两条路的费用与可靠性比,保留较小的那条,仍记为P(f),并将P(f)插入Р;另一条将g直接和i相连
5、。仍记它为P(j),将已访问的点归入Κ;
⑤若Р=,转④,否则转②。
(2)令*:=min(i),记与*对应的点为i*,i*即为算法给出的最佳配送中心位置。
2算例
给定一个时变网络如图1所示。
为节省篇幅,这里我们仅给出以点1为出发点至其余各点的最小费用/可靠性比值路(其中,τ为出发时间,α为到达时间,B为费用/可靠性比值)。
P(2)={1,2},τ(1)=2,α(2)=3,B2=7.14;
P(3)={1,2,5,3},τ(1)=
6、2,τ(2)=3,τ(5)=4,α(3)=5;
B12=3/e-1.20=15,B25=3/e-2.12=25,B35=3/e-0.72=6.12,B3=46.12;
P(4)={1,5,4},τ(1)=1,τ(5)=2,α(4)=4;
B15=7/e-1.20=23.33,B54=3/e-2.12=25,B4=48.33;
P(5)={1,5},τ(1)=4,α(5)=6,B5=3.33。
算法开始时,P={P(3),P(4),P(5),P(2)
7、},Q=,K={1}。从P中取出第一条动态路P(3),其中2,5,3均为未访问点,但已超过容量限制R=2,故将该路切分为两条,一条记为P′(2),一条记为P′(3)={1,5,3},依上述方法可计算得出P′(3)的最小费用与可靠性比值=48.57,P′(2)与P(2)的最小费用与可靠性比值一样,但超过容量限制,故放弃P′(2)保留P(2),同时令Q={P′(3)},K={1,5,3}。接着,取出P(4),P(4)所包含的为未访问点,未超过容量限制,故直接放入Q中,亦即Q
8、={P′(3),P(4)},K={1,5,3,4};同理,考虑P(5),P(2)的情况。
此时,P=,Q={P′(3),P(4),P(
