、旅行商問題（Traveling Salesman Problem, TSP）
這個問題字面上的理解是：有一個推銷員，要到n個城市推銷商品，他要找出一個包含所有n個城市的具有最短路程的環(huán)路。
TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周游問題，即對于國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，并且最終返回到起始點。
TSP由美國RAND公司于1948年引入，該公司的聲譽(yù)以及線性規(guī)劃這一新方法的出現(xiàn)使得TSP成為一個知名且流行的問題。
2、中國郵遞員問題（Chinese Postman Problem CPP）
同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發(fā)，到所轄街道投遞郵件，最后返回郵局，如果他必須走遍所轄的每條街道至少一次，那么他應(yīng)如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題， 因為是我國學(xué)者管梅古谷教授于1962年提出的這個問題并且給出了一個解法。
3、“一筆畫”問題（Drawing by one line）
還有一個用圖論語言的描述方式：平面上有n個點，用最短的線將全部的點連起來。稱為“一筆畫”問題。
4、配送路線問題（Route of Distribution）
TSP問題在物流中的描述是對應(yīng)一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。
TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨于無窮大的復(fù)雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）！。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達(dá)到山頂或谷底的過程。
5、多回路運輸問題（Vehicle Routing Problem, VRP）
多回路運輸問題在物流中的解釋是對一系列客戶的需求點設(shè)計適當(dāng)?shù)穆肪€，使車輛有序地通過它們，在滿足一定的約束條件下，如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛載重量限制、行駛里程限制、時間限制等等，達(dá)到一定的優(yōu)化目標(biāo)，如里程最短、費用最少、時間最短，車隊規(guī)模最少、車輛利用率高。
VRP問題和TSP問題的區(qū)別在于：客戶群體的數(shù)量大，只有一輛車或一條路徑滿足不了客戶的需求，必須是多輛交通工具以及運輸工具的行車順序兩個問題的求解。相對于TSP問題，VRP問題更復(fù)雜，求解更困難，但也更接近實際情況。
6、多個旅行商問題（Multiple TSP）
由于限制條件的增加，TSP問題可以衍生出多個旅行商問題（MTSP），就是一個出發(fā)點，m個旅行商的TSP，即所訪問的客戶沒有需求，車輛沒有裝載的限制，優(yōu)化目標(biāo)就是要遍歷所有的客戶，達(dá)到總里程最短。
VRP問題是MTSP問題的普遍化，當(dāng)客戶的需求不僅僅是被訪問，而是有一定容積和重量的商品的裝載和卸載，涉及到不同種類和型號或不同載重量車輛的調(diào)度策略時，MTSP問題轉(zhuǎn)換為VRP問題。
7、最近鄰點法（Nearest Neighbor）
這是一種用于解決TSP問題的啟發(fā)式算法。方法簡單，但得到的解并不十分理想，可以作為進(jìn)一步優(yōu)化的初始解。求解的過程一共四步：首先從零點開始，作為整個回路的起點，然后找到離剛剛加入到回路的上一節(jié)點最近的一個節(jié)點，并將其加入到回路中。重復(fù)上一步，直到所有的節(jié)點都加入到回路中，最后，將最后一個加入的節(jié)點和起點連接起來，構(gòu)成了一個TSP問題的解。
8、最近插入法（Nearest Insertion）
最近插入法是另一個TSP問題的求解方法。它的求解過程也是4步：首先從一個節(jié)點出發(fā)，找到一個最近的節(jié)點，形成一個往返式子回路；在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點，再在子回路中找到一個弧，使弧的兩端節(jié)點到剛尋找到的最近節(jié)點的距離之和減去弧長的值最小，實際上就是把新找到的節(jié)點加入子回路以后使得增加的路程最短，就把這個節(jié)點增加到子回路中。重復(fù)以上過程，直到所有的節(jié)點都加入到子回路中。最近插入法比最近鄰點法復(fù)雜，但可以得到相對比較滿意的解。
9、節(jié)約里程法（Saving Algorithm）
節(jié)約算法是用來解決運輸車輛數(shù)目不確定的VRP問題的最有名的啟發(fā)式算法。它的核心思想是依次將運輸問題中的兩個回路合并為一個回路，每次使合并后的總運輸距離減小得幅度最大，直到達(dá)到一輛車的裝載限制時，再進(jìn)行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種。
10、掃描算法（Sweep Algorithm）
它也是求解車輛數(shù)目不限制的VRP問題的啟發(fā)式算法。求解過程同樣是4步：以起始點為原點建立極坐標(biāo)系，然后從最小角度的兩個客戶開始建立一個組，按逆時針方向?qū)⒖蛻糁饌€加入到組中，直到客戶的需求總量超出了車輛的載重定額。然后建立一個新的組，繼續(xù)該過程，直到將全部客戶都加入到組中