基于物流配送路径的优化算法研究

摘要：目前，对物流配送车辆优化调度问题(VRP)还是一个研究热点，许多学者采用了各种优化方法来解决实际问题。该文综述了物流配送车辆调度问题的各种优化方法，对其发展历程、优缺点、适用性等都作了详细的说明，并对它们作以比较分析，从而找到最适合现实状况的优化方法。

关键词：优化；物流配送；算法

中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)10-2297-02

The Research on Optimum Algorithm of Logistics Distribution

XU Yan, LI Sheng-qin

(College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China)

Abstract: At present, logistics vehicle routing problem(VRP) is focused on as hot-question. Lots of scholars adopts various optimum ways to solve actual question. This paper sums up all kinds of methods of VRP and particularly explain merit and disadvantages, evolution course and applicability, which compare and analyze them each other in order to discover best of realistic status s optimum ways.

Key words: optimizing; logistics distribution; algorithm

物流(logistics)是指利用现代信息技术和设备，将物品从供应地向接收地准确的、及时的、安全的、保质保量的、门到门的合理化服务模式和先进的服务流程。物流是随商品生产的出现而出现，随商品生产的发展而发展，所以物流是一种古老的传统的经济活动。物流管理是指在社会再生产过程中，根据物质资料实体流动的规律，应用管理的基本原理和科学方法，对物流活动进行计划、组织、指挥、协调、控制和监督，使各项物流活动实现最佳的协调与配合，以降低物流成本，提高物流效率和经济效益。现代物流管理是建立在系统论、信息论和控制论的基础上的。配送路径优化问是一个NP问题，只有在需求点和路段较少时才能求得精确解。随着信息技术的不断进步，企业运营节奏加快，物流配送路径的研究方法也随着进步，可以说问题由简单到复杂。优化方法有精确算.法、传统启发式算法、现代启发式算法这么几种。下文便分类介绍以下几种最优化算法。

1 物流配送路径优化问题的精确算法

1）动态规划法。此算法(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

2）分枝定界法。该法是将原始问题分解，产生一组子问题。分支是将一组解分为几组子解，定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外，就将这一子组舍弃（剪枝）。分支定界法原为运筹学中求解整数规划（或混合整数规划）问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。

3）切平面法。此方法与分枝定界法相类似，它也是在整数规划与求解相对应的线性规划上，不断的增加新的约束，相区别是会加入一些特别的约束条件，然后切掉非整数规划中的可行解，获得最优解。

2 物流配送路径优化问题的传统启发式算法

传统的启发式算法在求解过程中主要是从初始解出发，以搜索邻域的方式实现解的改进，并在较短的时间内获得一个可以接受的解。传统的启发式算法主要有以下4种：1）节约算法。此算法是将较短路径与原路径定义为节约值，然后将节约值从大到小进行排序，在节点的数量允许的情况下，依此将节点对应的顾客点插入到路径中，直到所有的顾客都被插入路径为止，从而获得可行解，不过解非最优。2）邻接算法。此算法是由数据结构中的邻接表演变过来。邻接表是图的一种链式存储结构，对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。此算法的思想是从一个起始点出发，然后搜索路线中与之距离最近的点，然后在次以此方法不断搜索最近的点，从而进行路线的构造。这种方法可以保持原有路线的可行性，从而搜索着一条疑似最短的路线，节约路线成本。3）插入算法。此算法是又数据结构中的插入排序演变过来。它将邻接算法与节约算法有机的结合起来，先利用节约算法确定一条基本路线，然后根据邻接算法搜索客户节点的位置，依次按距离将客户节点插入到原有路径中，最后形成新的配送路线。4）扫除算法。此算法是将邻接算法与插入算法相结合，它是先对车辆进行分组，然后确定不同的路线，在配送过程中以扫除的方式搜索未被分配的点，然后用插入算发对路线进行扩充，如果一次分组之后还存在未被分配的点，那么继续对路线进行构造，直到所有的点都被分配为止。

3 物流配送路径优化问题的现代启发式算法

与传统的启发式算法相比，现代启发式算法并不是每次在迭代中都延着目标值下降的方向进行搜索，它还允许在搜索中接受目标值上升甚至是不可行的解，现在启发式算法与传统启发式算法的一大区别就是它会在搜索过程中跳出局部邻域进行全局搜索。现代启发式算法有以下4种：1）禁忌搜索算法。此算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的。2）遗传算法。此算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的。遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的，容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。3）模拟退火算法。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。此算法是一种随机松弛技巧，它模拟了退火的过程，在搜索的初始阶段，算法跳向远点，随着时间的延伸或下降，跳跃幅度逐渐减小，最终转向局部搜索的下降方法。4）蚁群算法。蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。

4 各种优化算法的比较

以上各种优化算法在不同时期与情况下都有其优缺点，都有解决某些问题的能力，但随着发展的需要，对优化算法的要求也越来越高。下面对各种方法进行比较分析，通过表格的形式展示出各自的特点，如表1所示。

5 结束语

车辆路径问题由于在管理学和运筹学上非常重要而且求解有一定的难度，同时由于它具有很强的现实价值，可产生极其可观的经济效益，因而是理论界与企业界关注的一个极其具有魅力的优化问题。通过表格的分析比较，可以看出各种方法的优点和缺点，在不同的任务中可以挑选不同的优化算法，从而使物流效率达到最高。本文通过介绍各种优化算法来比较各类算法的优缺点，以便能在实际中解决各种复杂的物流路径优化问题，从而找到最好的优化方法。

参考文献：

[1] 孙学农,徐辉增.物流配送车辆调度问题方法综述[J].科技信息:学术研究,2007(12).

[2] 刘明广,李高扬.物流配送车辆优化调度模型及其求解策略[J].工业工程,2007(2).

[3] 方金城,张岐山.物流配送车辆路径问题(VRP)算法综述[J].沈阳工程学院学报:自然科学版,2006(4).

[4] 李贵春,刘冬梅.物流配送系统车辆的优化调度算法[J].天津工业大学学报,2006(3).

[5] 骆义.物流配送车辆调度优化研究[D].大连:大连海事大学,2003.