A GRASP with iterated local search for the traveling repairman problem with profits

被引:24
作者
Avci, Mustafa [1 ]
Avci, Mualla Gonca [1 ]
机构
[1] Dokuz Eylul Univ, Dept Ind Engn, TR-35397 Izmir, Turkey
关键词
Traveling repairman problem; Minimum latency; Profits; Variable neighborhood structure; VEHICLE-ROUTING PROBLEM; MINIMUM LATENCY PROBLEM; SALESMAN PROBLEM; APPROXIMATION ALGORITHMS; ORIENTEERING PROBLEM; NEIGHBORHOOD SEARCH; MEMETIC ALGORITHM; PATH-RELINKING; TIME WINDOWS; CONSTRAINTS;
D O I
10.1016/j.cie.2017.09.032
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Traveling Repairman Problem with profits (TRPP) is an extension of the Traveling Repairman Problem (TRP), where there is not an obligation to visit all vertices. A time-dependent profit is associated with each vertex and the objective is to maximize the total collected revenue. In this paper, we initially develop a new mixed-integer linear model capable of solving small size instances for the TRPP. To solve medium and large size instances, a simple and effective metaheuristic algorithm (GRASP-ILS) is introduced for the TRPP, which combines Greedy Randomized Adaptive Search Procedure (GRASP) for initial solution construction and Iterated Local Search (ILS) with an adaptive perturbation mechanism for solution improvement. The proposed GRASP-ILS is tested on the TRPP benchmark instances derived from the literature. The results indicate that the developed GRASP-ILS can produce efficient and effective solutions for the TRPP. Particularly, it has been observed that the developed GRASP-ILS has improved the best solutions for 46 instances and obtained all the best known results for the remaining instances in a reasonable computation time.
引用
收藏
页码:323 / 332
页数:10
相关论文
共 58 条
[1]   Balancing and scheduling tasks in assembly lines with sequence-dependent setup times [J].
Andres, Carlos ;
Miralles, Cristobal ;
Pastor, Rafael .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 187 (03) :1212-1223
[2]  
Archer A, 2003, SIAM PROC S, P88
[3]  
Archer A, 2010, PROC APPL MATH, V135, P429
[4]   The Undirected Capacitated General Routing Problem with Profits [J].
Archetti, Claudia ;
Bertazzi, Luca ;
Lagana, Demetrio ;
Vocaturo, Francesca .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 257 (03) :822-833
[5]  
Archetti C, 2014, MOS-SIAM SER OPTIMIZ, P273
[6]   Incomplete Service and Split Deliveries in a Routing Problem with Profits [J].
Archetti, Claudia ;
Bianchessi, Nicola ;
Speranza, M. Grazia ;
Hertz, Alain .
NETWORKS, 2014, 63 (02) :135-145
[7]   Approximation schemes for minimum latency problems [J].
Arora, S ;
Karakostas, G .
SIAM JOURNAL ON COMPUTING, 2003, 32 (05) :1317-1337
[8]  
Ausiello G, 2000, LECT NOTES COMPUT SC, V1767, P1
[9]   A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem [J].
Avci, Mustafa ;
Topaloglu, Seyda .
COMPUTERS & OPERATIONS RESEARCH, 2017, 83 :54-65
[10]   A GRASP based solution approach to solve cardinality constrained portfolio optimization problems [J].
Baykasoglu, Adil ;
Yunusoglu, Mualla Gonca ;
Ozsoydan, F. Burcin .
COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 90 :339-351