Blockage-Free Route Planning for In-Plant Milk-Run Material Delivery Systems

In this chapter, two kinds of intertwined decisions regarding the movement of vehicles in an in-plant milk-run delivery system are considered: routing decisions, which determine the set of sequences of stations visited by each tugger train, and scheduling decisions, which plan congestion free movement of the tugger trains. The problem under study, called the Multi Trip and Multi Cycle Pick-up and Delivery Problem with Time Windows and Congestion Free Traffic, can be viewed as an extension of the pick-up and delivery problem with time windows in which multiple tugger trains travel along closed-loop congestion-free routes in different cycles. A declarative model of the investigated milk-run delivery principle makes it possible to formulate a vehicle routing and scheduling problem the solution to which determines the route, the time schedule, and the type and number of parts that the different trucks must carry to fulfill orders from various customers/recipients. Due to the requirement of congestion-free milk-run traffic, a scheduling period slicing principle allowing to synchronize cyclic flows of different periods is applied. Its implementation, resulting in a cyclic schedule composed of quasi cyclic sub-schedules, implies a recursive formulation of a well-known constraint satisfaction problem. The goal is to find solutions that can minimize both vehicle downtime and the takt time of the production flow. Computer experiments illustrate the possibility of using the present approach in real-life systems.