Tóm tắt luận án Tiến sĩ Khoa học máy tính: Các phương pháp heuristics giải bài toán định vị và hướng lộ trong hậu cần đô thị

Chia sẻ: Minh Tú | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

22
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án có cấu trúc gồm 3 chương trình bày tổng quan về hậu cần đô thị; nghiên cứu vấn đề định tuyến của mô hình hậu cần đô thị một mức thông qua giới thiệu và giải quyết bài toán chia sẻ phương tiện SARP; nghiên cứu vấn đề định vị và định tuyến trong hậu cần đô thị thông qua bài toán giao và nhận đa loại hàng hóa, đa tuyến.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận án Tiến sĩ Khoa học máy tính: Các phương pháp heuristics giải bài toán định vị và hướng lộ trong hậu cần đô thị

MỞ ĐẦU Lý do chọn đề tài Vận tải hàng hóa là một trong những hoạt động chính của nền kinh tế. Theo báo cáo của Ủy ban châu Âu [1], vận tải hàng hóa thu hút 5% tổng số lao động và đóng góp 5% tổng GDP của liên minh châu Âu. Ủy ban châu Âu dự đoán đến năm 2050 mức tăng trưởng của vận tải hàng khách đạt 42% và của vận tải hàng hóa đạt 60% [1]. Đối với Việt Nam, theo “Báo cáo Logistics Việt Nam 2020” của Bộ Công Thương, tốc độ tăng trưởng của vận tải hàng hóa đạt trung bình 14-16%/năm. Theo Quyết định số 318/QĐ-TTg, trong giai đoạn 2021-2030, tốc độ tăng trưởng bình quân hàng năm về vận tải hàng hóa dự định là 6,7% và vận tải hành khách là 8,2%. Để nâng cao hiệu quả của hệ thống vận tải, cộng đồng khoa học thực hiện nhiều khảo sát và đề xuất nhiều mô hình vận tải. Hai chiến lược phân phối hàng hóa chính được nghiên cứu trong hậu cần đô thị: phân phối trực tiếp và phân phối thông qua hệ thống đa mức [2]. Trong chiến lược phân phối trực tiếp, phương tiện vận tải sẽ vận tải hàng hóa trực tiếp từ kho hàng đến khách hàng. Thông thường, mô hình hậu cần đô thị một mức được sử dụng khi nghiên cứu chiến lược phân phối trực tiếp. Đối với chiến lược phân phối thông qua hệ thống đa mức, hàng hóa sẽ được vận tải từ trung tâm phân phối CDC (Central Distribution Center) đến khách hàng thông qua các điểm trung chuyển thuộc các mức trung gian khác nhau [3]. Với đặc thù của luồng vận tải hàng hóa và quy mô của đô thị, chiến lược phân phối qua hệ thống hai mức được cộng đồng khoa học nghiên cứu chuyên sâu hơn so với chiến lược phân phối trực tiếp [4]. Chiến lược phân phối thông qua hệ thống hai mức được nghiên cứu trong mô hình hậu cần đô thị hai mức. Trong mô hình hậu cần đô thị hai mức, hàng hóa sẽ được phân phối giữa trung tâm phân phối CDC và khách hàng thông qua các điểm trung chuyển. Các vấn đề nghiên cứu chính của mô hình hậu cần đô thị: định vị các điểm trung chuyển, định tuyến phương tiện vận tải trong từng mức phục vụ các yêu cầu vận tải và cơ chế đồng bộ hàng hóa giữa các mức [3] [5]. Vấn đề định vị và định tuyến trên chính là các quyết định của bài toán định vị và định tuyến trong mô hình hậu cần đô thị [6]. Ngoài ra, các yếu tố chính tác động đến tính thực tiễn của mô hình hậu cần đô thị cũng được quan tâm nghiên cứu như: loại hàng hóa vận tải, luồng vận tải của hàng hóa. Mô hình hậu cần đô thị một mức thông thường chỉ xem xét một loại hàng hóa đại diện. Đối với mô hình hậu 1
cần đô thị hai mức, hầu hết các mô hình đề xuất chỉ nghiên cứu hai loại hàng hóa đặc trưng: hàng hóa chuyển vào thành phố (viết tắt: hàng hóa e2c), hàng hóa chuyển ra ngoài thành phố (viết tắt: hàng hóa c2e). Tuy nhiên, nhu cầu vận tải hàng hóa trong nội bộ thành phố (viết tắt: hàng hóa c2c) như: vận tải hành khách, hàng hóa nhỏ… cũng chiếm tỷ trọng lớn nên cần quan tâm nghiên cứu. Do đó, việc nghiên cứu các vấn đề của bài toán định vị và định tuyến trong hậu cần đô thị sẽ giúp tiết kiệm thời gian vận tải, tối ưu chi phí vận tải, giảm ùn tắc giao thông, tối ưu việc sử dụng cơ sở vận tải, tác động tích cực đến kinh tế…. Phương pháp nghiên cứu ● Nghiên cứu theo mức của mô hình hậu cần đô thị: Đầu tiên, luận án nghiên cứu vấn đề định tuyến trong hậu cần đô thị một mức (vận tải hàng hóa trong thành phố) thông qua bài toán chia sẻ phương tiện SARP (viết tắt là: bài toán SARP, trình bày chi tiết tại Chương 2). Sau đó, mở rộng nghiên cứu đồng thời vấn đề định vị và định tuyến trong hậu cần đô thị thông qua bài toán giao và nhận đa loại hàng hóa, đa tuyến (trình bày chi tiết tại Chương 3). Cụ thể, nghiên cứu vấn đề định vị và định tuyến trong hậu cần đô thị một mức thông qua bài toán giao và nhận đa loại hàng hóa, đa tuyến với khung thời gian và đồng bộ MTT- PDTWS. Vấn đề định vị và định tuyến của mô hình đô thị hai mức được nghiên cứu thông qua xây dựng bài toán giao và nhận đa loại hàng hóa, đa tuyến ở hai mức với khung thời gian và đồng bộ 2E-MTT-PDTWS (viết tắt là: bài toán 2E-MTT- PDTWS); ● Nghiên cứu theo loại hàng hóa: Đầu tiên, luận án nghiên cứu vận tải hàng hóa c2c trong nội bộ thành phố (vận tải hành khách và hàng hóa nhỏ) thông qua bài toán SARP. Sau đó, mở rộng bài toán nghiên cứu đồng thời ba loại hàng hóa: hàng hóa c2c, hàng hóa c2e và hàng hóa e2c thông qua bài toán MTT-PDTWS và bài toán 2E-MTT-PDTWS; ● Nghiên cứu từ mô hình thực tế: Đầu tiên, luận án nghiên cứu mô hình vận tải chia sẻ phương tiện trong thành phố. Sau đó luận án mô hình hóa và nghiên cứu thông qua bài toán chia sẻ phương tiện SARP. Từ đó, luận án xây dựng bài toán định vị và định tuyến trong mô hình hậu cần đô thị hai mức. Phạm vi nghiên cứu 2
● Nghiên cứu bài toán chia sẻ phương tiện SARP; ● Nghiên cứu bài toán giao và nhận đa loại hàng hóa, đa tuyến với khung thời gian và đồng bộ MTT-PDTWS; ● Nghiên cứu bài toán giao và nhận đa loại hàng hóa, đa tuyến ở hai mức với khung thời gian và đồng bộ 2E-MTT-PDTWS. Các đóng góp của luận án ● Đối với bài toán chia sẻ phương tiện SARP, luận án đóng góp: o Mô hình phụ thuộc hoàn toàn thời gian với khung tốc độ cho bài toán và bổ sung các yếu tố, ràng buộc thực tế để cải tiến mô hình; o Mô hình toán học biểu diễn bài toán; o Thuật toán tham lam và thuật toán tìm kiếm địa phương; o Phương pháp xây dựng bộ dữ liệu thực nghiệm trên dữ liệu thực tế của công ty taxi Tokyo-Musen và thực nghiệm. ● Đối với bài toán MTT-PDTWS: o Xây dựng thuật toán tìm kiếm lân cận lớn thích nghi ALNS; o Thực nghiệm và so sánh với kết quả bài toán khi giải bằng thuật toán tìm kiếm Tabu. ● Đối với bài toán 2E-MTT-PDTWS: o Xây dựng bài toán “Bài toán giao và nhận đa loại hàng hóa, đa tuyến ở hai mức với khung thời gian và đồng bộ 2E- MTT-PDTWS”; o Xây dựng thuật toán tìm kiếm lân cận lớn thích nghi ALNS và thuật toán heuristic để giải quyết bài toán; o Xây dựng bộ dữ liệu thực nghiệm và thực nghiệm. Các kết quả nghiên cứu của luận án đã được công bố ở 2 bài báo tạp chí và 3 bài báo hội nghị quốc tế (chi tiết tại DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ CỦA LUẬN ÁN). Trong đó có 01 tạp chí ISI Q2 và 01 bài báo đạt giải Best Paper Award của hội nghị KSE 2016. Cấu trúc của luận án Chương 1: trình bày tổng quan về hậu cần đô thị. Trình bày vấn đề định vị và định tuyến trong hậu cần đô thị thông qua bài toán chia sẻ phương tiện và bài toán giao và nhận đa loại hàng hóa, đa tuyến; Chương 2: nghiên cứu vấn đề định tuyến của mô hình hậu cần đô thị một mức thông qua giới thiệu và giải quyết bài toán chia sẻ phương tiện SARP. Xây dựng mô hình toán học biểu diễn bài toán. Xây dựng thuật toán tham lam, thuật toán tìm kiếm địa phương để giải quyết bài toán. 3
Xây dựng dữ liệu thực nghiệm từ dữ liệu thực tế của công ty taxi Tokyo- Musen và tiến hành thực nghiệm; Chương 3: nghiên cứu vấn đề định vị và định tuyến trong hậu cần đô thị thông qua bài toán giao và nhận đa loại hàng hóa, đa tuyến. Vấn đề định vị và định tuyến trong hậu cần đô thị một mức được nghiên cứu thông qua bài toán MTT-PDTWS. Mở rộng bài toán MTT-PDTWS, vấn đề định vị và định tuyến trong hậu cần đô thị hai mức được nghiên cứu thông quan bài toán 2E-MTT-PDTWS. Xây dựng thuật toán tìm kiếm lân cận lớn thích nghi ALNS để giải quyết bài toán MTT-PDTWS và bài toán 2E-MTT-PDTWS. Xây dựng dữ liệu thực nghiệm và tiến hành thực nghiệm, phân tích, đánh giá hiệu quả của thuật toán. CHƯƠNG 1. TỔNG QUAN VẤN ĐỀ ĐỊNH VỊ VÀ ĐỊNH TUYẾN CỦA HẬU CẦN ĐÔ THỊ TRONG BÀI TOÁN CHIA SẺ PHƯƠNG TIỆN VÀ BÀI TOÁN GIAO VÀ NHẬN ĐA LOẠI HÀNG HÓA, ĐA TUYẾN 1.1. Hậu cần đô thị Hậu cần đô thị bắt đầu được nghiên cứu từ những năm 1970. Đến những năm 1980, vấn đề vận tải trong hậu cần đô thị thu hút nhiều công trình nghiên cứu với các kết quả đạt được như: các khảo sát về giao thông, các dự án nghiên cứu và các kết quả thực nghiệm của mô hình nghiên cứu. Các nghiên cứu trong giai đoạn này diễn ra chủ yếu tại liên minh Châu Âu và Nhật. Năm 2019, tác giả Hu phân tích 513 công trình nghiên cứu về hậu cần đô thị từ năm 1993 đến năm 2018 [9]. Theo thống kê, từ năm 2010 số lượng nghiên cứu về hậu cần đô thị chiếm 90% và được quan tâm nghiên cứu tại hơn 25 nước. Hội đồng quản lý hậu cần CLM đưa ra định nghĩa về hậu cần [15]. Từ vào định nghĩa này, khi xem xét trong bối cảnh đô thị, tác giả Taniguchi [16] đưa ra định nghĩa: “Hậu cần đô thị là quá trình tối ưu hóa các hoạt động hậu cần và các hoạt động vận tải trong khu vực đô thị trên cơ sở xem xét các vấn đề liên quan đến môi trường giao thông, tắc nghẽn giao thông và năng lượng tiêu thụ”. Trong mô hình hậu cần đô thị, hàng hóa sẽ được tập trung trước khi vận tải vào thành phố hoặc sau khi vận tải ra ngoài thành phố tại các trung tâm CDC. Việc sử dụng trung tâm CDC là đóng góp quan trọng và được sử dụng trong đa số các đề xuất và nghiên cứu liên quan đến hậu cần đô thị [17]. 1.2. Vấn đề quy hoạch trong hậu cần đô thị 4
Mô hình hậu cần đô thị yêu cầu sự quy hoạch ở các mức khác nhau: mức chiến lược, mức chiến thuật và mức vận hành [5]. Ở mức chiến lược, mô hình hậu cần đô thị sẽ được xem xét trong trường hợp là hệ thống độc lập cũng như là một hệ thống nhỏ của hệ thống giao thông vận tải tổng thể. Yêu cầu định vị thuộc mức chiến lược. Quy hoạch ở mức chiến thuật sẽ tập trung xử lý các vấn đề liên quan đến định tuyến (thời gian khởi hành, lộ trình và trọng tải của phương tiện vận tải, …) [20][21]. Từ mức quy hoạch chiến thuật, lịch làm việc của tài xế vận tải, nhân viên tại điểm trung chuyển cũng như việc điều chỉnh các hoạt động của phương tiện vận tải và kho trung gian sẽ được thực hiện ở mức vận hành. Các nghiên cứu tiêu biểu về hoạt động của một đội xe vận tải ở mức vận hành được tác giả Taniguchi, tác giả Thompson nghiên cứu tại công trình [22][23]. Bên cạnh các mức quy hoạch, tác giả Barcelo bổ sung tính chất quản lý theo thời gian thực đối với: quá trình vận tải, thông tin trong khi vận tải (vị trí của phương tiện, tình trạng giao thông), điều hành phương tiện vận tải tại bất kỳ thời điểm nào [24]. Theo thống kê tại các nghiên cứu [9][16][25][26], có rất ít mô hình chính thức được đề xuất cho hậu cần đô thị. Các vấn đề quy hoạch đặt ra thường chỉ xem xét hậu cần đô thị là một phần của hệ thống giao thông vận tải tổng thể như: hệ thống vận tải hành khách trong khu vực đô thị… 1.3. Các mô hình hậu cần đô thị điển hình 1.3.1. Mô hình hậu cần đô thị một mức Trong mô hình hậu cần đô thị một mức, hàng hóa sẽ được phân phối trực tiếp giữa trung tâm CDC và khách hàng. Các dự án đầu tiên thực hiện nghiên cứu về mô hình hậu cần đô thị được thực hiện ở Châu Âu và Nhật Bản [25][35][36][37]. Mô hình hậu cần đô thị một mức đầu tiên là mô hình “City Logistik” được áp dụng ở Đức, Thụy Sỹ và Monaco. Dự án kết thúc vào năm 2002 do không nhận được sự quan tâm của chính phủ vì phát sinh các chi phí, các chính sách hỗ trợ nhưng mô hình mới chỉ mang lợi ích ngắn hạn cho chính phủ. Tuy nhiên, lĩnh vực nghiên cứu này đang tiếp tục phát triển tại các quốc gia như: Úc, Châu Á, Đông Âu và Bắc Mỹ. Nghiên cứu [38] cho thấy rằng mô hình hậu cần đô thị một mức chỉ phù hợp các thành phố quy mô nhỏ và vừa, không phù hợp với các thành phố lớn. 1.3.2. Mô hình hậu cần đô thị hai mức 5
Để áp dụng cho các thành phố có quy mô lớn, đa số các nghiên cứu đề xuất mô hình vận tải hai mức. Trong mô hình này, hàng hóa sẽ được tập trung tại một trung tâm CDC và được phân phối bởi đội xe tải đến khách hàng thông qua các điểm trung chuyển. Hai hệ thống hậu cần đô thị hai mức điển hình: hệ thống CityCargo ở Amsterdam sử dụng tàu điện và xe điện để vận tải; hệ thống chuyển phát nhanh Chronopost International ở Pháp sử dụng xe tải lớn và xe điện. Một số đề xuất cho mô hình hậu cần đô thị hai mức được giới thiệu bởi tác giả Crainic [31] và tác giả Gragnani [41]. Trong mô hình hậu cần đô thị hai mức, các nghiên cứu chủ yếu tập trung giải quyết các vấn đề chính: • Định vị các điểm trung chuyển hàng hóa giữa hai mức; • Định tuyến các phương tiện vận tải theo từng mức; • Cơ chế đồng bộ hàng hóa giữa các phương tiện vận tải tại các điểm trung chuyển; • Loại hàng hóa và luồng vận tải hàng hóa theo từng mức. 1.4. Vấn đề định vị và định tuyến trong hậu cần đô thị Bài toán định vị và định tuyến LRP [6] bao gồm tối thiểu hai quyết định phụ thuộc lẫn nhau: • Quyết định định vị: cơ sở vận tải (nhà máy, nhà kho, điểm trung chuyển…) nên sử dụng như thế nào để đáp ứng luồng vận tải hàng hóa. Việc chỉ định phục vụ yêu cầu vận tải với cơ sở vận tải tương ứng là một quyết định định vị; • Quyết định định tuyến: xây dựng lộ trình vận tải cho phương tiện vận tải đáp ứng yêu cầu vận tải. Quyết định định vị và định tuyến của bài toán LRP chính là quyết định của mức chiến lược và mức chiến thuật của hậu cần đô thị. 1.4.1. Định tuyến trong bài toán chia sẻ phương tiện Vấn đề định tuyến trong hậu cần đô thị một mức được nghiên cứu thông qua việc vận tải hành khách và hàng hóa. Thông thường, trong hệ thống vận tải, hành khách và hàng hóa thường được vận tải bởi các phương tiện khác nhau. Tuy nhiên, đối với vận tải trong thành phố, hàng hóa thường có kích thước nhỏ và khối lượng nhỏ nên có thể vận tải cùng hành khách mà không ảnh hưởng nhiều đến chỗ ngồi và thời gian di chuyển của hành khách. Vấn đề chia sẻ phương tiện giữa hành khách và hàng hóa là một phần của bài toán chia sẻ phương tiện đang được quan tâm nghiên cứu. Bài toán chia sẻ phương tiện Share-a-Ride do Li và cộng sự đề xuất cho phép các hành khách và hàng hóa khác nhau cùng sử dụng chung một xe taxi [55]. Tuy nhiên, mỗi hành khách thường có 6
các yêu cầu khác nhau như về thời gian di chuyển, không gian ngồi riêng hay yêu cầu về an toàn. Do đó, mô hình chia sẻ phương tiện giữa các hành khách là không thực tế. Nhằm cải thiện tính thực tiễn của mô hình [55], luận án xây dựng mô hình chia sẻ phương tiện giữa một hành khách và các hàng hóa. Để thuận tiện cho hành khách, yêu cầu vận tải hành khách sẽ được thực hiện liên tục mà không dừng hoặc đỗ trong quá trình phục vụ. Ngoài ra, mô hình chia sẻ phương tiện SARP của Li và cộng sự sử dụng khoảng cách Manhattan để tính toán. Phương pháp tính toán dựa vào khoảng cách không phù hợp khi áp dụng cho vận tải trong đô thị nếu xem xét tình trạng tắc nghẽn giao thông. Do đó, luận án xây dựng mô hình sử dụng thời gian di chuyển để tính toán và xem xét các mức độ tắc nghẽn giao thông theo từng vùng (nội thành, vùng đệm và ngoại thành) và theo từng khung giờ. Mô hình luận án xây dựng là mô hình hoàn toàn phụ thuộc thời gian. Đối với mục tiêu của bài toán, mô hình luận án bổ sung thêm doanh thu trong trường hợp thời gian vận tải lớn hơn thời gian vận tải quy định do tắc nghẽn giao thông. Đối với chi phí, ngoài chi phí vận tải, luận án bổ sung hai chi phí vận hành thực tế bao gồm: chi phí nhân công cho tài xế taxi và chi phí sử dụng xe taxi. Ngoài ra, có rất ít nghiên cứu về chia sẻ phương tiện sử dụng dữ liệu thực tế để giải quyết bài toán như dữ liệu khu vực Atlanta Metropolitan [56], dữ liệu xe taxi của thành phố San Francisco [55]. Mô hình luận án xây dựng được thực nghiệm với dữ liệu được xây dựng từ dữ liệu thực tế được cung cấp bởi công ty taxi Tokyo-Musen. 1.4.2. Định vị và định tuyến trong bài toán giao nhận đa loại hàng hóa, đa tuyến Bài toán giao và nhận đa loại hàng hóa, đa tuyến sẽ nghiên cứu đồng thời tối thiểu hai trong ba loại hàng hóa: hàng hóa chuyển vào thành phố, hàng hóa chuyển ra ngoài thành phố, hàng hóa chuyển trong nội bộ thành phố. Một trong các nghiên cứu về hàng hóa e2c được trình bày trong bài toán TMZT-VRPTW [57]. Trong bài toán TMZT-VRPTW, một đội xe tải nhỏ xuất phát từ một kho đỗ xe đến điểm trung chuyển nhận hàng và sau đó giao hàng hóa e2c đến khách hàng trong khung thời gian quy định. Trong nghiên cứu [57], tác giả Nguyen và cộng sự đề xuất thuật toán tìm kiếm Tabu để giải quyết bài toán này. Sau đó, các tác giả tiếp tục mở rộng thuật toán tìm kiếm Tabu này để giải quyết một bài toán mới: “Giao và nhận hàng hóa, đa tuyến với khung thời gian và 7
đồng bộ MT-PDTWS” [58]. Bên cạnh thực hiện giao hàng hóa e2c tương tự bài toán TMZT-VRPTW, đội xe tải nhỏ trong bài toán MT-PDTWS cho phép nhận các hàng hóa c2e tại khách hàng và vận tải đến các điểm trung chuyển. Trong công trình [40], tác giả Crainic và cộng sự tổng quát hóa hai bài toán TMZT-VRPTW và MT-PDTWS, bằng một đề xuất cho bài toán mới “Giao và nhận đa loại hàng hóa, đa tuyến với khung thời gian và đồng bộ MTT-PDTWS”. Bài toán MTT-PDTWS nghiên cứu đồng thời ba loại hàng hóa: hàng hóa e2c, hàng hóa c2e và hàng hóa c2c. Bài toán MTT-PDTWS có các quyết định: - Định vị: xác định điểm trung chuyển cho hàng hóa c2e; - Định tuyến: xác định hành trình của đội xe tải. Để giải quyết bài toán này, tác giả Nguyen và cộng sự đã mở rộng thuật toán tìm kiếm Tabu được giới thiệu trong nghiên cứu [57]. Nhằm mục đích nghiên cứu mô hình bài toán làm nền tảng mở rộng áp dụng cho hậu cần đô thị hai mức ở các nghiên cứu tiếp theo, cũng như nâng cao chất lượng lời giải, luận án xây dựng thuật toán tìm kiếm lân cận lớn thích nghi ALNS để giải quyết bài toán MTT-PDTWS. Từ kết quả đạt được, luận án mở rộng bài toán MTT-PDTWS cho mô hình hậu cần đô thị hai mức. Xét ở góc độ định tuyến, mô hình hậu cần đô thị hai mức có thể được xem là mở rộng của bài toán định tuyến xe hai mức 2E-VRP. Mở rộng bài toán 2E-VRP, bài toán định vị và định tuyến hai mức 2E-LRP được Jacobsen và cộng sự đề xuất trong nghiên cứu [63]. Bài toán 2E-LRP thực hiện đồng thời việc định vị và định tuyến trên cả hai mức. Mở rộng bài toán 2E-LRP và bài toán MTT- PDTWS, luận án xây dựng bài toán “Giao và nhận đa loại hàng hóa, đa tuyến ở hai mức với khung thời gian đồng bộ 2E-MTT-PDTWS”. Kế thừa đặc trưng của bài toán MTT-PDTWS, bài toán 2E-MTT-PDTWS có quyết định: - Định vị: xác định điểm trung chuyển cho hàng hóa c2e và hàng hóa e2c; - Định tuyến: xác định hành trình của đội xe tải nhỏ và xe tải lớn. 1.5. Kết luận chương Hầu hết các thành phố thực hiện nghiên cứu và áp dụng mô hình hậu cần đô thị nhằm mục đích tăng hiệu quả vận tải và giảm sự tác động tiêu cực của việc vận tải hàng hóa trong môi trường đô thị. Vấn đề định vị và định tuyến của mô hình hậu cần đô thị là các quyết định của bài toán định vị và định tuyến. Vấn đề định tuyến trong mô hình hậu cần đô thị một mức được luận án nghiên cứu thông qua bài toán chia sẻ phương 8
tiện. Vấn đề định vị và định tuyến trong mô hình hậu cần đô thị được luận án nghiên cứu thông qua bài toán giao và nhận đa loại hàng hóa. Cụ thể, vấn đề định vị và định tuyến trong mô hình hậu cần đô thị một mức được luận án nghiên cứu thông qua bài toán MTT-PDTWS. Trong mô hình hậu cần đô thị hai mức, vấn đề định vị và định tuyến được luận án nghiên cứu thông qua bài toán 2E-MTT-PDTWS. CHƯƠNG 2. VẤN ĐỀ ĐỊNH TUYẾN TRONG BÀI TOÁN CHIA SẺ PHƯƠNG TIỆN 2.1. Phát biểu bài toán Bài toán đề xuất được định nghĩa trên đồ thị có hướng, có trọng số 𝐺 = (𝑉, 𝐸). 𝑉 là tập hợp các đỉnh trên đồ thị và bao gồm các tập con 𝑉 𝑝𝑜 ∪ 𝑉 𝑓𝑜 ∪ 𝑉 𝑝𝑑 ∪ 𝑉 𝑓𝑑 ∪ 𝐷 ∪ 𝑉 𝑝𝑎 , với 𝑉 𝑝𝑜 là tập các điểm đón hành khách; 𝑉 𝑓𝑜 là tập hợp các điểm nhận hàng hóa; 𝑉 𝑝𝑑 là tập hợp các điểm trả hành khách; 𝑉 𝑓𝑑 là tập hợp các điểm trả hàng hóa; 𝐷 là tập hợp các địa điểm kho xe taxi và 𝑉 𝑝𝑎 là tập hợp các bãi đỗ xe taxi. Mỗi đỉnh 𝑖 ∈ 𝑉 𝑝𝑜 ∪ 𝑉 𝑓𝑜 ∪ 𝑉 𝑝𝑑 ∪ 𝑉 𝑓𝑑 có một cặp tham số {∅𝑖 , 𝜔𝑖 } biểu diễn trọng số và thời gian chờ tối đa để phục vụ yêu cầu thứ 𝑖. Ngoài ra, mỗi đỉnh 𝑖 cũng được quy định khung thời gian phục vụ [𝑒𝑖 , ℓ𝑖 ]. 𝐾 là tập hợp các xe taxi. Để phục vụ yêu cầu vận tải thứ 𝑖, thời điểm của xe taxi 𝑘 ∈ 𝐾 đến điểm 𝑖 phải thuộc khung thời gian [𝑒𝑖 , ℓ𝑖 ]. Yêu cầu vận tải hành khách phải được phục vụ liên tục, nghĩa là xe taxi không được phép dừng khi đang vận tải hành khách. Xe taxi bắt đầu và kết thúc hành trình tại cùng một kho đỗ xe. Mỗi bãi đỗ xe 𝑗 ∈ 𝑉 𝑝𝑎 có sức chứa 𝑐𝑗 . Xe taxi 𝑘 được phép vận tải trong khoảng thời gian giới hạn 𝜏𝑘𝑚𝑎𝑥 và có tải trọng 𝜎𝑘 . Xe taxi không được vận tải vượt quá tải trọng của xe. Mỗi 𝑡 cạnh (𝑢, 𝑣) thuộc tập cạnh 𝐸 được đại diện bởi giá trị 𝑡𝑢,𝑣 ̅ và 𝜏𝑢,𝑣 . Trong 𝑡 đó, 𝑡𝑢,𝑣 ̅ là thời gian di chuyển cho phép từ điểm 𝑢 đến điểm 𝑣 và 𝜏𝑢,𝑣 là thời gian di chuyển từ điểm 𝑢 đến 𝑣 nếu xe taxi rời 𝑢 tại thời điểm 𝑡. Nếu thời gian xe taxi di chuyển từ điểm 𝑢 đến điểm 𝑣 vượt quá giá trị ̅ thì chi phí bổ sung sẽ được tính dựa vào chênh lệch giữa thời gian 𝑡𝑢,𝑣 ̅ . di chuyển thực tế và giá trị 𝑡𝑢,𝑣 Yêu cầu của bài toán là tìm tập hợp các hành trình của xe taxi để phục vụ các yêu cầu vận tải với mục tiêu đạt tổng lợi nhuận cao nhất. Tổng lợi nhuận là tổng doanh thu sau khi trừ đi tổng các chi phí. Tổng doanh thu bao gồm: doanh thu vận tải hành khách, doanh thu vận tải hàng hóa và doanh thu vận tải hành khách vượt quá thời gian vận tải cho phép. 9
Tổng chi phí vận tải bao gồm: chi phí vận tải, chi phí nhân công cho tài xế taxi và chi phí sử dụng xe taxi. 2.2. Mô hình toán học Chúng tôi kế thừa các tính năng của mô hình toán học được giới thiệu ở nghiên cứu [55]. Một điểm lưu ý trong mô hình là thời gian di chuyển giữa hai điểm có thể khác nhau và phụ thuộc vào thời gian bắt đầu ở 𝑚𝑖𝑛 𝑚𝑎𝑥 điểm xuất phát. Chúng tôi đề xuất sử dụng 𝜏𝑢,𝑣,𝑡 và 𝜏𝑢,𝑣,𝑡 đại diện cho thời gian di chuyển nhanh nhất và chậm nhất trong trường hợp xe taxi rời điểm 𝑢 đến điểm 𝑣 tại thời điểm 𝑡. Thời gian di chuyển từ điểm 𝑢 𝑡 tại thời điểm 𝑡 đến điểm 𝑣 là biến 𝜏𝑢,𝑣 . Mô hình được trình bày chi tiết trong bản luận án đầy đủ. 2.3. Thuật toán giải bài toán chia sẻ phương tiện 2.3.1. Kỹ thuật định tuyến trên đồ thị động Chúng tôi sử dụng đồ thị động để thể hiện mạng lưới vận tải trong mô hình bài toán. Trong đó, mỗi cạnh sẽ được gán nhãn bởi hàm số theo thời gian. 2.3.1.1. Kỹ thuật phân cấp đỉnh giản lược CH Kỹ thuật phân cấp đỉnh giản lược CH [75] là kỹ thuật tăng tốc độ tìm kiếm đường đi ngắn nhất trên đồ thị động bằng cách tạo ra các cạnh tắt để sử dụng trong quá trình tìm đường đi ngắn nhất. 2.3.1.2. Độ phức tạp Độ phức tạp phụ thuộc vào việc tìm kiếm đường đi ngắn nhất trên đồ thị thành phần 3-core. Độ phức tạp của thuật toán Dijkstra là Ο(|𝑉| log |𝑉|) và tỷ lệ thu hẹp của bộ dữ liệu Tokyo nằm trong khoảng từ 10 đến 11 nên số các bước cần xử lý giảm khoảng 33 (≈ 10 log 10) lần. 2.3.2. Thuật toán heuristic cho mô hình vận tải trực tiếp Thuật toán 2.1. Thuật toán heuristic cho mô hình vận tải trực tiếp Đồ thị G=(V, E); 𝑉 𝑝𝑜 : danh sách yêu cầu đón hành khách; Đầu 𝑉 𝑓𝑜 : danh sách yêu cầu nhận hàng hóa; vào: [𝑒𝑖 , ℓ𝑖 ]: khung thời gian cho phép của yêu cầu 𝑖, ∀𝑖 ∈ 𝑉 𝑝𝑜 ∪ 𝑉 𝑝𝑑 ∪ 𝑉 𝑓𝑜 ∪ 𝑉 𝑓𝑑 ; 𝐾: tập hợp các xe taxi. Đầu 𝑓: tổng lợi nhuận; ra: Giá trị của các biến. 1. Sắp xếp tất cả yêu cầu 𝑖 ∈ 𝑉 𝑝𝑜 ∪ 𝑉 𝑓𝑜 tăng dần theo 𝑒𝑖 và đưa vào vào danh sách 𝑉 ′ ; 2. foreach yêu cầu 𝑖 ∈ 𝑉 ′ do 10
3. Cập nhật trạng thái của tất cả xe taxi tại thời điểm 𝑒𝑖 ; 4. Cập nhật trạng thái của tất cả điểm đỗ xe taxi 𝑝 ∈ 𝑉 𝑝𝑎 tại thời điểm 𝑒𝑖 ; 5. if tìm thấy xe taxi 𝑘 ′ ∈ 𝐾 gần nhất có thể phục vụ yêu cầu i then 6. Đưa yêu cầu i vào cuối hành trình hiện tại của taxi 𝑘 ′ ; 7. Cập nhật tổng lợi nhuận 𝑓; 8. else 9. Từ chối vận tải yêu cầu i; 10. end if 11. end for 2.3.3. Thuật toán heuristic cho mô hình chia sẻ phương tiện 2.3.3.1. Cấu trúc chung Mô hình chia sẻ phương tiện sẽ được xử lý qua hai bước chính: ● Bước 1: Xây dựng dữ liệu bản đồ từ tập dữ liệu đầu vào và tiền xử lý dữ liệu bản đồ sử dụng kỹ thuật CH; ● Bước 2: Tại điểm kết thúc của mỗi chu kỳ: o Tổng hợp các yêu cầu vận tải và cập nhật trạng thái của tất cả taxi; o Áp dụng thuật toán tham lam để tìm ra lời giải đầu tiên (chi tiết tại mục 2.3.3.2); o Áp dụng các kỹ thuật tìm kiếm địa phương để cải thiện chất lượng lời giải hiện tại (chi tiết tại mục 2.3.3.3); 2.3.3.2. Thuật toán tham lam Độ linh hoạt của một yêu cầu đón hành khách hoặc nhận hàng hóa: 𝑓𝑟 (𝑖) = 𝜇(ℓ𝑖+𝑠 − 𝑒𝑖 ) − 𝜐𝜆𝑚𝑖𝑛 𝑖 với: ● 𝑒𝑖 : là thời điểm sớm nhất để đón hành khách/nhận hàng i; ● ℓ𝑖+𝑠 : là thời điểm muộn nhất để trả hành khách hoặc hàng tương ứng với yêu cầu đón hành khách hoặc nhận hàng i; ● 𝜆𝑚𝑖𝑛 𝑖 : là thời gian di chuyển giữa điểm trả hành khách/hàng i với bãi đỗ xe gần nhất; ● 𝜇, 𝜐: là các tham số tùy chỉnh. Thuật toán 2.2. Thuật toán tham lam cho mô hình chia sẻ phương tiện Đầu Đồ thị G=(V, E); vào: 𝑉 𝑝𝑜 : danh sách yêu cầu đón hành khách; 𝑉 𝑓𝑜 : danh sách yêu cầu nhận hàng hóa; [𝑒𝑖 , ℓ𝑖 ]: khung thời gian cho phép của yêu cầu 𝑖, ∀𝑖 ∈ 𝑉 𝑝𝑜 ∪ 𝑉 𝑝𝑑 ∪ 𝑉 𝑓𝑜 ∪ 𝑉 𝑓𝑑 ; 11
𝐾: tập hợp các xe taxi. Đầu 𝑓: tổng lợi nhuận; ra: Giá trị của các biến. 1. Sắp xếp tất cả yêu cầu đón 𝑖 ∈ 𝑉 𝑝𝑜 ∪ 𝑉 𝑓𝑜 tăng dần theo giá trị 𝑓𝑟 (𝑖) vào tập hợp 𝑅′ ; 2. foreach yêu cầu 𝑖 ∈ 𝑅′ do 3. if tìm thấy xe taxi 𝑘 ′ ∈ 𝐾 có thể phục vụ yêu cầu i mà đạt được tổng lợi nhuận tốt nhất then 4. Đưa yêu cầu i vào hành trình hiện tại của xe taxi 𝑘 ′ ; 5. Cập nhật tổng lợi nhuận 𝑓; 6. else 7. Từ chối vận tải yêu cầu i; 8. end if 9. end for 2.3.3.3. Thuật toán tìm kiếm địa phương Giá trị hiệu quả của yêu cầu vận tải r được định nghĩa: 𝑔(𝑟) = (𝜆𝑚𝑖𝑛 𝑚𝑖𝑛 𝑚𝑖𝑛 𝑚𝑖𝑛 𝑚𝑖𝑛 𝑚𝑖𝑛 𝑢𝑖−1 ,𝑢𝑖 + 𝜆𝑢𝑖 ,𝑢𝑗 − 𝜆𝑢𝑖−1 ,𝑢𝑗 ) + (𝜆𝑢𝑖 ,𝑢𝑗 + 𝜆𝑢𝑗 ,𝑢𝑗+1 − 𝜆𝑢𝑖 ,𝑢𝑗+1 ) với: 𝑢0 , … , 𝑢𝑖−1 , 𝑢𝑖 , … , 𝑢𝑗 , 𝑢𝑗+1 , … 𝑢0 : hành trình của xe taxi k; 𝑢𝑖 , 𝑢𝑗 : điểm đón và điểm trả của yêu cầu r; 𝜆𝑚𝑖𝑛 𝑢,𝑣 : thời gian di chuyển ngắn nhất giữa điểm u và v. Thuật toán 2.3. Thuật toán tìm kiếm địa phương Đầu Đồ thị G=(V, E); vào: 𝑉 𝑝𝑜 , 𝑉 𝑝𝑑 : danh sách yêu cầu đón và trả hành khách; 𝑉 𝑓𝑜 , 𝑉 𝑓𝑑 : danh sách yêu cầu nhận và trả hàng hóa; [𝑒𝑖 , ℓ𝑖 ]: khung thời gian cho phép của yêu cầu 𝑖, ∀𝑖 ∈ 𝑉 𝑝𝑜 ∪ 𝑉 𝑝𝑑 ∪ 𝑉 𝑓𝑜 ∪ 𝑉 𝑓𝑑 ; 𝐾: tập hợp các xe taxi. Lời giải bài toán: • 𝑓1 : tổng lợi nhuận; • Giá trị của các biến. Đầu ra: Lời giải bài toán: • 𝑓2 : tổng lợi nhuận; • Giá trị của các biến. 1. 𝑝𝑠𝑖𝑧𝑒 là tỷ lệ phần trăm số lượng yêu cầu vận tải bị loại bỏ; 2. repeat 3. Tính toán giá trị hiệu quả 𝑔(𝑖) của tất cả yêu cầu 𝑖 ∈ 𝑉 𝑝𝑜 ∪ 𝑓𝑜 𝑉 ; 12
4. Sắp xếp tất cả yêu cầu 𝑖 ∈ 𝑉 𝑝𝑜 ∪ 𝑉 𝑓𝑜 theo thứ tự tăng dần theo 𝑔(𝑖); Lấy 𝑝𝑠𝑖𝑧𝑒 các yêu cầu đầu tiên đã được sắp xếp đưa vào tập hợp 𝑉 ′ ; 5. foreach yêu cầu 𝑖 ∈ 𝑉 ′ do 6. Cập nhật trạng thái của tất cả xe taxi tại thời điểm 𝑒𝑖 ; Cập nhật trạng thái của tất cả điểm đỗ xe taxi 𝑝 ∈ 𝑉 𝑝𝑎 tại thời điểm 𝑒𝑖 ; 7. Gọi 𝑘1 là xe taxi đang phục vụ yêu cầu vận tải i; 8. if tìm thấy xe taxi gần nhất 𝑘2 có thể phục vụ yêu cầu i và tăng tổng lợi nhuận tốt nhất hiện tại then 9. Đưa yêu cầu i vào hành trình hiện tại của taxi 𝑘2 ; 10. Cập nhật tổng lợi nhuận tốt nhất hiện tại; 11. end if 12. end for 13. until không thể đạt được tổng lợi nhuận tốt hơn; 2.4. Thực nghiệm và đánh giá 2.4.1. Dữ liệu thực nghiệm 2.4.1.1. Xử lý mạng lưới đường giao thông Tokyo Bản đồ đường của Tokyo là bản đồ hình vuông với kích thước cạnh là 80 km. Bản đồ này sẽ được chia thành các vùng 8x8. Bản đồ đường của Tokyo gồm trung bình khoảng 130.000 điểm giao nhau, 15.000 đường và 1.000 hành khách mỗi giờ. Chúng tôi xử lý dữ liệu trong hai bước: tiền xử lý dữ liệu và bước giản lược bản đồ. 2.4.1.2. Chuyển đổi yêu cầu vận tải Dữ liệu thu thập chỉ bao gồm vị trí (kinh độ, vĩ độ), thời gian phục vụ (thời gian đón, thời gian trả hành khách) và tốc độ di chuyển của taxi. Do đó, chúng tôi thực hiện khớp những địa điểm yêu cầu vận tải với tọa độ của bản đồ và tạo ra các khung thời gian hợp lý cho các yêu cầu vận tải. Sau đó, chúng tôi chuyển đổi 70% yêu cầu vận tải hành khách thành yêu cầu vận tải hàng hóa. 2.4.1.3. Xử lý khung tốc độ Chúng tôi đã phân tích dữ liệu giao thông hàng ngày từ bộ dữ liệu taxi Tokyo-Musen trong các ngày liên tục từ 20/01/2009 đến 31/01/2009. Từ đó, xây dựng khung tốc độ của xe taxi theo khung thời gian và theo ba vùng của thành phố gồm: vùng trung tâm, vùng đệm và ngoại ô thành phố theo các mức tắc nghẽn giao thông. 2.4.1.4. Định vị kho, bến đỗ xe taxi 13
Tổng hợp các điểm bắt đầu và kết thúc của xe taxi trong suốt thời gian làm việc từ dữ liệu taxi Tokyo-Musen để xác định các kho đỗ xe taxi. Từ dữ liệu taxi Tokyo-Musen, chúng tôi tính toán tần suất của các điểm mà xe taxi dừng hơn 3 phút. Các điểm này được sử dụng làm bến đỗ xe. 2.4.1.5. Bộ dữ liệu thực nghiệm và tham số thực nghiệm Các dữ liệu thực nghiệm này được thống kê trong 4 ngày liên tục từ 22/01/2009 đến 25/01/2009. Cước phí vận tải bởi taxi Tokyo-Musen và giá cước vận tải hàng hóa được tham chiếu từ website [77][78]. 2.4.2. Kết quả thực nghiệm Hiệu năng của mô hình đề xuất thể hiện thông qua so sánh kết quả thực nghiệm đối với hai mô hình: mô hình trực tiếp và mô hình chia sẻ. Mô hình chia sẻ bao gồm hai trường hợp: mô hình chia sẻ tĩnh và mô hình chia sẻ động. Về tổng thể, mô hình chia sẻ tốt hơn mô hình vận tải trực tiếp như: tổng lợi nhuận cao hơn, tổng thời gian di chuyển ít hơn và số lượng xe taxi sử dụng ít hơn. Về tổng lợi nhuận, tổng lợi nhuận mô hình chia sẻ gấp 1,15 lần so với mô hình trực tiếp. Trong mô hình chia sẻ, số lượng yêu cầu chia sẻ chiếm 69,5% trên tổng số yêu cầu. Về thời gian vận tải, tổng thời gian di chuyển của mô hình chia sẻ ít hơn 0,27 lần so với mô hình trực tiếp. Về số lượng xe taxi tham gia vận tải, số lượng taxi sử dụng trong mô hình chia sẻ giảm 0,47 lần so với mô hình trực tiếp. Biểu đồ sau biểu diễn lợi nhuận theo từng khoảng thời gian 2h của một bộ dữ liệu. Các biểu đồ chi tiết về lợi nhuận, thời gian vận tải, số lượng xe taxi bổ sung được trình bày đầy đủ trong luận án. 2.5. Kết luận chương Các nội dung chính của Chương: Thứ nhất, giới thiệu bài toán mở rộng của bài toán chia sẻ phương tiện SARP; Thứ hai, đề xuất mô hình toán học biểu diễn bài toán. Thứ ba, giới thiệu các thuật toán để giải quyết bài toán với mô hình vận tải trực tuyến, mô hình chia sẻ tĩnh và mô hình chia sẻ động. Thứ tư, giới thiệu cách thức xây dựng bộ dữ liệu thực nghiệm 14
dựa vào dữ liệu của taxi Tokyo-Musen. Kết quả thực nghiệm cho thấy tính ứng dụng của mô hình chia sẻ phương tiện trong thực tiễn. Các kết quả chính của chương này đã được công bố tại tạp chí Data & Knowledge Engineering [3], hội thảo SOICT 2015 [1] và hội thảo KSE 2016 [2]. CHƯƠNG 3. VẤN ĐỀ ĐỊNH VỊ VÀ ĐỊNH TUYẾN TRONG BÀI TOÁN GIAO VÀ NHẬN ĐA LOẠI HÀNG HÓA, ĐA TUYẾN 3.1. Tổng quan bài toán giao và nhận đa loại hàng hóa, đa tuyến Bài toán giao và nhận đa loại hàng hóa, đa tuyến trong hậu cần đô thị sẽ nghiên cứu đồng thời tối thiểu hai trong ba loại hàng hóa: hàng hóa e2c, hàng hóa c2e và hàng hóa c2c. Một trong các nghiên cứu về hàng hóa e2c được trình bày trong bài toán TMZT-VRPTW [57]. Trong bài toán TMZT-VRPTW, một đội xe tải nhỏ xuất phát từ một kho đỗ xe đến điểm trung chuyển nhận hàng và sau đó giao hàng hóa e2c đến khách hàng trong khung thời gian quy định. Trong nghiên cứu [57], tác giả Nguyen và công sự đề xuất thuật toán tìm kiếm Tabu để giải quyết bài toán này. Sau đó, các tác giả tiếp tục mở rộng thuật toán tìm kiếm Tabu này để giải quyết một bài toán mới: Bài toán giao và nhận hàng hóa, đa tuyến với khung thời gian và đồng bộ MT-PDTWS [58]. Bên cạnh thực hiện giao hàng hóa e2c tương tự bài toán TMZT-VRPTW, đội xe tải nhỏ trong bài toán MT-PDTWS cho phép nhận các hàng hóa c2e tại khách hàng và vận tải đến các điểm trung chuyển. Trong công trình [40], tác giả Crainic và cộng sự tổng quát hóa hai bài toán TMZT-VRPTW và MT-PDTWS, bằng một đề xuất cho bài toán mới “Giao và nhận đa loại hàng hóa, đa tuyến với khung thời gian và đồng bộ MTT-PDTWS”. Bài toán MTT-PDTWS nghiên cứu đồng thời ba loại hàng hóa: hàng hóa e2c, hàng hóa c2e và hàng hóa c2c. 3.2. Bài toán giao và nhận đa loại hàng hóa, đa tuyến với khung thời gian và đồng bộ 3.2.1. Phát biểu bài toán Bài toán MTT-PDTWS sử dụng một đội xe tải nhỏ có trọng tải Q và chi phí sử dụng cố định F cho mỗi xe tải nhỏ. Xe tải nhỏ xuất phát từ một kho đỗ xe g và thực hiện vận tải các lộ trình giao hàng e2c và nhận hàng c2e. Đối với loại hàng hóa e2c, hàng sẽ được tập trung tại điểm trung chuyển và được xe tải nhỏ giao đến khách hàng. Ngược lại, xe tải nhỏ sẽ nhận các hàng hóa c2e từ khách hàng và chuyển đến các điểm trung chuyển. Trong mô hình bài toán, mỗi điểm trung chuyển 𝑠 ∈ 𝑆 được quy định: 15
• Xe tải nhỏ không được phép chờ tại điểm trung chuyển; • Khung thời gian hoạt động [𝑡(𝑠) − 𝜂, 𝑡(𝑠)]: quy định thời điểm sớm nhất và trễ nhất cho phép xe tải nhỏ đến. Trong trường hợp xe vận tải đến trước thời điểm 𝑡(𝑠) − 𝜂, xe tải nhỏ có thể đỗ tạm thời tại một trạm chờ 𝑤 ∈ 𝑊; • Khoảng thời gian tương ứng để bốc và dỡ hàng hóa của một xe tải nhỏ là ∅(𝑠) và ∅′ (𝑠). Yêu cầu vận tải hàng hóa có thể một trong các yêu cầu sau: • Nhận hàng hóa e2c từ các điểm trung chuyển tại các khung thời gian khác nhau; • Yêu cầu nhận và giao hàng hóa c2e đến một trong các điểm trung chuyển đăng ký trước; • Yêu cầu nhận và giao hàng hóa c2c đến khách hàng khác. Các yêu cầu nhận hàng e2c được biểu diễn bởi tập hợp 𝐶 𝐷 . Tập hợp 𝐶 𝑃 là tập hợp của các yêu cầu nhận và giao hàng c2e từ khách hàng và chuyển đến điểm trung chuyển. Yêu cầu nhận và giao hàng c2c được biểu diễn bởi tập hợp (𝑝̅ , 𝑞̅ ) ∈ 𝑅. Trong đó, tập hợp các yêu cầu nhận 𝑝 𝑞 hàng c2c, 𝑝̅ ∈ 𝐶𝑐2𝑐 , và yêu cầu giao hàng c2c, 𝑞̅ ∈ 𝐶𝑐2𝑐 . Mỗi yêu cầu 𝑃 𝐷 vận tải của khách hàng 𝑖 ∈ {𝐶 𝐷 ∪ 𝐶 𝑃 ∪ 𝐶𝑐2𝑐 ∪ 𝐶𝑐2𝑐 } sẽ được đại diện bởi bộ thông tin (𝑖, 𝑞𝑖 , 𝛿(𝑖), [𝑒𝑖 , 𝑙𝑖 ]) với: • 𝑞𝑖 > 0: số lượng hàng hóa yêu cầu nhận hoặc yêu cầu giao. Với (𝑝̅ , 𝑞̅ ) ∈ 𝑅 thì 𝑞𝑝̅ = −𝑞𝑑̅ ; • [𝑒𝑖 , ℓ𝑖 ]: khung thời gian cho phép nhận hoặc giao hàng; • 𝛿(𝑖): thời gian thực hiện nhận hoặc lấy hàng hóa. Ngoài ra, mỗi yêu cầu 𝑑 ∈ 𝐶 𝐷 có một điểm trung chuyển tập trung hàng e2c tương ứng. Mỗi yêu cầu nhận và giao hàng 𝑝 ∈ 𝐶 𝑃 có danh sách các điểm trung chuyển được phép chuyển hàng. Việc lựa chọn một điểm trung chuyển thích hợp trong danh sách điểm trung chuyển này là một quyết định của bài toán. Gọi 𝑐𝑖𝑗 là chi phí di chuyển giữa 2 điểm và đồ thị miêu tả bài toán được 𝐷 𝑃 tạo thành từ các điểm 𝑖, 𝑗 ∈ {𝑔 ∪ 𝐶 𝐷 ∪ 𝐶 𝑃 ∪ 𝐶𝑐2𝑐 ∪ 𝐶𝑐2𝑐 ∪ 𝑆 ∪ 𝑊}. Các yêu cầu của bài toán: • Yêu cầu định vị: xác định các yêu cầu nhận hàng hóa c2e với các điểm trung chuyển tương ứng; • Yêu cầu định tuyến: tìm tập hợp các lộ trình theo từng xe tải nhỏ. Mục tiêu của bài toán tối thiểu hóa tổng chi phí bao gồm: chi phí di chuyển của đội xe tải nhỏ, chi phí cố định sử dụng xe tải nhỏ đáp ứng: 16
• Mỗi xe tải nhỏ xuất phát và kết thúc hành trình tại kho đỗ xe g. Các xe tải nhỏ vận tải theo chiến lược Pseudo-Backhaul [79]; • Mỗi yêu cầu nhận hàng c2e chuyển ra ngoài thành phố p được chỉ định cho một điểm trung chuyển thuộc tập hợp 𝑆𝑝 ; • Trong hành trình vận tải, xe tải nhỏ phải đến trong khung thời gian hoạt động của điểm trung chuyển; • Hàng hóa c2c nhận và giao trong thành phố thuộc lộ trình của một xe tải nhỏ phải tuân thủ nguyên tắc LIFO. Cụ thể, hàng hóa c2c xe tải nhỏ nhận sau sẽ được thực hiện giao trước để không cần phải dỡ các hàng hóa c2c khác ra khỏi xe; • Mỗi yêu cầu vận tải của khách hàng 𝑖 ∈ {𝐶 𝑃 ∪ 𝐶 𝐷 ∪ 𝐶𝑐2𝑐 𝑃 ∪ 𝐷 𝐶𝑐2𝑐 } do một xe tải nhỏ duy nhất phục vụ trong khung thời gian cho phép; • Tổng trọng tải của hàng hóa đang vận chuyển trên xe tải nhỏ không được phép vượt quá trọng tải Q. 3.2.2. Mô hình bài toán Bài toán MTT-PDTWS được định nghĩa trên đồ thị 𝐺 = (𝑉, 𝐴). 𝑉 là tập hợp các đỉnh trên đồ thị và bao gồm các tập con 𝑉 = {𝑔 ∪ 𝐶 𝐷 ∪ 𝐶 𝑃 ∪ 𝐷 𝑃 𝑃 𝐶𝑐2𝑐 ∪ 𝐶𝑐2𝑐 ∪ 𝑆 ∪ 𝑊}.𝐴 = {(𝑔, 𝑗): 𝑗 ∈ 𝐶 𝑃 ∪ 𝐶𝑐2𝑐 ∪ 𝑆} ∪ {(𝑠, 𝑗): 𝑠 ∈ 𝑃 𝑆, 𝑗 ∈ 𝑔 ∪ 𝐶 ∪ 𝐶 ∪ 𝐶𝑐2𝑐 ∪ 𝑆 ∪ 𝑊} ∪ {(𝑝, 𝑗): 𝑝 ∈ 𝐶 𝑃 , 𝑗 ∈ 𝐶 𝑃 ∪ 𝑆 ∪ 𝐷 𝑃 𝑃 𝑊} ∪ {(𝑑, 𝑗): 𝑑 ∈ 𝐶 𝐷 , 𝑗 ∈ 𝐶 𝐷 ∪ 𝐶 𝑃 ∪ 𝐶𝑐2𝑐 ∪ 𝑆 ∪ 𝑊 ∪ 𝑔} ∪ {(𝑝, 𝑗): 𝑝 ∈ 𝑃 𝑃 𝐷 } 𝐷 𝐷 𝑃 𝐶𝑐2𝑐 , 𝑗 ∈ 𝐶𝑐2𝑐 ∪ 𝐶𝑐2𝑐 ∪ {(𝑑, 𝑗): 𝑑 ∈ 𝐶𝑐2𝑐 , 𝑗 ∈ 𝐶𝑐2𝑐 ∪ 𝐶𝑐2𝑐 ∪ 𝐶𝑃 ∪ 𝑆 ∪ 𝑊 ∪ 𝑔} ∪ {(𝑤, 𝑠): 𝑤 ∈ 𝑊, 𝑠 ∈ 𝑆. Các biến quyết định được định nghĩa như sau: • 𝑋𝑖𝑗𝑘 𝑢 : nhận giá trị 1 nếu cạnh (𝑖, 𝑗) ∈ 𝐴 thuộc lộ trình của xe tải nhỏ 𝑘 và cạnh này có thứ tự thứ 𝑢 trong hành trình vận tải; nhận giá trị 0 trong trường hợp ngược lại; • 𝑌𝑝𝑠 : nhận giá trị 1 nếu hàng hóa c2e, 𝑝 ∈ 𝐶 𝑃 , được chỉ định cho điểm trung chuyển 𝑠 ∈ 𝑆𝑝 ; nhận giá trị 0 trong trường hợp ngược lại. Mô hình được trình bày chi tiết trong bản luận án đầy đủ. 3.3. Bài toán giao và nhận đa loại hàng hóa, đa tuyến ở hai mức với khung thời gian và đồng bộ 3.3.1. Đồng bộ hàng hóa tại điểm trung chuyển Kho trung gian tại điểm trung chuyển 𝑠 ∈ 𝑆 có khả năng chứa tối đa 𝐿𝑠 . Thời gian bốc hàng hoặc dỡ hàng vào kho trung gian được giả định là 17
0. Hàng hóa đồng bộ tại điểm trung chuyển giữa các xe tải tuân thủ yêu cầu sau: • Quá trình bốc hoặc dỡ hàng của một xe tải là liên tục; • Hàng hóa được phép lưu trữ tạm thời tại kho trung gian nếu xe tải nhận hàng chưa sẵn sàng; • Xe tải phải thực hiện dỡ hàng ngay khi xe đến điểm trung chuyển; • Thời điểm đến của xe tải phải thuộc khung thời gian hoạt động của điểm trung chuyển; • Quá trình bốc hàng của xe tải chỉ có thể bắt đầu sau khi xe tải này kết thúc quá trình dỡ hàng (nếu có) và tất cả hàng hóa cần bốc đã sẵn sàng. Nếu không, hàng hóa cần bốc đã đến và phải được lưu trữ tại kho trung gian. Tuân thủ các yêu cầu trên, bài toán cho phép cơ chế đồng bộ tổng quát giữa n xe tải lớn và m xe tải nhỏ. 3.3.2. Mô hình bài toán Bài toán 2E-MTT-PDTWS được nghĩa sử dụng đồ thị có hướng 𝐺 = (𝑉, 𝐴) để biểu diễn hai mức vận tải. Mức 1 được biểu diễn bởi đồ thị 𝐺1 = (𝑉1 , 𝐴1 ) với 𝑉1 = {𝑔1 ∪ 𝑆 ∪ 𝑊} và 𝐴1 = {(𝑖, 𝑗): 𝑖 ∈ 𝑉1 \𝑊, 𝑗 ∈ 𝑉1 } ∪ {(𝑤, 𝑠): 𝑤 ∈ 𝑊, 𝑠 ∈ 𝑆}. Mức 2 được biểu diễn bởi đồ thị 𝐺2 = 𝐷 𝑃 (𝑉2 , 𝐴2 ) với 𝑉2 = {𝑔2 ∪ 𝐶 𝐷 ∪ 𝐶 𝑃 ∪ 𝐶𝑐2𝑐 ∪ 𝐶𝑐2𝑐 ∪ 𝑆 ∪ 𝑊} và 𝐴2 = 𝑃 {(𝑔2 , 𝑗): 𝑗 ∈ 𝐶 ∪ 𝐶𝑐2𝑐 ∪ 𝑆} ∪ {(𝑠, 𝑗): 𝑠 ∈ 𝑆, 𝑗 ∈ 𝑔2 ∪ 𝐶 𝐷 ∪ 𝐶 𝑃 ∪ 𝑃 𝑃 𝐶𝑐2𝑐 ∪ 𝑆 ∪ 𝑊} ∪ {(𝑝, 𝑗): 𝑝 ∈ 𝐶 𝑃 , 𝑗 ∈ 𝐶 𝑃 ∪ 𝑆 ∪ 𝑊} ∪ {(𝑑, 𝑗): 𝑑 ∈ 𝑃 𝑃 𝑃 𝐶 , 𝑗 ∈ 𝐶 𝐷 ∪ 𝐶 𝑃 ∪ 𝐶𝑐2𝑐 𝐷 ∪ 𝑆 ∪ 𝑊 ∪ 𝑔2 } ∪ {(𝑝, 𝑗): 𝑝 ∈ 𝐶𝑐2𝑐 , 𝑗 ∈ 𝐶𝑐2𝑐 ∪ 𝐷 } 𝐷 𝐷 𝑃 𝑃 𝐶𝑐2𝑐 ∪ {(𝑑, 𝑗): 𝑑 ∈ 𝐶𝑐2𝑐 , 𝑗 ∈ 𝐶𝑐2𝑐 ∪ 𝐶𝑐2𝑐 ∪ 𝐶 ∪ 𝑆 ∪ 𝑊 ∪ 𝑔2 } ∪ {(𝑤, 𝑠): 𝑤 ∈ 𝑊, 𝑠 ∈ 𝑆}. Các biến quyết định của bài toán được định nghĩa như sau: • 𝑋𝑖𝑗𝑢𝑘1 : nhận giá trị 1 nếu cạnh (𝑖, 𝑗) ∈ 𝐴1 thuộc lộ trình của xe tải lớn 𝑘 ∈ 𝐾1 và cạnh này có thứ tự thứ 𝑢 trong hành trình vận tải; nhận giá trị 0 trong trường hợp ngược lại; • 𝑋𝑖𝑗𝑢𝑘 2 : nhận giá trị 1 nếu cạnh (𝑖, 𝑗) ∈ 𝐴2 thuộc lộ trình của xe tải nhỏ 𝑘 ∈ 𝐾2 và cạnh này có thứ tự thứ 𝑢 trong hành trình vận tải; nhận giá trị 0 trong trường hợp ngược lại. • 𝑌𝑝𝑠 : nhận giá trị 1 nếu hàng hóa c2e, 𝑝 ∈ 𝐶 𝑃 , được chỉ định cho điểm trung chuyển 𝑠 ∈ 𝑆𝑝 ; nhận giá trị 0 trong trường hợp ngược lại; 18
• 𝑍𝑑𝑠 : nhận giá trị 1 nếu hàng hóa e2c, 𝑑 ∈ 𝐶 𝐷 , được chỉ định cho điểm trung chuyển 𝑠 ∈ 𝑆𝑑 ; nhận giá trị 0 trong trường hợp ngược lại; Mô hình được trình bày chi tiết trong bản luận án đầy đủ. 3.4. Thuật toán giải bài toán MTT-PDTWS và 2E-MTT-PDTWS 3.4.1. Cấu trúc chung của thuật toán Thuật toán tìm kiếm lân cận lớn thích nghi ALNS cho phép lựa chọn thao tác hủy và thao tác chỉnh sửa từ tập hợp các thao tác có sẵn tại mỗi bước lặp của thuật toán. Mỗi thao tác được gán một trọng số và được lựa chọn theo xác suất dựa vào trọng số này tại mỗi bước lặp của thuật toán. 3.4.1.1. Thuật toán ALNS giải bài toán MTT-PDTWS Thuật toán 3.2. Thuật toán ALNS giải bài toán MTT-PDTWS Đồ thị G=(V, E); 𝑉 = {𝑔 ∪ 𝐶 𝐷 ∪ 𝐶 𝑃 ∪ 𝐶𝑐2𝑐 𝐷 𝑃 ∪ 𝐶𝑐2𝑐 ∪ 𝑆 ∪ 𝑊}; Đầu 𝐸 = {𝑖, 𝑗} với ∀𝑖, 𝑗 ∈ 𝑉; vào: 𝑐𝑖𝑗 : chi phí di chuyển giữa 2 điểm 𝑖, 𝑗 ∈ 𝐸; F, Q: chi phí sử dụng và trọng tải của một xe tải nhỏ. Đầu ra: Lời giải bài toán 𝑧𝑏𝑒𝑠𝑡 1. Khởi tạo lời giải ban đầu z; 2. Cập nhật lời giải tốt nhất 𝑧𝑏𝑒𝑠𝑡 ← 𝑧; 3. Khởi tạo trọng số của các thao tác hủy và thao tác chỉnh sửa; 4. repeat 5. Lựa chọn xác suất một thao tác hủy và một thao tác chỉnh sửa dựa theo trọng số của các thao tác; 6. Áp dụng thao tác hủy và thao tác chỉnh sửa được lựa chọn để tạo ra lời giải 𝑧 ′ ; 7. Cập nhật 𝑧 ← 𝑧 ′ nếu thỏa mãn tiêu chí chấp nhận lời giải mới; 8. Cập nhật 𝑧𝑏𝑒𝑠𝑡 ← 𝑧 ′ nếu lời giải mới tốt hơn lời giải tốt nhất hiện tại; 9. Cập nhật trọng số của các thao tác hủy, thao tác chỉnh sửa; 10. until thỏa mãn điều kiện dừng; 11. Thực hiện thủ tục nâng cao chất lượng lời giải; 12. return lời giải tốt nhất 𝑧𝑏𝑒𝑠𝑡 ; Thủ tục nâng cao chất lượng lời giải thực hiện cải thiện chất lượng các lộ trình thông qua hai bước: inter-route và intra-route [80]. 3.4.1.2. Thuật toán ALNS giải bài toàn 2E-MTT-PDTWS Thuật toán 3.3. Thuật toán ALNS giải bài toán 2E-MTT-PDTWS Đầu Đồ thị 𝐺 = (𝑉, 𝐴); vào: 𝑐𝑖𝑗 , 𝑡𝑖𝑗 : chi phí và thời gian di chuyển giữa 2 điểm ∀𝑖, 𝑗 ∈ 𝐴; 19
𝐹1 , 𝑄1 : chi phí sử dụng và trọng tải của một xe tải lớn; 𝐹2 , 𝑄2 : chi phí sử dụng và trọng tải của một xe tải nhỏ; Đầu Lời giải bài toán 𝑧𝑏𝑒𝑠𝑡 ra: 1. Khởi tạo lời giải ban đầu z; 2. Cập nhật 𝑧𝑏𝑒𝑠𝑡 ← 𝑧; 3. Khởi tạo trọng số của tất cả thao tác hủy và thao tác chỉnh sửa bằng giá trị 1; 4. repeat 5. Lựa chọn xác suất một thao tác hủy theo trọng số của thao tác; 6. Áp dụng thao tác hủy được lựa chọn và thao tác chỉnh sửa đối với phần thứ 2 của lời giải z để tạo ra lời giải 𝑧 ′′ ; 7. if 𝑧 ′′ thỏa mãn tiêu chí lựa chọn lời giải mới then 8. Áp dụng thuật toán tham lam đối với 𝑧 ′′ để tạo ra 𝑧 ′ ; 9. Cập nhật 𝑧 ← 𝑧 ′ ; 10. if lời giải 𝑧 ′ tốt hơn lời giải 𝑧𝑏𝑒𝑠𝑡 then 11. Cập nhật 𝑧𝑏𝑒𝑠𝑡 ← 𝑧 ′ ; 12. end if 13. end if 14. Cập nhật trọng số của các thao tác; 15. until thỏa mãn điều kiện dừng; 16. return kết quả tốt nhất 𝑧𝑏𝑒𝑠𝑡 ; 3.4.1.3. Thuật toán heuristic lập lịch vận tải ở mức 1 cho bài toán 2E-MTT-PDTWS Với lịch vận tải của xe tải nhỏ đã được xác định, mỗi yêu cầu vận tải c2e hoặc e2c sẽ có thời điểm bốc hàng lên xe tải lớn (𝑡 𝑝 ) hoặc thời điểm dỡ hàng từ xe tải nhỏ (𝑡 𝑑 ). Từ đó, các xe tải lớn sẽ được lập lịch như sau: • Xuất phát từ trung tâm CDC, đến điểm trung chuyển và dỡ hàng e2c tại thời điểm 𝑡 𝑑 ; • Đến các điểm trung chuyển và bốc hàng c2e tại thời điểm 𝑡 𝑝 và trở về trung tâm CDC. Một hành trình của xe tải lớn sẽ thuộc một trong ba trường hợp sau: chỉ gồm một lộ trình nhận hàng mức 1; chỉ gồm một lộ trình giao hàng mức 1; gồm một lộ trình giao hàng mức 1 và sau đó là một lộ trình nhận hàng mức 1. Mục đích của thuật toán là tạo ra tối đa các hành trình của xe tải lớn ở trường hợp thứ ba để giảm số lượng xe tải lớn tham gia vận tải. 3.4.2. Các cấu phần chính của thuật toán ALNS 3.4.2.1. Khởi tạo lời giải ban đầu 3.4.2.1.1. Khởi tạo lời giải ban đầu cho bài toán MTT-PDTWS 20