数学建模启发式算法范文

导语：如何才能写好一篇数学建模启发式算法，这就需要搜集整理更多的资料和文献，欢迎阅读由公文云整理的十篇范文，供你借鉴。

篇1

关键词：物流工程；运筹学；库存控制

作者简介：谢逢洁（1974-），女，重庆人，西安邮电大学管理工程学院，讲师。（陕西 西安 710061）崔文田（1966-），男，陕西米脂人，西安交通大学管理学院，教授。（陕西 西安 710049）

基金项目：本文系教育部高等学校物流类专业教学指导委员会教改课题（课题编号：JZW2011013）的研究成果。

中图分类号：G642.0 文献标识码：A 文章编号：1007-0079（2013）04-0110-02

随着电子商务近十年的迅速发展，我国物流企业如雨后春笋般成长起来。摊开一张中国物流地图，密密麻麻的干线、支线一团乱麻似的交织在一起。然而，中国物流每年30%左右的增长速度仍然难以满足每年100%速度增长的淘宝货运需求。那么，有效地利用现有资源进行优化配置，成为物流企业满足社会经济发展需求的重要途径，这无疑给物流专业的“运筹学”教学工作提出了前所未有的挑战。根据《教育部高等学校物流类专业教学指导委员会关于物流工程本科专业培养方案的指导意见》，“运筹学”是各高校物流工程专业必需开设的学科基础课程，建议课程学分为3分左右，其他学科基础课具体课程及学分由各高校自定。这充分说明了“运筹学”课程在物流工程专业教学中的基础性和重要性。那么，根据我国物流业发展中的实际问题，结合物流工程专业“运筹学”教学需求，探讨教学内容和教学方法的改革具有重要意义，但同时这也是摆在每个物流工程专业“运筹学”教学工作者面前的重要问题。

一、我国物流业的主要问题及其原因分析

在电子商务环境下，涌现出大量种类多、批量小、批次多、目的地分散的随机零散的物流需要，这与传统的粮食、燃料、建材等大宗物资运输需求有着明显的差别。大量的零散物流需求为我国物流业发展带来了契机，同时也暴露出其存在的问题。

首先，物流成本高是我国物流业一直以来存在的问题。随着电子商务环境下零散物流需求的激增，成本问题愈发显得严重。据国家发改委2011年12月1日披露的数据，2011年1月至10月，我国社会物流总费用6.4万亿元，同比增长18.7%。目前，中国的物流成本占GDP总量比重约为18%，而日本是11%，美国是8%，欧盟只有7%。究其原因，除了油价上涨以及物流运输中的各种乱收费现象外，每年以30%左右的速度发展起来的物流企业资质参差不齐，配送中心的选址、库存控制、车辆路径规划等有利于物流企业降低成本的优化途径在一些新建物流企业中并没有得到很好地应用。这是我国物流成本高的主观因素，也是物流专业“运筹学”教学需要重点关注的问题。

此外，在电子商务环境下，客户对产品可得性的心理预期增强，进而使得其对交货时间的要求远远高于传统物流货运的要求。而我国大多数物流企业尚未形成一个完整有效的物流系统，配送中心和运输系统缺乏协调，库存控制和车辆路径规划存在矛盾，长途运输和短途配送缺乏衔接等问题普遍存在。这无疑会导致物流企业货运时间的拖延，使得客户对交货时间的需求时常难以得到满足。因此，物流系统的协调优化也是“运筹学”教学需要重点关注的问题。

二、物流工程专业“运筹学”教学的主要内容

“运筹学”教材种类繁多，本文以清华大学出版社出版的《运筹学》章节划分为例进行相关内容的阐述。目前，我国各高校管理类本科层次的运筹学教学内容通常由线性规划与目标规划、整数规划、动态规划、图与网络、排队论等几部分构成，略有差异。非线性规划、存储论、对策论、决策论、启发式方法等则通常作为研究生阶段的教学内容。物流工程专业具有管理学科的一般属性，同时还具有本专业的一些特性。为了更好地满足我国快速发展的物流业对专业人才的需求，物流工程专业“运筹学”教学应在保持管理类运筹学教学内容广度的基础上，突出物流工程专业“运筹学”教学需要解决的一些重要问题，包括配送中心选址、库存控制、车辆路径规划以及物流配送系统协调优化等问题。

1.配送中心选址问题相关教学内容

配送中心选址问题是给定某一地区所有需求点的集合，要求从中选出一定数目的需求点建立配送中心，实现对所有需求点的配送，并使得总配送路径或配送费用最小。整数规划是目前应用最广泛也是最主要的定量选址技术，其求解方法包括分支定界法、割平面法和隐枚举法，其优点是能获得精确的最优解。但是对一些模型太复杂的情况，如对整个物流网络进行规划时的大型复杂选址问题，由于变量和约束条件众多、形式复杂，往往只能用启发式算法获得最优解。此外，多目标决策方法可以和启发式算法相结合进行配送中心的合理选址。

2.库存控制问题相关教学内容

库存控制问题是在保证生产或销售对物资需要的前提下，尽可能地减少资金占用，降低物资的库存成本。目前，库存控制研究已取得了丰硕的成果，形成了较为完整的库存控制理论——存储论，主要包括定常需求的库存控制、时变需求的库存控制、随机需求的库存控制、依赖于库存水平需求的库存控制以及多种物品的库存控制等。库存控制模型的求解主要利用高等数学中的微积分原理给出最优解的性质，并结合启发式算法给出最优值。

3.车辆路径规划问题相关教学内容

车辆路径规划问题是针对一系列发货、收货点，设计适当的行车路线，使车辆有序地通过它们，在满足规定的约束条件（如货物需求量、交发货时间、车辆容量、时间限制等）下，实现一定的目标（如路程最短、费用最低、时间尽量短、车辆尽量少等）。根据研究重点的不同，车辆路径规划问题的模型构造及算法有很大差别。但整数规划、动态规划和图论是车辆路径规划问题最常用的建模方法，启发式算法在车辆调度问题的求解中得到了广泛应用。

4.物流系统协调优化相关教学内容

配送中心选址、库存控制、车辆路径规划问题之间有着千丝万缕的关系，其中一个问题的决策往往影响到其他问题的决策，如果某一问题决策失败就无法获得整个物流系统的最优。因此，物流系统的协调优化越来越受到重视，配送中心选址与运输路线安排问题的集成建模、库存控制与车辆路径的集成建模、以及配送中心选址与库存控制的集成建模已经得到了广泛研究，主要涉及的运筹学方法有整数规划、非线性规划、动态规划和启发式算法等。

由以上分析可知，物流系统优化涉及的“运筹学”教学内容主要包括整数规划、非线性规划、动态规划、图论、存储论、多目标决策、启发式算法等，这分别对应于清华大学出版社《运筹学》教材中的第5章、第6～7章、第8～9章、第10章、第13章、第16章、第17章。其中，以整数规划和启发式算法的应用最为广泛。以此为依据，笔者建议对物流工程专业的“运筹学”教学内容作适当调整，打破以教材章节为依据划分本科和研究生教学内容的模式，在本科阶段教学中增加非线性规划、存储论、决策论、启发式算法的内容，在研究生阶段教学中进一步深化整数规划、动态规划、图论的内容，保证本科和研究生阶段课程的可延续性，并在教学深度上形成一定的梯度。本科阶段侧重于物流系统基本问题的建模和基本求解方法的掌握，研究生阶段则侧重于综合问题的建模和多种求解方法的结合应用以及优化理论的创新。

三、物流工程专业“运筹学”教学的实施手段

“运筹学”是一门以数学方法为基础寻求实际问题最优方案的应用科学，特别强调对实际问题的解决。应用运筹学解决现实生产、生活中的实际问题，需要针对实际问题的优化要求及面临的客观条件作必要的假设，抽象为数学模型，然后利用恰当的数学方法加以解决。根据《教育部高等学校物流类专业教学指导委员会关于物流工程本科专业培养方案的指导意见》，物流工程专业是一门实践性很强的专业，要求该专业的教学注重理论教学与实践教学相结合，课堂教学与课外活动和谐统一。因此，对于物流工程专业的“运筹学”教学，强调对物流系统中实际问题的解决则显得尤为重要。然而，由于“运筹学”本身所具有的明显的数学学科特征，加上“运筹学”教材的通用性特点，教师在教学实践中很容易产生偏重数理演算、忽略实践应用的倾向，在基本原理和手工演算的讲授上花费大量的课时，而对于如何从物流系统的实际问题出发，抽象出合理的数学模型以及如何应用先进的计算软件实现模型的求解则重视不够，甚至忽略。鉴于此，笔者建议对物流工程专业“运筹学”教学的实施手段做以下改革尝试。

1.讲述教学法和问题解决教学法相结合的课堂教学方式

由于“运筹学”既要求对基本理论和优化方法的理解，又强调应用理论方法解决实际问题的能力。因此，笔者建议采用讲述教学法和问题解决教学法相结合的课堂教学方式。

讲述教学法是指教师运用叙述的方式传递教材知识的教学方法，也是最为常用的一种教学方法。“运筹学”的基本理论和优化方法以数学为基础，对于物流工程专业的学生而言相对抽象和晦涩。如果在课堂讲述时利用高深的数学理论来推导一个定理，或者花费大量的时间手工求解一个问题，则违背了物流工程专业“运筹学”教学的应用目的，学生不仅难以接受讲述的内容，而且其学习积极性会受到打击。因此，笔者建议教师在课堂讲述中弱化“运筹学”中定理的推导以及手工演算过程，通过板书教学与多媒体教学相结合的讲述方式，根据课程内容的需要穿插一些动画、声音视频，充分调动学生的学习兴趣，使学生快速理解“运筹学”的基本理论和优化方法。在此基础上，结合问题解决教学法培养学生应用理论方法解决实际问题的能力。问题解决教学法是启发式教学方法的一种，是以学习者为中心的教学方法。教师可在教学中有目的地引导学生选择典型的物流系统优化案例，可以从简单的配送中心选址、库存控制以及车辆路径规划问题入手，协助学生对实际问题进行合理假设、抽象和建模，使学生逐步掌握运用“运筹学”解决物流系统优化问题的思维方式和方法。

2.课堂教学、计算实验和课外活动紧密配合

由于课堂教学中弱化了定理的推导和手工演算的过程，加上启发式算法在物流系统优化问题中的广泛应用，物流工程专业的“运筹学”教学应开设专门的实验课程，将课堂教学内容和上机实验紧密结合起来，帮助学生掌握WINQSB、LINDO、LINGO、MATHEMATICA、MATLAB 等优化软件，利用计算机代替手工演算实现模型的求解。同时，注重培养学生不拘泥于课本上的算法与思维，努力尝试新方法，开拓新思路，提高自己的创造性思维能力，逐步引导学生将学习的重点放在对实际问题的分析建模和求解思路的设计上来。此外，可以鼓励学生积极参加全国大学生物流大赛，实现“运筹学”教学与物流优化实践的结合，提高学生应用运筹学解决物流企业实际问题的能力。

3.改革考核体系，突出教学重点

成绩考核是整个教学周期的最后环节，是评估教学质量和学习水平的关键。为了与物流工程专业“运筹学”教学内容和教学方式的调整保持一致，其成绩考核方式也应做相应的调整。首先，突出物流工程专业的“运筹学”教学目的，考核内容应围绕物流系统优化问题展开，比如配送中心选址、库存控制、车辆路径规划等都是重点考核内容，相应地弱化对其他专业的相关问题考核。其次，改变目前“运筹学”课程考核采取的形式单一的笔试方式，将平时课堂教学中的问题讨论和实验课程中的上机练习作为课程考核的一部分。比如，可以在课堂教学中定期地进行物流系统案例优化小测验，让学生在规定的时间内完成问题分析和模型构建，将评价结果记入课程考核，还可以在实验课程中设置一定的考核环节，检查学生利用计算机求解运筹学模型的能力，将评价结果记入课程考核。最后，在试卷考核中要注重检验学生掌握运筹学思维方式和方法的程度，即检验学生针对一个具体的物流系统优化问题展开分析，进行适当的假设和理论抽象，建立合理的数学模型的能力，避免学生把大量的时间花费到简单记忆和繁杂计算中。

四、结语

本文从电子商务环境下我国物流业存在的实际问题出发，确定物流工程专业“运筹学”教学需要重点关注的问题包括配送中心选址、库存控制、车辆路径规划以及物流系统协调优化。在此基础上，通过对这些重要问题的分析给出了物流工程专业“运筹学”教学的重点内容和章节，并对教学实施手段提出了改革建议。这些有针对性改革措施不仅有利于物流工程学生掌握运筹学的思维方式和方法，而且有利于培养学生应用运筹学解决物流系统优化问题的能力。

参考文献：

[1]杨艳，王克近.配送中心选址方法研究综述[J].物流技术，2011，

（23）：148-152.

[2]周永务.物流系统的库存控制模型与方法研究[D].合肥：合肥工业大学，2002.

[3]刘云忠，宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报，2005，19（1）：124-130.

[4]林岩，胡祥培，王旭茵.物流系统优化中的定位——运输路线安排问题（LRP）研究评述[J].管理工程学报，2004，18（4）：45-49.

[5]李文锋，毕娅.物流系统优化与仿真[M].北京：中国标准出版社，

2010.

[6]王旭.管理运筹学的课程定位研究[J].高等教育研究，2008，

25（3）：75-76.

篇2

【关键词】配电网规划；优化方法；分析

配电网规划的数学规划方法包括确定性方法和不确定性方法。其中，确定性方法又包括线性规划法、非线性规划法、动态规划法、网流规划法，而不确定方法有模糊规划法、场景分析法、风险度估计法等。配电网规划的启发式方法包括传统启发式方法、启发式专家系统和现代启发式方法。

1.配电网数学规划优化方法

（1）线性规划法。在众多的数学规划方法中，线性规划法是研究最早，也是最为成熟的一种数学优化方法，它在配电网规划中的应用几乎涵盖了配电网规划早、中期的所有研究。线性规划法又分为运输模型、线性规划、整数规划、混合整数规划等。运输模型是最为简单的一种线性规划法。由于模型简单，其求解算法也最为有力。然而，运输模型的一个严重缺陷是运输费用必须严格表达为线性化费用，而用严格线性化费用模型来代替实际的非线性化费用模型是不准确的。运输模型另一个严重缺陷是它不满足电网运行的许多约束条件。不带整数变量的线性规划是传统的、狭义的线性规划法。它的模型虽然较运输模型复杂，但其求解算法也比较成熟。

无论是采用线性规划的运输模型还是不带整数受量的纯线性规划模型，都无法考虑到配电网规划的离散性，而整数规划则弥补了这方面的缺陷。在求解整数规划问题时，由于整数规划的离散特征，解的数目是有限的，并且随整数约束变量数目的增加而呈组合性的增加，因此，通过显式的方法枚举所有解的方案通常是不现实的。整数规划的常用方法是分文定界法，它是一种把隐式枚举和显式枚举有效结合起来的整数规划方法，它的有效性依赖于它的枚举逻辑的有效性。

（2）不确定性规划。目前，在配电网规划中考虑不确定性主要有三种方法。第一种方法是采用模糊数学理论。对配电网规划问题建立了相应的模糊线性规划模型，并相应发展了直流模糊潮流和交流模糊潮流。建立了以模糊供电总成本最小为优化目标，通过计算电网故障状态下的模糊电量不足期望值计算模糊缺电成本，最后利用遗传算法产生动态优化解。采用盲数模型在合理的考虑多种不确定信息基础上进行了电网规划，达到了理想效果。第二种方法是场景分析法。场景分析法并不直接对配电网规划中的不确定性因素进行建模，而是将未来规划年的环境预想为多种可能的确定性场景，然后在不同的场景下进行确定性的常规配电网规划，考虑对各种场景都具有较高适应性的配电网规划方案为最优的柔性方案；第三种方法是风险评估法。这种方法是通过对可能出现的不确定性情形进行评估和考虑，确定各个方案的风险率，然后进行确定性的电网规划，从而得到最优的柔性扩展方案。

2.配电网启发式规划优化方法

以上分析了数学规划方法在配电网规划中的应用，可以发现，非线性规划方法的局限性使得建立在非线性费用函数和非线性约束条件上的配电网规划模型往往得不到有效的解，而混合整数线性规划模型既弥补了运输模型和不带整数变量的纯线性规划模型过于简化的特点，又避免了非线性规划的“非鲁棒性”，因而成为求解配电网规划问题较理想的数学规划方法。但是，即使是这种最为理想的数学规划方法，当进行实际的配电网规划时，由于变量的数目和约束条件很多，也会变得非常因难，更不用说再在配电网规划中加入其他方面的考虑，如不确定性因素等。针对以上数学规划方法的不足，启发式算法的特点就更为突出，它综合考虑了规划效率和规划效果两个指标。在实践过程中，许多启发式方法，特别是现代启发式方法常常能给出令人满意的、高质量的解。启发式方法的优点是直观、灵活、计算速度快，便于规划人员在规划过程中参与具体的决策，通过规划人员过去的经验和常用的配电网规划启发式规则，并借助于数学规划方法，得出符合工程实际的规划方案。

（1）传统的启发式方法。传统的启发式方法通常基于系统某一性能指标对可行性路径上线路参数的灵敏度，根据一定的原则，逐步选代直到得到满足要求的方案为止。这种方法在配电网规划中的应用主要是结合“支路交换”技术进行的。所谓支路交换是指：对辐射状配电网，通过添加—条支路来形成一个环，然后断开另一条支路以恢复其辐射状网络结构。重复该过程，直到任意支路交换均不能使目标函数减小为止。

