Personal tools
Jump to: navigation, search

Adonis R. Cagape

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


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

  • This page was last modified on 14 March 2012, at 04:49.
  • This page has been accessed 1,196 times.
The Fine Print: contents on this site are owned by whoever posted them (as indicated on the page History). Neither the DILC nor the University is responsible for them in any way. DILC reserves the right to delete them if they are deemed in violation of the University's Acceptable Use Policy and other applicable laws.