单一物流中心货物配送模式之研究课程cfg.pptx

1 1单一物流中心货物配送模式之研究单一物流中心货物配送模式之研究2一、前言n n市场的扩大以及竞争的激烈，管理系统在市场的扩大以及竞争的激烈，管理系统在空间空间特性特性问题上处理能力不足的问题已慢慢浮现，问题上处理能力不足的问题已慢慢浮现，管理者对于地理信息系统的需求也大幅提高。管理者对于地理信息系统的需求也大幅提高。n n例如在货物运送方面，如能结合地理信息系统例如在货物运送方面，如能结合地理信息系统优异的空间展示、处理以及分析的功能，将能优异的空间展示、处理以及分析的功能，将能有效的克服空间阻隔，达到有效的克服空间阻隔，达到节省成本节省成本的目的。的目的。单一物流中心货物配送模式之研究3一、前言n n物流配送在物流配送在GISGIS实属于空间分析的问题，以往实属于空间分析的问题，以往研究则较少考虑研究则较少考虑空间分布差异空间分布差异对配送产生的影对配送产生的影响。故本研究将空间分析中响。故本研究将空间分析中群聚分析方法群聚分析方法（ClusteringAnalysisClusteringAnalysis）引入车辆途程问题引入车辆途程问题(VRP)VRP)模式当中，已改善以往模式当中，已改善以往VRPVRP算法未加入算法未加入空间考虑的问题。并尝试分析不同的空间考虑的问题。并尝试分析不同的空间分布空间分布型态型态（PatternPattern），），对不同对不同VRPVRP求解模式的影响。求解模式的影响。单一物流中心货物配送模式之研究4二、物流业特性分析n n美美国国物物流流管管理理协协会会（CLM,CLM,CouncilCouncilofofLogisticsLogisticsManagement,1995Management,1995）之定义如下：之定义如下：举凡涉及物品、劳务以及相关信息自原料地至举凡涉及物品、劳务以及相关信息自原料地至消费地间，如何有效率（消费地间，如何有效率（efficientefficient）及有效能及有效能（cost-effectivecost-effective）地加以储存（地加以储存（storagestorage）与流动与流动（flowflow），），以因应顾客所需之规划、执行与管理以因应顾客所需之规划、执行与管理程序，皆属之。程序，皆属之。单一物流中心货物配送模式之研究5二、物流业特性分析n n物流系统的演进，可分为主要的三个阶段：物流系统的演进，可分为主要的三个阶段：1.1.第一代物流系统：第一代物流系统：又又称称为为原原料料物物流流或或是是实实体体供供给给系系统统，主主要要是是属属于于物物料料之采购及移动过程。之采购及移动过程。2.2.第二代物流系统：第二代物流系统：又又称称为为销销售售物物流流或或是是实实体体分分配配系系统统，一一般般狭狭义义的的物物流流及及意意旨旨此此系系统统，本本研研究究所所要要探探讨讨的的问问题题也也正正是是属属于于实实体分配中货物运输的范畴。体分配中货物运输的范畴。3.3.第三代物流系统：第三代物流系统：又又称称为为企企业业物物流流系系统统（BusinessBusinessLogisticsLogisticsSystemSystem），就就是是将将上上述述实实体体供供给给和和实实体体分分配配的的各各项项活活动动，合合成成一一个整体，予以综合管理。个整体，予以综合管理。单一物流中心货物配送模式之研究6二、物流业特性分析n n而物流信息系统与一般信息系统不同的地方在而物流信息系统与一般信息系统不同的地方在于其对于其对资料搜集的密集性资料搜集的密集性，以及，以及信息的详细性信息的详细性和动态性和动态性，和数学模式的应用和数学模式的应用上皆比一般信息上皆比一般信息系统来的高，数学模式的使用则是帮助决策的系统来的高，数学模式的使用则是帮助决策的产生，例如线性规划、最短路径分析、系统仿产生，例如线性规划、最短路径分析、系统仿真等，而这些特性在物流系统营运上所扮演的真等，而这些特性在物流系统营运上所扮演的角色，主要是以最小的成本来处理订单以及配角色，主要是以最小的成本来处理订单以及配送的问题，以达到最佳的服务水平。送的问题，以达到最佳的服务水平。单一物流中心货物配送模式之研究7三、地理空间分析n n关关于于地地表表空空间间的的特特征征，一一般般来来说说属属于于空空间间分分析析的的范范畴畴，而而对对于于地地表表空空间间型型态态（patternpattern）的的描描述述，主主要要可可分分为为几几种种指指针针，以以点点资资料料来来说说，有有下下列列几种：几种：v 频率频率(frequency)frequency)v 密度密度(density)density)v 几何中心几何中心(geometriccenter)geometriccenter)v 离散离散(dispersion)dispersion)v 排列排列(arrangement)arrangement)Clustered(Clustered(密集型密集型),),Scattered(Scattered(扩散型扩散型),),Random(Random(随机随机型型)单一物流中心货物配送模式之研究8群聚分析n n而若要将空间中不同的点数据予以归纳分类，则而若要将空间中不同的点数据予以归纳分类，则必须要使用空间分析中的必须要使用空间分析中的群聚分析技术群聚分析技术（ClusterClusterAnalysisAnalysis）。）。群聚型随机型单一物流中心货物配送模式之研究9群聚分析方法1.UPGMA利用接近值算数平均数2.WPGMA加入了权重值的计算3.SLINK利用最小接近值4.Clink利用最大接近值5.WardsminimumvariancemethodE=(x1-Cmean1)2+(y1-Cmean1)2+.取MIN单一物流中心货物配送模式之研究10群聚分析方法6.K-meansalgorithms(Macqueen,1967)6.K-meansalgorithms(Macqueen,1967)在一群需求在一群需求(demand)demand)点中找出点中找出k k个供应个供应(supply)supply)中心的位中心的位置置 使得需求点至供应中心的总成本最低使得需求点至供应中心的总成本最低(邹明城邹明城，2000)2000)7.7.K-medoidalgorithmsg(Vinod,1969)K-medoidalgorithmsg(Vinod,1969)对于对于K-meansK-means法容易掉入去最佳解的问题加以修正。法容易掉入去最佳解的问题加以修正。8.8.CLARANS(NgandHan,1994)CLARANS(NgandHan,1994)9.DBSCAN(Easter,1996)9.DBSCAN(Easter,1996)以空间分布的密度为考虑发展求解模式。以空间分布的密度为考虑发展求解模式。10.GDBSCAN(SANDERet.al,1998)10.GDBSCAN(SANDERet.al,1998)单一物流中心货物配送模式之研究11四、VRP求解分析n n陈文瑞（陈文瑞（19901990）曾提到：）曾提到：VRPVRP是车辆在依序的服务地点做收货是车辆在依序的服务地点做收货(或，和或，和)送送货的服务，且必须依照指示依序通过这些服务地货的服务，且必须依照指示依序通过这些服务地点，开始和结束在同一个出发点点，开始和结束在同一个出发点(depotordepotordomicile)domicile)。n nVRPVRP问题的分类问题的分类 单一场站、多场站单一场站、多场站 本研究属于单一场站本研究属于单一场站单一物流中心货物配送模式之研究12VRP问题探讨n n本研究最主要的讨论是关于本研究最主要的讨论是关于单一场站与多车辆单一场站与多车辆路路线问题之研究，在实务应用上通常都以单一物流线问题之研究，在实务应用上通常都以单一物流中心，同时指派多部车辆，来达到时效性最高的中心，同时指派多部车辆，来达到时效性最高的顾客满意度。顾客满意度。n n这样的问题被定义为：在一广大的区域散置分布这样的问题被定义为：在一广大的区域散置分布N N各节点或顾客，每个顾客有其特定的需求量，各节点或顾客，每个顾客有其特定的需求量，这些需求量由某一个特定的中心站来提供，此中这些需求量由某一个特定的中心站来提供，此中心站有多部车辆，每部车辆的装载量为已知，来心站有多部车辆，每部车辆的装载量为已知，来求由配送中心到满足所有求由配送中心到满足所有N N各点的顾客需求的配各点的顾客需求的配送路线，并使送路线，并使配送成本达到最小配送成本达到最小。单一物流中心货物配送模式之研究13VRP问题求解模式(1)(1)先分群再排路线先分群再排路线(ClusterFirst-Routesecond)ClusterFirst-Routesecond)扫瞄法扫瞄法(GillettandMiller,1974)-GillettandMiller,1974)-采用及坐标角度扫瞄采用及坐标角度扫瞄分群。分群。(2)(2)先排路线再分群先排路线再分群(RouteFirst-clusterSecond)RouteFirst-clusterSecond)(BodinandBerman,1979)-(BodinandBerman,1979)-分群结果受先前排列之路进分群结果受先前排列之路进影响。影响。(3)(3)节省法或插入法节省法或插入法(SavingorInsertion)SavingorInsertion)节省法节省法(ClarkeandWright,1964)-ClarkeandWright,1964)-叫无弹性，无法视群叫无弹性，无法视群聚状况调整聚状况调整单一物流中心货物配送模式之研究14VRP问题求解模式n n(4)(4)改善与交换改善与交换(Improvementorexchange)Improvementorexchange)K-optimalK-optimal法法(LinandKernighan,1965)LinandKernighan,1965)n n(5)(5)数学规划法数学规划法(MathematicalProgrammingMathematicalProgrammingApproaches)Approaches)n n(6)(6)最佳解法最佳解法(ExactProcedures)ExactProcedures)n n(7)(7)人机互动法人机互动法(InteractiveOptimization)InteractiveOptimization)单一物流中心货物配送模式之研究15VRP问题求解模式分析n n由于由于VRPVRP属于非完全多项式属于非完全多项式(NP-Complete)NP-Complete)问题，问题，(5)(5)数学规划法、数学规划法、(6)(6)最佳解法两种方式求解复最佳解法两种方式求解复杂度随问题大小呈指数成长，近年来学者纷纷杂度随问题大小呈指数成长，近年来学者纷纷致力于启发式解法的开发。致力于启发式解法的开发。n n启发式解法基本步骤（徐吉田，启发式解法基本步骤（徐吉田，19931993）1.1.指定指定K K车辆（即路线）车辆（即路线）2.2.集结各需求点成一路线集结各需求点成一路线(启始解启始解)3.3.路线改善路线改善1.1.重新排列路线中各需求点，以得较好的路线。重新排列路线中各需求点，以得较好的路线。2.2.将某路线的点移到另一路线将某路线的点移到另一路线单一物流中心货物配送模式之研究16启发式解法基本概念n n目前学界研究目前学界研究VRPVRP问题通常采用二阶段法；问题通常采用二阶段法；第一阶段第一阶段初始解的产生，初始解的产生，例如例如(1)(1)先分群再排路先分群再排路线、线、(2)(2)先排路线再分群、先排路线再分群、(3)(3)节省法或插入法节省法或插入法 第二阶段第二阶段则为解的改善，则为解的改善，例如例如(4)(4)改善与交换改善与交换n n本研究采用先分群后排路线的方法，但考虑以本研究采用先分群后排路线的方法，但考虑以往相关研究较少将空间因子纳入考虑，故本研往相关研究较少将空间因子纳入考虑，故本研究引入空间分析中究引入空间分析中群聚分析群聚分析（ClusteringClusteringAnalysisAnalysis）的相关技术，来作为的相关技术，来作为VRPVRP的分群求解的分群求解（启始解）模式。（启始解）模式。单一物流中心货物配送模式之研究17五、研究架构VRP空间群聚求解模块配送以及物流之空间数据库车辆及路线的指派物流业特性分析VRP求解模式分析地理空间分析GIS系统比较其他求解策略不同空间Pattern分析归纳结果单一物流中心货物配送模式之研究18六、研究方法n n将空间分析中群聚分析模块应用于将空间分析中群聚分析模块应用于VRPVRP初始解初始解的求得，以离散的求得，以离散/群聚之空间分析为基础，并群聚之空间分析为基础，并以以clusteringclustering分析为核心改进方法，来改进及评分析为核心改进方法，来改进及评量配货地一解求法。量配货地一解求法。n n引入引入空间量度参数空间量度参数，以做为空间度量，来评定，以做为空间度量，来评定不同算法在不同空间度量上的优劣。不同算法在不同空间度量上的优劣。单一物流中心货物配送模式之研究19研究假设n n单一场站多部车辆单一场站多部车辆道路的特性道路的特性 初期考虑对称性路网，日后研究在考虑实际路网初期考虑对称性路网，日后研究在考虑实际路网配送点特性限制配送点特性限制 由一部车服务由一部车服务 需求皆不超过一部车容量需求皆不超过一部车容量车辆的限制型态车辆的限制型态 容量的限制容量的限制n n单一车种，多部车辆单一车种，多部车辆 行车距离的限制行车距离的限制单一物流中心货物配送模式之研究20研究假设时窗时窗(TimeWindow)TimeWindow)的限制的限制 不考虑时窗限制不考虑时窗限制客户区位特性客户区位特性 固定已知的需求固定已知的需求产品本身特性产品本身特性 以数量考虑，视为一种商品以数量考虑，视为一种商品单一物流中心货物配送模式之研究21群聚分析方法n n本研究考虑工具的取得以及符合研究假设需求本研究考虑工具的取得以及符合研究假设需求性，初步采用性，初步采用SPSSSPSS统计软件，利用其内建之统计软件，利用其内建之AnalyzeAnalyze模块中的模块中的ClassifyClassify的功能，采用的功能，采用k-k-meansClustermeansCluster以及以及 HierarchicalClusterHierarchicalCluster算法来算法来做分群，另外分区域配送之做分群，另外分区域配送之TSPTSP算法则采用最算法则采用最远内插法，利用远内插法，利用VBVB撰写求解程序配合撰写求解程序配合VRPVRP标准标准例题做测试。例题做测试。单一物流中心货物配送模式之研究22七、初步成果No.Problem NameNodesVehicle CapacitySourceCost and Fleet Data#1E-n51-k550160Christofieds&Eilon(1969)采用Christofieds&Eilon(1969)所提出的测试例题进行测试单一物流中心货物配送模式之研究23k-meansCluster结果单一物流中心货物配送模式之研究24HierarchicalCluster结果单一物流中心货物配送模式之研究25k-meansCluster配送结果单一物流中心货物配送模式之研究26HierarchicalCluster配送结果单一物流中心货物配送模式之研究27与过去研究之比较初步结果初步结果已知最佳解已知最佳解KC543KC543HC563HC563521521此结果为尚未进行改善解之初步结果，未来若配合良好都改善模块，应可达到同等水平。但由于SPSS为软件包，并无法另外加入容量限制式，故外来仍可能自行开发算法分析模块进行分析。单一物流中心货物配送模式之研究28八、结论n n初期由于受限于软件包限制，群聚分析部份的仅限于现有功能，并且未加入容量限制，未来仍以自行撰写程序模块，作为实验验证的工具。n n目前尚未就不同配送的模式讨论其不同空间分布型态下的结果，未来仍须进一步分析以了解群聚分析方法在空间群聚下的配送优势。