多車種接駁補貨車輛途程問題

A Study of the Feeder Vehicle Routing Problem

何宗育(Tsung-yu Ho)

指導教授 ： 陳惠國

國立中央大學/工學院/土木工程學系/碩士(2007年)

摘要

台灣都市地區部分巷道狹窄，致使大型貨車進出、臨時停車皆不容易；為因應此問題，物流業者使用機動性高但載貨量較小之輕便車輛(如機車)進行貨物配送，然而此舉可能造成車輛往返配送場站中心之次數與距離增加。近年來已有部分業者利用載貨量大但機動性較低之大車(如貨車)搭配機動性高但載貨量較小之小車(如機車)進行聯合貨物配送，亦即大車、小車各自進行貨物配送，當小車送貨完畢時，除了返回場站補貨亦可選擇直接前往大車所在位置補貨，補貨完畢小車即可再進行送貨服務，節省小車往返場站之次數、距離與時間。
針對上述問題，本研究提出「接駁補貨車輛途程問題」(Feeder Vehicle Routing Problem, FVRP)，根據問題特性建構數學模型，並提出預估平均法、門檻法兩種啟發式求解架構，再根據測試題庫The VRP Web為基礎，從中挑選出17題設計為FVRP之測試例題並作測試結果分析。經由測試結果比較，發現在測試例題的改善解當中，預估平均法的表現較良好，其最重要之原因為求解過程中預估平均法選擇較多補貨點，使小車補貨選擇更有彈性；而將測試例題補貨候選點由4點增為8點時，小車補貨選擇增加，可改善目標值約5.8%；最後提出本問題後續研究方向與建議。

關鍵字

啟發式解法 ； 多車種 ； 接駁補貨 ； 車輛途程問題

並列摘要

Due to scarcity of land resources, urban streets in Taiwan, especially those at local street level, are often not wide enough for big cars performing temporary parking and home delivery services. To solve this problem, few home delivery companies have invented a new type of vehicle routing and operations which involves two types of vehicles. During the operation, a big vehicle departs from the depot and travels along several “legitimate” stops whereas a set of small vehicles performs delivery to customers and, if necessary, reloads the commodity either from the depot or from the big vehicle at stops and then continues their work. The objective of the operation is to minimize the total travel cost. This new service not only overcomes the difficulty of accessing “narrowed” local streets with high-capacity big cars but also saves the low-capacity small vehicles a number of times to and from the depot to reload the commodities.
This problem can be regarded as an extension of the Vehicle Routing Problem and for easy of reference is named as the Feeder Vehicle Routing Problem (FVRP). In this research, the FVRP problem is formally formulated as a mixed integer programming problem and two heuristics, namely the method of average and the threshold method, are proposed for solving it. 17 test problems modified from a set of classical VRP benchmark instances were extensively examined. The results show that the method of average outperforms the threshold method in terms of the objective value, though the latter does have some nice features from the algorithmic point of view. In addition, we also observed that more candidates of stops allowed for the big car, the better objective value would be obtained. To conclude the research, a few remarks were made in the end.

並列關鍵字

Heuristic Algorithm. ； Heterogeneous Fleet ； Feeder ； Vehicle Routing Problem

參考文獻

1. 池昆霖(2006)，區位途程與易腐性商品排程之研究，國立中央大學土木工程研究所碩士論文，中壢。

10. Chao, I. (2002), “A Tabu Search Method for the Truck and Trailer Routing Problem,” Computers & Operations Research, Vol.29, pp.33-51.

11. Christofides, N., and Eilon, S. (1969), “An Algorithm for Vehicle Dispatching Problem,” Operational Research Quarterly, Vol.20, pp.309-318.

13. Clarke, G., and Wright, J.W. (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581.

15. Dueck, G., and Scheuer, T. （1990）,“Threshold Accepting: a General Purpose Optimization Algorithm Appeared Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp. 161-175.