The combined manpower-vehicle routing problem for multi-staged services

Abstract

This paper introduces a combined problem of vehicle routing and scheduling of manpower teams to perform multi-stage tasks at customer locations. Each customer demands several tasks in a given order. These tasks are performed by a set of teams and each team can perform a single task. The teams should be moved by a set of vehicles. The objective is to find an efficient schedule for the teams and to minimize the cost of vehicle routing. The problem differs from the traditional vehicle routing problem in that the tasks are not done by vehicles but done by teams, so teams must be assigned to customers and teams to vehicles. However, teams and vehicles are not bound to each other, so they can be scheduled separately but should be synchronized. Moreover, the multi-stage nature of the tasks in a given order makes the problem more complex. In this paper, a mixed integer programming model is developed for the problem, and a particle swarm optimization based heuristic algorithm is proposed. Some benchmark problems and the computational results of the proposed algorithm are also presented. (C) 2010 Elsevier Ltd. All rights reserved.