Multi-restart iterative search for the pickup and delivery traveling salesman problem with FIFO loading.

*(English)*Zbl 1391.90071Summary: The pickup and delivery traveling salesman problem with FIFO loading (TSPPDF) is a variant of the classic traveling salesman problem with pickup and delivery arising from several practical applications where services have to be carried out in the first-in-first-out fashion. In this paper, we present a multi-restart iterative search approach (MIS) for TSPPDF based on a combined use of 6 move operators. The basic idea behind MIS is to alternate between a threshold-based exploration phase, during which degrading solutions are considered as long as they satisfy a quality threshold, and a descent-based improvement phase that only accepts solutions that improve on the quality of the current solution. A dedicated restart strategy is applied to generate a new starting point for the next round of the iterative search as soon as the search is deemed trapped into a deep local optimum. Extensive experiments on a set of 42 benchmark instances from the literature show that the proposed approach competes very favorably with the existing methods from the literature. In particular, it reports new upper bounds (improved best-known solutions) for 20 instances, while matching the best-known result for the remaining instances. The key components of MIS are analyzed to shed light on their impact to the overall algorithmic performance.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90C27 | Combinatorial optimization |

90C59 | Approximation methods and heuristics in mathematical programming |

90C60 | Abstract computational complexity for mathematical programming problems |

##### Keywords:

heuristics; traveling salesman problem; pickup and delivery; first-in-first-out loading; threshold search
Full Text:
DOI

##### References:

[1] | Benavent, E.; Landete, M.; Mota, E.; Tirado, G., The multiple vehicle pickup and delivery problem with LIFO constraints, Eur. J. Oper. Res., 243, 3, 752-762, (2015) · Zbl 1346.90078 |

[2] | Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated f-race: an overview, Experimental methods for the analysis of optimization algorithms, 311-336, (2010), Springer Berlin Heidelberg · Zbl 1204.68280 |

[3] | Carrabs, F.; Cerulli, R.; Cordeau, J. F., An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO or FIFO loading, INFOR, 45, 4, 223-238, (2007) |

[4] | Carrabs, F.; Cordeau, J. F.; Laporte, G., Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading, INFORMS J. Comput., 19, 4, 618-632, (2007) · Zbl 1241.90103 |

[5] | Cassani, L.; Righini, G., Heuristic algorithms for the TSP with rear-loading, 35th Annual Conference of the Italian Operations Research Society (AIRO XXXV), (2004), Lecce Italy |

[6] | Cheang, B.; Gao, X.; Lim, A.; Qin, H.; Zhu, W., Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints, Eur. J. Oper. Res., 223, 1, 60-75, (2012) · Zbl 1253.90190 |

[7] | Chen, Y.; Hao, J. K., Iterated responsive threshold search for the quadratic multiple knapsack problem., Ann. Oper. Res., 226, 1, 101-131, (2015) · Zbl 1309.90085 |

[8] | Chen, Y.; Hao, J. K., Two phased hybrid local search for the periodic capacitated arc routing problem, Eur. J. Oper. Res., 264, 1, 55-65, (2018) · Zbl 1380.90037 |

[9] | Chen, Y.; Hao, J. K.; Glover, F., A hybrid metaheuristic approach for the capacitated arc routing problem, Eur. J. Oper. Res., 253, 1, 25-39, (2016) · Zbl 1346.90087 |

[10] | Cherkesly, M.; Desaulniers, G.; Laporte, G., A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading, Comput. Oper. Res., 62, 23-35, (2015) · Zbl 1348.90075 |

[11] | Cordeau, J. F.; Dell’Amico, M.; Iori, M., Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading, Comput. Oper. Res., 37, 5, 970-980, (2010) · Zbl 1177.90336 |

[12] | Cordeau, J. F.; Iori, M.; Laporte, G.; Salazar González, J. J., A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading, Networks, 55, 1, 46-59, (2010) · Zbl 1206.90137 |

[13] | Croes, G. A., A method for solving traveling-salesman problems, Oper. Res., 6, 6, 791-812, (1958) |

[14] | Dong, X.; Chen, P.; Huang, H.; Nowak, M., A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time, Comput. Oper. Res., 40, 2, 627-632, (2013) · Zbl 1349.90339 |

[15] | Dueck, G., New optimization heuristics: the great deluge algorithm and the record-to-record travel, J. Comput. Phys., 104, 1, 86-92, (1993) · Zbl 0773.65042 |

[16] | Duecka, G.; Scheuera, T., Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, J. Comput. Phys., 90, 1, 161-175, (1990) |

