Paper Info
Title
Generalized multiple depot traveling salesmen problem - polyhedral study and exact algorithm
Abstract
The generalized multiple depot traveling salesmen problem (GMDTSP) is a variant of the multiple depot traveling salesmen problem (MDTSP), where each salesman starts at a distinct depot, the targets are partitioned into clusters and at least one target in each cluster is visited by some salesman. The GMDTSP is an NP-hard problem as it generalizes the MDTSP and has practical applications in design of ring networks, vehicle routing, flexible manufacturing, scheduling and postal routing. We present an integer programming formulation for the GMDTSP and valid inequalities to strengthen the linear programming relaxation. Furthermore, we present a polyhedral analysis of the convex hull of feasible solutions to the GMDTSP and derive facet-defining inequalities that strengthen the linear programming relaxation of the GMDTSP. All these results are then used to develop a branch-and-cut algorithm to obtain optimal solutions to the problem. The performance of the algorithm is evaluated through extensive computational experiments on several benchmark instances.
Year
DOI
Venue
2015
10.1016/j.cor.2015.12.014
Computers & Operations Research
Keywords
Field
DocType
Generalized multiple depot traveling salesmen,Routing,Branch-and-cut,Polyhedral study
Combinatorics,Mathematical optimization,Vehicle routing problem,Manufacturing scheduling,Exact algorithm,Polyhedral analysis,Convex hull,Integer programming,Depot,Linear programming relaxation,Mathematics
Journal
Volume
ISSN
Citations 
70
0305-0548
11
PageRank 
References 
Authors
0.63
14
2
Name
Order
Citations
PageRank
Kaarthik Sundar17511.68
sivakumar rathinam2132.02