Program > By author > Schwindt Christoph

In this talk we propose the resource transfer problem (RTP), a framework for modeling and solving rich vehicle routing and resource-constrained scheduling problems in a unified way. Basically, the RTP consists in scheduling a set of activities to be performed at different locations in a network using a set of vehicles and further resources like personnel, machines, or handling facilities. The activities may represent pickups and deliveries, visits of patients to ambulant medical care services, or tasks of multiple projects distributed over different sites. They have to be scheduled subject to generalized precedence relations defining minimum and maximum time lags between their start or completion times. Certain resources are shared among the locations, causing resource transfers in the network. The transfers are operated by a fleet of heterogeneous vehicles, which may, e.g., differ in load capacities, driving speeds, or access limitations.

Within the RTP framework, we are able to model different types of VRP's, scheduling problems, and their combinations. Moreover, we can include a great variety of further side constraints arising in practical vehicle routing and scheduling applications. Examples of problem settings covered by the RTP are the dial-a-ride problem, the VRP with backhauls, the VRP with pickup and delivery, multi-mode resource-constrained project scheduling problems, or multi-site scheduling problems. As a solver for RTP we present a time-oriented branch-and-bound algorithm employing constraint propagation to prune the search space. We report on preliminary computational experience with the algorithm.