（2）专家式启发方法。启发式专家系统可以看作是传统启发式方法的发展，它与传统启发式方法的区别是在规划过程中引入了规划专家的经验，并便于规划人员参与到具体的规划决策中去。值得指出的是，专家系统不是用来代替规划人员的，而是利用存放在知识库中的知识和数据库中的基础数据，并通过推理机的推理，给规划人员提供相对较优的规划方案，而最终的规划方案的选择是由规划人员作出的。

（3）现代启发式方法。现代启发式方法是一种通用的优化算法。它的另外一个重要特点是所有这些方法均能实现并行计算。由于现代启发式方法在求解组合最优问题时表现出的卓越性能，在过去的20年中，它受到前所未有的关注。然而，现代启发式方法也有其不足之处，它在处理具体问题的约束条件时，虽然采用惩罚函数的方法把约束条件加到目标函数中去，但是在如何选择合适的惩罚函数方面，它往往缺少有效的手段。另外一个不容忽视的缺点是，当配电网节点比较多时，不可避免的会出现“维数灾”问题。

3.结论

综上所述，在配电网架优化规划的各种方法中，总的来讲可以分为数学规划和启发式算法两大类。但是，即使对于最理想的数学规划方法，由于配电网规划中变量的数目和约束条件很多，使用该类方法变得非常因难，更不用说再在配电网规划中加入其他方面的考虑，如不确定性因素等。而启发式算法又分为传统启发式方法、专家式启发方法和现代启发式方法的算法。传统的启发式方法具有较高的计算效率，但是容易陷入局部最优解；专家式启发方法目前还不成熟，有待进一步研究。 一方面，从表面上看，对于规划问题计算效率似乎并不重要，但是配电网规划中负荷点众多，若使用输电网规划方法或遗传算法等方法，不可避免地会遇到“维数灾”问题。更重要的是，实际上任何一种优化规划方法都是在规划工程师根据经验确定了设计思路和限制因素的情况下开展的，规划工程师需要根据所得结果不断调整设计思路和限制条件。因此电网规划实际上是一种人机交互式的设计过程，人的艺术性和经验性在其中起到了很大的作用，优化规划方法仅仅是针对设计师各种思路的辅助工具。因此要求优化规划算法具有较高的计算效率，以便能够对设计师众多的设计思路和调整方案产生较快的响应。另一方面，实践经验表明：对于配电网架规划问题，尽管存在大量局部最优解，但是大部分局部最优解与全局最优解的指标相差不大，作为工程近似最优解完全可行。

参考文献

篇3

【关键词】物流配送；双向物流；物流路径优化；蚁群算法；减法聚类

Two-way Logistics Path Optimization Problems Based on Clustering Analysis Research

LIU Yan-qiu YANG Yong

（Shenyang University of Technology， Shenyang Liaoning 110000， China）

【Abstract】According to the characteristics of two-way logistics， this paper focus on analysis and research the vehicles distribution. In order to better coordinate the vehicle path selection and the relationship between transport costs， and better conditions for considering comprehensive factors and the choice between nodes， study of two-way logistics path problem method， established the mathematical model of optimal path minimization. Finally based on path optimization method and the research situation， adopted the cluster analysis and the ant colony algorithm， and it has been verified by the simulation， the results reasonable and effective.

【Key words】Logistics distribution； Two-way logistics； Logistics path optimization； Ant colony algorithm； Subtraction clustering

0 引言

物流配送在物流管理中占有重要地位，它是指按照客户的订货需求，在配送中心进行分货、配货，并调度车辆及时为客户配送货物[1]。车辆路径问题（vehicle routing problem，VRP）是车辆配送研究中最核心的问题，一直是组合优化领域的热点和前沿问题[2]，而双向物流路径优化问题（vehicle routing problem with simultaneous delivery and pickup，VRPSDP）是VRP问题中的一个典型，它是指同时带送货取货的物流车辆路径优化问题，既考虑了客户需要的货物从配送中心送到各个客户，又需要把客户需要回送的货物运回到配送中心，要求取货送货同时进行，因此比单向物流问题还要复杂，也是一种NP-hard难题，所以求解复杂度较高，计算量较大。本文在前人研究的基础上通过聚类分析方法和蚁群算法对双向物流路径优化问题进行了求解。

1 双向物流配送的数学模型

1.1 问题描述

双向物流路径优化问题可以这样描述：

已知有C个客户点，给定每个客户的坐标点和需求量，货车从配送中心出发，将货物送到各个客户，并同时把客户供应的货物带回到配送中心。车辆应在条件允许下进行服务，当完成任务或者不存在能满足约束条件的情况下，返回配送中心，直到所有的客户的送取货任务完成，整个流程结束。物流路径优化要求在满足约束的条件下，合理安排货车的配送路线，使得运输成本最小。由于运输成本很大程度上是由货车的路径长度决定的，因此本文求解VRPSDP问题的目标函数的最优解就是要求路径最短。

1.2 数学模型的建立

1.2.1 参数说明

1.2.2 数学模型

根据上面对VRPSDP问题的描述和已设定的数学参数，加之针对该问题所需要考虑的约束条件，对此问题进行了建模，将服务完所有客户点后所有车辆的行驶总路程定义为目标函

2 VRPSDP模型的求解

本文中求解模型的方法，首先是通过FCM聚类，把需要提供服务的城市进行分类，然后再用蚁群算法在满足约束的情况下对每个分类进行求解最优路径，具体做法如图1所示。

图1 求解流程图

3 实例仿真

为了检验上述双向物流路径优化方法的有效性，本文采用实例数据对其进行性能分析。设车辆从配送中心出发，为各个客户提供服务，配送中心坐标位置是（0km，0km），车辆在满足约束的情况下向 30 个客户配送货物。

首先经matlab仿真得到的30个城市的聚类图如图2所示。

图2 经FCM聚类的城市坐标图

然后经过蚁群算法对每个聚类进行路径优化，得到的车辆配送路径图如图3所示。

图3 车辆配送路线图

4 结论

本文针对双向物流的特点，首先给出了问题的相关描述，然后通过抽象建模，给出了带路程和负载量约束的双向物流路径优化模型。根据给出的VRPSDP问题模型，用基于FCM聚类和蚁群算法的混合算法对模型进行求解。最后通过仿真实验，证明了本文混合算法求解双向物流路径优化问题的的正确性和有效性。

【参考文献】

[1]杨燕霞，伍岳庆，姚宇，等.带时间窗车辆调度问题的启发式算法研究与应用[J].计算机应用，2013，33（S1）：59-61.

篇4

关键词：车辆路径问题；遗传算法；ExtendSim；仿真；优化

中图分类号：U116.2 文献标识码：A

Abstract： This article has introduced the classical vehicle routing problem（VRP）in the field of logistics and the algorithm which can solve the problem firstly， then discusses that how to apply genetic algorithm to solving VRP， and describes how ExtendSim simulation software construct a model and make a optimize for an certain VRP in detail， with this method， finally concludes the optimal solution， and proves that the simulation optimization method is an effective way to solve the VRP.

Key words： vehicle routing problem； genetic algorithm； ExtendSim； simulation； optimization

我国国家标准《物流术语》（GB/T 18354-2006）中，给物流下的定义是：“物流是指物品从供应地向接收地的实物流动过程。根据实际需要，将运输、存储、装卸、搬运、包装、流通加工、配送、信息管理等基本功能实施有机结合。”物流有多方面的功能，而运输和储存保管则是其主要功能。在整个物流活动过程中，运输是其中各项子活动的核心活动，它是第三利润源的主要的源泉[1]。

日本在20世纪70年代就对物流有深刻的认识了，日本早稻田大学的西泽修教授在其著作中把物流称作不为人知的利润源泉，他认为，物流能为企业创造价值，是企业的利润源泉。石油危机后这一观点得到证实，物流也因而在企业管理中得到更加重视。目前我国生产型企业的物流成本占到总成本的20%～30%，而发达国家的则为10%左右[2]。因此，为了降低企业经营成本，获得更多的利润，必须尽量降低物流成本的比重，这对于国民经济的更好发展具有十分重要的作用。

在商品经济社会中，人们的生活质量与商品消费息息相关，而商品的价格直接影响人们的生活水平，如果商品价格不合理，超出人们普遍的可接受范围，那么人们的生活幸福度将会大大降低。而商品价格的构成部分除了有生产成本，还有更重要的一部分是物流成本，并且物流成本中的运输费又占了较大的比重。商品运输需要耗费大量的能源动力，消耗越多，花费成本越高，如果运输组织的不合理，就会加大运输成本，因而抬高物流成本，商品价格也因而升高，结果是不仅降低企业的利润，也间接提高人们的生活成本。

所以，运输问题是物流领域中值得研究的关键问题。其中车辆路径问题（Vehicle Routing Problems，VRP）是运输问题中的一个热点问题。该问题是指：在物资流通过程中，每个需求点的位置和需求量已知，供方如何调度车辆和安排行车路径向需方供应物资，使得在满足需方需要的同时也达到某些关键目标（如车辆数尽量少、花费时间尽量少、费用最少、路程最短等）。

学者们很早就开始对车辆路径问题进行了研究，积累了丰富的研究成果。在20世纪50年代末，车辆路径问题首先被G.Dantzig和J.Ramser[3]提出，两位学者根据如何运送汽油到加油站这个现实中的问题，利用数学方法对其建立模型，并得出求解算法。在1964年，Clark和Wright这两位学者研究了G.Dantzig和J.Ramser的方法后，认为后者的方法有改进的空间，并最后提出了Clark-Wright节约算法（即C-W算法）。从此VRP成为运筹学领域的研究热点。五年后，Christofides与Eilon又想出新的方法，他们应用2-opt和3-opt处理VRP，取得较好的效果。到1981年，Fisher、Jaikumar和Gullen、Ratliff、Jarvis提出不同的研究方法。前者主要利用数学规划，来对VRP进行最优化处理，后者则是运用人机互动的启发式方法处理VRP。到90年代，学者们开始利用人工智能构造大量的启发式算法来解决VRP，如禁忌搜索发、模拟退火法、遗传算法等。首先采用遗传算法（Genetic Algorithm，GA）的学者是Holland[4]，他利用遗传算法中的编码方法处理了VRP。在这几种人工智能方法中，遗传算法能较好地逼近最优解的同时具有较高的运算速度和效率，具有很好的发展前途。

1 VRP数学模型及遗传算法

1.1 VRP的基本数学模型

VRP的一般描述[5]：

（1）车辆的载重量大于等于配送路径上总的需求量；

（2）任一配送路径的长度小于等于车辆在一次配送任务中的最大行驶距离；

（3）每个需求点的需求都只能被同一辆送货车满足；

（4）设定每辆车都是从中心出发开展配送任务，任务完成后再重新回到中心。

将一个配送中心编号设为0，该配送中心拥有车k辆，车辆数m，车的额定载重量为q，该中心面向L个客户，第i个客户需求量为g■，且g■≤q（i=1，2，…，L），VRP的基本模型如下：

minz=■■■c■x■ （1）

■g■y■≤q ？坌k （2）

■y■=1 i=1，…，L （3）

■x■=y■ j=0，1，…，L； ？坌k （4）

■x■=y■ i=0，1，…，L； ？坌k （5）

x■=0 or 1 ？坌i，？坌j，？坌k （6）

以上式（1）中，c■表示由点i到点j的运输成本，该函数为最小运输成本目标函数；（2）为车容量的约束；（3）表示每个客户仅有一辆车服务；（4）、（5）表示到达和离开某一客户仅有一辆车。x■和y■为变量，定义为：

x■=■

y■=■

1.2 遗传算法

本文中的仿真软件ExtendSim拥有一个自带遗传算法的优化模块。遗传算法在处理车辆优化调度问题时，有以下几个步骤：

（1）确定染色体的编码和初始群体

对可行路线编码，如长度为1+m的染色体编为：

0，i■，i■，…，i■，0，i■，…，i■，0，…0，i■，…，i■

i代表着每一项运输任务，此染色体可理解为车辆从配送中心0出发，完成i■，i■，…，i■后返回配送中心0，形成子路径1；然后又从0出发，完成i■，…，i■后返回0，形成路径2，如此反复直至完成所有的任务。这个过程中，行走路径不断改变，使得函数目标也改变，这样的遗传迭代就能让函数目标最小，也即趋向于最佳路径。

（2）确定目标函数

根据所研究的具体问题，数学模型的目标函数可以表示相应问题（如运费最少问题、车辆数最少问题、路径最短问题、运输时间最少问题等）的最优解方程。

（3）约束的处理

遗传算法中各个染色体对应的解在群体中是占有一定比重的，在遗传算法迭代运算进程中，如果某个染色体的解不符合约束条件，则会受到遗传算法的惩罚机制的惩罚，使得其在群体中所占比重越来越小，而相反，可行解则越来越大，通过这样的一个机制最终可以得出最优解。

（4）遗传算子

遗传算子一般包括复制、交叉、变异。复制的目的是保留优良个体，提高全局收敛性和效率；交叉的作用是组合新个体，降低对有效模式的破坏概论；变异的目的，是为了减少基因的缺失和不成熟收敛对结果的影响。

（5）确定最终方案

经过上述遗传过程后，最终产生性能最优的染色体串。

2 仿真优化方法在VRP上的运用

对VRP的研究，大多停留在理论层面上，这些研究是通过分析问题，运用运筹学知识，用各种数学符号将问题抽象为一系列公式，形成能解决VRP的数学算法。这一类方法称为解析法，是通过建立某种符合逻辑推理的数学模型来解决VRP，具有精确求解的优点，但不足的是，它完全以数学公式的形式存在，所以它不易于理解，不具备良好的人机交互及可视化，也就无法让人直观地感受到所描绘系统是如何运行变化的。相反，仿真方法却可以直观方便地处理问题。

仿真方法是利用以计算机和软件为工具的仿真技术对实际或者设想的系统进行建模并运行，结合某种算法对系统分析，从而得出结果。它结合优化算法来计算模型，则可以求解出最优解。

李先永[6]根据VRP模型，利用EM-Plant仿真软件构建了相应的仿真模型，同时结合启发式求解方法计算和优化，从而验证了该仿真方法的可靠性。刘芳华、杨娟都采用了仿真平台MATLAB结合遗传算法对具体的VRP进行参数输入并运算，得到很好的效果。白雪利用ProModel对某汽车租凭公司的运营方案进行建模优化并评比备选方案，得出最优排程方案。孙姝婷利用 VISSIM 微观仿真软件对城市配送线路进行优化搜索，对多条配送路线进行评价分析，为配送车辆选出最优配送线路。陈静静[7]针对定位—路径—库存问题（Location—Routing—Inventory Problem，LRIP）这一物流领域中新的研究热点问题，采用ExtendSim仿真软件构造了该问题的模型，并用软件的遗传算法对其优化计算，求解出LRIP的最优方案。

3 ExtendSim对VRP建模优化

3.1 运输问题

运输问题，解决的是如何组织一个合理的运输方案，使得物资在供求地运送到需求地所需要的总运费最小。其数学模型如下[8]：

设有m个产地，记为A■，A■，…，A■，生产某种物品，可供应产量分别为a■，a■，…，a■；有n个需求地，记为B■，B■，…，B■，其需求量分别为b■，b■，…，b■；供需平衡，即■a■=■b■。从第i个产地到j个需求地的单位物品的运费为c■，在满足各地需要的前提下，求使得运费最小的调运方案。

设x■i=1，2，…，n为第i个产地到第j个需求地的运量，则该运输问题的数学模型可写为：

minz=■■c■x■ （7）

■x■=a■ i=1，2，…，m （8）

■x■=b■ j=1，2，…，n （9）

x■≥0 i=1，2，…，m j=1，2，…，n （10）

3.2 对具体问题建模

设有A■，A■两个工厂面向B■，B■，B■三个客户服务，工厂可供应产品数量分别为10，8个单位，客户需求量分别为5，6，7个单位，A■到B■，B■，B■的每单位产品运费分别为3，2，6个单位，A■到B■，B■，B■的每单位产品运费分别为5，3，8个单位。根据以上信息，如何安排一个运输计划，使总运费最少。

对此问题，本文采用ExtendSim仿真软件，实现了模型的整体构建。其整体结构如图1所示。

3.3 模块说明

ExtendSim中的每一个模块都有其特定的功能，这种功能可以是多个的，另外模块内部还有能输入和输出参数的结构。

首先，上述运输问题是一个离散事件，需要放置Executive仿真时钟模块，让软件自动推进事件的发展。两个Create模块表示两个工厂生产产品，Queue模块表示存放产品的仓库，Select item out模块表示选择不同的送货路径，Gate是个路径开关，与Information、Math、Decition共同作用，具有能根据客户是否得到满足而控制路径开通与否的功能。Get模块可设置此路径上每单位产品运费，而Activity模块则是计算运送给某个B客户的总成本，整个产品送货流程以Exit模块结束。

3.4 优化

以上模型只能直观地演示系统的运行，还不能对该系统进行计算最优方案，所以要求解最佳方案，必须使用优化模块Optimizer。

该模块内置遗传算法，在本问题中，有六个决策变量，该模块对这六个量分别随机编码成二进制的基因b■i=1，2，…，n，并使它们连接组成每一个都拥有六个基因的染色体个体，然后模块自行随机产生初始种群数，再根据目标函数来确定能评价染色体优劣的适应度函数，在本题中以值越小越优，并接着按照一定概率选择较优个体淘汰较劣个体进而产生一个种群，然后按一定概率对这种群里的个体进行交叉、变异运算，最终产生新一代的种群，这一代个体的适应度的数值和平均值都比上一代的有了明显的改进，也就是说向最优值靠拢，接着再继续对这新一代种群不断循环运算，经过运算多代直至不能搜寻到更优的解后，就停止运行并显示最优解了。

