Nghiên cứu và phát triển các thuật toán giải quyết các bài toán tối ưu trong giao thông vận tải người và hàng hóa.

Nội dung tài liệu: Nghiên cứu và phát triển các thuật toán giải quyết các bài toán tối ưu trong giao thông vận tải người và hàng hóa.

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN VĂN SƠN NGHIÊN CỨU VÀ PHÁT TRIỂN CÁC THUẬT TOÁN GIẢI QUYẾT CÁC BÀI TOÁN TỐI ƯU TRONG GIAO THÔNG VẬN TẢI NGƯỜI VÀ HÀNG HÓA Ngành: Khoa học máy tính Mã số: 9480101 TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội - 2023
2. Công trình được hoàn thành tại: Trường Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: 1. TS. Phạm Quang Dũng 2. PGS. TS. Nguyễn Xuân Hoài Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Trường họp tại Trường Đại học Bách khoa Hà Nội Vào hồi giờ, ngày tháng năm Có thể tìm hiểu luận án tại thư viện: 1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam
3. GIÎI THIỆU Ngành giao thông vªn t£i đóng vai trá quan trọng trong ph¡t triºn kinh t¸ và k¸t nèi giúa c¡c vùng. Điều này càng đúng hơn trong n·n kinh t¸ toàn c¦u, bao gồm sự t«ng cường hñp t¡c kinh t¸ li¶n quan đến sự di chuyºn cõa người và hàng hóa. Bài to¡n t¼m lë tr¼nh tèi ưu cho c¡c xe phục vụ c¡c y¶u c¦u vªn chuyºn được gọi là Bài to¡n Định tuy¸n Xe (VRP). Đây là mët bài to¡n thuëc lớp NP-khó. Hàng ngàn bài b¡o tr¶n th¸ giới đã được dành cho v§n đề này. Nhi·u nhà nghi¶n cùu đã đề xu§t nhi·u mô h¼nh và thuªt to¡n cho VRP và c¡c bi¸n thº cõa nó. Vi»c nghi¶n cùu và mở rëng bài to¡n với sự k¸t hñp cõa c¡c y¸u tè thực t¸ làm t«ng kh£ n«ng ùng dụng cõa bài to¡n VRP v¨n là mët v§n đề mang t½nh thời sự. V¼ vªy, luªn ¡n này nh¬m nghi¶n cùu và đề xu§t nhúng bi¸n thº mới cõa VRPs, xem x²t mët sè y¸u tè trong th¸ giới thực để mở rëng VRPs mët c¡ch linh ho¤t và thực t¸ hơn. Do t¦m quan trọng thực t¸ cõa VRP, mục ti¶u ch½nh cõa luªn ¡n này là mở rëng c¡c bài to¡n VRP hi»n có mët c¡ch linh ho¤t và thực t¸ hơn. Điều quan trọng là c¡c bi¸n thº mới được x¥y dựng và c¡c thuªt to¡n phù hñp được ph¡t triºn để gi£i quy¸t chúng mët c¡ch hi»u qu£ nh§t có thº. Theo kh£o s¡t tø c¡c công tr¼nh khoa học cũng như ho¤t động vªn hành thực t¸ cõa c¡c công ty vªn t£i, ho¤t động định tuy¸n thường được ph¥n thành hai kịch b£n: tĩnh và động. Do đó, luªn ¡n tªp trung vào hai trường hñp điển h¼nh này cõa c¡c bài to¡n VRP. Đối với bài to¡n VRP tĩnh, c¡c t¡c gi£ trong Vidal et al. 2020 tuy¶n bè r¬ng mët trong nhúng mục ti¶u quan trọng nh§t cõa bài to¡n định tuy¸n là c¥n b¬ng ph¥n bê khèi lượng công vi»c để đảm b£o c¡c k¸ ho¤ch được ch§p nhªn, duy tr¼ sự hài láng và tinh th¦n cõa nh¥n vi¶n, gi£m thời gian làm th¶m giờ và để gi£m t­c ngh³n trong sû dụng tài nguy¶n. Do sùc chùa h¤n ch¸, quy mô đội xe cè định và h¤n ch¸ v· thời gian, c¡c xe ph£i vªn chuyºn c¡c s£n ph©m tø nhi·u trung t¥m ph¥n phèi đến kh¡ch hàng và thực hi»n nhi·u chuy¸n đi. Tuy nhi¶n, mët sè chuy¸n đi cõa c¡c phương ti»n được lªp k¸ ho¤ch chở qu¡ ½t hàng hóa trong c¡c thực t¸ do ràng buëc thời gian chặt. V¼ vªy, luªn ¡n này đề xu§t mët bi¸n thº mới cõa bài to¡n VRP tĩnh trong đó x²t đến h¦u h¸t c¡c ràng buëc đã được nghi¶n cùu kỹ lưỡng và bao gồm mët ràng buëc mới v· giới h¤n dưới cõa t£i trọng chưa tøng được nghi¶n cùu trong c¡c công tr¼nh. Luªn ¡n này mô h¼nh hóa bài to¡n xem x²t dưới d¤ng quy ho¤ch nguy¶n tuy¸n t½nh hén hñp (MILP), ph¥n t½ch c¡c th¡ch thùc cõa c¡c ràng buëc mới v· giới h¤n dưới t£i trọng và đề xu§t mët khung t¼m ki¸m l¥n cªn lớn th½ch ùng (ALNS) để gi£i quy¸t nó. Đối với bài to¡n VRP động, mët mô h¼nh vªn chuyºn người mới 1
4. được nghi¶n cùu, đây là ph¦n mở rëng cõa bài to¡n chia s´ chuy¸n đi do Li et al. 2014 đề xu§t. Trong mô h¼nh đó, người và hàng hóa có thº chia s´ chuy¸n đi tr¶n cùng m¤ng lưới taxi và thông tin v· c¡c y¶u c¦u trong tương lai được dự đoán. Mët mô h¼nh to¡n học mới và mët thuªt to¡n học dựa tr¶n dú li»u đưñc đề xu§t. Đồng thời, mët thuªt to¡n điều phèi lịch tr¼nh taxi khai th¡c c¡c thông tin dự đoán cũng được ph¡t triºn trong luªn ¡n này. Động lực nghi¶n cùu Vi»c tèi ưu hóa giao thông vªn t£i đã trở thành mët v§n đề lớn trong nhúng n«m g¦n đây. Bài to¡n định tuy¸n là mët th¡ch thùc mới đối với ngành giao thông vªn t£i: n¥ng cao n«ng su§t và gi£m chi ph½ b¬ng c¡ch t«ng sè lượng kh¡ch hàng được phục vụ, gi£m thời gian và chi ph½ vªn chuyºn để đạt được k¸ ho¤ch nguồn nh¥n lực tèt và ho¤t động hi»u qu£. Nghi¶n cùu v· VRP không ch¿ mang l¤i lñi ½ch cho c¡c công ty vªn t£i mà cán cho c£ x¢ hëi. Điều này thúc đ©y chúng tôi l§p đầy kho£ng trèng trong tài li»u v· mët sè bài to¡n VRP b¬ng c¡ch k¸t hñp c¡c y¸u tè trong th¸ giới thực để mở rëng c¡c bài to¡n này mët c¡ch linh ho¤t và thực t¸ hơn. Phương ph¡p Phương ph¡p luªn cõa luªn v«n này như sau: • Nghi¶n cùu lý thuy¸t c¡c bi¸n thº cõa bài to¡n VRP. • Ph¥n t½ch c¡c công tr¼nh khoa học li¶n quan đến c¡c bài to¡n được xem x²t. • Thi¸t k¸ c¡c mô h¼nh thực t¸ và húu ½ch cho bài to¡n VRP đang xem x²t. • Đề xu§t c¡c thuªt to¡n metaheuristic hi»u qu£ để gi£i quy¸t c¡c mô h¼nh VRP nghi¶n cùu. Ph¤m vi nghi¶n cùu C¡c bài to¡n VRP là c¡c bài to¡n r§t phùc t¤p bao gồm nhi·u bài to¡n con và bi¸n thº. Do đó, ph¤m vi cõa luªn ¡n này là nghi¶n cùu hai bài to¡n định tuy¸n giao thông thực t¸ điển h¼nh cho hai lo¤i VRP, tĩnh và động. Trong lớp bài to¡n VRP tĩnh, bài to¡n ph¥n phèi hàng hóa được nghi¶n cùu. Bài to¡n xem x²t sự k¸t hñp c¡c ràng buëc thực t¸ để gi£i quy¸t c¡c v§n đề thực t¸ t¤i mët trong nhúng công ty súa lớn nh§t Vi»t Nam. Trong lớp bài to¡n VRP động, bài to¡n lªp lịch tr¼nh taxi động với thông tin dự b¡o được nghi¶n cùu. Bài to¡n này được mở rëng tø bài to¡n VRP chia s´ chuy¸n đi mới do Li et al. 2014 đề xu§t, trong đó người và hàng hóa được phục vụ tr¶n cùng mët m¤ng lưới taxi. 2
5. C¡c bài to¡n được xem x²t đều là c¡c bài to¡n NP -khó. Hơn núa, sự k¸t hñp cõa c¡c ràng buëc thực t¸ làm cho v§n đề trở n¶n th¡ch thùc hơn. V¼ vªy, luªn ¡n chõ y¸u tªp trung vào c¡c thuªt to¡n heuristic/metaheuristic để gi£i quy¸t c¡c bài to¡n đề xu§t. Đóng góp ch½nh Luªn ¡n này có ba đóng góp ch½nh bao gồm: • Với mục ti¶u ph¡t triºn c¡c mô h¼nh vªn chuyºn hàng hóa để gi£i quy¸t c¡c v§n đề thực t¸ cõa doanh nghi»p, luªn ¡n đề xu§t mët bài to¡n vªn chuyºn s£n ph©m mới có t½nh đến h¦u h¸t c¡c ràng buëc đã được nghi¶n cùu kỹ lưỡng, đặc bi»t là với mët ràng buëc mới v· giới h¤n dưới t£i trọng chưa được nghi¶n cùu trong c¡c công tr¼nh khoa học. Luªn ¡n x¥y dựng bài to¡n dưới d¤ng mô h¼nh MILP và đề xu§t mët sè thuªt to¡n metaheuristic hi»u qu£ để gi£i bài to¡n đó. C¡c th½ nghi»m được thực hi»n trong c¡c t¼nh huèng kh¡c nhau để kiºm tra hi»u qu£ cõa c¡c thuªt to¡n. • Đối với mô h¼nh vªn t£i hành kh¡ch, mët bi¸n thº mới cõa mô h¼nh định tuy¸n vªn t£i taxi chia s´ trong kịch b£n động được ph¡t triºn trong luªn ¡n này. Trong mô h¼nh này, người và hàng hóa được phục vụ trong cùng mët m¤ng lưới taxi, trong đó h» thèng định tuy¸n c¦n đề xu§t tuy¸n đường tèt nh§t cho tài x¸ taxi không t£i để cơ hëi nhªn được nhu c¦u vªn chuyºn mới cao khi taxi r£nh réi. Chúng tôi đề xu§t mët thuªt to¡n hi»u qu£ để định tuy¸n c¡c taxi và khai th¡c c¡c thông tin dự đoán. • Luªn ¡n này cũng đã đ· xu§t mët thuªt to¡n th½ch nghi và dựa tr¶n dú li»u để học quy tr¼nh Poison không thu¦n nh§t nh¬m dự đoán c¡c y¶u c¦u vªn chuyºn trong tương lai giúp gi£m thiºu kho£ng c¡ch không t£i cõa phương ti»n. K¸t qu£ thực nghi»m chùng minh r¬ng vi»c ¡p dụng c£i ti¸n hướng di chuyºn trong định tuy¸n dựa tr¶n dự đoán nhu c¦u d¨n đến di chuyºn linh ho¤t và hi»u qu£ di chuyºn têng thº. Nghi¶n cùu này đã li¶n k¸t c¡c v§n đề giao thông với học m¡y, vèn được kỳ vọng s³ gi£i quy¸t c¡c v§n đề giao thông truy·n thèng. C§u trúc luªn ¡n Luªn ¡n được bè cục như sau: • Chương 1 cung c§p mët sè ki¸n thùc n·n t£ng v· bài to¡n VRP và c¡c thuªt to¡n gi£i quy¸t c¡c bài to¡n VRP. • Chương 2 tr¼nh bày bài to¡n ph¥n phèi s£n ph©m, mô h¼nh, c¡c th¡ch thùc và thuªt to¡n ALNS được điều ch¿nh để gi£i quy¸t bài to¡n. Trong thuªt 3
6. to¡n đề xu§t, gi£i ph¡p ban đầu được t¤o và sau đó c¡c chi¸n lược t¼m ki¸m l¥n cªn lớn th½ch nghi được ¡p dụng để c£i thi»n ch§t lượng cõa gi£i ph¡p . Hi»u su§t cõa thuªt to¡n đề xu§t được so s¡nh với hi»u su§t cõa c¡c phương ph¡p phỏng đoán kh¡c b¬ng c¡ch ti¸n hành c¡c thû nghi»m sè mở rëng để đánh gi¡ kh£ n«ng ¡p dụng cõa thuªt to¡n được đề xu§t trong c¡c ùng dụng trong th¸ giới thực. • Chương 3 nghi¶n cùu bài to¡n định tuy¸n taxi chia s´ hành kh¡ch và bưu ki»n trong kịch b£n động. Mët phương ph¡p học tªp dựa tr¶n dú li»u được ph¡t triºn để dự đoán c¡c y¶u c¦u vªn chuyºn mới và mët thuªt to¡n hi»u qu£ đưñc đề xu§t để định tuy¸n taxi và khai th¡c c¡c y¶u c¦u được dự đoán trong tương lai. • Chương K¸t luªn têng k¸t c¡c k¸t qu£ nghi¶n cùu và định hướng nghi¶n cùu trong tương lai. 4
7. Chương 1 KIẾN THỨC CƠ SÐ 1.1 Bài to¡n tèi ưu hóa C¡c bài to¡n tèi ưu hóa (OP) là c¡c bài to¡n trong đó c¦n x¡c định mët tªp n hñp c¡c bi¸n quy¸t định chưa bi¸t fxg1 sao cho hàm mục ti¶u f được tèi thiºu hóa / cực đại hóa và mët sè ràng buëc được thỏa m¢n (Boyd et al. 2004) (tø b¥y giờ chúng ta s³ ch¿ xem x²t mục ti¶u tèi thiºu hóa). Định nghĩa 1. (Boyd et al. 2004) D¤ng chu©n cõa mët bài to¡n tèi ưu hóa là: Tèi thiºu hóa f(x) ∗ thỏa m¢n gj(x) = 0; j = 1; : : : ; m ; ∗ gj(x) ≤ 0; j = m + 1; : : : ; m; xi 2 Di; 8i = 1; : : : ; n trong đó x = fx1; x2; : : : ; xng là v²c tơ bi¸n quy¸t định, m là têng sè ràng buëc, ∗ m là têng sè ràng buëc d¤ng phương tr¼nh và Di là mi·n x¡c định cõa xi. 1.2 Vehicle Routing Problem and c¡c bài to¡n mở rëng 1.2.1 Bài to¡n định tuy¸n xe với ràng buëc t£i trọng Bài to¡n VRP ti¶u chu©n là bài to¡n định tuy¸n xe có ràng buëc t£i trọng (CVRP), trong đó mët đội xe cè định đồng nh§t đưñc lªp lë tr¼nh để phục vụ nhu c¦u cõa mët tªp kh¡ch hàng vªn chuyºn hàng hóa tø mët kho cụ thº với chi ph½ vªn chuyºn nhỏ nh§t. 1.2.2 Bài to¡n định tuy¸n xe giao và nhªn với ràng buëc thời gian Mët bi¸n thº quan trọng cõa VRP là bài to¡n định tuy¸n xe nhªn và giao hàng với khung thời gian (PDVRPTW). Trong PDVRPTW, bài to¡n y¶u c¦u t¼m mët hoặc nhi·u tuy¸n với chi ph½ tèi thiºu để phục vụ mët sè y¶u c¦u cõa kh¡ch hàng, trong đó méi y¶u c¦u được x¡c định bởi điºm nhªn hàng, điểm giao hàng tương ùng và nhu c¦u (hàng hóa hoặc hành kh¡ch) đưñc vªn chuyºn giúa c¡c vị tr½ này trong kho£ng thời gian x¡c định trước. 5
8. H¼nh 1.2: Rich vehicle routing problem. 1.2.3 Bài to¡n định tuy¸n taxi chia s´ lë tr¼nh H¦u h¸t c¡c mô h¼nh chia s´ chuy¸n đi đều dựa tr¶n bài to¡n định tuy¸n xe phục vụ y¶u c¦u dựa tr¶n cuëc gọi (DARP) nêi ti¸ng. DARP bao gồm vi»c thi¸t k¸ c¡c lë tr¼nh cho đội xe chở mët sè người tø điểm đón tới điểm tr£ theo y¶u c¦u. G¦n đây, Li et al. 2014 đã đề xu§t mô t£ v· bài to¡n lªp lë tr¼nh taxi chia s´ (SARP) động trong đó người và hàng hóa được phục vụ bởi cùng mët m¤ng lưới taxi. C¡c t¡c gi£ trong Li et al. 2014 đã tr¼nh bày c¡c công thùc MILP cho SARP với mët sè ràng buëc thực t¸. 1.2.4 Bài to¡n định tuy¸n xe phong phú Xu hướng mới chõ y¸u tªp trung vào vi»c ¡p dụng VRP và c¡c mở rëng cõa chúng cho c¡c v§n đề trong cuëc sèng thực b¬ng c¡ch k¸t hñp nhi·u ràng buëc thực t¸. Bài to¡n đó được gọi là bài to¡n định tuy¸n xe phong phú (RVRP). H¼nh 1.2 tr¼nh bày mët sè bi¸n thº và mở rëng cõa bài to¡n VRPs. 1.3 Phương ph¡p luªn cho bài to¡n VRP Nhi·u phương ph¡p kh¡c nhau để gi£i quy¸t VRP đã được nghi¶n cùu. C¡c phương ph¡p VRP hi»n t¤i có thº được chia thành hai lo¤i: phương ph¡p gi£i ch½nh x¡c và phương ph¡p không đ¦y đủ. 6
9. Chương 2 MÆ HÌNH HÂA VÀ GIẢI QUYẾT MËT BIẾN THỂ MÎI BÀI TOÁN ĐỊNH TUYẾN TĨNH 2.1 Giới thi»u Trong c¡c kịch b£n định tuy¸n tĩnh, mët công ty nhªn được lượng lớn nhu c¦u tø c¡c kh¡ch hàng có vị tr½ kh¡c nhau méi ngày. Họ thường định tuy¸n c¡c phương ti»n để phục vụ nhúng kh¡ch hàng này vào mët thời điểm cè định (v½ dụ: 8 giờ s¡ng). Công ty sở húu mët đội xe cè định (xe tự sở húu) và có thº thu¶ mët sè xe tø mët sè công ty logistics b¶n thù ba (xe thu¶ ngoài) khi c¦n. Do sùc chùa h¤n ch¸, quy mô đội xe cè định và h¤n ch¸ v· khung thời gian, c¡c phương ti»n ph£i vªn chuyºn c¡c hàng hóa tø nhi·u trung t¥m ph¥n phèi đến kh¡ch hàng và thực hi»n nhi·u chuy¸n đi. Têng trọng lượng s£n ph©m vªn chuyºn trong méi chuy¸n ph£i n¬m trong kho£ng cho ph²p tùy thuëc vào t£i trọng cõa phương ti»n vªn hành. Sự hi»n di»n cõa c¡c ràng buëc giới h¤n dưới t£i trọng làm cho v§n đề trở n¶n khó kh«n hơn. Nhúng y¶u c¦u thực t¸ này đến tø mët trong nhúng công ty ph¥n phèi súa lớn nh§t Vi»t Nam. Với trung b¼nh tr¶n 1000 điểm kh¡ch hàng méi l¦n lªp k¸ ho¤ch, công ty ph£i m§t ½t nh§t mët ngày làm vi»c để l¶n k¸ ho¤ch lë tr¼nh. Theo hiºu bi¸t tèt nh§t cõa chúng tôi, ràng buëc giới h¤n dưới cõa t£i trọng chưa được nghi¶n cùu trong c¡c công tr¼nh khoa học cho lớp bài to¡n VRP tĩnh. B¶n c¤nh đó, sự k¸t hñp cõa c¡c ràng buëc thực t¸ làm cho bài to¡n trở n¶n phùc t¤p hơn r§t nhi·u. C¡c đóng góp ch½nh cõa chương này là: • Chương này đề xu§t mët mô h¼nh bài to¡n VRP tĩnh mới có t½nh ùng dụng cao, với sự k¸t hñp cõa c¡c thuëc t½nh sau: – Có ba lo¤i điểm không gian: c¡c b¢i đỗ xe, c¡c trung t¥m ph¥n phèi và c¡c điểm kh¡ch hàng. – Méi xe có thº thực hi»n nhi·u chuy¸n và l§y hàng t¤i c¡c trung t¥m ph¥n phèi kh¡c nhau trong méi chuy¸n. – Têng trọng lượng hàng trong méi chuy¸n tr¶n xe ph£i lớn hơn hoặc b¬ng trọng lượng tèi thiºu quy định. – Thời gian phục vụ t¤i méi điểm phụ thuëc vào trọng lượng hàng được t£i lên/dỡ xuèng. 7
10. – Méi xe có mët tªp c¡c kh¡ch hàng không được ph²p phục vụ và mët tªp c¡c kh¡ch hàng được ch¿ định phục vụ. • Bài to¡n nghi¶n cùu được mô h¼nh hóa dưới d¤ng mô h¼nh quy ho¤ch nguy¶n tuy¸n t½nh hén hñp (MILP). Mët sè thû nghi»m được thực hi»n tr¶n c¡c kịch b£n thực quy mô nhỏ, c¡c phi¶n b£n ti¶u chu©n và c¡c kịch b£n tự sinh được gi£i b¬ng tr¼nh tèi ưu hóa GUROBI nh¬m x¡c thực mô h¼nh. • Chương này cũng ph¥n t½ch nhúng th¡ch thùc cõa ràng buëc cªn dưới t£i trọng, coi ràng buëc này là mët ràng buëc m·m và đưa nó (với mët h» sè x¡c định) vào hàm mục ti¶u để so s¡nh. Luªn ¡n đã xu§t ba thuªt to¡n x¥y dựng th½ch nghi hi»u qu£ để gi£i quy¸t v§n đề này. 2.2 Mô t£ bài to¡n và mô h¼nh hóa 2.2.1 Mô t£ bài to¡n Mët h» thèng lªp lịch xe nhªn được mët sè lượng lớn y¶u c¦u vªn chuyºn c¡c s£n ph©m súa tø trung t¥m ph¥n phèi đến kh¡ch hàng trong mët thời điểm cè định. Méi y¶u c¦u bao gồm thông tin v· vị tr½ cõa kh¡ch hàng, kho£ng thời gian c¦n phục vụ và trọng lượng c¦n vªn chuyºn. H» thèng thực hi»n lªp lịch tr¼nh và định tuy¸n mët đội xe không đồng nh§t thực hi»n nhi·u chuy¸n đi: mët xe khởi hành tø b¢i đỗ xe, thực hi»n mët chuéi c¡c chuy¸n đi và quay trở l¤i khu vực đỗ xe trong mët ngày làm vi»c. Bài to¡n này nh¬m đạt được sè lượng kh¡ch hàng được phục vụ lớn nh§t, sè lượng xe c¦n thi¸t tèi thiºu và lë tr¼nh xe ch¤y tèt nh§t để têng qu¢ng đường di chuyºn là nhỏ nh§t. Mët v½ dụ v· hành tr¼nh cõa c¡c xe được minh họa trong H¼nh 1.2 trong đó hành tr¼nh cõa mët xe được định tuy¸n theo tr¼nh tự c¡c điểm 0; 1; 2; 3; 4; 5; 6; 7; 8; 0. Xe này thực hi»n 2 chuy¸n, hàng hóa tr¶n méi chuy¸n được x¸p t¤i c¡c trung t¥m ph¥n phèi kh¡c nhau. Trong khi xe kh¡c ph£i ch¤y theo hành tr¼nh 9, 10, 11, 12, 13, 10, 14, 15, 16, 9. Hàng hóa giao cho kh¡ch hàng tr¶n c¡c chuy¸n kh¡c nhau được x¸p t¤i cùng mët trung t¥m ph¥n phèi trong hành tr¼nh này. Giới h¤n sùc chùa là [70; 110] cho méi xe. 8
11. H¼nh 1.2: Mët v½ dụ v· hành tr¼nh cõa c¡c xe trong bài to¡n MTDLC-VR. 2.2.2 K½ hi»u và định nghĩa 2.2.3 Mô h¼nh to¡n học P Chúng tôi định nghĩa sè kh¡ch hàng không được phục vụ bởi gr = η − i2C yi, P k;1 sè xe c¦n thi¸t bởi gv = k2K fkz , và têng qu¢ng đường di chuyºn bởi gc = P Pq(k) P k;q k2K q=1 (i;j)2E di;jxi;j . Bài to¡n MTDLC-VR được mô t£ dưới d¤ng to¡n học như sau: Tèi thiºu hóa F = fgb r + gv + gc (2.1) subject to • Ràng buëc v· luồng cõa hành tr¼nh q(k) q(k) X X k;q X X k;q xi;j = xj;i ; 8k 2 K; 8i 2 V (2.2) j2δ+(i) q=1 j2δ−(i) q=1 • Ràng buëc v· luồng tr¶n méi chuy¸n X k;q X k;q xi;j = xj;i ; 8k 2 K; 8q = 1; 2; : : : ; q(k); 8i 2 C (2.3) j2δ+(i) j2δ−(i) • N¸u xe k quay trở l¤i trung t¥m ph¥n phèi dp th¼ nó ph£i phục vụ chuy¸n ti¸p theo X k;q−1 X k;q xj;dp = xdp;j; 8k 2 K; 8q = 2; 3; : : : ; q(k); 8dp 2 D (2.4) j2δ−(dp) j2δ+(dp) • Thời điểm khởi hành cõa c¡c xe b¬ng thời điểm sớm nh§t b­t đầu phục vụ cõa b¢i đỗ. k;1 sp(k) = e(p(k)); 8k 2 K (2.5) 9
12. B£ng 2.1: C¡c tªp hñp và tham sè K½ hi»u Định nghĩa PK Tªp c¡c b¢i đỗ xe. Với méi b¢i đỗ pk 2 PK: [e(pk); l(pk)]: khung thời gian làm vi»c cõa b¢i pk. P Tªp c¡c s£n ph©m. Méi s£n ph©m p 2 P : w(p): trọng lưñng cõa mët đơn vị s£n ph©m p. D Tªp c¡c trung t¥m ph¥n phèi. Méi trung t¥m dp 2 D: [e(dp); l(dp)]: khung thời gian cõa trung t¥m ph¥n phèi dp. twait(dp): thời gian đợi để có thº truy cªp trung t¥m ph¥n phèi dp. tunit(dp): kho£ng thời gian c¦n thi¸t để t£i mët đơn vị s£n ph©m t¤i trung t¥m dp. C Tªp c¡c kh¡ch hàng. Sè lượng kh¡ch hàng được k½ hi»u bởi η. Với méi kh¡ch hàng c 2 C: [e(c); l(c)]: khung thời gian cõa méi kh¡ch hàng c. twait(c): thời gian đợi để truy cªp điểm kh¡ch hàng c. tunit(c): thời gian c¦n thi¸t để dỡ t£i mët đơn vị s£n ph©m t¤i điểm kh¡ch hàng c. d(c; p): trọng lưñng y¶u c¦u cõa s£n ph©m p cho kh¡ch hàng c. V Tªp t§t c£ c¡c điểm. V = PK [ D [ C K Danh s¡ch c¡c xe. K = f0; 1; 2; : : : ; κ − 1g, với méi xe k 2 K: p(k) 2 P : b¢i đỗ cõa xe k. fk: h» sè ưu ti¶n sû dụng xe k. c(k): giới h¤n dưới cõa t£i trọng xe k. c(k): giới h¤n tr¶n cõa t£i trọng xe k. q(k): sè chuy¸n tèi đa trong ngày cõa xe k. E Tªp c¡c c¤nh (i, j), 8(i; j) 2 (PK × D) [ (D × C) [ (C × C) [ (C × D) [ (C × PK) và i 6= j δ+(i) = fj j (i; j) 2 Eg δ−(i) = fj j (j; i) 2 Eg dmw(i; p) Tham sè đại di»n cho nhu c¦u trọng lượng cõa s£n ph©m p t¤i điểm i, 8i 2 V; 8p 2 P . dmw(i; p) = 0; 8i 2 PK [ D; 8p 2 P . dmw(i; p) = dm(i; p) ∗ w(p); 8i 2 C; 8p 2 P . dr(i) Tham sè đại di»n cho kho£ng thời gian phục vụ t¤i điểm i; 8i 2 V . dr(pk) = 0, 8pk 2 PK. dr(dp) = twait(dp), 8dp 2 D. P dr(i) = twait(i) + p2P dmw(i; p)tunit(i); 8i 2 C. rc(k; c) Giới h¤n truy cªp cõa xe k tới kh¡ch hàng c, 8c 2 C; 8k 2 K. rc(k; c) = 1: xe k có thº truy cªp kh¡ch hàng c rc(k; c) = 0: ngược l¤i. rp(k; p) rp(k; p) = 1: xe k được cho ph²p chở s£n ph©m p, 8k 2 K; 8p 2 P . rp(k; p) = 0: ngược l¤i. vc(k; c) vc(k; c) b¬ng 1 n¸u kh¡ch hàng c là mët kh¡ch hàng được ch¿ định trước cõa k, b¬ng 0 n¸u ngược l¤i, 8k 2 K; 8c 2 C. ti;j thời gian di chuyºn tø điểm i tới điểm j, 8(i; j) 2 E. di;j qu¢ng đường di chuyºn tø điểm i tới điểm j, 8(i; j) 2 E. fb H» sè ph¤t đối với mët y¶u c¦u cõa kh¡ch hàng không được phục vụ. M M là mët h¬ng sè lớn. 10
13. B£ng 2.2: Bi¸n mô h¼nh K½ hi»u Định nghĩa k;q xi;j Mët bi¸n nhị ph¥n b¬ng 1 n¸u xe k di chuyºn tr¶n c¤nh (i, j) trong chuy¸n thù q; b¬ng 0 n¸u ngược l¤i, 8k 2 K, 8(i; j) 2 E, 8q = 1; 2; : : : ; q(k). k;q wp Têng trọng lượng cõa s£n ph©m p vªn chuyºn bởi xe k trong chuy¸n thù q, 8k 2 K, 8q = 1; 2; : : : ; q(k), 8p 2 P . yi Mët bi¸n nhị ph¥n b¬ng 1 n¸u kh¡ch hàng i được phục vụ; b¬ng 0 n¸u ngược l¤i, 8i 2 C. zk;q Mët bi¸n nhị ph¥n b¬ng 1 n¸u xe k thực hi»n chuy¸n thù q; b¬ng 0 n¸u ngược l¤i, 8k 2 K; 8q = 1; 2; : : : ; q(k). k;q si Mët bi¸n để x¡c định thời gian b­t đầu phục vụ t¤i điểm i cõa xe k trong chuy¸n thù q, 8k 2 K; 8q = 1; 2; : : : ; q(k), 8i 2 C. • Ràng buëc thời điểm b­t đầu phục vụ t¤i điểm kh¡ch hàng ngay sau điểm trung t¥m ph¥n phèi tr¶n hành tr¼nh cõa xe k;q k;q X k;q k;q si + ti;j + dr(i) + M(xi;j − 1) + wp tunit(i) ≤ sj ; (2.6) p2P 8k 2 K; 8q = 1; 2; : : : ; q(k); 8(i; j) 2 D × C • Ràng buëc thời điểm b­t đầu phục vụ t¤i c¡c điºm không ph£i trung t¥m ph¥n phèi. k;q k;q k;q si + ti;j + dr(i) + M(xi;j − 1) ≤ sj ; (2.7) 8k 2 K; 8q = 1; 2; : : : ; q(k); 8(i; j) 2 (PK × D) [ (C × C) [ (C × PK); i 6= j • Ràng buëc thời điểm b­t đầu phục vụ t¤i điểm cuèi cùng cõa méi chuyºn k;q−1 k;q k;q−1 k;q si + ti;j + dr(i) + M(z − 1) + M(xi;j − 1) ≤ sj ; (2.8) 8k 2 K; 8q = 2; 3; : : : ; q(k); 8(i; j) 2 C × D • Ràng buëc khung thời gian phục vụ t¤i méi điểm k;q X k;q si + M( xi;j − 1) ≤ l(i); (2.9) j2δ+(i) k;q X k;q si + M(1 − xi;j ) ≥ e(i); (2.10) j2δ+(i) 8k 2 K; 8q = 1; 2; : : : ; q(k); 8i 2 V • Ràng buëc x¡c định têng trọng lượng s£n ph©m được t£i t¤i trung t¥m ph¥n phèi k;q X k;q wp = dmw(i; p)xi;j ; 8k 2 K; 8q = 1; 2; : : : ; q(k); 8p 2 P (2.11) (i;j)2E 11
14. • Ràng buëc đối với t£i trọng cõa xe X k;q k;q wp + M(z − 1) ≤ c(k); (2.12) p2P X k;q k;q wp + M(1 − z ) ≥ c(k); (2.13) p2P 8k 2 K; 8q = 1; 2; : : : ; q(k) • Méi kh¡ch hàng ch¿ được phục vụ 1 l¦n bởi 1 xe q(k) X X X k;q xi;j ≤ 1; 8j 2 C (2.14) k2K q=1 i2δ−(j) • Méi trung t¥m ph¥n phèi được th«m mët l¦n trong méi chuy¸n X X k;q k;q xdp;j = z ; 8k 2 K; 8q = 1; 2; : : : ; q(k) (2.15) dp2D j2C • Méi xe khởi hành t¤i b¢i đỗ nhi·u nh§t mët l¦n. X k;1 k;1 xp(k);dp = z ; 8k 2 K (2.16) dp2D • Méi xe ph£i quay trở l¤i b¢i đỗ nhi·u nh§t mët l¦n q(k) X X k;q k;1 xj;p(k) = z ; 8k 2 K (2.17) q=1 j2C • Ràng buëc quan h» giúa c¡c bi¸n quy¸t định k;q X k;q z ≤ xi;j ; 8k 2 K; 8q = 1; 2; : : : ; q(k); 8(i; j) 2 E (2.18) (i;j) k;q k;q xi;j ≤ z ; 8k 2 K; 8q = 1; 2; : : : ; q(k); 8(i; j) 2 E (2.19) q(k) X X X k;q xi;j = yj; 8j 2 C (2.20) k2K q=1 i2δ−(j) • Ràng buëc thù tự c¡c chuy¸n zk;q+1 ≤ zk;q; 8k 2 K; 8q = 1; 2; : : : ; q(k) − 1 (2.21) • Ràng buëc giới h¤n có thº truy cªp kh¡ch hàng cõa méi xe q(k) X X k;q xj;i ≤ M:rc(k; i); 8k 2 K; 8i 2 V (2.22) q=1 j2δ−(i) 12
15. • Ràng buëc giới h¤n s£n ph©m có thº chở cõa méi xe q(k) X k;q wp ≤ M:rp(k; p); 8k 2 K; 8p 2 P (2.23) q=1 • Ràng buëc ph£i phục vụ c¡c kh¡ch hàng được x¡c định trước cõa méi xe q(k) X X k;q vc(k; i) ≤ xj;i ; 8k 2 K; 8i 2 C (2.24) q=1 j2δ−(i) 2.3 Phương ph¡p 2.3.1 C¡c k½ hi»u dùng cho thuªt to¡n metaheuristic Do độ phùc t¤p t½nh to¡n r§t lớn, tr¼nh tèi ưu hóa GUROBI ch¿ có thº gi£i quy¸t c¡c kịch b£n nhỏ cõa bài to¡n MTDLC-VR. V¼ vªy, mët trong nhúng đóng góp cõa chúng tôi là đề xu§t c¡c thuªt to¡n metaheuristic để xû lý c¡c kịch b£n lớn cõa bài to¡n. Để đơn gi£n hóa vi»c tr¼nh bày c¡c thuªt to¡n được đ· xu§t, chúng tôi đưa ra mët sè ký hi»u được tóm t­t như sau. 2.3.2 Ph¥n t½ch th¡ch thùc cõa ràng buëc mới v· t£i trọng tèi thiºu trong bài to¡n MTDLC-VR 2.3.2.1 Th¡ch thùc đối với c¡c thuªt to¡n x¥y dựng Trong ph¦n này, chúng tôi ph¥n t½ch th¡ch thùc gặp ph£i khi x¥y dựng gi£i ph¡p ban đầu trong trường hñp giới h¤n dưới t£i trọng được coi là mët ràng buëc cùng. 2.3.3 C¡c thuªt to¡n x¥y dựng điều ch¿nh với thõ tục chia chuy¸n Trong ph¦n này, dựa tr¶n c¡c thuªt to¡n x¥y dựng được sû dụng rëng r¢i SA, SW và GIA, chúng tôi đề xu§t ba thuªt to¡n x¥y dựng phù hñp được sû dụng trong giai đo¤n khởi t¤o lời gi£i ban đầu. Dựa tr¶n ý tưởng v· phương ph¡p RF- CS, c¡c thuªt to¡n SA, SW và GIA được tinh ch¿nh cho bài to¡n MTDLC-VR b¬ng c¡ch t¤m thời nới lỏng ràng buëc (2.13). 2.3.4 Mët thuªt to¡n ALNS được c£i ti¸n với thõ tục chia chuy¸n Ph¦n này đ· xu§t thuªt to¡n ALNS được c£i ti¸n (A-ALNS) để xû lý c¡c kịch b£n lớn cõa bài to¡n MTDLC-VR. Thuªt to¡n A-ALNS sû dụng t¡m to¡n tû lo¤i bỏ và t¡m to¡n tû ch±n. Chúng tôi đề xu§t s¡u to¡n tû (R2, R5, I1, I2, I5 và I6) 13
16. và chọn mët sè to¡n tû phù hñp trong c¡c công tr¼nh khoa học theo kinh nghi»m cõa chúng tôi. C¡c to¡n tû th½ch hñp được l§y tø Ropke et al. 2006 và được sûa đổi mët chút để phù hñp với bài to¡n này. To¡n tû ch±n sû dụng quy tr¼nh ph¥n t¡ch để chia mët chuy¸n tham quan khêng lồ thành c¡c chuy¸n đi kh£ thi và đảm b£o c¡c ràng buëc (2.12)-(2.13). Do sự phùc t¤p cõa bài to¡n, có thº không t¼m th§y c£i ti¸n nào sau mët sè l¦n lặp l¤i (cụ thº là sè maxStable). Để tr¡nh bị kẹt trong tèi ưu cục bë, mët trong nhúng ý tưởng ch½nh cõa thuªt to¡n này là t«ng sè lượng kh¡ch hàng bị lo¤i bỏ. Điều đó có nghĩa là thuªt to¡n đề xu§t cè g­ng vượt qua c¡c điºm cao nguy¶n b¬ng c¡ch thực hi»n mët bước nh£y lớn. B¶n c¤nh đó, có thº th§y nguy¶n lý b¡nh xe quay ho¤t động tèt với sè l¦n lặp lớn. Tuy nhi¶n, đối với c¡c phi¶n b£n lớn, thời gian xû lý cõa méi l¦n lặp s³ l¥u hơn do không gian t¼m ki¸m lớn. V¼ vªy, chúng tôi đề xu§t phương ph¡p cªp nhªt trọng sè th½ch ùng để nhanh chóng t¼m to¡n tû tèt, trong đó trọng sè cõa to¡n tû được cªp nhªt sau méi l¦n lặp và li¶n quan đến sự thay đổi gi¡ trị cõa hàm mục ti¶u. 14
17. 1 Mët gi£i ph¡p ban đầu Sinit được t¤o bởi mët thuªt to¡n x¥y dựng c£i ti¸n; 2 Khởi t¤o x¡c su§t cho tøng to¡n tû; 3 Sbest Scur Sinit; 4 Mët sè ng¨u nhi¶n σ 2 [θη; γη] được sinh; 5 it 0; 6 while chưa gặp điều ki»n døng do 7 Mët to¡n tû xóa OR và mët to¡n tû ch±n OI được chọn ng¨u nhi¶n theo x¡c su§t; 8 hR∗;Snewi RmOpApplying(σ; OR;Scur); // xem mục 2.3.4.2 ∗ ∗ 9 R R [R∗; ∗ ∗ 10 hR ;Snewi InsOpApplying(R ;OI ;Snew); // xem mục 2.3.4.3 11 if F (Snew) maxStable then 27 Mët sè ng¨u nhi¶n σ∗ 2 [0; θη] được sinh; 28 σ σ + σ∗; 29 end 30 end 31 Cªp nhªt x¡c xu§t (??); // xem mục 2.3.4.1 32 end Algorithm 1: ALNS(θ; γ; π1; π2; π3) 15
18. 2.3.4.1 Phương ph¡p chọn c¡c to¡n tû 2.3.4.2 C¡c to¡n tû xóa 2.3.4.3 C¡c to¡n tû ch±n 2.4 C¡c th½ nghi»m sè 2.4.1 Kịch b£n và cài đặt Theo nhúng g¼ chúng tôi bi¸t, bài to¡n được mô t£ trong Chương này xem x²t mët sè ràng buëc trong đời thực chưa tøng được nghi¶n cùu trong c¡c công tr¼nh khoa học. Do đó, không có nghi¶n cùu trước đây và bë dú li»u ti¶u chu©n được t¼m th§y để so s¡nh. B¶n c¤nh đó, mët lý do ch½nh là không d¹ để có được c¡c trường hñp ti¶u chu©n phù hñp. V¼ vªy, để đánh gi¡ hi»u qu£ cõa thuªt to¡n và kh£ n«ng ùng dụng trong thực t¸, chúng tôi thû nghi»m tr¶n mët sè tªp dú li»u tø c¡c nguồn kh¡c nhau được mô t£ như sau. 2.4.2 Th½ nghi»m 1: X¡c thực mô h¼nh bài to¡n Mô h¼nh được gi£i b¬ng GUROBI Optimizer. Chúng tôi nhªn th§y r¬ng c¡c gi£i ph¡p mà mô h¼nh cõa chúng tôi t¼m th§y tương đương với gi£i ph¡p tèt nh§t trong bë dú li»u chu©n cõa Solomon đã được b¡o c¡o. Nhúng k¸t qu£ này cho th§y r¬ng mô h¼nh cõa chúng tôi được x¡c thực. B£ng 2.3 cho bi¸t k¸t qu£ cõa mô h¼nh A-ALNS và MILP là gièng nhau. Ngoài ra, c¡c thû nghi»m này cho th§y r¬ng thuªt to¡n được đề xu§t có thº t¼m ra c¡c gi£i ph¡p tèi ưu trong c¡c trường hñp nhỏ r§t nhanh so với GUROBI và GUROBI không thº gi£i quy¸t mô h¼nh MILP cho c¡c kịch b£n có hơn 25 kh¡ch hàng trong váng hai giờ. Lý do ch½nh là mô h¼nh MILP sû dụng nhi·u bi¸n phụ trñ để tuy¸n t½nh hóa c¡c ràng buëc. Do đó, mô h¼nh MILP không thực t¸ đối với c¡c bài to¡n lớn (nó không mở rëng quy mô n¸u sè lượng bi¸n t«ng l¶n), chõ y¸u v¼ lý do thời gian t½nh to¡n. 16
19. B£ng 2.3: Sự so s¡nh giúa k¸t qu£ cõa MILP và A-ALNS. MILP model A-ALNS Ins gr gv gc t gr gv gc t RG-1-2-2-2-6 0 1200 145 0.57 0 1200 145 3.69 RG-2-2-2-2-6 0 1200 118 0.34 0 1200 118 0.89 RG-1-2-2-3-8 0 1800 169 4325.14 0 1800 169 4.12 RG-2-2-2-3-8 0 1800 154 4259.2 0 1800 154 5.08 RG-1-2-4-4-25 0 2400 402 7521.64 0 2400 402 17.03 RG-2-2-4-4-25 0 2400 391 7681.02 0 2400 391 19.89 RG-1-2-4-4-50 0 2400 725 13724.62 0 2400 725 402.12 RG-2-2-4-4-50 0 2400 697 14018.26 0 2400 697 544.1 E21-1-2-4-6-5 0 20610 9982 0.84 0 20610 9982 4.28 E21-2-2-4-6-5 0 20610 9657 1.58 0 20610 9657 4.75 E21-1-2-2-2-25 0 200382 21682 6982.5 0 200382 21682 14.34 E21-2-2-2-2-25 0 197950 20793 7282.02 0 197950 20793 15.21 E21-1-2-2-4-50 0 401256 38017 11021.72 0 401256 38017 388.62 E21-2-2-2-4-50 0 401256 37882 12018.88 0 401256 37882 412.44 E21-1-2-2-4-75 0 426272 58544 67472.13 0 426272 58544 1214.75 E21-2-2-2-4-75 0 426272 58007 75721.47 0 426272 58007 1493.2 2.4.3 Th½ nghi»m 2: So s¡nh hi»u qu£ giúa c¡c thuªt to¡n x¥y dựng c£i ti¸n 2.4.4 Th½ nghi»m 3: Sự hiºu qu£ cõa thuªt to¡n A-ALNS 2.4.4.1 Tinh ch¿nh tham sè 2.4.4.2 Sự hi»u qu£ cõa c¡c to¡n tû ch±n và to¡n tû xóa 2.4.4.3 Sùc m¤nh cõa chi¸n lược A-ALNS Trong ph¦n này, chúng tôi ti¸n hành c¡c thû nghi»m để đánh gi¡ mùc độ m¤nh m³ cõa chi¸n lược A-ALNS. Chúng tôi nhªn th§y r¬ng kho£ng 84,64% đến 99,52% têng sè kh¡ch hàng được phục vụ trong h¦u h¸t c¡c trường hñp với std_gr nhỏ hơn hoặc b¬ng 26,11, ph¤m vi cõa ρ2 là [0; 89; 10; 86]. Chúng tôi th§y r¬ng sự tồn t¤i cõa giới h¤n dung lượng giới h¤n dưới khi¸n c¡c y¶u c¦u có qu¡ ½t trọng lượng và kho£ng thời gian eo hẹp s³ bị tø chèi. K¸t qu£ cũng cho th§y r¬ng trong h¦u h¸t c¡c trường hñp, sè lượng kh¡ch hàng chưa được phục vụ cõa A-ALNS th§p hơn tø 31,48% đến 91,43% so với c¡c thuªt to¡n x¥y dựng. Thuªt to¡n A-ALNS ti¸p tục ho¤t động tèt hơn thuªt to¡n LS. Têng sè kh¡ch hàng chưa phục vụ méi ngày cõa A-ALNS được c£i thi»n đáng kº so với thuªt to¡n LS, với tỷ l» c£i thi»n duy tr¼ cực kỳ ên định tø 10,87% đến 73,33%. Đối với c¡c kịch b£n lớn cõa bài to¡n MTDLC-VR có c¡c ràng buëc phùc t¤p, k¸t qu£ này được gi£i th½ch là do cơ ch¸ c¥n b¬ng giúa t«ng cường và đa d¤ng hóa cõa thuªt to¡n A-ALNS tèt hơn so với thuªt to¡n LS. 17
20. 2.4.5 Th½ nghi»m 4: Ph¥n t½ch nh¤y cõa ràng buëc giới h¤n dưới H¼nh 1.2 tr¼nh bày sè lượng y¶u c¦u vi ph¤m giới h¤n dưới t£i trọng được t¼m th§y bởi bèn thuªt to¡n. Sè lượng y¶u c¦u t«ng nhanh khi giới h¤n dưới cõa sùc chùa cõa xe được t«ng l¶n. Chúng ta th§y r¬ng c¡c đường cong có độ dèc th§p tø c(k) = 10% đến c(k) = 60%. Ngược l¤i, nó t«ng nhanh tø c(k) = 60%. Nó cũng ch¿ ra r¬ng ràng buëc cªn dưới có £nh hưởng lớn đến gi¡ trị hàm mục ti¶u. V¼ vªy, méi nhà qu£n lý ph£i c¥n đối giúa mục ti¶u t«ng tỷ l» l§p đ¦y xe tèi thiºu và t«ng sè lượng kh¡ch hàng được phục vụ tèi đa. Gi¡ trị tỷ l» giúa 40% và 50% được ch§p nhªn. K¸t qu£ cũng cho th§y thuªt to¡n vGIA v¨n tèt hơn so với c¡c thuªt to¡n x¥y dựng kh¡c và thuªt to¡n A-ALNS có sè lượng y¶u c¦u bị vi ph¤m th§p nh§t. H¼nh 1.2: Sè lượng y¶u c¦u bị xóa khỏi gi£i ph¡p khi vi ph¤m ràng buëc cªn dưới t£i trọng. 2.5 Têng k¸t Chương Chương này xem x²t mët bài to¡n lªp lịch tr¼nh tĩnh mới cõa VRP, được gọi là v§n đề định tuy¸n xe đa trung t¥m đa chuy¸n với c¡c ràng buëc v· t£i trọng giới h¤n dưới. Nghi¶n cùu này l§p đầy kho£ng trèng trong c¡c công tr¼nh khoa học v· bài to¡n này b¬ng c¡ch k¸t hñp mët sè ràng buëc trong th¸ giới thực, mët sè ràng buëc đã được xem x²t và mët sè kh¡c chưa được nghi¶n cùu. Bài to¡n xem x²t được mô h¼nh hóa b¬ng mô h¼nh MILP và c¡c th¡ch thùc v· ràng buëc t£i trọng giới h¤n dưới được ph¥n t½ch. K¸t qu£ nghi¶n cùu trong Chương này được công bè trong bài b¡o [1] trong Danh mục c¡c công tr¼nh đ¢ công bè. Đối với c¡c công vi»c trong tương lai, kịch b£n trực tuy¸n cõa bài to¡n MTDLC-VR s³ đưñc điều tra trong đó c¡c y¶u c¦u không được bi¸t trước và được ti¸t lë trực tuy¸n trong qu¡ tr¼nh thực hi»n lịch tr¼nh 18
21. Chương 3 MÆ HÌNH HÂA VÀ GIẢI QUYẾT MËT BIẾN THỂ MÎI CỦA BÀI TOÁN ĐỊNH TUYẾN ĐỘNG 3.1 Giới thi»u Dịch vụ taxi đã thu hút nhi·u sự quan t¥m cõa nhi·u người trong thªp kỷ g¦n đây do sự ti»n lñi, linh ho¤t và chi¸n lược ho¤t động s¡ng t¤o. Công vi»c g¦n nh§t với chúng tôi là Nguyen et al., 2016 đã giới thi»u c¡c kh¡i ni»m và mô h¼nh to¡n học cho SARP động (DSARP) để cung c§p dịch vụ chia s´ taxi. Trong Nguyen et al., 2016, c¡c t¡c gi£ đã nghi¶n cùu mô h¼nh DSARP hoàn toàn phụ thuëc vào thời gian, trong đó hành kh¡ch luôn được giao trực ti¸p mà không bị gi¡n đoạn bởi c¡c điểm đón hoặc điểm tr£ hàng hóa. Trong nghi¶n cùu này, chúng tôi nghi¶n cùu v§n đề định tuy¸n và lªp lịch chia s´ taxi trực tuy¸n (O-TSSP) được mở rëng tø nghi¶n cùu trong Nguyen et al., 2016. Chúng tôi mô h¼nh bài to¡n dưới d¤ng quy ho¤ch ràng buëc và xem x²t v§n đề đề xu§t taxi n¶n đi đâu khi hoàn thành c¡c y¶u c¦u. Chúng tôi đề xu§t mët phương ph¡p học dựa tr¶n dú li»u để học qu¡ tr¼nh đến cõa y¶u c¦u vªn chuyºn và dự đo¡n vị tr½, thời điểm xu§t hi»n y¶u c¦u. Sau đó, chúng tôi ¡p dụng thông tin dự đoán để định tuy¸n với mục ti¶u tèi đa hóa hi»u qu£ di chuyºn têng thº và gi£m thiºu thời gian ch¤y xe trèng cõa người l¡i xe. 3.2 Mô h¼nh taxi chia s´ 3.2.1 Mô t£ bài to¡n H» thèng điều phèi taxi nhªn được mët sè lượng lớn y¶u c¦u vªn chuyºn người và hàng hóa trong giờ làm vi»c cè định. Méi y¶u c¦u bao gồm thông tin v· địa điểm đón, địa điểm tr£ kh¡ch và kho£ng thời gian hñp l» tương ùng với hai địa điểm này. Trong kịch b£n động, h» thèng định tuy¸n c¦n theo dãi li¶n tục tr¤ng th¡i và lë tr¼nh cõa taxi. Khi t§t c£ c¡c y¶u c¦u được thực hi»n, xe taxi c¦n được khuy¸n nghị đến mët nơi đậu xe b¬ng cung đường có kh£ n«ng cao nh§t đón được y¶u c¦u mới. H¼nh 4.1 tr¼nh bày mët v½ dụ v· c¡c tuy¸n đường cho taxi không t£i, trong đó có ba cung đường ùng vi¶n được minh họa b¬ng c¡c đường ch§m mà người l¡i xe có thº đi đến điểm đỗ tø điểm tr£ kh¡ch cuèi cùng. 19
22. H¼nh 4.1: Mët v½ dụ v· c¡c cung đường tø điểm phục vụ cuèi cùng v· b¢i đỗ. 3.2.2 Mô h¼nh to¡n học 3.3 Thuªt to¡n đi·u phèi taxi dựa tr¶n thông tin dự đoán 3.3.1 Dự đoán nhu c¦u taxi Trong ph¦n này, chúng tôi đề xu§t mët thuªt to¡n để dự đoán sè lượng, vị tr½ và thời điểm cõa y¶u c¦u mới trong tương lai. Chúng tôi ph¥n t½ch t¦n su§t xu§t hi»n y¶u c¦u dựa tr¶n c¡c dú li»u y¶u c¦u được thu thªp theo thời gian và không gian trong qu¡ khù. Y¶u c¦u taxi có thº được xem như điểm dú li»u trong không-thời gian và được coi là mët sự ki»n. Chúng tôi gi£ sû c¡c sự ki»n này có c¡c thuëc t½nh sau: 1) T¦n su§t xu§t hi»n cõa mët sự ki»n có thº nhªn mët gi¡ trị nguy¶n không ¥m trong mët kho£ng thời gian; 2) C¡c sự ki»n x£y ra độc lªp; 3) Sự xu§t hi»n cõa mët sự ki»n độc lªp với sự ki»n trước đó; 4) Tỷ l» xu§t hi»n trung b¼nh cõa mët sự ki»n không phụ thuëc vào b§t kỳ sự ki»n nào. Với nhúng điều ki»n này, quy tr¼nh Poisson không đồng nh§t (NHPP), được sû dụng rëng r¢i cho c¡c quy tr¼nh đếm, hoàn toàn th½ch hñp đº lªp mô h¼nh bi¸n đếm cõa c¡c y¶u c¦u taxi (Ruda et al. 2020). Cho mët kho£ng thời gian T = [ts; te] ⊂ T (ch½nh x¡c tới 1 gi¥y) và mët không gian phụ thuëc D(t) 2 R2. Qu¡ tr¼nh đến cõa sự ki»n là mët qu¡ tr¼nh ng¨u nhi¶n phụ thuëc hàm λa(t), trong đó a đại di»n cho mët điểm trong D(t) and t 2 T là mët thời điểm. Nó được sû dụng để học ph¥n phèi cõa c¡c y¶u c¦u taxi và sau đó dùng để t¤o ra c¡c y¶u c¦u taxi t¤i thời điểm t và điểm a. 3.3.2 Thuªt to¡n điều phèi trực tuy¸n Trong Thuªt to¡n 2, dáng 1 x¡c định sự k¸t hñp cõa tªp hñp PP . Dáng 2 nhªn được mët tªp hñp c¡c y¶u c¦u mới Rcur. Thông tin v· taxi, ch¯ng h¤n như tr¤ng th¡i và vị tr½, được cªp nhªt t¤i dáng 5. Đối với méi y¶u c¦u mới r 2 Rcur, 20
23. mët taxi th½ch hñp k và vị tr½ j tèt nh§t tr¶n lë tr¼nh được t¼m bởi dáng 7. Với vị tr½ đón và tr£ kh¡ch li¶n quan đến vi»c thực hi»n y¶u c¦u, lịch tr¼nh cũng như c¡c tuy¸n đường cõa taxi được điều ch¿nh để hoàn thành nhi»m vụ mët c¡ch tèi ưu (dáng 9 và 10) b¬ng c¡ch ¡p dụng mët sè to¡n tû l¡ng gi·ng. Cuèi cùng, cung đường tø điểm tr£ kh¡ch cuèi cùng đến điểm đỗ tèt nh§t được đề xu§t bởi dáng 11. Thuªt to¡n được lặp l¤i cho đến khi k¸t thúc thời gian làm vi»c. α 1 PP fPf gf=1; 2 Rcur UnscheduledRequests(tcur); 3 tcur ts + ∆T ; 4 while tcur < te do 5 Update information of taxis for request r 2 Rcur do 6 hk; ji ; 7 FindAppropriateTaxi(r; tcur); 8 if hk; ji= 6 ? then 9 RequestInsertion(r; k; j; PP); 10 ImprovementOperator(); 11 DirectionToParkingPoint(k); 12 end 13 end 14 Rcur UnscheduledRequests(tcur); 15 tcur tcur + ∆T ; 16 end Algorithm 2: Thuªt to¡n điều phèi taxi trong kịch b£n động (OTSF-DP) 3.3.3 Th½ nghi»m 3.3.3.1 Mô t£ dú li»u Trong Chương này, c¡c kịch b£n đưñc thu thªp tr¶n cơ sở dú li»u Cabspotting ( ghi l¤i c¡c lë tr¼nh cõa taxi ở San Francisco. Chúng tôi sû dụng dú li»u tø 07-2005 đến 07-2006 để hu§n luy»n mô h¼nh dự đo¡n. 3.3.3.2 Thi¸t k¸ th½ nghi»m Đầu ti¶n, chúng tôi triºn khai thuªt to¡n OTSF đº hướng mët chi¸c taxi đến vị tr½ đỗ xe g¦n nh§t khi nó không có người và OTSF-DP để chuyºn hướng đến vị tr½ đỗ xe tèt nh§t với vi»c sû dụng điểm sè. Ti¸p theo, chúng tôi đánh gi¡ c¡c thuªt to¡n được đề xu§t so với thuªt to¡n chia s´ mët chuy¸n đi động hi»n có DSARP được đ· xu§t bởi Li et al., 2014 và bi¸n thº DSARP-DP cõa nó với vi»c mở rëng thông tin dự đoán v· c¡c y¶u c¦u mới và vị tr½ đỗ xe. 3.3.3.3 K¸t qu£ thực nghi»m Trường hñp 1: C¡c y¶u c¦u vªn chuyºn hàng có khung thời gian chặt K¸t qu£ ch¿ ra r¬ng trong h¦u h¸t c¡c kịch b£n, c¡c thuªt to¡n sû dụng thông tin dự đoán trong định tuy¸n mang l¤i lñi nhuªn tèt hơn c¡c thuªt to¡n không 21
24. có b§t kỳ thông tin dự đoán nào. OTSF-DP có thº ti¸t ki»m tø 2520 USD đ¸n 5730 USD têng lñi nhuªn méi ngày so với OTSF. Hơn núa, work in Li et al., 2014 gi£ sû r¬ng c¡c y¶u c¦u bưu ki»n đã được bi¸t trước, tuy nhi¶n, sè lượng y¶u c¦u được phục vụ trong DSARP và DSARP-DP là ½t hơn OTSF và OTSF-DP trong h¦u h¸t c¡c kịch b£n. Trường hñp 2: C¡c y¶u c¦u vªn chuyºn hàng có khung thời gian rëng B£ng 4.5 tr¼nh bày tỷ l» y¶u c¦u được phục vụ và lñi nhuªn thu được tø méi thuªt to¡n. Thuªt to¡n OTSF-DP v¨n vượt trëi hơn c¡c thuªt to¡n kh¡c. Mặc dù kho£ng thời gian rëng là lñi th¸ lớn đối với DSARP và DSARP-DP, lñi nhuªn thu được tø c¡c thuªt to¡n này v¨n ½t hơn so với c¡c thuªt to¡n OTSF và OTSF-DP. Ảnh hưởng cõa c¡c phương ph¡p học qu¡ tr¼nh đến cõa y¶u c¦u vªn chuyºn tới ch§t lượng gi£i ph¡p định tuy¸n Trong thû nghi»m này, chúng tôi đánh gi¡ lñi ½ch cõa vi»c sû dụng c¡c phương ph¡p đã học kh¡c nhau. B£ng 4.5 tr¼nh bày lñi nhuªn cõa c¡c thuªt to¡n lªp lịch với c¡c k¸t qu£ dự đoán bởi c¡c thuªt to¡n dự đoán kh¡c nhau. Chúng tôi biºu thị thuªt to¡n OTSF-DP b¬ng c¡ch sû dụng phương ph¡p học chia bin có độ dài b¬ng nhau bởi p1 và OTSF-DP b¬ng c¡ch sû dụng khung học tªp với phương ph¡p chia bin th½ch ùng là p2. Ph¦n tr«m c£i ti¸n được biºu thị b¬ng ρ = (p2 −p1)100=p1. Chúng tôi nhªn th§y r¬ng lñi nhuªn cõa vi»c sû dụng phương ph¡p học tªp têng qu¡t hóa tèt hơn lñi nhuªn thu được khi sû dụng phương ph¡p chia bin với độ dài b¬ng nhau ở t§t c£ ch½n ngày thực nghi»m. Ph¦n tr«m c£i thi»n là tø 3,61 % đến 9,21 % trong kịch b£n đầu ti¶n. Tỷ l» c£i thi»n trong kịch b£n 1 lớn hơn tỷ l» trong kịch b£n 2. Điều này có thº được gi£i th½ch bởi sè lượng y¶u c¦u ½t hơn và kho£ng thời gian rëng hơn cõa c¡c y¶u c¦u bưu ki»n B£ng 4.4: K¸t qu£ điều phèi cõa 4 thuªt to¡n trong trường hñp 1. OTSF OTSF-DP DSARP DSARP-DP Ins #Reqs1 PCT2 Profit3 PCT2 Profit3 PCT2 Profit3 PCT2 Profit3 D1 12334 99.71 71.22 99.91 74.97 97.79 38.37 100 39.4 D2 11536 99.74 63.24 100 67.09 97.68 32.6 99.99 33.92 D3 13292 99.14 72.88 99.98 78.61 97.87 40.2 99.47 40.93 D4 13346 99.65 74.03 99.94 78.89 97.64 59.77 99.90 59.77 D5 14420 99.62 80.16 99.91 85 97.68 45.9 99.66 46.25 D6 16458 99.73 90.54 99.81 94.36 97.95 52.06 99.58 54.22 D7 16476 99.92 89.65 99.90 92.47 97.91 50.7 99.55 52.87 D8 10332 99.97 60.5 99.98 63.5 99.96 29.66 99.96 31.92 D9 8294 99.92 46.79 99.93 49.31 99.95 21.73 99.95 24.3 (1) Têng sè y¶u c¦u được phục vụ. (2) Ph¦n tr«m sè y¶u c¦u được phục vụ. (3) Lñi nhuªn thu được (Profit × 1000 USD). 22
25. trong kịch b£n 2. Mặc dù tỷ l» c£i thi»n không cao trong hai kịch b£n nhưng k¸t qu£ đã chùng minh kh£ n«ng ùng dụng cõa c¡c thuªt to¡n đưñc đề xu§t và có thº được c£i thi»n b¬ng c¡ch ¡p dụng mët sè kỹ thuªt hi»n đại trong học m¡y. B£ng 4.5: Lñi nhuªn cõa thuªt to¡n điều phèi sû dụng thông tin học tø c¡c phương ph¡p đề xu§t. OTSF-DP (Kịch b£n 1) OTSF-DP (Kịch b£n 2) Ins p1 p2 ρ(%) p1 p2 ρ(%) D1 74.97 79.12 5.54 27.92 29.14 4.37 D2 67.09 70.37 4.89 30.89 32.11 3.95 D3 78.61 85.02 8.15 32.67 33.98 4.1 D4 78.89 81.74 3.61 29.62 31.03 4.76 D5 85 90.21 6.13 29.8 31.61 6.07 D6 94.36 101.68 7.76 29.24 30.15 3.11 D7 92.47 98.62 6.65 29.62 31.17 5.23 D8 63.5 66.2 4.25 28.56 29.72 4.06 D9 49.31 53.85 9.21 10.16 10.85 6.79 3.4 Têng k¸t chương Trong Chương này, chúng tôi đ¢ gi£i quy¸t v§n đề định tuy¸n taxi chia s´ lë tr¼nh người và hàng hóa. Chúng tôi đã đề xu§t thuªt to¡n OTSF-DP cho v§n đề định tuy¸n trực tuy¸n. Chúng tôi khuy¸n nghị người l¡i xe đi theo tuy¸n đường với kh£ n«ng cao nhªn được y¶u c¦u mới tr¶n tuy¸n đường đến vị tr½ đỗ xe được ch¿ định b¬ng c¡ch sû dụng thông tin dự đoán. K¸t qu£ nghi¶n cùu trong Chương này đã được công bè t¤i [2, 3, 4] trong Danh mục c¡c công tr¼nh công bè. B£ng 4.5: The routing results of four algorithms in the second scenario. OTSF OTSF-DP DSARP DSARP-DP Ins #Reqs PCT Profit PCT Profit PCT Profit PCT Profit D1 3718 99.62 26.31 99.68 27.92 94.67 18.31 98.51 18.45 D2 4227 99.67 29.41 100 30.89 93.21 18.92 93.21 21.99 D3 4385 97.86 30.15 98.52 32.67 92.22 17.33 98.56 22.79 D4 4117 99.85 27.95 100 29.62 93.98 18.31 98.18 21.09 D5 4351 99.95 28.22 99.98 29.8 92.67 18.44 98.51 21.5 D6 4606 99.78 26.91 99.91 29.24 88.02 15 99 20.14 D7 4797 99.79 28 99.83 29.62 90.08 15.5 98.83 20.23 D8 3651 99.97 27.01 99.81 28.56 98.22 18 98.63 20.79 D9 1194 99.08 7.01 98.91 10.16 76.05 5.16 87.37 6 23
26. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN K¸t luªn Luªn ¡n này đã tr¼nh bày nhúng đóng góp đối với c¡c bài to¡n VRP. Ba đóng góp ch½nh được tr¼nh bày trong ba chương và được tóm t­t như sau: Đầu ti¶n là thi¸t k¸ mët mô h¼nh vªn chuyºn hàng hóa mới, đại di»n cho lớp bài to¡n VRP tĩnh. Đó là mët h¼nh thùc vªn chuyºn s£n ph©m súa thực t¸, trong đó c¡c phương ti»n ph£i vªn chuyºn c¡c đơn vị s£n ph©m súa tø nhi·u trung t¥m ph¥n phèi đến kh¡ch hàng và vªn hành nhi·u chuy¸n và têng trọng lượng s£n ph©m vªn chuyºn trong méi chuy¸n ph£i n¬m trong mët ph¤m vi nh§t định tùy thuëc vào sùc t£i cõa phương ti»n vªn hành. Chúng tôi đã đề xu§t mët mô h¼nh lªp tr¼nh tuy¸n t½nh hén hñp sè nguy¶n và thuªt to¡n ALNS được điều ch¿nh để gi£i quy¸t v§n đề được xem x²t trong c¡c trường hñp lớn. Mô h¼nh được đề xu§t kh¡c đại di»n cho mô h¼nh vªn t£i hành kh¡ch trong đó hành kh¡ch và bưu ki»n có thº đi chung mët chuy¸n và h» thèng định tuy¸n c¦n đề xu§t tuy¸n đường tèt nh§t cho người l¡i xe taxi không t£i để cơ hëi nhªn được nhu c¦u vªn chuyºn mới cao khi taxi r£nh réi. Mët thuªt to¡n dự đoán mới để định tuy¸n taxi và khai th¡c c¡c y¶u c¦u dự đoán trong tương lai trong kịch b£n động được đề xu§t. Cuèi cùng, luªn ¡n này đề xu§t mët phương ph¡p học thèng k¶ để học qu¡ tr¼nh NHPP nh¬m dự đoán c¡c y¶u c¦u VRP giúp gi£m thiºu qu¢ng đường không t£i cõa xe. K¸t qu£ thû nghi»m cho th§y têng qu¢ng đường di chuyºn không t£i cõa c¡c thuªt to¡n cõa chúng tôi ½t hơn so với phương thùc chia s´ chuy¸n đi hi»n có. Hướng ph¡t triºn Luªn ¡n đã thu được mët sè k¸t qu£ đáng kº. Tuy nhi¶n, v¨n có nhúng điểm c¦n c£i thi»n. Trong c¡c công tr¼nh ti¸p theo, c¡c hướng nghi¶n cùu sau đây s³ được kh¡m ph¡: Nghi¶n cùu c¡c thuªt to¡n metaheuristics kh¡c để so s¡nh với c¡c thuªt to¡n đã đề xu§t với mục ti¶u c£i thi»n ch§t lượng gi£i ph¡p hi»n t¤i. Đề xu§t c¡c bi¸n thº mới, ràng buëc mới để c¡c bài to¡n VRP trở n¶n linh hoạt/thực t¸ hơn với môi trường ng¨u nhi¶n. Mët sè kỹ thuªt thèng k¶ để ph¥n t½ch c¡c trường hñp sè chi·u lớn hơn và sự £nh hưởng cõa phương ph¡p binning đối với c¡c trường hñp không gian-thời gian cũng s³ được nghi¶n cùu. 24
27. DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 1. Van Son NGUYEN, Quang Dung PHAM, Thanh Hoang NGUYEN, Quoc Trung BUI (2022), Modelling and Solving a Real-world Multi-trip Multi distribution center Vehicle Routing Problem with Lower-bound Capacity, Computers and Industrial Engineering, vol.172 (A), 108597. Doi: 10.1016/j.cie.2022.108597 (IF: 7.18) 2. Van Son NGUYEN, Babaki Behrouz, Dries Anton, Quang Dung PHAM, Xuan Hoai NGUYEN (2017), Prediction-based optimization for online People and Parcels share a ride taxis, 9th International Conference on Knowledge and Systems Engineering (KSE), pp. 42-47 (Best paper award) 3. Van Son NGUYEN, Quang Dung PHAM, Van Hieu NGUYEN (2021), Exploiting Demand Prediction to Reduce Idling Travel Distance for Online Taxi Scheduling Problem,s In Proceedings of MCO 2021, Volume 363 of Lecture Notes in Networks and Systems, pages 51-62 (Scopus Indexed) 4. Van Son NGUYEN, Thi Hong Nhan VU, Quang Dung PHAM, Xuan Hoai NGUYEN, BehrouZ BABAKI, Dries ANTON (2022), Novel Online Routing Algorithms for Smart People-Parcel Taxi Sharing Services, ETRI journal, 44(2), pp. 220-231 (IF: 1.622) 5. Van Son NGUYEN, Quang Dung PHAM, Quoc Trung BUI, Thanh Hoang NGUYEN (2017), Solving Min-Max Capacitated Vehicle Routing Problem by Local Search. Journal of Computer Science and Cybernetics, 33(1). doi:10.15625/1813-9663/33/1/8846 6. Van Son NGUYEN, Quang Dung PHAM, Anh Tu PHAN (2019), An Adaptive Large Neighborhood Search Solving Large People and Parcel Share-a-Ride Problem, 6th NAFOSTED Conference on Information and Computer Science, pp. 303-308, doi: 10.1109/NICS48868.2019.9023893 7. Van Son NGUYEN, Quang Dung PHAM (2019), A New Variant of Truck Scheduling for Transporting Container Problem, Proceedings of the Tenth International Symposium on Information and Communication Technology – SoICT, pages 139-146 8. Van Son NGUYEN, Quang Dung PHAM (2022), Solving a new variant of truck scheduling for transporting container problem by local search, Journal of Science and Technology Technical Universities, vol. 32(2), pp.64-73