物流网络设计问题.doc

此文档收集于网络，如有侵权，请联系网站删除物流网络设计问题3.1 基本形式的批发/零售物流网络设计双层规划模型批发/零售物流网络中运输路线的连接问题。此时的物流网络为公司内部的物流网络，网络中的连接线路为各个批发/零售点之间的已经建立的抽象的物流配送的连接线路。现在的任务是为了降低整个公司物流运输的总费用，在备选的几个批发/零售点之间挑选若干个点建立连接。针对该问题，基本形式的批发/零售物流网络设计问题的上层设计目标就是在现有投资约束允许的情况下使整个物流网络的运输费用达到最小。基本形式模型的下层模型一般采用UE平衡配流模型（Sheffi, 1985）。可以采用双层规划模型（P3.1）对批发/零售物流网络设计问题进行如下的描述：（P3.1）（U3.1） （3-1）s.t. （3-2） 或 1 （3-3）其中是的隐函数，它可以通过求解下层问题获得：（L3.3） （3-4）s. t. ， （3-5）， （3-6）， （3-7）， （3-8）本节使用的相关符号定义如下： 表示路段集合，其中 表示已经存在的路段， 表示备选的计划新建的路段，为任意一条路段；： 路段上的总的流量，为路段流量的向量表示； ： 从到的路径集合；： 起始节点， ；： 终到节点， ；： 起点到终点总的交通需求量，为交通需求量的向量表示；：起点到终点在路径上的流量，为网络中路径流量的向量表示；：标志路段的是否修建的0-1变量。当时表示不修建路段，当时表示修建路段。为该决策变量的向量表示；：路段行驶的时间（或费用）函数，设该函数为连续可微的单调上升函数（对变量），为阻抗函数的向量表示；：计划修建路段的修建费用；：任意足够大的正数；：为投资预算。批发/零售物流网络设计问题实际上是一个非线性混合整数规划问题（含有离散和连续决策变量），在该模型中假定O-D需求量固定，并且货车车队的路径选择行为符合用户平衡分配原则。上层的网络规划者在满足投资预算约束及其它约束的条件下使网络在添加若干路段方案后公司的总运输费用最小。在规划问题（P3.1）中，上层问题（U3.1）有投资约束（3-2）、路线连接添加方案决策0-1约束（3-3）。所以（U3.1）的目标函数代表了物流网络规划者对网络进行投资，增加新的路段，目的是使整个物流网络的系统总运输费用最小。在构造的下层问题模型（L3.1）中，假定货车车队的路径选择行为符合UE准则。约束（3-5）和（3-6）是流量的守衡及非负约束。约束（3-7）描述了路段与路径之间的关系。约束（3-8）禁止在不修建的备选路段上分配流量；如果=0，则为零，而如果=1时，不受限制。3.2 模型的求解算法而在物流网络设计问题中，假设有条计划确定的路段，则总共有种路段添加方案。如果通过穷举所有的路段添加方案来寻找最优路段添加方案将导致巨大的计算量，因此它被众多研究学者认为是极其难求解的问题之一（Gao和Sun, 2004）。求解这类模型的常用方法有Bender分解法、分枝定界法和其他启发式算法。在早期的综述文献中，Magnanti和Wong（1984）概述了网络设计问题的一般建模方法，总结了以往的求解算法，并认为针对一些特殊的离散网络设计问题Lagrange松驰法或对偶上升法能非常有效地定界。Chen和Alfa（1991）用基于logit的随机增量配流方法研究了离散网络设计问题，而刘灿齐（2001）采用了“隐枚举法”来求解离散网络设计双层规划模型。Friesz等,（1992、1993），Cree和Maher（1998），蔡金和高自友（2002），蔡金（2003）采用非数值优化算法研究了离散网络设计双层规划模型的求解算法并取得较好的使用效果，但由于此类算法求解双层规划模型时的具体参数（如编码长度等优化参数）难以确定，所以收敛性一般难以保证，况且在实践应用中可解释性也不理想，所以这方面的研究还属于探索阶段。综上所述，到目前为止一般采用比较多的相对成熟的算法还是基于分枝定界方法。显然为了将分枝定界方法较好地应用在较大规模的实际物流网络中，我们需要处理好该求解算法内在的非线性复杂性以及上下层的合理定界等问题。本章中所使用到的求解算法主要采用基于分枝定界方法的求解算法。在批发/零售物流网络设计问题中，假设有条计划确定的路段，则总共有种路段添加方案，因此如果通过穷举所有的路段添加方案来寻找最优路段添加方案将导致巨大的计算量。因此从离散网络设计问题的特点出发，为适应求解较大规模物流网络的要求，可以采用分枝定界方法对原问题（P3.1）进行求解。分枝定界方法比较适合求解混合整数规划问题，该算法不需要尝试决策变量的每一种排列组合情况，而仅通过计算组合方式中的一小部分分枝就可以得到整体的最优解。在物流网络优化问题中，分枝定界方法已经有所应用（Stairs,1968; Ochoa-Rosso,1968; Scott,1970; Leblanc, 1975），尤其是Stairs（1968）指出鉴于分枝定界方法的特性，该算法也应该可以应用于大型的网络优化中。在分析了批发/零售物流网络设计问题以及分枝定界方法的特点之后，可以发现将分枝定界方法应用在批发/零售物流网络设计中的关键是如何提高算法的计算效率，它在于以下两点：l 上界与下界的计算方法：上界取的尽可能小，而下界则应取较大的值。l 不同的分枝方法：（1）从下界最小的节点开始分枝。 该分枝方法需要较少的计算时间，但是需要较多的存储空间；因为所有等待分枝的子集以及它们的下界都需要存储下来。（2）从上次刚分枝过的节点开始分枝。 该分枝方法需要较多的计算时间，但是在存储空间方面却是高效的。在批发/零售物流网络设计问题的求解算法中，初始上界应该是某个尽可能接近但不能超过预算约束可行解的目标函数值；而计算下界的最显然的办法就是将该节点所有的自由变量都赋值为1（为了采用相对清晰的启发式求解算法求解离散网络设计问题，本章暂未考虑Brass诡异现象，虽然Leblanc（1975）为了避免Brass诡异现象，采用系统最优（SO）时的平衡流量计算目标函数，但这种假定对于城市物流网络设计问题是不切合实际。可以通过在模型中添加备用能力的办法更好的避免Brass诡异现象），此时可以认为网络的目标函数值应该比自由变量不全为1时的目标函数值要小。在分枝策略方面，由于存储介质的更新与新技术的应用，超大规模集成电路及计算应用技术的发展，海量存储器已经得到了大量的应用，CPU的计算能力也日新月异。我们可以在微型机算机上完成较大规模的批发/零售物流网络设计问题，并进一步以牺牲存储空间的方式将计算时间减少到我们认为可以承受的时间。任何分枝定界技术的最基本任务就是使用给定的分枝定界树节点的后继点值产生下界。可以构造模型（P3.1）的下界如模型（P3.2）所示。（P3.2）在（P3.1）的基础上扩大了上层模型的可行域（没有要求路段添加方案必须在投资预算之内），所以（P3.2）的最优解将小于或者等于（P3.1）的最优解，可以作为原问题的下界使用。本章提出的下界模型没有同Lelanc（1975）一样转化成为一个单层优化模型进行求解，模型（P3.2）为一个典型的连续平衡网络设计双层规划模型，可以采用高自友等（2000）基于灵敏度分析的求解方法进行求解：（P3.2）（U3.2） （3-9）s.t. （3-10）下层问题：（L3.4） （3-11）s.t. （3-15）、（3-16）、（3-17）其中：表示分枝定界树中某一个节点中值为0的集合；表示节点中值为1的集合；表示节点中自由变量集合。模型的求解算法是进行分枝、定界的过程，实际上是一个遍历二叉树中各个节点的过程，该过程本质是一个递归过程，在递归算法中仅需对子二叉树的左枝和右枝进行递归处理。我们利用图3-1给出模型（P3.1）中求解含有自由变量的某节点的左分枝及右分枝的算法基本流程。图3-1 分枝定界方法中遍历左、右分枝的基本流程图注：（1）在遍历左枝的过程中，由于没有添加新的路段，所以左枝的确定方案不会超过预算的限制，无需类似处理右枝那样对其进行可行性检查。（2）在对右枝的遍历过程中，因为计算下界的方法和其父节点计算下界的方法相同（自由变量全部置1），所以无需类似于处理左枝那样求解下界，仅需要简单的赋值操作，从而节省了较多的计算时间。批发/零售物流网络设计模型的算法步骤归纳如下：第1步：初始化。设定一个计划确定路段的初始值为。令迭代次数。将待选分枝集合清空后放入初始化后的分枝树根节点并确定一个合理的上界。第2步：选择下一步要处理的节点。从待选分枝集合中取出下界最小的节点，生成其左、右分枝：、。第3步：处理左分枝节点。1）部分解处理。：将自由变量置后计算下界。对于给定的，可以利用模型（P3.2）求解此时的物流网络设计模型，得到：、。：如果则放弃该分枝，否则将其放入待选分枝集合中。2）完全解处理。根据此时的求解该模型，得到目标函数值，如果令，保存得到的、，否则放弃该分枝。第4步：处理右分枝节点。将自由变量置零后判断该分枝是否可行，放弃不可行分枝。对于可行分枝，1）部分解处理：令本分枝下界等于其父节点的下界，即：。并将该分枝放入待选分枝集合中。2）完全解处理：根据此时的求解该模型，得到目标函数值，如果令，保存得到的、，否则放弃该分枝。第5步：抛弃现在处理的节点。第6步：如果待选分枝集合中没有可以处理的节点则停止，转第7步；否则转至第2步，。第7步：取出保存的、。3.2.3 基本形式模型的数值算例在这一节中我们采用Leblanc（1975）的算例说明上一节给出的算法是可行并且有效的。在模型中使用的数据及网络图来源于Sioux Falls, South Dakota。如图3-2所示，该网络包含24个节点及76条路段，每个节点之间为双向交通路段。在该网络图中有五条计划确定路段，新建路段的总预算为$3,000,000。路段的阻抗函数形式为：，其中及为路段的参数。已有路段的参数信息参见表3-1，计划确定路段的参数信息参见表3-2。表3-1 已有路段的参数，其中：（百小时），百小时/（千车/天）4路段路段( 7,18), (18, 7)2188( 2, 6), ( 6, 2)51712408(10,15), (15,10)587265(24,21), (21,24)3297896( 3, 4), ( 4, 3)43169(20,21), (21,20)57213728( 1, 3), ( 3, 1)43417( 4, 5), ( 5, 4)21635( 1, 2), ( 2, 1)59623( 8,16), (16, 8)48211568( 3,12), (12, 3)41416(11,12), (12,11)64615504(12,13), (13,12)29811( 5, 6), ( 6, 5)41710008(18,20), (20,18)44617(23,24), (24,23)1884512(10,11), (11,10)500750(21,22), (22,21)1674008(16,18), (18,16)26925(14,23), (23,14)42510200(15,19), (19,15)350104(22,23), (23,22)4009600(10,17), (17,10)80419296(14,15), (15,14)45210848( 8, 9), ( 9, 8)96123064(16,17), (17,16)1674008( 4,11), (11, 4)64615504(17,19), (19,17)2315544( 5, 9), ( 9, 5)503755(19,20), (20,19)3999576(11,12), (12,11)64615504(11,14), (14,11)44210608(15,22), (22,15)350525(20,22), (22,20)47111304表3-2 计划确定路段的参数及其确定费用项目编号费用（$）路段参 数1650,000( 6, 8), ( 8, 6000( 9,10), (10, 9)160373850,000(13,24), (24,13)220267841,200,000(10,16), (16,10)270324051,000,000( 7, 8), ( 8, 7)150355图3-2 算例中使用的Sioux Falls, South Dakota网络图在该算例中，我们设定初始可行求解为1, 0, 0, 0, 0。由此产生的初始上界，下界。在迭代的过程中，每一步的先后顺序参见图3-3。图3-3中的每一个空心圆圈代表着含有自由变量的分枝定界树节点，而实心圆圈代表当前已经找到的最好的可行解，五角星表示该节点为网络中剔除的节点。迭代过程中的当前上界、下界信息参见表3-3。（本文采用的试验环境：联想奔月2000型微型计算机，CPU主频800MHz，128M内存，计算平台：Matlab6；与之对应的Leblanc（1975）的实验环境为：CDC6400型计算机，计算平台：Fortran IV）图3-4 分枝定界树表3-3 算例中的分枝定界过程迭代步上界下界解0*,*,*,*,*10,*,*,*,*21,*,*,*,*31,0,*,*,*41,1,*,*,*51,1,0,*,*61,1,1,*,*71,1,1,0,*8不可行1,1,1,1,*91,0,0,*,*101,0,1,*,*111,0,1,0,*121,0,1,1,*131,0,1,1,014不可行1,0,1,1,1151,1,0,0,*161,1,0,1,*171,1,0,1,018不可行1,1,0,1,1191,1,1,0,020不可行1,1,1,0,1211,0,0,0,*221,0,0,1,*231,0,0,1,024不可行1,0,0,1,1250,0,*,*,*260,1,*,*,*270,1,0,*,*280,1,1,*,*290,1,1,0,*300,1,1,1,*310,1,1,1,032不可行0,1,1,1,1331,0,1,0,0341,0,1,0,1由此可知最优值的情况为，此时：。如前一小节所述，为了提高分枝定界方法的计算效率，上界应该取的尽可能接近下界，在批发/零售物流网络设计问题中，初始上界应该是某个尽可能接近但不超过预算约束的目标函数值。在本算例中为了说明在算法中选取不同初始上界对计算效率的影响，上界应该取，。此种确定方案的费用为$2,500,000，最接近总投资预算（$3,000,000）。采用该方案的求解过程及分枝定界树如表3-4和图3-4所示。表3-4 算例的分枝定界过程迭代步上界下界解0*,*,*,*,*10,*,*,*,*21,*,*,*,*31,0,*,*,*41,1,*,*,*51,1,0,*,*61,1,1,*,*71,1,1,0,*8不可行1,1,1,1,*91,0,0,*,*101,0,1,*,*111,0,1,0,*121,0,1,1,*131,0,1,1,014不可行1,0,1,1,1151,1,0,0,*161,1,0,1,*171,1,0,1,018不可行1,1,0,1,1图3-4 分枝定界树在表3-4中，给出了选择不同初始上界时求解该算例的迭代次数及计算时间。可以看出上界初始值的选择对算例的计算效率的影响非常大。在求解较大规模的物流网络时，选择较好的上界将大大缩短算法的计算时间，使该算法更加贴近实际情况。表3-4 不同初始上界的计算效率初始上界计算迭代次数迭代比率计算时间（秒）时间比率1，0，0，0，034100%593.9940100%1，0，1，1，01852.94%260.495043.85%表3-5给出了不同初始上界时，算法得到的最优解1，0，1，1，0所需的迭代次数及计算时间。表3-5 不同初始值迭代所需计算时间初始上界计算时间（秒）初始上界计算时间（秒）1，0，0，0，0593.99400，0，0，1，1471.66800，1，0，0，0540.97800，0，1，0，1485.17800，0，1，0，0517.08300，1，0，0，1458.18900，0，0，1，0494.99201，0，0，0，1488.10200，0，0，0，1526.99700，0，1，1，0479.41000，1，0，1，0531.99501，0，0，1，0448.27500，1，1，0，0492.65801，1，0，0，0517.46401，1，0，0，0517.46400，1，1，0，1540.54801，1，0，1，0349.18201，0，0，1，1288.26501，0，1，0，1419.94401，0，1，1，0260.49501，1，0，0，1325.18701，1，1，0，0446.1420图3-5 初始上界选取方案与算法计算时间关系图从图3-5中可以看到，当初始上界中路段确定方案所占用的资金越接近预算总数，算法的计算时间就占用的越少（个别点效果不好，可以排除）。3.2.4 基本形式的批发/零售物流网络设计拓展模型及求解算法基本形式的批发/零售物流网络设计模型考虑的是在投资预算允许的情况下，如何使整个物流网络的运输费用降低到最低程度。在这里我们可以对基本形式离散网络设计模型做一个简单的拓展，将（U3.1）中的目标函数与预算约束条件进行对调，构造了模型（P3.3），其目标是为了使整个网络的运输费用降低到某一标准（用货车车队的总行驶时间表示）而寻求最小的道路新建投资