An enhanced heuristic for the team orienteering problem with time windows considering multiple deliverymen.

This paper proposes a team orienteering problem with time windows considering multiple deliverymen (TOPTWMD), which arises from practical situations where firms deliver goods to customers in congested urban areas. In addition to the routing and scheduling decisions, the crew size for each route also has to be decided. Adapted from iterative three-component heuristic (I3CH), an enhanced heuristic is designed for this problem. Integrating two effective methods and the alteration between feasible and infeasible regions, the proposed heuristic finally consists of three components, including (i) an iterated local search in feasible region, (ii) a tabu search in infeasible region, and (iii) a route recombination for a high-quality solution. Besides, due to the particularity of deliverymen assignment, some adaptive changes must be made accordingly compared with the original I3CH. The TOPTWMD instances are generated by modifying the Solomon instances. To evaluate the performance of the enhanced heuristic, computational experiments are conducted on a set of 138 instances for comparing enhanced heuristic with CPLEX and original I3CH. Results demonstrate the effectiveness and the stability of the proposed algorithm. Moreover, additional analyses verify that the joint use of the three components and the alteration between feasible and infeasible regions make significant contributions to the performance of the enhanced heuristic. [ABSTRACT FROM AUTHOR]