物流系统优化问题研究方法概述

任　晔　顾　彬　李玉凯

摘要：结合物流系统的特点，分析了物流系统中存在的优化问题，并针对一些关键技术问题对近年来国内外有关文献进行梳理和研究。文章首先综述了物流系统中四类组合优化问题以及此类问题的传统确定性算法及智能优化算法，同时分析这些方法在处理不同的问题时各自的优缺点。最后对物流系统优化问题的研究方法及研究方向做了分析和展望。

关键词：物流系统优化；智能优化算法；组合优化

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

Abstract: In this paper, combining the characteristics of the logistics system, the research methods of the existing logistics system optimization are discussed, and for some of the key technical problems the literatures in recent years at home and abroad are given. Firstly, four types of typical combination optimization problems and some effective corresponding solutions such as traditionally affirmative methods and intelligent optimization algorithms are discussed, meanwhile, the advantages and disadvantages of each methods are pointed out. Finally, the future research direction and methods of logistics systematic optimization are given.

Key words: logistics systematic optimization; intelligent optimization algorithms; combination optimization

0引言

物流系统优化是实现物流管理目标、体现物流管理效率与效益的必要过程和手段。目前，物流系统优化主要有运筹学方法、智能优化方法和模拟仿真法三种方法。运筹学优化方法一般是建立在一个物流系统的数学模型基础之上的，智能优化方法为复杂物流管理决策问题提供了重要的可行性解决方案。系统仿真是根据被研究的系统模型，利用计算机进行实验研究的方法，是分析、研究复杂物流系统的重要工具。

本文对近年来国内外有关物流系统优化问题的解决方法的文献进行了梳理和研究，并对各种方法进行了比较，分析了各类方法在不同应用范围内的优势与不足。

1物流系统优化中四类子问题研究方法概述

目前物流系统优化方法主要是运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统的数量关系，以便求得最优决策。但由于物流系统庞大而复杂，建立整个系统的优化模型一般比较困难，而且用计算机求解大型优化问题的时间和费用太大，因此优化模型常用于物流系统的局部优化，并结合其他方法求得物流系统的次优解。如车辆路径问题（VRP）、旅行商问题（TSP）、配送中心选址问题、布局优化等问题是几种著名的物流系统优化问题。这些问题都是离散的组合优化问题，且都具有NP难题性质。本文将针对这四类问题对物流系统优化方法进行整理归纳。

1.1车辆路径问题

车辆路径问题（vehicle routing problem，VRP）由Danting和Rasmer在20世纪50年代末首先提出。该问题可定义为：运输车辆从一个或多个设施到多个地理上分散的客户点，优化设计一套货物流动的运输路线，同时要满足一系列的约束条件。该问题的前提条件是设施位置、客户点位置和道路情况已知，由此确定一套车辆运输路线，以满足目标函数（通常，VRP的目标函数是总费用最小）。

对VRP（车辆路径优化问题）的求解算法可分为精确算法和启发式算法两种。其中精确算法包括分枝定界算法、动态规划和整数规划。VRP的启发式算法多是来源于对TSP问题的求解算法。比如局部优先算法、插值法等可以不用修改地用于一些VRP。求解有时间窗车辆路径问题（VRPTW）的常用算法有禁忌搜索算法（TS）、模拟退火算法（SA）、遗传算法（GA）、蚁群算法（ACA）、粒子群优化算法（PSO）、免疫算法及节约算法等。

（1）动态规划法DM（Dynamic Programming，DM）是美国数学家Bellman R E等人在20世纪50年代初在研究多阶段决策过程的优化问题时提出的，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

（2）分枝限界法LC（Branch and Bound Method，LC）是由达金R.J和兰德一多伊格在20世纪60年代初提出的[4]。为了避免盲目搜索，人们提出了改进的分枝限界方法一LC分枝限界法。该方法的基本思想是：根据智能化的判定函数Ĉ(·)，只产生解的部分状态空间树，从而加速搜索过程，即通过计算小部分可行解即可以找到最优解。

