Luận án thạc sĩ: Bài toán thuê xe du lịch có hạn ngạch - ĐH Quốc gia Hà Nội

ĐẠI HOC QUOC GIA HÀ N I TRƯ NG ĐẠI HOC CÔNG NGHS HÀ N I Đinh Thị Thúy BÀI TOÁN THUÊ XE DU L±CH CÓ HẠN NGẠCH Ngành: Công ngh thông tin Chuyên ngành: Khoa hoc máy tính Mã so: 64080101 LU🄐N VĂN THẠC SĨ CÔNG NGHS THÔNG TIN Người hướng dȁn khoa hoc: PGS.Hoàng Xuân Huan Hà N i - 2018 L I CAM ĐOAN Tôi xin cam đoan rang đây là công trình nghiên c u cǔa cá nhân tôi dưới sụ hướng dȁn giúp đỡ cǔa PGS. Hoàng Xuân Huan. Các ket quǎ được viet chung với các tác giǎ khác đeu được sụ đong ý cǔa tác giǎ trước khi đưa vào lu n văn. Trong toàn b n i dung nghiên c u cǔa lu n văn, các van đe được trình bày đeu là nh ng tìm hieu và nghiên c u cǔa chính cá nhân tôi ho c là được trích dȁn t các nguon tài li u có ghi tham khǎo rõ ràng, hợp pháp.

Trong lu n văn, tôi có tham khǎo đen m t so tài li u cǔa m t so tác giǎ được li t kê tại mục tài li u tham khǎo. năm 2018 Hoc viên Đinh Thị Thúy L I CÁM ƠN Trước khi trình bày n i dung chính cǔa khóa lu n, em xin bày tǒ lòng biet ơn sâu sac tới PGS.Hoàng Xuân Huan người đã t n tình hướng dȁn đe em có the hoàn thành khóa lu n này. Em cũng xin bày tǒ lòng biet ơn chân thành tới toàn the các thay cô giáo trong khoa Công ngh thông tin, Đại hoc Công Ngh , Đại Hoc Quoc Gia Hà N i đã dạy bǎo em t n tình trong suot quá trình hoc t p. Nhân dịp này em cũng xin được g i lời cǎm ơn chân thành t ới gia đình, b ạn bè đã luôn bên em, cő vũ, đ ng viên, giúp đỡ em trong suot quá trình hoc t p và thục hi n lu n văn tot nghi p.

năm 2018 Hoc viên Đinh Thị Thúy 2 DANH MỤC KÍ HISU VÀ CHŨ VIET TAT ACO Phương pháp toi ưu hóa đàn kien(Ant Colony Optimisation). AS H kien AS(Ant System). ACS H kien ACS(Ant Colony System). MMAS H kien MMAS(Max-Min Ant System).

SMMAS H kien MMAS trơn(Smooth-Max Min Ant System). CaRS Bài toán thuê xe du lịch(Traveling car renter problem). GA Thu t giǎi di truyen(Genetic Algorithm ). QTSP Quota Traveling Salesman Problem.

q-CaRS Bài toán thuê xe du lịch có hạn ngạch(Quota traveling car renter problem) TSP Bài toán người chào hàng(Traveling Salesman Problem). || So phan t trong m t t p. Mục lục Danh mục kí hi u và ch viet tat. Bài toán thuê xe du lịch có hạn ngạch.

Quy hoạch nguyên. Dạng tőng quát cǔa bài toán. Úng dụng cǔa bài toán. Các phương pháp tiep c n giǎi bài toán quy hoạch nguyên.

Bài toán ngưài chào hàng(Traveling Salesman Problem - TSP). Bài toán thuê xe du lịch có hạn ngạch(q-CaRS). Bài toán người bán hàng có hạn ngạch(QTSP). Các bài toán liên quan.

Bài toán thuê xe du lịch có hạn ngạch(q-CaRS). Các phương pháp metaheuristic. Thu t giái di truyen. Thu t toán di truyen cő đien.

Bieu dien bang véc tơ so thục. GA trong toi ưu tő hợp. Phương pháp toi ưu hóa đàn kien. Cách tìm đường đi cǔa kien tụ nhiên.

