A variable iterated greedy algorithm for the traveling salesman problem with time windows

作者：Karabulut Korhan; Tasgetiren M Fatih^*

来源：Information Sciences, 2014, 279: 383-395.

DOI：10.1016/j.ins.2014.03.127

• Traveling salesman problem with time windows
• Iterated greedy algorithm
• Variable neighborhood search
• Heuristic optimization

This paper presents a variable iterated greedy algorithm for solving the traveling salesman problem with time windows (TSPTW) to identify a tour minimizing the total travel cost or the makespan, separately. The TSPTW has several practical applications in both production scheduling and logistic operations. The proposed algorithm basically relies on a greedy algorithm generating an increasing number of neighboring solutions through the use of the idea of neighborhood change in variable neighborhood search (VNS) algorithms. In other words, neighboring solutions are generated by destructing a solution component and re-constructing the solution again with variable destruction sizes. In addition, the proposed algorithm is hybridized with a VNS algorithm employing backward and forward 1_Opt local searches to further enhance the solution quality. The performance of the proposed algorithm was tested on several benchmark suites from the literature. Experimental results confirm that the proposed algorithm is either competitive to or even better than the best performing algorithms from the literature. Ultimately, new best-known solutions are obtained for 38 out of 125 problem instances of the recently proposed benchmark suite, whereas 15 out of 31 problem instances are also further improved for the makespan criterion.

• 出版日期2014-9-20