A computational study of a new heuristic for the site-dependent vehicle routing problem

In the site-dependent vehicle routing problem, a fleet of heterogeneous vehicles services a set of customers. Typically, there are several vehicle types (for example, small-, medium-, and large-capacity vehicles). In addition, there is a compatibility relationship between the customers and the vehicles. For example, some customers located in congested, urban areas can be serviced only by small-capacity vehicles, while some customers located in suburban areas can be serviced by any type of vehicle. In this paper, we develop a new heuristic for solving the site-dependent vehicle routing problem and apply it to a set of 23 test problems (six problems have appeared in the literature, 12 problems are new ones that we generated, and five problems are adaptations of well-known vehicle routing test problems). Our computational study indicates that the new heuristic is efficient and produces reasonably good solutions to moderate-size problems.