Consider the Pickup and Delivery Problem. Here customers are pickup customers with probability p and delivery customers with probability 1−p.

Assume a vehicle capacity of 1. If customer i is a pickup customer, then a load of size wi ≤ 1 must be picked up at the customer and brought to the depot. If customer i is a delivery customer, then a load of size wi ≤ 1 must be brought from the depot to the customer. Assume pickup sizes are drawn randomly from a distribution with bin-packing constant γP and delivery sizes are drawn randomly from a distribution with bin-packing constant γD. A pickup and a delivery can be in the vehicle at the same time.

(a) Develop a heuristic H for this problem and determine limn→∞

ZH n as a function of p, γP and γD.

(b) Assume all pickups are of size 13and deliveries are of size 2 3 . Suggest a better heuristic for this case. What is limn→∞

ZH n as a function of p for this heuristic?