Four service routes are operated by a liner shipping company. 5 days 4 days 6 days 5 days Route 1: Nansha - Chiwan Hong Kong Singapore Nansha 3 days 2 days 5 days Route 2: Tianjin Shanghai Hong Kong Tianjin 3 days 4 days 6 days 9 days Route 3: Karachi Nhava Sheva Colombo Singapore Karachi 10 days 5 days 8 days Route 4: Ningbo Los Angeles New York 2 days Tianjin Ningbo The sailing time between two ports on each route is also shown in the above figure, and the time spent at each port is assumed to be 0. Each route will serve only once. Ships 1, 2, 3, and 4 with the same capacity of 8000 containers are deployed on Routes 1, 2, 3, and 4, respectively, and each ship will depart from the first port of each route at day 0. The company receives some container shipment requests, and each request corresponds to an origin-destination (OD) pair of ports. The OD pairs, the demand, and the freight rate are shown in Table 8.1. Table 8.1: OD pair information Origin port Destination port Demand (container) Freight rate per container ($) Chiwan Singapore 2400 50 Shanghai Ningbo 1800 65 Colombo Karachi 3000 45 Karachi Nansha 1200 70 Tianjin Hong Kong 2000 45 Ningbo New York 3200 60