The tour construction and Improvement Method: An alternative approach to the multiple traveling salespersons problem

Adonis R. Cagape

Thesis (MS in Industrial Engineering)--University of the Philippines Diliman-2008

Abstract

The traveling salesperson problem (TSP) is a classical combinatorial optimization problem which finds a route for a salesperson required to visit a set of locations exactly once and return to the starting location after the strip. Its application has been widely recognized in various industries which ranges from delivery routing, bus scheduling, planning hotel inspection trips to multiple-job sequencing and newspaper printing. The common objective in TSP is minimizing the total travel costs which may be monetary-based, distance-based, time-based, whichever is more practical and applicable. The TSP with a single salesperson is a special case of the general multiple traveling salespersons problem (MTSP). In MTSP, the sum of the travel costs incurred by each salesperson is being optimized. This paper introduces the Tour Construction and Improvement Method, an MTSP solution technique that is carried out in two phases: Phase 1 or the Tour Construction Method (TCM) finds an initial feasible solution (IFS) by finding arcs with cheapest costs Phase 2 or the Tour Improvement Method (TIM) attempts to improve this IFS by a series of arc deletions and replacements. The effectiveness and robustness of TCIM was tested using both actual industry data and a statistically sound randomly generated data which proved applicability of the model to real world problems. From the industry data used, the heuristic produced solutions that are within 4.08% to13.51% from optimal in a fraction of a second, that is 1/26.05 to 1/31, 183.55 of ILIP runtime. TCIM also performed very well in other test data used. It was able to produce solutions within 0.00% to 23.21% from the optimal solution with a large improvement in runtime over ILIP. TCIM was able to produce the optimal solution in small problem size. TCIM was proven a cost-effective and satisfactory decision making tool for the multiple travelling salesperson problem.

Subject Index : Traveling salesman problem