車輛路線含回程取貨問題（The Vehicle Routing Problem with Backhauls ; VRPB)是VRP的擴展，它將服務的顧客分爲兩類，第一類是將貨物送達的顧 客（Linehaul，or Delivery customers)，第二類是回程取貨的顧客（Backhaul， or Pickup customers)。近年來，大眾了解運用此種在運送途中回程取貨的混合 運送方式，可大量節省運輸成本，以美國雜貨業而言，從一九八二年開始利 用回程取貨的運送方式，每年節省配送成本超過一千六百億美元。本研究係 針對VRPB問題特性，依據劉復華與申生元所提出「路線鄰域」（Route Neighborhood)觀念，對各顧客點指派參考路線指標(Reference Route Identifier ，RRI)，用於實施路線鄰域插入時之依據，進而發展出一種新的啓發式演算 法：「路線鄰域法」來建構VRPB求解模式，運用電腦語言撰寫程式，以國 際網路標準測試例題作測試，評估其績效，並與最佳解做一比較，驗證求解 品質，供未來國内探討車輛路線問題回程取貨研究之參考。最後提出研究結 論並建議後續研究者針對本研究啓發式演算法中的步驟，可再進行路線改善 的方法。而運用路線鄰域法除求解Backhaul問題外，學者已有用於求解Time Window問題，並得到相當好的解。因此，値得後續研究者運用此方法求解 VRP領域其他相關問題

The VRPB (Vehicle Routing Problem with Backhauls) is considered as an extension of VRP (Vehicle Routing Problem) and the customers it services are divided into two categories. Category I consists of the Linehaul, or Delivery customers, each of which is to be delivered of certain products from the Depot or the Distribution Center. Category II consists of the Backhaul, or Pick Up customers, each of which has certain products to be picked up in or after the distribution routes before moving back to the Depot or the Distribution Center. In recent years, people have recognized the fact that huge amount of transportation costs could be saved by applying this kind of mixed delivery/pick up method of including Backhaul customers in the traditionally Delivery only routes. For example, the American grocery industry started applying the mixed delivery/pick up transportation method in 1982 and thus saved more than one hundred sixty billion US Dollars annually. In this paper, based on the concepts of 'Route Neighborhood' presented by Fuh-hwa Liu and Sheng-yuan Shen, we assign RRI ( Reference Route Identifier ) to the customer nodes for the convenience of route insertion when applying Route Neighborhood methodology,and develop a new heuristic algorithm. The algorithm uses the Route Neighborhood method to build a VRPB model which is converted into a program in computer languages for obtaining the results faster. Tests are conducted on benchmark problems from the Internet to evaluate the solution quality by comparing them with the optimal solutions. We hope this will provide a good reference for future studies on the Vehicle Routing Problem with Backhauls. Other researchers find that Route Neighborhood methodology also brings out very good solutions when applied to the VRP with Time Window problems. Therefore, further studies on Route Neighborhood method are encouraged for better solutions to other VRP problems.