物流系统优化理论.doc

《《物流系统优化理论物流系统优化理论》》课程论文课程论文1定位定位- -配送路线最优化问题研究配送路线最优化问题研究摘要摘要：LRP 问题一直是物流领域的研究热点，本文就多个工厂，多个配送中心的 LRP 问题进行了讨论，并结合库存进行了研究，建立了相应的模型由于问题本身是 NP-hard，所以我们用启发式算法对该问题进行求解，首先用类似“插入”法求得初始解，然后用类似“路线改善”并结合禁忌搜索法对所求得的解进行改进，最后进行了算例分析关键词关键词：定位 配给 车辆路线安排 禁忌搜索 库存1.1.引言引言随着当今物流向不规则性和全球化的趋势发展，企业竞争日趋激烈，企业管理者希望能协调物流系统各个环节，以最低的价格、最好的服务满足顾客的需要，因此在 LAP、VRP和其他物流决策模型的基础上，产生了集成物流管理的概念，这种概念认为：在设施（工厂、库存点或分销中心）相对于客户的位置、货物的配给、运输货物的车辆路线安排之间存在相互依赖的关系，根据这种关系来相应地进行综合优化与管理根据这种集成物流管理系统的概念，就产生了对设施定位-车辆运输路线安排为题（Location-Routing Problems，LRP)的研究。

通过建立 LRP 模型，对于多客户与多设施的情形，可同时解决确定设施最优数量、容量与寻求最优运输计划、路线安排之间的总体问题，从而降低物流成本，提高产品分销的效率一般而言，LRP 是指给定一系列潜在的设施点（这些设施的容量、位置为已知）和客户（客户的需求量、位置为已知） ，确定设施的位置和数量以及确定最佳运输行驶路线，使总的费用最低在 LRP 中有很多约束条件，如：每个客户只能从一个设施得到货物，且每个客户只能由一辆车服务；每辆车从一个设施出发，最后回到这个设施点，且每一条线路上的客户需求之和不能超过车的容量等等目前 LRP 的算法大致可以分为两类，一类是精确算法，一类是启发式算法精确算法有：分枝定界；动态规划；整数规划等启发式算法有：先解决定位-配给，然后解决运输路线安排；先解决运输路线安排，再解决定位-配给；节约成本/插入等，另外还有一些人工智能的启发式算法，如遗传算法、蚁群算法神经网络算法等虽然目前解决 LRP 的算1法很多，但其中大部分精确算法是为特定的 LRP 研究设计的，因而希望建立具有普遍意义的解决 LRP 的精确算法，为判定启发式算法解决问题的效率提供一个有意义的基准。

而目前大多数启发式算法是将 LRP 分解成几个子问题先后解决，因而在同一个决策层次内，这样的算法对定位和行程路线因素权衡分析很不充分，因而希望能建立同时解决整个 LRP 问题的启发式算法2.2. LRPLRP 模型及模型及 TabuTabu searchsearch 算法算法2.12.1 LRPLRP 的数学模型的数学模型本文讨论的是多工厂，多物流中心的定位——车辆路线安排问题，同时考虑了简单的《《物流系统优化理论物流系统优化理论》》课程论文课程论文2库存控制，期模型可叙述如下：2.1.12.1.1 基本假设基本假设（1）本文考虑的是多工厂多物流中心的定位——车辆安排问题；（2）每个客户只能由一辆车服务；（3）每条路线上的客户需求之和不能超过车的装载能力；（4）没一条线路从一个中心出发并回到同一中心；（5）所有的车辆是相同的，即装载能力相同；（6）货物大小、价值相同2.1.22.1.2 参数设定参数设定P 工厂的数目；m 客户的数目；n 配送中心的数目；N 节点的数目；p 工厂的下标；i 客户的下标；j 配送中心的下标（j=1,......,n）;节点的下标（ =1,......,N）;llM 最大路线数；工厂 p 到配送中心 j 的单位运输费用；pj配送中心 j 到工厂 p 的进货数；pjx配送中心 j 的建造费用；jf从节点 k 到 l 的行驶费用；kl客户 i 的需求；id工厂 p 的生产能力；p配送中心 j 的容量；jSV 车的装载能力；配送中心 j 的需求量；jRC 货物的单位成本；A 固定订购成本；配送中心 j 的单位时间，单位库存价值的存储成本；jh《《物流系统优化理论物流系统优化理论》》课程论文课程论文3配送中心 j 的订购批量()；jQChARQjj j2； 其他被分配到配送中心客户01jizij； 其他配送中心建立01jy； 其他上）路边（0,1rlkwklr。