（3）禁忌搜索法（TS）属于一种人工智能型（AI）的局部搜寻方法。是对局部领域搜索的一种扩展，是一种全局逐步寻优算法。TS算法通过引入一个灵活的存储结构和相应的禁忌表来避免重复搜索，并通过藐视准则赦免一些被禁忌的优良状态。TS最重要的思想是标记对应已搜索到的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象，从而保证对不同的有效搜索途径的探索，最终实现全局优化。TS对初始解的依赖性较强，好的初始解有助于搜索很快地达到最优解，而较坏的初始解使搜索很难或不能够达到最优解。迭代搜索过程是串行的，仅是单一状态的移动，而非并行搜索，在TS中集中性搜索和多样性搜索是它的两个重要策略。其中多样性搜索尤为重要，通常的算法都是使用基于频率记忆或改变其参数来实现多样性搜索策略。在问题规模较大时，单纯应用频率记忆或改变参数来实现多样性搜索往往得不到理想的效果。Willard首先将此算法用来求解VRP，Laporte用禁忌搜索提高了求解VRP问题的精度[2]。西南交通大学的袁庆达等设计考虑时间窗和不同车辆类型的禁忌算法[3]。

（4）模拟退火算法（SA）又称模拟冷却法、概率爬山法等，于1983年由Kirpatrick提出的另一种启发式的、随机优化算法。SA是基于迭代求解策略的一种随机寻优算法，源于对固体退火过程的模拟，采用Metropolis接受准则，并用一组称为冷却进度表的参数来控制算法的进程，使算法在多项式时间内给出一个近似最优解。从理论上讲，它是一个全局最优算法。模拟退火算法的基本思想由一个初始的解出发，不断重复产生迭代解，逐步判定、舍弃，最终取得满意解的过程。模拟退火算法具有收敛速度快，全局搜索的特点，不但可以往好的方向发展，也可以往差的方向发展，从而使算法跳出局部最优解，达到全局最优解。Osman提出模拟退火方法主要适合解决组合优化问题[4]，但此方法一般与其他算法结合使用。

（5）遗传算法（GA）具有求解组合优化问题的良好特性。Holland首先采用遗传算法（GA）编码解决VRP问题。GA是一种比较通用的优化算法，编码技术和遗传操作比较简单，主要操作有选择、交叉和变异。以n个城市的一种排列作为一条染色体，随机构造若干条染色体构成初始种群；然后根据适应度进行优胜劣汰的选择，一次繁殖由两个双亲产生一个子代；根据一定的交叉算子和变异算子进行交叉和变异。以一定的迭代次数或某个到达条件作为算法终止的条件。GA的优点是将问题参数编码成染色体后进行优化，而不针对参数本身，从而不受函数约束条件的限制；搜索过程从问题解的一个集合开始，而不是单个个体，具有隐含并行搜索特性，可大大减少陷入局部最小的可能。GA的主要缺点是对于结构复杂的组合优化问题，搜索空间大，搜索时间比较长，往往会出现早熟收敛的情况；对初始种群很敏感，初始种群的选择常常直接影响解的质量和算法效率。国内姜大立等构造了车辆路径问题的染色体表达，并对染色体进行可行化映射，建立此问题的遗传算法[5]。

（6）蚁群算法（Ant Colony System）是一种全局启发式算法，它是在对自然界中真实蚁群的集体行为的研究基础上，由意大利学者Dorigo等人首先提出的。目前求解效率最高的最大最小蚁群算法（MMAS）是德国学者T．Stuetzle和H.Hoos针对蚁群算法容易出现过早的停滞现象而提出的蚁群改进算法[6]。该算法的优点是：它是一种自适应、自组织、本质上并行的方法，而且是一种正向反馈的方法，可以促使整个系统向最优解进化，而且参数少、易于调整，易于移植到其他组合优化问题。但是，它同样存在收敛慢、易于陷入局部最优的缺点。张翠军等人针对VRPTW问题，设计了一种混合蚁群算法，通过在蚁群算法中引入interchange变异算子，增强了算法的局部搜索能力，获得了取长补短的效果[7]。

（7）微粒群优化算法（Partic1e Swarm Optimization，PSO）是在模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群体智能的演化计算技术。该算法属于求解全局最优化的群体智能算法，具有并行处理、鲁棒性好等特点，计算效率比传统随机方法高。自提出以来，已得到了学术界的高度关注，在许多领域得到了非常成功的应用，如神经网络训练、预测控制、多目标优化等。李军军等人尝试用此算法解决路径优化问题经验证具有可行性[8]。

可以分析，这些算法为求解VRP问题提供了方便，但也存在一些问题。如遗传算法（GA）及模拟退火算法（SA）是人工智能中用于解决组合优化问题的经典算法，但是，SA在全局搜索能力方面不足，GA在局部搜索能力方面不足。可见传统的配送线路优化方法都在不同方面上遇到各种问题。因此，现在多数使用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuk提出了用遗传算法进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。Ben和Van Hentenryck用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法将运输费用降到最低[9]，黄樟灿等人提出一种有时间窗车辆路径问题的基于模拟退火算法（SA）和大规模邻域搜索（LNS）的混合算法[10]，这些都可以证明是收敛速度快，收敛性好的混合智能算法。

