求解考慮收貨與送貨路線之區位途程問題

Solving the Capacitated Location Routing Problem with Pickup and Delivery Routes

黃山璋(Shan-Huen Huang)

《運輸學刊》 27卷3期 (2015/09) Pp. 415-438

https://doi.org/10.6383/JCIT.201509_27(3).0004

摘要

考慮車輛途程問題以探討配送中心區位位置選擇之問題稱之為區位途程問題。此研究討論一延伸之區位途程問題，其區位包含收貨與送貨兩個車隊。此兩不同車隊之路線將同時影響區位之選擇。為求解此問題，本研究提出一包含三階段之解法。第一階段為決定所需之設備數，本研究提出一策略以協助做此決策。第二階段為指派客戶至區位以接受該區位之服務。同樣的，本研究亦提出一方法以協助此指派作業。最後一階段使用禁忌搜尋法以協助求出車輛途程。此求解流程首先應用於文獻中之區位途程問題以驗證其求解品質，之後，此流程用於求解本研究所建立之問題題組。根據所得之結果可驗證此求解流程能夠有效率的求解此類問題。

關鍵字

區位途程問題 ； 禁忌搜尋法 ； 啟發式演算法

並列摘要

The problem of determining the location of distribution centers that takes vehicle routes into account is called the Location Routing Problem. This paper presents an extended capacitated location routing problem that considers two different routes, including pick-up and delivery originated from the depots. These two different sets of routes will affect the decision of distribution center deployment. A new solving process that contains three stages is proposed to address this issue. The first stage is to determine the number of open depots needed, and thus one strategy is proposed in this research to help in the selection of open depots. The second stage is to assign customers to one of the open depots for logistics service, and a method is provided in this work to assist with this process. The last stage is to form the vehicle routes, and a modified TABU search is designed to help in vehicle dispatching. This solving process is applied to the conventional location routing benchmarks to verify its solution quality. A new set of benchmarks with regard to the problem is then established and solved by this proposed process. According to the results of the experiments, the proposed solving process can efficiently and effectively solve the location routing problem with pick-up and delivery routes.

並列關鍵字

Location routing problem ； Tabu search ； Heuristics

參考文獻

Albareda-Sambola, M.,Diaz, J. A.,Fernandez, E.(2005).A Compact Model and Tight Bounds for a Combined Location-routing Problem.Computers and Operations Research.32(3),407-428.

Albareda-Sambola, M.,Diaz, J. A.,Fernandez, E.(2010).Lagrangean Duals and Exact Solution to the Capacitated P-center Problem.European Journal of Operational Research.201(1),71-81.

Albareda-Sambola, M.,Fernandez, E.,Laporte, G(2007).Heuristic and Lower Bound for Stochastic Location-routing Problem.European Journal of Operational Research.179(3),940-955.

Barreto, S.,Ferreira, C.,Paixao, J.,Santos, B. S.(2007).Using Clustering Analysis in a Capacitated Location-routing Problem.European Journal of Operational Research.179(3),968-977.

Belenguer, J. M.,Benavent, E.,Prins, C.(2011).A Branch-and-cut Method for the Capacitated Location-routing Problem.Computers and Operations Research.38(6),931-941.