以啟發式演算法求解單一場站多車種同時收送貨之車輛途程問題

A Heuristic Algorithm for Single Depot Vehicle Routing Problem with Simultaneous Pickup and Delivery

由配送中心運送貨物給顧客是配銷管理者每日所面臨的決策問題，如何有效率將貨物運送給顧客對配銷管理而言，是一項很重要的決策，因為運輸成本在配銷各項成本中所佔之比例很高，除此之外，速度也是一完善物流系統不可或缺的服務。本研究中以單一配送中心為研究對象，並以實務中多車種同時收送貨車輛途程問題（Vehicle Routing Problem with Simultaneous Pickup and Delivery:VRPSPD）為探討情境，研究之主要目的為在於滿足顧客需求及考慮公司成本下，發展一演算法，幫助配銷管理者解決規劃運送路線問題。研究中建構數學規劃模式與發展啟發式演算法，其中數學規劃模式僅適合小型問題求解與驗證演算法精確度之用。經測試比較後顯示啟發式演算法之效率與準確度均十分良好。

How to efficiently delivery goods to customers from a depot is a daily and an important decision for the logistics managers, because the transportation cost accounts for a large portion of the distribution cost. Furthermore, the speed of delivery is also an indispensable element of a sound logistics system. A single-depot vehicle routing problem with simultaneous pickup and delivery is studied in this paper. The main purpose of this paper is to develop a heuristic algorithm facilitating the logistics managers in planning the delivery routes under the consideration of customers' demands and operating costs. Both the mathematical model and heuristic algorithm are developed in this paper. The mathematical model is suitable for small size problem and developed for comparing the accuracy with the heuristic algorithm. From the empirical results, we know that the heuristic algorithm performs well in terms of efficiency and accuracy.