A unique integer linear programming formulation is proposed to define a Hamiltonian tour in which the cost between a node pair is determined by the number of nodes between each pair on the tour. In addition, a node separation requirement may be conditional on other node separations. Properties of this new traveling salesman problem formulation are discussed, along with an a priori solution to the probabilistic traveling salesman problem with equal node coverage probability as a linear programming alternative to the probabilistic programming method in the literature. A linear programming-based heuristic is proposed and numerically tested.
Get full access to this article
View all access options for this article.
References
1.
CramaY., van de KlundertJ., and SpieksmaF. C. R.Production Planning Problems in Printed Circuit Board Assembly. Discrete Applied Mathematics, Vol. 123, No. 1-3, 2002, pp. 339–361.
2.
JailletP.Probabilistic Traveling Salesman Problem. PhD dissertation. Massachusetts Institute of Technology, Cambridge, Mass., 1985.
3.
DantzigG., FulkersonD., and JohnsonS.Solution of a Large Scale Traveling Salesman Problem. Operations Research, Vol. 2, 1954, pp. 393–410.
4.
FoxK. R., GavisB., and GravesS. C.An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem. Operations Research, Vol. 28, 1980, pp. 1018–1021.
5.
MillerC. E., TuckerA. W., and ZemblinR. A.Integer Programming Formulation of Traveling Salesman Problems. Journal of the ACM, Vol. 7, No. 4, 1960, pp. 326–329.
6.
ClausA.A New Formulation for the Traveling Salesman Problem. SIAM Journal on Algebraic and Discrete Methods, Vol. 5, No. 1, 1984, pp. 21–25.
7.
PicardJ. C., and QueyranneM.The Time Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One Machine Scheduling. Operations Research, Vol. 26, 1978, pp. 86–110.
8.
SarinS. C., SheraliH. D., and BhootraA.New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem With and Without Precedence Constraints. Operations Research Letters, Vol. 33, No. 1, 2005, pp. 62–70.
9.
LaporteG., LouveauxF. V., and MercureH.A Priori Optimization of the Probabilistic Traveling Salesman Problem. Operations Research, Vol. 42, No. 3, 1994, pp. 543–549.
10.
TangH., and Miller-HooksE.Solving a Generalized Traveling Salesperson Problem with Stochastic Customers. Computers & Operations Research, Vol. 34, No. 7, 2007, pp. 1963–1987.
