Warehouse order picking, Ratliff and Rosenthal (1983). In a rectangular warehouse, a stacker overhead crane is used to pick and deliver orders between specified locations in the warehouse. The tasks of the crane involve the following: (1) picking a load at a location, (2) delivering a load to a location, and (3) moving unloaded to reach a picking location. Suppose that there are n orders to be picked and delivered.

The goal would be to complete all the orders while minimizing the unproductive time of the crane [item (3)]. The unproductive times can be computed based on the pickup and delivery locations of the orders and the lateral and traversal speeds of the crane, among other factors. For the purpose of this situation, the crane starts on the orders from an idle state and also terminates in an idle state after all orders are completed.

For a specific pool of eight orders, the times (in minutes) to reach the locations of orders 1, 2,

c, and 8 from idle state are .1, .4, 1.1, 2.3, 1.4, 2.1, 1.9, and 1.3, respectively.

The following table provides the unproductive times (in minutes) associated with the sequencing of the orders:

‘tij ‘ = ®

0 1.0 1.2 .5 1.7 .9 1.3 .7 1.1 0 .9 2.0 .8 1.1 .3 .5 1.2 1.9 0 1.4 .4 1.0 1. 1.6 1.5 2.3 .4 0 2.0 1.5 2.8 1.

1.2 1.8 1.4 2.5 0 2.1 .4 .9

.9 1.1 1.0 .5 2.1 0 .2 .3 1.3 .8 1.1 2.2 1.4 .6 0 1.2 1.7 1.5 1.6 1.0 1.9 .9 2.0 0



(a) Define the cities and distance matrix of the TSP model.

(b) Determine a lower bound on the unproductive time during the completion of all orders.