TY - JOUR

T1 - A split delivery vehicle routing problem

AU - Mohri, Hitoaki

AU - Kubo, Mikio

AU - Yajima, Yasutoshi

AU - Mori, Masao

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0001199997&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001199997&partnerID=8YFLogxK

U2 - 10.15807/jorsj.39.372

DO - 10.15807/jorsj.39.372

M3 - Article

AN - SCOPUS:0001199997

SN - 0453-4514

VL - 39

SP - 372

EP - 387

JO - Journal of the Operations Research Society of Japan

JF - Journal of the Operations Research Society of Japan

IS - 3

ER -