运用混合模拟退火算法研究供应链中越库的布局和路径调度问题.docx
《运用混合模拟退火算法研究供应链中越库的布局和路径调度问题.docx》由会员分享，可在线阅读，更多相关《运用混合模拟退火算法研究供应链中越库的布局和路径调度问题.docx（20页珍藏版）》请在冰点文库上搜索。
运用混合模拟退火算法研究供应链中越库的布局和路径调度问题
运用混合模拟退火算法研究供应链中越库的布局和路径调度问题
越库的位置和路径调度问题可以被视为供应链分销网络新的研究方向。
这些问题的目的是同时设计越库中心位置和车辆路径调度模型，称为NP难问题。
为解决越库的中心位置和车辆路径调度问题在分销网络潜在的应用问题，本文提出了一种两阶段混合整数规划（MIP）模型。
然后，基于两阶段混合的算法模拟退火（HSA）并带有禁忌搜索（TS）中的禁忌表，被提出解决出现的模型。
该建议人HSA不仅可以防止解决方案发生，但还保持着随机性。
最后，并通过对HSA算法解决了随机生成的大规模的测试问题。
计算结果不同的问题表明，所提出的HSA表现良好和快速收敛到合理的解决方案。
关键词：
供应链管理；分销网络；越库中心位置；车辆路径调度；模拟退火；禁忌搜索
1.引言
越库的位置和路径调度问题被发现于新的研究领域，它考虑的越库的分销网络的两个主要组成部分，即越库的中心位置和车辆路径调度。
位置和路径调度问题涉及供应链管理战略（即位置）和战术/操作（即路径调度）的决策水平。
在早期的研究中，他们被视为相互依存的组成部分。
分别集中在两个组件对限制分销网络的设计[1,2]，因此，要处理这些重要的组件这一问题是非常重要的，同时，从精心挑选的越库中心位置中瞄准客户的高效服务。
一般来说，位置和路径问题已被广泛应用在各种的分配问题网络的实际生活中的应用中，例如，清单分发[3]，医疗后送[4]和废物收集[5]。
越库的位置和路径调度是NP-hard的问题[例如，6-9]。
通过提高这些问题的大小或考虑真实世界的情况，启发式和元启发式算法仅作为推荐可行的解决方法。
越库的分销网络在过去十年间强烈吸引了研究人员的兴趣力。
贾亚拉曼[10]考虑到传统的仓储问题，并提供了一个仓库的数量和位置，然后在不违反仓库的容量限制下以最低成本分配给客户。
Donaldson等人[11]集中于一个时间表，推动交通规划中的越库的分布网络设计。
贾亚拉曼和Ross[6]提出了一种实用的求解多产品多梯队问题的方法由模拟退火分销网络设计（SA）算法。
Li等人[12]讨论了越库中心的运作为了消除或最大限度地减少储存和拣选通过实时（JIT）调度。
那么他们的问题被转换成一个机器调度问题。
Lim等人[13]发展了传统的转运的问题，包括了一定数量的供应，转运及需求点。
Lee等人[8]是第一个提出越库中心的问题与整合模式的路径调度配送网络设计。
里夫斯[14]提出两个案例研究，考虑供应链管理和图示两种截然不同的办法来在自动化工业提供越库服务。
Ross和贾亚拉曼[7]设计了一个评价启发式算法解决越库中心的位置分销网络的供应链的方法。
Bachlaus等[15]提出集成的多级敏捷供应链网络。
这个问题被表述为一个多目标数学编程模型为了最小化固定和可变成本，并最大化车间的灵活性和体积的灵活性。
Liao等人[16]提出了一种禁忌搜索（TS）算法来解决一个模型，考虑了为了运输货物从供应商到零售商的越库车辆路径调度问题。
穆萨等人[17]提出了一种蚁群优化（ACO）的启发式算法来解决越库的分销网络的交通问题。
这项研究说明所提出的启发式算法提供的适当的结果在合理的时间。
Yang等人[18]通过仿真研究了拖车在入站和出站之间的运输费用。
Liao等人。
[19]提出了两个混合差分进化算法优化入站和出站在越库中的排序问题。
梅洛等人[20]考虑重新设计的一个问题用多层次和商品供应链网络，和模拟为一个大规模混合整数线性规划模型。
然后，他们提出了一个TS启发式算法求解该模型。
Ma等人[21]专注于考虑安装成本和时间窗约束来巩固和通过越库的分销网络运输问题。
ALPAN等[22]在多门越库转运解决问题，并做出了尝试，以找到最佳的时间表最大限度地降低库存之和卡车更换成本。
栋多等[23]通过最小化总运输供应链管理成本提出了混合多级多项目的分销网络包含越库的多级车辆路径问题。
通过浏览文献表明了越库中心的位置和车辆路径调度，同时未考虑在供应链分销网络管理。
事实上，这些问题是可以相互关联的为解决物流经理最关心的众多现实生活中的应用。
另外，位置和路径调度可以帮助管理者实现显著通过使决策生产率战略和战术层面的越库分布规划网络。
本文提出了一种两阶段混合整数规划（MIP）模型解决越库中心的位置和对于越库分布路径调度问题关于网络中的供应链。
目标函数是最小固定成本、总运输成本，在装载和分配的过程中的成本，车辆的运营成本，提早及延迟时间交付给客户的惩罚成本。
然后，本文提出了一种新的两阶段混合模拟退火（HSA）算法嵌入TS为特征的一种特殊的解决方案对于越库中心和车辆的位置表示路径调度。
最后，计算结果表明，所提出的HSA以及在执行在目标函数计算小和大规模的问题对于函数值和处理次数表现较好。
不像在越库以往的文献研究，本文关注于不仅介绍一种有效框架，通过建立新的MIP模型结合越库中心和车辆路径调度问题，而且通过一个高效的混合算法调度越库系统的两个决策水平解决了共同的位置和路径问题。
从解决问题的角度来看，本文认真设计了一种新的混合启发式算法，针对受益的两个著名的主要优点算法（即SA和TS）以最小的迭代同时达到接近最佳解决方案。
通过使用所提出的HSA，大量的解决方案回访可以减少通过提供一种短期记忆由一个禁忌表，同时保持建议对SA算法的随机性。
本文的结构是由六个部分组成。
在接下来的部分，越库的位置和路径调度问题将被定义。
第3部分介绍了拟分两个阶段MIP模型在供应链中制定的越库的分销网络。
提出的HSA元启发式算法作为解决问题的办法在第4节将被提出。
然后，计算结果在第5节中讨论。
最后，显著的结论是在第6节被讨论。
2.问题定义
越库中心是在分布的中间节点为了降低库存，同时满足顾客的要求。
通过越库，不同的货物通过入场车辆交付给该中心。
他们被立刻巩固了基于目的地，然后运出站车辆交付给客户的时间很短旨在消除存货储存[24]。
因此，最常规仓储昂贵成分可被减小。
的确，在最近一年里越库被引入作为新的物流战略涉及零售，杂货，食品公司和饮料产业[16,25,26]。
图1阐释出了提出越库的分销网络，在其中两个主要节点（即，取货和交付节点）是同时到来和整合。
本文中讨论的分销网络是一个时期，产品单一，多层级物流网络，包括供应商，越库中心和客户。
越库中心和车辆路径的位置在分销网络调度问题可以表述如下：
将一组客户与已知的需求和一组的提供潜在的越库中心。
越库的位置中心在第一阶段确定。
产品应通过越库中心交付给客户。
该每个客户的需求发货是由潜在的运输工具在满足那是从越库中心分派过程，操作上涉及多个客户路径。
然后，从越库中心的车辆路径调度的完成是为了尽量减少通过在取货和交付过程中获得的越库总成本。
在第一阶段，打开越库固定成本中心的潜力点对商品的运动从供应商到越库中心，并从越库中心到顾客。
此外，在第二阶段中分配成本与相关联含车辆的运作成本车辆的路径和运输成本考虑在内。
总之，带有多个越库的中心的分配和路径调度计划被设计成每个客户都能满意的情况。
每个客户都仅由一辆车服务。
车辆的在取货和分配的数量是有限的。
此外，假定所有的车辆位于多个越库中心，并分离取货和交付中心是不允许的。
每条路径上的总需求小于等于分配给各车辆的容量。
每个路径开始和结束于同一个越库。
此外，拾取的总数量应该等于分配的数量。
最后，提出的两阶段的MIP模型的第一阶段目的是获得离散位置中的越库中心的最小数目。
然后，目的第二阶段是获得车辆的数目和最佳路径以及多个越库中心的各车辆分销网络的到达时间。
3.提出的两阶段MIP模型
描述两个阶段MIP模型在本节中，符号，
输入参数和决策变量列示如下：
设置和输入参数：
P：
在取货过程中设置的供应商
O：
设置越库中心
D：
在分配过程中设置客户
Di‘：
客户的需求。
CAP：
越库的容量中心P来处理产品
SI‘：
供应商生产产品的数量
Fp：
固定经营成本来打开越库配送中心P
CIP：
成本从供应商到越库中心p运输产品
CPI：
成本从越库中心P到客户i运输产品
TC：
可能支付越库中心最大的总成本
K：
在取货过程可用的车辆的数量
K：
在分配过程中可用车辆的数量
Q：
每辆车的最大容量
PI：
产品在节点i装载量在取货的过程
DI：
产品在节点i卸载量在分配过程
CIJ：
运输成本从节点i到节点j在取货过程
CI’J’：
从节点i到在交付节点j的运输成本
CK：
车辆K的运营成本
CK‘：
车辆k的运营成本。
DIJ：
取货过程中从节点i到节点j的距离
DI‘J’：
在分配过程中节点i到节点j的距离
tik：
长度为车辆k上访问到节点i的取货过程
etij：
车辆从一个节点i到节点取货过程的时间
eti’j’:
车辆从一个节点i‘移动到节点j’分配过程的时间
EI：
要求以客户在分配过程中结点i却提早交付的罚款
LI：
要求以客户在分配过程中结点i总的延迟交付的罚款
Αi’：
分配过程从顾客的节点i‘交付的处罚单位
：
分配过程从顾客的节点i‘延迟交货的处罚单元
dui‘：
应付日期从客户交期要求在节点i的交付过程
决策变量：
yij：
运输产品的数量从节点i到在节点j取货过程
zi‘j’:
分配过程从运输节点i到在节点j产品的金额
DTik：
在取货过程中车辆k从节点的出发时间
DTi‘k’：
在交付过程车辆k‘从节点出发时间，
DTjk：
在取货过程中从结点j车辆的k的发车时间
DTj‘k’：
在交付过程中车辆k‘节点j的出发时间
ATjk：
车辆的k在取货过程中在节点j的到达时间
ATJ’k’：
在分配过程中抵达节点j’的车辆k’的时间
ATPK：
取货过程中到达越库中心P车辆k的时间
ATP’K’：
分配过程中到达越库中心P’车辆k’的时间
3.1越库中心位置（阶段1）
上面的符号都是在MIP模型在越库中心选址问题在第一阶段提到的方程中使用。
位置问题可以用如下公式制定：
目标函数
（1）减少固定费用来打开越库中心和成本在取货过程中从供应商到越库中心，以及从越库中心的提供产品满足分配需求的成本。
约束条件
（2）可确保每个客户在分配过程中的需求是打开越库中心唯一满足的。
约束（3）确保产品从每个供应商的数量仅仅满足每个越库中心。
约束（4）确保产品从每家供应商的数量应等于/小于比开放式越库中心在取货过程中。
约束（5）表示每个客户的需求应该比越库中心容量等于/小于在分配过程中。
约束条件（6）和（7）确保供应商的产品到越库中心，并从越库中心到客户在取货和交付过程可以进行只有当相应的越库中心是开放的。
约束（8）考虑限制总支付越库中心的成本。
约束（9）定义的模型的相应的决策变量。
3.2车辆路径调度（第二阶段）
上面的符号都是在提出的MIP模型的车辆路径调度问题多用在第二阶段越库中心。
该路径调度问题可以如下制定：
目标函数（10）最小化总运输与移动产品的取货和交付相关费用进程，每个车辆在这些过程中的运作成本总提早及延迟时间分开，并惩罚成本交付给客户在分配过程中。
约束（11）和（12）代表一辆车要到达和离开一个节点取货过程。
约束（13）和（14）表示，在分配过程中一个车辆必须到达和离开一个节点。
约束（15）和（16）认为，每一个供应商或客户属于一个并且只有一个路径，但越库中心可属于一个以上的路径。
约束（17）和（18）表示车辆的连续运动。
约束（19）和（20）考虑车辆是否到达和离开一个越库集中在取货和交付流程。
约束（21）和（22）认为车辆的到达或离开的数量在取货和交付流程越库中心应少于可用的车辆的数目。
约束（23）和（24）强制在车辆装产品的数量不能超过车辆的最大容量。
产品代表的流被表示在约束（25）。
在约束条件（26）-（29）中考虑的是到在取货和交付过程中节点之间的产品的数量。
约束（30）和（31）确保每位客户都在连接到越库中心。
约束（32）和（33）表示出从一个节点的车辆的出发时间是由到达时间在一个节点决定的，访问的长度，移动在取货和交付流程的时间总和。
到达时间在越库中心被表示在约束（34）和（35），用于取货和交付过程。
同时到达一个越库中心被限制于方程（36）和（37）。
约束（38）和（39）表示的计算的在分配过程中迟到的惩罚。
约束（40）-（43）强制要求相应的完整性以限制该模型的决策变量。
4.两阶段HSA启发式算法求解的位置和路径调度
以SA和TS交叉两个著名的算法为基础将HSA元启发式算法引入位置和路径调度。
提出的HSA具有许多优点，包括随机功能，避免循环和禁忌表跳出局部最优解。
这些特来自先前造访过的解决方案，将搜索范围限制，提高传统SA的显著性能。
SA视为一种随机搜索优化算法。
首先由大都会等人提出的[27]和由柯克帕特里克等人传播[28]。
根据对算法的工作原理是应用于冶金工业退火工艺。
该SA采用了随机方法，可直接进行搜索。
该算法通过接收非改善解决方案，从局部最优以一定的概率在每个温度逃逸。
该算法在现实生活中被广泛应用到众多复杂的组合问题[例如，2,29-31]。
TS被视为是被施加到一个局部搜索算法组合优化。
TS首先由格洛弗提出的[32]。
该算法能够逃脱局部极值发生通过禁止邻域解决方案的列表，称为搜索禁忌表。
TS已经应用在各种各样的在现实生活中[例如实际的优化问题，8,16,33]。
在下面的章节中，提出的带有禁忌名单的的HSA元启发式算法补充说明详细两级MIP模型越库的位置中心和车辆路径的越库调度网络。
HSA的算法的核心是最初基于中提出的元启发式[6,33,34]。
读者了解更多详情可参考[例如，6,7,34-36]供应链的文献。
4.1提出元启发式算法来确定位置（阶段1）
在本节中，提出的算法HAS带有禁忌表中描述位置的问题。
该搜索是由一个控制参数进行的最低成本的解决方案，即温度和冷却时间表，决定了迭代的算法的次数。
随机生成的初始状态中第一次提出的混合算法，它表示越库中心将被打开，分配给越库中心的供应商和客户。
然后，总成本的计算是由第一阶段的目标函数计算提议的数学模型完成的。
步骤1：
初始化。
初始值和最终值都考虑控制温度的参数，分别称为T0和Tf;i是一个特定的迭代的数目，N是迭代的总数。
最初的越库中心解决方案是通过随机分配的充分数量的供应商获得的和客户与在越库分配网络传送节点在越库中心之间的流量需求。
它导致一个初始可行的解决方案，涉及产品流。
解决方案的目标函数的值可以被视为目标函数获得最佳配置的值（BS），当前配置OBF（XC）和最新的配置OBF（XA）。
所有计数器被设置为1。
步骤2：
检查可行性。
该算法调查分配越库中心的产品流量，以保证越库的产能，固定费用和潜在的越库中心的数量。
另外，产品数量和顾客的需求的数量应该是被满足的。
如果配置不可行的话，我们返回到步骤1。
步骤3：
提供了一个可行的邻域解决方案:
。
一旦网络设计问题已被初始化，目标函数的值计算和可行性就要考虑。
然后，目前可行的越库分销网络配置通过选择一个供应商和重新分配的越库中心和供应商之间的产品的数量进行更新。
此外，此方法可以可用于客户。
它的执行是由随机选择的供应商和扰乱的客户。
随机分配取给货/越库中心/分配节点。
必须再次调查所有的可行性。
最后，该对于邻域解决方案OBF（XA），得到目标函数值。
步骤4：
评估目前的解决方案与邻域解决方案。
如果目标函数与邻域的方案比邻域的方案的值是较高的（OBF（XA）>OBF（XC）），继续执行步骤5。
否则，如果目标函数为最新的值成形增强了当前解决方案（OBF（XA）然后，这种解决方案相比，获得（BS）的最佳解决方案。
如果目标函数为最新配置的值比目前为止最好的值低（OBF（XA）然后更换与此邻域的最佳解决方案。
继续执行步骤8。
步骤5：
调查Metropolis的条件。
计算出相邻的解决方案和当前的解决方案之间的不同，成本=OBF（XA）-OBF（XC）。
然后，用于获得的概率的Metropolis的标准，其中，所述相对邻域解决方案是可以接受的，P（A）。
这个概率是通过下式计算
其中T是当前温度。
然后，随机数是从间隔（0,1）确定的。
如果随机数是比P（A）低级，则邻域解决方案被目前的解决方案所取代。
继续执行步骤8。
步骤6：
禁忌表。
禁忌表可以调查的每一步算法所获得的解决方案是否为参加与否。
因此，这导致了该算法的关于重新访问该限制的提前参与的解决方案。
HSA的这一特性减少了算法的CPU时间，实现合理的解决方案。
步骤7：
愿望。
愿望是与TS联系的。
它企图限制从被困在由禁忌邻域搜索算法包围的搜索。
如果得到的解决方案有禁忌算法的解决方案，该解决方案的一个邻域的目标函数比更高的愿望被选择的
步骤8：
增加计数器。
存储器和变量被更新。
该计数器可以由1递增。
如果迭代计数值是低于或等于最大迭代次数为温度水平，然后返回到步骤3。
否则，请转至步骤9。
步骤9：
调节温度。
温度适应的迭代i使用冷却时间表：
如果钛的新值大于或等于所述止动值（TF），然后迭代计数器从1和返回重新启动步骤3。
否则，程序将停止。
4.2提出了启发式的路径调度（阶段2）
在本节中，提出带有禁忌表HSA算法的步骤被用于解释路径调度问题。
步骤1：
初始化。
该路径表示被施加到编码车辆路径调度问题的解决方案，跨在分销网络对接中心。
路径的想法代表性的是，供应商和客户都以一定顺序，通过越库他们参与取货和交付流程。
例如，假设有八个供应商编号为1-8。
如果路径表示为[082730410650]，然后三条路径都需要访问所有这些八家供应商的取货的过程。
在第一路中，车辆从越库中心开始，表示为0，然后路径行驶从8，2，7，最后供应商3。
在这之后，在车辆的回到越库中心。
在第二路径，在车辆开始与供应商4，然后供应商1。
同样，在车辆行驶回服务供应商后越库中心。
在第三条路径，车辆开始与供应商6，然后供给商5。
以相同的方式，该过程可被用于交付过程。
举例来说，假设有七名客户列为数字1-7。
如果路径表示为[0713604520]，然后两个路径需要服务所有这七个客户在交付过程中。
在第一条路径，一个车辆从越库中心开始，表示为0，然后行进到客户7，1,3和最后是客户6。
在这之后，在车辆返回到越库中心。
在第二个路径，在交付过程中，车辆以客户4开始，然后客户5最终到客户2。
同样，在车辆服务三名客户后行驶回越库中心。
这是值得大家注意的是如果排除O越库中心外每个解决方案包含O连接，如果有连接在车辆路径存在O越库中心的调度问题。
用于初始化的步骤此问题，有三个子步骤，以提供一个可行的初始解。
该第一子步骤是供应商/客户分配给每个越库中心或链路，即，分组的问题。
有大量的越库中心，供应商和客户在分销网络。
每个供应商/客户应分配到一个越库中心或连接。
供应商和客户通过考虑最小分配给越库中心，由于目标函数的最小的开放及分销成本，以最小化总开放和分配成本提出的模型。
第二子步骤就是在指定的供应商/客户在提出的节约方法，以不同的路径相同的节约方法呈现[34,37]。
这个方法建立一个节约矩阵为每两个供应商/客户在同一链路。
然后，供应商/客户的节约值可以在其中相同的路径进行分组在车辆容量限制和到达时间限制是不影响的前提下。
第三子步骤是通过呈现在[34,35]的NNH方法解决排序问题。
NNH的原理是随机开始的第一个供应商和客户。
然后，将接下来的供应商/客户选择，与前一个从那些未被选择的供应商/客户相比被视为最低的成本为了建立取货和交付顺序，直到所有的供应商和客户都考虑在内。
步骤2：
改进。
这个过程是基于组合的SA和TS，以提高在每个步骤中确定的最佳解决方案的算法。
该混合算法列示如下：
（a）初始化迭代数最大值，初始温度。
设置计数=1，T0=temp-初始。
（b）设在该初始化步骤中确定的最佳解决方案是所谓当前的解决方案，XC。
对于目前的解决方案，OBF（XC）计算目标函数值。
获得初步的解决方案之后，执行下列步骤中的一个是重复用于改善初始解。
2-选择交换操作
2-选择运算操作可被用来提高单一路径。
这可以交换路径方向在取货和交付节点之间。
如果与相关的成本函数路径被增强，然后将修改后的路径被保留，否则，路径返回到最后一个条件。
例如，2-选择在拾取节点交换操作是描绘在图2[30]。
这程序同样可以用于交付节点进行。
插入方法
假设随机的路径，然后选择作为每个路径的最大[0.1×（路径的长度），2]节点，并改变整数选定的拾取和交付数量的随机节点在[0，n]和[0，M]中所选择的节点。
换句话说，一个节点可以从一条路径离开，它可以通过插入法添加到另一个路径。
所有可行性可以再次调查。
最后，让邻域解决方法称为邻近的解决方法，XA为邻近解决方法计算目标函数的目标，OBF（XA）。
（c）如果OBF（xa）则令xc=xa
否则
令
=OBF（xa）−OBF（xc）;.
令T=temp-初始/log（1+count）;
有
的概率使xc=xa.
count增量每次为1.
（d）如果count<最大迭代数，返回步骤（b）
上述算法，退火步骤（c）采用时间表法则被基于[34,38]
步骤3：
禁忌列表。
禁忌表可以调查算法每一步所获得的解决算法是否参与。
因此，这导致了该算法的限制提前参与重新访问。
HSA的这一特性减少了算法的CPU时间，实现合理的解决方案。
步骤4：
抱负。
抱负是TS相关的。
它使企图限制搜索算法从由禁忌邻域包围的解决方案。
如果得到的解决办法有禁忌邻域的环绕，该解决方案的邻域目标函数值进一步比更深入的搜索的抱负高。
步骤5：
停止准则。
在停止状态调查在该步骤中可以被视为迭代的最大数目。
如果迭代的数量比设定的最大数目更高，搜索过程停止，否则，程序重新从第2步。
图3和4描述一个带有两个越库中心和HSA元启发式算法的提出第二阶段数学模型呈现的视觉插图的解决方案。
5.计算结果
产生本节中的计算方法来验证和评估建议的HSA元启发式算法，解决提出了两个阶段的MIP模型的位置越库中心和分销网络的车辆路径调度问题。
为此目的，14个测试问题在供应链环境的大小不等区别了随机纳入样本内的小型和大型案例。
因此，在提出的两阶段GAMS软件的帮助下通过精确的方法解决了7个小规模测试问题，包括两个阶段的第一阶段的越库中心定位和第二阶段多个越库中心的车辆路径调度。
测试的问题的规模列于表1。
所有参数都给出在表2和表3中所提出的第一和第二阶段位置和路径调度模型与越库。
一些参数是随机均匀分布生成的。
值得注意的是HSA元启发式算法提出的解决问题的方法编码在MATLAB®。
所有小和大规模的测试问题通过英特尔双核运行2.8GHz的编译器和2GB的RAM运行。
对于七个小规模的测试问题，该报告的结果这些表中按公式Eq（46）计算，它表示通过HSA获得的最佳的解决方案和启发式的解决方案之间的差距。
此外，该目标函数的值，CPU次数和目标函数的值列于表4和5为这是解决给定的七个小规模的问题提出HSA元启发式算法、传统的SA算法与GAMS软件的帮助下确切的方法。
该确切的方法的对照与所提出的混合算法说明该HSA可以在较准确的方法以更少的时间大致得到近似最优解。
最优和平均值的第一和第二阶段之间的平均差异是3.87％和3.96％，表明越库分销网络中带有禁
升级会员 