| Summary |
Yu-Ning Peng, 2008.06
Department of Transportation Technology and Management National Chiao Tung University
This research is concerned with the dynamic dispatching of multiple couriers in a fixed region with uniformly distributed demand point, i.e. K-Dynamic Couriers Service Problem, K-DCSP. The problem concerned is essentially a dynamic mTSP. Although abundant literature can be found on dynamic routing and dispatching problems, little has been discussed on the application of dynamic zoning strategies. This paper proposed a new dynamic zoning method, and showed its potential in dealing with the dynamic dispatching of multiple couriers.
The dynamic zoning procedure, we proposed, starts with a dynamic wait. We first hold the couriers, and wait until M demand calls before we start the service. We then use the k-medoids method to divide the M points into m clusters, and define the service zone for each courier using Voronoi graphs. In each service zone, the courier follows the nearest neighbor heuristic to service the customers. Such a procedure is repeated every time interval until the end of demand arrivals.
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. 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. We found that the dynamic zoning strategy would perform best when the demand density is low and the allowed waiting time is high. Under such conditions, the dynamic zoning may yield 20% and 40% savings in the distance traveled as compared to the fixed zone and single zone scenarios respectively. Finally, the optimal numbers of dispatchers under different scenarios were discussed. |