Kien nhân tạo. Phương pháp ACO tőng quát. Thu t giái di truyen cho bài toán q-CaRS. Bieu dien quan the.

Quá trình tái tạo. Thú tục tìm kiem địa phương. Thu t toán MemPlas. Ket quá thục nghi m.

Tien hành chạy thục nghi m. Ket quǎ thục nghi m. Thu t toán ACO giái bài toán q-CaRS. Đo thị cau trúc.

Vet mùi và thông tin heuristic. Quy tac c p nh t mùi. Thú tục tìm kiem cục b. Ket quá thục nghi m.

Ket quá thục nghi m và đánh giá.53 5 L I M ĐAU Trong nh ng năm gan đây, đi cùng với sụ bùng nő m ạnh mẽ c ǔa công ngh thông tin và du lịch, các dịch vụ ti n ích ph ục v ụ cho khách du l ịch v ới các ng dụng di đ ng cũng được phát trien mạnh mẽ. Nhu cau tìm kiem các ke ho ạch cho chuyen đi với chi phí phù hợp và thu n lợi là m t trong nh ng nhu cau phő bien. Cụ the, trong m t tour du lịch tham quan các địa điem c ǔa thành pho, t ại mői địa điem đeu có nh ng sȁn nh ng chiec xe du lịch v ới giá thành c ụ the. Vì lý do tài chính cũng như thời gian hành khách có the sẽ không đi tham quan được het các địa điem nhưng ho luôn mong muon sẽ có m t chuyen đi hài lòng nhat với chi phí nhǒ nhat.

Đây bài toán thu c van đe toi ưu tő hợp, thu c lớp bài toán NP-khó và là bài toán bien the cǔa bài toán người bán hàng du lịch(TSP) và bài toán thuê xe du lịch(CaRS). Đã có rat nhieu các nghiên c u đưa ra cho bài toán này như : “Các phương pháp toi ưu cho bài toán người bán hàng du lịch trục tuyen”[46] , “Bǎo đǎm xap xǐ cho bài toán người bán hàng có trong so”[6] , “Thu t toán Memetic cho bài toán thuê xe du lịch”[20]. Tuy nhiên các nghiên c u này không xét đen chi phí di chuyen mà mới chǐ xét đen thời gian di chuyen thành công gi a các địa điem. Van đe được đ t ra trong nghiên c u này đó là s ụ tőng quát hóa c ǔa thu t toán QTSP với m t t p hợp các xe ô tô đe ng ười bán hàng có the thuê đe di chuyen.

QTSP là m t bien the cǔa TSP với mői đǐnh đeu có rang bu c nhat đ ịnh và mục tiêu là toi thieu hóa chi phí di chuyen với yêu cau rang bu c không nh ǒ h ơn giá trị định sȁn. Trong nghiên c u “Thu t toán Memetic cho bài toán thuê xe du lịch”[20] đã đưa ra nh ng ket quǎ được đánh giá khá cao, tuy nhiên trong nghiên c u không có ràng bu c nào đoi với các địa điem đen thăm. Bài toán q-CaRS là bài toán toi ưu tő hợp có nhieu ràng bu c , thu c lớp bài toán NP khó, chǐ có the tìm lời giǎi gan đúng trong thời gian đa th c. Trong nghiên c u [21] tác giǎ đã đưa ra thu t giǎi di truyen đe giǎi bài toán và ket quǎ thu được là khá tot.

Tuy nhiên trong thời gian gan đây, phương pháp toi ưu hóa đàn kien giǎi bài toán toi ưu tő hợp đang được női lên với nh ng thục nghi m được đánh giá khá cao đ c bi t là thành công trong bài toán người bán hàng v ới so đǐnh lên đen 2000. Vì v y lu n văn đe xuat thêm phương pháp tői ưu hóa đàn kien giǎi bài toán q-CaRS trên. Ket quǎ thục nghi m cho thay phương pháp toi ưu hóa đàn kien cho ket quǎ trong nhieu hợp tot hơn thu t giǎi GA ve cǎ chat lượng và thời gian. Trong phương pháp toi ưu hóa đàn kien, lu n văn s dụng quy tac c p nh t mùi Max- min trơn trong nghiên c u cǔa tác giǎ Đő Đ c Đông và các c ng sụ [2].