在Optimizer的Objectives中，对分别输入运量的最小值0和最大值（客户B的需求量），以及表示总费用最少的目标函数：Mincost=yunfei1+yunfei2+yunfei3。

在Optimizer的Constraints中，输入决策变量的约束条件：

if（yunliang1+yunliang4 ！=5） reject=true；

if（yunliang2+yunliang5 ！=6） reject=true；

if（yunliang3+yunliang6 ！=7） reject=true；

if（yunliang1+yunliang2+yunliang3 ！=10） reject=true；

if（yunliang4+yunliang5+yunliang6 ！=8） reject=true；

最后，点击New Run，系统自动运行，最终求解出最优结果，结果显示，软件运行了24秒，最小总成本值为82，最优解方案为best行：A■向B■，B■，B■分别运送1、3、6单位的产品；A■向B■，B■，B■分别运送4、3、1单位的产品。

4 结 论

本文论述了当前物流领域热点问题车辆路径问题及前人对其研究出来的解决方法，这些方法当中以某种算法来建立数学模型的理论研究居多，仿真建模层面上的研究比较少，因此重点探讨了仿真优化方法在VRP上的应用，并基于ExtendSim仿真优化软件对某一VRP问题进行了建模和优化，得出可靠结果，突显出了仿真软件界面友好、可视化强、操作简单易懂、运算速度快的特点，是解决物流领域中VRP的一种有效的途径。

参考文献：

[1] 邓红星，韩锐，武慧荣. 物流技术[M]. 哈尔滨：东北林业大学出版社，2010.

[2] 纪红任，游战清，刘克胜，等. 物流经济学[M]. 北京：机械工业出版社，2007.

[3] C.G.Dantzig， J.Ramser. The truck dispatching problem[J]. Management Science， 1959（6）：80-91.

[4] J Holland. Adaptation in Natural and Artificial System[D]. The University of Michigan Press， Ann Arbor， MI， 1975.

[5] 彭扬，伍蓓. 物流系统优化与仿真[M]. 北京：中国物资出版社，2007.

[6] 李永先. 车辆路径问题的仿真模型及优化方法研究[D]. 大连：大连理工大学（博士学位论文），2008.

篇5

Abstract： Critical chain method adhering of the TOC process, both in the planning of projects between the process logic operations and identify key chain of the resource constraints relationships, through the buffer to deal with uncertainty. However, most of the existing key chain theories are researched based on certain networks. Petri nets with similar description and flow charts and other visual identification of the flow though the simulation system of dynamic event. This article describes how to identify the critical chain of the projects based on the Petri nets, in order to respond to complex and changing reality better, it has important theoretical significance to perfect critical chain theory.

关键词： Petri网；关键链；变迁

Key words： Petri net；Critical Chain；transition

中图分类号：TP393文献标识码：A文章编号：1006-4311（2011）01-0186-02

0引言

关键链管理[1]正是把项目看作一个系统，来实施对项目的管理。关键链依托于约束理论，从瓶颈、系统思考方式入手，将DBR的核心思想应用到项目管理中，把着眼点从工序提升到整个系统，考虑整体系统的有效性，关键链理论对传统网络计划技术诸多方面予以较大改进，综合考虑资源约束以及人的行为，突破了传统计划的模式，提出的面向项目的进度计划方法[2]。在关键链的判断方面，J-B Yang[3]通过一个例子对关键链和关键路经进行了比较，并指出如果所有的项目参与者都能改变他们以往在关键路经上的行为因素，那么关键链的方法对于大多数的建筑项目都非常有用的。同时他也提出现有的一些关键链的确定方法存在着很多的不足。 田文迪运用动态规划的思想设计一个启发式算法来识别关键链和非关键链，并将此法与标准问题库中其他方法所得解进行比较，证明了方法的优越性，但由于方法的设计过程复杂，不具有通用性。 万伟、蔡晨等[2]也关键链管理进行了系统的论述，但也不够完善。近年来，Petri网理论的发展十分迅猛， Petri网既是图形工具又是数学工具，具有图形直观、能描述冲突和并发，且能以状态分布表示等优点，Petri网因其强大的并发处理功能日显优越，因此将关键链的先进思想与Petri网的有机结合将有力的推动关键链理论的完善[4]。

1Petri网

Petri网(PN)是1962年德国的C.A.Petri博士在研究自动机通信时，提出了一套形式化的建模方法，以他的名字命名，在当时引起了学术界的广泛关注。其是一种系统建模与分析工具，以并发论、网逻辑和网拓扑为主要内容，它同时具有充分的模拟能力和丰富的分析方法[4]。经过几十年的发展，Petri网理论已经被广泛应用于许多领域， 本文采用Petri网对项目管理建模与分析优化调度方案。

1.1 Petri网的定义在生产调度中Petri网模型是一个五元组∑=（P，T，F，W，M），P={P1，P2，…，Pm}为库所集；T={t1，t2，…，tm}称为变迁集；F表示连接库所和变迁的有向弧集合；W为关联库所和变迁的实数对[a（S）i，β（S）i]（a（S）i1时，将W（f）标注在流关系上。当一个库所的容量有限时，通常将K（p）标注在库所旁边。K（p）=∞时，通常省略K（p）的标注，标识是托肯在库所中的一种分布[4]。

1.2 Petri网与项目管理项目管理从本质上来说就是一个离散事件动态系统，其特点在于事件发生在离散的时间点上，具有并发、异步和突发性。而Petri网恰好是为离散事件系统建模的最好工具之一。所以，用Petri网理论来研究项目管理，能起到比较好的效果。Petri网理论能够正确、合理地表示出项目管理的整个过程。这对于发现问题、解决问题会有极大的帮助,通过Petri网与传统的、成熟的项目管理模型之间的映射，我们可以直观地了解项目的情况，从而实时地调整项目计划和动态控制项目的执行。在随机事件驱动计划下，多项目管理网络计划的在时间τ的HLPN:（Ω，R，M0）满足以下需求：

（1）Ω是一组项目集合：

在τ时间，每个项目ω∈Ω是一个集合（P，T，δ，∑，D+，D-，μ0）

P是库所的集合；T变迁的集合：T=T1∪TD，T1是立即变迁，TD是一系列时间延迟变迁；δD（t）R是TD的时间延迟函数，R是正实数；∑是染色集合；∑（pi）是库所pi的联系，是∑（tj）变迁tj的联系；D是输入函数；D是输出函数；μ0是项目ω的初始标识；

（2）R={r，r，r，…，r}是一组资源集合；R=R∪R=R∪R

R代表的是被多项目共享的资源；R代表的是只分配给一个项目使用的资源；R代表的是可循环使用的资源；R代表消耗性资源；R∪R=

（3）M0是Ω的一个初始标识，μ0∈M0

在模型中库所中有一个托肯意味着，活动即将发生或资源可以使用。由于模型的整个网络计算工作比较复杂，我们用计算机对可达性及矩阵的运行进行分析。

2基于Petri网项目管理中关键链判断方法

Step.1构建多项目管理下的随机PETRI网模型根据定义及Petri网的规则建立项目管理的Petri网模型用高级PN的展开模型来定义资源约束的活动，资源类型，及冲突的原因。Step.2寻找锁死点锁死是当并行的活动竞争相同的资源，通常是资源配置不合理造成，基于PN的锁死算法可以找到潜在的锁死，从而重新设计或修正资源安排，来防止与回避锁死。相反，无锁死，说明条件可行，资源满足项目活动。

锁死寻找:

输入：AHLPN代表在τ时多项目管理的网络计划

输出：无锁死方案

01 Definition；

μ0=初始标识，μm=结束标识，μk=活动标识

D=输入函数D=输出函数

D=D-D，关联矩阵，α=实施向量

02 Findμ0 and μm

03 perform: calculate D，D and D

04 Set k=0

05 Let μk+1=μk+α•D， solve for α

06 If a is a feasible solution

07 If k=m

08 Indicate deadlock-free state

09 Else

10 Set k=k+1

11 Go to 05

12 End if

13 Eels

14Indicate deadlock

15 End if

16 End

Step.3产生可行性计划安排及输出关键链

根据step.2的无锁死路径及，可以运用计划概括计算产生可行性计划安排并估计其工期，所有作业根据资源约束，资源的有效利用，一种资源每次只能用作一项任务。通过PN模型得到多个可行性计划（根据不同的PN的不同变迁顺序），通常会工期最短的作为最优的，即得到相应的关键链。

程序：总体计划

输入：无锁死方案

输出：可行性计划及工期

01 Definition:

μ0=初始标识，μm=结束标识，μk=活动标识

MS=makespan，MSL=the lower bound of makespan

02 Find μ0 and μm

03 Initialize MSL of MS

04 Set k=1

05 Find the enabled transition(s) of μk

06 Perform: select one enabled transition to fire(put others in waiting lit)

07 Perform: record the firing transition

08 Perform: calculate MS from μ0 to μk

09 If MSL

10If Waiting-list of transition is empty

11 If k= m

12MSL=feasible solution

13 Else

14 Set k= k+1

15 Go to 06

16End if

17 Else

18 Go to 06

19 End if

20 Else

21 MSL=MS

22Go to 10

23 End if

24 End

3算例分析

本算例由两个项目同时开始，需要3种可恢复资源R1、R2、 R3资源的可使用量分别是3、2、2。项目活动及资源分配如表1。项目的Petri 网模型如图1，通过锁死判断及项目计划计算，项目计划的最短工期为22天，可得到项目的甘特图如图2。

可得出关键链为:1.1-1.2-2.2-2.7-2.8-2.10-1.8

4结论

本文是结合时间Petri网对多项目管理的关键链进行研究，其作为数学工具，在判断关键链有严密的数学基础，作为图形工具，能清晰的描述项目管理计划。本文是在确定型网络中对关键链分析，为其关键链在不确定型网络研究提供了研究方向。

参考文献：

[1]龚俏巧，韩文民.关键链技术在RCPSP问题中的应用研究[J].中国管理信息化，2009：（15）：105-107.

[2]蔡晨，万伟．基于PERT/CPM的关键链管理[J].中国管理科学，2003，12（11）：35-39．

篇6

第一节 物流发展的现状

物流最早是在二战中，围绕战争物资供应，美国军队建立的“后勤”（logistics）理论发展过来的。当时的“后勤”是指将战时物资生产、采购、运输、配给等活动作为一个整体进行统一布置，以求战略物资补给的费用更低、速度更快、服务更好。后来，将“后勤”体系移植到现代经济生活中，才逐步演变为今天的物流。

物流科学于80年代传入我国，由于经济体制的问题，物流研究直到改革开放进行了十几年的90年代末期才开展起来。总的说来，由于我国的市场经济刚刚起步，一方面存在限制物流发展的因素，另一方面又存在许多可以挖掘的物流潜力。同发达国家相比，我国物流研究的市场基础还存在很多的差距。

根据中国物流与采购联合会此前的数据显示，在2008年之前，我国物流业规模快速增长，全国社会物流总额达89.9万亿元，比2000年增长4.2倍，年均增长23%；物流业实现增加值2.0万亿元，比2000年增长1.9倍，年均增长14%。2008年，物流业增加值占全部服务业增加值的比重为16.5%，占GDP的比重为6.6%。而到了2009年，受国际金融危机的影响，我国社会物流总额同比增速由一季度下降3.3%，上半年下降0.8%，转为前三季度增长 2%，反映出物流需求在逐步扩大；前三季度物流业增加值同比增长4%，增幅比上半年提高1.9个百分点，呈加快增长态势。从企业来看，2009年业务收入基本上经历了一季度止跌，二季度企稳，三季度回升，全年比前一年略有增长的积极变化。整个行业运行呈现加快回升的积极变化。在2009年，国务院及时出台了《物流业调整和振兴规划》，实现传统物流业向现代物流业的转变，不仅是物流业自身结构调整和产业升级的需要，也是整个国民经济发展的必然要求。

物流行业的发达程度与发展水平，直接关系到制造业的效率和利润。中国是世界有名的“工厂”，以前物流外包的比例还比较低，制造企业自营物流仍是主流，第三方物流占物流服务份额很低，据调查仅为17%左右，且第三方物流发展不成熟，目前其需求仍呈增长趋势。我国近几年的物流发展比较迅速，有很多的物流企业，但是现代化的物流企业还不多，基础建设落后、信息化程度低、服务范围小、内容单薄、总体服务质量和水平不好，无法跟上制造业的发展脚步，提供有利的支持。制造企业不放心物流企业的供应服务能力，认识程度低，担心物流外包会丧失主动权，而过于依赖物流企业，导致控制权减弱。双方之间的沟通并不流畅，物流企业也不了解制造企业的真实需求，导致供应能力不足和有效需求不足并存的矛盾。但随着近几年，物流行业的迅速发展，制造行业的物流外包速度加快，产业融合与联动趋势更加明显，比如2006年销售物流外包以5％～10％的速度增长，运输与仓储外包以10％～15％的速度增长，运输业务委托第三方已占企业运输业务的67．1％。

第二节 选题的意义与背景

在物流管理出现之前，制造业企业还没有一个独立的配送管理部门，只是被作为制造活动的一部分，没有职业物流人员和关于这方面的学术研究。直到20世纪60年代物流管理和物资配送出现后，情况才有了变化。20世纪80年代有了一个新的理论----集成物流，把企业的输入、输出物流管理以及一部分制造功能集成在一起。在90年代，供应链管理这种新的模式出现了，随即就有了集成供应链的概念，企业把焦点从里面转到外面，通过和其他供应链的成员进行物流的合作协调寻找商业机会。而制造业配送包括制造企业的物料和成品在供应商、制造商和客户之间，以及企业内部各生产车间甚至生产工位之间的有序平稳流动，以及它们之间的信息流动。配送管理对于有效提高制造业的柔性和对市场的响应速度具有决定性的作用，因此非常有必要开展对制造业配送管理的研究。

     

第二章 配送管理  

第一节 配送的概念和作用

一、配送的概念

日本1991年版《物流手册》的表述：生产厂到配送中心之间的物品空间移动叫“运输”，从配送中心到顾客之间的物品空间移动叫“配送”。 美国《物流管理供应链过程的一体化》表述：实物配送这一领域涉及特制成品交给顾客的运输。实物配送过程，可以使顾客服务的时间和空间的需求成为营销的一个整体组成部分。我国出版的《现代物流学》的表述：配送是以现代送货形式实现资源最终配置的经济活动；按用户订货要求，在配送中心或其他物流结点进行货物配备并以最合理方式送交用户。而对于制造业来说，配送是围绕制造业企业所进行的原材料、零部件的供应配送，各生产工序上的生产配送以及企业为销售产品而进行的对客户的销售配送。

制造业配送结构模型如图2-1所示。

 

                                        图1-1 制造业配送结构模型

二、制造业配送的作用

（一）通过集中库存使企业实现低库存或零库存

制造业企业为了实现高水平的配送，而依靠配送中心的准时配送，一方面可以降低库存量甚至是“零”库存，从而解放大量的的 储备资金，另一方面采用配送中心集中库存可以利用规模经济的优势使单位存货成本下降。

（二）简化事务，方便客户

客户只需要向一个配送中心订货，就能订到所有想要的货物，降低交易成本，提高效率。而对于生产单位来说，只需要把货物集中配送到一个地方，减少接货成本，可以全身心投入到自己擅长的业务中。

（三）提高供应保证程度

         制造企业自己保持库存，维持生产，供应保证程度很难提高，受到库存费用的控制。采取配送，配送中心可以比任何单位企业的储备量更大。而对于每个企业而言，中断供应、影响生产的风险相应缩小，使客户免去缺货之忧。

（四）降低缺损，防止内盗

假如各个生产车间自己保持库存，由于没有专业的仓库保管人员，同时设施也不可能十分完善，容易造成货物的缺损。同时由于库存分散，造成管理混乱，容易发生内盗事件，造成大量损失。配送中心经验丰富的专业仓库保管员和完善的仓库保管设施，可以最大程度地保证货物得到妥善保管，降低缺损率。

 

第二节 配送作业流程

一、进货

在配送的基本作业流程中，进货作业包括把货品等物质从实体上领取，从货车上将货物卸下、开箱、检查其数量。当客户下订单以后，工厂因为成品的可存率不足，并会向供应商订购原材料、零配件等。这个时候，要按照保证货物先进先出，缓不围急，根据货物的尺寸、数量 、特性、保管要求选择货位，出入库频率高使用方便作业的货位，小票集中、大不围小，方便操作，作业分布均匀等原则安排货位。

二、订单处理

从接受客户订单开始着手准备拣货之间的作业阶段，称为订单处理。通常包括订单资料确认、存货查询、单据处理等内容。其中有以下几个内容确认：货物数量及日期的确认、客户信用的确认、订单形态的确认、订单价格的确认、加工包装的确认、设定订单号码、建立客户档案、存货查询和存货分配、计算拣取的标准时间、按订单排定出货时序及拣货顺序、订单资料处理输出等。

三、拣货作业

拣货作业是配送作业的中心环节。所谓拣货，是依据顾客的订货要求或配送中心的作业计划，近尽可能迅速、准确地将商品从其储位或其他区域拣取出来的作业过程。拣货作业在配送作业环节中不仅工作量大，工艺复杂，而且要求作业时间短。拣货方式包括按订单拣取、批量拣取、复合拣取。

四、补货作业

是将货物从仓库保管区域搬运到拣货区的工作。

五、配货作业

指把拣货分类完成的货品经过配货检查过程后，装入容器和做好标示，在运到配货准备区，待装车后发送。

六、送货作业

