宅配業車輛路線規劃問題之模式建立與求解

Modeling and Solving Vehicle Routing Problem for Home Delivery Carriers

林志鴻(Chih-Hung Lin)

《運輸學刊》 17卷1期 (2005/03) Pp. 65-94

https://doi.org/10.6383/JCIT.200503.0065

摘要

近年來，國內宅配市場日趨受到重視，進而促使國內幾個大型企業相繼投入宅配市場之經營，亦帶動國內的傳統貨物運輸業者轉型進行宅配服務（以下簡稱宅配業），而本研究主要是針對宅配業之車輛路線規劃問題進行探討，經實地訪查了解，宅配業車輛路線規劃問題之特性包括單一性、時段性、收送性、以及動態性等，屬旅行銷售員問題之變化。本研究除深入探討此問題特性外，並依其問題特性直接構建相關數學模式，且依實務上之作法與其問題特性，分別研擬三種策略進行路線規劃。經求解結果顯示，無法斷定何種策略可使車輛路線旅程較短，但如以顧客服務之觀點，則以策略三可獲得較高的顧客服務水準，且我們亦提供一些有用的建議，期能供相關業者之參考。

關鍵字

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

並列摘要

In the last years, the development of computer networks and e-commerce has quickly led to changes in freight transport supply and demand. An increase in the demand of delivery goods to home has attracted many companies participating into this market. Generally speaking, these companies are called delivery-goods-to-home carriers (DHC), which are similar to less-than-truck-load carriers. This paper explores the vehicle routing problem of DHC, which is also called the vehicle routing problem for home delivery (VRPHD). Actually, the characteristics of VRPHD and the traveling salesman problem (TSP) are similar Characteristics of VRPHD include pickup-delivery routing, order-clustered customers, and real-time needs. So, the VRPHD is a dynamic pickup-delivery traveling salesman problem with backhauls (DPDTSPB) and we have developed some models to solve it and proposed corresponding operational strategies. The empirical results show that none of the strategy is clearly better than the others in terms of transportation cost. But our recommended strategy is better than the others in considering customer service. Furthermore, thus paper also provides some useful suggestions to DHC in Taiwan.

並列關鍵字

Home delivery carrier ； Vehicle routing problem ； Traveling salesman problem

參考文獻

林志鴻、陳春益、許晉嘉()。

蘇昭銘、張志鴻、莊子駿()。

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

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.

Brown, G. G.,Graves, G. W.(1981).Real-time Dispatch of Petroleum Tank Trucks.Management Science.27(1),19-32.