摘要
本研究試圖在傳統的VRP問題上，加入加油點的考量，探討考量加油點之車輛途程問題(Vehicle Routing Problem with Refueling; VRPR)，此為車輛途程問題(Vehicle Routing Problem; VRP)的新型延伸問題。研究之主要目的在於完整定義此問題、建立數學規劃模型及發展有效率之啟發式演算法。由於車輛途程問題屬於NP-hard的問題，原本即不易求得最佳解，因此除小型問題可由數學規劃方法求得最佳解外，中、大型問題多以啟發式演算法求解。本研究所關心之VRPR問題，在原本的VRP問題上，加入加油點的考量，求解上將更困難，因此本研究除了建立VRPR問題之數學規劃模型，並據以求解小型問題外，也參考以往文獻，以禁忌搜尋法(Tabu Search; TS)為基礎，設計二階段演算法以有效求解中、大型之VRPR問題。

Abstract
This research considers the vehicle routing problem with refueling (VRPR), a new variant of the well-known vehicle routing problem (VRP). The objectives of this study are clearly defining the problem, constructing a mathematical programming model for the problem, and developing an effective heuristic algorithm for solving the problem. Since VRP belongs to the class of NP-hard problems, it is difficult to find an optimal solution for the problem, except for small-scale instances. Therefore, medium- and large-scale instances are often tackled by heuristic algorithms. The VRPR considered in this research is even more difficult to solve than the VRP since it also considers constraints on refueling, in addition to those constraints in the VRP. Thus, this research not only constructs a VRPR model, which can be used to solve small-scale VRPR instances, but also develops a two-stage heuristic based on Tabu Search to solve medium- and large-scale VRPR instances.

