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

Abstract

同時收送貨車輛路線問題(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%.