VRP12 (vehicle routing problem with distances one and two) with side constraints

Abstract

The problem undertaken in this study is inspired from a real life application. Consider a vehicle routing problem where the distances between the customer locations are either one or two. We name this problem as VRP12 in an analogy for the name TSP12 used for the traveling salesman problem in the literature. Additionally, assume that, the time to visit each customer is not constant and the visiting time together with the travel time constitutes the capacity of the vehicle. Furthermore, each customer has two characteristics and any two customers having a common characteristic should not be visited at the same time. If visited, a penalty fee incurs. In this study, we give the formulation of this problem and suggest some simple but effective algorithms that can be used to solve it. The algorithms are built with the relaxation of the side constraints but their performances are evaluated with their success in satisfying them. Information on our case study is also provided.