The vehicle sharing and task allocation problem: MILP formulation and a heuristic solution approach

In many customer service operations, workers visit customer locations to perform on-site service tasks. Each worker drives a vehicle and so the task allocation problem is often solved as a vehicle routing problem. However, unlike delivery services, the workers spend the majority of their time working on the service tasks leaving the vehicles idle. This creates a possibility of sharing vehicles among the workers to save vehicles used and reduce the total carbon emissions. This paper studies this new problem of vehicle sharing and task allocation. Given the team of workers and a set of customer tasks with their locations and time requirements, decisions need to be made on the scheduling of workers to tasks, workers sharing each vehicle and the routing of the vehicles. We first formulate the problem as an integer programming model. To solve larger problem instances, a three-phase heuristic algorithm is then developed. Computational experiments are carried out to demonstrate the benefits of sharing vehicles. The effects of problem parameters on the solution are also investigated.