【正文】 問所有城市。TSP一般描述為:旅行商從駐地出發(fā)，經(jīng)所要去的城市至少一次后返回原地，應(yīng)如何安排其旅行線路，才能使總的旅行距離(或時間、費用等)最少。（三）旅行商問題問題概述 旅行商問題(Traveling Salesman Problem，簡稱TSP)是運籌學(xué)、圖論以及組合優(yōu)化中的著名難題，由于其有廣泛的應(yīng)用背景，引起了人們的極大興趣。由此可見，求解最短路意義是很重大的。最短路在物流運輸、配送活動中的意義是不言而喻的，一般情況下，最短路的權(quán)重是以―對之間的距離、車輛行駛時間、費用來表示。另外，諸如運價最小、運行時間最短、最可靠路等問題，都可以轉(zhuǎn)化為最短路問題加以解決[7]。這里的權(quán)在不同的情況下具有不同的含義，它可以表示距離，也可以表示時間，甚至還可以表示費用。這時，可給圖中的反映聯(lián)系的邊賦一數(shù)值，稱為權(quán)，來表明一定的含義，一般標(biāo)在邊上。無向圖中兩個方向均可以通過，但有向圖中只能沿著箭頭方向通過。有向圖是點與弧的集合，記作={,}。有向圖上的連線是有規(guī)定指向的，稱作弧。上面定義的圖 區(qū)別于幾何學(xué)中的圖。這里的點不是真正的幾何點，它只是某種事物的一種抽象，連線也不是幾何中的線段，而是代表某些事物之間的關(guān)系[6]，因此點與連線的畫法具有隨意性。這里所研究的圖是反映實際生活中某些對象之間某種特定關(guān)系的一種工具。四、基本問題（一）圖的基本概念在生產(chǎn)和日常生活中，人們常常用點和線畫出的示意圖來反映一些對象之間的關(guān)系。比如，在運輸過程中，一味的追求成本最小化，就會出現(xiàn)一些不應(yīng)出現(xiàn)的情形，超載運輸是最常見的一種，運輸安全受到比較大的威脅。(9)物流車輛調(diào)度觀念的落后并且缺乏相應(yīng)的人才。(8)一些融入當(dāng)今先進(jìn)的數(shù)字移動通信技術(shù)、計算機實時信息處理技術(shù)、全球衛(wèi)星定位系統(tǒng)(GPS)、地理信息系統(tǒng)(GIS)、數(shù)據(jù)庫處理技術(shù)于一體的比較先進(jìn)的車輛調(diào)度系統(tǒng)己經(jīng)開始運用在120救護(hù)車調(diào)度、城市出租車調(diào)度等。由于我國物流企業(yè)總體上信息化起步較晚，信息化程度較低，對企業(yè)信息化存在著許多分歧，不少物流企業(yè)還處在電話聯(lián)系、手工操作、人工裝卸的低級階段，并且信息化建設(shè)的難度也比較大。物流企業(yè)屬于資金密集型企業(yè)，其投資資金大多用于車場的建設(shè)、車輛的購買、倉庫的建設(shè)等大規(guī)模資金投資的基礎(chǔ)項目建設(shè)，這也導(dǎo)致現(xiàn)行的調(diào)度模式還是基于電話、傳統(tǒng)倉庫、人力搬運設(shè)備的等傳統(tǒng)設(shè)備，車輛調(diào)度工作效率的提升空間便受到了限制。服務(wù)于城市集貨和城市配送工作的車輛來自社會，車型五花八門，每輛車的新舊程度、載重噸位、單位油耗等參數(shù)都不盡相同，但是在具體的車輛調(diào)度過程中，很少考慮到那種車型更適合于什么貨物、什么路線的運輸。但是在實際工作中，由于每次分配給每個司機的任務(wù)一般都在5個以上，等司機完成這些任務(wù)后，時間己經(jīng)不應(yīng)許司機再去完成其他的運輸任務(wù)。(4)集貨過程與送貨過程相互脫離，這導(dǎo)致物流企業(yè)運作成本增加，并且物流企業(yè)對所掌握的資源利用率降低。在上節(jié)所分析的現(xiàn)行的車輛調(diào)度過程，不論是集貨過程還是送貨過程，物流企業(yè)的調(diào)度管理員只對駕駛員分配和安排任務(wù)，具體的路徑選擇由駕駛員根據(jù)自己的偏好進(jìn)行選擇，這就可能會導(dǎo)致一系列不良的后果。因為物流企業(yè)對駕駛員的管理一般基于任務(wù)管理，即根據(jù)駕駛員每天完成的任務(wù)，物流企業(yè)給他相對應(yīng)于任務(wù)的報酬，但是駕駛員在服務(wù)過程中物流企業(yè)卻沒有能力去進(jìn)行管理。例如顧客大部分時候?qū)r間的要求彈性很大，物流企業(yè)有充分的時間來完成顧客的需求服務(wù)，所以時間因素很多時候并不是物流企業(yè)首要考慮的問題，而考慮最多的是經(jīng)濟(jì)因素。這種基于經(jīng)驗的傳統(tǒng)調(diào)度模式存在著以下一些問題:(1)我國物流實際與理論研究差距很大，限制了充分發(fā)揮物流車輛調(diào)度的功能和優(yōu)勢。一旦正常的秩序被打亂，那么就會影響到物流企業(yè)的經(jīng)營效益和該企業(yè)在顧客心中的信心。由于沒有一套規(guī)范的、完整的、科學(xué)的理論進(jìn)行指導(dǎo)，當(dāng)出現(xiàn)突發(fā)情況，正常的秩序較容易被打破，現(xiàn)場調(diào)度就可能出現(xiàn)問題。（二）物流車輛調(diào)度存在問題分析上節(jié)所描述的基于經(jīng)驗的車輛調(diào)度模式，基于傳統(tǒng)設(shè)備和調(diào)度員、駕駛員經(jīng)驗。對于貴重品，則會選擇即安全又快捷的路徑，使得貴重物品最先卸載。ⅳ)貨物種類因素:對不同的貨物，可能會選擇出不同的路徑。ⅱ)時間因素:在顧客規(guī)定的時間內(nèi)把貨物送達(dá)口但是我國的物流需求大多屬于低端的物流需求，很多情況下，顧客對時間的要求并不是那么嚴(yán)格。從上述所說的物流車輛調(diào)度過程，我們可以知道，這些物流企業(yè)中的車輛調(diào)度其實只分配了運輸任務(wù)，對行駛路徑?jīng)]有做規(guī)定。在第二類車輛中，物流公司又把它們分為4個組，分別負(fù)責(zé)來自周邊4個地區(qū)的貨物的配送任務(wù)。第一類車輛由于運輸距離遠(yuǎn)、載重噸位大、購買費用高，所以這一部分車輛大多屬于公司的固定資產(chǎn)。(4)送貨過程:物流公司把專門用來負(fù)責(zé)送貨的車輛分為兩種，第一種為長途送貨車輛。(3)貨物的存放:貨物被送到公司所屬的倉庫后，根據(jù)貨物的去向和出貨的先后順序存放于倉庫中。對于另一部分貨物而言，物流公司調(diào)度管理人員就會及時與收貨人進(jìn)行聯(lián)系，確認(rèn)交貨的時間和地點。當(dāng)顧客向該物流公司提出運輸需求時，調(diào)度管理人員便電話通知相應(yīng)的車主，之后車主便去完成相應(yīng)的任務(wù)。所以，調(diào)度決策者只對駕駛員分配和安排調(diào)度任務(wù)，對路徑的選擇很多情況下都由司機憑經(jīng)驗做出選擇。但是目前，我國貨物運輸車輛調(diào)度方法比較落后，多采用傳統(tǒng)的人工方法編制調(diào)度方案。在規(guī)劃配送路線時，回程路線應(yīng)當(dāng)盡量縮短；在進(jìn)行穩(wěn)定的、計劃配送時，回程車輛可將包裝物、廢棄物、殘次品運回集中處理，或者將用戶的產(chǎn)品運回配送中心，作為配送中心的資源，向其他用戶進(jìn)行配送。配送加工是流通加工的一種，但配送加工有它不同于一般流通加工的特點，即配送加工一般只取決于特殊用戶要求，其加工的目的較為單一。 (7)配送加工在配送中，配送加工這一功能要素不具有普遍性，但是往往是有重要作用的功能要素。因此，要圓滿地實現(xiàn)運到交貨的移交，并有效地、方便地處理相關(guān)手續(xù)并完成結(jié)算，還應(yīng)講究卸貨地點、卸貨方式等。與干線運輸?shù)牧硪粋€區(qū)別是，配送運輸路線選擇問題是一般干線運輸所沒有的，干線運輸?shù)母删€是惟一的運輸線，而配送運輸由于配送用戶多，一般城市交通路線又較復(fù)雜，如何組成最佳路線，如何使配裝和路線有效搭配等，是配送運輸?shù)奶攸c，也是難度較大的工作。和一般送貨不同之處在于，通過配裝可以大大提高送貨水平及降低送貨成本，所以配裝也是配送系統(tǒng)中有現(xiàn)代特點的功能要素，是現(xiàn)代配送不同于傳統(tǒng)送貨的重要區(qū)別之處。有了分揀及配貨，就會大大提高送貨服務(wù)水平，所以，分揀及配貨是決定配送系統(tǒng)水平的關(guān)鍵要素。(3) 分揀及配貨這是配送不同于其他物流形式的有特點的功能要素，也是配送成敗的一項重要支持性工作。由于總體儲存效益取決于儲存總量，所以這部分暫存數(shù)量只會對工作方便與否造成影響，而不會影響儲存的總效益，因而在數(shù)量上控制并不嚴(yán)格。配送的儲備保證有時在配送中心附近單獨設(shè)庫解決。(2)儲存配送中的儲存有儲備及暫存兩種形態(tài):ⅰ)儲備 配送儲備是按一定時期的配送經(jīng)營要求，形成的對配送的資源保證。配送的優(yōu)勢之一就是可以集中若干用戶的需求進(jìn)行一定規(guī)模的備貨。（三）物流配送的流程物流配送的主要操作(1)備貨配送的準(zhǔn)備工作和基礎(chǔ)工作。具體看，現(xiàn)代零售業(yè)的管理重點是：ⅰ)實行“單品管理”，迅速制定經(jīng)營中的“暢銷品”與“滯銷品”，以此為基礎(chǔ)確定定貨商品的種類和數(shù)量。除此之外，推動無在庫經(jīng)營的原因是，由于消費行為的多樣化、個性化發(fā)展，商品品牌、品種、式樣的急劇增多，使零售商對顧客實際需求的預(yù)測十分困難。但是，與此同時，由于政策、環(huán)境、房地產(chǎn)價格等原因，店鋪的規(guī)模和倉庫規(guī)模不可能無限擴大，特別是在大都市中，由于人口密度大、地價高昂、消費更新快、環(huán)境規(guī)制嚴(yán)格等原因，更加限制了倉儲點和倉儲空間的擴大，在這種情況下，只有提高店內(nèi)管理效率，通過加快商品周轉(zhuǎn)來抵消倉儲空間不足等問題。伴隨著連鎖經(jīng)營的興起，配送服務(wù)的重要性越來越為人們所關(guān)注。零售商向連鎖經(jīng)營發(fā)展的趨勢在傳統(tǒng)的流通模式下，商品從制造商生產(chǎn)出來后，經(jīng)由層層的批發(fā)商再到零售商，最后到達(dá)消費者手上，批發(fā)商在此扮演著整個通路的樞紐作用。此外，基本生活品在全社會普及之后，商品在質(zhì)量上的稍微改進(jìn)或價格的稍微降低都不能大量激發(fā)消費者的購買欲望，因而能開發(fā)出具有爆發(fā)性需求規(guī)模的革新產(chǎn)品也會越來越困難。但是隨著消費個性化、多樣化的發(fā)展，原來那種商品在一部分人中開始流行后，大家爭相購買的情況會越來越少，而且流行商品的生命周期也越來越短。生產(chǎn)商生產(chǎn)策略的轉(zhuǎn)變在傳統(tǒng)消費模式中，當(dāng)新產(chǎn)品被廠家研制、開發(fā)出來后，通過各種各樣的媒體、特別是電視廣告等促銷手段的運用和商業(yè)推廣，其一般能喚起全國規(guī)模的需求，這種營銷模式背后隱含的是消費者具有“與他人一致”的消費意識。伴隨著這種生活觀念的變化，在經(jīng)濟(jì)社會向國際化、信息化急劇轉(zhuǎn)變的基礎(chǔ)上，消費者價值觀趨于多元化和多樣化，喜歡購買具有差別化的商品。（二）物流配送產(chǎn)生的原因配送作為先進(jìn)的物流形式，它的產(chǎn)生以及推廣并不是偶然的，而是隨著現(xiàn)代商業(yè)經(jīng)營環(huán)境和經(jīng)營形式的變化而出現(xiàn)的。 (7)以最“合理的方式”的提法是基于這樣一種考慮:過分強調(diào)“按用戶要求”是不妥的，受用戶本身的局限，要求有時候存在不合理性，在這種情況下會損失自我或雙方的利益。配送企業(yè)的地位是服務(wù)地位而不是主導(dǎo)地位，不能從本企業(yè)利益出發(fā)，而應(yīng)從用戶利益出發(fā)，在滿足用戶利益基礎(chǔ)上取得本企業(yè)的利益。(6)配送以用戶的要求為出發(fā)點“按用戶的訂貨要求”明確了用戶的主導(dǎo)地位。(5)配送是市場經(jīng)濟(jì)產(chǎn)物配送是在市場經(jīng)濟(jì)條件下，在“供大于求”的買方市場環(huán)境中所派生的一種形式。如果不進(jìn)行分揀、配貨，有一件運一件，需要一點送一點，這就會加大送貨成本。ⅲ)配送依靠現(xiàn)代生產(chǎn)力，依靠科技進(jìn)步支撐，實現(xiàn)對用戶的送貨服務(wù)。其區(qū)別主要在于:ⅰ)一般送貨可以是一種偶然的行為，而配送卻是一種體制行為，是市場經(jīng)濟(jì)的一種體制形式。(2)配送的實質(zhì)是送貨配送的主要經(jīng)濟(jì)活動，尤其是接近顧客的經(jīng)濟(jì)活動是送貨。對于現(xiàn)代企業(yè)而言，“接近顧客”是至關(guān)重要的。配送不是單純的運輸或送貨，而是運輸與其它活動的組成，除了各種“運”、“送”活動外，還要從事大量的集貨、分貨、配貨、配裝等工作，是配與送的結(jié)合。一般認(rèn)為物流配送是指物流過程的中轉(zhuǎn)型送貨(也稱為二次輸送、支線輸送、終端輸送)。美國《物流管理供應(yīng)鏈過程一體化》表述:實物配送這一領(lǐng)域涉及將制成品交給顧客的運輸。日本工業(yè)標(biāo)準(zhǔn)表述，將貨物從物流結(jié)點送交收貨人。因此，將物流配送車輛調(diào)度問題作為研究對象具有一定的理論和現(xiàn)實意義。在現(xiàn)實應(yīng)用中，由于Scheduling涉及的內(nèi)容和關(guān)鍵技術(shù)比Routing寬泛，因此絕大多數(shù)研究者的主要研究興趣集中在Scheduling問題上，且主要對車輛調(diào)度問題(Vehicle Scheduling Problem簡稱VSP)開展廣泛的研究。國外將物流配送車輛調(diào)度問題歸結(jié)為VRP ( Vehi