描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787302523031丛书名: 清华大学优秀博士学位论文丛书
本书可作为运筹学、应用数学及经济管理有关专业的参考书，也可供从事物流管理工作的政府经济部门、企业的研究机构和相关专业的研究人员和管理人员阅读参考。
第 1章绪论 . 1
1.1研究背景及意义 1
1.2研究现状 3
1.2.1供应链网络优化概述 . 3
1.2.2经典选址问题 . 5
1.2.3选址-路径联合优化问题 . 7
1.2.4选址-库存联合优化问题 . 9
1.2.5考虑中断风险的选址问题 . 10
1.2.6竞争选址问题 . 11
1.3研究内容及本书结构 . 13
第 2章确定性选址 -库存 -路径问题 . 15
2.1引言 . 15
2.2问题建模 17
2.2.1问题描述 17
2.2.2数学模型 17
2.3库存成本计算 . 20
2.4算法设计 23
2.4.1初始化 . 23
2.4.2路径优化 24
2.4.3强化阶段 26
2.4.4后优化阶段 . 33
2.5数值实验 34
2.5.1标准 CLRP算例分析 35
2.5.2标准 IRP算例分析 . 37
2.5.3 ILRP算例分析 . 37
2.6本章小结 42
第 3章考虑中断风险的选址 -路径问题 . 43
3.1引言 . 43
3.2问题建模 43
3.2.1符号系统 44
3.2.2数学模型 45
3.2.3场景识别 46
3.3算法设计 48
3.3.1初始化 . 48
3.3.2车辆路径优化 . 50
3.3.3路径重分配子问题 . 50
3.3.4局部搜索算子 . 57
3.3.5主程序 . 58
3.4数值实验 60
3.4.1算例 60
3.4.2参数设置 61
3.4.3 Barreto’s CLRP算例分析 . 62
3.4.4小规模 RLRP算例分析 . 64
3.4.5大规模 RLRP算例分析 . 65
3.5本章小结 71
第 4章考虑中断风险的选址 -库存问题 . 73
4.1引言 . 73
4.2问题建模 73
4.2.1符号 74
4.2.2数学模型 75
4.3基于 RLT和 SOS2的线性化方法 . 79
目录 17
4.3.1线性化乘积项 . 80
4.3.2线性化平方根 . 80
4.4拉格朗日松弛算法 . 81
4.4.1拉格朗日松弛子模型 . 81
4.4.2下界 83
4.4.3上界 90
4.4.4拉格朗日乘子的初始化 92
4.4.5拉格朗日乘子的更新 . 92
4.4.6变量固定 92
4.4.7分支定界 93
4.5数值实验 93
4.5.1库存表达式的精度测试 94
4.5.2 HRFLP算例 95
4.5.3 RLMRP算例 . 97
4.5.4 HRLMRP算例 102
4.5.5相同和不同失效概率的比较 103
4.5.6可靠性选址模型的比较 .106
4.6本章小结 .108
第 5章考虑中断风险的竞争选址问题 109
5.1引言 109
5.2问题建模 .109
5.2.1符号系统 .110
5.2.2数学模型 .111
5.2.3对模型的进一步说明 113
5.3可变邻域分解搜索算法 .114
5.3.1算法原理 .115
5.3.2强化与多样化 117
5.3.3初始化 119
5.3.4变量固定 .119
5.3.5局部搜索 .120
5.3.6 VNDS算法 .122
5.4数值实验 .124
5.4.1 RPCP算例分析 125
5.4.2 CFLPD算例分析 130
5.4.3模型比较： RPCP与 CFLPD.133
5.5本章小结 .135
第 6章总结与展望 137
6.1总结 137
6.2展望 139
参考文献 141
附录 A计算结果 149
附录 B函数 Mir(wi)的特性 .157
附录 C证明 .159
C.1引理 4.1的证明 .159
C.2命题 4.2的证明 .159
C.3引理 4.2的证明 .162
C.4其他证明 163
在学期间发表的学术论文与研究成果 167
致谢 .169
21世纪初，出现了一系列供应链服务中断事件，暴露出了供应链网络的脆弱性。中断服务会降低生产与服务的整体效率，给企业带来难以估量的经济损失。在供应链上下游，不同企业是紧密关联的，如果从原材料供应到产品配送的任何环节出现供给和服务中断，都会影响整个供应链的运作，导致运行效率降低，增加社会经济运行压力。本书正是在这样的背景下，通过研究供应链网络的可靠性优化设计问题，寻求在正常情况和失效情况下，供应链都能以适当成本运作的模型，从而保证社会经济运行活动的正常进行。
带着这样的问题，本书从不同层次，将中断风险与选址、库存和路径等问题相结合，展开多方协调和优化策略的研究。本书以博士学位论文为主体，进行了少量修改而成，主要成果内容如下：
(1)
建立了一个混合整数规划模型，可以对供应链中的多级决策进行集成优化，设计了有效的元启发式算法，并用大量数值实验验证了算法的有效性。所提出的算法在经典的网络优化问题中，如 VRP、LRP、IRP都极具竞争力。
(2)
将设施的中断风险引入到经典的选址 -路径问题中，建立了基于场景的整数规划模型，设计了包括最大似然取样、路径重分配的元启发式算法。算例测试表明，此算法可以找到更加可靠的解，在日常运营成本只增加很少的情况下，大幅度降低应急运输成本。
(3)
首次将设施中断引入到选址 -库存问题中，建立了非线性混合整数规划模型，可以在风险分散和风险共担中找到最佳平衡。设计了可精确求解小规模问题的 SOS2线性化方法，以及能有效求解大规模问题的拉格朗日松弛算法。数值实验得出了在最优设施布局、客户指派和库存策略上的结论。
(4)
在可靠性选址模型中，考虑了存在竞争的两个决策者，建立了双层规划模型，通过引入多种割平面，设计了可变邻域分解搜索算法，并将此算法推广到求解一般的二元双层线性规划问题，在算法设计上具有理论价值。
本书研究的若干子问题，如车辆路径规划、有容量限制的设施选址、可靠性设施选址、竞争选址、周期性库存策略、库存 -路径优化、需求波动下的库存调拨等，都是物流运作领域的一些典型问题，本书提供了一些有价值的解决方案。
在未来研究中可对设施失效下的等待与动态指派等问题展开讨论研究。以色列作家尤瓦尔 ·赫拉利在《未来简史》中表达了一个观点，所有能够用算法描述的人类行为，人工智能将超越人类。可以预期未来人工智能方法在该领域将发挥越来越大的作用。
很高兴看到本书的出版，希望这些研究成果能够为物流行业降低成本和提高效率起到切实作用。书中所存在的缺点和不足，也请专家和读者批评指正。
缪立新
2018年 4月 18日于清华园
1.1研究背景及意义
不少企业和公共机构都面临着空间维度上的选址问题，以为客户提供一定的服务功能。工业企业需要在供应链中选择不同的设施，如仓库、制造和组装厂、零售网点等；政府机构也需要确定公共服务设施的位置，如学校、医院、消防站、救护站、垃圾填埋场等。设施选址影响着系统的运营水平和服务水平，好的设计方案可以有效地提高服务质量，降低运输成本。
现实案例中广泛存在着不确定因素，如需求的波动和设施的中断，给选址规划带来了很大的挑战。在过去的几十年里，大量的研究都专注于需求端的不确定性；只有较少的研究关注供应端的不确定性 [1]。实际上，设施的运作经常会被意外的事件影响，如自然灾害、停电、操作事故、罢工或恐怖袭击。虽然设施中断的概率通常比较低，但是后果是灾难性的。设施的中断，将迫使客户从其他正常工作的设施来寻求服务（尽管距离可能较远），或者完全放弃服务（产生缺货惩罚成本）。无论哪一种情形，系统运行成本都会上升、服务质量会下降。如果多个设施同时失效，所产生的不利影响将会进一步加剧。 Kleindorfer和 Saad [2]指出，中断风险的不确定性和需求的不确定性有着根本的不同，因为它们使产品的流动完全停止，并可能持续较长一段时间。设施的中断，将给供应链的结构带来本质的变化，对运营层次的决策（如库存策略、配送路径）带来影响，产生较高的应急成本。这些挑战和复杂性，使研究中断风险条件下的供应链网络设计问题成为必然。
供应链风险 [3]可以定义为：“由供应链内、外部环境中存在的不确定因素所导致的造成供应链中断或运营障碍的可能性”。21世纪头几年的一些中断事件，暴露了各个公司乃至全球整个行业的脆弱性，引起了人们对供应链风险的重视。 2001年“9·11”事件中，世贸中心和五角大楼遇袭，供应链风险问题变得空前突出。事件发生后，美国境内桥梁、隧道和机场关闭，物流受阻；零部件的缺乏给汽车行业带来了巨大冲击，福特、通用、本田和丰田都暂时关闭了它们在北美的部分工厂。 2008年中国南方遭遇百年不遇的大雪，几乎让所有的道路交通都处于类瘫痪状态；而建立在这些物流网络上的供应链系统，则无一例外地出现延迟。 2011年 3月 11日，日本发生了 9.0级大地震，并伴有大规模海啸。厂房损坏、交通堵塞和停电，造成了重大人员伤亡和财产损失，也造成了全国大范围的工业停产；半导体、液晶面板、闪存芯片等电子元件的短期供应中断，影响到了全球电子行业。 2011年 7月，泰国发生了一场严重洪灾，公路、民航等枢纽节点无法有效运转，相关企业供应链陆续出现中断。泰国是全球硬盘的主产地，这次特大洪水给全球硬盘产业带来重大冲击，导致其价格上涨 30％。时至今日，所引发的蝴蝶效应仍未结束。
由于面对供应中断事件反应的不同，直接改变了诺基亚和爱立信这两家欧洲电子公司在手机业务上的平衡。飞利浦是这两大巨头 RFC芯片的主要供应商，2000年 3月 18日，飞利浦设在美国新墨西哥州的芯片厂由于雷电火花引发了一场大火。核心部件的供应中断，对当时需求旺盛的手机业来说，无疑是个致命的重创。爱立信公司在此前为了节省成本，基本上排除了后备供应商；火灾发生时，又错误地低估了该事件的影响而未能及时做出反应，手机生产陷入停工状态，生产计划落空，失去了市场，直接导致当年手机业务亏损 17亿美元；第二年初，即宣布退出手机生产。这场持续了 10分钟的火灾，害苦了爱立信，却成全了诺基亚。诺基亚公司火线突围挽残局，迅速找到了日本和美国的供应商来承担部分芯片的生产，赶上了市场需求的高潮，在全球移动电话市场上的占有率从 27％迅速上升到 30％。
上述事件表明，当前的供应链都运行在高度不确定的环境下，中断风险对供应链网络的运营有着重大影响，会降低整体效率，给企业带来难以估量的经济损失。由于供应链上的不同企业相互关联，如果从原材料供应到产品配送的任何环节出现中断，都会影响整个链条的运作，导致供应链运行效率降低、运输成本和库存压力增大。
很多优化模型都通过各种方法，使供应链变得更加精简、有效。然而，最近的研究指出，这方面的努力虽然可以成功地降低运营成本，但是也增加了供应链的脆弱性 [4]。为了规避风险，提供一个可靠的网络设计方案至关重要，在正常情况和失效情形下，都能以低成本运行良好。因此，在中断风险的可能性下，研究供应链网络的优化设计具有重要的意义。
1.
2研究现状
1.
2.1供应链网络优化概述
供应链 [5]是围绕核心企业，通过对商流、信息流、物流、资金流的控制，从采购原材料开始，制成中间产品以及最终产品，最后由销售网络把产品送到消费者手中的将供应商、制造商、分销商、零售商、最终用户连成一个整体的功能网链结构。而供应链网络是由这些相互交互的公司或组织构成的，其目标是生产产品并在指定时间和地点，将产品发送给顾客。对供应链进行优化，就是从整条供应链最优的角度，综合考虑供应商、零售商、最终客户组成的网络，指出各方需要相互协调，以较低成本完成采购、配送等功能。考虑中断风险的供应链网络优化，是指在供应端因为台风、地震、停电、火灾等原因发生故障时，仍然可以以较低成本保证整个网络有序、可靠地运行。
一般的供应链网络设计问题都包括战略层的设施选址问题（ facility location problem，FLP），即确定设施（仓库、配送中心（ distribution center，DC）、停车场、工厂等）的最优数量及最佳位置，以使物流成本最低 [6]。设施选址决策对整个供应链网络的效率和效益的提高都起着重要的作用，并且属于长期规划项目，要考虑众多因素，这使得选址问题非常复杂。配送中心的建设投资大、周期长、回收慢，且一经选定后需长期运营，因此，合理选址就显得十分重要。为提高综合效益，在供应链网络的分析和设计时，设施选址需要模型化和定量化。
我国物流业正处于起步阶段，国际上一般以物流成本占 GDP的比例来衡量一个国家的物流发展水平。据国家发改委网站消息 [7]，国家发改委、国家统计局和中国物流与采购联合会联合通报 2015年全国物流运行情况，数据显示， 2015年社会物流总费用 10.8万亿元，其中，运输费用 5.8万亿元，占社会物流总费用的比重为 53.3％；保管费用 3.7万亿元，占社会物流总费用的比重为 34.1％；管理费用 1.4万亿元，占社会物流总费用的比重为 12.6％。社会物流总费用占 GDP的 16.0％，比 2014年下降 0.6％。而美国自 1990年开始，物流费用占 GDP的比例就已下降到 10％左右。这些数据显示，要降低物流成本、提高物流发展水平，首先应该降低物流配送成本。优化操作层的配送路径方案，运输成本最低（如运费最少），是降低配送成本的关键。车辆路径问题（ vehicle routing problem，VRP）是指在配送中心和客户位置已知的前提下，依据客户的需求量、配送车辆的容量和路况等信息，确定配送车辆数目以及每一辆车的配送路径，在满足客户需求的前提下，使总配送成本最低。
在我国 2015年的物流费用结构中，库存保管费用占物流总费用的
34.1％。库存管理是预测、计划和执行补充库存的行为，并对这种行为进行控制，重点是确定何时订货、订购多少。库存量过大，占用资金多，利息负担重；库存量过小，则会出现断档，影响生产的连续性。库存管理常作为战术层的决策，支持上游的制造过程和下游的配送过程。
长期以来，运输问题和库存问题都是被独立研究的，造成库存成本和运输成本之间存在着“效益背反”（trade-o?）现象。所谓“效益背反”，通俗地讲，即此消彼长，同一资源（如成本）的两方相互矛盾，想要较多地达到某一目的，必然会使另一方受到部分损失 [8]。例如，对零售商来说，他希望在不缺货和及时满足客户需求的前提下，尽可能降低自己的库存水平（零库存），所以他希望供应商能够准确、及时和频繁地送货，这必然造成供应商运输成本的增加；对供应商来说，他希望大批量配送，以取得生产和运输的规模效应，这必然导致零售商库存水平上升、库存成本增加。因此，把库存和运输分开来单独研究，会使得一方成本的降低以另一方成本的上升为代价，难以作出对供应链系统整体最优的库存和运输策略。对库存和路径的整合研究，即库存 -路径问题（ inventory routing problem，IRP），或库存-运输联合优化（ inventory transportation integrated optimization，ITIO）问题可以通过协调控制配送过程中的库存成本、运输成本、配送频率和配送数量等因素，达到有效组织和管理配送活动的目的。
在过去的几十年里，学者们对 FLP和 VRP分别进行了大量的研究。 Salhi和 Rand [9]指出，将这两个问题分开优化，很容易陷入子问题最优、整体次优，从而增加配送总成本。 Stenger等 [10]进一步表明 FLP和 VRP之间存在强烈的相互依存关系。作为 FLP和 VRP的集成问题，即选址 -路径问题（ location routing problem，LRP）逐渐成为研究热点，指在由一系列客户和潜在配送中心构成的系统中，确定开放的配送中心位置，同时确定配送车辆从各配送中心出发、完成多个客户需求的行驶路线，使得总费用最小或配送时间最短。
综上，在供应链网络设计中，选址（ location）决策、库存（ inventory）决策、路径（ routing）决策都是相互联系的。 Chopra和 Meindl [11]指出，供应链管理的功能可以根据其决策分为战略层、战术层和操作层。战略层面的决策包括协调整个供应链网络（如选址），战术层面的决策涉及到长期的生产决策（如库存），业务层面的决策都集中在短期计划（如车辆调度）。从供应链网络长久的运营来看，三个层次的决策耦合度非常高，相互影响。因此，供应链设计就是在同时兼顾战略层、战术层、操作层的基础上，考虑选址、库存、路径决策，将供应链的长期运营成本减小到最低。本书借鉴了 Guerrero等人[6]的工作，将供应链网络设计问题等价于选址 -库存-路径联合优化问题（ inventory location routing problem，ILRP）。
1.2.2经典选址问题
经典的选址问题有覆盖问题、 P -中值问题（P -median problem，PMP）、 P -中心问题、无容量限制的设施选址问题（ uncapacitated facility location problem，UFLP）、有容量限制的设施选址问题（ capacitated facility location problem，CFLP）等 [12]。下面列出了 CFLP模型 [12]，这个模型将在后文中被多次用到。
min汇 fj yj 汇汇dicij zij (1.1)
j∈J i∈I j∈J
s.t.
汇 zij = 1, ∀i ∈ I (1.2)
j∈J
汇 dizij《 Cjyj, ∀j ∈ J (1.3)
i∈I
yj,zij ∈{0, 1}, ∀i ∈ I,j ∈ J (1.4)
其中，集合 I和 J分别是客户点和候选设施的集合，参数 fj和 Cj分别是设施 j的开放固定成本和容量， di是客户 i的需求量， cij表示客户 i到设施 j单位需求量的运输成本；二元决策变量 yj =1表示开放设施 j，zij =1表示客户 i的需求由设施 j来满足。引入下面的有效不等式，能加强问题 (1.1)∼(1.4)的线性松弛：
zij《 yj , ∀i ∈ I,j ∈ J (1.5)
汇Cj yj》汇di (1.6) j∈Ji∈I
UFLP模型由式 (1.1)、式 (1.2)、式 (1.5)和式 (1.4)组成。选址模型的标杆算例常采用美国地图数据 ①。这组算例含有一个 49节点的数据集，包括华盛顿以及 48个内陆州的首府；一个 88节点的数据集，包括上述 49个节点和美国最大的 50个城市（去掉重复点）；一个 150节点的数据集，包括美国最大的 150个城市。每个节点同时作为客户点和候选设施点（即 I = J），节点需求与所在州的人数成正比，节点坐标用经纬度表示。这些算例在文献 [12]中提出，并由文献 [13]做了修改。 49节点的 UFLP最优解如图 1.1(a)所示（图 1.1(b)和图 1.1(c)，将分别在 1.2.4节和 1.2.5节中加以介绍），一共新建了 5个设施。
P -中值模型是指，给定需求已知的客户集合，在若干候选设施集合中，找到 P个设施，并指派每一个客户到一个特定的设施点，使客户和设施点之间的运输费用最低，其数学模型表示为：
min汇汇 dicijzij (1.7) i∈Ij∈J
s.t.汇 yj = P (1.8)
j∈J
式 (1.2),式 (1.5),式 (1.4)
①数据来源： http://coral.ie.lehigh.edu/ larry/research/publications/
图 1.1模型的比较
(a) UFLP; (b) LMRP; (c) RFLP
若运输成本 cij独立于需求量，那么从目标函数 (1.1)和 (1.7)中移除参数 di即可。
覆盖模型，就是对于若干需求已知的客户点，确定一组服务设施来满足这些客户点的需求。此模型需要确定设施的最小数量和合适位置，可以分为两类 [14]：集合覆盖模型，即用最小数量的设施去覆盖所有的需求点；最大覆盖模型，即在给定数量的设施下，覆盖尽可能多的需求点。
评论
还没有评论。