臺灣博碩士論文加值系統

本研究介紹了具場站間路徑之區位途程問題 (Location-Routing Problem with Inter-Depot Routes; LRPI)以及具場站間路徑之開放式區位途程問題 (Open Location-Routing Problem with Inter-Depot Routes; OLRPI)，LRPI是區位途程問題 (Location-Routing Problem; LRP) 的變形，也同時為具場站間路徑之多場站車輛途程問題(Multi-Depot Vehicle Routing Problem with Inter-Depot Routes; MDVRPI)的延伸。LRPI有別於LRP的地方在於車輛可以在其路徑上的其他場站補貨，並且只要不超過場站容量限制，車輛可以重複經過場站。在LRPI中，其路徑為一封閉迴路，車輛完成服務顧客後必須返回場站，而在OLRPI則是考慮現今第三方物流業的營運和專車接送等等，為一開放式路程，在服務完最後一位顧客後無需返回場站即算完成路程。此問題由第三方物流業者的角度思考，試圖找出一組最有效之路徑，在不違背各項路程限制的情況下最小化總成本，其中包括設施設置成本，車輛的固定成本和旅行成本。我們提出了一個以模擬退火 (Simulated Annealing; SA) 為基礎的啟發式演算法去求解LRPI和OLRPI，在實驗中互相比較了LRP、OLRP、LRPI和OLRPI四個問題的解，實驗結果顯示加上Inter-Depot Routes能為傳統物流節省成本。

This research introduces the location-routing problem with inter-depot routes (LRPI) and the open location-routing problem with inter-depot routes (OLRPI). LRPI is a variant problem of location-routing problem and it extends the multi-depot vehicle routing problem with inter-depot routes (MDVRPI). LRPI is different from LRP as vehicles may be replenished at intermediate depots along their route. The depot can be repeated passed through by vehicles as long as its capacity limit is not exceeded. The LRPI concerns a closed loop problem in which all the routes start and end at the depot. On the other hand, the OLRPI is an open loop problem in which each vehicle starts from a depot, but ends at a final served customer. The applications of OLPRI include shuttle bus routing and third party logistics. The problem finds a set of the most effective paths to minimize total costs, including depot opening costs, fixed costs, and travel costs, without violating various side constraints. We propose a Simulated Annealing (SA) based heuristic algorithm to solve LRPI and OLRPI. The experiments compare the solutions of LRP, OLRP, LRPI and OLRPI. Experimental results indicate that using Inter -Depot Routes reduces costs for traditional logistics.

目錄
摘要 I
ABSTRACT II
目錄 III
圖目錄 V
表目錄 VI
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 1
1.3 研究目的 2
1.4 論文架構 2
第二章 文獻探討 3
2.1 區位途程問題及開放式區位途程問題 3
2.2 模擬退火法 3
2.3 具場站間路徑之多場站車輛途程問題 4
2.4 具中繼場站之週期性車輛途程問題 4
第三章 數學規劃模型 5
3.1 具場站間路徑之區位途程問題定義 5
3.2 具場站間路徑之區位途程問題模型 6
3.3 具場站間路徑之開放式區位途程問題定義 10
3.4 具場站間路徑之開放式區位途程問題模型 11
第四章 演算法 17
4.1 編碼方式 17
4.2 初始解 19
4.3 模擬退火法 21
4.4 鄰域搜尋 22
4.4.1 交換(Swap) 22
4.4.2 插入(Insert) 22
4.4.3 反轉(Reverse) 23
4.4.4 場站鄰域(Depot Neighborhood) 23
4.5 模擬退火法程序 24
第五章 實驗測試與結果分析 27
5.1 測試題庫 27
5.2 模擬退火法參數設定 28
5.3 LRP和OLRP測試結果 38
5.4 SA各參數的敏感度分析 44
5.5 鄰域搜尋對LRPI和OLRPI的影響 48
5.6 LRPI以及OLRPI比較 56
5.6.1 LRP與LRPI結果比較 56
5.6.2 OLRP與OLRPI結果比較 60
5.6.3 LRPI與OLRPI結果比較 65
第六章 結論與建議 68
參考文獻 70