1.2旅行商问题（TSP）

旅行商问题描述为：给定n个城市和两两城市之间的距离，求一条访问各城市一次且仅一次的最短路线。TSP（Travelling Salesman Problem）问题是一个典型的组合优化问题，且是一个NP难题。

对于TSP问题（旅行商问题）的研究方法主要有精确算法和智能优化方法。精确算法主要包括分枝定界法、动态规划法等；智能优化算法则主要包括禁忌搜索法、模拟退火算法、蚁群算法、遗传算法、郭涛算法、人工神经网络算法、r-opt算法、LK（Lin Kernighan，LK）算法、人工免疫AIS（Artificial Immune System）算法和粒子群优化PSO（Particle Swarm Optimization，PS0）算法[11-12]等。

贺一等设计一种基于Matlab实现的禁忌搜索算法，用以求解组合优化难题中的典型代表旅行商问题[13]。所得结果都能达到或优于公布的最优解，与传统的Hopfield神经网络求解TSP相比，禁忌搜索算法具有强健、快速和高效的特点。

郑立平等通过混合使用多种杂交算子，提出了一种求解旅行商问题的新型遗传算法，并给出实验验证[14]。

随着遗传算法的发展，遗传算法广泛地与其他算法相结合，产生许多混合遗传算法。王俊海将Memetic算法与遗传算法结合起来，提出一种基于Memetic算法的高效遗传算

法[15]，魏平等针对TSP问题的特点用混合遗传算法求解，设计了贪婪子路交叉算子，在选择算子设计中引人稳定状态选择机制[16]。任春玉设计了新的基于模拟退火机制的混合遗传算法。为了避免陷入局部优化，提出使用混合遗传算法，即应用模拟退火算法的Boltzmann生存方法，根据个体适应性的变异值Δ和概率值exp-ΔfT，来保持个体的多样性，阻止提前收敛，用顺序交叉算子和部分路径翻转变异算子来提高算法的收敛速度，较好地解决了群体的多样性和收敛速度的矛盾。算法分析和测试表明，该改进算法是有效的[17]。

虽然，遗传算法是求解TSP问题效率相当高的一种算法，但也有其局限性。即它的搜索过程是鲁棒的，因而，区域搜索能力不够好。而模拟退火算法在鲁棒的区域搜索过程可以避免区域优化过程中迷失。但是它们不适应总体解析空间寻找优化解法。许多研究表明将GA与局部启发式算法相结合可以有效提高求解大型TSP问题的质量。到目前为止解决TSP问题的最好方法为混合启发式算法，即将一些启发式算法与局部搜索结合。

1.3物流配送中心选址问题描述

配送中心选址问题描述：给定某一地区所有需求点（用户）的地址集合，要求从中选出一定数目的地址建立配送中心，从而建立一系列的配送区域，实现各个需求点的配送，使得在选出点建立的配送中心与各个需求点所建立的配送系统总配送费用最小。其目的在于加快货物流动速度并避免不必要的配送成本。

物流配送中心的选址决策对于整个物流系统运作和客户满意情况有着重要的影响。文献[18]对国内外有关物流配送中心选址方法文献进行研究，指出目前选址方法主要有定性和定量的两种方法。定性方法有专家打分法、Delphi法等，定量方法有重心法、P中值法、数学规划方法、多准则决策方法、解决NP hard问题（多项式复杂程度的非确定性问题）的仿真法及各种启发式算法如遗传算法、人工神经网络、模拟退火算法等。文章对比分析了数学规划方法、多准则决策、启发式算法、仿真方法在配送中心选址中的应用。

研究发现数学规划方法、多属性决策方法、启发式算法、仿真方法各自有自己的优缺点和一定的适用范围，开发各种各样的混合优化算法和模型是未来研究的一种趋势。任春玉（2006）提出了定量化的模拟退火遗传算法与层次分析法相结合来确定配送中心地址的方法[19]。该方法确保总体中个体多样性以及防止遗传算法的提前收敛，运用层次分析法确定物流配送中心选址评价指标权重，并与专家评分相结合进行了综合评价。由此看出，由于选址问题本身具有的动态性、复杂性、不确定性等特性，通过利用一种算法的优点同时结合其它算法避免该算法的不足是进一步解决配送中心选址问题的必须途径。

