開放式區域途程問題(Open Location Routing Problem; OLRP)是區域途程問題(Location Routing Problem; LRP)的延伸問題。在LRP問題中，位於各個場站的每一車輛從場站出發，服務完顧客後必須再回到場站，OLRP與其不同之處在於車輛不需再回到場站。
由於開放式區域途程問題是屬於NP-hard的問題，原本即不易求得最佳解，因此中、大型的問題通常是以啟發式演算法求解。因此本研究之主要目的在於完整定義此問題，建立OLRP之數學規劃模型並且參考以往文獻，以粒子群最佳化演算法(Particle Swarm Optimization; PSO)為基礎，發展能有效求解中、大型之OLRP問題之兩階段演算法。
本研究利用發展出的兩階段啟發式演算法去求解三個LRP題庫，結果與文獻中之目前最佳解的平均誤差分別為2.77%與1.8%及1.92%，顯示本研究發展出之演算法為一有效率的演算法。本研究最後以此演算法求解OLRP問題，其結果將可供未來研究參考。

The open Location Routing Problem (OLRP) is a new variant of the Location Routing Problem (LRP). In the Location Routing Problem, every vehicle starts its route from a depot. When it finishes serving customers, the vehicle must return to the same depot. The difference between LRP and OLRP is that the vehicle in OLRP does not need to return to the same depot from where it starts its route. Since OLRP belongs to the class of NP-hard problems, it is difficult to find an optimal solution to the problem. Therefore, medium-scale and large-scale instances are often solved by heuristic algorithms. Thus, the purposes of this research include defining OLRP, constructing its mathematical model, and developing a two-stage heuristic based on the Particle Swarm Optimization algorithm to effectively solve medium- and large-scale OLRP instances.
The results of computational study indicate that two phase particle swarm optimization heuristic method can solve the LRP efficiently. The relative percentage gaps between the solution obtained by the proposed PSO algorithm and the best known solutions for three set of LRP benchmark instances are 2.77%, 1.8%, and 1.92%, respectively. Finally, the proposed method is used to solve OLRP instances. The results could be used as benchmarks for future research.

Archetti, C., Speranza, M., & Hertz, A. (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 40(1), 64-73.
Baker, B. M., & Ayechew, M. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.
Baker, E. K. (1983). An exact algorithm for the time-constrained traveling salesman problem. Operations Research, 31(5), 938-945.
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.
Barreto, S. (2004). Analysis and Modelling of Location-Routing Problems. PhD thesis, University of Aveiro, Aveiro, Portugal.
Beasley, J. E. (1983). Route first--cluster second methods for vehicle routing. Omega, 11(4), 403-408.
Berger, R. T., Coullard, C. R., & Daskin, M. S. (2007). Location-routing problems with distance constraints. Transportation Science, 41(1), 29-43.
Bodin, L., Golden, B., Assad, A., & Ball, M. (1983). Routing and scheduling of vehicles and crews: The state of the art. Computers & Operations Research, 10(2), 63-211.
Brandao, J., & Mercer, A. (1998). The multi-trip vehicle routing problem. Journal of the Operational Research Society, 49(8), 799-805.
Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An improved ant System algorithm for thevehicle Routing Problem. Annals of Operations Research, 89, 319-328.
Chan, Y., Carter, W. B., & Burnes, M. D. (2001). A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands. Computers & Operations Research, 28(8), 803-826.
Cheng, C. B., & Mao, C. P. (2007). A modified ant colony system for solving the travelling salesman problem with time windows. Mathematical and Computer Modelling, 46(9-10), 1225-1235.
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.
Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth & C. Sandi (Eds.), Combinatorial Optimization. (pp. 315-338). Chichester, UK: Wiley.
Clarke, G., & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 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.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6, 80-91.
Daskin, M. S., Coullard, C. R., & Shen, Z. J. M. (2002). An inventory-location model: Formulation, solution algorithm and computational results. Annals of Operations Research, 110(1-4), 83-106.
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.
Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2-3), 243-278.
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.
Fisher, M. L., & Jaikumar, R. (1981). A 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. In D. Corne, M. Dorigo & F. Glover (Eds.), New Ideas in Optimization (pp. 63-76). UK: McGraw-Hill.
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. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340-349.
Golden, B. L., & Assad, A. (1988). Vehicle Routing: Methods and Studies. Amsterdam: North-Holland.
Kirkpatrick, S., Gelatt Jr., C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671-680.
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., Nobert, Y., & Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science, 22(3), 161-172.
Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for thetraveling-salesman problem. Operations Research, 21(2), 498-516.
Liu, S., & Lin, C. (2005). A heuristic method for the combined location routing and inventory problem. The International Journal of Advanced Manufacturing Technology, 26(4), 372-381.
Marinakis, Y., & Marinaki, M. (2008). A particle swarm optimization algorithm with path relinking for the location routing problem. Journal of Mathematical Modelling and Algorithms, 7(1), 59-78.
Mazzeo, S., & Loiseau, I. (2004). An ant colony algorithm for the capacitated vehicle routing. Electronic Notes in Discrete Mathematics, 18, 181-186.
Or, I. (1976). Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Northwestern University.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421-451.
Potvin, J., Duhamel, C., & Guertin, F. (1996). A genetic algorithm for vehicle routing with backhauling. Applied Intelligence, 6(4), 345-355.
Prins, C., Prodhon, C., Ruiz, A., Soriano, P., & Wolfler Calvo, R (2007). Solving the capacitated location-routing problem by a cooperative Lagrangian relaxation-granular tabu search heuristic. Transportation Science, 41(4), 470-483.
Schrage, L. (1981). Formulation and structure of more complex/realistic routing and scheduling problems. Networks, 11, 229-232.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265.
Tan, C., & Beasley, J. (1984). A heuristic algorithm for the period vehicle routing problem. Omega, 12(5), 497-504.
Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications.
Tuzun, D., & Burke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 116(1), 87-99.
Van Breedam, A. (1995). Improvement heuristics for the vehicle routing problem based on simulated annealing. European Journal of Operational Research, 86, 480-490.
Yu, B., Yang, Z.-Z., & Yao, B. (2009). An Improved Ant Colony Optimization for Vehicle Routing Problem. European Journal of Operational Research, 196(1), 171-176.
Yu, V. F., Lin, S.-W., Lee, W., & Ting, C.-J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299.