A variable neighbourhood search (VNS) heuristic for the traveling salesman problem with pickup and delivery (TSPPD) executed in a last-in-first-out (LIFO) fashion has been ably developed by Hu QIN, a PhD student studying in the MS Department. The VNS heuristic involves several search operators based on the tree data structure. Experiments show that this heuristic is superior to the current best heuristics for this problem in terms of both solution quality and computing time. Therefore, this research paper is accepted by the AAAI conference, which invites presentations that identify significant social, philosophical, and economic issues influencing the development of artificial intelligence throughout the world. In existing literatures, the feasible solutions of the TSPPD are represented by vertex lists. However, when the TSPPD requires its loading and unloading operations to be performed in a last-in-first-out (LIFO) manner, Mr. Qin shows that its feasible solutions can be represented by trees. Therefore, his study addresses a variant of the TSPPD, in which loading and unloading operations must be performed in a LIFO manner. This problem is referred to as the TSPPD with LIFO loading (TSPPDL). The TSPPDL has been considered a more complex problem than the TSPPD because both the precedence and LIFO constraints must be checked to ensure solution feasibility. In his research paper, Mr. Qin shows that the problem will be greatly simplified if feasible solutions of TSPPDL are represented by using a tree. As a result, he is able to build upon the Variable Neighbourhood Search (VNS) heuristic proposed by Carrabs, Cordeau, and Laporte in 2007, which is the best existing approach for TSPPDL at the time of his writing. He reproduces four of the original operators using the tree representation, and also introduces three new operators. All in all, the new heuristic outperforms the original in terms of both solution quality and computation time.
Research Paper Accepted by the AAAI Conference 2010