以適應性門檻接受法求解同時收送貨之車輛路線問題之研究

Threshold accepting metaheuristic with adaptive parameter setting for solving the vehicle routing problem with simultaneous pickups and deliveries

趙致傑

指導教授 ： 韓復華

國立交通大學/管理學院/運輸科技與管理學系/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.00620

摘要

同時收送貨車輛路線問題(vehicle routing problem with simultaneous pickups and deliveries, VRPSPD)是傳統車輛路線問題(vehicle routing problem, VRP)之延伸。不同於VRP僅考慮全程收貨或取貨，VRPSPD較能符合供應鏈物流配送的條件。
本研究針對VRPSPD以門檻接受法(threshold accepting, TA)為巨集演算法架構，設計一套新的RVND鄰域搜尋法進行求解。RVND代表隨機變動鄰域尋優法(randomized variable neighborhood descent)，其中共使用1-0、1-1、2-opt、2-opt*與Or-opt五種鄰域搜尋法。此外，本研究亦針對TA求解過程，建立一套適應性參數設定公式，可自動為不同題型設定起始門檻值、結束門檻值與門檻下降比例三種參數。
本研究以Salhi and Nagy所發表的14題例題、Tang Montané and Galvão所發表的18題例題以及Dethloff所發表的40題題庫，共72題國際標竿例題進行測試，發現其中有40題找到文獻已知最佳解，平均誤差為0.42%。

關鍵字

同時收送貨之車輛路線問題 ； 變動鄰域尋優法 ； 門檻接受法

並列摘要

The Vehicle Routing Problem with Simultaneous Pickups and Deliveries (VRPSPD) is an extension of the conventional VRP. Unlike the VRP which restricts the distribution for pickups or deliveries only, the VRPSPD is more flexible and applicable for solving real-world distribution problems in a supply chain.
This paper proposes a new metaheuristic method for solving the VRPSPD based on the threshold accepting (TA) framework. A new randomize variable neighborhood decent (RVND) method, which incorporates 1-0, 1-1, 2-opt*, Or-Opt and 2-Opt local search methods, is applied in our solution method. In addition, we also propose an adaptive parameter setting system to help the planner determine appropriate parameters of initial threshold, end threshold and threshold reduced ratio value.
Our proposed algorithms tested on a set of 72 benchmark instances including 14 instances from Salhi and Nagy, 18 instances from Tang Montané and Galvão and 40 instances from Dethloff. Results showed that our proposed methods have generated 40 best know solutions (BKS). The average deviation of all the tested instances is merely 0.42%.

並列關鍵字

VRP ； VRPSPD ； TA ； VND

參考文獻

5. Cho,Y.J. and Wang, S.D, “A threshold accepting meta-heuristic for the vehicle routing problem with backhauls and time windows”, Journal of Eastern Asia Society for Tranportation Studies, Vol. 6, pp.3022-3037, 2005.

29. 卓裕仁、朱佑旌，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究」，運輸計畫季刊，第三十七卷，第四期，頁405-430，民國97年。

30. 呂泓儒，「以改良型可回溯式門檻接受法求解回程取貨車輛路線問題之研究」，國立交通大學，碩士論文，民國98年。

32. 韓復華 , 陳仲豪 「應用時窗離散策略與可回溯式門檻接受法求解VRPBTW問題之研究 」, 運輸學刊 ，第二十二卷第三期，民國99年。

1. Ai, T.J. and Kachitvichyanukul, V., “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery”, Computers & Operations Research, Vol.36, pp.1693–1702, 2009.