《配送网络地地研究地的综述.doc》由会员分享，可在线阅读，更多相关《配送网络地地研究地的综述.doc（6页珍藏版）》请在三一办公上搜索。
1、word配送网络研究综述我国物流理论研究起步较晚，20世纪70年代，物流的概念从日本引入我国，并且受到国外物流开展的影响很深。由于计划经济的限制，在接下来的20年，物流的开展也相当缓慢。当前关于物流的理解存在管理学派、技术学派、工程学派、流通学派等多种侧重。单讲配送角度的区别：管理、流通学派更侧重于从政策主导的全局考虑，追求运作合理化；技术、工程学派更倾向于将配送中心与运输系统结合，从技术角度考虑设施以与运输过程的合理化。物流在不同的角度，可以有不同的划分，如：宏观、微观物流；社会、企业物流；国际、国内物流；一般、特殊物流。假如从物流运作上分，有第三方物流、第四方物流，甚至有人提出第五方物流的
2、概念。但目前为止，第三方物流企业开展较为成熟，也比拟受社会认可。安德森咨询公司最早提出第四方物流的概念“一个调配和管理组织自身的与具有互补性的服务提供商的资源、能力与技术，来提供全面的供给来呢解决方案的供给链集成商。国外对于物流的研究，从微观角度出发的较多。从微观角度研究企业资源配置或者协调问题，如物流根底设施、市场竞争机制与配送运输等问题。研究中用到较多的方法为运筹学的规划论、系统仿真、启发式等方法。一、 配送路径问题的介绍我国物流本钱一直徘徊在20%左右，这中，运输、存储本钱分别占到物流本钱的57.1%、31.8%，而兴旺国家物流本钱占GDP比重应该根本稳定在10%左右。因此，了解、和设计
3、更为合理、算法复杂度低的运输、配送方案而达到降低运输本钱的目标，是非常有现实意义的。在物流网络研究的领域，主要集中在分销渠道和运输模式的选择，以与制造业原材料、半成品或成品在供给网络中的流动问题。无论是最短路径还是有约束的线性规划方法，都是解决运输、配送问题的经典方法。丘成桐教授曾经说过：“经典算法之所以经典，就在于其本身对问题解决铺就了最直接的道路。配送线路和布点问题是数学领域和管理应用的一个结合点，到目前为止最大的难题就是理论成果向应用的转换。物流网络配送运输问题中，Danting和Ramser在上世纪50年代年提出了车辆路径选择问题vehicle routing problem，VRP。
4、“TSP问题的求解算法问题属于典型的NP-Hard问题Non-deterministic Polynomial hard无确定解的多项式难题。目前倾向于承受NPC问题和NP-Hard问题不存在有效算法这一猜测。国内有不少研究是尝试使用遗传算法、蚁群算法等启发式算法来求取满意解。Frod和Fulk最早对物流网络中的流flow开始研究，并成为后来成为教材经典，成为节点网络中求最大流最小割的经典方法。此后不少算法被用来研究网络流问题。从拓扑角度分析网络流问题1、点与点间运输也成单元节点运输，表现了最短路径算法的思想。而后面集中模型的处理也都表现出了最根本的最短路思想：假设一个n节点m条弧的有向连通图
5、G(V,A)(V=v1,v2,vn, A= a1,a2,am )，权重矩阵C=Cij|1in, 1jm，找到一条从节点v1到vn的距离最短路径，G1nG，为所有连接两点的弧以与相应点构成的连通图，minL=(vi,vj)G1nCij.2、多点间运输多元节点运输，主要用于解决多个节点之间的送货、配货问题，一般为起始点和终止点不唯一的运输问题。3、单回路TSP问题(Traveling Salesman Problem)TSP问题是一个典型的NP-Hard问题，对于大规模的线路优化问题无法获得最优解，只能通过一些算法来获取满意解。对于小型问题，想要得到最优解的最简单方法为枚举法，但枚举法的跌代数为(
6、n-1)!次，当节点数到达一定规模以后，运算量将是无法承受的。Rosenkrantz和Stearns在1977年提出一种可以较为迅速得到解的算法最近邻点法。4、多回路运输这种运输问题在现实中更为普遍。VRPVehicle Routing Problem便是解决本问题的一个最根本的模型。Danting和Ramser在提出这个问题以后，立即引起了运筹学、数学、图论、物流、计算机等各学科研究者的重视，到目前为止它仍是一个NP-Hard问题。VRP问题的数学表达为：连通图G(V,A)(V=v1,v2,vn, A= a1,a2,am 为供给点的供给能力矩阵)，运输距离或本钱矩阵为C=Cij|i,jN,
7、1i,jn ，需求点的需求矩阵B= b1,b2,bn ，Xij为从ai到bj的发送量。目标函数：mini=1mj=1ncijxijs.t. j=1nxij=ai, i=1nxij=aj, Nm, xij0, i=1,2,m;j=1,2,n.但在实际问题中，还有面临更多更为复杂的约束条件。例如：每辆运输车完成任务须回到某一点；车辆的最大容量、最大载重；订单配送的时间窗；局部商品的运输特定规章制度等等。VRP问题时对实际运输过程所遇到问题的最为概括性的模型，按照不同的原如此，可以将其分类为多种子问题：按任务特质分类：纯装问题、纯卸问题，装卸混合问题；按任务性质分类：对弧服务CPP、对点服务TSP，
8、混合的车辆行驶路线问题；按装货的状况：单车任务，单车多任务问题；按车场数目：单车场、多车场问题；按车辆种类：单车型、多车型问题；车辆对车场所属：车辆开放问题，车辆封闭问题。实际工程实践中的布点以与线路问题，包含的配送节点可能是上万个，采用什么样的建模方法至关重要，因为这直接影响到计算机的运算时间。一个研究实例中，在烟草集团的配送节点中，对一万多个点，采用节约里程算法进展线路的仿真运算，使用了十天；另外吧整个城市进展分区，也花费了十天，而且这本身又违背了线路在城市内随机选择的前提。二、求最短路径的几种经典算法：1、Dijkstra算法该算法可以求出图中一个顶点到其他各顶顶啊的最短路径的长度，得出
9、一条最短路径。把节点集合V分成两组：1S：已求出最短路径的顶点的集合2V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序参加到S中，保证：1从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度；2每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。2、Floyd算法该算法的目的是计算全部顶点间最短路径。主要思想是从任意两个顶点vi到vj的距离的带权邻接矩阵开始，
10、每次插入一个顶点vk，然后将vi到vj间的最短路径与vk作为中间点时增加的路径的距离比拟，取较小值更新距离矩阵。然后迭代，最终得到Dn，即为所有丁点之间的最短距离讯息。这个方法还适合用在物流中心选址问题的解决。3、节约里程法该算法为Clarke和Wright于1964年提出，用来解决运输车辆数目不确定的VRP问题。其核心思想是将运输问题中存在的两个或多个回路进展合并，以使得运输的总里程改变。假如变化后的总里程减少，如此该减小值为节约里程。4、TS算法Tabu Search Algorithm由Hansen的最速上升缓和下降启发式算法Steepest Ascent Mildest Descent
11、 Algorithm的思想，Fred Clover提出了一种求解组合优化问题的启发式算法。TS算法为广义的局部邻域搜索方法，在每一步搜索中求得局部邻域中的最优解，可能该最优解不如当前解，但TS算法还是将邻域中的最优解作为当前解继续搜索。为防止搜索过程的循环，所有局部最优解被存放在一个Tabu列表中，而每一步向Tabu的移动是不允许的。Tabu列表定长，假如增加一个解进入列表，将替代Tabu中的最劣解。以上经典算法在理论上均是可行的，也均发挥着较为重要的作用。一旦考虑应用的实际工程中，算法本身就要增加更多实际客观条件所带来的约束，并且还需要有较快的运算或收敛速度。三、物流网络的其他研究：对于物流
12、网络、设计，以与网络中的选址、运输问题，有一些新的方法与尝试。Pedro M. Reyes 利用博弈论中的夏普里值(Shapleyvalue)的方法来解决物流网络中的运输问题，以维持网络状况的稳定; Nakatsu 对物流网络中的三种常用的结点( 工厂、仓库和消费市场) 所组成的网络结构展开研究, 利用基于模型的推理方法和启发式搜索方法来解决仓库设施的定位问题和物流网络结构设计中的聚集或分散决策; J. Neto 等通过对影响物流网络中的环境、本钱的各种活动, 如运输、制造、产品消费、测试和完毕使用等的研究, 基于多目标规划提出了物流网络的优化设计框架, 并讨论了其在可持续物流网络设计中的应用
13、。京都大学Eiichi Taniguchi于1999年最早提出城市物流概念，借助排队论和非线性理论研究城市中的物流中心选址和规划问题，并阐述了城市交通网络中物流中心等公共节点对于交通网络的影响。Jorg Ackermann 等如此提出了物流系统网络结构的三层模型。多层物流网络的定义，包括上层的制造商、中间层的分销商和底层的消费者，而物流网络中的流被视为从自上而下的穿透三层的，有容量吸纳之的商品流、信息流、资金流。四、配送网络与交通网络研究的结合过去对于物流网络与配送网络的研究，均为拓扑意义上的节点与边组成的网络，各条“道路所具有的特性，最多可以由边上的加权值来度量。对于红绿灯，往往也只能采用时间窗作为约束；对于道路、节点的局部拥堵，只能改变其所在或者连接的弧上的权值，并没有与交通领域的研究结合。6 / 6
