物流中心货物配送模式

1、单一物流中心货物配送模式之研究1一、前言市场的扩大以及竞争的激烈，管理系统在空间特性问题上处理能力不足的问题已慢慢浮现，管理者对于地理信息系统的需求也大幅提高。例如在货物运送方面，如能结合地理信息系统优异的空间展示、处理以及分析的功能，将能有效的克服空间阻隔，达到节省成本的目的。2一、前言物流配送在GIS实属于空间分析的问题，以往研究则较少考虑空间分布差异对配送产生的影响。故本研究将空间分析中群聚分析方法（Clustering Analysis ）引入车辆途程问题(VRP)模式当中，已改善以往VRP算法未加入空间考虑的问题。并尝试分析不同的空间分布型态（Pattern），对不同VRP求解模式的

2、影响。3二、物流业特性分析美国物流管理协会（CLM, Council of Logistics Management, 1995）之定义如下：举凡涉及物品、劳务以及相关信息自原料地至消费地间，如何有效率（efficient）及有效能（cost-effective）地加以储存（storage）与流动（flow），以因应顾客所需之规划、执行与管理程序，皆属之。 4二、物流业特性分析物流系统的演进，可分为主要的三个阶段：1.第一代物流系统：又称为原料物流或是实体供给系统 ，主要是属于物料之采购及移动过程。2.第二代物流系统：又称为销售物流或是实体分配系统，一般狭义的物流及意旨此系统，本研究所要探讨的

3、问题也正是属于实体分配中货物运输的范畴。3.第三代物流系统：又称为企业物流系统（Business Logistics System），就是将上述实体供给和实体分配的各项活动，合成一个整体，予以综合管理。5二、物流业特性分析而物流信息系统与一般信息系统不同的地方在于其对资料搜集的密集性，以及信息的详细性和动态性，和数学模式的应用上皆比一般信息系统来的高，数学模式的使用则是帮助决策的产生，例如线性规划、最短路径分析、系统仿真等，而这些特性在物流系统营运上所扮演的角色，主要是以最小的成本来处理订单以及配送的问题，以达到最佳的服务水平。6三、地理空间分析关于地表空间的特征，一般来说属于空间分析的范畴，

4、而对于地表空间型态（pattern）的描述，主要可分为几种指针，以点资料来说，有下列几种：频率(frequency )密度(density)几何中心(geometric center)离散(dispersion)排列(arrangement) Clustered (密集型),Scattered (扩散型), Random (随机型)7群聚分析而若要将空间中不同的点数据予以归纳分类，则必须要使用空间分析中的群聚分析技术（Cluster Analysis）。群聚型随机型8群聚分析方法1. UPGMA 利用接近值算数平均数2.WPGMA 加入了权重值的计算3. SLINK 利用最小接近值4. Cli

5、nk 利用最大接近值5. Wards minimum variance method E=(x1-Cmean1)2+(y1-Cmean1)2+.取MIN9群聚分析方法6.K-means algorithms(Macqueen,1967) 在一群需求(demand)点中找出k个供应(supply)中心的位置使得需求点至供应中心的总成本最低(邹明城 ，2000)7. K-medoid algorithmsg (Vinod,1969) 对于K-means法容易掉入去最佳解的问题加以修正。8.CLARANS (Ng and Han,1994)9.DBSCAN (Easter,1996) 以空间分布的密

6、度为考虑发展求解模式。10. GDBSCAN (SANDER et. al,1998) 10四、VRP求解分析陈文瑞（1990）曾提到： VRP是车辆在依序的服务地点做收货 (或，和)送货的服务，且必须依照指示依序通过这些服务地点，开始和结束在同一个出发点 (depot or domicile)。VRP问题的分类单一场站、多场站本研究属于单一场站11VRP 问题探讨本研究最主要的讨论是关于单一场站与多车辆路线问题之研究，在实务应用上通常都以单一物流中心，同时指派多部车辆，来达到时效性最高的顾客满意度。这样的问题被定义为：在一广大的区域散置分布N各节点或顾客，每个顾客有其特定的需求量，这些需求量

7、由某一个特定的中心站来提供，此中心站有多部车辆，每部车辆的装载量为已知，来求由配送中心到满足所有N各点的顾客需求的配送路线，并使配送成本达到最小。 12VRP问题求解模式(1)先分群再排路线(Cluster First-Route second)扫瞄法(Gillett and Miller,1974)-采用及坐标角度扫瞄分群。(2)先排路线再分群(Route First-cluster Second)(Bodin and Berman,1979)-分群结果受先前排列之路进影响。(3)节省法或插入法(Saving or Insertion)节省法(Clarke and Wright,1964)-

8、叫无弹性，无法视群聚状况调整13VRP问题求解模式(4)改善与交换(Improvement or exchange)K-optimal法(Lin and Kernighan,1965)(5)数学规划法(Mathematical Programming Approaches)(6)最佳解法(Exact Procedures)(7)人机互动法(Interactive Optimization)14VRP问题求解模式分析由于VRP属于非完全多项式(NP-Complete)问题，(5)数学规划法、(6)最佳解法两种方式求解复杂度随问题大小呈指数成长，近年来学者纷纷致力于启发式解法的开发。启发式解法基本

9、步骤（徐吉田，1993）1.指定K车辆（即路线）2.集结各需求点成一路线(启始解)3.路线改善重新排列路线中各需求点，以得较好的路线。将某路线的点移到另一路线15启发式解法基本概念目前学界研究VRP问题通常采用二阶段法；第一阶段初始解的产生，例如 (1)先分群再排路线、(2)先排路线再分群、(3)节省法或插入法第二阶段则为解的改善，例如(4)改善与交换本研究采用先分群后排路线的方法，但考虑以往相关研究较少将空间因子纳入考虑，故本研究引入空间分析中群聚分析（Clustering Analysis）的相关技术，来作为VRP的分群求解（启始解）模式。16五、研究架构VRP空间群聚求解模块配送以及物流

10、之空间数据库车辆及路线的指派物流业特性分析VRP求解模式分析地理空间分析GIS系统比较其他求解策略不同空间Pattern分析归纳结果17六、研究方法将空间分析中群聚分析模块应用于VRP初始解的求得，以离散/群聚之空间分析为基础，并以clustering 分析为核心改进方法，来改进及评量配货地一解求法。引入空间量度参数，以做为空间度量，来评定不同算法在不同空间度量上的优劣。18研究假设单一场站多部车辆道路的特性初期考虑对称性路网，日后研究在考虑实际路网配送点特性限制由一部车服务需求皆不超过一部车容量车辆的限制型态容量的限制单一车种，多部车辆行车距离的限制19研究假设时窗(Time Window)

11、的限制不考虑时窗限制客户区位特性固定已知的需求产品本身特性以数量考虑，视为一种商品20群聚分析方法本研究考虑工具的取得以及符合研究假设需求性，初步采用SPSS统计软件，利用其内建之Analyze 模块中的Classify 的功能，采用k-means Cluster 以及 Hierarchical Cluster 算法来做分群，另外分区域配送之TSP算法则采用最远内插法，利用VB撰写求解程序配合VRP标准例题做测试。21七、初步成果No.Problem NameNodesVehicle CapacitySourceCost and Fleet Data#1E-n51-k550160Christofieds & Eilon(1969)采用Christofieds & Eilon(1969)所提出的测试例题进行测试22k-means Cluster结果23Hierarchical Cluster结果24k-means Cluster 配送结果25Hierarchical Cluster配送结果26与过去研究之比较初步结果已知最佳解KC543HC 563521此结果为尚未进行改善解之初步结果，未来若配合良好都改善模