Milk-run routing and scheduling subject to different pick-up/delivery profiles and congestion-avoidance constraints

Two kinds of intertwined decisions: the routing decisions, which determine the set of sequences of stations visited by each tugger train's route, and the scheduling decisions, which plan congestion-free movements of tugger train fleets, are considered. The problem under study can be seen as extension of the pick-up and delivery problem with time windows in which different profiles of separately executed delivery and pick-up operations are assumed. The NP-hard character of the problem considered follows from its roots derived from the vehicle routing and the deadlock-avoidance problems. In this regard, a constraint programming paradigm allowing the further integration of multi-period, multi-trip and multi-commodity flows with various customers' demands as well as distribution network topology constraints is applied. Consequently, a recursive formulation of a well-known constraint satisfaction problem is proposed. The computer experiments provided illustrate the possibility of using the approach presented in systems of real-life scale.