TY - JOUR
T1 - An experimental comparison of human schedulers and heuristic algorithms for the traveling salesman problem
AU - Hill, Arthur V.
PY - 1982/8
Y1 - 1982/8
N2 - Vehicle routing and scheduling for laundry, courier, mail, and other service operations is a significant service industry problem. Several computer-based heuristic algorithms have been developed to assist schedulers in developing efficient delivery (and pick up) vehicle routes. This paper reports the results of an experiment that compared the performance of inexperienced human schedulers and seven heuristic vehicle routing algorithms. A large set of traveling salesman test problems ranging in size from 10 to 80 customers was used in the experiment. The results of the experiment suggest that inexperienced, untrained human schedulers can consistently find traveling salesman solutions as good as or better than all but one of the seven heuristic algorithms tested (including the widely used ClarkeWright distance saved heuristic and the recently published largest-angle insertion heuristic). The human schedulers found traveling salesman routes as good as the best heuristic tested (Lin 's 3-optimal) in 29 percent of the test problems. On average, the human schedulers' solution distances were only 2.8 percent above the 3-optimal heuristic solution distances.
AB - Vehicle routing and scheduling for laundry, courier, mail, and other service operations is a significant service industry problem. Several computer-based heuristic algorithms have been developed to assist schedulers in developing efficient delivery (and pick up) vehicle routes. This paper reports the results of an experiment that compared the performance of inexperienced human schedulers and seven heuristic vehicle routing algorithms. A large set of traveling salesman test problems ranging in size from 10 to 80 customers was used in the experiment. The results of the experiment suggest that inexperienced, untrained human schedulers can consistently find traveling salesman solutions as good as or better than all but one of the seven heuristic algorithms tested (including the widely used ClarkeWright distance saved heuristic and the recently published largest-angle insertion heuristic). The human schedulers found traveling salesman routes as good as the best heuristic tested (Lin 's 3-optimal) in 29 percent of the test problems. On average, the human schedulers' solution distances were only 2.8 percent above the 3-optimal heuristic solution distances.
UR - http://www.scopus.com/inward/record.url?scp=0039798360&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0039798360&partnerID=8YFLogxK
U2 - 10.1016/0272-6963(82)90010-9
DO - 10.1016/0272-6963(82)90010-9
M3 - Article
AN - SCOPUS:0039798360
SN - 0272-6963
VL - 2
SP - 215
EP - 223
JO - Journal of Operations Management
JF - Journal of Operations Management
IS - 4
ER -