Branch and price and cut for split-delivery vehicle routing problem with time windows and linear weight-related cost

摘要

Most vehicle routing problems (VRPs) assume that the cost of traversing a route is proportional to the length of the route and the objective is to minimize the total traveling distance. However, in reality the transportation cost depends upon many factors other than the distance. These include weight of the vehicle, road conditions, vehicle speed and fuel price. This study takes the weight of the vehicle and distance as the two factors that affect the cost of transportation assuming the other factors are constant. Thus, the cost of transportation can be d × f(w) where d is the distance and f(w) is a cost function depending on the weight of the vehicle. The weight related cost is important in sequencing load delivery so that higher weight goods are delivered earlier without increasing the travel distance to overshadow the gain. The article addresses a problem of extended split-delivery VRP with time windows (SDVRPTW) with the cost function as linear in load weight W. That is f(w) = a×w + b where a and b are constants. SDVRPTW is an extension of VRP with time windows (VRPTW) allowing customer demand to exceed vehicle capacity by relaxing the constraint that each customer should be visited exactly once. Though this model can address both delivery and collection of goods, this study considers only the delivery case and the problem is therefore called the split-delivery vehicle routing problem with time windows and linear weight-related cost (SDVRPTWL) where SDVRPTW becomes a special case. The collection problem can be modeled with slight modifications. (47 refs.)