原文：Computing optimal road trips on a limited budget
大约一年前，我写了一篇文章来介绍使用遗传算法和谷歌地图组合进行公路旅行优化。在那段时间里，我考虑了如何才能让那个算法对那些正在计划夏天公路旅行的人更有用。
让我吃惊的一个想法是，我之前创建的公路旅行是相当宏伟的 —— 跨越整个国家，甚至欧洲大部分地区 —— 以至于对于那些只有一些积蓄，并有一个月假的人来说，甚至会希望去其中给一个旅行。在现实中，我们大多数人对于我们的公路旅行会有预算限制：我们只能花那么多钱，或者我们只有这么多时间，然后就要回去工作。
在这篇文章中，我将通过引入多目标Pareto优化到算法中，以扩展优化公路旅行的想法。我将简要介绍Pareto优化是如何工作的，以及它如何帮助我们在有限的预算内优化公路旅行。
注意：如果你对该项目的技术细节不感兴趣，那么直接跳到在8天半中的1/248个美国州议会大厦章节。
对于这次公路旅行，有一个目标：尽可能拍下尽可能多的美国州议会大厦的照片。（额外的收获是旅行或者主题照片！）
我们将仅通过汽车旅行，因此排除了Alaska(太远)以及Hawaii(需要搭飞机)，于是剩下48个州（不包括D.C.）。
只要有可能，我们会避免需要途经国外的路线，因为入境/出境需要一本护照，而边境管制往往会拖延时间。
最后，澄清一下：我们的目标是参观_议会大厦_，而不是建筑所在的城市（例如，州的首府）。也就是说，在这个公路之旅中，我们是冲着史诗般的旅程和一些美丽的建筑去的。
图片来源：Daniel Mennerich
掌握了美国各州议会大厦的列表，下一步是要找到所有议会大厦之间乘坐汽车的“真实”距离。由于我们不能在任意国会大厦之间直线驾驶 —— 驾驶汽车有这种讨厌的限制，也就是我们必须停在路上 —— 我们需要找到任意国会大厦之间_通过公路_的最短路线。
如果你曾经使用谷歌地图获取两个地址之间的方向，那么这基本就是这里我们要做的事情。除了这次，我们需要查询2,256个方向，已获取所有48个州议会大厦之间的“真实”距离 —— 如果我们要手工完成，这将是一个艰巨的任务。谢天谢地，Google Maps API使得这些信息免费提供，因此，所需要的仅是一个简短的Python脚本，它计算48个议会大厦之间驾驶汽车的所有2,256个路线的距离和时间。
现在，有了2,256个议会大厦-议会大厦距离，我们下一步是将这项任务当成旅行商问题：我们需要对议会大厦列表进行排序，使得如果我们按顺序参观，那么它们之间旅行的总距离尽可能的小。这意味着，发现尽可能少回溯的路线，这在参观Florida和东北时会特别困难。
如果你读过我的_Waldo在哪里？_一文，那么你已经知道了要解决像这样的路径优化问题会有多难。将48个路标按序排放，我们将不得不彻底评估1.24 x 1061种可能的路线以找到最短的那一个。
提供一些背景：如果你现在立刻开始在你的家用电脑上计算这个问题，那么你将会在大约3.98 x 1049年内找到这个最佳路径 —— 那个时候，太阳早已进入红巨星阶段并吞噬地球。这种复杂性就是为嘛谷歌地图的路径优化服务只优化至多10个航点的路径，而最好的免费路径优化服务只优化20个航点，除非你付给他们很多钱，让他们用一些更大的计算机来计算。
旅行商问题是如此出了名的难以解决，甚至xkcd对它开起了玩笑：
显然，如果我们要在我们的有生之年进行这个公路旅行，那么我们需要一个更聪明的解决方案。值得庆幸的是，旅行商问题多年来已经得到了充分研究，因此我们有许多种办法，在一个合理的时间量内解决它。
如果我们愿意降低要求，接收不需要所有的议会大厦之间的_绝对最佳_路线，那么我们可以转向诸如遗传算法这种更智能的技术，以找到一个对我们足够好的方案。遗传算法开始于少数随机解决方案，并持续修补这些方案，而不是彻底的寻找每一个可能的解决方法。该算法总是尝试与当前的方法稍微不同的方法，从而保持最佳的方法，直到它们再也无法找到一个更好的为止。
下面，我已经包含了遗传算法优化的一个公路旅行的可视化版本。
通常在优化问题中，我们想要最大化或最小化一个标准：最大化我们赚了多少钱，或者最小化发生事故的概率。在多目标Pareto优化中，我们可以_同时_优化多个标准 —— 例如，最大化我们要参观的州，同时最小化我们花在路上的总时间。
在下面的图中，每个点对应一个公路旅行。看看遗传算法同时优化48个公路旅行。
Pareto最优特别有用的是，在优化过程的最后，我们有一个_Pareto前端_可供选择，其中列出我们正在努力优化路线之间的取舍。在上图中，我们看到，我们参观的州越多，行程需要越长。如果我们的旅程只有两天，例如，Pareto前端提供了繁多的行程可供选择：也许我们应该只访问只少数议会大厦，留有充足的时间去探索它们，或许我们应该尽可能在2天内访问尽可能多的议会大厦。选择权在我们手上。
在下面的动画图中，我已经从Pareto优化过程中看到了全部48种优化路线。注意，每个路线之间稍有不同，例如，参观7个议会大厦的优化路线是与参观8个议会大厦的优化路线大大不同的。
在我的笔记本电脑上运行约20分钟后，遗传算法达到最优解决方案，使得仅需驾驶13,310英里（21,420公里）就能参观所有的美国州议会大厦。我在下面绘制了路线。
点击这里，活动该地图的交互式版本
假设没有交通，这个公路之旅将需要大约8天半的总驾驶时间，所以你最好带上一个大水瓶。最棒的是，这个公路之旅的设计让你可以在路线上的任何地方开始你的旅程：只要你按照你从任何地方开始的路线，你将会采访美国48个州中的每一个州议会大厦，并且作为补充奖励，你甚至可以添加华盛顿特区到路线而无需任何额外英里。
下面是按顺序排列的议会大厦完整列表：（Ele注：好长的地名，我就不翻了，保持原样吧）
- State House, 107 North Main Street, Concord, NH 03303
- Maine State House, Augusta, ME 04330
- Vermont State House, 115 State Street, Montpelier, VT 05633
- New York State Capitol, State St. and Washington Ave, Albany, NY 12224
- New Jersey State House, Trenton, NJ 08608
- Pennsylvania State Capitol Building, North 3rd Street, Harrisburg, PA 17120
- West Virginia State Capitol, Charleston, WV 25317
- Ohio State Capitol, 1 Capitol Square, Columbus, OH 43215
- Kentucky State Capitol Building, 700 Capitol Avenue, Frankfort, KY 40601
- Tennessee State Capitol, 600 Charlotte Avenue, Nashville, TN 37243
- Indiana State Capitol, Indianapolis, IN 46204
- Michigan State Capitol, Lansing, MI 48933
- Illinois State Capitol, Springfield, IL 62756
- 2 E Main St, Madison, WI 53703
- Minnesota State Capitol, St Paul, MN 55155
- 500 E Capitol Ave, Pierre, SD 57501
- North Dakota State Capitol, Bismarck, ND 58501
- Montana State Capitol, 1301 E 6th Ave, Helena, MT 59601
- Washington State Capitol Bldg, 416 Sid Snyder Ave SW, Olympia, WA 98504
- Oregon State Capitol, 900 Court St NE, Salem, OR 97301
- L St & 10th St, Sacramento, CA 95814
- Nevada State Capitol, Carson City, NV 89701
- 700 W Jefferson St, Boise, ID 83720
- Utah State Capitol, Salt Lake City, UT 84103
- Wyoming State Capitol, Cheyenne, WY 82001
- 200 E Colfax Ave, Denver, CO 80203
- New Mexico State Capitol, Santa Fe, NM 87501
- Arizona State Capitol, 1700 W Washington St, Phoenix, AZ 85007
- Texas Capitol, 1100 Congress Avenue, Austin, TX 78701
- Oklahoma State Capitol, Oklahoma City, OK 73105
- 300 SW 10th Ave, Topeka, KS 66612
- Nebraska State Capitol, 1445 K Street, Lincoln, NE 68509
- Iowa State Capitol, 1007 E Grand Ave, Des Moines, IA 50319
- Missouri State Capitol, Jefferson City, MO 65101
- Arkansas State Capitol, 500 Woodlane Street, Little Rock, AR 72201
- 400-498 N West St, Jackson, MS 39201
- Louisiana State Capitol, Baton Rouge, LA 70802
- 402 S Monroe St, Tallahassee, FL 32301
- Alabama State Capitol, 600 Dexter Avenue, Montgomery, AL 36130
- Georgia State Capitol, Atlanta, GA 30334
- South Carolina State House, 1100 Gervais Street, Columbia, SC 29201
- North Carolina State Capitol, Raleigh, NC 27601
- Virginia State Capitol, Richmond, VA 23219
- Maryland State House, 100 State Cir, Annapolis, MD 21401
- Legislative Hall: The State Capitol, Legislative Avenue, Dover, DE 19901
- Connecticut State Capitol, 210 Capitol Ave, Hartford, CT 06106
- Rhode Island State House, 82 Smith Street, Providence, RI 02903
- Massachusetts State House, Boston, MA 02108
(注意，谷歌地图自身一次只允许路由10个航点，这就是为嘛有多个地图链接。)
在这一点上，有些人可能会抓抓脑袋。“Randy，你不是答应停止向我们展示_宏伟的_公路旅行吗？”，我想像着你这样想。
这就是Pareto优化的用武之地：如果我们看看最后的Pareto前端，我们不是一定要挑选那个48个州的公路旅行的。我们有全_范围_的公路旅行可供选择。
比方说，例如，我们只有24小时可以全身心地投入到公路之旅中。如果是这样的话，那么我们可以看看前面的Pareto前端，然后看到我们可以参观10个州议会大厦，并在不到24小时内回家。想到我们能在一个早晨离开，访问10个州的议会大厦，然后回来开始第二天的早餐，这岂不是很不可思议？
如你所料，这个公路之旅在美国东北部：
这里是这个24小时公路之旅的谷歌地图：[1]
如果你想在Pareto前端看看其他公路旅行，我已经将它们上传到GitHub上了。
从理论上讲，我们可以扩展这个想法到各种预算。如果我们只有100美刀的油钱，那么我们可以增加燃气费到Pareto前端。如果我们平均每天花在酒店的预算只有50美刀，那么我们可以添加每一站的酒店平均成本到Pareto前端。诸如此类。此时，唯一的限制就是你的想象力。
如果你受这篇文章启发，想制作自己的公路旅行，那么我已经发布了在这个项目中使用的Python代码，它带有开放源码许可和如何优化你的自定义公路旅行的说明。你可以在这里找到代码。
你还应该看看Nathan Brixius使用运筹学技术解决这个挑战的方法。Nathan人超好，他分享了他所有的Python代码。
注意：我不受理定制公路旅行的请求；我根本没时间。但是，如果你有一个可能对很多人来说很好玩的简洁公路旅行的想法，请随时发邮件告诉我你的想法。
我想起了引述：
世界犹如一本书，而那些从不出门旅行的人仅仅读了这本书的一页。(The world is a book, and those who do not travel read only one page.)
我希望这篇文章 —— 通过旅行、机器学习和可视化的奇怪混杂 —— 启发你走出去，开始你自己的公路旅行。无聊它是一次计算机在几分钟内优化的旅行，还是一次你花费了几个星期手工设计的旅程，重要的是，你旅行并从一个全新的视角体验了这个世界。
玩得开心!