“機智”的快遞員
文章來源：計算機科學國家重點實驗室 雷震東 傅英杰 蔡少偉 | 發布時間：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 的距離。可以大大的減少我的送快遞的時間了，可以更早得回家啦！
我可以一直這樣嘗試改進自己的路線規劃，直到時間快到了，就這樣，我每天走的路程就會變的很少很少，我就可以更早的把所有的包裹送到，然后更早的完成任務，下班回家休息啦！
這其實就是算法哦，以上的路線規劃過程就是局部搜索算法的一個例子。算法存在我們生活的方方面面，它們的作用就是幫助我們更好更快的完成我們的任務，所以我們也需要設計很好的算法來改善我們的生活。