其他上路节点01rkvkr2.1.32.1.3 数学模型数学模型（0）     MrNkNlklrklPpnjnjnjjjjj jjjpjpjwChQAQRCRyfx1111111)2()(mins.t. (p=1,......,P) (1) njppjx1(j=1,......,n) (2) PpmijjijijpjySzdRx11(r=1,......,M) (3) niirinVdv1,(l=n+1,......,N) (4) VrNkklrw111(k=1,......,N;r=1,......,M) (5) NlNllkrklrww11(k=1,......,N;r=1,......,M) (6) Nlkrklrvw1(i=1,......,m) (7) njijz11(i=1,......,m;j=1,......,n) (8)0jijyz《《物流系统优化理论物流系统优化理论》》课程论文课程论文4(j=1,......,n) (9) Ppmiijipjzdx11(j=1,......,n;r=1,......,M) (10)0jiryv(i=1,......,m;j=1,......,n;r=1,......,M) (11)1,ijrnijrzvv其中（0）式中第一项为工厂到配送中心的运输费用，第二项为配送中心的建造费用，第三项为货物成本与订购成本以及库存成本，第四项为配送中心到客户的运输成本。

约束（1）表示工厂生产能力的约束；（2）表示配送中心容量的约束；（3）表示每一条线路的客户需求和不能超过车的容量；（4）表示一个客户只能由一辆车服务；（5）表示路线连续性约束，即表示在一条路线上对每个节点来说，如果一辆车从该节点进那么该辆车应该从这个节点出来；（6）表示如果节点 k 被分配到路线 r 上，那么有且只有一条边流出该节点；（7）表示一个客户能分配到且只能分配到一个配送中心；（8）表示只有当配送中心开放时才能给其分配客户；（9）表示配送中心的进货与出货相等；（10）表示只有当配送中心开放时，一条线路才能始于该中心；（11）表示一个客户只能分配到一个配送中心和一条线路上2.22.2 算法的实现算法的实现2.2.12.2.1 初始解的求法初始解的求法首先任意开放一个配送中心，按节约法插入客户以生成线路，直到该线路不能容纳更多的客户，按此法依次生成其他的线路，直到该配送中心不能容纳更多的客户然后开放第二个配送中心，如此一次开放配送中心直到所有的客户被服务最后按运输问题安排工厂给这些物流中心供货，运输问题是解一个线性规划问题2.2.22.2.2 解的改进解的改进解的改进包括配送中心的改进和路线的改进。

1）配送中心的改进对于配送中心的改进，用类似 relocate exchange 的方法进行改进这种交换包括：被选中的配送中心之间的交换以及被选中的配送中心与未被选中的配送中心之间的交换，我们记这种交换为 relocate exchange2）路线的改进采用 2-opt exchange 和 Or-opt exchange，再结合禁忌搜索法对路线进行改进2-opt exchange就是在可行的基础上两条边与另外两条边交换，如图： 2《《物流系统优化理论物流系统优化理论》》课程论文课程论文5图中 表示客户， 表示配送中心， 表示配送路线Or-opt exchange就是把线路中相邻的 个点插入到其他位置，一般而言，如 2l3l图：2-opt exchange 可用于同一配送中心不同线路上的两边交换，Or-opt exchange 可用于同一线路上的点的交换，也可用于不同线路点的交换Tabu search 是一种启发式算法，为了防止算法陷入局部最优，当领域中的最优解比当前解要差时，仍把它当作新的当前解，因而它具有记忆功能和深度探索功能本文采用两层禁忌搜索法首先应用于配送中心的改进，它的邻域结构为下面定义的 relocate exchange 的邻域，再应用于线路的改进，它的邻域结构是根据 2-opt 与 Or-opt 的邻域来定义的，其禁忌表长度为 5.定义 1： 3为 relocate exchange 的邻域，其大U jexchangerelocatejU交换的中心所有的能与 小为，n 为配送中心的数目； 2no U  )1,(2) 1,(1,) 1,(1,) 1,( | ) 1,(iioptijjijjiijjjjU交换）与能被（）与使（为 2-opt 的邻域（（i,i+1）与（j,j+1）属于同一个中心上的不同路线上） 。

很容易知道它的大小为，m 为客户的数目，为所有线性集合 2mo为 Or-opt 的邻U  个连续的点中之间与个点可以插入在该loptorjjljjjU1,) 1,( |域（） 显然它的大小也为3l 2mo两层 Tabu search 算法：《《物流系统优化理论物流系统优化理论》》课程论文课程论文6Step1：初始解的构造首先任意开放一个配送中心，按节约法插入客户以生成线路，直到该线路不能容纳更多的客户，按此法一次生成其他线路，直到该配送中心不能容纳更多客户然后开放第二个配送中心，如此依次开放配送中心直到所有客户被服务最后按运输问题安排工厂给这些配送中心供货，构成初始解Step2：不断循环 Step2.1 直到不能再改善所求到的最优解Step2.1：对于每一个开放的中心 j，与其相关的 relocate exchange 邻域中的每一个 中心交换，在每一次交换中将执行 Step2.2，知道在此邻域求得最优解把此 最优解当作当前解，其反向交换被禁，更新禁忌表Step2.2：不断循环 Step2.2.1 直到不能再改善所求到的最优解。

Step2.2.1：对于每一个客户 i，在 2-opt 的邻域中求与（i,i+1）有关的最优解，把它当作当前最优解，其反向交换被禁，更新禁忌表不断循环 Step2.2.2 直到不能再改善所求到的最优解Step2.2.2：对于每一个客户 i（有时包含 i+1,i+2)在其 Or-opt 邻域中求得最优解，把它当作最优解，其反向插入被禁，更新禁忌表Step2.2.3：利用 Step2.2.2 所求的最优解从新安排工厂给这些中心供货以及从新安排库存把 Step2 求得的最优解作为我们要求的解3.3. 算例构造及结果分析算例构造及结果分析3.13.1 算例实验的构造算例实验的构造本文的数据主要采取文献的数据，其工厂、客户与待选的配送中心平均分布在 4上，客户的需。