1.4布局优化问题

布局优化问题广泛地存在于人们的日常生活和现代工程设计中，如物流园区的设施布局，空间管道布局，船舶管路优化布局等，布局优化问题是典型的组合优化问题，具有NP完备性。布局分为二维布局和三维布局，它们一般要求待布物之间、待布物与容器之间不干涉，并尽量提高空间利用率，此类问题为无性能约束的布局问题。还有一类问题除以上基本要求外，还需考虑其它的性能约束，惯性、平衡性、稳定性等，称之为带性能约束布局问题，简称约束布局问题。相比之下，后者较之前者更复杂，更难于求解。

自20世纪70年代以来，国内外不少学者对布局设计问题进行了研究，并取得了一定的成果。但至今，仍然没有形成成熟的理论和理想的方法，布局优化仍然是一个亟待解决的智能问题。解决布局优化问题有基于MILP（混合整数线性规划）模型的布局优化方法，最具代表性的方法是理查德缪瑟提出的SLP（Systematic Layout Planning）法[20]。Braglia提出了在产品产量随机变化情况下，以最小化总物流量的均值为优化目标进行设施布局。然而目前还没找到一个能解决布局优化问题的通用方法，因为影响布局的限制性因素过多，其数学模型形式复杂、维数大，这就使得依赖于特殊数学形式的方法不可行。近年来遗传算法（Genetic A1gorithm）作为一种新的全局优化搜索算法，以其简单通用和鲁棒性强的特点，被广泛而成功地应用于布局优化问题并取得了许多成功的案例。林琳等人提出了基于遗传算法的交互式布局方

法[21]。李军军等人尝试用粒子群算法来解决布局优化问题，经仿真试验证明该方法具备可行性和有效性[8]。

2未来研究方向

文章全面回顾了物流系统优化问题中的四类NP-hard问题。整理归纳了这类组合优化问题的研究历史和研究现状，展望未来的研究方向，从技术难点和攻克问题来看可做以下概括：

（1）优化问题的数学模型建立。针对要解决的物流系统优化问题进行分析，运用解析的方法（包含数学规划）分别建立相应的数学理论模型（如定义、目标函数、约束条件）及其变形模型。更重要的是，物流系统优化是一个全局概念，可在前期研究工作中将局部优化问题加以整合与扩展，从而实现更贴近现实的研究。国内外已有学者做了这方面的工作并取得了可喜的成果[22-25]。

（2）智能优化算法的选择。可以分析看出由于以TSP问题为代表的组合优化问题均属于NP-hard问题，运用常规优化方法难以进行求解，可以通过对智能算法中的参数进行数值模拟计算，找出较好的参数搭配，分析各种算法对解的质量影响，并对标准测试数据进行计算结果测试。同时验证建立的数学模型以及进行测算对比分析，通过计算机编程，在可接受的计算时间内得到满足一定精度的相对最优解，最终找出解该类问题有效的智能算法。

（3）智能优化算法的组合应用。SA、GA和TS等随机优化算法，在全局优化性能方面有所改善，但很难确定合适的算法参数，且不良参数会导致收敛速度慢或早熟等缺点。许多学者通过利用一种算法的优点同时通过结合其它算法避免该算法的不足，出现了各种各样的混合优化算法。例如，把遗传算法和模拟退火算法结合起来的模拟退火遗传混合优化，人工免疫遗传混合优化以及免疫模拟退火算法。除此以外还有把蚁群算法和遗传算法相结合的算法，启发式算法和模拟退火算法结合的混合启发式算法，遗传算法与禁忌搜索相结合的算法，及人工神经网络与模拟退火算法相结合的算法，等等[26-29]。由此可见，充分利用各种算法的优点，协同工作，取长补短，也是一个很有希望的研究方向。而这些混合智能优化算法在物流系统优化上必将发挥更大的作用。

3结论

目前，物流系统优化已成为当代物流业快速发展的必然趋势，由此，建立完善、切合实际的数学模型并实现最优最快解决问题已成为物流系统工程发展的客观需求；不断改进和创新现代智能优化算法，已成为解决物流系统优化的新的解决途径。总之，物流系统优化问题的研究前景值得期待。

参考文献：

[1] 胡祥培，杨德礼. 智能运筹学与动态系统实时优化控制[C] // 经济管理与社会科学前沿研究——2000年中国博士后学术大会经济管理与人文社会分会暨全国博士后第四届经济学管理学学术会议论文集. 北京：中国金融出版社，2000.

