이종 확률적 외판원 문제를 위한 최소 평균거리 삽입 및 집단적 지역 탐색 알고리듬
A Minimum Expected Length Insertion Algorithm and Grouping Local Search for the Heterogeneous Probabilistic Traveling Salesman Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
The Probabilistic Traveling Salesman Problem (PTSP) is an important topic in the study of traveling salesman problem and stochastic routing problem. The goal of PTSP is to find a priori tour visiting all customers with a minimum expected length, which simply skips customers not requiring a visit in the tour. There are many existing researches for the homogeneous version of the problem, where all customers have an identical visiting probability. Otherwise, the researches for the heterogeneous version of the problem are insufficient and most of them have focused on search base algorithms. In this paper, we propose a simple construction algorithm to solve the heterogeneous PTSP. The Minimum Expected Length Insertion (MELI) algorithm is a construction algorithm and consists of processes to decide a sequence of visiting customers by inserting the one, with the minimum expected length between two customers already in the sequence. Compared with optimal solutions, the MELI algorithm generates better solutions when the average probability is low and the customers have different visiting probabilities. We also suggest a local search method which improves the initial solution generated by the MELI algorithm.
Abstract
The Probabilistic Traveling Salesman Problem (PTSP) is an important topic in the study of traveling salesman problem and stochastic routing problem. The goal of PTSP is to find a priori tour visiting all customers with a minimum expected length, which simply skips customers not requiring a visit in the tour. There are many existing researches for the homogeneous version of the problem, where all customers have an identical visiting probability. Otherwise, the researches for the heterogeneous version of the problem are insufficient and most of them have focused on search base algorithms. In this paper, we propose a simple construction algorithm to solve the heterogeneous PTSP. The Minimum Expected Length Insertion (MELI) algorithm is a construction algorithm and consists of processes to decide a sequence of visiting customers by inserting the one, with the minimum expected length between two customers already in the sequence. Compared with optimal solutions, the MELI algorithm generates better solutions when the average probability is low and the customers have different visiting probabilities. We also suggest a local search method which improves the initial solution generated by the MELI algorithm.
참고문헌 (15)
- Bertsimas,D.J, "Probabilistic Combinatorial Optimization Problem", 박사, pp.1988
- Bertsimas,D.J, "Further Results on the Probabilistic Traveling Salesman Problem", European Journal of Operational Research, 65(1), pp.68~95 (1993)
- Bianchi,L, "Local Search for the Probabilistic Traveling Salesman Problem:Correction to the 2-p-opt and 1-shift Algorithms", European Journal of Operations Research, 162(1), pp.206~219 (2005)
- Bianchi,L, "Ant Colony Optimization and Local Search for the Probabilistic Traveling Salesman Problem:A Case Study in Stochastic Combinatorial Optimization", 박사, pp.2006
- Bowler,N.E, "Characterization of the Probabilistic Traveling Salesman Problem", Physical Review E, 68 (2003)
- Clarke,G, "Scheduling of Vehicles from a Central Depot to a Number of Delivery Point", Operations Research, 12, pp.568~581 (1964)
- Held,M, "The Traveling Salesman Problem and Minimal Spanning Trees", Operations Research, 18(6), pp.1138~1162 (1970)
- Jaillet,P, "Probabilistic Traveling Salesman Problems", 박사, pp.1985
- Jaillet,P, "Stochastic Routing Problems, Advanced School on Stochastic in Combinatorial Optimization", pp.192~213 (1987), World Scientific Publisher
- Jaillet,P, "A Priori Solution of a Traveling Salesman Problem in which a Random Subset of the Customers are Visited", Operations Research, 36, pp.929~936 (1988)
- Jaillet,P, "The Probabilistic Vehicle Routing Problem, Vehicle Routing : Methods and Studies", pp.293~318 (1988), Amsterdam
- Laporte,G, "A Priori Optimization of the Probabilistic Traveling Salesman Problem", Operations Research, 42, pp.543~549 (1994)
- Liu,Y.-H, "Genetic Algorithms for the Probabilistic Traveling Salesman Problem", Proceedings of the Conference on E-Logistics,Taoyuan,Taiwan,77-82, pp.77~82 (2004)
- Liu,Y.-H, "A Hybrid Scatter Search for the Probabilistic Traveling Salesman Problem", Computers and Operations Research, 34, pp.2949~2963 (2007)
- Marinakis,Y, "Expanding Neighborhood Search-GRASP for the Probabilistic Traveling Salesman Problem", Optimization Letters, 2(3), pp.351~361 (2008)