Pickup and Delivery of Partial Loads with “Soft” Time Windows

Abstract

We apply Benders' decomposition procedure to the single-vehicle routing and scheduling problem with time windows, partial loads, and dwell times. We provide a formulation and demonstrate that the scheduling subproblem is the dual of a network flow problem. We describe an exact algorithm which exploits its structure, and construct a route improvement heuristic based on the master problem. A heuristic for building an initial route is also presented.