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

Vehicle Routing Problem for Home Delivery Carriers

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

《運輸計劃季刊》 35卷4期 (2006/11) Pp. 443-474

https://doi.org/10.6402/TPJ.200611.0443

摘要

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

關鍵字

宅配業 ； 車輛路線規劃問題 ； 旅行銷售員問題

並列摘要

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.

並列關鍵字

Home delivery carrier ； Vehicle routing problem ； Traveling salesman problem

參考文獻

韓復華,王國琛(2002).巨集啟發式解法在求解大規模旅行推銷員問題之應用.運輸學刊.14(2),1-14.

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.

Anily, S.,Mosheiov, G.(1994).The Traveling Salesman Problem with Delivery and Backhauls.Operations Research Letters.16,11-18.

Dueck, G.,Scheuer, T.(1990).Threshold Accepting: A General Purpose Optimization Algorithm Appeared Superior to Simulated Annealing.Journal of Computational Physics.90,161-175.

Gendreau, M.,Hertz, A.,Laporte, G.(1996).The Traveling Salesman Problem with Backhauls.Computers Operations Research.23(5),501-508.