參考文獻
Alvarenga, G. B., Mateus, G. R., & de Tomi, G. (2007). A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers & Operations Research, 34(6), 1561-1584.
Archetti, C., Speranza, M., & Hertz, A. (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 40(1), 64-73.
Augerat, P., Belenguer, J., Benavent, E., Corberan, A., & Naddef, D. (1998). Separating capacity constraints in the CVRP using tabu search. European Journal of Operational Research, 106(2-3), 546-557.
Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30, 787-800.
Bard, J. F., Huang, L., Dror, M., & Jaillet, P. (1998). A branch and cut algorithm for the VRP with satellite facilities. IIE Transactions, 30(9), 821-834.
Bent, R., & Van Hentenryck, P. (2004). A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 38(4), 515-530.
Berger, J., & Barkaoui, M. (2004). A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research, 31(12), 2037-2053.
Bodin, L., Golden, B. L., Assad, A., & Ball, M. O. (1983). Routing and scheduling of vehicles and crews: the state of the art. Computers & Operations Research, 10, 62-212.
Brandao, J., & Mercer, A. (1998). The multi-trip vehicle routing problem. Journal of the Operational research society, 49(8), 799-805.
Braysy, I., & Gendreau, M. (2005a). Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Science, 39(1), 104-118.
Braysy, I., & Gendreau, M. (2005b). Vehicle routing problem with time windows, part II: Metaheuristics. Transportation Science, 39(1), 119-139.
Braysy, O. (2003). A reactive variable neighborhood search for the vehicle-routing problem with time windows. Informs Journal on Computing, 15(4), 347-368.
Braysy, O., Dullaert, W., & Gendreau, M. (2004a). Evolutionary algorithms for the vehicle routing problem with time windows. Journal of Heuristics, 10(6), 587-611.
Braysy, O., Hasle, G., & Dullaert, W. (2004b). A multi-start local search algorithm for the vehicle routing problem with time windows. European Journal of Operational Research, 159(3), 586-605.
Chin, A. J., Kit, H. W., & Lim, A. (1999). A new GA approach for the vehicle routing problem. 11th IEEE International Conference on Tools with Artificial Intelligence, Chicago, Illinois, USA.
Clarke, G., & Wright, J. V. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568-581.
Cordeau, J.-F., Desaulniers, G., Desrosiers, J., Solomon, M. M., & Soumis, F. (2002a). VRP with time windows. In P. Toth & D. Vigo (Eds.), The vehicle routing problem. (pp. 157-194). Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications.
Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J. Y., & Semet, F. (2002b). A guide to vehicle routing heuristics. Journal of the Operational Research Society, 53(5), 512-522.
Cordeau, J. F., & Laporte, G. (2002). Tabu search heuristics for the vehicle routing problem. GERAD Technical Report, G-2002-15. Montreal, Canada: University of Montreal.
Cordeau, J. F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), 928-936.
Cordone, R., & Calvo, R. W. (2001). A heuristic for the vehicle routing problem with time windows. Journal of Heuristics, 7(2), 107-129.
Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M. M., & Soumis, F. (2002). VRP with pickup and delivery. In P. Toth & D. Vigo (Eds.), The vehicle routing problem. (pp. 225-242). Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications.
Filipec, M., Skrlec, D., & Krajcar, S. (1998). An efficient implementation of genetic algorithms for constrained vehicle routing problem. IEEE International Conference on Systems, Man, and Cybernetics, San Diego, CA, USA.
Fischetti, M., Toth, P., & Vigo, D. (1994). A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Operations Research, 42(5), 846-859.
Fisher, M. L., & Jaikumar, R. (1981). Generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gambardella, L. M., Taillard, E.,Agazzi, G. (1999). MACS-VRPTW: A Multiple Colony System For Vehicle Routing Problems With Time Windows. New ideas in optimization, 63-76.
Gendreau, M., Hertz, A., & Laporte, G. (1994). Tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1290.
Gendreau, M., Laporte, G., & Seguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3-12.
Gillett, B., & Miller, L. (1974). A heuristic algorithm for the vehicle dispatch problem. Operations Research, 22(2), 340-349.
Glover, F. (1989). Tabu search - part I. ORSA Journal on Computing, 1(3), 190-206.
Glover, F. (1990). Tabu search - part II. ORSA Journal on Computing, 2(1), 4-32.
Homberger, J., & Gehring, H. (2005). A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research, 162(1), 220-238.
Ioannou, G., Kritikos, M., & Prastacos, G. (2001). A greedy look-ahead heuristic for the vehicle routing problem with time windows. Journal of the Operational Research Society, 52(5), 523-537.
Kohl, N., & Madsen, O. (1997). An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation. Operations Research, 45(3), 395-406.
Laporte, G. (1992). The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345-358.
Laporte, G., Gendreau, M., Potvin, J. Y., & Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7(4-5), 285-300.
Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem. Surveys in Combinatorial Optimization, 31, 147-184.
Laporte, G., & Semet, F. (2002). Classical heuristics for the capacitated VRP. In P. Toth & D. Vigo (Eds.), The Vehicle Routing Problem. (pp. 109-128). Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications.
Le Bouthillier, A., & Crainic, T. G. (2005). A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. Computers & Operations Research, 32(7), 1685-1708.
Le Bouthillier, A., Crainic, T. G., & Kropf, P. (2005). A guided cooperative search for the vehicle routing problem with time windows. IEEE Intelligent Systems, 20(4), 36-42.
Lin, S.-W., Yu, V. F., & Chou, S.-Y. (2009). Solving the truck and trailer routing problem based on a simulated annealing heuristic. Computers & Operations Research, 36(5), 1683-1492.
Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269.
Longo, H., de Aragao, M., & Uchoa, E. (2006). Solving capacitated arc routing problems using a transformation to the CVRP. Computers & Operations Research, 33(6), 1823-1837.
Mazzeo, S., & Loiseau, I. (2004). An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 18, 181-186.
Mester, D., & Braysy, O. (2005). Active guided evolution strategies for large-scale vehicle routing problems with time windows. Computers & Operations Research, 32(6), 1593-1614.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421-451.
Osman, I. H., & Wassan, N. A. (2002). A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. Journal of Scheduling, 5(4), 263-285.
Potvin, J., Duhamel, C., & Guertin, F. (1996). A genetic algorithm for vehicle routing with backhauling. Applied Intelligence, 6(4), 345-355.
Renaud, J., Laporte, G., & Boctor, F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research, 23(3), 229-235.
Russell, R. A., & Chiang, W. C. (2005). Scatter search for the vehicle routing problem with time windows. European Journal of Operational Research, 169(2), 606-622.
Scheuerer, S. (2006). A tabu search heuristic for the truck and trailer routing problem. Computers & Operations Research, 33, 894-909.
Semet, F., & Taillard, E. (1993). Solving real-life vehicle routing problems efficiently using tabu search. Annals of Operations Research, 41, 469-488.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research, 35, 254-265.
Tan, C., & Beasley, J. (1984). A heuristic algorithm for the period vehicle routing problem. Omega, 12(5), 497-504.
Ting, C. J., & Huang, C. H. (2005). An improved genetic algorithm for vehicle routing problem with time windows. International Journal of Industrial Engineering-Theory Applications and Practice, 12(3), 218-228.
Toth, P., & Vigo, D. (2002). The vehicle routing problem. Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications.
Van Breedam, A. (1995). Improvement heuristics for the vehicle routing problem based on simulated annealing. European Journal of Operational Research, 86, 480-490.
Wassan, N. A., & Osman, I. H. (2002). Tabu search variants for the mix fleet vehicle routing problem. Journal of the Operational Research Society, 53(7), 768-782.