zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Kỹ Thuật - Công Nghệ

» Tự động hoá

Tổng quan một số dạng của bài toán lập lộ trình xe và giải thuật metaheuristic iterated local search có cải tiến để giải quyết một số dạng của bài toán lập lộ trình xe

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:12

Báo xấu

14
lượt xem 5
download

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

Bài báo này đề cập đến các cách tiếp cận chính xác và metaheuristic để giải quyết các dạng khác nhau của VRP, và đã thực hiện một rà soát thống kê rộng rãi. Giải thuật được trình bày trong bài báo được dựa trên giải thuật metaheuristic Iterated Local Search (ILS) với việc sử dụng một thủ tục giảm lân cận giá trị theo thứ tự lân cận ngẫu nhiên (Variable Neighborhood Descent with Random neighborhood ordering (RVND)), trong đoạn tìm kiếm địa phương.

Chủ đề:

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

Lưu

Nội dung Text: Tổng quan một số dạng của bài toán lập lộ trình xe và giải thuật metaheuristic iterated local search có cải tiến để giải quyết một số dạng của bài toán lập lộ trình xe

NGHIÊN CỨU - TRAO ĐỔI TỔNG QUAN MỘT SỐ DẠNG CỦA BÀI TOÁN LẬP LỘ TRÌNH XE VÀ GIẢI THUẬT METAHEURISTIC ITERATED LOCAL SEARCH CÓ CẢI TIẾN ĐỂ GIẢI QUYẾT MỘT SỐ DẠNG CỦA BÀI TOÁN LẬP LỘ TRÌNH XE  ThS. NGUYỄN MINH ĐẾ (*) TÓM TẮT Bài toán lập lộ trình xe (Vehicle Routing Problem (VRP)) là dạng bài toán tối ưu rời rạc và được giới thiệu lần đầu tiên trong cuối những năm 1950. Các giải pháp chính xác cho VRP thường tạo nên bùng nổ tổ hợp tính toán phức tạp. Vì tính hiệu quả nên các giải pháp phải dựa vào các phương pháp xấp xỉ và heuristic đã hoạt động tốt trong thực tế. Các nhà nghiên cứu vẫn tiếp tục nỗ lực để thiết kế ra các giải thuật xấp xỉ mà có tỉ lệ tốt hơn các giải thuật xấp xỉ đã có. Bài báo này đề cập đến các cách tiếp cận chính xác và metaheuristic để giải quyết các dạng khác nhau của VRP, và đã thực hiện một rà soát thống kê rộng rãi. Giải thuật được trình bày trong bài báo được dựa trên giải thuật metaheuristic Iterated Local Search (ILS) với việc sử dụng một thủ tục giảm lân cận giá trị theo thứ tự lân cận ngẫu nhiên (Variable Neighborhood Descent with Random neighborhood ordering (RVND)), trong đoạn tìm kiếm địa phương. Từ khóa: lập lộ trình xe, tối ưu tổ hợp, tìm theo vùng lặp lại, giảm lân cận giá trị theo thứ tự lân cận ngẫu nhiên. SUMMARY The Vehicle Routing Problem (VRP) is a discrete optimization problem, and first introduced in the late 1950's. Exact solutions of VRPs are often computationally intensive. For the sake of efficiency, one must resort to approximation methods and heuristics which work well in practice. Researchers are continuously applying their best efforts to design new approximation algorithms which have better approximation ratio as compared to the previously existing algorithms. This paper mentions about exact and metaheuristic approaches for solving different variants of the VRP, and make a survey of extensive literature reviewing. The proposed algorithm is based on the Iterated Local Search (ILS) metaheuristic which uses a Variable Neighborhood Descent procedure, with a Random Neighborhood Ordering (RVND), in the local search phase. Key words: Vehicle routing problem (VRP), Combinatorial Optimization (CO), Iterated Local Search (ILS); Variable Neighborhood Descent with Random neighborhood ordering (RVND). (*) Trường ĐH KTCN LA TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 50
NGHIÊN CỨU - TRAO ĐỔI 1. Mở đầu Bài toán lập lộ trình xe (VRP) được Phương pháp metaheuristic là phần lõi giới thiệu lần đầu tiên bởi Dantzig and trung tâm một số lớn các giải thuật Ramser [1]. Kể từ đó đã có rất nhiều heuristic có kết quả tốt cho các bài toán công trình mở rộng cho dạng bài toán CO, bao gồm cả bài toán VRP. Các VRP và cố gắng nỗ lực giải quyết chúng. phương pháp metaheuristic ngày càng Ngành vận tải hỗ trợ hầu hết các hoạt được chú ý và phát triển mạnh mẽ để cho động kinh tế-xã hội. Chi phí đi lại hàng ra các giải pháp có hiệu quả rất cao. năm ở Hợp chủng quốc Hoa Kỳ xấp xỉ Bài toán VRP là bài toán NP-khó [22] 45 tỉ USD [2] và doanh thu vận tải hàng cho nên việc giải quyết nó là vấn đề hóa ở Châu Âu khoảng 168 tỉ USD mỗi thách thức lớn. Việc giải bài toán VRP năm. Ngành vận tải ở Vương quốc Anh, thông thường được giải tổng quát bằng Pháp và Đan Mạch đóng góp khoảng giải thuật chính xác và giải thuật 15%, 9% và 15% tiêu dùng quốc gia heuristic. Giải thuật chính xác dùng để tương ứng [2]. Ở Việt Nam, theo số liệu tìm ra lời giải tối ưu chính xác đúng. thống kê của Tổng Cục Thống kê thì: Giải thuật heuristic để tìm giải pháp tổng số lượt hành khách vận chuyển cả trong số những cái có thể, nhưng không nước trong năm 2010 là 71.942,90 triệu đảm bảo rằng cái tốt nhất sẽ được tìm lượt người.km; tổng khối lượng hàng hoá thấy, do đó có thể giả định đó là giải luân chuyển cả nước trong năm 2010 là thuật xấp xỉ và không chính xác. 73.572,10 triệu tấn.km. Như nói ở trên, tài toán VRP cho đến VRP và các dạng của nó có ứng dụng nay đã được phát triển thành nhiều dạng và vai trò rất quan trọng trong dây khác nhau và việc giải tất cả các dạng chuyền cung ứng (lĩnh vực quản trị phân bài toán VRP là công việc khó khăn và phối) và liên quan chặt chẽ đến ngành rất phức tạp. Trong khuôn khổ bài báo vận chuyển hàng hóa và con người. Do này chỉ tập trung vào các dạng sau: sự quan trọng trong ứng dụng thực tế nên (i) Capacitated VRP (CVRP). dạng bài toán VRP được nghiên cứu và (ii) VRP with Simultaneous Pickup phát triển rộng rãi. Golden và các cộng and Delivery (VRPSPD). sự [18] đã nghiên cứu và chỉ ra các (iii) VRP with time window (VRPTW). trường hợp ứng dụng bài toán VRP ở (iv) Multi-depot VRP (MDVRP). nhiều lĩnh vực khác nhau: chất thải rắn, (v) Heterogeneous Fleet VRP nước giải khát, thực phẩm, sữa, các (HFVRP) và các dạng mở rộng của nó. ngành công nghiệp báo chí, hệ thống thư Phần còn lại bài báo như sau: phần kế viện … Công trình Toth and Vigo [21] tiếp định nghĩa 5 dạng bài toán VRP đã cho thấy việc sử dụng công cụ tin học đề cập ở trên. Phần 3 rà soát và thống kê hóa trong việc hoạch định phân phối sơ lược các bài báo có phương pháp giải mang lại 5% đến 10% tiết kiệm chi phí quyết nền tảng và đóng góp quan trọng vận chuyển. cho 5 dạng VRP. Phần 4 trình bày giải Các phương pháp heuristic được sử thuật heuristic ILS-VND cho các bài dụng rộng rãi để xử lý các bài toán tối ưu toán đề cập ngay ở trên: (i) Capacitated tổ hợp (CO) do chúng có khả năng đưa ra VRP; (ii) VRP with Simultaneous Pickup giải pháp tốt trong một khoảng thời gian and Delivery; (iii) VRP with time chấp nhận được. window; (iv) Multi-depot VRP; (v) TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 51
NGHIÊN CỨU - TRAO ĐỔI Heterogeneous Fleet VRP. Cuối cùng từng khách hàng. Bài toán cần xây dựng Phần 5 kết quả, đánh giá và kết luận. một tập lộ trình hợp lý, chi phí thấp – 2. Bài toán VRP và các dạng mở rộng dành cho từng xe một. Một lộ trình là thứ của bài toán VRP tự của các vị trí mà một xe phải đến với Khai báo bài toán: Cho G (V, E) là số lượng hàng được yêu cầu nó phải một đồ thị vô hướng có trọng số, V đại cung cấp. Xe phải bắt đầu và kết thúc lộ diện cho các địa điểm (đỉnh) và các cạnh trình của nó tại kho trung tâm. trong E đại diện cho đường đi giữa một Mục đích bài toán là: tìm ra lộ trình cặp địa điểm. Đi kèm với từng đường đi xe ngắn nhất (tối thiểu tổng độ dài của e ∈ E là một trọng số không âm a(e) thể tất cả các lộ trình xe) mà tất cả khách hiện khoảng cách giữa hai đỉnh. hàng có yêu cầu phục vụ phải được thoả Cho O ⊆ V đại diện cho tập kho hàng, mãn [3]; hoặc tìm ra lộ trình nhanh nhất mỗi kho x ∈ O lúc đầu chứa m(x) xe. (tối thiểu lộ trình dài nhất cho tất cả các Cho C ⊆ V là tập khách hàng, mỗi x ∈ C lộ trình xe) [4]. có nhu cầu d(x) ≥ 0, nhu cầu là số đơn vị Như vậy, phải xây dựng một tập có tới hàng hóa mà khách hàng có yêu cầu. m lộ trình mà: (i) từng lộ trình bắt đầu và Mục đích bài toán là thiết kế một tập kết thúc tại kho; (ii) tất cả nhu cầu phải lộ trình tối ưu và/hoặc lịch trình cho được thỏa mãn; (iii) sức tải của các xe từng xe theo thứ tự để thỏa mãn tất cả không bị vượt tải; (iv) một khách hàng các yêu cầu của khách hàng. chỉ được duy nhất một xe đi đến; (v) Nhóm bài toán VRP có nhiều dạng tổng chi phí phải tối thiểu hóa. khác nhau, trong khuôn khổ bài báo sẽ c. Bài toán VRPTW: là bài toán trình bày 5 dạng bài toán VRP đã đề cập VRP, có cấu hình tương tự CVRP với ở trên là: (i); (ii); (iii); (iv); (v). thêm ràng buộc là từng yêu cầu khách a. Bài toán VRP (gốc): có nhiều xe hàng phải được phục vụ trong một khung bắt đầu ở một kho trung tâm để phục vụ thời gian (từng khách hàng phải được đi khách hàng. Mỗi xe có tốc độ khác nhau. đến trong một khoảng thời gian xác định, Mục đích bài toán là tối thiểu tổng thời được gọi là khung thời gian) [5] [6] [7]. gian để đến từng khách hàng có yêu cầu d. Bài toán VRPSPD: là bài toán mở [1]. Nếu thay thế yêu cầu về thời gian rộng bài toán CVRP, mà mỗi khách hàng thành tổng chi phí (khoảng cách) ít nhất i ∈ V’= V \ {0} (đỉnh {0} là đỉnh đại diện thì ta có bài toán người bán hàng đi du cho kho hàng, các đỉnh còn lại là khách lịch - Traveling Salesman Problem hàng) có cả hai nhu cầu: phân phối hàng (TSP). d(i); thu hàng p(i). Bài toán dạng này có b. Bài toán CVRP: là bài toán VRP, thể được xem xét như là bài toán Pickup có nhiều xe được dán nhãn từ: 1, 2, .., m, and Delivery Problem (PDP). khởi hành từ một kho trung tâm để phục Bài toán PDP được Berbeglia và các vụ khách hàng. Xe i ∈ {1, 2, .., m} có sức cộng sự [8] đưa ra một lược đồ phân lớp tải w(i), từng khách hàng x ∈ C có nhu tổng quát cho nó dựa trên các đặc trưng cầu d(x). từng bài toán. Berbeglia và các cộng sự Các xe được đặt ở một kho trung tâm đã đưa bài toán VRPSPD vào dạng bài và sẽ đi đến các khách hàng nằm rải rác toán PDP đa xe một – nhiều – một kèm khắp nơi trên các vị trí, sẽ đi đến các vị theo các nhu cầu. trí theo trình tự trước sau để phục vụ TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 52
NGHIÊN CỨU - TRAO ĐỔI Bài toán VRPSPD lần đầu tiên giới Bài toán dạng HFVRP đầu tiên được thiệu bởi Min [9]. Tác giả đã trình bày đưa ra là FSM do Golden và các cộng sự một giải thuật heuristic để giải quyết một [11]. Các tác giả đã phát triển 2 giải bài toán trong cuộc sống liên quan đến thuật heuristic: giải thuật 1 phát triển phân phối và thu nhặt sách của một thư dựa trên giải thuật [12]; giải thuật 2 phát viện công cộng. triển dựa vào hoạch định đường đi lớn. e. Bài toán MDVRP: là bài toán mở 3. Một số giải thuật quan trọng cho rộng bài toán CVRP. Cho G là tập kho, nhóm bài toán VRP xe phải bắt đầu và kết thúc tại cùng một Trong bài báo này sẽ đề cập đến một kho, số lượng xe của từng kho được cho số bài báo quan trọng đã công bố thuộc là dữ liệu nhập vào. nhóm bài toán VRP. Đa số các bài báo Tillman [10] đã định nghĩa lần đầu được đề cập đều được công bố trong tiên bài toán MDVRP. vòng 15 năm trở lại, nhưng một số bài f. Bài toán HFVRP: là bài toán mở báo cũ hơn cũng sẽ nhắc đến do tính rộng bài toán VRP, cho phép các xe với quan trọng và nền tảng của nó. Các sức tải khác nhau, thay vì đoàn xe đồng thống kê bài toán được chọn ở sau là một nhất sức tải. Đoàn xe được tạo thành từ phần của [22]. m dạng xe khác nhau, với M = {1, 2, …, a. Xét bài toán CVRP: m}. Từng u ∈ M, có m(u) xe, từng xe có Một số phương pháp chính xác cho lời sức tải Q(u). Mỗi xe có một chi phí cố giải bài toán: Brammel và Simchi-levi định bởi hàm f(u) và chi phí riêng theo (2002); Fisher (1994); Laporte và các từng khoảng cách. cộng sự (1985); Lapote và Nobert g. Bài toán mở rộng của HFVRP: có (1987); Lysgaard và các cộng sự (2004); nhiều dạng mở rộng cho bài toán HFVRP Naddef và Rinaldi (2002); Toth và Vigo trong thực tế. Các bài toán này chủ yếu (1998); Toth và Vigo (2002). liên quan đến giới hạn của đoàn xe và Một số phương pháp metaheuristic cho các chi phí xét đến (phụ thuộc hay cố lời giải bài toán: định).  Mô phỏng luyện kim và tất định  HVRPFD: giới hạn đoàn xe, các (Simulated and Deterministic chi phí cố định và phụ thuộc. Annealing): Breedam (2001); Dueck và  HVRPD: giới hạn đoàn xe, các Scheurer (1990); Dueck (1993); Osman chi phí phụ thuộc, không có chi (1993); Tarantilis và các cộng sự (2002). phí cố định, f(u) = 0, ∀ k ∈ M.  Tìm kiếm Tabu (Tabu Search):  FSMFD: không giới hạn đoàn xe, Barbarosoglu và Ozgur (1999); Gendreau m(u) = +∞, ∀ k ∈ M, các chi phí và các cộng sự (1994); Osman (1993); cố định và phụ thuộc. Rego và Roucairol (1996); Rego (1998);  FSMF: không giới hạn đoàn xe, Rego (2001). các chi phí cố định mà không phụ  GRASP: Hjorring (1995); Marinakis thuộc. và các cộng sự (2006).  FSMD: không giới hạn đoàn xe,  Bộ nhớ thích nghi (Adaptive các chi phí phụ thuộc và không cố Memory): Rochat và Taillard (1995); định. Taillard và các cộng sự (2001); Tarantilis và Kiranoudis (2002). TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 53
NGHIÊN CỨU - TRAO ĐỔI  Giải thuật di truyền (Genetic cộng sự (2004); Lim và Wang (2004); Algorithm): Alba và các cộng sự (2005); Taillard và các cộng sự (1997). Alba và Dorronsoro (2006); Baker và  GRASP (Greedy Randomized Ayechew (2003); Berger và Mohamed Adaptive Search Procedure): (2003); Jaszkiewicz và Kominek (2003); Chaovalitwongse và các cộng sự (2003); Marinakis và các cộng sự (2006); Mester Kontoravdis và Bard (1995); Li (2004); và các cộng sự (2007); Prins (2004). Lim và Wang (2004).  Tối ưu hóa đàn kiến (Ant Colony  Giải thuật di truyền (Genetic Optimization): Bullnheimer và các cộng Algorithm): Alvarenga và các cộng sự sự (1997); Doerner và các cộng sự (2007); Hwang (2002); Potvin và Bengoi (2002); Mazzeo và Loiseau (2004); (1996); Tan và các cộng sự (2003); Reimann và các cộng sự (2002); Thangiah (1993). Reimann và các cộng sự (2003);  Tối ưu hóa đàn kiến (Ant Colony Reimann và các cộng sự (2004). Optimization): Gambardella và các cộng  Mạng nơ-ron (Neural Networks): sự (1999). Modares và các cộng sự (1999).  Mạng nơ-ron (Neural Networks):  Dạng khác (Others): Coy và các Potvin và Robillard (1995). cộng sự (2001); Irnich và các cộng sự  Phương pháp khác (Other (2006); Kytöjoki và các cộng sự (2005); Methods): Cordone và Calvo (2001); Li và các cộng sự (2005); Marinakis Kilby và các cộng sự (1999); Liu và (2006); Mester và Braysy (2005). Shen (1999); Mester và Braysy (2004); b. Xét bài toán VRPTW: Russel và Chiang (2006). Một số phương pháp chính xác cho lời c. Xét bài toán VRPSPD: giải bài toán: Desrochers và các cộng sự Một số phương pháp chính xác cho lời (1992); Desrosiers và các cộng sự giải bài toán: Dell'Amico và các cộng sự (1986); Baker và Schaffer (1986); (2006); Angelelli và Manisini (2002); Brammel và các cộng sự (1993); Potvin Dethloff (2001); Montané và Galvão và Rousseau (1993); Rousseau và các (2006); Subramanian (2008). cộng sự (2004); Solomon và các cộng sự Một số phương pháp metaheuristic (1988). cho lời giải bài toán: Một số phương pháp metaheuristic Tác giả năm Phương pháp cho lời giải bài toán: Vural 2003 Genetic  Mô phỏng luyện kim (Simulated and Algorithm (GA) Deterministic Annealing): Arbelaitz và Røpke và 2004 Large các cộng sự (2001); Chiang và Russel Pisinger Neighborhood (1996); Czech và Czarnas (2002); Li và Search Lim (2003). Crispim và 2005 TS+ Variable  Tìm kiếm Tabu (Tabu Search): Brandão Neighborhood Badeau và các cộng sự (1997); Brandao Descent VND (1998); Bräysy và Grendreau (2001); Chen và Wu 2006 Danh sách Tabu Cordeau và các cộng sự (2001); Subramanian 2008 ILS+VND Homberger và Gehring (1999); Li và các và các cộng sự TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 54
NGHIÊN CỨU - TRAO ĐỔI Zachariadis 2011 Tìm kiếm địa 4. Giải thuật heuristic ILS cho các bài and phương toán VRP tổng quát Kiranoudis Nội dung thuật toán ILS này chủ yếu d. Bài toán MDVRP: ở [18] [19]. Theo [18] [19] thì giải thuật Một số phương pháp metaheuristic heuristic ILS kết hợp RVND đã cho kết cho lời giải bài toán: quả tốt hơn nhóm giải thuật khác đã phát Tác giả năm Phương pháp triển trước đó cho nhóm bài toán VRP, Renaud và 1996 TS nhất là dạng bài toán HFVRP. các cộng sự a. Giải thuật heuristic ILS Cordeau và 1992 TS + GENI Giải thuật 4.1 ILS các cộng sự 1: Procedure ILS Baldacci và 2003 Giải thuật chính 2: s 0  tao_giai_phap_dau; Mingozzi xác trên SP 3: s * tim_vung(s 0 ); Vidal và các 2004 GA lai 4: while dieu_kien_dung do cộng sự 5: s’ tron(s *, lich_su); e. Bài toán HFVRP và các dạng mở 6: s *’  tim_vung (s’); rộng: 7: s *  thoa_dieu_kien(s *, s *’, lich_su); Một số phương pháp metaheuristic 8: end ILS; cho lời giải nhóm bài toán: Giải thuật ILS có 4 thủ tục chính: (i) Tác giả năm Dạng Phương tao_giai_phap_dau, một giải pháp pháp ban đầu được xây dựng; (ii) tim_vung, cải tiến giải pháp ban đầu; Ochi và 1998 FSMF GA+ (iii) tron, vị trí bắt đầu trộn lẫn giải các Scatter pháp; (iv) thoa_dieu_kien, xác định giải cộng sự Search pháp nào thích hợp để tiếp tục. Taillard 1999 HVRPD, TS + b. Giải thuật heuristic ILS-RVND FSMD daptive Giải thuật 4.2 ILS-RVND Memory 1: Procedure ILS-RVND(MaxIter, Procedure MaxIterILS, v) Lee và 2008 FSMF, TS+ Set 2: tai_du_lieu( ); các FSMD Partitionin 3: if v chưa xác định then cộng sự g (SP) 4: v  so_luong_xe(seed); Liu và 2004 FSMF, GA lai 5: f*  ∞; các FSMD 6: for i:=1,..., MaxIter do cộng sự 7: s  tao_giai_phap_dau (v, MaxIter, Imran 2009 FSMF, Variable seed); và các FSMD, Neighborh 8: s’  s; cộng sự FSMFD ood Search 9: iterILS  0; Li và 2010 HVRPFD SP +AMP 10: while iterILS ≤ MaxIterILS do các + TS 11: s  RVND(s); cộng sự 12: if f(s) < f(s’) {hoặc v của s < v của s 0 ’ (chỉ xét khi v là nhỏ nhất)} then Brandão 2011 HVRPD TS 13: s’  s; 14: iterILS  0; TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 55
NGHIÊN CỨU - TRAO ĐỔI 15: s  tron(s’, seed); Giải thuật cho phép có thể số lượng xe 16: iterILS  iterILS + 1; có được thì chưa biết lúc ban đầu. 17: if f(s’) < f* then Candidate List (CL) là danh sách tạo bởi 18: s*  s’; khách hàng mà chưa được thêm vào từng 19: f*  f(s’); phần giải pháp. Đầu tiên xét 1 xe (dòng 20: return s*; 2). Một khách hàng k ∈ CL được chọn 21: end ILS-RVND. ngẫu nhiên và được chèn vào lộ trình Tham số MaxIterILS là số lần trộn đơn (dòng 2-5). Nếu CL khác rỗng thì liên tiếp lớn nhất có thể có được. v là số một điều kiện chèn được mô tả ở giải xe (hoặc lộ trình), nếu giá trị v chưa xác thuật 4.2.2 sẽ được chọn ngẫu nhiên để định thì sẽ được ước tính ở (dòng 3-5). tính khách hàng k ∈ CL ở từng vị trí của Giải thuật lặp lại MaxIter lần (dòng 6- lộ trình v và việc chèn chi phí thấp nhất 19), mỗi lần lặp thì một giải pháp được sẽ được xét (dòng 6-14). Nếu xe v đã đầy tạo ra bằng cách xây dựng thủ tục (dòng thì một xe mới sẽ được thêm vào (dòng 7). Vòng lặp chính của giải thuật ILS 11-12). (dòng 10-16) dùng thủ tục RVND để tìm  tao_giai_phap_dau: kiếm cải tiến giải pháp ban đầu (dòng Giải thuật 4.2.2 tao_giai_phap_dau 11) ở đoạn tìm địa phương kết hợp với 1: Procedure tao_giai_phap_dau (v, một tập cấu hình trộn (dòng 15). MaxIter, seed) Thủ tục trộn luôn luôn lấy giải pháp 2: thu_nghiem  0; tốt nhất (s’) của một vòng lặp đã cho. 3: khởi tạo CL; c. Trình bày các thủ tục trong 4: s ={s 1 , .. , s v-1 } là tập tạo bởi v-1 lộ trình heuristic ILS-RVND 5: for v0 = 1 .. v - 1 do  so_luong_xe: 6: s v  k ∈ CL chọn ngẫu nhiên; Giải thuật 4.2.1 so_luong_xe 7: cập nhật CL; {CL  CL – {k}} 1: Procedure so_luong_xe (seed) 8: Điều kiện chèn  MCFIC hoặc 2: v  1; NFIC (chọn ngẫu nhiên); 3: khởi tạo CL 9: Cách chèn  SIS hoặc PIS (chọn 4: s v  k ∈ CL (được chọn ngẫu ngẫu nhiên); nhiên); 10: if Cách chèn = SIS then 5: cập nhật CL; 11: s  chen_trinh_tu(s, v, CL, điều 6: while CL ≠ Ø do kiện chèn); 7: tính chi phí g(k) cho từng k ∈ CL 12: else (dùng điều kiện chèn ngẫu nhiên); 13: s  chen_song_song(s, v, CL, điều 8: gmin  min {g(k) | k ∈ CL}; kiện chèn); 9: n  khách hàng e cho gmin ; 14: if s không phù hợp then 10: s v  s v U {n}; 15: if v chưa xác định then 11: if xe v đầy then 16: thu_nghiem  thu_nghiem + 1; 12: v  v + 1; 17: if thu_nghiem = MaxIter then 13: else 18: v  v + 1; 14: cập nhật CL; 19: thu_nghiem  0; 15: return v; 20: lặp dòng 3; 16: end so_luong_xe. 21: else TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 56
NGHIÊN CỨU - TRAO ĐỔI 22: if đội xe không đồng nhất và không được xét khi đánh giá việc chèn chi phí ít giới hạn then nhất. 23: thêm một lộ trình rỗng cho từng kiểu  Giải thuật 4.2.3 RVND xe s 1: Procedure RVND(s) 24: return s; 2: Cập nhật Auxiliary Data Structures 25: end tao_giai_phap_dau. (ADS); Từng lộ trình sẽ nhận khách hàng k 3: Khởi tạo liên lộ trình Neighborhood vào, chọn ngẫu nhiên (dòng 5-7). Một List (NL); Điều kiện chèn và Cách chèn sẽ được 4: while NL ≠ 0 do chọn ngẫu nhiên (dòng 8-9). Một giải 5: chọn một lân cận N (n) ∈ NL ngẫu nhiên; pháp đầu được tạo ra do kết hợp Điều 6: tìm lân cận s’ của s ∈ N(n) ; kiện chèn và Cách chèn (dòng 10-13). 7: if f(s’) < f(s) then Nếu thấy giải pháp không hiệu quả thì 8: s  s’; giải thuật lặp lại ở dòng 3. 9: s  tim_lo_trinh_trong(s); Nếu số xe chưa biết cho từng trường 10: if đoàn xe không đồng nhất và hợp, số thử nghiệm cho việc tạo ra một không giới hạn then giải pháp ban đầu phù hợp là MaxIter và 11: cập nhật đoàn xe bằng cách tạo một sau đó số xe sẽ được thêm vào (dòng một xe rỗng trong từng loại xe 14-20). Nếu một giải pháp phù hợp tìm 12: cập nhật NL; {NL ở trong tất cả cấu thấy thì giải thuật kết thúc (dòng 21-25). trúc lân cận lộ trình bên trong} Điều kiện chèn: chi phí để chèn một 13: else khách hàng chưa có trong lộ trình k ∈ 14: loại N (n) khỏi NL; CL vào một lộ trình đã cho bằng Modied 15: cập nhật ADS; Cheapest Feasible Insertion Criterion 16: lam_ rong_lo_trinh(s); {chỉ xét khi (MCFIC) với công thức sau: đoàn xe cần phải tối thiểu hóa} g(k) = (cik + c kj - cij ) - ¥ (c0k + c k0 ) 17: return s; Hàm g(k) là chi phí chèn. Giá trị g(k) 18: end RVND. được tính gồm 2 phần. Phần 1 tính chi VND thực hiện việc tìm địa phương phí chèn khách hàng k nằm giữa cặp với việc sử dụng một thứ tự lân cận ngẫu khách hàng liền kề i và j. Phần 2 tính chi nhiên (RVND). Cho N = { N (1) , N (2), …, phí thêm để tránh phải việc chèn khách N(r) } là tập cấu trúc lân cận. Bất cứ khi hàng ở quá xa kho hàng. Chi phí đi tới và nào một lân cận đã cho của tập N thất bại lui từ kho hàng được tính là ¥. để cải tiến giải pháp hiện tại, thì giải Nearest Feasible Insertion Criterion thuật RVND chọn ngẫu nhiên một lân (NFIC): trực tiếp tính khoảng cách giữa cận khác trong cùng một tập để tiếp tục 1 khách hàng k ∈ CL với từng khách tìm kiếm toàn bộ không gian giải pháp. hàng i mà đã được thêm vào giải pháp. N được tạo chỉ bởi cấu trúc liên lộ trình g(k) = (c ik), giả sử việc chèn k luôn lân cận. sau i. Trước tiên, một NL chứa một số xác Cách chèn: chọn cách chèn theo trình tự định bước đi liên lộ trình sẽ được khởi (SIS), chỉ một lộ trình đơn được xét để tạo (dòng 3). Trong vòng lặp chính (dòng chèn vào ở từng vòng lặp; chọn cách 4-13), một lân cận N (n) ∈ NL được chọn chèn song song (PIS), tất cả các lộ trình ngẫu nhiên (dòng 5) và sau đó bước đi TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 57
NGHIÊN CỨU - TRAO ĐỔI chấp nhận được tốt nhất sẽ được xác VRP mà giải thuật ILS-RVND đã cho kết định (dòng 6). Nếu có cải tiến giải pháp, quả tốt. Trong phần 3 bài báo đã rà soát một tìm kiếm địa phương bên trong-lộ và thống kê các bài báo có giải pháp nền trình sẽ được thực thi, đoàn xe được cập tảng và quan trọng. nhật (chỉ với đoàn xe không giới hạn) và Giải thuật ILS-RVND dựa trên ILS, là NL sẽ được nhận thêm vào tất cả các lân một thủ tục đa bắt đầu (chạy với các cận (dòng 7-12)… Tập ADS sẽ được cập dạng tham số khác nhau) và lặp lại nhật vào lúc bắt đầu thực thi (dòng 2) và MaxIterILS số lần trộn liên tiếp. Trong bất cứ khi nào tìm kiếm địa phương được quá trình chèn thì sử dụng giải thuật thực thi (dòng 15). heuristic đặc biệt ở đoạn xây dựng giải  Giải thuật 4.2.4 tim_lo_trinh_trong pháp, giải thuật đó là giảm lân cận giá trị 1: Procedure tim_lo_trinh_trong (s) theo thứ tự lân cận ngẫu nhiên (RVND), 2: khởi tạo Intra-Route Neighborhood trong đoạn tìm kiếm địa phương. List (NL’); Kịch bản chèn là chèn trình tự 3: while NL ≠ 0 do Sequential Insertion Strategy (SIS) và 4: chọn một lân cận N ’(n) ∈ NL’ ngẫu chèn song song Parallel Insertion nhiên; Strategy (PIS). Điều kiện để chèn là dựa 5: tìm lân cận tốt nhất s’ của s ∈ NL’ (n) trên điều kiện chèn hợp lý gần nhất 6: if f(s’) < f(s) then Nearest Feasible Insertion Criterion 7: s  s’; (NFIC) và dựa trên điều kiện chèn hợp lý 8: else chỉnh sửa ít nhất Modied Cheapest 9: loại NL’ (n) khỏi NL’; Feasible Insertion Criterion (MCFIC). 10: return s; Trong quá trình chèn, giải thuật chọn 11: end tim_lo_trinh_trong. ngẫu nhiên một điều kiện chèn và kịch Trước tiên, một danh sách lân cận NL’ bản chèn. Nếu điều kiện chèn NFIC được được khởi tạo với tất cả cấu trúc lân cận chọn thì chi phí chèn một khách hàng k ở lộ trình-trong (dòng 2). Trong khi NL’ sau khách hàng i là c ik . Nếu điều kiện khác rỗng thì một lân cận NL’ (n) ∈ NL sẽ chèn MCFIC được chọn thì chi phí chèn được chọn ngẫu nhiên và một tìm kiếm một khách hàng k ở giữa khách hàng i và địa phương được thực thi cho đến khi j là (c ik + ckj - cij ) + ¥(c 0k + c k0 ). Tham số không phát hiện thêm việc cải tiến nào ¥ điều khiển mức độ ưu tiên chèn khách nữa (dòng 3-9). hàng vị trí ở xa kho hàng.  ADS: cấu trúc dữ liệu phụ trợ để Giải thuật RVND là kiến trúc lân cận tăng cường tìm kiếm địa phương, các lộ trình bên trong. Mỗi lần lặp thì 1 lộ thông tin dữ liệu đều lưu trữ dạng trình sẽ được chỉnh lại do việc tìm kiếm mảng. Cấu trúc ADS sẽ được tùy chọn địa phương chuyển từ liên lộ trình sang tùy thuộc vào kết cấu cụ thể của từng lộ trình bên trong. Việc chèn lại bao gồm dạng dữ liệu cho trước. việc chuyển một khách hàng từ vị trí 5. Kết quả, đánh giá và kết luận hiện tại đến một vị trí khác trong cùng Do tầm quan trọng trong thực tế ứng một lộ trình. dụng mà bài toán VRP được phát triển Giải thuật heuristic ILS-RVND tóm nhiều phiên bản khác nhau và đã có rất lược ở trên có ưu điểm là kiến trúc giải nhiều công trình nghiên cứu. Trong phần thuật đơn giản và chỉ có vài ba tham số 2 đã trình bày cô đọng 5 dạng bài toán đầu vào. Các ưu điểm này hỗ trợ rất tốt TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 58
NGHIÊN CỨU - TRAO ĐỔI cho việc triển khai lập trình và giảm tải mẫu thử ILS-RVND thực thi khoảng 20 bớt tính toán cho máy điện toán. Thêm lần và mỗi lần thì sẽ được tính lại. Kết vào đó, giải thuật có tính linh hoạt rất quả cho thấy chất lượng giải pháp và cao ở chỗ có thể thiết lập cấu hình tùy thời gian tính toán có khuynh hướng tăng chọn cho đoàn xe phục vụ khách hàng. dần theo giá trị và MaxIter. Với cấu Tính linh hoạt này có tác dụng rất mạnh hình = 5 and MaxIter = 50 cho thấy mẽ để áp dụng giải các bài toán có đoàn thời gian tính toán ít hơn nhiều khi so xe hỗn hợp trong thực tế. với cấu hình có kết quả tốt nhất về chất Giải thuật ILS-RVND có thể lập trình lượng giải pháp ( = 7 and MaxIter = với nhiều ngôn ngữ lập trình khác nhau, ngôn ngữ lập trình được chọn ở đây là 75). C++. Cấu hình máy tính để chạy thử Tổng quát, thuật toán đã được [18] nghiệm là Intel R CoreTM i7 tốc độ 2.93 [19] thử nghiệm với 52 trường hợp tiêu GHz và 8 GB RAM, hệ điều hành Linux chuẩn bài toán VRP với 100 khách hàng. 64 bits (kernel 2.6.32-22). Kết quả thực nghiệm cho thấy giải thuật Tham số để chạy chương trình: n là số heuristic ILS-RVND đã cho kết quả cải khách hàng; BKS là số lượng giải pháp tiến cho 4 trường hợp và tương đương đã được biết; gap là độ lệch giữa ILS- với 42 trường hợp khác. RVND và giải pháp tốt nhất đã biết. Trong tương lai, giải thuật cần được Xét bài toán HFVRP và các dạng mở cải tiến để phù hợp với các yêu cầu thêm rộng: thì với từng nhóm mẫu thử, hiệu như: nhu cầu khách hàng theo khung thời suất chạy thử với giải thuật ILS-RVND gian trực tuyến, thu nhặt và phân phối được so sánh với các giải thuật khác thì hàng hóa, đa kho hàng… Tuy giải thuật dùng công thức: ILS-RVND có nhiều ưu điểm nhưng cũng cần phải so sánh với các giải thuật phát triển mạnh mẽ theo xu hướng ngày nay là các giải thuật lai (Hybrid Algorithms). Số khách hàng chọn trong (50-480), MaxIter có 2 giá trị là 50 và 75, với mỗi TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 59
NGHIÊN CỨU - TRAO ĐỔI Tài liệu tham khảo [1]. Angelelli, E.; Mansini, R (2002), “Quantitative Approaches to Distribution Logistics and Supply Chain Management”, Springer, Berlin-Heidelberg. [2]. Berbeglia, G.; Cordeau, J.-F.; Gribkovskaia, I.; Laporte, G (2007), “Static pickup and delivery problems: a classication scheme and survey ”, Top 15 (April 2007), 1-31. [3]. Clarke, G.; Wright, J. W (1964), “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research 12 (1964), 568-581. [4]. Dell'Amico, M.; Righini, G.; Salani, M (2006), “A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection”, Transportation Science 40, 2 (2006), 235-247. [5]. Dethloff, J (2001), “Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up”, OR Spektrum 23 (2001), 79-96. [6]. E. W. Dijkstra và C. S. Scholten (1980), “Termination detection for diffusing computations”, Inf. Proc. Letters, 11(1):1–4. [7]. G. B. Dantzig và J. H. Ramser (1959), “The truck dispatching problem”, Management Science, 6(1):80–91. [8]. King; G.F. và C.F. Mast (1997), “Excess Travel: Causes, Extent and Consequences”, Transportation Research Record1111, 126−134. [9]. J. Bramel và D. Simchi-Levi (1996), “Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows ”, Operations Research, 44(3):501– 509. [10]. Golden, B. L.; Assad, A. A.; Levy, L.; Gheysens, F. G (1984), “The feet size and mix vehicle routing problem”, Computers & Operations Research 11 (1984), 49- 66. [11]. Golden, B. L.; Assad, A. A.; Wasil, E. A (2002), “The Vehicle Routing Problem”, Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, chương Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy and newspaper industries, 245 -286. [12]. Lenstra, J. K.; Rinnooy-Kan, A. H. G (1981), “Complexity of vehicle routing and scheduling problems”, Networks 11 (1981), 221-227. [13]. Lixin Tang . Xianpeng Wang (2006), “Iterated local search algorithm based on very large-scale neighborhood for prize-collecting vehicle routing problem”, Int J Adv Manuf Technol (2006) 29: 1246–1258, DOI 10.1007/s00170-005-0014-0. [14]. Min, H (1989), “The multiple vehicle routing problem with simultaneous delivery and pick-up points”, Transportation Research 23, 5 (1989), 377-386. [15]. Montan_e, F. A. T.; Galvão, R. D (2006) (2006), “A Tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service”, European Journal of Operational Research 33, 3 (2006), 595-619. [16]. O. Bräysy và M. Gendreau (2005), “Vehicle routing problem with time windows, part i: Route construction and local search algorithms ”, Transportation Science, 39(1):104–118. TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 60
NGHIÊN CỨU - TRAO ĐỔI [17]. Puca Huachi Vaz Penna, Anand Subramanian, Luiz Satoru Ochi (2013), “An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem”, J Heuristics (2013) 19:201–232, DOI 10.1007/s10732-011-9186-y. [18]. Tillman, F. A (1994), “The multiple terminal delivery problem with probabilistic demands”, Transportation Science 3 (1994), 192-204. [19]. Toth, P.; Vigo, D (2002), “The Vehicle Routing Problem”, Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, 2002. [20]. T. Ralphs; L. Kopman; W. Pulleyblank; và L. Trotter (20010, “On the capacitated vehicle routing problem”, Mathematical Programming. [21]. T. Ralphs; J. Hartman; và M. Galati (2001), “Capacitated vehicle routing and some related problems”, Rutgers University. [22]. Yannis Marinakis, Athanasios Migdalas (2007), “Annotated Bibliography In Vehicle Routing”, Technical University of Crete, University Campus, 73100 Chania. Ngà nhận 2 2 14 Ngà du t đ ng 3 2 14 TẠP CHÍ KINH TẾ - CÔNG NGHIỆP 61

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí

65 tài liệu

2431 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.