Dữ liệu cho đơn giản TSP

Question

Tôi đã viết một thuật toán di truyền đơn giản có thể giải quyết vấn đề người bán hàng đi du lịch với 5 thành phố. Tôi muốn xem nó như thế nào trên một vấn đề với nhiều thành phố, một cái gì đó như 10, 25, 50, 100, nhưng tôi không thể tìm thấy một ngày mẫu cho vấn đề để thử nó trên. Về cơ bản, tôi đang tìm kiếm danh sách 2D hoặc ma trận với khoảng cách giữa các thành phố. Sẽ tốt hơn nếu có một giải pháp. Tôi nên tìm ở đâu?

Cảm ơn bạn trước

Answer 1

Tôi không chắc chắn, nhưng khi có vẻ như, trang "Read or Write Traveling Salesman Problem (TSP) Files" có một số tập tin dữ liệu đầu vào, ví dụ, this one.

Ngoài ra, "TSP Test Data" là một nguồn tốt.

Answer 2

Thư viện điểm chuẩn nổi tiếng cho TSP với các trường hợp dao động từ 14 đến gần 100.000 thành phố là TSPLIB. Các trường hợp đã được giải quyết để tối ưu, đối với một số trường hợp giải pháp tối ưu cũng có sẵn.

Nhiều trường hợp có nền tảng thực tế như du lịch là thành phố ở Đức, Thụy Sĩ, Hoa Kỳ hoặc trên toàn thế giới. Một số trường hợp đại diện cho các vấn đề khoan cho bố trí bảng máy tính Ngoài ra còn có một trường hợp đại diện cho chuyến đi của Ulysses.

Answer 3

Các nguồn tôi đã tìm thấy trực tuyến khá lớn. Tôi có thể làm điều gì đó sai, nhưng 10 địa điểm (thành phố) mất ~ 0,6 và 11 địa điểm mất ~ 7 giây. Số liệu giải pháp nhỏ nhất được biết đến mà tôi có thể tìm thấy là 15 địa điểm (và được coi là "nhỏ", "cổ điển" là 48 địa điểm) nhưng có lẽ đó là các thuật toán tối ưu hóa (không phải brute force). Cuối cùng tôi đã thực hiện bảng của riêng tôi với các thành phố thế giới thực:

  m 
      a 
      a       h 
      s  h s    u 
      t a e i g   l 
      r a e t e   s 
      i c r t l e b b a  e 
      c h l a e c o e n o p 
      h e e r e h n r n h e 
      t n n d n t n g e e n 
maastricht 0 29 20 21 16 31 100 12 4 31 18 
    aachen 29 0 15 29 28 40 72 21 29 41 12 
    heerlen 20 15 0 15 14 25 81 9 23 27 13 
    sittard 21 29 15 0 4 12 92 12 25 13 25 
    geleen 16 28 14 4 0 16 94 9 20 16 22 
     echt 31 40 25 12 16 0 95 24 36 3 37 
     bonn 100 72 81 92 94 95 0 90 101 99 84 
    hulsberg 12 21 9 12 9 24 90 0 15 25 13 
    kanne 4 29 23 25 20 36 101 15 0 35 18 
     ohe 31 41 27 13 16 3 99 25 35 0 38 
     epen 18 12 13 25 22 37 84 13 18 38 0 

Optimal (by program): cities 0-7-4-3-9-5-2-6-1-10-8-0 = 253km 
maastricht -> hulsberg -> geleen -> sittard -> ohe -> kanne -> echt 
-> heerlen -> bonn -> aachen -> epen -> kanne -> maastricht 

Định dạng dữ liệu có thể đọc được bởi chương trình là một bảng một phần (vì nó là đối xứng):

29 20 21 16 31 100 12 4 31 18 
15 29 28 40 72 21 29 41 12 
15 14 25 81 9 23 27 13 
4 12 92 12 25 13 25 
16 94 9 20 16 22 
95 24 36 3 37 
90 101 99 84 
15 25 13 
35 18 
38 

Đối với tôi đây mất ~ 6,7 giây để xử lý trên gen thứ 3 i7 (i7-3630QM). Chương trình được viết bằng C++, đơn luồng và chỉ đơn giản là brute-lực lượng khả năng. Để thử nghiệm có thể thực tế hơn khi xóa một địa điểm, sau đó phải mất ~ 660ms (0,7 giây) mà vẫn đủ để xem liệu các thay đổi mã có tạo ra nhiều sự khác biệt hay không.