以禁忌搜尋演算法求解車輛路徑與代理人選址問題

A Tabu Search Based Heuristic for the Vehicle Routing and Agent Location Problem

吳佳哲(Joseph, Sebastian Widagdo)

指導教授 ： 黃寬丞

國立交通大學/管理學院/運輸與物流管理學系/碩士(2016年)

摘要

在經典的車輛路徑問題（VRP），也可以是低效率（成本/時間）使用的車輛由一個服務於所有的客戶之一。如果客戶端的一組（或以後稱為群集）都集中在一個特定區域這種擔憂，尤其如此。在長期或中期規劃的背景下，利用代理商在集群內進行本地採集可以大大提高工作效率。訪問群集內的所有客戶端的路徑然後通過訪問代理，在一些招致成本外包的價格縮短路線所取代。為了確定最經濟有效的路徑和代理的位置，我們制定了車輛調度和代理選址問題（VRALP），它擴展了經典的VRP考慮到由代理人送達含集團客戶群，除了典型的客戶端的操作車輛送達。所述VRALPs兩個版本進行了研究。基本一要求在每個群集正好一個代理，以及先進的一者來確定的基於所述外包成本和車輛路徑的成本節約之間的權衡和它們的位置的最佳數目。
整數線性數學模型運用至解決這兩個問題。為了解決大問題的情況下，禁忌基於搜索的共通啟發式演算法開發。基於一些數值實驗，算法相比，基本和修改問題分支和綁定解決方案顯示了良好的性能。對於基本和高級模式，該算法可以分別給予0.82％ 和2.02％的目標差距。基於幾個數值實驗也提出來設置算法參數的準則。此外，該算法也適用於更大的問題多達150客戶看到算法的邊界。

關鍵字

車輛路徑 ； 代理人位置 ； 禁忌搜索 ； 外包

並列摘要

In the classic Vehicle Routing Problem (VRP), it can be inefficient (in terms cost and/or time) to use the vehicles to serve all of the customers one by one. This concern is particularly true if a group (or later referred to as a cluster) of clients are concentrated in a certain area. Under the context of long- or mid-term planning, using agents to perform local collection within a cluster can greatly improve the efficiency. The route for visiting all clients within a cluster is then replaced by the shortened route for visiting the agents, at the price of incurring some outsourcing cost. In order to determine the most cost-efficient routing and agent location, we formulate the Vehicle Routing and Agent Location Problem (VRALP), which extends the classic VRP to consider the clusters containing a group of clients to be served by an agent, in addition to the typical clients to be served by the operated vehicles. Two versions of the VRALPs have been studied. The basic one requires exactly one agent in each cluster, and the advanced one determines the optimal number of agents and their locations based on the trade-off between the outsourcing cost and the cost saving in vehicle routing.
Integer linear mathematical models are presented to solve both problems. To solve large instance problems, tabu search-based metaheuristics is developed. Based on some numerical experiments, the algorithms show good performance compared to the branch-and-bound solutions for both basic and modified problems. For the basic and advanced model, the algorithm can give 0.82% and 2.02% objective gap, respectively. A guideline to set algorithm parameters is also presented based on several numerical experiments. Also, the algorithm is also applied to bigger problems up to 150 clients to see the boundary of the algorithm.

並列關鍵字

Vehicle Routing ； Agent Location ； Tabu Search ； Outsourcing

參考文獻

Belenguer, J. M., Benavent, E., Martinez, A., Prins, C., Prodhon C., Villegas, J. G. 2015. A branch-and-cut algorithm for the single truck and trailer routing problem with satellite depots. Transportation Science, Article in Advance, pp. 1-15.

Bolduc, M., Renaud, J., Boctor, F. 2007. A heuristic for the routing and carrier selection problem. European Journal of Operational Research 183, pp. 926-932.

Bolduc, M., Renaud, J., Boctor, F., Laporte, G. 2008. A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers. Journal of the Operational Research Society, 59, pp. 776-787.

Chao, I-Ming. 2002. A tabu search method for the truck and trailer routing problem. Computers and Operations Research 29, pp. 33-51.

Chu, Ching-Wu. 2005. A heuristic algorithm for the truckload and less-than-truckload problem. European Journal of Operational Research 165, pp. 657-667.