Illa Kesten-Kühne née Weiss

Abstract

The overwhelming part of the vehicle routing and the scheduling literature is devoted to specific problem settings such as the capacitated vehicle routing problem with time windows VRPTW, the pickup-and-delivery problem VRPPD, or the resource-constrained project planning problem RCPSP. In the operational production and distribution planning in supply chains there does however frequently come to strong interdependencies between the scheduling and routing problems, and typically there exist requirements that cannot be taken into account with the aid of basic models. Out-patient care services or spatially distributed projects constitute instances of further application areas in which routing and scheduling decisions are to be taken in common.

The resource transfer problem (RTP) developed within the context of this doctoral project offers a generic modeling framework for integrated routing and scheduling problems. We consider a set of tasks which are to be carried out in various locations in a network using nonconsumable production factors such as people, machines, and vehicles, or consumable factors like upstream and intermediate products. The tasks correspond, for example, to production processes, deliveries between locations, dispatches to customers, out-patient care services, or activities of a project. The necessary resources can be transferred between locations in the network, the transfer times generally being sequence- and resource-dependent. In the RTP model, each task is represented as the pair of respective start and completion events. Prescribed minimum and maximum time lags between the occurrence times of the events must be observed. For each event, aside from its occurrence time, an occurrence mode has to be selected, which influences the resource requirements as well as the transfer times and time lags. Problem RTP consists in assigning the allocated or released resource units to the events and scheduling them subject to the limited availability of the resources, the transfer times, and the minimum and maximum time lags. With respect to resource allocation, RTP also includes incompatibility conditions and inclusion constraints for the sets of resource units assigned to the events.

A multitude of different problems from the fields of vehicle routing, machine scheduling, and resource-constrained project scheduling, as well as their combinations, can be formulated within the framework of the RTP. Moreover, it is possible to take numerous requirements of practical routing and scheduling problems into consideration. In the field of vehicle routing, these include for example spatial and temporal synchronization, heterogenous fleets of vehicles, mixed order types, or incompatibilities between goods. The scheduling aspects of the problem setting cover alternative execution modes of tasks, sequence-dependent changeover times of resource units, spatially distributed projects, as well as minimum and maximum time lags. A time-oriented branch-and-bound algorithm, in which the search spaces of the nodes are reduced by means of advanced constraint-propagation techniques, is proposed as a solver for RTP.