标题: 不同需求特性下多运务员动态分区派遣策略之研究
Dynamic Zoning Strategies for Dispatching of Couriers under Different Demand Patterns
作者: 岳忠杰
Yueh, Chung-Chieh
韩复华
Han, Fu-Wha Anthony
运输与物流管理学系
关键字: 动态分区;动态派遣;k-medoids分群法;动态等待;动态多旅行推销员问题;Dynamic Zoning;Dynamic Dispatch;k-medoids;Dynamic Wait;Dynamic mTSP
公开日期: 2008
摘要: 近年来动态车辆路线问题的研究日益增多,但鲜有考虑顾客需求在不同时间与空间分布上,对分区派遣策略的影响。本研究即考虑顾客需求于不同时间与空间分布的影响下,对多位快递运务员的服务作业问题进行探讨。研究问题假设服务范围固定,且由单一场站指派k位运务员对动态产生的顾客进行取件作业。
本研究在需求面考虑:时间分布上无尖峰、单尖峰与双尖峰的情况,而空间分布上则考虑均匀与群聚的情况。在动态派遣方面,包括动态等待与动态分区两部份,动态等待策略方面:等待订单数量的DM与等待时间间隔的DW两种。完成动态等待条件后,即进入动态分区的部份:以k-medoids法分群,再以Voronoi图分派每位运务员的责任区域。在方法论方面,以系统模拟建构不分区、固定分区、动态分区等策略,并针对尖离峰时段执行分区派遣策略的模拟。并在各需求面之下,测试二至四位运务员,搭配不同分区派遣策略时,各绩效指标:营运成本、服务水准与劳役分配的表现。为避免顾客等待过久,本研究亦限制顾客所能接受的平均等待时间,以不同目标为前提来推荐运务员数量与派遣分区策略。
模拟程式以C#程式语言建构,并在Intel(R) Core(TM)2,CPU为2.00GHz的个人电脑进行测试。研究结果发现在各种情境假设之下,营运成本而言,动态分区最佳,固定分区次之,不分区殿后。服务水准而言,不分区最佳,固定分区次之,动态分区则殿后。劳役分配而言,动态分区最为佳,固定分区次之,不分区殿后。若假设顾客可接受平均等待时间60分钟以内,无尖峰需求型态下,执行DM与DW为分群条件的动态分区,与不分区相较,最少运务员为目标时,总旅行距离约节省9%~36%,最短总旅行距离为目标时,约节省21%~56%;尖峰需求型态下,针对尖离峰执行不同参数设定的DM策略,与不分区相较,最少运务员为目标时,总旅行距离约节省23%~45%,最短总旅行距离为目标时,约节省26%~48%。
This research is concerned with the dynamic dispatching of multiple couriers in a fixed region with the demand patterns which are influenced by temporal and spatial characteristics. Although abundant literature can be found on dynamic routing and dispatching problems, little has considered the impact of various demand patterns to the optional dynamic routing and dispatching.
In our research, we consider both temporal and spatial characteristics of different demand patterns. Temporal characteristics include uniform, single peak-hour and double peak-hour distributions over a day of operation; spatial characteristics include uniform and cluster distributions over the service area. The dynamic zoning procedure, as we proposed, starts with a dynamic wait. Two dynamic waiting strategies are considered: DM which waits for M demand calls, and DW which waits a fixed time interval of W. As to the dynamic zoning, we first use the k-medoids method to cluster demand points, and then the Voronoi graphs to define the service zone for each courier. In each service zone, the courier follows the nearest neighbor heuristic to service the customers. In addition, both the “single zone” and “fixed zone” strategies are also considered in order to evaluate the performance of the proposed “dynamic zone” strategy.
Simulation models were built and coded in C# to analyze the performance of the three zoning strategies. We tested on a Intel(R) Core(TM)2 CPU 2.00GHz personal computer. Under various temporal and spatial situations, results showed that the dynamic zoning yielded the lowest average travel distance, and yet the highest average waiting time. On the other hand, the single zone strategy gives the lowest waiting time, and yet the longest average travel distance. If the customer can accept the average waiting time in 60 minutes, dynamic zoning strategies under DM or DW will save significant travel distance more than single zone or fixed zone strategies when the demand is uniformly distribution. In addition, dynamic zoning strategies which wait more at peak hours and wait less at off-peak hours perform better than other strategies in travel distance.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079632529
http://hdl.handle.net/11536/42843
显示于类别:Thesis


文件中的档案:

  1. 252901.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.