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

《基于物流配送路径的优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于物流配送路径的优化算法研究：目前，对物流配送车辆优化调度问题(VRP)还是一个研究热点，许多学者采用了各种优化方法来解决实际问题。该文综述了物流配送车辆调度问题的各种优化方法，对其发展历程、优缺点、适用性等都作了详细的说明，并对它们作以比较分析，从而找到最适合现实状况的优化方法。　　关键词：优化；物流配送；算法　　：TP312：A：1009-3044(2011)10-2297-02　　TheResearchonOptimumAlgorithmofLogisticsDistribution　　XUYan,LISheng-qin　　(CollegeofMathematicsan

2、dInformationScience,NorthalUniversity,Lanzhou730070,China)　　Abstract:Atpresent,logisticsvehicleroutingproblem(VRP)isfocusedonashot-question.LotsofscholarsadoptsvariousoptimumsupallkindsofmethodsofVRPandparticularlyexplainmeritanddisadvantages,evolutioncourseandapplicability,eachotherinordert

3、odiscoverbestofrealisticstatussoptimumizing;logisticsdistribution;algorithm　　物流(logistics)是指利用现代信息技术和设备，将物品从供应地向接收地准确的、及时的、安全的、保质保量的、门到门的合理化服务模式和先进的服务流程。物流是随商品生产的出现而出现，随商品生产的发展而发展，所以物流是一种古老的传统的经济活动。物流管理是指在社会再生产过程中，根据物质资料实体流动的规律，应用管理的基本原理和科学方法，对物流活动进行计划、组织、指挥、协调、控制和监督，使各项物流活动实现最佳的协调与配合，以降低物流成

4、本，提高物流效率和经济效益。现代物流管理是建立在系统论、信息论和控制论的基础上的。配送路径优化问是一个NP问题，只有在需求点和路段较少时才能求得精确解。随着信息技术的不断进步，企业运营节奏加快，物流配送路径的研究方法也随着进步，可以说问题由简单到复杂。优化方法有精确算.法、传统启发式算法、现代启发式算法这么几种。下文便分类介绍以下几种最优化算法。　　1物流配送路径优化问题的精确算法　　1）动态规划法。此算法(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。

5、在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。　　2）分枝定界法。该法是将原始问题分解，产生一组子问题。分支是将一组解分为几组子解，定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外，就将这一子组舍弃（剪枝）。分支定界法原为运筹学中求解整数规划（或混合整数规划）问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。　　3）切平面法。此方法与分枝定界法相

6、类似，它也是在整数规划与求解相对应的线性规划上，不断的增加新的约束，相区别是会加入一些特别的约束条件，然后切掉非整数规划中的可行解，获得最优解。　　2物流配送路径优化问题的传统启发式算法　　传统的启发式算法在求解过程中主要是从初始解出发，以搜索邻域的方式实现解的改进，并在较短的时间内获得一个可以接受的解。传统的启发式算法主要有以下4种：1）节约算法。此算法是将较短路径与原路径定义为节约值，然后将节约值从大到小进行排序，在节点的数量允许的情况下，依此将节点对应的顾客点插入到路径中，直到所有的顾客都被插入路径为止，从而获得可行解，不过解非最优。2）邻接算法。此算法是由数据结构中的邻

7、接表演变过来。邻接表是图的一种链式存储结构，对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。此算法的思想是从一个起始点出发，然后搜索路线中与之距离最近的点，然后在次以此方法不断搜索最近的点，从而进行路线的构造。这种方法可以保持原有路线的可行性，从而搜索着一条疑似最短的路线，节约路线成本。3）插入算法。此算法是又数据结构中的插入排序演变过来。它将邻接算法与节约算法有机的结合起来，先利用节约算法确定一条基本路线，然后根据邻接算法搜索客户节点