Lu n văn trình bày ve bài toán thuê xe có hạn ngach q-CaRS, sau đó là gi ới thi u 6 chung ve hai phương pháp metaheuristic là thu t giǎi di truyen và phương pháp 7 toi ưu hóa đàn kien giǎi bài toán toán toi ưu tő h ợp. Tiep theo lu n văn trình bày cụ the ve hai phương pháp trên giǎi bài toán q-CaRS và chương trình thục nghi m. Bo cục cǔa lu n văn bao gom 4 chương: • Chương 1: Bài toán thuê xe có hạn ngạch. • Chương 2: Các phương pháp metaheuristic.

• Chương 3: Thu t toán di truyen giǎi bài toán q-CaRS. • Chương 4: Thu t toán ACO giǎi bài toán q-CaRS. • Phụ lục trình bày m t so module cơ bǎn trong l p trình thu t toán. Do thời gian thục hi n lu n văn không nhieu, kien th c còn hạn che nên khi làm lu n văn không tránh khǒi nh ng hạn che và sai sót.

Tác giǎ mong nh n được sụ góp ý và nh ng ý kien phǎn bi n cǔa quý thay cô và bạn đoc. Xin chân thành cǎm ơn! Hà N i, ngày. năm 2018 Hoc viên Đinh Thị Thúy 8 Chương 1 Bài toán thuê xe du lịch có hạn ngạch 1. Quy hoạch nguyên Quy hoạch nguyên (Integer Programming) , viet tat là IP, là bài toán quy hoạch mà trong đó tat cǎ ho c m t phan các bien bị ràng bu c chǐ lay giá trị nguyên.

Trường hợp th nhat được goi là quy hoạch nguyên hoàn toàn (Pure Integer Pro- gramming – PIP), trường hợp th hai được goi là quy hoạch nguyên b ph n (Mixed Integer Programming – MIP) 1. Dạng tong quát cúa bài toán Bài toán quy hoạch nguyên tőng quát được bieu dien dưới dạng: f (x) = c T x → min(max) với các đieu ki n: Ax ≤ bx ≥ 0 x ∈ Zn Bài toán quy hoạch nguyên được goi là hoàn toàn khi tat cǎ các bien đeu là so nguyên và được goi là b ph n khi m t so bien không phǎi là so nguyên. Bài toán quy hoạch nguyên 0-1 là bài toán khi các bien được giới hạn là 0 ho c 1. Úng dụng cúa bài toán Úng dụng cǔa bài toán được phát trien dụa vào các bien the là bài toán quy hoạch nguyên hőn hợp và bài toán quy hoạch nguyên 0-1.

9 L p ke hoạch sán xuat Quy hoạch nguyên hőn hợp có nhieu ng dụng trong sǎn xuat công nghi p, bao gom mô hình hóa vi c làm. M t ví dụ quan trong xǎy ra trong quy hoạch sǎn xuat nông nghi p bao gom xác định năng suat sǎn xuat cho m t so loại cây trong có the chia sě tài nguyên (ví dụ như đat đai, lao đ ng, von, h ạt giong, phân bón. M t mục tiêu có the là toi đa hóa tőng sǎn lượng mà không v ượt quá các nguon lục sȁn có. Trong m t so trường hợp, đieu này có the được bieu dien dưới d ạng m t chương trình tuyen tính, nhưng các bien phǎi được hạn che là so nguyên.

Bài toán l p lịch Bài toán này liên quan đen dịch vụ và l p lịch trình xe trong m ạng l ưới v n t ǎi. Ví dụ, bài toán liên quan đen vi c chǐ định xe buýt ho c tàu đi n ngam vào các tuyen đường riêng đe có the đáp ng được thời gian bieu, và cũng đe trang bị cho ho các trình đieu khien.