宅配業車輛路線問題之研究

Vehicle Routing Problem for Home Delivery Carriers

10.6402/TPJ.200611.0443

林志鴻(Chih-Hung Lin)；許晉嘉(Chin-Chia Hsu)

宅配業 ； 車輛路線規劃問題 ； 旅行銷售員問題 ； Home delivery carrier ； Vehicle routing problem ； Traveling salesman problem

運輸計劃季刊

35卷4期（2006 / 11 / 30）

443 - 474

繁體中文

近年來，國內宅配市場日趨受到重視，進而促使國內幾個大型企業相繼投入宅配市場之經營，亦帶動國內的傳統貨物運輸業者轉型進行宅配服務（以下簡稱宅配業），而本研究主要是針對宅配業之車輛路線問題進行探討。經實地訪查了解，宅配業車輛路線問題之特性包括須同時考量收送貨、需求點具有動態性質、車輛起迄點相同、…等，屬旅行銷售員問題之變化，而本研究除深入探討此問題特性外，並依其特性直接構建相關數學模式，以及研提啟發式解法，且進一步進行實例研究，以了解本研究成果於實務上之適用性，依求解結果顯示，本研究所規劃之路線均符合問題特性，故本研究成果應可進一步作為後續研究或相關業者之參考。

In recent years, the development of computer networks and e-commerce has led to changes in freight transport supply and demand and to an increase in the demand of delivery goods to home, which many freight transport companies are interested in. Generally speaking, the companies are called delivery-goods-to-home carriers (DHC), similar to less-than-truckload carriers. This paper explores the vehicle routing problem of DHC (or vehicle routing problem for home delivery (VRPHD)). Actuality, the VRPHD and traveling salesman problem (TSP) are similar and the characteristics of VRPHD include pickup-delivery routing, order clustered customers, and real-time needs of certain customers. Therefore, the VRPHD is a dynamic pickup-delivery traveling salesman problem with backhauls (DPDTSPB). In this study, we have developed some models and a heuristics algorithm to solve the VRPHD. The empirical results suggest that the route design proposed in this study fits in well with the characteristics of VRPHD. Furthermore, this study also provides valuable suggestions for future studies and the DHC in Taiwan.

1. 韓復華,王國琛(2002).巨集啟發式解法在求解大規模旅行推銷員問題之應用.運輸學刊,14(2),1-14.
   連結：
2. Anily, S.,Bramel, J.,Hertz, A.(1999).A 5/3-Approximation Algorithm for the Clustered Traveling Salesman Tour and Path Problems.Operations Research Letters,24,29-35.
3. Anily, S.,Mosheiov, G.(1994).The Traveling Salesman Problem with Delivery and Backhauls.Operations Research Letters,16,11-18.
4. Dueck, G.,Scheuer, T.(1990).Threshold Accepting: A General Purpose Optimization Algorithm Appeared Superior to Simulated Annealing.Journal of Computational Physics,90,161-175.
5. Gendreau, M.,Hertz, A.,Laporte, G.(1996).The Traveling Salesman Problem with Backhauls.Computers Operations Research,23(5),501-508.
6. Gendreau, M.,Laporte, G.,Vigo, D.(1999).Heuristics for the Traveling Salesman Problem with Pickup and Delivery.Computers and Operations Research,26(7),699-714.
7. Jongens, K.,Volgenant, T.(1985).The Symmetric Clustered Traveling Salesman Problem.European Journal of Operational Research,68-75.
8. Mitrovic-Minic, S.,Krishnamurti, R.,Laporte, G.(2004).Double-horizon Based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows.Transportation Research Part B,38,669-685.
9. Mitrovic-Minic, S.,Laporte, G.(2004).Waiting Strategies for the Dynamic Pickup and Delivery Problem with Time Windows.Transportation Research Part B,38,635-655.
10. Mosheiov, G.(1994).The Traveling Salesman Problem with Pick-up and Delivery.European Journal of Operational Research,299-310.
11. Psaraftis, H. N.(1988).Dynamic Vehicle Routing Problems.Vehicle Routing: Methods and Studies
12. Renaud, J.,Boctor, F. F.,Ouenniche, J.(2000).A Heuristic for the Pickup and Delivery Traveling Salesman Problem.Computers Operations Research,27,905-916.
13. Savelsbergh, M. W. P.,Sol, M.(1995).The General Pickup and Delivery Problem.Transportation Science,29(1),17-29.
14. 蘇昭銘、張志鴻、莊子駿(2001)。應用GIS分析宅配業車輛路線排程作業之研究。中華民國運輸學會第十六屆論文研討會，411-420。

1. 彭國芳、陳乃華(2011)。宅配組織之內部服務品質因子對宅配服務司機之工作滿意與服務行為之影響─路徑模型之釐清。資訊與管理科學，4(1)，50-68。