01514491

Component

The traveling salesman problem (TSP) is the most famous problem in the operations research community and has attracted great interest from various scientific domains. Most efforts are currently focused on employing case-tailored fine-tuned heuristics to overcome the problem’s inherent complexity. In this paper the authors focus towards improving exact solution approaches without targeting to compete against the best solutions provided by heuristics. The authors devise techniques to improve solution time in an exact approach setting following a cutting plane approach. The authors relax the subtour elimination constraints known to render the problem intractable due to their exponential nature and progressively append cuts to the original problem. In these cuts the authors enforce connection between the vertices of the identified subtour and the remaining vertices so that a previously encountered subtour never appears in the course of the algorithm. The authors introduce additional integer variables for each node providing the number of outgoing and ingoing arcs of the two disjoint sets. The authors compare their results against classical known formulations and observe that the proposed new approach is dominant in terms of solution time for all instances tested.

This paper was sponsored by TRB committee ADB30(8) Paper Review Group #4. Alternate title: Improvements in Exact Solution Method for Traveling Salesman Problem.

01503729

14-2983

English

11p

2014

Transportation Research Board 93rd Annual Meeting

Digital/other

Figures; References; Tables

Commercial vehicle operations; Operations research; Pickup and delivery service; Routing; Traveling salesman problem

Computation time

Freight Transportation; Highways; Planning and Forecasting; I72: Traffic and Transport Planning

Transportation Research Board Annual Meeting 2014 Paper #14-2983

TRIS, TRB, ATRI

Jan 27 2014 3:01PM