Chương 1, quy trình khai thác ở cảng container gồm một chuỗi các hoạt động nối tiếp nhau.1 mô tả các hoạt động diễn ra ở 3 khu vực chính, khu vực mặt đất là các hoạt động giao nhận hàng hóa bằng xe tải hoặc tàu hỏa, kể cả hoạt động trung chuyển hàng hóa, khu vực bãi là các hoạt động bốc xếp container ra/vào các bãi, khu vực bờ là nơi tàu cập bến để giao nhận hàng hóa. Kết nối các khu vực là các xe tải nội bộ làm nhiệm vụ di chuyển container từ bờ vào bãi, giữa các bãi với nhau và ngược lại. Các nghiên cứu trước đây tập trung giải quyết các bài toán lập lịch cho hoạt động của từng loại thiết bị riêng biệt, ví dụ như lập lịch cho cầu cảng, lập lịch cho cẩu bãi, lập lịch cho cẩu bờ, lập lịch cho xe tải nội bộ hay lập lịch cho xe tải giao nhận hàng hóa. Tuy nhiên, vấn đề đặt ra là làm sao để có được danh sách các vị trí đặt container trong bãi khi tàu cập bến mà nghiên cứu của Ng W.[6] đã xem như là có sẵn.
Thêm vào đó, liệu danh sách này có hiệu quả cho các hoạt động khai thác về sau như việc xuất container từ bãi cho xe tải của khách hàng. Bên cạnh đó, nghiên cứu của Phan Thị Mai Hà[7] cũng mang đến một cái nhìn mới cho hoạt động khai thác container ở cảng biển khi xây dựng hệ thống hẹn lịch xe tải đến cảng giao nhận hàng. Để lấp đầy khoảng trống giữa những nghiên cứu này, luận văn tập trung khai thác bài toán bốc xếp container từ tàu vào bai dựa trên lịch giao nhận của khách hang. Bài toán sẽ được trình bay cu thể hơn ở phần sau.
Bai toán Trong phan nay, chúng ta xem xét một bài toán bốc xếp container cu thé với thông tin biết trước về vị trí các container trên tàu cần lưu trữ trong cảng (sau đây gọi là danh sách nhập cảng) và thời điểm mà các container này rời khỏi bãi lưu trữ xuất cho khách hàng. Ngữ cảnh thực tế như sau: e Vị trí các container cần lưu trữ trên cảng được tàu cung cấp trước khi tàu cập cảng. Thời điểm mà các container này rời khỏi bãi được khách hàng cung cấp trước khi tiễn hành bốc xếp thông qua hệ thống hen lịch TAS (Truck Appointment System). Bãi (nơi lưu trữ container của cảng) phải có sức chứa lớn hơn hoặc bằng số container cần lưu bãi trên tàu sẽ cập cảng.
Các container được dé trên tàu theo thứ tự từ trên xuống dưới (container nằm II Truck Arrivals | Landside Operations Transfer Areas Rail Dock | Container Storage Yard for. | Imports and Exports Yard Operations | | — mì AeeeHH es Quayside Berths A O = 0) < = 2. © O oO ® ee |pe) = © = a Ỷ Vessel Arrivals Hình 3.1: Cac hoạt động khai thác ở cảng container trên thì lay trước). Trong quá trình bốc đỡ container từ tàu, các container có thể được đặt trực tiếp lên các xe tải trung chuyển đến các bãi hoặc đặt vào bãi tạm bên cạnh khi chưa thể sắp ngay vào bãi.
Chi phí cho một container ở bãi tạm gấp đôi bình thường vì tốn 2 lần di chuyển của cẩu bờ. Các container được xếp vào bãi lưu trữ từ dưới lên trên (xếp chồng lên nhau, gọi là các /ớp - tier). Các contaner trên bãi được giao cho khách hàng cũng phải được bốc theo thứ tự từ trên xuống dưới (do xếp chồng lên nhau nên phải lay container ở trên trước), néu container cần giao cho khách hàng được nằm ở vi trí bên dưới một hoặc nhiều container khác thì các container đó phải được bốc ra vùng tạm để lấy container cần thiết giao cho khách hàng (gọi là đảo chuyển), chi phí này do cảng chịu. Mục tiêu của bài toán là tìm phương án bốc xếp container từ tàu vào bãi sao cho tổng chi phí bốc xếp từ tàu và chi phí xuất bãi là nhỏ nhất (hạn chế sử dụng bãi tạm và đảo chuyển).
12 Quay crane Yard crane Vessel Hình 3.2: Minh họa quy trình bốc xếp container ở cảng biển 3. Cac ràng buộc chính Với mục đích tìm phương án bốc xếp container từ tàu lên bãi sao cho tổng chi phí bốc xếp từ tàu và chi phí xuất bãi là nhỏ nhất, bài toán được cu thể như sau: e Khi bốc cont trên tàu để xếp lên bãi chính phải đảm bảo việc sử dụng bãi tạm là ít nhất có thể — Bãi chính phải có sức chứa lớn hơn hoặc bằng số lượng các container cần bốc từ tàu và được ký hiệu theo chuẩn vàùng-đãy-hàng-lớp (tương ứng là block-bay-row-tier). — Vùng tạm có một lớp duy nhất. e Thứ tự sắp xếp trên bãi chính phải đảm bảo khi khách hàng vào lay container theo lich hẹn trước thì không phải đảo chuyển.
Trong đó, ta phải chú ý đến: — Bãi chính là nơi container được lưu trữ và xuất cho khách hàng. Bãi chính được tổ chức theo dạng các cột sắp gần nhau trong một không gian nhất định (hình hộp chữ nhật). — Việc bốc dỡ container ở hai cột khác nhau trong bãi chính là độc lập với nhau. Các container trong cùng một cột phải được bốc dỡ từ trên xuống dưới.
— Việc đảo chuyển sẽ không xảy ra khi container có lịch xuất bãi trước được đặt phía trên các container có lịch xuất bãi sau nó (trong cùng một cột). e Chi phí bốc xếp được xác định dựa trên số lần di chuyển container từ vị trí này sang vị trí khác (tàu, vùng tạm, bãi chính).4 Giai pháp Từ đặc tả của bài toán nêu trên, ta có thể hình dung được giải pháp cho bài toán giảm thiểu chi phí bốc xếp ở cảng container được thiếp lập như sau: e Các container được sắp xếp ở bãi lưu trữ (sau đây gọi là bãi chính) sao cho trong cùng một cột thi container có lịch giao nhận trước phải được sap ở trên; 13 e Các container được bốc xếp từ tàu vào bãi chính phải tuân theo quy tắc sắp xếp trên; e Trong quá trình bốc dỡ container từ tàu, néu không thể sắp một container nào đó theo quy tắc trên, thì có thể chuyển container đó vào bãi tạm cạnh cẩu bờ; e Container ở bãi tạm sau đó được cân nhắc để sắp vào bãi chính tại thời điểm thích hợp mà không vi phạm quy tắc sắp xếp; Như đã phân tích ở trên, các container trên tau và bãi chính được tổ chức theo dạng bay-row- fier trong không gian 3 chiều. Việc sắp xếp này cũng có thể được biểu diễn thành những cột độc lập với nhau trong không gian 2 chiều column-tier với tổng sô cột là tích số của số lượng bay và row tương ứng. Nhờ đó, bài toán cũng được rút giảm số chiều cần tính toán.
Trong hình minh họa dưới đây, quy ước lịch giao nhận các container theo thứ tự trước-sau tương ứng với chỉ số của mỗi container, là phương án bốc xếp contaner từ tàu vào bãi có sử dụng bãi tạm. 3 |14 | 13 5 | 4 1 2193115 6 7 2 5 | 6 | 10 9 |10| 3 7 |12 4 13 |12 | 8 8 | 1 |11 14 | 15 | 11 I3l2z[|_- | Vessel Main Yard Temp yard Hình 3.3: Minh họa phương án bốc xếp container từ tau vào bãi 3.5 Các trường hợp đặc biệt Một cách lý tưởng, tổng số lần di chuyển các container bằng với tổng số container trong danh sách nhập cảng, hay nói cách khác các container được di chuyển trực tiếp từ tàu vào bãi chính mà không cần phải thông qua bãi tạm. Trong trường hợp này, giá trị mục tiêu bằng với tổng số container cần được bốc. Tuy nhiên, có những trường hợp mà bắt buộc phải sử dụng bãi tạm để tuân thủ quy tắc sắp xếp các container ở bãi chính.
Trong trường hợp đó, giá trị mục tiêu lớn hơn tổng số container vì phải bao gồm cả chi phí phát sinh cho các container ở bãi tạm. Dưới đây ta tìm hiểu các trường hợp đặc biệt này. Gọi hị, w lần lượt là chiều cao và chiều rộng của các cột trên tàu (với w là tổng số cột trên tàu); hạ, wa lần lượt là chiều cao và chiều rộng của các cột trên bãi chính (với w2 là tổng số cột trên bãi chính). Ta xét 3 trường hợp sau: a) hy < wy Ở trường hợp này, luôn tổn tại một lời giải sao cho không cần dùng đến bãi tạm mà vẫn có thể bốc các container vào bãi chính thỏa mãn các ràng buộc của bài toán.
Xét một cột bất kỳ trên tàu, giả sử bất kỳ hai container nào trong cột cũng không thể xếp vào một cột trên bãi chính vì sự ràng buộc về quy tắc sắp xếp các container trong bãi. Khi đó, vì chiều cao của mỗi cột trên tàu nhỏ hơn số cột trên bãi nên ta có thể xếp tất cả các container này lần lượt vào mỗi cột trên bãi chính mà không vi phạm ràng buộc của bài toán. 14 b) hy =w2 Tượng tự, trường hợp nay cũng luôn tổn tại một lời giải sao cho không cần dùng đến bãi tam mà vẫn có thể bốc các container vào bãi chính thỏa mãn các ràng buộc của bài toán. c) hy >W›2 Với điều kiện này, có thể có những trường hợp mà một hoặc một vài container bắt buộc phải được chuyển đến bãi tạm để thỏa mãn các ràng buộc của bài toán.
e Quy luật số 1: số container theo thứ tự tăng dan ở một cột trên tàu lớn hơn chiều rộng của bãi chính. Xét từ trên xuống dưới ở mỗi cột trên tàu, néu tồn tại những container có thứ tự tăng dan (có thể bị ngắt quãng) sao cho tổng số container đó (tạm gọi là m) lớn hơn chiều rộng của bãi chính, thì số container phải bốc vào bãi tạm bằng với hiệu số m— wp. 3 | 14 | 13 4| 9 |15 2 |6 |10 7 |12| 5 2 8 | 1 |11 314 |1 7 Vessel Main Yard Hình 3.4: Trường hợp bắt buộc sử dụng bãi tạm Chứng minh: xét những container theo thứ tự tăng dần này — Vì thứ tự các container này là tăng dần nên không thể bốc 2 container trong đó vào cùng | cột, — vim > wa nên chỉ có tối đa w2 container được bốc vào các cột trên bãi chính, — như vậy, các container còn lại phải được bốc vào bãi tạm để không vi phạm ràng buộc sự phụ thuộc về thứ tự các container trong bãi chính. Trong hình họa trên, container số 8 không thể được sắp vào bãi chính vì 3 container trước đó là 3,4 và 7 có số thứ tự nhỏ hơn 8.
Trong trường hợp này, một trong 3 container 3, 4 hoặc 7 phải được sắp vào bãi tam để dành chỗ cho container số 8 trong bãi chính.