From 86240eac6b3889aa01c93e32978138572f87f81b Mon Sep 17 00:00:00 2001 From: Mitsuo Tokumori Date: Tue, 3 May 2022 22:29:21 -0500 Subject: Add some translations and sample input data --- example1.py | 12 +- multiple_ant_colony_system.py | 11 +- odiparpack/pedidosperu195.txt | 392 +++++++++++++++++++++--------------------- 3 files changed, 209 insertions(+), 206 deletions(-) diff --git a/example1.py b/example1.py index c867f44..8b909bb 100644 --- a/example1.py +++ b/example1.py @@ -1,16 +1,18 @@ from vrptw_base import VrptwGraph from multiple_ant_colony_system import MultipleAntColonySystem + def main(): - file_path = './solomon-100/c101.txt' - #file_path = './odiparpack/pedidosperu78.txt' + #file_path = './solomon-100/c101.txt' + file_path = './odiparpack/pedidosperu195.txt' ants_num = 10 - beta = 2 # 5 - q0 = 0.1 # 0.5 ? + beta = 2 # 5 + q0 = 0.1 # 0.5 ? show_figure = True graph = VrptwGraph(file_path) - macs = MultipleAntColonySystem(graph, ants_num=ants_num, beta=beta, q0=q0, whether_or_not_to_show_figure=show_figure) + macs = MultipleAntColonySystem(graph, ants_num=ants_num, beta=beta, q0=q0, + whether_or_not_to_show_figure=show_figure) macs.run_multiple_ant_colony_system() diff --git a/multiple_ant_colony_system.py b/multiple_ant_colony_system.py index 45c896a..9305b95 100644 --- a/multiple_ant_colony_system.py +++ b/multiple_ant_colony_system.py @@ -183,10 +183,11 @@ class MultipleAntColonySystem: :return: """ - # 最多可以使用vehicle_num辆车，即在path中最多包含vehicle_num+1个depot中，找到路程最短的路径， - # vehicle_num设置为与当前的best_path一致 + # At most vehicle_num vehicles can be used, that is, the path contains + # at most vehicle_num+1 depots to find the path with the shortest + # distance, vehicle_num is set to be consistent with the current best_path print('[acs_time]: start, vehicle_num %d' % vehicle_num) - # 初始化信息素矩阵 + # Initialize the pheromone matrix global_best_path = None global_best_distance = None ants_pool = ThreadPoolExecutor(ants_num) @@ -206,13 +207,13 @@ class MultipleAntColonySystem: ants_thread.append(thread) ants.append(ant) - # 这里可以使用result方法，等待线程跑完 + # Here you can use the result method to wait for the thread to finish running for thread in ants_thread: thread.result() ant_best_travel_distance = None ant_best_path = None - # 判断蚂蚁找出来的路径是否是feasible的，并且比全局的路径要好 + # Determine whether the path found by ants is feasible and better than the global path for ant in ants: if stop_event.is_set(): diff --git a/odiparpack/pedidosperu195.txt b/odiparpack/pedidosperu195.txt index 651ec69..88e286e 100644 --- a/odiparpack/pedidosperu195.txt +++ b/odiparpack/pedidosperu195.txt @@ -7,199 +7,199 @@ NUMBER CAPACITY CUSTOMER CUST NO. XCOORD. YCOORD. DEMAND READY TIME DUE DATE SERVICE TIME -0 -166.922 712.41 96 0 5433 60 -1 -85.354 682.914 22 0 5615 60 -2 -93.619 646.767 88 0 5592 60 -3 -92.734 828.799 85 0 5355 60 -4 -102.462 656.816 69 0 5292 60 -5 -50.227 628.253 3 0 5455 60 -6 -156.975 699.583 66 0 5734 60 -7 -64.518 251.936 81 0 5391 60 -8 1.52 327.456 71 0 5701 60 -9 -37.311 320.667 31 0 5343 60 -10 -14.044 210.587 76 0 5627 60 -11 -68.474 307.36 3 0 5688 60 -12 -33.207 328.199 57 0 5467 60 -13 -141.768 285.753 76 0 5272 60 -14 -96.467 386.458 86 0 5737 60 -15 -55.416 279.76 50 0 5601 60 -16 -15.619 300.062 37 0 5556 60 -17 -124.736 219.856 9 0 5328 60 -18 -86.684 333.288 9 0 5277 60 -19 -36.36 353.708 63 0 5388 60 -20 -40.73 182.633 20 0 5269 60 -21 -108.806 406.196 52 0 5663 60 -22 -47.787 358.647 25 0 5499 60 -23 -47.33 258.399 34 0 5612 60 -24 -173.806 330.402 6 0 5343 60 -25 -66.798 388.218 35 0 5468 60 -26 -79.439 323.136 64 0 5384 60 -27 461.639 -176.959 85 0 5731 60 -28 404.815 -179.078 41 0 5353 60 -29 461.76 -257.843 66 0 5493 60 -30 421.009 -250.054 34 0 5378 60 -31 367.799 -163.691 6 0 5405 60 -32 539.968 -211.301 4 0 5411 60 -33 480.68 -229.002 37 0 5525 60 -34 610.847 -484.02 17 0 5736 60 -35 480.238 -509.161 17 0 5559 60 -36 407.539 -414.337 78 0 5602 60 -37 504.648 -448.192 60 0 5647 60 -38 603.623 -399.281 25 0 5657 60 -39 486.926 -421.798 71 0 5641 60 -40 557.648 -554.124 32 0 5459 60 -41 460.607 -352.153 72 0 5734 60 -42 321.0 -176.067 15 0 5259 60 -43 311.871 -123.91 21 0 5334 60 -44 299.85 -208.375 96 0 5640 60 -45 309.412 -99.408 91 0 5535 60 -46 339.076 -107.497 37 0 5678 60 -47 323.166 -294.458 91 0 5521 60 -48 361.339 -330.367 27 0 5388 60 -49 409.879 -359.488 12 0 5471 60 -50 354.896 -218.536 60 0 5590 60 -51 329.603 -189.758 78 0 5738 60 -52 342.105 -178.702 46 0 5424 60 -53 -112.919 491.724 47 0 5421 60 -54 -165.35 543.615 21 0 5664 60 -55 -123.99 576.033 26 0 5683 60 -56 -180.108 609.831 57 0 5547 60 -57 -197.274 520.369 49 0 5433 60 -58 -198.796 630.316 78 0 5374 60 -59 -165.53 596.714 46 0 5480 60 -60 -197.63 704.655 10 0 5287 60 -61 -219.552 767.208 51 0 5523 60 -62 -126.759 523.712 69 0 5645 60 -63 -202.479 561.031 85 0 5291 60 -64 -199.359 547.922 18 0 5710 60 -65 -212.815 602.652 25 0 5330 60 -66 -12.252 -1.604 98 0 5604 60 -67 594.559 -208.3 72 0 5590 60 -68 542.821 -158.528 80 0 5598 60 -69 564.253 -141.866 63 0 5270 60 -70 622.521 -241.407 61 0 5492 60 -71 645.375 -247.639 60 0 5584 60 -72 550.239 -267.34 56 0 5544 60 -73 561.727 -163.544 95 0 5309 60 -74 624.65 -305.475 63 0 5723 60 -75 482.321 -90.891 48 0 5714 60 -76 576.329 -190.744 54 0 5597 60 -77 604.208 -141.427 15 0 5468 60 -78 600.999 -182.575 89 0 5575 60 -79 546.468 -140.107 53 0 5274 60 -80 273.463 -88.779 75 0 5622 60 -81 257.077 -104.204 96 0 5708 60 -82 190.293 -137.595 43 0 5394 60 -83 293.881 -77.096 76 0 5450 60 -84 228.772 -82.426 90 0 5719 60 -85 186.521 -173.297 65 0 5512 60 -86 240.412 -39.238 81 0 5634 60 -87 91.851 213.126 86 0 5533 60 -88 25.485 246.562 43 0 5598 60 -89 8.66 334.48 86 0 5303 60 -90 23.898 277.533 75 0 5421 60 -91 87.939 235.33 52 0 5607 60 -92 44.354 218.816 14 0 5683 60 -93 114.554 305.512 22 0 5455 60 -94 -13.216 382.68 47 0 5410 60 -95 115.22 238.896 65 0 5719 60 -96 229.568 296.508 65 0 5523 60 -97 46.936 243.203 99 0 5563 60 -98 99.841 -152.523 77 0 5593 60 -99 144.697 -224.393 77 0 5559 60 -100 232.781 -309.304 45 0 5678 60 -101 205.195 -276.634 39 0 5384 60 -102 91.99 -185.026 82 0 5603 60 -103 189.286 110.076 18 0 5272 60 -104 193.799 -1.756 71 0 5314 60 -105 190.981 14.173 84 0 5393 60 -106 202.424 -2.451 21 0 5451 60 -107 170.125 30.101 92 0 5532 60 -108 115.356 98.394 62 0 5658 60 -109 266.144 88.068 16 0 5401 60 -110 149.304 69.608 44 0 5289 60 -111 125.701 58.858 12 0 5642 60 -112 -230.954 481.711 10 0 5367 60 -113 -74.739 543.971 77 0 5540 60 -114 -266.772 535.807 90 0 5509 60 -115 -198.92 507.768 77 0 5726 60 -116 -161.915 445.157 3 0 5252 60 -117 -170.707 460.727 23 0 5285 60 -118 -275.072 513.038 37 0 5407 60 -119 -29.558 419.203 38 0 5322 60 -120 -113.211 470.395 18 0 5647 60 -121 -127.071 433.722 58 0 5286 60 -122 -222.189 437.458 0 0 5544 60 -123 -191.447 403.82 20 0 5702 60 -124 -312.254 586.488 9 0 5268 60 -125 -306.625 601.197 0 0 5551 60 -126 -319.765 593.982 46 0 5639 60 -127 -81.206 143.652 10 0 5493 60 -128 71.506 -114.734 28 0 5436 60 -129 4.169 174.936 28 0 5731 60 -130 45.118 64.371 94 0 5399 60 -131 -19.647 61.214 83 0 5615 60 -132 71.658 22.367 37 0 5463 60 -133 -64.483 104.23 65 0 5366 60 -134 0.0 0.0 71 0 5362 60 -135 28.625 153.206 10 0 5386 60 -136 123.627 -46.014 19 0 5283 60 -137 102.977 683.921 32 0 5514 60 -138 52.927 802.199 24 0 5590 60 -139 384.183 838.332 21 0 5353 60 -140 724.291 905.119 40 0 5699 60 -141 420.998 922.537 39 0 5694 60 -142 485.059 1067.329 45 0 5560 60 -143 352.945 776.388 41 0 5279 60 -144 224.773 522.105 6 0 5434 60 -145 630.652 -87.873 52 0 5479 60 -146 828.745 122.423 4 0 5656 60 -147 873.352 -60.968 76 0 5369 60 -148 673.89 -514.611 54 0 5578 60 -149 632.164 -622.681 53 0 5540 60 -150 677.822 -572.419 81 0 5449 60 -151 57.14 172.862 58 0 5492 60 -152 180.789 163.639 42 0 5386 60 -153 86.1 151.476 73 0 5742 60 -154 -298.529 823.476 46 0 5563 60 -155 -269.106 756.895 90 0 5586 60 -156 -348.08 772.735 45 0 5631 60 -157 -454.028 774.005 46 0 5395 60 -158 -399.863 761.547 12 0 5658 60 -159 -421.627 721.474 41 0 5250 60 -160 -406.627 795.697 21 0 5351 60 -161 -471.614 830.207 48 0 5571 60 -162 760.034 -318.307 19 0 5593 60 -163 733.791 -224.895 6 0 5607 60 -164 841.886 -463.394 32 0 5366 60 -165 821.941 -449.333 9 0 5480 60 -166 808.282 -351.175 78 0 5448 60 -167 740.886 -369.029 6 0 5484 60 -168 716.14 -315.339 8 0 5442 60 -169 837.365 -368.588 78 0 5321 60 -170 778.641 -421.951 30 0 5609 60 -171 796.371 -318.934 72 0 5442 60 -172 766.684 -383.324 57 0 5685 60 -173 841.065 -253.202 2 0 5491 60 -174 882.657 -466.835 85 0 5504 60 -175 49.57 553.645 32 0 5358 60 -176 37.32 604.011 21 0 5257 60 -177 28.76 568.151 6 0 5486 60 -178 57.189 625.369 40 0 5537 60 -179 33.809 541.02 17 0 5559 60 -180 6.208 668.421 1 0 5384 60 -181 77.858 569.905 93 0 5344 60 -182 -15.264 665.314 51 0 5401 60 -183 74.576 618.044 94 0 5468 60 -184 57.842 428.909 19 0 5561 60 -185 753.912 -580.69 92 0 5721 60 -186 696.981 -619.124 66 0 5642 60 -187 753.868 -663.587 85 0 5502 60 -188 778.184 -603.655 58 0 5334 60 -189 -405.393 930.174 61 0 5366 60 -190 -381.296 942.387 4 0 5571 60 -191 -360.775 950.187 70 0 5564 60 -192 364.237 146.354 51 0 5295 60 -193 277.793 407.271 29 0 5464 60 -194 169.224 334.59 97 0 5497 60 -195 702.797 252.808 40 0 5367 60 +0 -166.922 712.41 22.0 0 5636.0 60 +1 -85.354 682.914 0.0 0 0.0 60 +2 -93.619 646.767 0.0 0 0.0 60 +3 -92.734 828.799 0.0 0 0.0 60 +4 -102.462 656.816 0.0 0 0.0 60 +5 -50.227 628.253 0.0 0 0.0 60 +6 -156.975 699.583 10.0 0 5608.0 60 +7 -64.518 251.936 63.0 0 5372.0 60 +8 1.52 327.456 64.0 0 5741.0 60 +9 -37.311 320.667 24.0 0 5607.0 60 +10 -14.044 210.587 10.0 0 5427.0 60 +11 -68.474 307.36 4.0 0 5369.0 60 +12 -33.207 328.199 85.0 0 5459.0 60 +13 -141.768 285.753 33.0 0 5477.0 60 +14 -96.467 386.458 0.0 0 0.0 60 +15 -55.416 279.76 0.0 0 0.0 60 +16 -15.619 300.062 0.0 0 0.0 60 +17 -124.736 219.856 0.0 0 0.0 60 +18 -86.684 333.288 0.0 0 0.0 60 +19 -36.36 353.708 0.0 0 0.0 60 +20 -40.73 182.633 0.0 0 0.0 60 +21 -108.806 406.196 0.0 0 0.0 60 +22 -47.787 358.647 0.0 0 0.0 60 +23 -47.33 258.399 61.0 0 5577.0 60 +24 -173.806 330.402 99.0 0 5264.0 60 +25 -66.798 388.218 87.0 0 5635.0 60 +26 -79.439 323.136 4.0 0 5388.0 60 +27 461.639 -176.959 1.0 0 5608.0 60 +28 404.815 -179.078 0.0 0 0.0 60 +29 461.76 -257.843 0.0 0 0.0 60 +30 421.009 -250.054 0.0 0 0.0 60 +31 367.799 -163.691 0.0 0 0.0 60 +32 539.968 -211.301 0.0 0 0.0 60 +33 480.68 -229.002 0.0 0 0.0 60 +34 610.847 -484.02 0.0 0 8000.0 60 +35 480.238 -509.161 15.0 0 5671.0 60 +36 407.539 -414.337 65.0 0 5534.0 60 +37 504.648 -448.192 93.0 0 5463.0 60 +38 603.623 -399.281 38.0 0 5554.0 60 +39 486.926 -421.798 14.0 0 5680.0 60 +40 557.648 -554.124 63.0 0 5345.0 60 +41 460.607 -352.153 93.0 0 5614.0 60 +42 321.0 -176.067 5.0 0 5365.0 60 +43 311.871 -123.91 0.0 0 0.0 60 +44 299.85 -208.375 0.0 0 0.0 60 +45 309.412 -99.408 0.0 0 0.0 60 +46 339.076 -107.497 0.0 0 0.0 60 +47 323.166 -294.458 0.0 0 0.0 60 +48 361.339 -330.367 0.0 0 0.0 60 +49 409.879 -359.488 0.0 0 0.0 60 +50 354.896 -218.536 0.0 0 0.0 60 +51 329.603 -189.758 78.0 0 5642.0 60 +52 342.105 -178.702 6.0 0 5331.0 60 +53 -112.919 491.724 28.0 0 5743.0 60 +54 -165.35 543.615 90.0 0 5745.0 60 +55 -123.99 576.033 83.0 0 5509.0 60 +56 -180.108 609.831 29.0 0 5731.0 60 +57 -197.274 520.369 36.0 0 5533.0 60 +58 -198.796 630.316 37.0 0 5305.0 60 +59 -165.53 596.714 84.0 0 5700.0 60 +60 -197.63 704.655 99.0 0 5679.0 60 +61 -219.552 767.208 0.0 0 0.0 60 +62 -126.759 523.712 0.0 0 0.0 60 +63 -202.479 561.031 0.0 0 0.0 60 +64 -199.359 547.922 0.0 0 0.0 60 +65 -212.815 602.652 0.0 0 0.0 60 +66 -12.252 -1.604 0.0 0 0.0 60 +67 594.559 -208.3 0.0 0 0.0 60 +68 542.821 -158.528 0.0 0 0.0 60 +69 564.253 -141.866 0.0 0 0.0 60 +70 622.521 -241.407 0.0 0 0.0 60 +71 645.375 -247.639 0.0 0 0.0 60 +72 550.239 -267.34 50.0 0 5319.0 60 +73 561.727 -163.544 80.0 0 5517.0 60 +74 624.65 -305.475 3.0 0 5323.0 60 +75 482.321 -90.891 89.0 0 5413.0 60 +76 576.329 -190.744 75.0 0 5567.0 60 +77 604.208 -141.427 22.0 0 5417.0 60 +78 600.999 -182.575 5.0 0 5255.0 60 +79 546.468 -140.107 14.0 0 5309.0 60 +80 273.463 -88.779 0.0 0 0.0 60 +81 257.077 -104.204 0.0 0 0.0 60 +82 190.293 -137.595 0.0 0 0.0 60 +83 293.881 -77.096 0.0 0 0.0 60 +84 228.772 -82.426 0.0 0 0.0 60 +85 186.521 -173.297 0.0 0 0.0 60 +86 240.412 -39.238 0.0 0 0.0 60 +87 91.851 213.126 0.0 0 0.0 60 +88 25.485 246.562 0.0 0 0.0 60 +89 8.66 334.48 0.0 0 0.0 60 +90 23.898 277.533 0.0 0 0.0 60 +91 87.939 235.33 0.0 0 0.0 60 +92 44.354 218.816 0.0 0 0.0 60 +93 114.554 305.512 0.0 0 0.0 60 +94 -13.216 382.68 53.0 0 5712.0 60 +95 115.22 238.896 22.0 0 5395.0 60 +96 229.568 296.508 77.0 0 5665.0 60 +97 46.936 243.203 54.0 0 5696.0 60 +98 99.841 -152.523 21.0 0 5565.0 60 +99 144.697 -224.393 9.0 0 5297.0 60 +100 232.781 -309.304 99.0 0 5739.0 60 +101 205.195 -276.634 98.0 0 5309.0 60 +102 91.99 -185.026 93.0 0 5451.0 60 +103 189.286 110.076 4.0 0 5417.0 60 +104 193.799 -1.756 10.0 0 5671.0 60 +105 190.981 14.173 0.0 0 0.0 60 +106 202.424 -2.451 0.0 0 0.0 60 +107 170.125 30.101 0.0 0 0.0 60 +108 115.356 98.394 0.0 0 0.0 60 +109 266.144 88.068 0.0 0 0.0 60 +110 149.304 69.608 0.0 0 0.0 60 +111 125.701 58.858 0.0 0 0.0 60 +112 -230.954 481.711 0.0 0 0.0 60 +113 -74.739 543.971 0.0 0 0.0 60 +114 -266.772 535.807 0.0 0 0.0 60 +115 -198.92 507.768 0.0 0 0.0 60 +116 -161.915 445.157 0.0 0 0.0 60 +117 -170.707 460.727 0.0 0 0.0 60 +118 -275.072 513.038 0.0 0 0.0 60 +119 -29.558 419.203 69.0 0 5292.0 60 +120 -113.211 470.395 57.0 0 5508.0 60 +121 -127.071 433.722 17.0 0 5500.0 60 +122 -222.189 437.458 0.0 0 8000.0 60 +123 -191.447 403.82 16.0 0 5651.0 60 +124 -312.254 586.488 99.0 0 5740.0 60 +125 -306.625 601.197 63.0 0 5697.0 60 +126 -319.765 593.982 0.0 0 0.0 60 +127 -81.206 143.652 0.0 0 0.0 60 +128 71.506 -114.734 0.0 0 0.0 60 +129 4.169 174.936 0.0 0 0.0 60 +130 45.118 64.371 0.0 0 0.0 60 +131 -19.647 61.214 87.0 0 5459.0 60 +132 71.658 22.367 22.0 0 5530.0 60 +133 -64.483 104.23 67.0 0 5743.0 60 +134 0.0 0.0 0.0 0 8000.0 60 +135 28.625 153.206 30.0 0 5463.0 60 +136 123.627 -46.014 67.0 0 5338.0 60 +137 102.977 683.921 76.0 0 5640.0 60 +138 52.927 802.199 16.0 0 5410.0 60 +139 384.183 838.332 26.0 0 5658.0 60 +140 724.291 905.119 39.0 0 5688.0 60 +141 420.998 922.537 35.0 0 5563.0 60 +142 485.059 1067.329 16.0 0 5259.0 60 +143 352.945 776.388 0.0 0 0.0 60 +144 224.773 522.105 0.0 0 0.0 60 +145 630.652 -87.873 0.0 0 0.0 60 +146 828.745 122.423 0.0 0 0.0 60 +147 873.352 -60.968 0.0 0 0.0 60 +148 673.89 -514.611 0.0 0 0.0 60 +149 632.164 -622.681 0.0 0 0.0 60 +150 677.822 -572.419 0.0 0 0.0 60 +151 57.14 172.862 0.0 0 0.0 60 +152 180.789 163.639 0.0 0 0.0 60 +153 86.1 151.476 0.0 0 0.0 60 +154 -298.529 823.476 0.0 0 0.0 60 +155 -269.106 756.895 0.0 0 0.0 60 +156 -348.08 772.735 0.0 0 0.0 60 +157 -454.028 774.005 0.0 0 0.0 60 +158 -399.863 761.547 0.0 0 0.0 60 +159 -421.627 721.474 0.0 0 0.0 60 +160 -406.627 795.697 0.0 0 0.0 60 +161 -471.614 830.207 0.0 0 0.0 60 +162 760.034 -318.307 75.0 0 5377.0 60 +163 733.791 -224.895 2.0 0 5394.0 60 +164 841.886 -463.394 47.0 0 5685.0 60 +165 821.941 -449.333 63.0 0 5406.0 60 +166 808.282 -351.175 82.0 0 5678.0 60 +167 740.886 -369.029 97.0 0 5281.0 60 +168 716.14 -315.339 65.0 0 5749.0 60 +169 837.365 -368.588 38.0 0 5406.0 60 +170 778.641 -421.951 0.0 0 0.0 60 +171 796.371 -318.934 0.0 0 0.0 60 +172 766.684 -383.324 0.0 0 0.0 60 +173 841.065 -253.202 0.0 0 0.0 60 +174 882.657 -466.835 0.0 0 0.0 60 +175 49.57 553.645 0.0 0 0.0 60 +176 37.32 604.011 0.0 0 0.0 60 +177 28.76 568.151 0.0 0 0.0 60 +178 57.189 625.369 0.0 0 0.0 60 +179 33.809 541.02 0.0 0 0.0 60 +180 6.208 668.421 76.0 0 5514.0 60 +181 77.858 569.905 50.0 0 5491.0 60 +182 -15.264 665.314 65.0 0 5388.0 60 +183 74.576 618.044 79.0 0 5373.0 60 +184 57.842 428.909 13.0 0 5600.0 60 +185 753.912 -580.69 99.0 0 5371.0 60 +186 696.981 -619.124 74.0 0 5339.0 60 +187 753.868 -663.587 0.0 0 0.0 60 +188 778.184 -603.655 0.0 0 0.0 60 +189 -405.393 930.174 0.0 0 0.0 60 +190 -381.296 942.387 0.0 0 0.0 60 +191 -360.775 950.187 0.0 0 0.0 60 +192 364.237 146.354 0.0 0 0.0 60 +193 277.793 407.271 0.0 0 0.0 60 +194 169.224 334.59 29.0 0 5633.0 60 +195 702.797 252.808 2.0 0 5718.0 60 -- cgit v1.2.3