送货作业是利用配送车辆把用户订购的物品从制造厂、生产基地、批发商、经销商或配送中心，送到用户手中的过程。送货通常是一种短距离、小批量、高频率的运输形式。它以服务为目标，以尽可能满足客户需求为宗旨。本文着重探讨就是制造业送货过程中，车辆的安排、送货路线的选择、送货的顺序。

制造业的配送流程如图2-2所示。

                                                  图2-2 制造业的配送流程

第三节  配送模式的选择

配送模式是企业对配送所采取的基本战略和方法，根据国内外的发展经验及我国配送理论与实践，目前，主要形成了以下几种配送模式：

一、自营配送模式

自营配送模式是企业物流配送的各个环节由企业自身筹建并组织管理，实现对企业内部及外部货物配送的模式。这种模式有利于企业供应、生产、和销售的一体化作业，系统化程度相对较高，既可满足企业内部原材料、半成品、及成品的配送需要，又可满足企业对外进行市场拓展的需要。其不足之处表现在，企业为建立配送体系的投资规模将会大大增加，在企业配送规模较小时，配送的成本和费用也相对较高。

二、共同配送模式

共同配送是物流配送企业之间为了提高配送效率以及实现配送合理化所建立的一种功能互补的配送联合体。共同配送的优势在于有利于实现配送资源的有效配置，弥补配送企业功能的不足，促使企业配送能力的提高和配送规模的扩大，更好地满足客户需求，提高配送效率，降低配送成本。

共同配送的核心在于充实和强化配送的功能。提高配送效率，实现配送的合理化合系统化。因此，作为开展共同配送的联合体成员，首先要有共同的目标、理念和利益，这样才能使联合体有凝聚力和竞争力，才能有利于共同目标和利益的实现。开展共同配送、组建联合体要坚持以下几个原则：

1、功能补充

2、平等自愿

3、互惠互利

4、协调一致。

共同配送的实施步骤为：

1、选择联合对象

2、组建谈判小组，做好谈判准备

3、签订合同意向书及合同，并进行公证

4、组建领导班子，拟定管理模式

5、正式运作

共同配送的类型，大体可归纳为：紧密型、半紧密型和松散型；资源性和管理型；功能型；集货型、送货型和集送型等。

三、互用配送模式

互用配送模式是几个企业为了各自利益，以契约的方式达成某种协议，互用对方配送系统而进行的配送模式。其优点在于企业不需要投入较大的资金和人力，就可以扩大自身的配送规模和范围，但需要企业有较高的管理水平以及相关企业的组织协调能力。

与共同配送相比，它的特点主要有：

1、共同配送模式旨在建立配送联合体，以强化配送功能为核心，为社会服务；而互用配送模式旨在提高自己的配送功能，以企业自身服务为核心。

2、共同配送模式旨在强调联合体的共同作用，而互用配送模式旨在强调企业自身的作用。

3、共同配送模式的稳定性较强，而互用配送模式的稳定性较差。

4、共同配送模式的合作对象需要经营配送业务的企业，而互用配送模式的合作对象即可以是经营配送业务的企业，也可以是非经营配送业务的企业。

四、第三方配送模式

第三方就是为交易双方提供部分或全部配送服务的一方。第三方配送模式就是指交易双方把自己需要完成的配送业务委托为第三方来完成的一种配送运作模式。随着物流产业的不断发展，以及第三方配送体系的不断完善，第三方配送模式应成为工商企业和电子商务网站进行货物配送的首要模式和方向。

随着物流管理的理念在中国企业内逐步被认知，第三方物流作为有着较新物流理念的产业正在逐步形成。中国原有的运输企业、仓储企业、电子商务企业经过改造和合并，形成了新兴的第三方物流企业。第三方物流企业在对企业的服务中逐渐形成了一种战略关系，随着JIT管理方式在中国的普及，不论制造业还是商业企业，普遍应用JIT管理的理念，采用拉动方式，减少库存，降低库存储备，适应市场变化。JIT管理方式的应用，使服务于制造企业和商业企业的第三方物流企业，采取小批量、多频次的JIT运输。第三方运输与传统运输的比较如表2-1。

表2-1 传统运输与第三方运输的比较

传统运输的特点 组合配送的特点

供应商对运输独立管理 第三方物流企业管理

分散操作，缺乏合作及可见性 整合操作完全的可见性和管理

分散复杂的流动 简单集中的流动

低货物空间利用率 优化车辆利用率

库存水平不均 有效的库存控制

无IT解决方案平台 有一体化的IT平台支持

第三方运输是一种适应市场发展的新型的运输配送模式，但其发展和推广又有相当的条件和前提。

1、 市场需求程度。消费者的需求变化是导致市场需求变化的主要因素，对消费品本身可变性和带动性需要进行分析。

2、 供应链体系的建立。供应链体系的建立是组合配送模型实施的前提，作为第三方物流企业，掌握了相当的主导企业和配套企业的机密信息，没有战略性的合作伙伴关系，第三方物流企业无法深入到供应链管理体系当中。作为第三方物流企业，在没有建立战略关系时，为供应链服务无形中会增加相当的交易成本和沟通成本，导致整个供应链成本上升和供应链体系的不稳定，无法发挥整合物流的优势。

3、 信息技术和物流标准的推广。依托Internet和企业内部局域网有效实施信 息共享是建立组合配送的基础。供应链企业通过电子数据交换系统（EDI）、电子邮件系统等通过Internet在企业之间进行快速的信心交换，完成订单下达和处理工作，减少了前置时间。第三方物流企业建立自己的物流管理系统与供应链主导企业和配套企业的信息系统进行有效连接，完成提货通知、发运状态、线路设定、发运结算等信息的交换，对配送指令进行快速反应。通过集装化运输、GPS跟踪控制、条形码技术等的应用，有效控制运输，降低货物的操作时间，适应快速的供应体系。

总之，第三方配送作为一种配送模式，符合企业发展和供应链发展的要求，对今后物流体系发展有着一定的引导作用。而本论文所要研讨的配送方式正是符合第三方配送模式。

第四节 货物运输与配送管理

一、货物运输的影响因素与原则

货物运输是物流的核心业务，也是配送管理中不可缺少的一环。充分利用现有运输管道，提高运输、改进经营组织、管理体制等对改善配送管理有着重要的作用。

货物运输子系统的基本目标是安全、迅速、准确的成本。配送运行过程必须利用运输网络，即利用有运输路线和结点组成的资源体系。在一定综合运输格局的情况下，不同运输方式的服务质量、技术性能、方便程度、管理水平是影响不同层次物流系统选择运输方式的重要因素。在构思货物运输系统时，应根据系统实际担负的货运量的大小、作业内容与范围、以及与其他各个子系统的协调关系，进行规划、构筑工作，一般必须考虑一下几个方面的因素：

1、 货物的特点、性质、数量以及运输方式的选择。

2、 运输路线的确定。

3、 设备设施、工具的配备和利用情况。

4、 运输质量的保障。

5、 运输战场的利用。

6、 运输费用的节约。

7、 运输计划的制定、货物运输与集散过程的控制。

8、 运输网络的形成与运行机制。

9、 不同的运输方式之间的协作。

10、运输与物流其他作业环节活动的综合集成与管理等。

就组织运输工作，应贯彻执行“及时、准确、经济、安全”的原则，即

1、 及时。就是按着产、供、运、销情况，及时把货物从产地运到销地，尽量缩短货物在途时间，及时供应工农业生产和人民生活的需要。

2、 准确。就是在货物运输过程中，切实防止各种差错事故，做到不错不乱，准确无误的完成运输任务。

3、 经济。就是采取经济、最合理地运输方案，能有效地利用各种运输工具和运输设施，节约人力、物力和运力，提高运输经济效益，降低货物运输费用。

4、 安全。就是货物在运输过程中，不发生霉烂、残损、丢失、燃烧、爆炸等事故，保证货物安全地达到目的地。

在配上过程中，要组织合理的运输，所谓合理运输就是按照商品流通规律、交通运输条件、物品合理流向、市场供需情况、走最少的里程、经最少的环节、用最少的运力、花最少的费用、以最快的时间、把货物从生产地运输到消费地。也就是用最少的劳动消耗，运输更多的货物，取得最佳的经济效益。因此，在运输生产活动中，需要一定的劳动消耗，衡量运输的合理与否，是从技术经济角度，看消耗在运输上的社会劳动量，来评价运输的经济效益。

二、运输的五要素

组织合理运输工作，涉及面广，比较复杂，影响它的因素很多。要实现运输合理化，起决定作用的有以下五个主要因素，物流业称为合理运输“五要素”。

（一）运输距离

运输既然是商品在空间的移动，那么这个移动的距离，即运输里程的远近，是决定其合理与否因素中一个最基本的因素。因此，物流部门在组织货物运输时，首先要考虑到运输距离，应尽可能实习近产近销，就近运输，近可能避免舍近求远。

（二）运输环节

    在物流过程环节中，运输是一个主要的环节，也是决定合理运输的一个重要因素。因为，围绕着运输业务活动，还有进行装卸、搬运、包装等工作，多一道环节，须多花费、多劳动。所以，物流部门在调运物资时，对有条件直达、直拨运输。使物资不进入中转仓库，越过一切不必要的中间环节，有产地直运到销地，越过一切不必要的中间环节，减少二次运输。

（三）运输工具

在交通运输日益发展，各种运输工具并存的情况下，必须选择运输工具和运输路线，合理运用。根据不同货物的特点，分别利用铁路、水运和汽车运输，选择最佳的运输路线。

（四）运输时间

对物流业来说，为了更好的为顾客服务，及时满足顾客的需要，时间是一个决定性的因素。尤其在市场变化很大的情况下，时间问题更为突出。所以在物流过程中，必须特别强调运输时间，要抢时间、争速度，想方设法加快货物运输，尽量压缩待运期，使大批货物不要长期徘徊、停留在运输过程中。

（五）运输费用

运输费用占物流费用比重大，它是衡量运输经济效益的一项重要指标，也是组织合理输的主要目的之一。运输费用的高低，不仅关系到物流企业或运输部门的经济核算，而且也影响商品销售成本。为此，在组织合理运输工作中，积极节约运输费用，是物流企业的一项重要任务。

上述五个因素，既是互相联系，又是互相影响的，有的甚至是互相矛盾的。这就要求进行综合比较分析，要求最佳运输方案。在一般情况下，运输时间快、运输费用省、是考虑合理运输的两个主要因素，它集中体现了物流过程中的运输经济效益。

第五节 配送的信息技术

一、条码技术

条码技术是在计算机的应用实践中产生和发展起来的一种自动识别技术。为我们提供了一种对物流中的货物进行标识和描述的方法。条码是实现POS系统、EDI、电子商务、供应链管理的技术基础，是物流管理现代化、提高企业管理水平和竞争能力的重要技术手段。

二、EDI技术

EDI (Electronic Data Interchange)是指通过电子方式，采用标准化 的格式，利用计算机网络进行结构化数据的传输和交换。构成EDI系统的三个要素是EDI软硬件、通信网络以及数据标准化。

工作方式大体如下：用户在计算机上进行原始数据的编辑处理，通过EDI转换软件(Mapper)将原始数据格式转换为平面文件(Flat File)，平面文件是用户原始资料格式与EDI标准格式之间的对照性文件。通过翻译软件{Translator)将平面文件变成EDI标准格式文件。然后在文件外层加上通信信封(Envelope)，通过通信软件(EDI系统交换中心邮箱(Mailbox))发送到增值服务网络(VAN)或直接传送给对方用户，对方用户则进行相反的处理过程，最后成为用户应用系统能够接收的文件格 式。

三、射频技术

射频识别技术（RFID）是一种非接触式的自动识别技术，它通过射频信号自动识别目标对象来获取相关数据。识别工作无须人工干预，可工作于各种恶劣环境。短距离射频产品不怕油渍、灰尘污染等恶劣的环境，可以替代条码，例如用在工厂的流水线上跟踪物体。长距射频产品多用于交通上，识别距离可达几十米，如自动收费或识别车辆身份等。

四、GIS技术

GIS（Geographical Information System，地理信息系统）是多种学科交叉的产物，它以地理空间数据为基础，采用地理模型分析方法，适时地提供多种空间的和动态的地理信息，是一种为地理研究和地理决策服务的计算机技术系统。其基本功能是将表格型数据（无论它来自数据库、电子表格文件或直接在程序中输入）转换为地理图形显示，然后对显示结果浏览、操作和分析。其显示范围可以从洲际地图到非常详细的街区地图，显示对象包括人口、销售情况、运输线路和其它内容。

五、GPS技术

全球定位系统（Global Positioning System－GPS）具有在海、陆、空进行全方位实时三维导航与定位能力。GPS在物流领域可以应用于汽车自定位、跟踪调度，用于铁路运输管理，用于军事物流。

第三章  配送路线优化的理论模型

  第一节   启发式算法理论

一、启发式算法的概念

启发式源自英文单词heuristics,启发式方法意为通过对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观推断或试探的方法。启发式方法要求分析人员必须运用自己的感知和洞察力，从与研究问题相关而较基本的模型及算法中寻找其间的联系，从中得到启发，去发现适于解决该问题的思路和途径。

用启发式方法解决问题时强调“满意”，常常是得到满意解，决策者就认为可以了，而不去追求最优性和探求最优解。之所以这样，其原因是：1、很多问题不存在严格最优解，这时，对目标的满意性常比最优性更能准确地描述人们的选择行为。2、对有些问题，得到它的最优解所花的代价太大。3、从实际决策的需要出发，有时要求解具有过高的精度没有意义。

用启发式方法求解问题是通过迭代过程实现的，因而需拟定出一套解得探索规则。为能得到满意解，在整个迭代过程中要不断吸收新的信息，必要时改变原来拟定的不合适的策略，建立新的搜索规则，注意从失败中吸取教训，并逐步缩小搜索范围。启发式方法具体求解过程如图3-1所示。

 

                          图3-1 启发式方法的求解过程

二、启发式算法的求解策略

用启发式方法求解问题时，需采用一定的策略，下面列出几个常用的策略，可根据问题的性质和要求选用。

（一）逐步构造解策略

逐步构造解策略是指每次增加解的一个元素（如节点、弧等），直到得到一完整的可接受解。

（二）改进解策略

从一初始解（初始解不一定可行）开始，通过一系列替换分解和合并过程来逐渐修正解，以提高解的可接受性。

（三）数学规划策略

运用数学模型和优化算法，并通过对解的判别和修正以提高对问题的适用性，常会提出高效的启发式算法。

（四）分解策略

把一个复杂的问题分解成一系列易于处理的子问题来求解，一个子问题的输出常是下一个子问题的输入。

（五）分割策略

把一个复杂的问题分割成一些平行的小的子问题，然后求解每个子问题，最后在相容原则下进行综合，把子问题的解合并成原问题的一个解。

（六）可行解空间的限制策略

在某些情况下，把可行解集限制在一个可应用已存在高效算法的解集上，然后再求解问题。

（七）松弛策略

有时扩展问题的可行域以得到一个易于处理问题，然后求解松弛问题，就能直接得到或者很容易得到原问题的一个可行解，然后再对得到的解进行修正。

（八）搜索学习策略

包括在解的空间的定向搜索以及在搜索过程中发现和收集新的信息，并根据对新信息的分析，重新确认或改变搜索方向，修正搜索参数，消去不必要的搜索范围，以有效提高搜索效率，尽快获得问题的解。

第二节 遗传算法理论

一、遗传算法的由来

遗传算法是60年代由美国 J. Holland 教授和他的学生建立发展的，其思想源于生物遗传适者生存的自然规律，是一种新兴的自适应随即搜索方法，它对优化对象既不要求连续，也不要求可微，并具有极强的鲁棒性和内在的并行计算机制，特别适合于非凸空间中复杂的多极值优化和组合优化问题，在机器学习、自动控制、机器人技术、电气自动化以及计算机和通信等领域已取得了非凡的成就。近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探索。

遗传算法的工作机理是从达尔文进化论中得到灵感和启迪，借鉴自然选择和自然进化的原理，模拟生物在自然界的进化过程中所形成的一种优化求解方法。尽管这种自适应寻优技术可用来处理复杂的线性、非线性问题，但它的工作机理十分简单。

二、遗传算法的步骤

（一）构造满足约束条件的染色体。

由于遗传算法不能直接遗传算法是60年代由美国 J. Holland 教授和他的学生建立发展的，其思想源于生物遗传适者生存的自然规律，是一种新兴的自适应随即搜索方法，它对优化对象既不要求连续，也不要求可微，并具有极强的鲁棒性和内在的并行计算机制，特别适合于非凸空间中复杂的多极值优化和组合优化问题，在机器学习、自动控制、机器人技术、电气自动化以及计算机和通信等领域已取得了非凡的成就。近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探索。

遗传算法的工作机理是从达尔文进化论中得到灵感和启迪，借鉴自然选择和自然进化的原理，模拟生物在自然界的进化过程中所形成的一种优化求解方法。尽管这种自适应寻优技术可用来处理复杂的线性、非线性问题，但它的工作机理十分简单。

处理解空间中的解，所以必须通过编码将解表示成适当的染色体。实际问题的染色体有多种编码方式，染色体编码方式的选取应尽可能地符合问题约束，否则将影响计算效率。

（二）随即产生初始群体。

初始群体是搜索开始时的一组染色体，其数量应适当选择。

（三）计算每个染色体的适应度。

适应度是反映染色体优秀与否的唯一标识，遗传算法就是要寻得适应度最大的染色体。

（四）使用复制、交叉和变异算子产生子群体。

这三个算子是遗传算法的基本算子，其中复制体现了竞争与淘汰的自然规律，交叉体现了有性繁殖的思想，变异体现 了进化过程中的基因突变。

（五）重复步骤3、4直到满足制止条件为止。

