Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman Problem
Pourquoi ce travail est dans la base
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Notice bibliographique
Résumé
Neighborhood search is a cornerstone of state-of-the-art traveling salesman and vehicle routing metaheuristics. Whereas neighborhood exploration procedures are well-developed for problems with individual services, their counterparts for one-to-one pickup-and-delivery problems are more scarcely studied. A direct extension of classic neighborhoods is often inefficient or complex because of the necessity of jointly considering service pairs. To circumvent these issues, we introduce major improvements to existing neighborhood searches for the pickup-and-delivery traveling salesman problem and new large neighborhoods. We show that the classic Relocate Pair neighborhood can be fully explored in [Formula: see text] instead of [Formula: see text] time. We adapt the 4-Opt and Balas–Simonetti neighborhoods to consider precedence constraints. Moreover, we introduce an exponential-size neighborhood called 2k-Opt, which includes all solutions generated by multiple nested 2-Opts and can be searched in [Formula: see text] time using dynamic programming. We conduct extensive computational experiments, highlighting the significant contribution of these new neighborhoods and speedup strategies within two classical metaheuristics. Notably, our approach permits us to repeatedly solve small pickup-and-delivery problem instances to optimality or near-optimality within milliseconds, and therefore, it represents a valuable tool for time-critical applications, such as meal delivery or mobility on demand. Funding: This work was supported by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 308528/2018-2, 315361/2020-4, 422470/2021-0], and Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro [Grants E-26/202.790/2019, E-26/201.417/2022, E-26/010.002232/2019]. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/trsc.2022.1176 .
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,001 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,001 |
| Études des sciences et des technologies | 0,001 | 0,000 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,000 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découle