Variable neighborhood search algorithm for heterogeneous traveling repairmen problem with time windows

摘要

The focus of this paper is generalized traveling repairman problem (TRP), a special case of the well known and well studied traveling salesman problem (TSP). Because of its specific objective function, that minimizes the sum of overall time all clients wait for until the end of a service, TRP has great applicability potential in client oriented practical problems. Therefore it has been known in literature as traveling deliveryman problem, minimum latency problem and cumulative capacitated vehicle routing problem. However, most studies that have treated TRP related problems have implied that only one repairman is present in the system and/or that all clients are available for service at the beginning of the planning horizon. In this paper we consider a TRP with a heterogeneous fleet of repairmen serving a set of clients whose arrival times are distributed over a planning horizon, i.e. heterogeneous TRPTW (hetTRPTW). For the hetTRPTW we present a mixed integer linear programming model, and a heuristic algorithm based on a variable neighborhood search (VNS) framework. Additionally, we propose a reduction strategy for neighborhoods in the VNS algorithm and test efficiency of implemented algorithms on four benchmark sets of problem instances. Results show that proposed algorithms could be used in real systems for solving small and moderate problem instances.