[17] | Erdoǧan, G.; Cordeau, J. F.; Laporte, G., The pickup and delivery traveling salesman problem with first-in-first-out loading, Comput. Oper. Res., 36, 6, 1800-1808, (2009) · Zbl 1179.90280 |

[18] | Gao, X.; Lim, A.; Qin, H.; Zhu, W., Multiple pickup and delivery TSP with LIFO and distance constraints: a VNS approach, Modern Approaches Appl. Intell., 193-202, (2011) |

[19] | Gendreau, M.; Laporte, G.; Vigo, D., Heuristics for the traveling salesman problem with pickup and delivery, Comput. Oper. Res., 26, 7, 699-714, (1999) · Zbl 0957.90069 |

[20] | Geng, X.; Chen, Z.; Yang, W.; Shi, D.; Zhao, K., Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search, Appl. Soft Comput., 11, 4, 3680-3689, (2011) |

[21] | Glover, F., Tabu thresholding: improved search by nonmonotonic trajectories, ORSA J. Comput., 7, 4, 426-442, (1995) · Zbl 0843.90097 |

[22] | Kirkpatrick, S.; Jr, G. C.; Vecchi, M. P., Optimization by simulated annealing, Read. Comput. Vision, 220, 4598, 606-615, (1983) |

[23] | Kruskal, J. B., Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis, Psychometrika, 29, 1, 1-27, (1964) · Zbl 0123.36803 |

[24] | Li, Y.; Lim, A.; Oon, W. C.; Qin, H.; Tu, D., The tree representation for the pickup and delivery traveling salesman problem with LIFO loading, Eur. J. Oper. Res., 212, 3, 482-496, (2011) · Zbl 1237.90203 |

[25] | Li, Y.; Zhou, A.; Zhang, G., Simulated annealing with probabilistic neighborhood for traveling salesman problems, Natural Computation (ICNC), 2011 Seventh International Conference on, 3, 1565-1569, (2011), IEEE |

[26] | López-Ibánez, M.; Dubois-Lacoste, J.; Stützle, T.; Birattari, M., The irace package, iterated race for automatic algorithm configuration, Technical Report TR/IRIDIA/2011-004, IRIDIA, (2011), Université Libre de Bruxelles Belgium |

[27] | Nikolakopoulos, A.; Sarimveis, H., A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem, Eur. J. Oper. Res., 177, 3, 1911-1929, (2007) · Zbl 1102.90025 |

[28] | Or, I., Traveling salesman-type combinational problems and their relation to the logistics of blood banking (phd thesis), (1976), Northwestern University USA |

[29] | Pacheco, J. A., Metaheuristic based on a simulated annealing process for one vehicle Pick-up and delivery problem in LIFO unloading systems, Proceedings of the Tenth Meeting of the Europen Chapter of Combinatorial Optimization (ECCO X), (1997), Tenerife Spain |

[30] | Porumbel, D. C.; Hao, J. K.; Kuntz, P., A search space “cartography for guiding graph coloring heuristics, Comput. Oper. Res., 37, 4, 769-778, (2010) · Zbl 1176.90613 |

[31] | Reinelt, G., TSPLIB-a traveling salesman problem library, ORSA J. Comput., 3, 4, 376-384, (1991) · Zbl 0775.90293 |

[32] | Rocki, K.; Suda, R., Accelerating 2-opt and 3-opt local search using GPU in the travelling salesman problem, High Performance Computing and Simulation (HPCS), 2012 International Conference on., 489-495, (2012), IEEE |

[33] | Tarantilis, C. D.; Ioannou, G.; Kiranoudis, C. T.; Prastacos, G. P., A threshold accepting approach to the open vehicle routing problem, RAIRO-Oper. Res., 38, 4, 345-360, (2004) · Zbl 1114.90063 |

[34] | Tarantilis, C. D.; Kiranoudis, C. T.; Vassiliadis, V. S., A backtracking adaptive threshold accepting algorithm for the vehicle routing problem, Syst. Anal. Model. Simul., 42, 5, 631-664, (2002) · Zbl 1070.90528 |

[35] | Wei, L.; Qin, H.; Zhu, W.; Wan, L., A study of perturbation operators for the pickup and delivery traveling salesman problem with lifo or FIFO loading, J. Heuristics, 21, 5, 617-639, (2015) |

[36] | Xie, B. L.; Liang, L. I.; Guo, Y. H., Using simulated annealing for solving travelling salesman problem with pickup and delivery, Syst. Enging-theory Methodol. Appl., 11, 3, 240-243, (2002) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.