“机智”的快递员
文章来源：计算机科学国家重点实验室 雷震东 傅英杰 蔡少伟 | 发布时间：2018-12-24 | 【打印】 【关闭】
我叫小徐，生活在中关村地区的小伙伴们也许不熟悉我的名字， 但你们一定熟悉我的三轮小货车吧！对，就是那辆每天风雨无阻地为你们送来新快递的小货车啊！作为一名快递员，我每天的工作就是穿梭在辖区的各个派送点之间，把当天的快递按时送到你们手中。所以我说，我不是在送快递，就是在送快递的路上。
然而最近天气越来越冷，送快递的路上已经刮起了冻人的寒风。所以我决定好好规划一下每天送快递的路线，先给谁送，然后再给谁送。我要好好的计划一下，这样才能让自己每天穿梭的路程少一些。这样省时，省油，还省得挨冻。
首先，我每天从配送站出发，辖区内的每个派送点都要送到，当然，已经去过的地方就不用再去了。最后，快递都派送完以后，我还得回到配送站。考虑到特定时段有些方向的交通会非常不方便，我决定在设计路线的时候不只使用路程，而是使用代价。代价综合体现了路程、路况等因素，路程长，路况差的路线代价也会大。
下面我就会给大家举一个简单的例子，然后让大家来理解为什么要规划自己的出行路线。在这个简单的例子里面我只需要去送三个包裹，但是实际上我每天要送成百上千个包裹呢！
如果用A,B,C,D 来表示我每天需要经过的地点。其中 A 为配送站，
B,C,D 都是派送点，各个地点之间的距离如上表所示。
|
|
到达A |
到达B |
到达C |
到达D |
|
(配送站)A |
0 |
6 |
7 |
5 |
|
B 出发 |
8 |
0 |
9 |
7 |
|
C 出发 |
5 |
8 |
0 |
8 |
|
D 出发 |
6 |
5 |
5 |
0 |
我想要确定一条路线，从 A(配送站)出发走遍所有的点，然后回到配送站，保证除了配送站之外的点都只走了一遍。应该要怎么做呢？ 最简单的做法是按照 A-B-C-D -A 的顺序走，这样我一天需要的总路程为：
6+9+8+6=29
我感觉这条路线可能不是很合理，我想要走一条更加合理的路线， 这样能使我的总路程变小，我可以更早的回到配送站然后回家！于是， 为了更快地把所有的包裹送到客户手里，我设计了一个巧妙的算法来帮我改进当前的路线，这个算法的思想很简单：
我先随便想到一个路线方案，比如上面的路线方案： A->B->C->D->A。接下来我每次通过一个很简单的操作来缩短我的 路线。这个操作就是，我任意交换两个点（除了出发点 A 之外）的次序，来看看我的总路程是不是减少了。如果减少了呢，我就留下这个
新的路线方案，否则呢，我就尝试其他点的交换方式。
例如：当前路线方案是：A->B->C->D->A
如果交换B 和C， A->C->B->D->A 总的路程变为： 7+8+7+6=28
我发现路线总路程变少了，那我就决定先留着这个新的方案啦！ A->C->B->D->A。
因为B 和C 刚刚交换过，所以我暂时不会再交换他们两个了。我会尝试其他的交换组合。比如交换 C 和 D。如果交换后的路程是A->D->B->C->A：
5+5+9+5=24
注意哦，在当前情况下，我已经比一开始随便选择的路线整整少了5km 的距离。可以大大的减少我的送快递的时间了，可以更早得回家啦！
我可以一直这样尝试改进自己的路线规划，直到时间快到了，就这样，我每天走的路程就会变的很少很少，我就可以更早的把所有的包裹送到，然后更早的完成任务，下班回家休息啦！
这其实就是算法哦，以上的路线规划过程就是局部搜索算法的一个例子。算法存在我们生活的方方面面，它们的作用就是帮助我们更好更快的完成我们的任务，所以我们也需要设计很好的算法来改善我们的生活。