[2] Gilbert Laporte. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithm[J]. European Journal of Operational Research, 1992,59:345-358.

[3] 袁庆达，闫昱，周再玲. Tabu Search算法在优化配送路线问题中的应用[J]. 计算机工程，2001,27(11):86-89.

[4]Osman I H. Meta-strategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routine Problem[J]. Operations Research, 1993,41:77-86.

[5] 姜大立，杨西龙，杜文,等. 车辆路径问题的遗传算法研究[J]. 系统工程理论与实践，1999,l9(6):40-45.

[6]Stutzle T, Hoos H H. The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem[C] // Proc. of the IEEE International Conference on Evolutionary Computation. Indianapolis: [s.n.], 1997:309-314.

[7] 张翠军，张敬敏，王占锋. 基于车辆路径问题的蚁群遗传融合优化算法[J]. 计算机工程与应用，2008,44(4):233.

[8] 李军军，王锡淮，黄有方,等. 微粒群算法在现代物流系统优化中的应用[J]. 物流技术，2006(4):33-35.

[9]Bent R. P Van Hentenryck. A Two-stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows[R]. Brown University, Technical Report: CS-1-06, 2001:1-30.

[10] 黄樟灿，蒋文霞，李书淦. 有时间窗车辆路径问题的混合算法[J]. 武汉理工大学学报：信息与管理工程版，2008,30(1):15.

[11]Lin S, Kernighan B W. An Effective Heuristic Algorithm for the Traveling Salesman Problem[J]. Operational Research, 1973,21(2):486-515.

[12]Hunt J, Cooke D. Learning Using an Artificial Immune System[J]. Journal of Network and Computer Applications, 1996,19(2):189-212.

[13] 贺一，刘光远. 禁忌搜索算法求解旅行商问题研究[J]. 西南师范大学学报，2002,27(3):341-345.

[14] 郑立平，郝忠孝. 基于混合杂交的遗传算法求解旅行商问题[J]. 计算机工程，2005,31(20):168-172.

[15] 王俊海. TSP问题的一种高效Memetic算法[J]. 交通与计算机，2002,20(1):14-17.

[16] 魏平，熊伟清. 求解TSP问题的一种混合遗传算法[J]. 计算机工程与应用，2005,31(12):70-73.

[17] 任春玉. 基于混合遗传算法的TSP问题优化研究[J]. 哈尔滨商业大学学报：自然科学版，2007,23(5):552-554.

[18] 李智桦，庄伯超，曾敏刚,等. 物流配送中心选址方法研究综述[J]. 商业时代，2007(17):20-21.

[19] 任春玉，王晓博. 基于模拟退火遗传算法和AHP的选址研究[J]. 哈尔滨商业大学学报：自然科学版，2006,22(1):58-61.

[20] 李庆庚. SLP在农产品物流园区布局中的应用研究[D]. 上海：上海同济大学（硕士学位论文），2006.

[21] 林琳，何涛，李士才,等. 基于进化策略的空间管道布局优化方法研究[J]. 计算机应用，2007(27):162-164.

[22]Dhaenens-Flipo C. Spatial decomposition for a multi

-facility production and distribution problem[J]. International Journal of Production Economics, 2000,64(1/2/3):177-186.

[23]Melkote S, Daskin M S. An integrated model of facility location and transportation network design[J]. Transportation Research Part A, 2001,35(6):515-538.

[24]Goetschalckx M, Vidal C J. Dogan K. Modeling and design of global logistics systems: a review of integrated strategic and tactical models and design algorithms[J]. European Journal of Operational Research, 2002,143(1):1-18.

[25]Hwang H S. Design of supply-chain logistics system considering service level[J]. Computers and Industrial Engineering, 2002,43(1/2):283-297.

[26]Wu T H, Low c, Bai J W. Heuristic solutions to multi

-depot location-routing problems[J]. Computers and Operations Research, 2002,29(10):1393-1415.

[27]Syam S S. A model and methodologies for the location problem with logistical components[J]. Computers and Operations Research, 2002,29(9):1173-1193.

[28]Amiri A. Designing a distribution network in a supply chain system[J]. European Journal of Operational Research, 2004,171(2):567-576.

[29]Gena M, Syarif A. Hybrid genetic algorithm for multi

-time period production/dis-tribution planning[J]. Computers and Industrial Engineering, 2005,48(4):799-809.