Ant Colony Optimization Based Heuristics for the On-road Air-express Courier Routing Problem
| Autor: | Wilson W. Lan, 藍唯誠 |
|---|---|
| Rok vydání: | 2008 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 96 The on-road courier routing operation is the most critical part of air-express companies. With good routing guidelines, couriers can serve larger areas, thus the company can save the labor cost and the vehicle routing cost. Facing the ever-increasing labor and fuel costs, finding good solutions to the on-road courier routing problems becomes imperatively important to the air-express companies. This study treats the courier routing problem in suburban areas and dense urban areas as traveling salesman problem (TSP) and multi-stop location-routing problem (MSLRP), respectively. In suburban areas, the courier routing problem is formulated such that the couriers would drive to visit each customer point (delivery or pickup) exactly once to minimize the total traveled distance. Two novel approaches: stepwise-ACO (SACO) and cheapest insertion stepwise-ACO (CISACO) are proposed. Three pickup emerging patterns are tested in the numerical experiments. The results under 1-update rule show that CISACO is superior to SACO, and both approaches are better than the cheapest insertion (CI) heuristic in terms of total traveled distance. Further experiments on n-update rules show that the 1-update rule cannot guarantee the minimum total traveled distance by the three routing approaches. However, it is rather robust that CISACO approach performs no worse than the SACO approach, which is far superior to the CI approach, regardless of the updated rules or pickup patterns. In dense urban areas, the courier routing problem is formulated in such a way that the couriers would find appropriate locations of vehicle stops, each stop covering several customer ends by a foot route, to minimize the total system costs. Two solving strategies are proposed: sequential and refined strategies. The sequential strategy is used to obtain the preliminary solutions for locating the vehicle stops, assigning the customer points to each vehicle stop, and determining the foot tours and vehicle tour. The refined strategy is to further improve the routing efficiency based on the results of the sequential strategy. The numerical experiments show that the number of vehicle stops decreases with the threshold value, regardless of the strategies used. The total vehicle routing distance also decreases with the threshold value. However, the total foot routing distance will increase with the threshold value. The refined strategy is superior to the sequential strategy in terms of total delivery costs and time, for larger threshold value. Moreover, the influences of different customer distributions on the final results are also investigated with three different instance types. The air-express companies are recommended to introduce our proposed routing algorithms to examine their on-road couriers’ operations. The minimum routing distance or cost obtained by our proposed algorithms can benchmark the couriers’ and managers’ objective experiences in the on-road courier routing operations. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|