三、遗传算法的优势

（一）遗传算法对问题参数的代码集起作用，而不是对参数本身起作用。遗传算法处理的对象是染色体，因而要求把所要优化问题的基本参数转化成定长的有限符号的染色体。

（二）遗传算法是从初始群体开始搜索的，而不是从单点开始搜索的，许多传统优化方法都是从搜索空间的单点出发，通过某些转换规则确定下一点。这种点到点的搜索方法在多峰值优化问题中，首先找到的可能不是最优峰值；而遗传算法是以点集开始的寻优过程，初始群体是随机地在搜集空间中选取的，这样在搜索过程中达到最优峰值的概率远大于点到点方法的概率。

（三）遗传算法在搜索过程中只使用适应度函数信息，而不用倒数及其他辅助信息。对于不同类型的优化问题，传统方法需要不同形式的辅助信息，没有一种优化方法能适应各类问题的要求。遗传算法在优化过程中，放弃使用这些辅助信息，具有广泛适应性。

（四）遗传算法使用频率转换规则而不用确定性规则。遗传算法使用概率转换规则来调整期搜索方向，各代群体间没有统一的联系规律。但使用概率转换规则并不意味着这种方法属于随机算法范畴，它只是使用随机转换作为工具来调整搜索过程中趋向于目标函数不断改进的区域。

于传统方法相比，遗传算法的优越性主要表现在：首先，在遗传算子的作用下，遗传算法具有很强的搜索能力，能以很大概率找到问题的全局最优解；其次，由于它固有的并行性，能有效地处理大规模的优化问题。

第三节  配送路线的优化模型

一、模型简介

TSP一般描述为：旅行商从驻地出发，经所要去的城市至少一次后返回原地，应如何安排其旅行线路，才能使总的旅行距离（时间、费用）最少。对于现实问题，由于限制条件的增加，TSP可衍生出许许多多相关的问题。

一般TSP指一个旅行商访问所有的城市。这里设城市O为旅行商出发城市，需要访问的L各城市编号为1，••••，L，为了便于说明问题，把旅行商问题构造成网络图，以G=｛V,A,C｝表示，其中

V=｛0,1，L｝------点集，表示旅行商需要经过的地点。

A=｛（i,j）|i,j=1,1,••••，L, i≠j｝-----弧集，表示旅行商可能走过的线路段集合。

C=｛ |（i，j）≤A｝-----费用矩阵， 表示旅行商经过对应弧段（i，j）所花费，如时间、距离、花费等。

求解TSP即要求在加权图G找到总费用做小的哈密尔顿回路，这里点O称为源点。定义变量如下：

 =1 若弧（i,j）在线路上  或者   =0  若弧（i,j）不在线路上

则得到一下模型

 

 =1,j=0,1,••••l

 =1,i=0,1,••••l

X=( ) ≤S

 =0或1

二、求解方法

（一）节约法算法

节约算法又称C—W算法，是有Clarke和Wright于1964年首次提出的。

它的基本思想是首先把各点单独与源点O相连，构成1条仅含一个点的线路。总费用那个为

                    

然后计算将点i和j连接在一起线路上费用的“节约值”：

         

         

    

S(i,j)越大，说明把i和j连接在一起时总路程减少越多。构建线路时，根据S(i,j)从大到小的顺序进行，实现时可在表上操作，具体步骤如下:

Step1：计算节约纸S(i,j)，并排列成表格形式。

Step2：在表格中选择最大元素S(i,j):

Step3：考察对应的点i和点j，检查是否满足下列条件：

1、若点i和j均不在已构成的线路上，则可连接点i和j，得到线路段o→i→j→o，转步骤step4；

2、若点i和j在已构成的线路上，连接后，但不是线路的内点（即不与源点O直接相连），则可以连接，连接后得到线路段o•••→i→j→o或o→i→j→•••o，转步骤step4；

3、若点i和j在已构成的同一条线路上，则不能再进行连接，转步骤step4。

Step4：划去第i行和第j列，则i点不能再到其他点，而j点也不能有其他点达到；

Step5：若所有元素均被划去，则已得到完整线路，算法终止；否则，在未被划去的元素中选择最大元素，转步骤step3。

（二）最邻近法

Step1：取源点O开始作为线路的起点；

Step2：寻找与上一次加进线路中的点距离最近的点，把此点加到线路中去；

Step3：重复step2，直到所有的点都已考虑，这就得到了一条线路。

（三）几何启发式算法

step1：构建点集的凸组合，此组合给出一初始线路。

Step2：选择不属于初始线路上的点k*及线路上的弧（ ， ），使由弧（ ， ）与弧（ ， ）构成的角度最大。

Step3：把点k*插入到点 与 之间。

Step4：重复step2---step3，直到得到—哈密尔顿回路。

（四）最小生成树算法

Step1：求图G的一颗最小生成树T；

Step2：在T的所有奇数度顶点上，求最小费用匹配，从匹配解中增加分枝给已在T中的分枝，得到—欧拉回路；

Step3：检查所有被不足访问过一次的顶点，将欧拉回路转化成哈密尔顿回路。

（五）最近插入算法

Step1：取源点O作为起点。

Step2：找到点L，使 最小，构成局部线路O—L—O；

Step3：对于已形成的局部线路，在不属于此线路的点中，寻找离线路上的点最近的点K。

Step4：在线路上寻找弧(i,j)，使满足 极小，把K插入点i与j之间。

Step5：返回step3，直到得到—哈米尔顿回路。

（六）最节约插入算法

Step1、step2与最近插入算法相同。

Step3：在局部线路中寻找（i,j）及不属于此线路上的点K，满足 极小，然后把K插入i与j之间；

Step4：重复，直到得到—哈密尔顿回路。

（七）凸集插入算法

Step1：构造点集的凸组合，此组合给出—初试线路。

Step2：对不在线路上的点K,确定在线路的哪两个点i与j间插入点k。即对每个点k，找到 极小的（i,j）；

Step3：对在step2中找到的所有（i，k，j），确定（ ），使 极小；

Step4：把点k*插入到线路上的点 与 之间；

Step5：重复step2—step4，直到得到—哈密尔顿回路。

第四章 贝因美公司的配送流程优化

第一节 贝因美公司的简介

贝因美始创于1992年，总部设在中国杭州，并在上海、北京、沈阳、武汉、成都、敦化、郑州设有分公司。全国设立25个分公司，有K/A、批销、婴童店、百货、网络五大渠道，50000多个零售网点。品牌价值超过50亿元人民币。2008年的全年销售总额 有50多亿元，2009年的全年销售总额达到了100亿元。

贝因美以“关爱生命，热爱生活”为宗旨，全方位服务于中国婴童事业，致力于婴幼儿食品及婴童产业的研究与国际性合作。主营事业以婴幼儿食品、婴幼儿用品、育婴咨询服务、生命科学和母婴保健、育婴工程、爱婴工程六大块架构而成。其中婴幼儿食品为主导项目，全面涵盖代乳品、断奶期食品和辅助食品三大类，是华东地区最大的断奶期食品生产基地和中国三大婴幼儿基本营养食品专业生产企业之一，产品覆盖全国。产品包括贝因美商标各阶段婴幼儿米粉，奶粉，豆粉，营养奶糕，营养荷花糕，婴幼儿磨牙饼，葡萄糖，蜂蜜，母婴护理用品，童车，童床，童装，玩具等。

贝因美奶粉的三大优势 优质奶源、先进工艺、科学配方是打造奶粉品质的三大关键因素，贝因美三者兼备，建立、实施和不断完善生产管理体系，应用全球领先的生产工艺与专业设备，为中国宝宝提供代表国际先进水平的产品。 优质奶源——北纬45度以上是国际公认的“黄金奶带”。贝因美在地处北纬45度以上、有“中国奶牛之乡”美誉的黑龙江省安达市设有贝因美奶源基地，并从同样地处北纬45度以上、有“欧洲农村”之称的爱尔兰进口优质原料乳。

优质奶源，是安全的品质基础；

全面科学管理，是安全的制度保障。

先进工艺——在生产工艺与设备方面，贝因美投资13亿元，联手全球乳业工艺巨头荷兰斯托克公司，配置专门为婴幼儿奶粉生产设计的谢弗尔斯三效牛奶浓缩器等国际一流专业生产设备，并在安达工厂建成了国内首条高端婴幼儿配方奶粉专用生产线；杭州工厂也分别从荷兰高达公司和日本引进了国际先进的滚筒干燥营养米粉生产设备 ，形成了具有年产婴幼儿营养米粉2万吨的生产能力，是华东地区最大的断奶期食品专业工厂之一，从硬件上保障了为中国宝宝提供专业的国际先进的产品。

科学配方——专为中国宝宝研制是贝因美的研发理念。不同国家的民族特性、地域环境和膳食结构导致了各国婴童食品配方的不同需求。

贝因美17年来，一直致力于研发符合中国婴童特质的产品，不断完善研发组织和制度、引进尖端研发人才和设备；与国内外研发机构展开深度合作，比如创建贝因美母乳研究中心，致力于精准还原中国母乳复杂的营养结构,研发实现从高级配方到仿生配方的目标，针对中国宝宝的身体特点能够提供更为专业的配方和养育方案，以确保科学性与安全性。 这些就是贝因美为什么能够一直没有出任何问题的原因，因为贝因美始终以质量位企业发展的原则，16年来一直严把质量关，始终做到对宝宝负责，让妈妈放心！

 本文要研究的是贝因美坐落在杭州余杭区的安溪工厂，是全国最大的GMP标准婴儿营养米粉工厂，安溪工厂年产6万吨配方乳粉，总投资近3亿引进全套进口全球领先工艺设备，目前在生产婴幼儿配方奶粉生产线中首屈一指，采用全自动化流程高架立体库，建设现代化物流中心，打造了国家级检测中心，已全面质量监控的软硬件建设为中国宝宝提供专业的国际先进产品。

            

图4-1 贝因美工厂的生产车间

          

图4-2 贝因美婴幼儿用品

 

图4-3 贝因美公司的组织结构

第二节 贝因美的配送流程分析

首先，贝因美的安溪工厂每天会生产出全国各个分公司所需要的产品，包括贝因美什锦营养米粉、营养磨牙饼、磨牙棒、健儿葡萄糖、儿童成长配方奶粉、乳清蛋白营养米粉、猪肝番茄营养米线、宝贝宝宝成长奶粉、营养小馒头、淮山营养米粉、深海旗鱼营养鱼酥等。因为贝因美安装ERP系统，每个分公司可以根据自己的需求情况给工厂下订单，工厂根据订单进行生产。接下来的流程是对生产出来的产品进行分类保管，同时要检查产品的品种和数量是否正确，检查包装是否有破损的情况，一切就绪之后，工作人员通过叉车把货物搬到仓库的指定位置。

当第二天要发货的时候，工作人员开始根据订单把商品分拣出来，放到发货场所指定的位置。配货作业采用的是机械化的设备，采用的是摘果方式，即搬运车往返保管场所，按照分公司的要求从某个货位上取下某种商品，巡回完毕后就完成了一个分公司的配货，接着在对下一个分公司配货。

发货是配送中心工作流程的最后一道环节，贝因美在浙江、上海、南京、苏州、武汉、贵阳、成都、北京、天津等全国各地都有自己的分公司，每天的发货量平均有300多吨，每天光运费就要10万左右，所以如何通过优化配送路线控制物流的成本是本文要研究的重点，因为贝因美的网点遍布全国各个城市，所以要进行全部的路线的优化有一定的困难，本文选择的研究范围是浙江省内的各个城市，有衢州、浦江、兰溪、桐乡、义乌、金华、湖州、诸暨、东阳、嘉善10个城市。这些城市一个星期内的需求情况相关数据如表4-1。杭州余杭到各个城市的距离的相关数据如表4-2。

表4-1 各个城市的一个星期之内的需求数据

省份 单位名称 食品件数 食品体积 促销品体积 总体积 总重量 发货地

浙江 东阳一诺（杭州分公司） 256 6.3 0.9  7.2  1.8  杭州分公司发

浙江 湖州黎明（杭州分公司） 1274 31.9 2.9  34.8  6.9  杭州分公司发

浙江 嘉善新昕（杭州分公司） 950 22.5 3.2  25.7  5.7  杭州分公司开

浙江 金华鑫金珠（杭州分公司） 805 19.3 1.7  21.0  4.8  杭州分公司发

浙江 兰溪永旺（杭州分公司） 416 9.9 2.4  12.3  2.9  杭州分公司开

浙江 浦江金贝（杭州分公司） 479 11.8 1.0  12.8  3.2  杭州分公司发

浙江 衢州龙游（杭州分公司） 1269 29.8 36.0  33.4  8.3  杭州分公司开

浙江 桐乡梧桐店（杭州分公司） 267 6.7 5.4  13.7  5.3  杭州分公司开

浙江 义乌钰尔（杭州分公司） 526 11.9 4.0  15.9  4.7  杭州分公司发

浙江 诸暨一百（杭州分公司） 590 14.4 5.4  19.8  4.3  杭州分公司发

                 

表4-2   各个城市之间的距离

杭州 杭州

东阳 172.0 东阳

湖州 93.6 243.0 湖州

嘉善 88.9 237.0 106.0 嘉善

金华 193.0 74.9 264.0 260.0 金华

兰溪 209.0 90.6 280.0 276.0 27.8 兰溪

浦江 146.0 46.2 217.0 213.0 76.4 57.0 浦江

衢州 270.0 159.0 310.0 345.0 101.0 92.1 161.0 衢州

桐乡 45.9 194.0 65.7 59.0 216.0 231.0 168.0 303.0 桐乡

义乌 149.0 20.7 220.0 217.0 56.8 71.8 32.5 135.0 172.0 义乌

诸暨 99.6 82.3 171.0 167.0 108.0 123.0 60.2 187.0 122.0 64.0 诸暨

                           

 

                                     图4-1 目前的配送模式

目前的配送模式来回所需的总路程有2934公里。

第三节 配送路线的分析与优化

这里所用的配送车辆都是12顿的柴油货车。

一、 方案一

不考虑车辆装载，只考虑路线设计，使配送路线最短。先从杭州出发找距离杭州最近的城市，再由该城市作为中心点，找出距离该城市最近的另一个城市，这样依次类推，回到杭州的话就是一个回路了。要是还有城市没连的话再按照这个方法依次连起来，直到各个城市都与杭州连起来成为一个回合了，这样才算完成本次的配送。

可以得出的最终的配送路线如图4-2所示：

 

                                       图4-2  改进后的配送路线

经过计算优化得到的路线有：

杭州－桐乡－诸暨－杭州   总距离为267.5公里  总需求量为9.6吨 需要1辆车子

杭州－嘉善－浦江－义乌－杭州   总距离为483.4公里  总需求量为13.6吨  需要2辆车子

杭州－湖州－金华－兰溪－衢州－杭州   总距离为747.5公里   总需求量为22.9吨  需要2辆车子

杭州－东阳   总距离为172公里  总需求量为1.8吨  需要1辆车子

二、方案二

考虑车辆最优装载的路线优化

配送中心与用户最短的距离的相关数据如表4-2。

表4-2  各个城市之间的距离

货运量 杭州

1.8 172.0 东阳

6.9 93.6 243.0 湖州

5.7 88.9 237.0 106.0 嘉善

4.8 193.0 74.9 264.0 260.0 金华

2.9 209.0 90.6 280.0 276.0 27.8 兰溪

3.2 146.0 46.2 217.0 213.0 76.4 57.0 浦江

8.3 270.0 159.0 310.0 345.0 101.0 92.1 161.0 衢州

5.3 45.9 194.0 65.7 59.0 216.0 231.0 168.0 303.0 桐乡

4.7 149.0 20.7 220.0 217.0 56.8 71.8 32.5 135.0 172.0 义乌

4.3 99.6 82.3 171.0 167.0 108.0 123.0 60.2 187.0 122.0 64.0 诸暨

 

表4-3 所得的节约路程如表

货运量 杭州

1.8  东阳

6.9  22.6 湖州

5.7  23.9 76.5 嘉善

4.8  290.1 22.6 21.6 金华

2.9  290.4 22.6 21.9 374.2 兰溪

3.2  271.8 22.6 21.9 262.6 298.0 浦江

8.3  283.0 53.6 13.9 362.0 386.9 255.0 衢州

5.3  23.9 127.4 75.8 22.9 23.9 23.9 12.9 桐乡

4.7  300.3 22.6 20.9 285.2 286.2 262.5 284.0 22.9 义乌

4.3  189.3 22.2 21.5 184.6 185.6 185.4 182.6 23.5 184.6 诸暨

表4-4 节约路程排序（从大到小）

从（i-j) 兰溪-衢州 金华-兰溪 金华-衢州 东阳-义乌 兰溪-浦江 东阳-兰溪

路程（i-j) 386.9 374.2 362.0 300.3 298.0 290.4

从（i-j) 东阳-金华 兰溪-义乌 金华-义乌 衢州-义乌 东阳-衢州 东阳-浦江

路程（i-j) 290.1 286.2 285.2 284.0 283.0 271.8

从（i-j) 金华-浦江 浦江-义乌 浦江-衢州 东阳-诸暨 兰溪-诸暨 浦江-诸暨

路程（i-j) 262.6 262.5 255.0 189.3 185.6 185.4

从（i-j) 金华-诸暨 义乌-诸暨 衢州-诸暨 湖州-桐乡 湖州-嘉善 嘉善-桐乡

路程（i-j) 184.6 184.6 182.6 127.4 76.5 75.8

从（i-j) 湖州-衢州 东阳-嘉善 东阳-桐乡 兰溪-桐乡 浦江-桐乡 桐乡-诸暨