AngelelliandSperanza. (2002). The periodic vehicle routing problem with intermediate facilities. European journal of Operational research, 137(2), 233-247.
Barreto. (2004). Análise e Modelização de Problemas de localização-distribuição.
Bertsimas. (1992). A vehicle routing problem with stochastic demand. Operations Research, 40(3), 574-585.
Bouhafs, Hajjam, andKoukam. (2006). A combination of simulated annealing and ant colony system for the capacitated location-routing problem. Paper presented at the Knowledge-Based Intelligent Information and Engineering Systems.
Boventer. (1961). The relationship between transportation costs and location rent in transportation problems. Journal of Regional Science, 3(2), 27-40.
Contardo, Cordeau, andGendron. (2014). A GRASP + ILP-based metaheuristic for the capacitated location-routing problem. Journal of Heuristics, 20(1), 1-38. doi:10.1007/s10732-013-9230-1
Coy, et al. (2001). Using experimental design to find effective parameter settings for heuristics. Journal of Heuristics, 7(1), 77-97.
Crevier, Cordeau, andLaporte. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), 756-773.
Desrochers, Desrosiers, andSolomon. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations research, 40(2), 342-354.
Dorigo, Di Caro, andGambardella. (1999). Ant algorithms for discrete optimization. Artificial life, 5(2), 137-172.
Duhamel, et al. (2010). A GRASP× ELS approach for the capacitated location-routing problem. Computers & Operations Research, 37(11), 1912-1923.
Escobar, Linfati, andToth. (2013). A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Computers & Operations Research, 40(1), 70-79.
Escobar, et al. (2014). A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem. Transportation Research Part B: Methodological, 67, 344-356.
Ghaffari-Nasab, Ahari, andGhazanfari. (2013). A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands. Scientia Iranica, 20(3), 919-930.
Hemmelmayr, Cordeau, andCrainic. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & operations research, 39(12), 3215-3228.
Hochbaum. (1996). Approximation algorithms for NP-hard problems: PWS Publishing Co.
KaraoglanandAltiparmak. (2010). A hybrid genetic algorithm for the location-routing problem with simultaneous pickup and delivery. Paper presented at the Computers and Industrial Engineering (CIE), 2010 40th International Conference on.
Kirkpatrick, Gelatt, andVecchi. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Kleywegt, Shapiro, andHomem-de-Mello. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
LinandKwok. (2006). Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data. European Journal of Operational Research, 175(3), 1833-1849.
Lin, Yu, andLu. (2011). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 38(12), 15244-15252.
LinandYu. (2012). A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 217(1), 94-107.
Lopes, Ferreira, andSantos. (2016). A simple and effective evolutionary algorithm for the capacitated location–routing problem. Computers & Operations Research, 70, 155-162.
Metropolis, et al. (1953). Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), 1087-1092.
Prins, Prodhon, andWolfler-Calvo. (2004). Nouveaux algorithmes pour le problème de localisation et routage sous contraintes de capacité. Paper presented at the MOSIM.
RosenandHarmonosky. (2005). An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. Computers & Operations Research, 32(2), 343-358.
Shariff, Omar, andMoin. (2016). Location Routing Inventory Problem with Transshipment Points Using p-Center. Paper presented at the Industrial Engineering, Management Science and Application (ICIMSA), 2016 International Conference on.
Tan, Cheong, andGoh. (2007). Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. European Journal of operational research, 177(2), 813-839.
TingandChen. (2013). A multiple ant colony optimization algorithm for the capacitated location routing problem. International Journal of Production Economics, 141(1), 34-44.
TuzunandBurke. (1999). A two-phase tabu search approach to the location routing problem. European journal of operational research, 116(1), 87-99.
Wu, Low, andBai. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393-1415.
Yu, et al. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299.
YuandLin. (2014). Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery. Applied Soft Computing, 24, 284-290.
YuandLin. (2015). A simulated annealing heuristic for the open location-routing problem. Computers & Operations Research, 62, 184-196.