Tối ưu điều độ tàu Container với ràng buộc cầu cảng liên tục tại cầu cảng bằng giải thuật Simulated Annealing Lai

Tạp chí Khoa học Công nghệ và Thực phẩm 20 (4) (2020) 110-115 110 TỐI ƯU ĐIỀU ĐỘ TÀU CONTAINER VỚI RÀNG BUỘC CẦU CẢNG LIÊN TỤC TẠI CẦU CẢNG BẰNG GIẢI THUẬT SIMULATED ANNEALING LAI Hoàng Trọng Trần Huy, Nguyễn Lê Nam, Nguyễn Vũ Anh Duy* Trường Đại học Công nghiệp Thực phẩm TP.HCM *Email: duynva@hufi.edu.vn Ngày nhận bài: 12/7/2020; Ngày chấp nhận đăng: 03/9/2020 TÓM TẮT Vận chuyển hàng hóa bằng container trở nên phổ biến khắp thế giới và tại Việt Nam bởi tính ưu việt của nó. Bên cạnh đó, sự cạnh tranh trong vận chuyển container lại trở nên khốc liệt hơn bao giờ hết. Nghiên cứu này tập trung giải quyết vấn đề điều độ tàu container trong cảng với nhiều cầu tàu và dựa trên giả sử cầu cảng là liên tục nhằm tăng năng suất cho cảng. Trong nghiên cứu này, mô hình toán học được lập và một giải thuật meta-heuristic sẽ được đề xuất để tìm kiếm lời giải gần tối ưu cho bài toán. Lời giải của giải thuật meta-heuristic lai sẽ được so sánh với trình tự kinh nghiệm thông thường hay áp dụng tại cảng là tàu đến trước phục vụ trước (First come first served, FCFS). Từ khóa: Điều độ, tối ưu hóa, meta-heuristic, cầu cảng, cảng container 1. GIỚI THIỆU Vận chuyển hàng hóa toàn cầu có xu hướng tăng không ngừng về lượng hàng hóa và mức độ cạnh tranh giữa các công ty trên thị trường. Đối với các cảng container đường sông và đường biển, không gian cầu cảng là giới hạn về khả năng tiếp nhận và phục vụ tàu. Do đó, việc tăng năng suất phục vụ của cầu cảng sẽ ảnh hưởng đến khả năng cạnh tranh của cảng trong việc phục vụ tàu vận chuyển container. Nghiên cứu của Bierwirth & Meisel tổng hợp các nghiên cứu gần đây trên thế giới [1]. Trên thế giới, đề tài này đã được nghiên cứu nhiều, một số nghiên cứu kết hợp giữa việc điều phối tàu và cẩu bờ. Nghiên cứu của Chang et al. [2] dùng mô hình bài toán động để giải quyết vấn đề phân phối tàu vào cảng kết hợp với việc điều phối cần cẩu bờ. Bài báo đã dùng giải thuật di truyền song song lai giữa giải thuật di truyền song song và giải thuật kinh nghiệm để giải quyết vấn đề. Nghiên cứu của Emde & Boysen kết hợp với tàu cấp container [3]. Một số công trình nghiên cứu chỉ tập trung giải quyết vấn đề điều phối tàu container vào bến cảng [4-8]. Tuy nhiên, các nghiên cứu này khó lòng được vận dụng tại Việt Nam do các cảng tại nước ta không có sự đồng bộ về thiết bị. Hiện tại, việc bốc xếp container lên xuống tàu hàng, và việc bố trí tàu vào cảng chủ yếu vẫn dựa trên kinh nghiệm của người vận hành. Do đó, việc điều hành không được tối ưu, nhất là đối với kích thước bài toán lớn. Ở Việt Nam, những nghiên cứu về vấn đề này vẫn chưa được nghiên cứu nhiều. Trong bài báo này, nhóm tác giả nghiên cứu việc tối ưu hóa trình tự phục vụ tàu trong cầu cảng với mục tiêu cực tiểu hóa thời gian đợi của tất cả các tàu trong cảng. Vì bài toán thuộc dạng NP (nondeterministic polynomial time) nên nhóm tác giả đã đề xuất một giải thuật SA (Simulated Annealing) lai với một giải thuật kinh nghiệm để tìm kiếm lời giải gần tối ưu của bài toán. Kết quả tính toán của giải thuật sẽ được so sánh với một quy luật kinh nghiệm thường được áp dụng tại các cảng, tàu đến trước phục vụ trước (First come, first served). Tối ưu điều độ tàu container với ràng buộc cầu cảng liên tục tại cầu cảng bằng giải thuật 111 Bài báo này được bố cục như sau: phần 2 mô tả vấn đề tối ưu hóa công việc tại cầu cảng, phần 3 sẽ đưa ra giải thuật để tìm lời giải gần tối ưu cho bài toán, phần 4 là thực nghiệm số, và phần 5 kết luận bài báo. 2. MÔ TẢ VẤN ĐỀ Vấn đề điều độ tàu vào cầu cảng được áp dụng trong nghiên cứu này là cầu cảng liên tục. Trên thế giới, việc điều độ cầu cảng chia làm 2 hướng, cầu cảng rời rạc và cầu cảng liên tục. Trong vấn đề cầu cảng rời rạc, cầu cảng sẽ được chia thành các đoạn bằng nhau, khi tàu đến một số đoạn sẽ được sắp xếp cho tàu vào. Trong cách tiếp cận như vậy, khoảng cách giữa các tàu phải cố định theo khoảng chia, do đó không tận dụng hết chiều dài cầu tàu, nếu tàu quá ngắn hoặc quá dài. Với cách tiếp cận cầu tàu liên tục, cầu tàu là một khoảng liên tục, các tàu sẽ được bố trí nối tiếp nhau sao cho không vi phạm khoảng cách an toàn giữa các tàu. Với phương án tiếp cận này, việc điều độ sẽ khó khăn hơn, nhưng sẽ hiệu quả hơn phương án rời rạc vì sẽ không có khoảng trống thừa nằm giữa các tàu. Đối với cảng nước ta, do thiết bị không đồng bộ, nhiều loại cầu bờ khác nhau được sử dụng đồng thời nên mỗi tàu khi đến sẽ có vị trí mà nó được phục vụ tốt nhất, nhưng khi không được cập bến tại vị trí tốt nhất đó thời gian được phục vụ sẽ tăng lên và trong nghiên cứu này mức độ tăng thời gian sẽ được xem xét. Trong bài báo này, mô hình toán của vấn đề được lập như bên dưới. Những ký hiệu sau sẽ được dùng trong mô hình toán của vấn đề, ngoài ra Hình 1 cũng mô tả một số thông số của tàu được liệt kê bên dưới: i, j Chỉ số của tàu, ,i j V V Tập hợp các tàu đến cảng  1,2,3,...,V n= N Tổng số tàu đến cảng trong khoảng thời gian cần điều phối L Chiều dài cầu cảng ia Thời điểm tàu i đến bến cảng w i Trọng số của tàu i, phụ thuộc vào độ ưu tiên của tàu. ip Thời gian dự kiến để phục vụ tàu i il Chiều dài của tàu thứ i s Khoảng cách an toàn giữa 2 tàu t Khoảng thời gian an toàn giữa 2 tàu được phục vụ tải cảng Biến quyết định: if Thời điểm tàu i được phục vụ xong. is Thời điểm bắt đầu phục vụ tàu i iv Vị trí của điểm giữa tàu tính từ gốc tọa độ của cầu cảng p ijt Hệ số chồng lấn về không gian, = 1 nếu không trùng lấn, = 0 ngược lại ij tt Hệ số chồng lấn về thời gian, = 1 nếu không trùng lấn, = 0 ngược lại Hoàng Trọng Trần Huy, Nguyễn Lê Nam, Nguyễn Vũ Anh Duy 112 Tàu i Thời gian Vị trí li pi vi si fi Hình 1. Mô hình bài toán Mô hình toán Hàm mục tiêu: Min ( ) 1 w n i i ii f a = − (1) Ràng buộc: ( )ij , , 2 i jp p i j ji l l v v t s t i j i V +  −  +       (2) ( ), , , 2 2 2 j j i jt ti i ij ji f s p pf s t t t i j i V + + + −  +       (3) ( )1 , ,p tij ijt t i j i V+ =    (4) 0 , 2 i i l v i V−    (5) , 2 i i l v L i V+    (6) ( )max ,0 ,i is a t i V +   (7) , 0 ,i iv s i V   (8)   ( ),t 0,1 , ,t pij ijt i j i V    (9) Trong mô hình toán ở trên, (1) là hàm mục tiêu, chúng ta tìm cực tiểu của tổng theo trọng số của thời gian tàu lưu tại cảng. (2), (3), (4) là ràng buộc chống sự chồng lấn lẫn nhau của các tàu theo 2 phương, không gian và thời gian. Ràng buộc (5) và (6) đảm bảo tàu chỉ có thể được neo đậu trong phạm vi của cầu cảng. Ràng buộc (7) thể hiện tàu chỉ được phục vụ sau khi đã đến bến cảng. Ràng buộc (8) và (9) là điều kiện biên. Bài toán được mô hình dựa trên bài toán cutting stock 2d, đây là bài toán không có lời giải trong thời gian tính toán tuân theo hàm đa thức (NP, nondeterministic polynomial computation time). Do đó, trong phần kế tiếp của bài báo giải thuật meta-heuristic lai được đề xuất để tìm nghiệm gần tối ưu cho bài toán. 3. GIẢI THUẬT SIMULATED ANNEALING (SA) Để tìm kiếm lời giải gần tối ưu cho bài toán NP, giải thuật SA được đề xuất. Giải thuật SA là một trong những giải thuật meta-heuristic, có khả năng quay lui để thoát khỏi tối ưu cục bộ. Giải thuật SA trong nghiên cứu này được kết hợp với một giải thuật kinh nghiệm để khởi tạo lời giải ban đầu nên gọi giải thuật trong bài là giải thuật lai. Để sử dụng giải thuật này, một Tối ưu điều độ tàu container với ràng buộc cầu cảng liên tục tại cầu cảng bằng giải thuật 113 lời giải ban đầu được tạo ra sao cho các ràng buộc về không gian và thời gian được thỏa, ràng buộc số 2, số 3 và số 4. Tạo lời giải ban đầu Trong bài báo này, quy luật thời gian phục vụ ngắn nhất được ưu tiên phục vụ trước (SPT, Shortest Processing Time) được áp dụng để tạo lời giải ban đầu. Tuy nhiên, việc xung đột về vị trí và thời gian của các tàu sẽ xảy ra, ràng buộc (2) và (3). Trong trường hợp đó, tàu có xung đột về vị trí và thời gian phải chờ đợi đến khi những xung đột này không còn nữa. Tạo lời giải lân cận Lời giải lân cận được tạo ra bởi lời giải hiện hành bằng cách thay đổi ngẫu nhiên vị trí của một tàu sang trái hay sang phải một đoạn 1 m. Thời điểm phục vụ của từng tàu cũng sẽ thay đổi ngẫu nhiên sớm hơm 10 phút hoặc trễ 10 phút. Những thay đổi nhỏ đó sẽ thay đổi một lời giải hiện hành sang một lời giải lân cận, trong quá trình thay đổi nếu ràng buộc (2) và (3) không thỏa. thì trình chỉnh sửa lời giải sẽ tiến hành. Việc chỉnh sửa để cho ràng buộc không gian và thời gian luôn thỏa. Hai quy luật sau sẽ được tiến hành: Luật 1, dời vị trí tàu đang lỗi ràng buộc ra khỏi không gian của tàu được chọn. Cộng hoặc trừ vị trí tâm của tàu bị lỗi với một con số sao cho vị trí không còn bị lỗi. Việc cộng hoặc trừ được chọn sao cho trị tuyệt đối của giá trị là nhỏ nhất. Luật 2, lùi thời điểm phục vụ tàu đang bị lỗi ràng buộc với tàu được chọn ra khỏi miền thời gian phục vụ của tàu được chọn. Trong hai luật này, luật có giá trị hàm mục tiêu nhỏ hơn sẽ được chọn. Chiến lược làm nguội của giải thuật được tiến hành theo hàm mũ, (10), và giải thuật được ngừng lại khi giới hạn xác suất, T, nhỏ hơn khoảng cho phép,  . Hình 2 sẽ thể hiện lưu đồ thuật toán. T T =  (10) 4. THỰC NGHIỆM SỐ Trong mục này thuật toán sẽ được sử dụng để tính toán các kích thước khác nhau của bài toán. Thuật toán được viết bằng ngôn ngữ Java, và chạy trên máy tính có cấu hình core i3, ram 8Gb và hệ điều hành Window 10 SL. Các thông số của giải thuật như sau: T = 1000, 0, 999999 = và 0, 01 = số lượng tàu được điều độ từ 4 đến 16 tàu. Với số lượng này là phù hợp với khoảng thời gian điều độ cho một vài ngày làm việc tại cảng. Mỗi trường hợp giải thuật được chạy 7 lần, giá trị mục tiêu được lấy là giá trị trung bình. Ngoài ra, độ lệch chuẩn cũng được tính toán. Giá trị hàm mục tiêu trong cột A và C (Bảng 1) thể hiện tổng có trọng số thời gian lưu tại cảng của các tàu (flowtime) với thứ nguyên là thời gian. Trong nghiên cứu này, thời gian được định nghĩa là giới hạn về khoảng thời gian nhỏ nhất có thể chấp nhận, đó là thời gian để một cẩu bờ di chuyển giữa hai dãy container. Chiều dài của cầu cảng khoảng 1500 m, và chiều dài của tàu được chọn ngẫu nhiên trong khoảng 300-500 m. Qua Bảng 1, ta thấy rằng thời gian tính toán của giải thuật từ 5 đến 50 giây, điều này phù hợp với việc điều độ cho khoảng thời gian làm việc từ 1 ngày làm việc. Thời gian tính toán đủ nhỏ cho nhân viên điều độ có thể chờ đợi để có lời giải của một bài toán NP. Độ lệch chuẩn dưới 5% của giá trị hàm mục tiêu. Trong cột cuối cùng của Bảng 1, giá trị hàm mục tiêu của giải thuật được so sánh với quy luật đến trước làm trước (cột C), quy luật này thường được áp dụng tại các cảng. Giải thuật được bài báo đề xuất có thể giảm trung bình 49,9% (trung bình tổng của cột cuối cùng Bảng 1). Hoàng Trọng Trần Huy, Nguyễn Lê Nam, Nguyễn Vũ Anh Duy 114 Đúngε>T? Bắt đầu End Sai Khởi tạo lời giải ban đầu (SPT) Khởi tạo lời giải lân cận từ lời giải hiện hành Cập nhật lời giải hiện hành bằng lời giải lân cận Đúng Lời giải lân cận tốt hơn lời giải hiện hành ? Hoặc thành phần ngẫu nhiên nhỏ hơn xác suất cho phép? Đúng Lời giải hiện hành tốt hơn lời giải tốt nhất? Cập nhật lời giải tốt nhất bằng lời giải hiện hành T= T× π Sai Sai Hình 2. Lưu đồ thuật toán SA Bảng 1. Kết quả tính toán của giải thuật STT Số lượng tàu SA FCFS (C) So sánh ( ) ( ) 100% B A  So sánh ( ) ( ) ( ) 100% C A A −  Hàm mục tiêu (A) Độ lệch chuẩn (B) Thời gian tính toán (giây) 1 4 110,00 0,00 5 110 0,00 0,00 2 5 170,00 0,00 6 440 0,00 61,36 3 6 247,00 6,21 8 530 2,51 53,40 4 7 358,57 14,12 10 650 3,94 44,84 5 8 428,43 1,59 12 1030 0,37 58,40 6 9 536,14 9,85 12 1180 1,84 54,56 7 10 578,29 24,89 23 1370 4,30 54,74 8 12 770,00 0,00 17 1580 0,00 51,27 9 14 802,57 17,39 29 1955 2,17 58,95 10 16 922,86 32,54 50 2220 3,53 58,43 5. KẾT LUẬN Bài báo đã đề xuất được một giải thuật có thể điều phối tàu vào cầu cảng với mục tiêu cực tiểu tổng có trọng số tổng thời gian phục vụ và thời gian hoàn thành tàu cuối cùng. Giải Tối ưu điều độ tàu container với ràng buộc cầu cảng liên tục tại cầu cảng bằng giải thuật 115 thuật là sự kết hợp của quy luật SPT (thời gian phục vụ ngắn nhất) và giải thuật SA truyền thống. Quy luật SPT được sử dụng để tạo lời giải ban đầu cho giải thuật SA truyền thống. Khi so sánh giá trị hàm mục tiêu so với quy luật vận hành thông thường tại các cảng, giải thuật được đề xuất giảm được trung bình 49,9%. Ngoài ra, thời gian tính toán của giải thuật là có thể chấp nhận được cho một ngày làm việc. Bài toán có thề được mở rộng trong các nghiên cứu sau theo hướng kết hợp việc điều phối tàu và cần cẩu bờ hoặc chuyển đổi sang mô hình thống kê. TÀI LIỆU THAM KHẢO 1. Bierwirth C., Meisel F. - A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research 244 (3) (2015) 675-689. 2. Chang D., Jiang Z., Yan W., He J. - Integrating berth allocation and quay crane assignments. Transportation Research Part E: Logistics and Transportation Review 46 (6) (2010) 975-990. 3. Emde S., Boysen N. - Berth allocation in container terminals that service feeder ships and deep-sea vessels, Journal of the Operational Research Society 67 (4) (2016) 551-563. 4. Golias M.M., Boile M., Theofanis S. - A lamda-optimal based heuristic for the berth scheduling problem, Transportation Research Part C: Emerging Technologies 18 (5) (2010) 794-806. 5. Kim K.H., Park K.T. - A note on a dynamic space-allocation method for outbound containers, European Journal of Operational Research 148 (1) (2003) 92-101. 6. Imai A., Sun X., Nishimura E., Papadimitriou S. - Berth allocation in a container port: using a continuous location space approach, Transportation Research Part B: Methodological 39 (3) (2005) 199-221. 7. Nishimura E., Imai A., Papadimitriou S. - Berth allocation planning in the public berth system by genetic algorithms, European Journal of Operational Research 131 (2) (2001) 282-292. 8. Venturini G., Iris Ç., Kontovas C.A., Larsen A. - The multi-port berth allocation problem with speed optimization and emission considerations, Transportation Research Part D: Transport and Environment 54 (2017) 142-159. ABSTRACT BERTH SCHEDULING FOR CONTAINER TERMINAL IN VIETNAM WITH HYBRID SIMULATED ANNEALING ALGORITHM Hoang Tran Trong Huy, Nguyen Le Nam, Nguyen Vu Anh Duy* Ho Chi Minh City University of Food Industry *Email: duynva@hufi.edu.vn The use of container has become widespread because of their advantages. Moreover, the competition in the container transportation is more and more intense. In this paper, we consider the scheduling problem of vessel in berth with the continuous assumption in order to increase the throughput of container terminals. A mixed integer programming model is built. A hybrid meta-heuristic algorithm is suggested to solve the problem. The results of the algorithm are compared with a common solution first come first served. Keywords: Scheduling, optimization, meta-heuristic, berth, container terminal.