路程（i-j) 53.6 23.9 23.9 23.9 23.9 23.5

从（i-j) 桐乡-义乌 金华-桐乡 湖州-金华 湖州-兰溪 湖州-浦江 湖州-义乌

路程（i-j) 22.9 22.9 22.6 22.6 22.6 22.6

从（i-j) 东阳-湖州 湖州-诸暨 嘉善-兰溪 嘉善-浦江 嘉善-金华 嘉善-诸暨

路程（i-j) 22.6 22.2 21.9 21.9 21.6 21.5

从（i-j) 嘉善-义乌 嘉善-衢州 衢州-桐乡   

路程（i-j) 20.9 13.9 12.9   

 

表4-5  用户连接过程

（i-j)

兰溪-衢州 金华-兰溪 金华-衢州 东阳-义乌

 11.2 >12 >12 6.5

连接与否 兰溪-衢州 不连 不连 东阳-义乌

（i-j)

兰溪-浦江 东阳-兰溪 东阳-金华 兰溪-义乌

 >12 >12 11.3 >12

连接与否 不连 不连 义乌-东阳-金华 不连

（i-j)

金华-义乌 衢州-义乌 东阳-衢州 东阳-浦江

 11.3 >12 >12 >12

连接与否 义乌-东阳-金华 不连 不连 不连

（i-j)

金华-浦江 浦江-义乌 浦江-衢州 东阳-诸暨

 >12 >12 >12 >12

连接与否 不连 不连 不连 不连

（i-j)

兰溪-诸暨 浦江-诸暨 金华-诸暨 义乌-诸暨

 >12 7.5 >12 >12

连接与否 不连 浦江-诸暨 不连 不连

（i-j)

衢州-诸暨 湖州-桐乡 湖州-嘉善 嘉善-桐乡

 >12 >12 >12 11.0

连接与否 不连 不连 不连 嘉善-桐乡

（i-j)

湖州-衢州 东阳-嘉善 东阳-桐乡 兰溪-桐乡

 >12 >12 >12 >12

连接与否 不连 不连 不连 不连

（i-j)

浦江-桐乡 桐乡-诸暨 桐乡-义乌 金华-桐乡

 >12 >12 >12 >12

连接与否 不连 不连 不连 不连

（i-j)

湖州-金华 湖州-兰溪 湖州-浦江 湖州-义乌

 >12 >12 >12 >12

连接与否 不连 不连 不连 不连

（i-j)

东阳-湖州 湖州-诸暨 嘉善-兰溪 嘉善-浦江

 >12 >12 >12 >12

连接与否 不连 不连 不连 不连

（i-j)

嘉善-金华 嘉善-诸暨 嘉善-义乌 嘉善-衢州

 >12 >12 >12 >12

连接与否 不连 不连 不连 不连

经过节约法计算后得出的方案二的配送路线如图4-3所示。

 

                                            图4-3 方案二的配送路线

杭州－兰溪－衢州－杭州  总距离为571.1公里   总需求量为11.2吨  需要1辆车子

杭州－义乌－东阳－金华－杭州  总距离为437.6公里  总需求量为11.3吨 需要1辆车子

杭州－浦江－诸暨－杭州  总距离为305.8公里  总需求量为7.5吨  需要1辆车子

杭州－嘉善－桐乡－杭州  总距离为193.8公里  总需求量为11.0吨 需要1辆车子

杭州－湖州－湖州   总距离为187.2公里  总需求量为6.9吨 需要1辆车子

三、 选择最优解

表4-6 各个方案之间的比较

 所需车辆 共行驶距离 共行驶小时数 运输费用

线路优化前 10  2934.0  48.9 5253

线路优化方案一 6 1670.4  27.9  3542

线路优化方案二 5  1695.5  28.3 2800

 

图4-4  三个方案的车辆和行驶小时的比较图

 

                                          图4-5 三个方案的行驶距离和运输费用的比较图

从图表4-6中可以看出来，方案二的运输费用是最少的，所以方案二为最优方案。

第五章 总结和展望

        通过对制造业配送的研究，让我更深入地了解了配送的各个流程，进货、订单处理、拣货作业、补货作业、配货作业、送货作业，并且通过对贝因美公司的配送流程的研究，理论结合实践，对整个流程的操作体系有了新的理解。

        大型的制造业公司，往往在全国各地都有自己的分销公司，本文因为篇幅限制的原因，只对贝因美公司在浙江省内的各个网点进行了跟踪调查，并且搜集了很多的数据，最后对其配送路线进行了优化，得出了新的配送方案。

        但是这个模型是一个非常理想的情况，现实中会遇到很多的情况，比如说天气情况、路上的交通情况、甚至要考虑员工的流失情况，非常多的不可预测因素会影响这个模型最后的结果，所以我在这边只能谦虚地说配送路线的优化的精确度还有很大的空间可以提高。

        未来，物流业和制造业的联动发展是一定是以后发展的趋势，并且发展潜力巨大。在物流需求扩大，成本上升的压力之下，越来越多的制造企业开始从战略高度重视物流功能整合，实施流程再造，分离外包物流业务，以更加专注于核心竞争力的打造。制 造业为物流业的发展提供设施和技术基础，物流业为制造业提供生产，现代物流业发展的滞后，必将在一定程度上影响制造业的发展，影响制造业产业结构的升级。

参考文献：

[1]汝宜红，宋伯慧.配送管理[M].北京：机械工业出版社，2004.10

[2]李军，郭耀煌.物流配送车辆优化调度和理论与方法[M].北京：中国物资出版社，2001.11

[3]胡运权.运筹学教程[M].北京：清华大学出版社，2007.4

[4]郎茂祥.配送车辆优化调度模型与算法[M].北京：电子工业出版社，2009.3

[5]张潜.物流配送路径优化调度建模与实务[M].北京：中国物资出版社，2006.9

[6]白世贞，言木.现代配送管理[M].北京：中国物资出版社，2005.1

[7]徐天亮.运输与配送[M].北京：中国物资出版社，2002.9

[8]丁立言，张耀平.配送物流新趋势[M].北京：清华出版社，2003.6

[9]薛荔.我国商业物流现状与发展对策[A].武汉：西南农业大学学报，2009.10

[10]庞文英.浅谈我国制造业与物流业的联动发展[A].上海：物流工程与管理，2009

[11]李云，王平，陈勇，马根峰，焦方源，苏水根.邮政物流配送的数学模型研究[A].重庆：实用物流技术，2002

[12]刘宁杰，陈宇.基于ERP平台的物流配送路径优化[A].广西财经学院工商管理系，2009

[13]杨锦冬，徐丽群.城市物流中心车辆配送配载调度指派模型研究[J].同济大学学报(自然科学版)，2004，11（32）:1452-1456.

[14] 霍震佳，张磊.求解配送收集旅行商问题的启发式算法[J].同济大学学报， 2006，34（1）： 134-138

[15]蒋忠中，注定伟.物流配送车辆路径优化的模糊规划模型与算法[J].系统仿真学报， 2006，18（11）：3301-3304， 3312

[16]姜昌华，戴树贵，胡幼华.求解车辆路径问题的混合遗传算法[J].计算机集成制造系统， 2007， 13（10）：2047- 2052

[17]唐连生，程文明，张则强.基于改进蚁群算法的车辆路径仿真研究[J].计算机仿真， 2007， 24（4）：262-264

[18]刘兴，贺国光.车辆路径问题的禁忌搜索算法研究[J].计算机工程与应用，2007，43（24）：179-181，199

.上海：上海海事大学，2007.

[20] 何明珂.现代物流与配送中心.[M].中国商业出版社，1997.

[21] 吴清一著. 现代物流概论［M］.北京：中国物资出版社，2005.

[22] 周程著. 物流配送路径优化策略研究 [J].武汉理工大学学报，2005.

[23] MARKUS HESSE.Global Chain, Local Pain Regional Implications of Global Distribution Networks in the German North Range.  Growth and Change,2006,Vol. 37 No. 4 , 570–596.

[24] Alan Rushton, John Oxley, Phil Croucher. The handbook of logistics and distribution management [M]. Kogan Page Publishers，2000.

[25] Ronald H Ballou. Business Logistics Management.[M]. Fourth Edition.

Prentice-Hall,Inc.,1999.

       致 　谢

篇7

关键词：随机模拟法 航班计划 航班元素 统计特征

中图分类号：TP31 文献标识码：A 文章编号：1674-098X（2014）01（b）-0089-04

Abstract：The paper aimed at the requirements for simulation flight plan in the airspace capacity evaluation work，sets up a mathematics model according to the flow and pivotal property statistical characteristics of flight plan，the stochastic simulation method is used to solve the problem.For simulatingmany times，the simulation results is analyzed，the results shows that：the advantages of stochastic simulation method that solve complex and uncertainty problem can effectively solve the problem of generating simulation flight plan，the various flow statistical characteristics can meet the requirements，the method has strong stability and practicability.

Key Words：stochastic simulation flight plan flight elements statistical characteristics

我国经济的快速发展，对民航运输提出了新的要求，全国各主要机场通过改扩建或者增加航班架次等方式来提高运力运量，这就需要对运量提升进行容量评估。在进行容量评估工作时，往往需要多种不同容量的航班计划作为评估模型的输入数据。仿真航班计划的生成对空域容量评估工作具有重大意义。

国际上，Terrab、Odoni和Richetta等人研究了基础网络中单个机场的航班集合起降时间分配问题[1]。2003年，Thomas、Frederick等人研究了基于TAAM的仿真航班计划，利用仿真的方法安排跑道航班计划[2]。在国内，1996年，王峰、马寿峰和贺国光研究了航班计划制定及优化因素，运用非线性规划方法对航班计划进行优化[3]。2001年，朱晶波等人建立了多元受限航班计划优化模型，提出了求解的改进启发式算法，并设计了相应的航班时刻优化系统[4]。2008年，钟育鸣、韩松臣等人以机场实际航班运行数据库为基础，讨论了仿真飞机流的数据构成，提出了飞机流的仿真思路、模块结构设计和仿真流程，构建了飞机流的生成模型[5]。2011年，黄魁建立了终端区容量评估模型，并对终端区容量评估中的飞机流产生算法进行了优化研究[6]。

生成仿真航班计划既要满足相应的流量分布要求，又要保证航班流的随机性，同时航空公司对机场机位的使用权以及管制因素，也对容量评估工作以及航班计划生成有重要影响。本文在跑道航班时刻研究的基础上，考虑了航空公司机位的使用问题以及管制因素，结合航班时刻分配的规则，对航班流量特征进行分析并建立数学模型，然后采用随机模拟法将目标航班计划流量特征参数作为已知参数，并针对航班流的随机性，对模型进行求解并生成仿真航班计划。

1 航班流量分析及建模

在已知仿真航班计划流量分布的条件下，首先根据进离港高峰的数学特征对进离港航班时刻进行分配，然后综合考虑以该机场为基地的航空公司的流量特征，进行进离港航班时刻的再分配，最后根据管制部门要求，对各时段各公司各机型的航班的具体航班时刻进行最终分配。

1.1 仿真航班计划流量分布

仿真航班计划流量分布是由数据提供单位根据机场所在地理位置、人群出行特征、经济社会环境等因素，对未来航班流量预测的结果。作为仿真航班计划生成的已知条件，仿真航班计划流量分布还包含离港高峰、全天高峰和全天航班总流量三个关键条件。以图1为例，已知的离港高峰时段出现在7点至10点之间，进港高峰出现在18点以后，全天高峰流量出现在10点至18点之间，全天高峰流量值为32架次，全天流量为466架次。

1.2 进离港航班时刻初次分配

2 随机模拟法的应用

随机模拟法也被称为蒙特卡洛法或者统计试验法，随机模拟法求解问题的思想为：首先，建立一个概率模型或者随机过程，使它的参数等于问题的解；然后通过对模型或者过程的观察或抽样试验来计算所求参数的统计特征，最后给出所求解的近似值。而解的精确程度可用估计值的标准误差来表示。

仿真航班计划数据量大，除了要保证各种机型、公司以及各个方向的航班的到达和离港具有随机性，还要保证航班计划的各项统计特征能够满足对应的预测参数，只有满足这些条件，生成的仿真航班计划才有意义。由此可知，仿真航班计划的生成问题，就变成了如何产生满足相应参数要求的航班计划的问题和如何保证航班计划随机性的问题。

仿真航班计划的各项特征，决定了传统的确定性模型难以解决航班计划生成中的不确定性难题。在这种情况下，可以考虑随机模拟法。随机模拟法可以针对仿真航班计划中的各项属性的随机性问题建立一个简单且便于实现的概率统计模型，使所求的量或解恰好是各项航班属性概率分布或者数字特征。

2.1 随机模拟法实现航班时刻初次分配

在已知航班流量分布的情况下，结合随机模拟法，可以生成全天各小时的航班进离港流量，并完成航班时刻的初次分配。

使用随机模拟法，将航班计划中的进离港流量参数的目标值作为已知条件，设，，，。为进离港流量相对均衡时段离港航班流量占该时段航班流量的比例，为进港高峰时段离港航班的流量比例，为进离港相对均衡时各时段的航班流量集合。在进港高峰时间为，在该时段内生成取值范围为的均匀分布随机数，离港高峰时间为，在该时段内生成取值范围为的均匀分布随机数，在进离港流量相对均衡的时段内，生成取值范围为的均匀分布随机数。令，

，由此可得全天各个时段的离港航班流量，的表达式为：。那么全天各时段的进港航班流量也可求得。

2.2 随机模拟法实现航班时刻再分配

对航空公司进行分类，在该机场有基地的航空公司称为基地航空公司，其他的航空公司称为无基地航空公司。在离港高峰时段，基地航空公司离港航班流量比例和无基地航空公司离港航班流量的比例可由终端区或者机场规划设计部门给出预测值。假设第个小时的航班流量占全天航班流量比例为，航空公司的预测份额为，各航空公司航班流量占该时段航班总流量的比例为，那么由可以求得各个时段各航空公司航班流量的比例。

生成均匀分布的随机数列，根据求得的值将生成的随机数列划分为区间，当随机数值落在对应的区间时，设定该航班所属的航空公司为对应的航空公司，由此可以完成航空公司航班时刻的再分配。

2.3 航班时刻的最终分配

以8点至9点的航班为例，该时段，该小时航班流量占全天航班流量的比例为5.4%，那么可以求得该时段各个航空公司的离港流量占全天流量的比例，同理可以求得其它时段的比例值。表2为添加了航空公司信息的8点到9点的部分航班计划表，进离港标志中，A代表航班进港，D代表航班离港。各航空公司8点到9点的航班流量为。

第三步，同样以8点至9点的航班时刻为例，令，。生成随机数对航班排序，以五分钟为单位对航班时刻进行规范化处理，得到如表3所示的部分航班计划表。由于8点至9点之间航班量为28架次，以五分钟为单位规范航班时刻时，每五分钟的航班流量为。

3.2 结果分析

经过以上三个步骤，可以生成目标航班计划。使用matlab程序进行100次航班计划生成仿真，对航班计划中的关键流量数据进行统计，统计结果见表3。由以上结果可知，该文采用的航班计划生成方法具有较好的稳定性和实用性。

航班计划是由管制部门、机场部门以及航空公司多方参与制作的，限于篇幅，本文未考虑航班来向去向、航班机型等因素。同时，随机模拟法中对随机数的使用，使本文中的方法更适用于大流量机场的仿真航班计划的生成。对于更复杂仿真条件下航班计划的分析与生成，还有待进一步的深入研究。

参考文献

[1] O.Richetta，A.R.Odoni.Solving optimally the static ground-holding policy problem in air traffic control[J].Transportation Science，1983，27，August 1993：p228-238.

[2] Thomas Curtis Holden，FrederickWieland.Runway schedule deter-mination by simulation optimization[Z].Proceedings of the 2003 Winter Simulation Conference.McLean，MITRE corporation，2003：1670-1676.

[3] 王峰，马寿峰，贺国光.航班时刻表优化模型的研究[J].系统工程学报，1996，11（1）：50-56.

[4] 胡明华，朱晶波，田勇.多元受限的航班时刻优化模型与方法研究[J].南京航空航天大学学报，2003，35（3）：326-332.

篇8

关键词：运筹学；应急物流；选址―定位

中图分类号：F250 文献标识码：A

Abstract： Because the efficient of emergency logistics can reduce the harms caused by emergency， it has caused wide public concerns among theorists. This paper provides an overview of Chinese emergency logistics study from many aspects： basic theory， the construction of system and the related models on the base reviewing the liberations in recent years， also it indicated that the modeling sense in operation research plays a decisive role in the research of emergency logistics.

Key words： operation research； emergency logistics； location-routing

近年来，我国各地突发事件频发，其中自然灾害的发生的占比非常高，如2010年8月甘肃舟曲发生特大山洪泥石流、2014年7月云南发生洪涝泥石流灾害、2013年3月墨竹工卡县发生山体滑坡灾害、2013年7月甘肃岷县漳县发生6.6级地震灾害、2014年新疆于田发生7.3级地震灾害、2015年9月江西福建等地发生洪涝风雹灾害、2015年8月陕西山阳发生滑坡灾害等。这些自然灾害的发生严重威胁人类的生命和财产安全，以及社会的经济发展甚至会影响和谐社会的构建，在突发事件发生后，如何尽快地将赈灾物资送至灾区以减少灾害损失是应急物流问题研究的主要内容，即应急物流LRP问题的研究。应急救援部门必须以最小的成本、最快的时间、合理地选择物资存储点将存储物资科学地安排车辆对受灾点进行物资的配送服务以减少伤亡，提高受灾地区民众的抗灾信心。

