Vehicle routing and appointment scheduling with team assignment for home services

In home services (such as home care), a service provider (with a set of service teams) provides services to a set of geographically distributed customers. A critical operations decision in such services is to assign and route the service teams, while making appointment times for the customers so as to efficiently deliver the services. For this purpose, we consider a simultaneous routing and appointment scheduling problem with team assignment. We build a scenario-based mixed integer program and develop an algorithm based on Tabu Search (TS) method to efficiently solve the problem. Our computational experiments show that the TS-based algorithm works quite well. Specifically, compared with known optimal solutions on small-size problem instances, the algorithm efficiently produces optimal solutions for 38 out of 40 instances and near-optimal solutions for the other 2 instances. Moreover, the algorithm significantly outperforms the approach that separately optimizes assignment, routing, and appointment scheduling.