A split delivery vehicle routing problem

We consider a standard vehicle routing problem, i.e. a routing problem where all nodes (customers) should be visited only once by only one vehicle and without exceeding a vehicle's capacity. The objective function minimizes total distance traveled. In this paper, we relax the first standard problem condition. We call this problem the Split Delivery Vehicle Routing Problem (SDVRP). The term "split delivery", means, as long as the total delivery equals the demand, the demand may be satisfied using more than one vehicle. Under the relaxed condition, we are able to reduce the number of vehicles and the total distribution cost (time). Hence, it will find practical application. SDVRP has been little researched. On a mathematical programming base, Suzuki et al. (1987) suggested an exact algorithm using a Branch and Bound Method for this problem. But it is only useful for a small number of nodes. On a local search base, Doror and Trudeau (1990) proposed heuristic algorithm. In this paper, we take another formulation. Solving this problem on mathematical programming base, we decompose it into two problems: First, a problem of which vehicle serves the node and to what extent each vehicle serves each node. Second, the problem of the route that each vehicle takes. This idea is based on Fisher and Jaikumar (1981) whose solutions is very good one for a standard vehicle routing problem. The second problem is the Traveling Salesman Problem. Therefore, the first problem is the essential one. We suggest that by method of Fisher (1985) we can generate a heuristic solution from the Lagrangean Solution for the first problem. From this we are able to solve a large size SDVRP.