Stability Analysis for the Modification Method Under the a Priori Strategy of the PTSP

Résumé

We propose in this paper a new formulation for the stability of the Traveling Salesman Problem (TSP) compared with its probabilistic version, the Probabilistic Traveling Salesman Problem (PTSP). It is a real extension of the TSP, where the number of customers to be served each time is a random variable. That is only a subset of customers will need its services, moreover this subset varies from day to day. From the literature, several methods of resolution of the TSP have been proposed. In order to use these methods as they are for the PTSP came the idea of the study of stability. It is interested in finding cases where the solution for the TSP is also for the PTSP. First we survey and comment a number of easy TSPs. We also present via the notion of “Master tour” the stable problems in the TSP-PTSP context. An exact Branch and Bound is used for recognizing the TSPs that are not stable. Finally, we propose a new modification method, -different from the usual method of PTSP-, called the method of Taxi Driver, it takes the structure of the tour into consideration.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 1

Téléchargements : 0