当前国内外学者对一般LRP问题的研究比较具体深入，比如Min等[1]（1998）、Nagy等[2]（2007）、陈久梅等[3]（2014）都做过一般LRP问题的优化研究，当前应急物流的优化问题已经引起了众多学者的关注，但是对于应急物流的LRP研究（定位―路径）还相对较少。现有文献主要有两种研究范式：一种是单独研究其中一个问题，即单独研究应急物流中心选址问题或单独研究应急资源调度问题；另外一种是将这两个问题集成起来进行研究。然而应急物流中物流中心点的选择和运输路径安排是直接影响应急物流系统效率的两个关键问题，两者之间相互依赖和影响，有必要结合应急物流的突发性、不确定性、紧急性等特点，从整体系统优化的角度，将这两方面结合起来进行研究，故近年来，大部分对于应急物流问题的研究均是对选址―配送这两个问题集成起来进行研究。根据现有的研究，应急物流LRP问题基本可以按照信息是否确定分为以下两类：确定信息下的应急救援问题研究和不确定信息下的应急救援问题研究。

1 确定信息下的应急物流LRP研究

确定性的应急物流LRP问题，通常考虑的问题中信息基本都是确定的，即不存在任何风险因素，并且受灾点的需求是确定的。针对确定性的应急物流LRP问题的研究，张玲[4]（2008）考虑到由于灾区范围比较广泛进而灾区存在不同的级别，针对该实际情况，通过对灾区进行分组，并运用场景分析的发放，考虑其资源的布局和选址问题，引入多类0-1变量来表述该优化问题，构建了基于多级别的资源布局多目标规划模型。黄向荣等[5]（2009）在考虑食品物流的相关特点和突发事件的突发性、紧急性以及弱经济性等特性的基础上，构建了食品的应急物资分发中心选址决策的评价体系，并且结合蚁群算法（ACA）和径向基神经网络（RBFNN）构建了应急物流物资分发点选址决策模型。曾敏刚等[6]（2009）针对应急服务应急物资分发点定位以及物资配送路径这两个子问题，引入多个0-1决策变量去表述该优化问题，建立了以最小化总成本为目标的选址―定位模型。葛春景等[7]（2011）研究了应急设施选址中的多重覆盖问题，并以在满足需求点的多次覆盖需求和多需求点同时需求的条件下覆盖的人口期望最大为目标，建立了确定性的应急物流优化模型，通过改进的遗传算法对该模型进行求解。郑斌、马祖军等[8]（2013）针对两级应急物流系统中的中转站选址和上下级进行联运调度的集成优化问题，建立双层规划模型，并根据该模型的特点设计了一种混合遗传算法。

通过以上文献梳理可知，在运用运筹学建立应急物流LRP模型过程中，通常引入0-1决策变量去解决应急物资分发点选址问题和车辆物资配送问题，引入三类决策变量，第一类0-1决策变量是表示应急物资分发点是否开设，通常1表示该应急物资分发点开设，0则表示不开设，当该决策变量为1时，才分配运输车辆从该应急物资分发点出发进行物资配送服务，并且从同一个应急点出发车辆的物资运输量需小于应急点的物资存储量；第二类0-1决策变量是用来表示某运输车辆服务哪个受灾点的问题，1表示运输车辆服务该受灾点，0则表示运输车辆不服务该受灾点；第三类决策变量则表示某运输车辆是否从该应急物资分发点出发，1表示这运输车辆从该应急物资分发点出发，0则表示这个运输车辆不从该应急物资分发点出发。这三类0-1变量的引入合理地表述了应急物流系统的优化问题，目标函数通常为应急物流系统总成本最小以及运输车辆到达所有受灾点的总时间最小，建立的模型均为0-1线性规划模型。运筹学中0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面，而应急物流的优化问题从运筹学的角度就是一种分派问题，因此运筹学能够在应急物流优化问题中大放光彩。目前，0-1应急物流规划问题通常有三种解法，即穷举法、变换法和隐枚举法。解0-1型整数规划最容易想到的方法，和一般整数线性规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种决策组合，比较目标函数值的大小，从而选出目标值最小的那一组决策组合就是应急物流优化问题的最优解。然而由于应急物流优化问题中涉及的变量较多，所有决策组合就非常多，可能解集将成指数剧增加，此时用这种方法效率就比较低下，因此通常运用隐枚举法进行求解，“隐”的含义是指在检验可能解的可行性和非劣性过程中，根据目标函数的特性增加一个以前一非劣解目标值的附加约束的过滤条件，以此达到减少问题求解过程的运算次数的目的。方法的核心思想均为检查变量取值为0或1的策略组合，通过目标函数值比较从而得出最优解。

2 不确定信息下的应急物流LRP研究

针对不确定性的应急物流LRP研究，通常考虑的问题中信息基本都是不确定的，并且在救灾期间存在一定的风险，比如应急设施点失灵风险、路径中断风险、路径复杂度等，同时往往受灾点的需求是不确定的。

何珊珊等[9]（2013）针对在突发事件发生的紧急救援期，受灾点的需求很难确定，基于此建立了受灾点配送总时间最短和系统总成本最小的选址―路径问题的数学模型，并通过算例验证了多目标鲁棒优化模型能够体现受灾点对各类物资需求不确定条件下选址―配送方案的最优性与鲁棒性的均衡。孙华丽等[10]（2013）针对需求随机变化的应急物流定位―路径问题，将救援过程划分为两个阶段，将受灾点的物资需求表示为一个区间数，以物资送达时间最短和系统总成本最小为目标，构建了多物资、多运输车辆、多目标的定位―路径模型。张玲等[11]（2014）也将救灾过程分为了两个阶段，考虑到突发灾害初期灾情相关参数概率分布信息很难精确获得，建立了基于情景的最小最大后悔值准则的鲁棒优化模型，求解模型时，利用有限情景集表示第二阶段的不确定数据，并将模型化为与其等价的混合整数模型，利用情景松弛的迭代算法进行求解。商丽媛等[12]（2013）考虑不同情景下应急物流需求的不确定性，将不确定需求用区间灰数表示，构建了多情景下不确定需求的应急物流配送中心选址模型，并设计了免疫量子粒子群算法进行求解。针对由于自然灾害带来的路网风险的应急物流LRP问题，阎俊爱、郭艺源[13]（2016）考虑到路网情况实时变化的复杂性下，构建了应急物流LRP动态模型，以车辆配送时间最小为目标，并通过设计的遗传算法实现了基于动态路网实时调整的问题求解。陈钢铁、黎青松等[14]（2016）考虑到路网存在灾后受损的风险，故引入多种运输方式，基于此构建了震后多式联运的应急物资配送路径优化模型，并设计了启发式算法对该应急物流模型进行了求解。

以上不确定信息下的应急物流LRP优化问题研究中，均运用了运筹学不确定规划的思想建立了应急物流LRP模型，在应急物资分发点选址问题以及路径配送与否方面，同样引入三类0-1决策变量来表示应急物资分发点建立与否，车辆是否从某个应急物资分发点出发以及车辆是否服务某个受灾点。除此以外，引入两类整数决策变量，一类为运输车辆配送至某个受灾点的物资量，一类为某个受灾点的物资未满足量，在约束中，这两个量的和大于该受灾点的物资需求量，同时针对未满足量尽量最小化的目标，将在目标函数中赋予未满足量一个很大的惩罚数。在模型求解中，运用了随机规划的思想去处理一些风险因素，在处理受灾点物资需求的不确定方面，则运用三角模糊数的理论或鲁棒优化的思想去处理不确定性，在模型求解过程中，最终均通过一定的方法把不确定模型转化为确定的混合整数模型去进行求解。

运筹学的核心思想即为从现实生活场合抽出本质的要素来构造数学模型，探索求解的结构，从可行方案中寻求系统的最优解作为决策者最好的选择。通过以上文献的梳理，可以看出运筹学在应急物流系统定位―路径优化问题中已经成为核心工具之一，而应急物流系统定位―路径优化问题作为当前的热点问题之一，它的研究仍然处于初步阶段，许多领域还缺乏系统性和深入性的研究，需要进一步加强研究。

参考文献：

[1] Min H， Jayaraman V， Srivastava R. Combined location-routing problems： a synthesis and future research directions[J]. European Journal of Operational Research， 1998，

108（1）：1-15.

[2] Nagy G， Salhi S. Location-routing： issues， models and methods[J]. European Journal of Operational Research， 2007，177（2）：649-672.

[3] 陈久梅，邱晗光. 两级定位―路径问题模型及变邻域粒子群算法[J]. 运筹与管理，2014（6）：38-44.

[4] 张玲，黄钧，朱建明. 应对大规模突发事件的资源布局模型与算法[J]. 系统工程，2008，26（9）：26-31.

[5] 黄向荣，谢如鹤. 基于蚁群算法与RBF神经网络模型的突发应急配送决策[J]. 决策参考，2009（15）：56-58.

[6] 曾敏刚，崔增收，余高辉. 基于应急物流的减灾系统LRP研究[J]. 中国管理科学，2010，18（2）：75-80.

[7] 葛春景，王霞，关贤军. 重大突发事件应急设施多重覆盖选址模型及算法[J]. 运筹与管理，2011，20（5）：50-56.

[8] 郑斌，马祖军，李双琳. 基于双层规划的应急物流系统选址―联运问题[J]. 系统科学与数学，2013，33（9）：1046

-1060.

[9] 何珊珊，朱文海，任晴晴. 不确定需求下应急物流系统多目标鲁棒优化模型[J]. 辽宁工程技术大学学报，2013，32（7）：998-1003.

[10] 孙华丽，周战杰，薛耀锋. 考虑路径风险的不确定需求应急物流定位―路径问题[J]. 上海交通大学学报，2013（6）：962-966.

[11] 张玲，陈涛，黄钧. 基于最小最大后悔值的应急救灾网络构建鲁棒优化模型与算法[J]. 中国管理科学，2014（7）：131-139.

[12] 商丽媛，谭清美. 不确定应急物流中心选址模型及算法研究[J]. 计算机应用研究，2013，30（12）：3603-3605.

篇9

关键词：配送中心；选址问题；成本；服务半径

中图分类号：F252.14 文献标识码：A

0 引 言

物流配送中心是专门从事物资配送业务的物流基地，是通过转运、分类、保管、流通、加工和信息处理等作业，根据用户的订货要求备齐商品，并能够迅速准确和廉价地进行配送的基本设施。物流配送中心连接着供应商、制造商和分销商及客户，决定着供应链的流通成本和运作效率。在整个物流配送中心建设规划中，一个非常重要的问题就是配送中心的选址。正确的选址策略不仅可以减少企业的各项成本，还能为客户提供更优质的服务。

一般来讲，配送中心是一个成本中心而非利润中心，如果使用绝对成本作为考核指标，管理人员将会更倾向于压缩支出，这样不利于高质量地完成物流服务。因此，使用相对指标更加合理，例如企业配送中心的服务半径。如果配送中心的服务半径过大，那么它的辐射范围也越大，覆盖的客户就越多，其服务能力将供不应求，这样会影响配送服务的质量及水平；另一方面，如果配送中心的服务半径过小，那么它的辐射范围也就越小，服务能力将会过剩，严重影响配送中心的使用效率。21世纪以来，物流企业的侧重点已经由单纯地追求收益和利润向更好更高效地为客户服务转变。例如，以前百胜的配送中心设定300公里的最远服务半径。在2012年年末盼盼食品等17家食品企业为了合理地布局增加企业竞争力而大大缩短企业在全国各配送中心的配送半径。由此可见，服务半径对于企业来说是一个决定企业布局的重要影响因素。

而配送中心最终是要为特定的目标客户服务的。因此，配送中心一定要能够辐射到其特定的目标客户。那么配送中心的位置就必然要受到服务半径的制约。配送中心选址问题就是确定配送中心的数目、位置以及每个配送中心所服务的客户群体。配送中心选址问题所追求的目标可归纳为三类：一是成本，即追求总费用最低；二是距离，即如何选择确定配送中心的位置使得整个物流网络总路径最短；三是时间，即要求在最短的时间内将物资运送到需求点。这三个方面互为侧重点，国内外很多学者分别从三个方面加以研究，取得了重要的研究成果。

选址问题近年来受到了越来越广泛的关注，并且形成了几种基本的模型，如连续选址模型、网络选址模型和离散选址模型。连续选址也称为平面选址，允许在可行的连续空间任何位置选址。它有两个基本的属性，一个是解空间是连续的，另一个是要用适当的量度测量其距离。相关研究，如Brimberg等（2000）[1]、Kafer and Nickel（2001）[2]、Klamroth（2001）[3]等。对于网络选址，距离被视为地图中的最短路径，允许在指定网络的顶点和边上选址。网络选址的研究，如Boffey等（2003）[4]、Beasley（1993）[5]等。如果给定一个预配送中心集合，选址问题可归为离散选址。有兴趣的读者可以查阅Goldengorin等（2003）[6]、Harkness and ReVelle（2003）[7]、Grunert（2002）[8]、Chardaire（1999）[9]、Gourdin（2000）[10]等。

针对选址问题模型的求解方法主要有定性和定量两种。定性方法包括专家打分法和德尔菲法等；定量方法包括重心法、P中值法、数学规划法、多准则决策方法、各种启发式算法、仿真法以及这几种方法的结合等。

本文遵循经济性与服务性的原则，与传统离散选址模型不同之处是，在考虑成本，即运输成本、固定建设成本、存储成本基础上，引入了服务半径的约束，建立了多物流配送中心选址问题的数学模型。最后，通过一数学例子对模型进行了数值计算。然后用分区域法对同一例子进行了求解。并将结果进行了对比分析。结果表明带服务半径约束的选址模型比企业普遍使用的区域划分选址方法成本更低，服务更高效。本文的研究将对实际问题具有一定的借鉴作用。

1 建立模型

1.1 问题描述

物流配送中心选址问题可描述为：某地区有需求点若干个，已知每个需求点的需求量，现欲在有限个备选地址中选择某几个地址建立配送中心，并为每个需求点运送物资，用来满足每个需求点的需求，配送中心到其服务的需求点的配送半径不能超过限值。目标是使总费用最少。结构图如图1所示：

1.2 假设条件

为了简化配送中选址问题，我们不妨做如下的几个假设：

（1）在给定的若干个备选地址中选择某几个地点建立配送中心；

（2）每个需求点可由多个配送中心提供物资；

（3）配送中心容量足够大，能够满足所有需求点的需求；

（4）各需求点的需求量一定且为已知；

（5）各配送中心没有多余的物资冗余；

（6）配送中心与各用户间的单位运费已知；

（7）运输费用与运输量成正比。

为了建立模型，我们引入以下的几个变量：

2 案例分析

山东某物流公司的客户分布在本省的17个城市，为了满足客户需求并且降低成本，该公司决定在这些城市中建立3个配送中心，配送中心备选地分别是城市1、2、3、8、11、15、17，单位运输成本为1.8（元/吨公里），要求配送中心的服务半径是270公里。公司面临的首要问题就是配送中心的位置和配送方案。图2为山东省地图，表1至表4分别列出了各需求点及其编号、各需求点的年需求量、各需求点的物资单位存储费用和固定建设成本，以及各需求点与备选点间的公路距离等。

2.1 精确求解

用LINGO软件求解，得到目标值为1 311 818元，配送中心选择的地点为2、11、17（如图3所示），配送方案如图4所示。

2.2 分区域解法

精确解法将所有的地点放在一起进行整体选址、配送。而现如今，很多企业是将配送中心按要求进行分区域配送，比如现在很多企业习惯将中国分为华南、华中、华北、东北、西北、西南6个大区，然后分别在每个大区设定区域机构，然后向下属单位或者客户进行区域内配送。

本案例中由于需求点较多而且分布比较广，因此首先对所有的需求点进行区域划分，形成若干个配送区域。影响选址决策的因素有很多，本文选择主要的几个宏观因素，根据各需求点间宏观因素的相似性将需求点进行分类，使相似性较大的需求点聚集在同一个区域，具有较大差异的需求点划分在不同的区域。为了确保所选因素量化的可行性，除了需求点坐标外，本文还选取了5项反映该区域物流发展水平的主要指标，包括市场繁荣度、信息、区位商、货运比重和工业比重[11]。各指标含义如下：

（1）坐标：坐标主要是用于根据各需求点的相对位置确定其归类。

（2）市场繁荣度：城市批发零售贸易业的产品销售额 / 该城市的国内生产总值。

（3）信息：（城市移动电话人数+城市固定电话户数+使用网络人数） / 该城市人口总数。

（4）区位商：（城市交通、仓储、邮电业从业人数/该城市总从业人数） / （全国交通、仓储、邮电业从业人数/全国总从业人数）。城市区位商反映了该城市的物流专业化水平。商值大于1，表示物流部门从事基本经济活动；值小于1，表示全部物流部门都属于非基本经济活动，不利于城市的发展。

（5）货运比重和工业比重分别指该城市的货运总量和工业产值占山东本省相应项目的比重。

表5显示了各需求点相应的指标值及其分区结果，其中第5至第9列的数据来源于2011年山东省统计年鉴。最后一列是用SPSS软件根据上述7项指标用系统聚类法归类的结果。

从表中可以看出配送区域分类的结果，最佳配送区域划分数量为3，其中需求点威海市、烟台市构成区域1，需求点青岛市、日照市构成区域2，需求点潍坊市、东营市、滨州市、淄博市、莱芜市、泰安市、济南市、德州市、聊城市、菏泽市、济宁市、枣庄市、临沂市构成区域3。

计算各区域内的最佳配送中心。根据表2、表3、表4的数据，利用EXCEL分别求出7个备选点作为配送中心时所对应的总费用，结果如表6所示。从表6的结果可以看出，3个区域的配送中心分别应该建在威海市、青岛市和济南市，总费用为

