運用基因演算法求解同時收送貨之車輛路線問題之研究

Abstract

同時收送貨車輛路線問題(vehicle routing problem with simultaneous pickups and deliveries, VRPSPD)假設顧客點同時具有收貨與送貨的需求，目標為在滿足所有顧客點需求下最小化車輛總旅行距離，此問題限制較符合現實生活中之物流配送之情境。 本研究採用基因演算法為整體架構設計一演算法求解VRPSPD；在交配機制中提出有別於典型基因交配之設計：結合兩種不同之傳統交配法，配合隨機概念交錯使用，以改善兩種傳統交配法各自之缺點；並提出一放寬車容量限制之機制以尋找新的搜尋區域，確實進行廣度搜尋，避免侷限於區域最佳解。 本研究針對Salhi and Nagy所發表的14題例題以及Dethloff所發表的40題題庫，共54題標竿範例進行測試，實測結果證實本研究所提出之交配設計與放寬車容量限制之機制皆能有效改善演算法之效用；本研究最佳解與文獻已知最佳解之平均誤差為3.50%。

The Vehicle Routing Problems with Simultaneous Pickups and Deliveries (VRPSPD) is an extension of the classical Vehicle Routing Problems (VRP), where customers may receive and delivery goods simultaneously. The objective of this problem is to determine a set of routes with minimal cost to fulfill the entire customer needs. We develop a genetic algorithm (GA) based heuristic algorithm for solving VRPSPD. The most significant characteristics of our algorithm are adopting two different types of crossover designs and the technique of relaxing vehicle capacity to escape from the local optimal. We test our proposed algorithms on a set of 54 benchmark instances including 14 instances from Salhi and Nagy and 40 instances from Dethloff. The numerical experimental results show that our proposed algorithm is sound and promising. The average deviation from the known best solutions is merely 3.50%.