1 393 432.72元，具体的配送方案如图5所示。

表7列举了带服务半径约束的精确解法与现在普遍适用的分区域法的各种参数，分别从配送中心的选择地点、固定建设成本、存储成本、运输成本以及总费用等方面进行对比分析。可以看出，配送中心选择的地点有很大的差异。带服务半径约束的精确解法相比分区域解法，不仅总费用要少很多，而且能够更高效地为客户提供服务，服务水平明显提高。导致这种差异的因素主要有以下几个方面：其一，固定建设费用。分区域解法在划分区域的时候并没有将各城市的固定建设成本考虑进去，这导致了配送中心选择地点的时候很可能将地点设在建设成本很高的备选点，如本例中青岛市；其二，运输费用，带服务半径约束的精确解法由于考虑了距离的因素，也就变相地缩短了配送中心的配送路程，从而最终使得总运输路径减少，运输费用比区域划分法要少很多。综合几方面的考虑，本文引入服务半径建立的模型要比现今很多企业正在使用的分区域法更适合企业。

3 结 论

本文重点就选址配送问题，建立了带有服务半径约束的规划模型，通过数学例子对模型进行了数值计算。然后用分区域法对同一例子进行了求解。并将结果进行了对比分析。结果表明带服务半径约束的选址模型比企业普遍使用的区域划分选址方法成本更低，服务更高效。对于企业来说，不仅能够节省相关的成本，而且能够更好地为客户服务，符合物流企业“一切以客户为中心”的战略要求。尤其是在油价上涨的当下，本文提出的模型更有利于企业长远、持续的发展。

但在建模及求解过程中，本文没有对配送中心的容量（承载量）加以限定。而且在配送过程中，我们假定车辆是一次配送完成，不涉及车辆调度的具体问题，并且对道路的状况、客户需求不确定情况等方面都没有考虑，与现实有一定的差异。这些都需要在今后的研究中加以解决，从而更好地为企业的决策者服务。

参考文献：

[1] J. Brimberg， P. Hansen， N. Mladenovic， E. Taillard. Improvements and comparison of heuristics for solving the multisource Weber problem[J]. Operations Research， 2000，48：444-460.

[2] B. Kafer， S. Nickel. Error bounds for the approximate solution of restricted planar location problems[J]. European J. Oper. Res.， 2001，135：67-85.

[3] K. Klamroth. Planar Weber location problems with line barriers[J]. Optimization， 2001，49：517-527.

[4] B. Boffey， D. Yates， R. D. G. Galvao. An algorithm to locate perinatal facilities in the municipality of Rio de Janeiro[J]. J. Oper. Res. Soc.， 2003，54：21-31.

[5] J. E. Beasley. Lagrange an heuristics for location problems[J]. European J. Oper. Res.， 1993，65：383-399.

[6] B. Goldengorin， D. Ghosh， G. Sierksma. Branch and peg algorithms for the simple plant location problem[J]. Comput. Oper. Res.， 2003，30：967-981.

[7] J. Harkness， C. Re Velle. Facility location with increasing production costs[J]. European J. Oper. Res.， 2003，145：1-13.

[8] T. Grunert. Lagrangean tabu search， in： C.C. Ribeiro， P. Hansen （Eds.）， Essays and Surveys in Metaheuristics[M]. Kluwer Academic Publishers， Boston， 2002：379-397.

[9] P. Chardaire， J. L. Lutton， A. Sutter. Upper and lower bounds for the two-level simple plant location problem[J]. Ann. Oper. Res.， 1999，86：117-140.

[10] E. Gourdin， M. Labbe， G. Laporte. The incapacitated facility location problem with client matching[J]. Oper. Res.， 2000，48：671-685.

篇10

鉴于即期客户较难准确预测，传统的舱位分配存在着很大的不确定性，综合运用市场细分和收益管理的方法，考虑空箱调运问题，围绕即期客户和合同客户这两大客户群建立航运电商环境下两艘对开班轮的舱位分配优化模型.以中日韩航线为例，计算为即期客户和合同客户预留的舱位数；根据在航运电商环境下预测值与实际值差距缩小的特征，分析传统环境下与航运电商环境下集装箱班轮舱位分配方案的差异.在航运电商环境下计算所得的总收益大于传统环境下的总收益，显示该优化模型的有效性和电商平台的优越性.结论如下：航运电商的发展能有效提高班轮公司收益；电商平台下的舱位分配趋势使预测精度大大提高，预留的舱位数与实际到达的客户需求出入较小；电商客户在航运电商环境下会得到大力发展，合同客户的数量会逐渐下降.

关键词：

航运电商； 集装箱班轮； 收益管理； 舱位分配

中图分类号： U695.22； F551

文献标志码： A

0 引 言

在当今航运市场竞争越发激烈、航运市场环境越发黯淡时，随着互联网的风起云涌，电子商务出现革命性的飞跃.它改变着世界贸易环境和企业运作方式，成为航运企业提高自身竞争力的有力法宝.航运电商已将传统的订舱和比价推上“线上交易”平台.这些新的电商平台不仅使海运业供需双方长期以来的交易模式发生改变，而且使交易双方成本降低、效率提升、服务水平提高.行业集中度和标准化水平的提高促使海运物流行业从原先的价格和规模竞争升级到服务、体验和整合能力竞争.航运企业的信息化水平将直接影响供应链的有效建立，进而影响企业的竞争力.通过电子商务，航运企业能够及时获取订舱信息，以便实时调整航线、班期、配载和运价，及时调整合同客户和即期客户的舱位分配，从而提高效率、降低成本.航运电商正成为航运业突破市场低迷与剧烈动荡、转变商业模式的有效手段.

集装箱班轮的舱位分配一直都是国内外学者研究的热点问题.TING等[1]基于收益管理的思想，考虑客户满意度和航运企业收益最大化两个目标，提出一种模糊多目标规划方法求解集装箱班轮航位分配问题.HA[2]利用泛太平洋西向航线的订货数据，应用期望边际收益（Expected Marginal Revenue）和阈曲线（Threshold Curve）模型，对集装箱班轮公司的舱位控制策略进行较为深入的研究.MARAGOS[3]和SPYRIDON[4]分析班轮货运的特点，研究多种情况（单航段、多航段、多航段多种类货物、临时取消订舱、超订）下集装箱舱位动态分配和定价问题，建模的方式有整数规划、线性规划、动态规划等，采用启发式算法求解.随后，ZURHEIDE等[5]对舱位分配问题进行持续的研究.FENG等[6]以装载港货量一定为前提，优化传统的舱位分配模型，使其更适用于复杂密集的亚洲港口网络的港到港舱位分配问题.卜祥智等[7]针对海运收益管理的特征，建立考虑长期运力合同、空箱调运的班轮运力分配和路径选择随机规划模型，然后应用稳健优化方法对此模型进行求解.杨华龙等[89]利用概率统计方法，计算出在一个多港挂靠循环航次中所包括的各个航段应为普通客户预留的舱位数量，建立包含空箱调运问题的舱位分配随机规划模型，通过确定各航段为长期合同客户预留的舱位数量的上下限，将随机规划模型转化为可以求解的确定性规划模型.施欣[10]结合对集装箱海运空箱调运过程的剖析，建立相应的系统优化模型，并通过数字仿真揭示成本、收益等经济参数以及船舶装载能力对集装箱空箱调运策略的影响机制.陈继红[11]以班轮运力配置模型为基础，建立基于非线性目标规划的班轮联盟舱位租赁决策优化模型，用于分析和研究联盟情况下集装箱班轮系统舱位租赁、配置优化与决策问题.王琳等[12]对非合作博弈和联合决策情形下的系统效率进行比较，通过数值算例分析远期合同舱位优惠价格对系统效率的影响，给出协调整个系统的方法，有效地提高系统总效率.李冰州等[13]进一步研究考虑集装箱二维特性（容量和重量）的最优舱位分配策略，还考虑最优超订水平.殷明等[14]认为：班轮运输是海洋运输的一种方式，为海上集装箱提供定期的运输服务，带有浓厚服务性色彩；它向社会提供的不是实物形态的产品，而是一种劳务产品，即集装箱货物的空间位移.郭咏春等[15]探讨碳约束配额、燃油价格、码头装卸效率等对成本及碳排放量的影响，为船公司运营和政府决策提供参考.

综上：现有文献有的只考虑重箱而忽略空箱调运；有的只研究确定情况下的需求，对于不确定需求没有给出有效解法；有的仅仅考虑如何减少空箱调运成本，并没有考虑整个航运公司的收益管理问题；所有文献都没有考虑航运电商对舱位分配的影响.本文在现有文献的基础上，运用概率统计的方法，基于市场细分和收益管理理论，考虑空箱预留和航运电商环境下不同客户群的差异化定价进行舱位分配，以谋求收益的最大化.

1 舱位分配模型构建

1.1 问题描述

在一条由若干个港口组成的固定航线上，班轮公司安排两艘集装箱班轮分别从该航线两端相向对开，依次挂靠沿线的各个港口.班轮公司的客户群大体分为两类，合同客户和即期客户.合同客户指已经与班轮公司签订长期合同的客户，以一些大的货主和货运公司为主；即期客户指那些零散的、不确定的客户.

假设班轮公司的客户群在航运电商环境下分为电商客户和合同客户， 在传统环境下分为普通客户和合同客户.本文的即期客户指航运电商环境下的电商客户或传统环境下的普通客户.

合同客户由于货物的稳定性和数量较大可以享受班轮公司为其制定的折扣价格，而即期客户定价相对较高.班轮公司为维持运营，在每个航次上都会为合同客户预留一定数量的舱位，其余的则留给即期客户.如何确定为合同客户和即期客户在每个港口预留的舱位数，既满足合同客户的需求，又最大限度地满足即期客户的需求，尽可能多地降低舱位的虚耗和需求的溢出，以使获益最大，是班轮公司需要考虑的问题.

1.2 参数设置

Rc为来自合同客户的单位运输收益，Re为来自电商客户的单位运输收益，Ro为来自普通客户的单位运输收益，Rb为空箱的单位运输收益，Q为每艘班轮的舱位数量，de为电商客户实际的舱位需求量，do为普通客户实际的舱位需求量，dc为合同客户的舱位需求量，dbj为在港口j的空箱需求量，Qe为班轮为电商客户预留的舱位数，Qo为班轮为普通客户预留的舱位数，re为电商客户预期的边际收入，X为分配给合同客户的舱位数，Y为空箱调运数.

1.3 模型假设

（1）对开的两艘班轮舱位数相同.

（2）这条固定航线共有n个港口，i，j=1，2，…，n， i

（3）合同客户、电商客户和普通客户在正向航段（ij）和反向航段（ji）上的舱位需求都服从正态分布，即dc～N（d-c，σc），de～N（d-e，σe）和do～N（d-o，σo），其中d-c，d-e，d-o为期望值，σc，σe，σo为标准差.

（4）下列参数已知：Rc，Re，Ro和Rb，以及dc，de和do三者各自的均值和标准差.

（5）当合同客户的边际收入与即期客户预期的边际收入相等时收益最大.

1.4 模型构建

式（11）表示即期客户与合同客户的收益之和减去空箱运输费用，所得集装箱班轮运输收益最大；

式（12）表示第1艘班轮从港口i出发，分配给合同客户的舱位数与空箱数之和不超过在港口i可接受即期客户的舱位数；

式（13）表示第2艘班轮从港口j出发，分配给合同客户的舱位数与空箱数之和不超过在港口j可接受即期客户的舱位数；

式（14）表示在正向航段（ij）上，为使各港口进出的集装箱数保持平衡，空箱调运数不小于港口j的空箱需求数，保证港口有空箱可用；式（15）表示在反向航段（ji）上，空箱调运数不小于港口i的空箱需求数；式（16）表示在正向航段（ij）上，分配给合同客户的

舱位数不能超过合同客户实际的集装箱舱位需求，目的是尽可能多地满足即期客户的舱位需求；式（17）表示在反向航段（ji）上，分配给合同客户的舱位数不能超过合同客户实际的集装箱舱位需求；式（18）表示决策变量的整数约束.

2 算例分析

2.1 案例

有一条固定航线（见图1），由5个停靠港口组成，依次为上海港―青岛港―釜山港―神户港―东京港.在这条航线上有相向而行的两艘班轮，合理分配舱位以使两艘班轮的总收益最大.

2.2 已知条件

这两艘班轮的容量都是5 000 TEU，其他已知条件见表1和2.

2.3 两种环境下舱位的优化结果

相对于传统的舱位分配，通过航运电商平台预定舱位波动幅度更小，舱位分配更加合理.根据航运电商环境下预测值与实际值差距缩小的特征，当de=do时分别取各航段σe的平均值为10，20和30 TEU，运用MATLAB，根据表1和2给出的已知数据，求出传统环境下和航运电商环境下两艘班轮在每一航段应为合同客户预留的舱位数、各港口可接受的即期客户的订舱数以及空箱调运的情况.求解模型得到两艘集装箱班轮在各航段不同σ值所对应的舱位优化分配结果，见表3和4.

2.4 对比分析

根据上面的优化结果，可以计算出航运电商环境下和传统环境下集装箱班轮公司该航次运费总收益，见图2.在传统环境下，即使进行舱位的优化分配，最后计算出的总收益也只有29 448 717美元；在航运电商环境下，即使当σe=30 TEU时总收益也能达到31 244 778美元.对比两种情况所计算的总收益可知，班轮公司通过电商平台至少可以多赚取1 796 061美元的收益.

由图2可知，在市场细分条件下通过航运电商平台进行的舱位分配优于传统平台下的舱位分配，且随着σe的增大总效益呈下降趋势，即在航运电商环境下预测精度越低期望收益越小.

由图3和4中合同客户和即期客户的平均数量可知，随着σe逐渐减小（即预测精度逐渐提高），合同客户数量逐渐下降，

即期客户数量逐渐上升.因此，在航运电商环境下进行集装箱班轮的舱位分配，一方面要保持电商平台预测精准性，合理拥有合同客户，另一方面要积极发展电商客户.

3 结束语

电子商务在近几年发展迅速，电商对航运的影响也日益显著，特别是电商订舱平台的开发使广大客户受益的同时，大大推了进传统航运业向现代航运业转型.本文围绕即期客户和合同客户这两大客户群建立舱位优化分配模型，代入已知的各航段的运费率和舱位需求，首先求出传统环境下两艘班轮

分别为普通客户预留的舱位数以及可以接受的合同客户的舱位数，再求出航运电商环境下不同σe值所对应的舱位分配结果.根据最后的优化结果对航运电商平台与传统平台总收益进行对比，在航运电商环境下计算所得的总收益大于传统环境下的总收益，并远远大于只考虑合同客户的总收益，显示出该优化模型的有效性和电商平台的优越性；通过对航运电商平台舱位分配的分析可知，随着σe值的下降，班轮总收益呈上升趋势，同时电商客户增加，合同客户相应减少.从中可以看出电商平台下的舱位分配趋势使预测精度大大提高，预留的舱位数与实际到达的客户需求出入很小；电商客户在航运电商环境下会得到大力发展，合同客户数相反会得到抑制以致逐渐下降.

本文只研究航运电商环境下单一固定航线上的两种客户群.今后可以进一步研究多式联运，探讨多班轮与多航线之间的相互作用与影响，对电商的概念和对象可以进一步拓展，并考虑客户群和集装箱的种类或一些特定情况下的集装箱舱位分配问题.

参考文献：

[1] TING S C， TZENG G H. Fuzzy muliobjective programming approach to allocating containership slots for liner shipping revenue management[C]//Austria， Mikulas Luptacik， Rudolf Vetschera. Semmering： the 16th International Conference on MCDM， 2002： 116.

[2] HA D. Capacity management for the maritime industry （shipping，itineraries）[D]. Knoxville， USA： University of Tennessee， 1994.

[3] MARAGOS S A. Yield management for the maritime industry （shipping， itineraries）[D]. Cambridge， USA： Massachusetts Institute of Technology， 1994.

[4] SPYRIDON A M. Yield management for the maritime industry[D]. Cambridge， USA： Massachusetts Institute of Technology， 1994.

[5] ZURHEIDE S， FISCHER K. A revenue management slot allocation model for liner shipping networks[J]. Maritime Economics & Logistics， 2012， 14（3）： 334361.

[6] FENG CM.，CHANG CH. Optimal slot allocation with empty container reposition problem for Asia ocean carriers[J]. International Journal of Shipping and Transport Logistics， 2010， 2（1）： 2243.

[7] 卜祥智， 陈荣秋， 赵泉午. 考虑长期运力合同的班轮收益管理运输路径优化模型[J]. 中国管理科学， 2007， 15（6）： 3945.

[8] 杨华龙， 刘迪， 夏秋. 集装箱班轮多港挂靠循环航次舱位分配[J]. 重庆交通大学学报（自然科学版）， 2013， 31（6）： 12481251.

[9] 杨华龙， 夏秋， 刘迪. 基于市场细分的集装箱班轮运输舱位分配[J]. 中国航海， 2013， 36（1）： 132135， 142.

[10] 施欣. 集装箱海运空箱调运优化分析[J]. 系统工程理论与实践， 2003， 23（4）： 7076， 89.

[11] 陈继红. 集装箱班轮联营系统舱位租赁与分配决策优化模型[J]. 数学的实践与认识， 2011， 41（17）： 4855.

[12] 王琳， 全雄文. 集装箱班轮远期舱位分配博弈研究[J]. 物流技术， 2009， 28（4）： 5760.

[13] 李冰州， 陈旭， 武振业. 集装箱海运二维收益管理能力分配随机模型[J]. 系统管理学报， 2007， 16（4）： 447453.